# Tag Info

## Hot answers tagged coding-theory

8 votes

### Research in Coding Theory

From a mathematical perspective: Try 1) Handbook of coding theory - Huffman and Pless 2) Fundamentals of Error-Correcting Codes - Huffman and Pless 3) Introduction to coding theory - Ron ...
• 12.5k
7 votes

### Minimum distance of a code

The problem for an arbitrary binary code is NP-hard. Reference: Alexander Vardy, “The Intractability of Computing the Minimum Distance of a Code,” IEEE Trans. Inf. Thy., Vol. 43 pp. 1757-...
• 23.5k
7 votes
Accepted

### Complexity of finding automorphism group of code

By taking direct sum of codes (given their two generator matrices $G_1, G_2$, consider the block matrix $G_1 \oplus G_2 = \begin{bmatrix} G_1 & 0 \\ 0 & G_2 \end{bmatrix}$), finding the ...
• 35.6k
6 votes
Accepted

### How many different Huffman encoding for a given number of symbols

The answer is $C_{n-1} n!$ . That is, the $(n-1)$st Catalan number times $n$ factorial. There are $C_{n-1}$ ways of making a complete binary tree with $n$ leaves, and there are $n!$ ways of assigning ...
• 23.5k
6 votes
Accepted

### Relation between group theory and information theory

Sadly, group structure is nearly so limited that there isn't much one can do with it to be of use in information theory, thus the literature is prone to be fairly sparse. Even Abelian groups aren't ...
6 votes

• 6,940
4 votes

### Research in Coding Theory

Lecture notes of the course "An Algorithmic Introduction to Coding Theory," by Madhu Sudan. Publication Date: 2001. The first chapter offers useful comments regarding several textbooks on coding ...
• 182
4 votes
Accepted

### Are there Similar Distance Binary Error Correcting Codes?

Every $\epsilon$-biased set gives a code whose minimal relative distance is $0.5 - \epsilon$ and maximal relative distance is $0.5 + \epsilon$. To see it, write the elements of the set as the rows of ...
• 5,055
4 votes
Accepted

### Distance of arbitrary vectors to Hadamard code

What you are asking is the covering radius of the Hadamard code. I am not sure what the answer is but the covering radius of the punctured Hadamard code is at least $\frac{N}{2} - \frac{\sqrt{N}}{2}$, ...
4 votes

### Relation between group theory and information theory

Reference Goppa's information theory work. http://iopscience.iop.org/article/10.1070/RM1984v039n01ABEH003062/meta;jsessionid=2978C0F66C0E4C77833FEDFE7B511F98.c1.iopscience.cld.iop.org [CITATION] ...
• 12.5k
4 votes
Accepted

### Is subtractive dithering the optimal algorithm for sending a real number using one bit?

Note: See the edit at the bottom for an argument showing that there is an unbiased algorithm which has variance strictly lower than $1/12$ for all $x \in [0,1]$. We can at least prove that if $x$ is ...
• 366
3 votes
Accepted

### Can Quarter-Subset Membership be decided space-efficiently?

I assume from the discussion that you are not actually interested in work space as claimed, but in total space including the size of the input. (Otherwise the trivial $n$-bit encoding scheme can be ...
• 14.7k
3 votes

### Approximation algorithms for min vector subset-sum over GF(2)

Dumer, Miccancio and Sudan showed that the minimum distance of a linear code is not approximable to any constant factor in randomized polynomial time, unless $\mathsf{NP} = \mathsf{RP}$. The minimum ...
• 6,940
3 votes

### Question about "typical set" in Shannon's source coding theorem

$S_δ$ is not a subset of the typical set. As you mentioned, the most probable element is a member of $S_δ$ but it is not necessarily a member of the typical set. The only reason to use the typical ...
• 467
3 votes
Accepted

### Source Coding Theorem: what happen when we go below N*H(x) bits?

It's not clear exactly what your question is. What the textbook is talking about is the strong converse to Shannon's source coding theorem, but rate distortion theory is another part of information ...
• 23.5k
3 votes
Accepted

### Subspace-evasive set performance in the random case

Here's a quick calculation. For a fixed affine subspace $H$ of dimension $k$, the probability that a random point falls in $H$ is $1/q^{n-k}$. The probability that at least $c$ points in $S$ fall in ...
• 6,940
3 votes

### Information and Coding Theory Texts

Both texts in the other answer are great texts, and the Guruswami, Rudra, Sudan book is more based in the TCS approach to coding theory, which may be relevant to the potential reader. The books below ...
• 1,966
2 votes

### Research in Coding Theory

My favorites for the first part of your question: Neal Koblitz: "A Course in Number Theory and Cryptography" $\rightarrow$ Very good introduction for mathematical treatment Oded Goldreich: "The ...
• 490
2 votes

### Explanation of polar decoding?

Shor is probably referring to this fantastic lecture by Emre Telatar that walks you through the steps in polar coding. Do watch it! In doing so, you shall see that the best mental model to have in ...
• 21
2 votes

### Bivariate low-degree polynomial testing of Polishchuk-Spielman

If I understand it correctly, Gauss's lemma implies that that $P$ and $E$ have a non-trivial common factor over $\mathbb{F}[x,y]$. But in the beginning of the proof of Lemma 8 they assume without ...
• 1,877
2 votes

### Research in Coding Theory

excellent 50p survey by leading expert/member Luca Trevisan from 2004 also tracking recent/latest research in the field Some Applications of Coding Theory in Computational Complexity sections: ...
• 10.8k
2 votes

### Good codes decodable by linear-sized circuits?

You should look at Tornado codes {1}, which, for any $R$ and $\epsilon>0$ and large enough $n$ can be designed to recover (with high probability) from a loss of a $(1-R)(1-\epsilon)$ fraction of ...
2 votes

### Using error-correcting codes in theory

Error-correcting code have had applications in property testing: Functional property testing: Showing tolerant testing can be quite hard: Tolerant Versus Intolerant Testing for Boolean Properties, ...
2 votes

### Determining the distribution of results of a simple algorithm

I suspect you won't get a closed form solution for the distribution you're looking for. Think of the seemingly easier problem where $k$ is always chosen to be exactly $2$, and where you get the set \$\{...
• 1,101

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