97 votes
Accepted

Is Morse code without spaces uniquely decipherable?

The following are both plausible messages, but have a completely different meaning: ...
user avatar
  • 1,064
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 ...
user avatar
38 votes

Is Morse code without spaces uniquely decipherable?

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 ...
user avatar
30 votes

Is Morse Code binary, ternary or quinary?

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, ...
user avatar
  • 402
22 votes
Accepted

Is Morse Code binary, ternary or quinary?

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 ...
user avatar
  • 19.1k
17 votes

Is Morse code without spaces uniquely decipherable?

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: ...
user avatar
14 votes
Accepted

Is there a generalization of Huffman Coding to Arithmetic coding?

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 ...
user avatar
  • 19.1k
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 ...
user avatar
12 votes
Accepted

PRNG for generating numbers with n set bits exactly

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 ...
user avatar
  • 19.1k
11 votes

Is Morse code without spaces uniquely decipherable?

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 ...
user avatar
11 votes

Hamming distance required for error detection and correction

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 ...
user avatar
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|=...
user avatar
  • 34.8k
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 ...
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 ...
user avatar
6 votes
Accepted

What is the reason behind a specific ordering of the rows in the generator matrix for Hamming codes?

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),...
user avatar
  • 239
6 votes
Accepted

Subset of numbers whose XOR has least Hamming weight

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, ...
user avatar
6 votes

Smallest set of balls under hamming distance that covers all $n$-bit strings

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-...
user avatar
5 votes
Accepted

About codes over $\mathbb{F}_2$

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 ...
user avatar
5 votes

Is Morse Code binary, ternary or quinary?

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,...
user avatar
  • 1,230
5 votes
Accepted

How to decode multiple-digit gamma codes and get the gap sequence?

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 ...
user avatar
  • 313
5 votes

"Huffman coding is unsuitable for text files"?

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 ...
user avatar
  • 25.5k
4 votes

Is Morse code without spaces uniquely decipherable?

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 ...
user avatar
  • 10.8k
4 votes

Binary code with constraint

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 ...
user avatar
4 votes

How is the Varshamov-Tenegolts code decoded?

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. ...
user avatar
  • 20.4k
4 votes
Accepted

What is the algorithm for Shannon-Fano code? am I correct?

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 ...
user avatar
4 votes
Accepted

Existence of Hamming code

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. ...
user avatar
4 votes

Using Data Compression on the output of Data Compression

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 ...
user avatar
  • 9,325
4 votes
Accepted

Complexity of / best algorithm for finding the dichotomy that maximizes information gain?

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. ...
user avatar
  • 13.2k
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 ...
user avatar
  • 143k
4 votes
Accepted

Counting the number of multiples of number A that perfectly divides the number B

Start by checking whether $A$ divides $B$. If it doesn't, we're done, the answer is $0$. If it does, let $C = \frac{B}{A}$. The numbers you're looking for are all of the form $AM$ where $M$ divides $C$...
user avatar
  • 106

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