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 ...
- 81.4k
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 ...
- 21.7k
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 ...
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 ...
- 21.7k
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|=...
- 38.6k
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 ...
- 275k
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 ...
- 275k
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),...
- 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, ...
- 275k
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-...
- 275k
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 ...
- 28.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 ...
- 275k
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.
...
- 275k
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 ...
- 9,425
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.
...
- 13.3k
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.♦
- 156k
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$...
- 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 ...
- 2,092
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 ...
- 20.6k
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, ...
- 28.4k
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 ...
- 275k
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.♦
- 156k
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 ...
- 276
3
votes
coding theory- perfect codes
Guidelines for the future: start with reviewing the definitions.
According to Wolfram, a perfect code (with distance $d=2e+1$) is one such that "for every possible word $w_0$ of length $n$ with ...
- 20.6k
3
votes
Why is Hamming Weight (in the CRC context) independent from the data?
Let us call a data vector of some fixed length together with its CRC a codeword. Since CRC is a linear code, the set of codewords is closed under XOR (this is the definition of linear code).
Let $x$ ...
- 275k
3
votes
Accepted
Number of words within Hamming distance $\delta$
That's an inaccuracy. If $\delta < 1/2$ is constant then it is the case that $\sum_{k=0}^{\delta m} \binom{m}{k} = O\left(\binom{m}{\delta m}\right)$, since the binomial coefficients increase very ...
- 275k
3
votes
Accepted
Need help understanding textbook solution
Try to think of it that way. A code $C$, is just a subspace. A generator matrix is simply one basis of that subspace (i.e., each row is a basis element).
So in order to create the subspace $C_1+C_2$, ...
- 20.6k
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 ...
- 3,256
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, ...
- 275k
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 ...
- 275k
Only top scored, non community-wiki answers of a minimum length are eligible