# 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 codeword \(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~. \end{align}

## Rate

## Notes

## Parent

## Children

## Cousins

- Calderbank-Shor-Steane (CSS) stabilizer code — Construction uses two related binary linear codes \(C_X\) and \(C_Z\).
- Entanglement-assisted (EA) QECC — Any linear binary code can be used to construct an EAQECC.
- Entanglement-assisted (EA) stabilizer code — Any linear binary code can be used to construct an EA stabilizer code.
- Fock-state bosonic code — Fock-state code distance is a natural extension of Hamming distance between binary strings.
- Lattice-based code — Since lattices are closed under addition, lattice-based codes can be thought of as linear codes over the reals.
- Low-density parity-check (LDPC) code — Binary LDPC codes are a subset of binary linear codes.
- Qubit stabilizer code — Qubit stabilizer codes are quantum analogues of binary linear codes.

## Zoo code information

## References

- [1]
- 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.

## 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.