Classical Linear Codes
Classical linear codes protect bits using a generator matrix and a parity-check matrix, the foundation on which CSS quantum codes are built.
Generators and checks
A binary linear code encodes k message bits into n code bits as codewords forming a k-dimensional subspace of the n-dimensional binary space. A generator matrix G maps messages to codewords, and a parity-check matrix H satisfies H c = 0 for every codeword c. The code is written [n, k, d], where d is the minimum Hamming distance between codewords.
Decoding uses the syndrome s = H r for a received word r. If r = c + e for an error e, then s = H e depends only on the error, not the message. The decoder finds the lowest-weight e consistent with s and subtracts it. A code with distance d corrects up to (d-1)/2 errors.
Distance and rate
Two figures of merit govern a code. The rate k/n measures efficiency, how many message bits per code bit. The distance d measures protection, how many bit flips can be corrected. Good codes push both up, but they trade off, and finding families that keep rate and relative distance bounded away from zero is a central goal of coding theory.
- G encodes messages; H checks codewords with H c = 0.
- Syndrome s = H e reveals the error pattern, not the message.
- Distance d corrects up to floor((d-1)/2) errors, detects up to d-1.
- Rate k/n measures overhead; higher is more efficient.
Bridge to quantum codes
CSS codes lift a pair of classical codes into a quantum code, using one code's parity checks for phase errors and another's for bit errors. The classical Hamming code gives rise to the Steane code. Classical low-density parity-check codes inspire quantum LDPC codes. Understanding generator and check matrices, syndromes, and the distance-rate trade-off is therefore a prerequisite for the quantum constructions in this category.
The essential difference is that quantum codes must handle two error types at once and obey a commutation constraint between the two check families, which classical codes never face.