53 votes
Accepted

Huffman encoding: why is there no need for a separator?

You don't need a separator because Huffman codes are prefix-free codes (also, unhelpfully, known as "prefix codes"). This means that no codeword is a prefix of any other codeword. For example, the ...
David Richerby's user avatar
35 votes

Is UTF-8 the final character encoding for all future time?

UTF-8 might not last forever, but you probably don't have to worry too much. Two universal truths: We can't predict the future. Nothing lasts forever, especially in software. But that doesn't mean ...
Bernhard Barker's user avatar
28 votes
Accepted

Why is this code uniquely decodable?

Your code has the property that if you reverse all codewords, then you get a prefix code. This implies that your code is uniquely decodable. Indeed, consider any code $C = x_1,\ldots,x_n$ whose ...
Yuval Filmus's user avatar
19 votes

Is UTF-8 the final character encoding for all future time?

When it comes to software, the future always means needing to handle more data--- bigger files, and more of them in a shorter period of time. How does UTF-8 processing scale in those situations? UTF-...
Kyle Jones's user avatar
  • 8,091
13 votes

Huffman encoding: why is there no need for a separator?

It's helpful to imagine it as a tree. You are simply traversing the tree until you hit a leaf node, and then restarting from the root. From the algorithm which does huffman coding, you can see that ...
crackpotHouseplant's user avatar
12 votes
Accepted

Optional prefix code for the naturals

I wrote a paper on this. The short answer is that there is no optimal encoding, nor even an optimal sequence of better and better encodings. Kraft's inequality states that there is a prefix code with ...
Yuval Filmus's user avatar
11 votes

Why the 127 encodings of ASCII needed to be extended to 256?

ASCII has 128 characters. Many countries had similar encodings for 128 characters. That is all history. Nobody uses ASCII anymore. There was a phase with lots of different encodings for more than 128 ...
gnasher729's user avatar
10 votes

Is UTF-8 the final character encoding for all future time?

UTF-8 might not last forever, but if you permit long UTF-8 again, it will outlast all other encodings that exist today. I have heard it projected that we will eventually run out of UTF-16 codepoints, ...
Joshua's user avatar
  • 390
9 votes
Accepted

Does a binary code with length 6, size 32 and distance 2 exist?

Yes, there is such a set. You are actually on the right track to find the following example. Let $C = \{c : |c|=6 \text{ and there are even number of 1's in c}\}$. You can check the following. $|C|=...
John L.'s user avatar
  • 39k
9 votes

Is UTF-8 the final character encoding for all future time?

UTF-8 is an elegant hack to remain backward compatible with ASCII and trivially compatible with Latin-1, which were both widely entrenched when Unicode started to take hold. UTF-8 can be extended ...
Adrian McCarthy's user avatar
8 votes
Accepted

What is the name of the following binary encoding?

Your encoding is not self-terminating, which makes it somewhat less useful than encodings such as universal codes. Given an integer $n \geq 0$, write $n+2$ in binary without leading zeroes, and remove ...
Yuval Filmus's user avatar
7 votes

Does a binary code with length 6, size 32 and distance 2 exist?

All words of even parity from a linear code with $2^{n-1}$ codewords and minimum distance $2$. More generally, if $A_2(n,d)$ is the maximum size of a code of length $n$ and minimum distance $d$, then ...
Yuval Filmus's user avatar
7 votes

Is UTF-8 the final character encoding for all future time?

Your question appears to slightly conflate two related concepts (as people often do): Unicode is a standard, whose primary part is a "coded character set" - a list of "code points", and a lot of ...
IMSoP's user avatar
  • 501
6 votes

Why the 127 encodings of ASCII needed to be extended to 256?

There are a few other good reasons to expand from 7-bit ASCII, but since you ask specifically about foreign languages, I want to tell you about that angle. English has words with diacritical marks, ...
kviiri's user avatar
  • 1,227
6 votes
Accepted

Why does the BOM consist of two bytes instead of one for example in encoding utf-16

The BOM started out as an encoding trick. It was not part of Unicode, it was something that people discovered and cleverly (ab)used. Basically, they found the U+FEFF Zero width non-breaking space ...
Jörg W Mittag's user avatar
5 votes
Accepted

Understanding the binary and hexadecimal representations of UTF-8

Where the 21 bits come from: The idea of unicode is based on the Universal Coded Character Sets (short UCS). It's a concept for a 31bit character set ordered as a 4D hypercube where the first three ...
Burgberg's user avatar
5 votes

Is there any practical trick to mentally count in Gray code?

I have a solution that I just found looking at the patterns, and I checked the pattern up to decimal 31 or binary 11111 or Gray 10000, and it worked quite fine, and I am confident enough the answer ...
Krischal Khanal's user avatar
5 votes

Defining computable functions on arbitrary sets

Effective model theory studies computable structures. The collection of all finite trees is a two-sorted computable structure in which one sort consists of vertices (which can be identified with the ...
Yuval Filmus's user avatar
5 votes

Why is this code uniquely decodable?

If I give you any message that you are supposed to decode, then you can do the following: Reverse the message, starting with the last bit instead of the first bit. Reverse the code words. Decode the ...
gnasher729's user avatar
5 votes

Is UTF-8 the final character encoding for all future time?

I'm frankly confused about why UTF-16 and UTF-32 etc. exist at all UTF-16 exists because Unicode was originally supposed to be a fixed-width 16-bit encoding and many systems were designed during this ...
Peter Green's user avatar
4 votes

When would the worst case for Huffman coding occur?

According to NIST: The worst case for Huffman coding (or, equivalently, the longest Huffman coding for a set of characters) is when the distribution of frequencies follows the Fibonacci numbers. For ...
Johan's user avatar
  • 1,080
4 votes
Accepted

Prefix encoding of algebraic data types

A code is prefix-free if there does not exist any distinct two values v, w such that ...
D.W.'s user avatar
  • 159k
4 votes

Can nested structures be encoded more "readably" with a single delimiter?

\n and \t would get the job done as best as I could tell. In memory they're each only a character, but visually they offer a lot ...
ryan's user avatar
  • 4,511
4 votes
Accepted

Why encoding of graph in adjacency matrix is $\Omega (\sqrt n)$?

An $m\times m$ adjacency matrix requires $m^2$ bits, and $m=\sqrt{n}$ is just the solution to $m^2 = |\langle G\rangle| = n$. The point of the $\Omega$ is that a reasonable encoding doesn't have ...
David Richerby's user avatar
4 votes

Defining computable functions on arbitrary sets

Unfortunately, as Raphael says, the answer is no. The formalist answer is that computability is defined for functions $f:\{0,1\}^* \to \{0,1\}$; it's not defined for functions on other domains. A ...
D.W.'s user avatar
  • 159k
4 votes
Accepted

Period of sum of two periodic sequences

If you sum a sequence with period $a$ and a sequence with period $b$, then you get a sequence which is $\mathsf{LCM}(a,b)$-periodic. But the new sequence might have a smaller period, as the following ...
Yuval Filmus's user avatar
4 votes

Why the 127 encodings of ASCII needed to be extended to 256?

The question of how foreign languages justifies expanding the encoding in actual usage is well explained by earlier answers. The question of why foreign languages would affect the American Standard ...
Yufan Lou's user avatar
  • 128
3 votes

How to encode a sequence of non-decreasing integers with an integer without redundancy, loops, and recursions

Let $\mathcal{C}(n,m)$ denote the set of sequences you are interested in, namely non-decreasing sequences of length $n$ consisting of integers from $\{0,\ldots,m\}$, and let $C(n,m) = |\mathcal C(n,m)|...
Yuval Filmus's user avatar
3 votes
Accepted

Encode an ascii string in base 15

Let's take a different view angle. The problem is not really about encoding something like "decimals numbers" 0..127 into base-15 (which is messy). It's about converting a base-127 string into base-...
jvb's user avatar
  • 221

Only top scored, non community-wiki answers of a minimum length are eligible