Tag Info

Hot answers tagged coding-theory

91

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

50

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 ...

36

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 ...

28

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 ...

19

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 ...

15

What you are missing is that you need to consider all bits of size 3 or less. That is: if in a compression scheme for bits of size 3 or less we compress one of the 3-bit strings to a 2-bit string, then some string of size 3 or less will have to expand to 3 bits or more. A losless compression scheme is a function $C$ from finite bit strings to finite bit ...

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

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 ...

10

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 ...

10

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 ...

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 ...

8

Many widely used codes for binary data are concatenated codes, which are composed by using two error-correcting codes. The inner code is over a binary alphabet, and the outer code is over an alphabet whose symbols correspond to the codewords of the inner code. This allows you to use the superior power of larger alphabet sizes to encode binary messages ...

7

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

Just an additional note to Andrej's good answer: You can also take a look to to Kolmogorov complexity: Definition: Given a string $s$, its Kolmogorov complexity $C(s)$ relative to a fixed model of computation is the length of the shortes program (e.g. Turing machine) that outputs $s$. Informally $C(s)$ measures its information content or its degree of ...

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.

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

Well, these examples are not easy to read, by they are indeed correct. e.g.1: The word to code has 4 bits, and lets call them $b_1 b_2 b_3 b_4$. To this "data" word add 3 parity bits (adding is over $GF(2)$): $p_1 = b_1 \oplus b_2 \oplus b_3$, $p_2 = b_1 \oplus b_2 \oplus b_4$, and $p_3 = b_1 \oplus b_3 \oplus b_4$. [remark: for odd parity, add "1"...

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

The probability $P$ that a uniformly chosen random prime between $1$ and $n^c$ satisfies $a \equiv b \mod{p}$ is the number of primes in this range that satisfy $a \equiv b \mod{p}$ divided by the total number of primes in this range. Writing $[C] = 1$ if $C$ is true and $[C] = 0$ if $C$ is false, and $\pi(x)$ for the number of primes less than $x$: P = \...

4

Your counterexample is wrong. Your list of compressed values has some hidden information which indeed makes the average length longer than 3 bits. The extra information is the length of the output string. With our eyes we can see from your table that the first output string is only 1 bit long, and the others are 3 bits, but you're cheating if you don't ...

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 splitting sequences of ...

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 \...

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