Skip to main content
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
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

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 ...
Pseudonym's user avatar
  • 22.1k
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
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
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),...
vsz's 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, ...
Yuval Filmus's 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-...
Yuval Filmus's user avatar
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 ...
gnasher729's user avatar
  • 30.1k
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 ...
Evil's user avatar
  • 9,455
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. ...
Yuval Filmus's user avatar
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. ...
Ariel's user avatar
  • 13.4k
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
  • 160k
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$...
RcnSc's user avatar
  • 106
4 votes
Accepted

Am I right that Reed-Solomon codes can be used to implement arbitrary-parity RAID schemes?

A Reed-Solomon code applied to 512-byte (4096-bit) sectors can support up to $n=2^{4096}$ drives in an array, of which any fraction may be parity drives. The limits of real-world RAID setups come from ...
benrg's user avatar
  • 2,112
3 votes

How do I calculate MDS codes?

It seems you are looking after (linear) MDS codes. A linear $[n,k,d]$-MDS code "partitions" the space into $2^k$ balls of size $2^n/2^k$ elements each, so that the minimal distance between any two ...
Ran G.'s user avatar
  • 20.7k
3 votes

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

No code other than E starts with 0000. No code other than i starts with 0001. And so on. As an extreme case, no code other than e starts with 01. You don't have things like E = 0000, space = 000, ...
gnasher729's user avatar
  • 30.1k
3 votes
Accepted

How many independent yes/no questions can be asked about a point in binary space (linear vs nonlinear codes)?

Linear codes which satisfy your requirement are known as linear MDS (maximum distance separable) codes. While there are no non-trivial (in your sense) binary linear MDS codes, there are such codes ...
Yuval Filmus's user avatar
3 votes
Accepted

Compactly representing integers when allowed a multiplicative error

Storing $x$ to within a $1+\epsilon$ approximation can be done with $\lg \lg n - \lg(\epsilon) + O(1)$ bits. Given an integer $x$, you can store $z = \text{Round}(\log_{1+\epsilon} x)$. $z$ is in ...
D.W.'s user avatar
  • 160k
3 votes
Accepted

Huffman Coding and Depth Calculation?

In each step of the Huffman coding algorithm the list of probabilities is being sorted and the 2 lowest of them are merged into a new node of the tree, resulting into a new probability. As for your ...
Sorrop's user avatar
  • 276
3 votes

PRNG for generating numbers with n set bits exactly

Very similar to Pseudonym's answer, obtained by other means. The total number of available combinations is approachable by the stars and bars method, so it will have to be $c=\binom{64}{n}$. The ...
André Souza Lemos's user avatar
3 votes

Kraft's inequality and Shannon's noiseless coding theorem for an encoding

I don't know what a "compact instantaneous binary encoding" is, but I'm guessing it's a prefix code that saturates Kraft's inequality. If so, your numbers don't correspond to a compact prefix code, ...
Yuval Filmus's user avatar
3 votes
Accepted

What is the complexity of Hamming nearest neighbor to a subspace ...?

Your problem is known as the nearest codeword problem, and it is NP-hard to approximate. See for example lecture notes of Madhu Sudan. The way to make this problem an NP-problem is to ask whether the ...
Yuval Filmus's user avatar
3 votes
Accepted

Parameters of a linear code

You're right, minimum distance is the minimal nonzero weight, thus 1. A basis is what you gave. There are many bases. And youre right on size and dimension as well. Edit: As pointed out in the other ...
kodlu's user avatar
  • 607
3 votes
Accepted

Minimum number of strings to cover entire space within Hamming distance

The object you are interested in is called a covering code. While less popular than error-correcting codes, covering codes share many of the same difficulties. In particular, there is little hope for ...
Yuval Filmus's user avatar
3 votes
Accepted

Sphere packing inequality for error-correcting codes

For a codeword $x$, let $B_k(x)$, the ball of radius $k$ around $x$, consist of all words at distance at most $k$ from $x$. Notice that $$|B_k(x)| = \sum_{i=0}^k \binom{m+r}{i}. $$ If the code ...
Yuval Filmus's user avatar
3 votes
Accepted

Coding for data compression with large target's symbol set (where the target symbol set is larger than the source symbol set)

Both arithmetic coding and asymmetric numeral systems can be done in arbitrary base $b$. Is it a right assumption that when the target symbol size is larger, the goal is to find a map from a ...
orlp's user avatar
  • 13.4k
3 votes

Understanding connection between length of codeword and hamming distance in Hamming code

The answer to both questions is the sphere-packing bound. Consider a binary code on $n$ bits with minimum distance $2d+1$ and $M$ codewords. Imagine surrounding each point of the code with a ball of ...
Yuval Filmus's user avatar
3 votes
Accepted

Name of binary encoding scheme for integer numbers

The technique idea is perfectly described in Yuval Filmus answer. Even if slightly different, it is called Truncated binary encoding in Wikipedia. I couldn't find an original source for that, apart ...
Costantino Grana's user avatar

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