Linear binary code 

Description

An \((n,2^k,d)\) linear code is denoted as \([n,k]\) or \([n,k,d]\), where \(d\) is the code's distance. Its codewords form a linear subspace, i.e., for any codewords \(x,y\), \(x+y\) is also a codeword. A code that is not linear is called nonlinear.

Linear codes can be defined in terms of a generator matrix \(G\), whose rows form a basis for the \(k\)-dimensional codespace. Given a message \(x\), the corresponding encoded codeword is \(G^T x\). The generator matrix can be reduced via coordinate permutations to its standard or systematic form \(G = [I_k~A]\), where \(I_k\) is a \(k\times k\) identity matrix and \(A\) is a \(k \times (n-k)\) binary matrix.

Protection

Distance \(d\) of a linear code is the number of nonzero entries in the (nonzero) codeword with the smallest such number. Corrects any error set for which no two elements of the set add up to a codeword.

Linear codes admit a parity check matrix \(H\), whose columns make up a set of parity checks, i.e., a maximal linearly independent set of vectors that are in the kernel of \(G\). It follows that \begin{align} G H^{\text{T}} = 0 \mod 2~. \tag*{(1)}\end{align}

The decision problem corresponding to finding the minimum distance is also \(NP\)-complete [1], and approximating the weight enumerator is \(\#P\)-complete [2].

Rate

A family of linear codes \(C_i = [n_i,k_i,d_i]\) is asymptotically good if the asymptotic rate \(\lim_{i\to\infty} k_i/n_i\) and asymptotic distance \(\lim_{i\to\infty} d_i/n_i\) are both positive.

Decoding

Decoding an arbitary linear binary code is \(NP\)-complete [3].Slepian's standard-array decoding [4].Recursive maximum likelihood decoding [5].Transformer neural net for soft decoding [6].

Notes

Tables of bounds and examples of linear codes for various \(n\) and \(k\), extending code tables by A. E. Brouwer [7], are maintained by M. Grassl at this website.

Parents

Children

Cousins

  • Binary linear LTC — Linear binary codes with distances \(\frac{1}{2}n-\sqrt{t n}\) for some \(t\) are called almost-orthogonal and are locally testable with query complexity of order \(O(t)\) [9]. This was later improved to codes with distance \(\frac{1}{2}n-O(n^{1-\gamma})\) for any positive \(\gamma\) [10], provided that the number of codewords is polynomial in \(n\).
  • Construction-\(A\) code — Every binary linear code yields a lattice code under Construction \(A\).
  • Single parity-check (SPC) code — Any \([n,k,d]\) code with odd distance can be extended to an \([n+1,k,d+1]\) code by adding a bit storing the sum of codeword coordinates.
  • Binary Varshamov-Tenengolts (VT) code — By adapting a construction of Tenengolts [11], binary VT codes can be modified to yield slightly longer linear codes [12].
  • Slepian group-orbit code — Any length-\(n\) binary linear code can be used to define a diagonal subgroup of \(n\)-dimensional rotation matrices with \(\pm 1\) on the diagonals via the antipodal mapping \(0\to+1\) and \(1\to-1\). The orbit of this subgroup yields the corresponding Slepian group-orbit code; see [8; Thm. 8.5.2].
  • Binary PSK (BPSK) code — Concatenating binary linear codes with BPSK yields a standard way of digitizing the analog AGWN channel [13; Ch. 29].
  • Entanglement-assisted (EA) QECC — Any linear binary code can be used to construct an EAQECC.
  • Spacetime circuit code — The set of measurement outcomes of a Clifford circuit can be made into a classical binary linear code. Error syndromes of the spacetime circuit code can be used to obtain the parity checks of the outcome code.
  • EA qubit stabilizer code — Any linear binary code can be used to construct an EA qubit stabilizer code.
  • Qubit CSS code — Construction uses two related binary linear codes \(C_X\) and \(C_Z\).
  • Qubit stabilizer code — Qubit stabilizer codes are the closest quantum analogues of binary linear codes because addition modulo two corresponds to multiplication of stabilizers in the quantum case.

References

[1]
A. Vardy, “The intractability of computing the minimum distance of a code”, IEEE Transactions on Information Theory 43, 1757 (1997) DOI
[2]
M. N. Vyalyi, “Hardness of approximating the weight enumerator of a binary linear code”, (2003) arXiv:cs/0304044
[3]
E. Berlekamp, R. McEliece, and H. van Tilborg, “On the inherent intractability of certain coding problems (Corresp.)”, IEEE Transactions on Information Theory 24, 384 (1978) DOI
[4]
D. Slepian, “Some Further Theory of Group Codes”, Bell System Technical Journal 39, 1219 (1960) DOI
[5]
Y. S. Han et al., “Maximum-likelihood Soft-decision Decoding for Binary Linear Block Codes Based on Their Supercodes”, (2014) arXiv:1408.1310
[6]
Y. Choukroun and L. Wolf, “Error Correction Code Transformer”, (2022) arXiv:2203.14966
[7]
Andries E. Brouwer, Bounds on linear codes, in: Vera S. Pless and W. Cary Huffman (Eds.), Handbook of Coding Theory, pp. 295-461, Elsevier, 1998.
[8]
T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
[9]
T. Kaufman and S. Litsyn, “Almost Orthogonal Linear Codes are Locally Testable”, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05) DOI
[10]
T. Kaufman and M. Sudan, “Sparse Random Linear Codes are Locally Decodable and Testable”, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07) (2007) DOI
[11]
G. M. Tenengolts, Class of codes correcting bit loss and errors in the preceding bit (translated to English), Automation and Remote Control, 37(5), 797–802 (1976).
[12]
N. J. A. Sloane, “On Single-Deletion-Correcting Codes”, (2002) arXiv:math/0207197
[13]
A. Lapidoth, A Foundation in Digital Communication (Cambridge University Press, 2017) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: binary_linear

Cite as:
“Linear binary code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/binary_linear
BibTeX:
@incollection{eczoo_binary_linear, title={Linear binary code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/binary_linear} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/binary_linear

Cite as:

“Linear binary code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/binary_linear

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/bits/binary_linear.yml.