Linear binary code


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.


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}


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.


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




Zoo code information

Internal code ID: binary_linear

Your contribution is welcome!

on (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.
@incollection{eczoo_binary_linear, title={Linear binary code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={} }
Permanent link:


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.