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 ...
- 176
6
votes
Why can't codes be defined over infinite fields?
Sphere packings give a nice analogue of codes over $\mathbb{R}$. A sphere packing is a set $\mathcal{P} \subset \mathbb{R}^n$ such that $d_{\mathcal{P}} := \inf_{x,y \in \mathcal{P}, x \neq y} \|x - y\...
- 1,134
5
votes
Why can't codes be defined over infinite fields?
It is possible to define codes over infinite fields, but it is usually not as useful as codes over finite fields. The original motivation for error-correcting codes comes from the needs to transmits ...
- 5,055
5
votes
Accepted
Reference request: Classical analog of quantum threshold theorem
The classical theory of fault tolerance was pioneered by John von Neumann. I think this is the original reference:
von Neumann, J. (1956). "Probabilistic Logics and Synthesis of Reliable Organisms ...
- 5,366
5
votes
Information and Coding Theory Texts
Maybe not so math oriented but with math rigor:
Elements of Information Theory by Thomas M. Cover, Joy A. Thomas
Essential Coding Theory by Venkatesan Guruswami, Atri Rudra and Madhu Sudan
- 61
5
votes
Accepted
Reference request for linear algebra over GF(2)
Strangely, linear algebra specific to finite fields is best studied in textbooks on the theory of error-correcting codes (for example, MacWilliams and Sloane).
Pretty much all familiar notions in ...
- 4,011
5
votes
Accepted
Maximal uniquely decodable codes
Maximal implies sharp, even for uniquely decodable codes.
Proof: If there is some sequence of letters which will never appear in the middle of a concatenation of codewords, then we can add this ...
- 23.5k
4
votes
Accepted
Are there good locally decodable _erasure_ codes
Locally decodable codes and locally decodable erasure codes are qualitatively equivalent. Both imply $\Omega(m)$ many disjoint $q$-tuples from which one can recover a given message coordinate, where $...
- 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}$, ...
- 18k
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 ...
- 262
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