13
In coding theory, the quantity you are looking for is called $A_q(n, d)$, where $n$ is the length of vectors, $d$ is the minimum distance between them, and $q$ is the alphabet size (omitted when $q=2$). Characterizing $A_q(n,d)$ is a challenging open problem (with many basic questions remaining unanswered) but various asymptotic and non-asymptotic upper and ...
10
The probability of error when sampling $f(x)$ is $\delta$ when $x$ is chosen at random. Using self-correction, the probability of error is $2δ$ for all $x$ (not only random $x$)
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
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 ...
7
Yes. For example, a Reed-Solomon code contains a BCH code, which is a binary linear code, as a sub-code. These are called subfield-subcodes.
7
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 ...
6
Cayley graphs of codes and derandomized code products can be a good example. See the following thesis (Chapter 6) for details and references: http://library.epfl.ch/en/theses/?nr=3816
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
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
For the benefit of the others, the minimum code distance problem for codes over $\mathbb{F}_2$ is: given a matrix $H$ ($m$ by $n$, with elements from $\mathbb{F}_2$) and a positive integer $w$, does there exist a vector $x$ such that $Hx = 0$ and the hamming weight (number of 1's) of $x$ is at most $w$.
Since both max ind set and the minimum distance of a ...
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
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 ...
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 ...
4
I really don't think that there is a known algorithm to be optimal. In fact, there is a major conjecture about how effective a set of code words can be, see: http://arxiv.org/abs/0709.2598
(the name I knew for affix code is fix-free code). If an algorithm was proved to be optimal, then most probably it would also solve (or disproof) this conjecture as well.
4
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 "...
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
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.
3
There are known worst-case hardness results about ML decoding (for general and specific families of codes such as Reed-Solomon), computing or approximating minimum distance of codes, and so on. However there is a great room for improvement in these directions and several seemingly intractable problems are not analyzed yet.
There are coding theoretic ...
3
Consider $p=2q$, $q\ge 1$.
Asymptotically, the quantity you are after is $2^{4q-2}$.
First, let's prove a lemma of general interest.
Lemma $(2^{2q}/\sqrt{\pi q})/1.136 < \binom{2q}{q} < 2^{2q}/\sqrt{\pi q}$.
Proof: Recall the Robbins bounds
$$
n! = \sqrt{2\pi}n^{n+1/2}e^{-n}e^{r_n},
$$
where $1/(12n+1) < r_n < 1/(12n)$.
This gives
$$
\binom{...
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 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 ...
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
Vasili, I think a good reference is anything by Raymond Yeung (he is one of the inventors of network coding).
The following is one of the most famous monographs on the subject:
R. W. Yeung, S.-Y. R. Li, N. Cai, and Z. Zhang, Network Coding Theory, now Publishers, 2005
http://iest2.ie.cuhk.edu.hk/~whyeung/netcode/monograph.html
IMHO it is a really good read.
...
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
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
