# Tag Info

## Hot answers tagged coding-theory

95

The following are both plausible messages, but have a completely different meaning: SOS HELP = ...---... .... . .-.. .--. => ...---.........-...--. I AM HIS DATE = .. .- -- .... .. ... -.. .- - . => ...---.........-...--.

53

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 codeword for "e" in your example is 10, and you can see that no other codewords begin with the digits 10. This means that you can decode greedily by reading the ...

37

Quoting David Richerby from the comments: Since ⋅ represents E and − represents T, any Morse message without spaces can be interpreted as a string in $\{E,T\}^*$ Further, since A, I, M, and N are represented by the four possible combinations of two morse characters (⋅-, ⋅⋅, --, -⋅, respectively), any message without spaces can also be interpreted as a ...

29

This answer isn't as long as it looks; this site just puts a lot of spacing between list items! Update: Actually it's getting pretty long... Morse Code isn't "officially" binary, ternary, quaternary, quinary, or even 57-ary (if I count correctly). Arguing about which one it is without context is not productive. It is up to you to define which of those five ...

20

Morse code is a prefix ternary code (for encoding 58 characters) on top of a prefix binary code encoding the three symbols. This was a much shorter answer when accepted. However, considering the considerable misunderstandings between users, and following a request from the OP, I wrote this much longer answer. The first "nutshell" section gives you the gist ...

17

It is enough to observe that certain short combinations of letters give ambiguous decodings. A single ambiguous sequence suffices, but I can see the following: ATE ~ P EA ~ IT MO ~ OM etc. As David Richerby notes in the comments, any letter is equivalent to a string of Es and Ts, which makes Morse Code ambiguous as a way of encoding arbitrary sequences of ...

14

Let's look at a slightly different way of thinking about Huffman coding. Suppose you have an alphabet of three symbols, A, B, and C, with probabilities 0.5, 0.25, and 0.25. Because the probabilities are all inverse powers of two, this has a Huffman code which is optimal (i.e. it's identical to arithmetic coding). We will use the canonical code 0, 10, 11 for ...

13

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 this sort of structure is created in the process. https://en.wikipedia.org/wiki/File:HuffmanCodeAlg.png

12

What you need is a random number between 0 and ${ 64 \choose n } - 1$. The problem then is to turn this into the bit pattern. This is known as enumerative coding, and it's one of the oldest deployed compression algorithms. Probably the simplest algorithm is from Thomas Cover. It's based on the simple observation that if you have a word that is $n$ bits long,...

11

Morse Code is actually a ternary code, not a binary code, so the spaces are necessary. If spaces were not there, a lot of ambiguity would result, not so much with the entire message, but with individual letters. For example, 2 dots is an I, but 3 dots is an S. If you are transcribing and you hear two dots, do you immediately write "I" or do you wait until ...

11

The Hamming distance being 3 means that any two code words must differ in at least three bits. Suppose that 10111 and 10000 are codewords and you receive 10110. If you assume that only one bit has been corrupted, you conclude that the word you received must have been a corruption of 10111: hence, you can correct a one-bit error. However, if you assume that ...

9

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|=32$. $d(u,v)\geq2$ for all $u,v\in C$, $u\not=v$. (In fact, $d(u,v)=2$ or 4 or 6.) Here are four related exercise, listed in the order of increasing difficulty. ...

8

There are zillions of papers in coding theory, proposing zillions of codes. Most of them are not used, due to several reasons: Some of the codes are non-constructive. Some of the codes don't have efficient decoding procedures. Some of the codes have bad parameters. The main reason, however, is that practitioners don't spend their time reading the coding ...

7

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 $A_2(n,2d) = A_2(n-1,2d-1)$.

6

Here's a more efficient way of doing it. Let's map all the strings of length $n$ into strings of length $n+O(\sqrt{n} \log n)$ with no consecutive string of $0$'s of length more than $\sqrt{n}$. We then add a string $1 0^{a}1$ at the end, where $a \geq \sqrt{n} + 1$. Our mapping isn't always going to give us the same length string, so $a$ can vary. How do ...

6

If a single-bit error correction is attempted, the ordering presented in the example guarantees that the syndrome vector (the result of the multiplication of the checking matrix and the received data), if interpreted as an integer, will indicate the position of the error. Otherwise, a lookup table would have to be used.

6

Your problem is known as calculating the minimal distance of a (binary) linear code, and is NP-hard, as shown by Vardi. It is even NP-hard to approximate within any constant factor, as shown by Dumer, Miccancio and Sudan.

6

The object you are looking for is known as a covering code. Finding the smallest covering code for a given radius is generally a difficult problem, just like its more well-known dual problem, error-correcting codes.

5

The above sequence it read as a concatination of 5 numbers: You start from the left side, read the first unary code. It let's you know what is the length of the first number. The 2nd number starts right after the 1st, and you interpet it the same way. First, read the first unary code, it is 1110 - so the first number is "1110:001", which is 9 The next ...

5

Despite my initial thoughts on this, it turns out this question can be formalized in a way that admits a fairly precise answer (modulo a couple of definition issues). The answer turns out to be 3 or 4, i.e. ternary or quaternary. The crowd-pleaser "everything goes from 2 to 57" answer is correct only in the sense that if someone asks you for a ...

5

A binary code is a set of vectors in $\mathbb{F}_2^n$ for some $n$. Presumably the context in which you encountered this construction is a motivation for it. It's a particular case of a more general construction known as a Cayley graph, though perhaps this particular case has a specific name. You are right that all arithmetic is done in $\mathbb{F}_2$. There ...

5

It's not unsuitable, it is just not optimal. That's because letters in human readable text are not independent, but quite strongly correlated. That correlation can be used to get huge savings. For example, the letters q and Q are almost always followed by u. Comma and period are almost always followed by a space character, and period space is almost always ...

4

a few notes not covered in other (good) answers but which dont generally research prior knowledge and cite any stuff (to me an intrinsic part of computer science). this general theory of CS falls into the category of text segmentation and also "word splitting"/ "disambiguation" although there the theory is a bit different, its about ...

4

Right, the code $VT_0(4)$ has Levenshtein distance (edit distance) of 4: to get from one codeword to another you must do 2 deletions and 2 insertions. Therefore, the code can correct one deletion. Indeed, if 101 was received, the only possible way to get this message assuming one deletion, is if 1001 was sent. Decoding can be done in several ways: The ...

4

Here is a lower bound and an asymptotically matching construction, at least for some ranges of the parameters. Denote by $m$ the number of columns, and suppose for simplicity that $p \leq n/2$. We start with a lower bound on $m$. Let $X$ be the encoding of symbol chosen uniformly at random. Let $X_1,\ldots,X_m$ be the individual coordinates, and let $w_i \... 4 You are confusing "Shannon coding" from "Shannon–Fano coding" (terminology could vary across sources). Per Wikipedia, Shannon–Fano coding is the algorithm you mention, while Shannon coding is any coding assigning a symbol occurring with probability$p_i$a codeword of length$\ell_i = \lceil \log_2 \frac{1}{p_i} \rceil$. Per Wikipedia, Shannon–Fano coding ... 4 The Hamming bound is an upper bound on the size of codes. It's not a tight bound in general, though in some specific cases it is achievable. Codes achieving the Hamming bound are called perfect codes. When the alphabet size is a prime power, all perfect codes are known: apart from some trivial cases (repetition codes, codes with one codeword, and codes ... 4 When we compress something the output is smaller than input (that is the purpose of compression, otherwise we do not use it or cope with bigger file). This can be achieved by various methods including (but not limited to) matching of substrings (dictionary compression) or frequency of characters (entropy compression, like Huffman encoding) or arithmetic ... 4 The information gain in that case depends only on the mass of$A$, and is maximized when$P(A)=\frac{1}{2}$. This probably shows why this definition of information gain is not very interesting. Suppose$X=\left\{x_1,...,x_n\right\}$and$P=\left(p_1,...,p_n\right)$. The information gain is defined as$IG(A)=H(X)-\left(P(A)H(A)+\left(1-P(A)\right)H\left(X\...

4

A code is prefix-free if there does not exist any distinct two values v, w such that encode(v) is a prefix of encode(w). So, to prove that your encoding is prefix-free, you start by considering two arbitrary distinct values v, w and demonstrate that encode(v) is not a prefix of encode(w). I suggest you use proof by induction on the "size" of the largest ...

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