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.

The automorphism group of a linear binary code is the largest subgroup of coordinate permutations that maps the code onto itself. Two linear binary codes are equivalent if the codewords of one code can be mapped into those of the other under a permutation [1; Ch. 8][2; Ch. 3].

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 [3], and approximating the weight enumerator is \(\#P\)-complete [4].

There are several standard procedures for increasing or decreasing the length of an \([n,k,d]\) code [1; Ch. 1]:

(1)

Puncturing: removing a coordinate to yield a code whose length is shorter by one and whose distance is \(\geq d-1\).

(2)

Expurgating: removing odd-weight codewords of a non-even-weight code to yield a code whose dimension is \(k-1\).

(3)

Augmenting: adding the all-ones codeword to a code without it to yield a code whose dimension is \(k+1\).

(4)

Lengthening: adding a the all-ones codeword and then adding a parity check to yield a code whose size and dimension increase by one.

(5)

Shortening: keeping only codewords which have a zero in a fixed coordinate and removing that coordinate to yield a code whose length is shorter by one.

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. Nearly all good linear binary codes for the asymmetric channel are also good for the symmetric channel [5]; this is not the case for non-binary codes [6].

Decoding

Decoding an arbitary linear binary code is \(NP\)-complete [7].Slepian's standard-array decoding [8].Recursive maximum likelihood decoding [9].Deep learning [10] and a transformer graph neural net (GNN) for soft decoding [11].Chase decoding, which uses channel measurement information [12].

Notes

Tables of bounds and examples of linear codes for various \(n\) and \(k\), extending code tables by A. E. Brouwer [13], 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)\) [15]. This was later improved to codes with distance \(\frac{1}{2}n-O(n^{1-\gamma})\) for any positive \(\gamma\) [16], provided that the number of codewords is polynomial in \(n\).
  • Frustration-free Hamiltonian code — Parity-check constraints defining a binary linear code can be encoded into a classical Ising model Hamiltonian, a commuting-projector model whose terms contain produts of Pauli \(Z\) matrices participating in each parity check. Such Ising models are also frustration-free since the codewords satisfy all parity checks.
  • Commuting-projector Hamiltonian code — Parity-check constraints defining a binary linear code can be encoded into a classical Ising model Hamiltonian, a commuting-projector model whose terms contain produts of Pauli \(Z\) matrices participating in each parity check. Such Ising models are also frustration-free since the codewords satisfy all parity checks.
  • 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.
  • Lexicographic code — Binary lexicodes are linear [17].
  • 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 [14; Thm. 8.5.2].
  • Binary PSK (BPSK) code — Concatenating binary linear codes with BPSK yields a standard way of digitizing the analog AGWN channel [18; Ch. 29].
  • 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 [19–21].
  • Majorana stabilizer code — When constructing a Majorana stabilizer code from a self-orthogonal classical code with an odd number of bits and generator matrix \(G\), a more complex procedure must be applied to ensure that the fermion code has an even number of Majorana zero modes, and thus a physical Hilbert space [22,23]. Rather than taking \(G\) to be the stabilizer matrix as in the even case, we take \(G\oplus G\). This is a concatenation of classical codes as in the CSS construction and it yields a mapping \([2n-1,k,d]\rightarrow [[2n-1,2n-1-k,d^\perp]]_f\). This procedure may be further generalized by concatenating two different self-orthogonal classical codes with an odd number of bits, as is often done in the CSS construction.
  • Coherent-parity-check (CPC) code — The CPC Construction uses two binary linear codes.
  • Quantum data-syndrome (QDS) code — The QDS code construction employs a particular binary linear code to provide protection against syndrome measurement errors.
  • CSS-T code — CSS-T codes are constructed from a pair of linear binary codes via the CSS construction, with the pair satisfying certain conditions [24].
  • Hypergraph product (HGP) code — Hypergraph product codes are constructed out of two linear binary codes.
  • Qubit CSS code — The CSS 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. Any binary linear code can be thought of as a qubit stabilizer code with \(Z\)-type stabilizer generators [25; Table I]. The stabilizer generators are extracted from rows of the parity-check matrix, while logical \(X\) Paulis correspond to rows of the generator matrix. States close to the equal superposition of all bitstrings within Hamming distance \(b\) of a binary linear code can be prepared efficiently [26]. Binary linear codes can be used for error-corrected entanglement distillation protocols [27].
  • 2D color code — As CSS codes, variants of the 2D color code are constructed out of self-dual classical codes on cubic planar graphs [28].

References

[1]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[2]
J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
[3]
A. Vardy, “The intractability of computing the minimum distance of a code”, IEEE Transactions on Information Theory 43, 1757 (1997) DOI
[4]
M. N. Vyalyi, “Hardness of approximating the weight enumerator of a binary linear code”, (2003) arXiv:cs/0304044
[5]
Varshamov, R. R. "Some features of linear codes that correct asymmetric errors." Soviet Physics Doklady. Vol. 9. 1965.
[6]
M. Grassl, P. W. Shor, G. Smith, J. Smolin, and B. Zeng, “New Constructions of Codes for Asymmetric Channels via Concatenation”, IEEE Transactions on Information Theory 61, 1879 (2015) arXiv:1310.7536 DOI
[7]
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
[8]
D. Slepian, “Some Further Theory of Group Codes”, Bell System Technical Journal 39, 1219 (1960) DOI
[9]
Y. S. Han, H.-T. Pai, P.-N. Chen, and T.-Y. Wu, “Maximum-likelihood Soft-decision Decoding for Binary Linear Block Codes Based on Their Supercodes”, (2014) arXiv:1408.1310
[10]
E. Nachmani, Y. Beery, and D. Burshtein, “Learning to Decode Linear Codes Using Deep Learning”, (2016) arXiv:1607.04793
[11]
Y. Choukroun and L. Wolf, “Error Correction Code Transformer”, (2022) arXiv:2203.14966
[12]
D. Chase, “Class of algorithms for decoding block codes with channel measurement information”, IEEE Transactions on Information Theory 18, 170 (1972) DOI
[13]
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.
[14]
T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
[15]
T. Kaufman and S. Litsyn, “Almost Orthogonal Linear Codes are Locally Testable”, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05) 317 DOI
[16]
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) 590 (2007) DOI
[17]
J. Conway and N. Sloane, “Lexicographic codes: Error-correcting codes from game theory”, IEEE Transactions on Information Theory 32, 337 (1986) DOI
[18]
A. Lapidoth, A Foundation in Digital Communication (Cambridge University Press, 2017) DOI
[19]
T. A. Brun, I. Devetak, and M.-H. Hsieh, “Catalytic Quantum Error Correction”, IEEE Transactions on Information Theory 60, 3073 (2014) arXiv:quant-ph/0608027 DOI
[20]
T. Brun, I. Devetak, and M.-H. Hsieh, “Correcting Quantum Errors with Entanglement”, Science 314, 436 (2006) arXiv:quant-ph/0610092 DOI
[21]
J. Qian and L. Zhang, “Entanglement-assisted quantum codes from arbitrary binary linear codes”, Designs, Codes and Cryptography 77, 193 (2014) DOI
[22]
S. Bravyi, B. M. Terhal, and B. Leemhuis, “Majorana fermion codes”, New Journal of Physics 12, 083039 (2010) arXiv:1004.3791 DOI
[23]
S. Vijay and L. Fu, “Quantum Error Correction for Complex and Majorana Fermion Qubits”, (2017) arXiv:1703.00459
[24]
E. Camps-Moreno, H. H. López, G. L. Matthews, D. Ruano, R. San-José, and I. Soprunov, “An algebraic characterization of binary CSS-T codes and cyclic CSS-T codes for quantum fault tolerance”, Quantum Information Processing 23, (2024) arXiv:2312.17518 DOI
[25]
D. Bacon and A. Casaccino, “Quantum Error Correcting Subsystem Codes From Two Classical Linear Codes”, (2006) arXiv:quant-ph/0610088
[26]
E. Farhi and S. P. Jordan, “Efficiently constructing a quantum uniform superposition over bit strings near a binary linear code”, (2024) arXiv:2404.16129
[27]
Y. Shi, A. Patil, and S. Guha, “Stabilizer Entanglement Distillation and Efficient Fault-Tolerant Encoder”, (2024) arXiv:2408.06299
[28]
H. Oral, “Constructing self-dual codes using graphs”, Journal of Combinatorial Theory, Series B 52, 250 (1991) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

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/edit/main/codes/classical/bits/binary_linear.yml.