7
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 ...
- 186
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-...
- 24.3k
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 ...
- 36.9k
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,204
6
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
- 181
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
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,350
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 ...
- 24.3k
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.8k
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 ...
- 376
4
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 ...
- 2,070
3
votes
Accepted
Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless?
Before we try to get into ergodic or whatever else, let's try to understand what phenomenon a mathematician or scientist is trying to (or could be trying to) model with AEP. Well
Asymptotic for ...
- 234
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 ...
- 16.9k
3
votes
Accepted
Theorem of Sudan, Trevisan and Vadhan about list-decoding
I don't think Step 4 works. The circuit $C_j^{\mathrm{Enc}(x)}$ takes $i \in [N]$ as input and outputs the $i$-th bit of $x$. For each $i \in [N]$, the circuit asks $\mathrm{poly}(\log N)$ queries ...
- 46
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,897
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
Minimum distance of a code
I hate to reopen an old topic but I just want to add for future searches that there is no way to do this in general unless you can logic-out the weight enumerators, but for a specific instance of a ...
- 21
2
votes
Bounds for maximum number of code-words in a ternary error correcting code with length n and distance d?
If you're not looking for asymptotic results, there are extensive tables that are maintained by researchers.
You can find them at www.codetables.de. Go to that webpage, and click "linear codes". They ...
- 24.3k
2
votes
Accepted
Bounds for maximum number of code-words in a ternary error correcting code with length n and distance d?
The exact answer is unknown in general. One standard upper bound for $q-$ary codes is the Singleton bound, which gives
$$|C|\leq q^{n-d+1},$$ and codes meeting this bound are called MDS.
A lower ...
- 2,070
2
votes
Accepted
Why are folded Reed Solomon Codes considered non linear?
Suppose we consider $s$-folded Reed-Solomon codes that are based on polynomials over a field $\mathbb{F} = \mathrm{GF}(p^t)$. Then the alphabet of those codes is of size $p^{t \cdot s}$. Hence, in ...
- 5,350
2
votes
Accepted
Families of LDPC codes with constant error fraction corrected
Here are a few examples:
There are the expander codes of Spielman (not to be confused with Sipser-Spielman):
http://www.cs.yale.edu/homes/spielman/Research/ITsuperc.pdf
There are the linear-time ...
- 5,350
2
votes
What are the general direction and target question in the field of quantum error correction?
One big open question is the existence of "good" quantum LDPC codes. These are stabilizer quantum error correcting codes with constant check weight, constant rate and linear distance. Most ...
- 839
2
votes
Survey on Quantum error correction
Try these:
Quantum Error Correction by Todd Brun
Quantum Error Correction: An Introductory Guide by Joschka Roffe
For surface codes, Dan Browne's lecture notes might help.
- 203
2
votes
Accepted
The noise distribution on $F_2^n$: probability of landing in a subspace versus a coset
The probability that $x \in C + e$ is equal to $2^n \langle T_\rho 1_{0}, 1_{C+e} \rangle$, where $T_\rho$ is the noise operator and $\rho = 1-2\epsilon>0$. Now
$$
2^n \langle T_\rho 1_0, 1_{C+e} \...
- 14.3k
2
votes
Are all linear-rate and -distance classical linear codes expanding?
Really cool question! This is a little bit on the handwavy side of things, but here is my take. The conclusion is that we can show the existence of an $\Omega(1)$-expander of size $\Theta(n)$, let me ...
- 41
1
vote
Reference request for linear algebra over GF(2)
As you mention, standard Linear Algebra books demonstrate the notions using infinite fields (usually the reals and the complex numbers). Pretty much, though, all the definitions are general enough to ...
- 25
1
vote
Accepted
Notation of sequences in rate distortion theory
In information theory notation, capital letters such as $X$ denote random variables, and lowercase letters such as $x$ mean their possible outcomes (i.e., fixed values). For example you can write the ...
- 4,011
1
vote
Accepted
weights in low density codes
Your question is somewhat ill-posed: given $n$ and $k$, it is easy to construct a Tanner graph with a 4-cycle and column weight at most 2.
Instead, you can ask the question of what is the maximum ...
- 839
1
vote
Accepted
Explicit Bits-back Coding (a.k.a. Free Energy Coding) applied to Gaussian mixtures
Apparently, no. This is a generalization where the relationship between $k$ and $i$ is stochastic (i.e. defined by a distribution and not deterministic).
To recover the original bits-back argument, we ...
- 139
Only top scored, non community-wiki answers of a minimum length are eligible