8
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 Roth
4) Algebraic Geometric Codes: Basic Notions - Vladut, Nogin and Tsfasman
5) Introduction to Coding Theory - Van Lint
6) Algebraic ...
8
This is a question of encoding and decoding constant-weight code. There are several possible efficient algorithms for that, that provide different efficiency benefits.
Here's a list of some papers on this field:
Tenkasi V. Ramabadran. A Coding Scheme for m-out-of-n Codes. IEEE Transactions on Communications, 38(8):1156–1163, August 1990.
Vitaly Skachek, ...
8
The "canonical" answer (not necessarily linear time) is to use what could be termed binomial encoding (this is probably the same solution given by Knuth). The idea is to interpret Pascal's identity $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ as stating that the code of those subsets not containing $n$ should fit into $[0,\binom{n-1}{k})$, while the ...
7
Here is a table of the best known (linear and non-linear) binary codes for distance 3, for $n \leq 512\,$. Distance 3 is equivalent to being able to correct one error. The table only gives you the number of codewords, but the references given in the table will tell you how to construct the codes themselves.
The best known codes for $n$ not in this table can ...
7
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--1766.
7
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 automorphism group is at least as hard as testing isomorphism of codes (also called code equivalence). The current best upper bound for testing equivalence of linear ...
6
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 these leaves to the symbols to get a Huffman code.
This sequence goes 2, 12, 120, 1680, 30240, and is listed in the Online Encyclopedia of Integer Sequences ...
6
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 enough structure.
Even basic abstract algebra texts which have some basic coding theory applications generally provide examples using field theory or linear ...
6
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\| > 0$, where $\|\cdot \|$ is the Euclidean norm. This is called a sphere packing because we can place a(n open) sphere of radius $d_{\mathcal{P}}/2$ at ...
5
I think the term is deletion channel. As the Wikipedia article says, this "should not be confused with the binary erasure channel".
5
Well, you could just use a two-way hash map between $S_k$ to $\{0,1\}^{\lceil\lg{{n}\choose{k}}\rceil}$. That's easily computable in each direction in time corresponding to the length of the input, but it uses a lot of space.
Knuth's "Pre-Fascicle 3a: Generating all combinations", as well as TaoCP, 7.2.1.3, Theorem L and exercise 17 explore the "...
5
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 from Unreliable Components", in Automata Studies, eds. C. Shannon and J. McCarthy, Princeton University Press, pp. 43–98
5
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 bits over a noisy channel. Over such a channel, it is usually not possible to send real numbers with arbitrary precision.
However, there have been some works ...
5
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
4
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 theory.
Available at http://people.csail.mit.edu/madhu/FT01/scribe/overall.pdf.
4
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 $m$ is the codeword length and $q$ is the query complexity. A formal argument appears in Section 3.4 of Kerenidis and de Wolf's paper.
4
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}$, i.e. any Boolean vector is at most $\frac{N}{2}-\frac{\sqrt{N}}{2}$ Hamming distance away from some code word of the punctured Hadamard code. The $O(\sqrt{N})$ ...
4
This is my (somewhat unorthodox) answer to the comparison between Huffman. Huffman and arithmetic codings. A Huffman code is only optimal if the frequency of the letters in the input alphabet are $2^{-k}$, for an integer $k$. Otherwise, there are internal nodes in the coding tree whose children have different weights. As a result, the output bit stream does ...
4
Reference Goppa's information theory work.
http://iopscience.iop.org/article/10.1070/RM1984v039n01ABEH003062/meta;jsessionid=2978C0F66C0E4C77833FEDFE7B511F98.c1.iopscience.cld.iop.org
[CITATION] Nonprobabilistic mutual information without memory
VD Goppa - Probl. Contr. Inform. Theory, 1975
I know no other work which uses group theory to frame information ...
4
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 chosen uniformly from $[0,1]$, then the average variance must be at least $\pi^2/64 - 1/12$. There is a dithering algorithm that achieves this average-case ...
3
Usually the question is interesting for constant alphabet sizes, since otherwise Reed-Solomon codes obviously achieve the Singleton bound.
For constant (but still large) alphabet sizes, there are explicit codes that "approximately" achieve the Singleton bound, and are thus also asymptotically good. See
Venkatesan Guruswami and Piotr Indyk. Linear time ...
3
This is not the best bound even for $q=2$; in fact, this is not the best bound derived from the Delsarte linear program; see the paper "On the optimum of Delsarte's linear program" by Samorodnitsky (1998).
Thus, a better analysis of the linear program is likely to improve the bounds over larger $q$. Even for $q=2$, this is a complicated analysis, so I don'...
3
An answer to the first question can be found in a paper by Schaefer and Umans, Completeness in the polynomial-time hierarchy: A compendium (2002).
In subsection "Coding and cryptology" (see p. 24), two $\Pi_2^p$-complete problems appear: checking an upper bound on the covering radius of a linear code, and deciding whether a linear code is $r$-identifying ($...
3
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 distance problem is the same as your problem if the $v_i$'s form the columns of the parity check matrix and $y = 0$.
3
$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 set instead of $S_δ$ is to make the proof of the source coding theorem easier. (See the paragraph at the top of page 84 in your book.) The typical set along with ...
3
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 theory relevant to this.
The strong converse says that if you try to compress information to fewer bits than the entropy, the probability that all of the ...
3
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 $H$ is at most:
$${q^{(1-\epsilon)n} \choose c} \cdot \frac{1}{q^{(n-k)c}}\leq
\frac{q^{(n-\epsilon n) c}}{q^{(n-k)c}} = \frac{1}{q^{(\epsilon n -k)c}}$$
A ...
3
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 a matrix, and then define the code to be the span of the columns of the matrix. The $\epsilon$-biased property of the set is equivalent to saying that the ...
3
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 decoded in logarithmic space.)
Let $k$ be a sufficiently large constant, and consider the following encoding scheme for $X\subseteq\{0,\dots,n-1\}$. Split $\{0,\...
3
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 have been split into the "mainly information theory" and "mainly coding theory" subsets.
Information Theory:
For mathematical rigour, the ...
Only top voted, non community-wiki answers of a minimum length are eligible