Classical error correction is a nodal subroutine in which a party processes classical data in order to detect and correct errors. In quantum protocols, this subroutine often appears after a quantum communication or measurement stage, when the relevant quantum information has already been converted into classical strings. The goal is to transform noisy or partially mismatched classical data into a reliable string that can be used by the rest of the protocol.

A typical setting is that one party holds a classical message or raw string $x$, while another party receives a noisy version $y$. Classical error correction adds redundancy, or exchanges correction information, so that the receiver can recover $x$ from $y$ with high probability. Depending on the protocol, the errors may arise from noisy classical communication, imperfect measurement devices, lossy channels, or natural noise in a quantum transmission followed by measurement. Error Correction is particularly important in protocols such as quantum key distribution, where honest parties must reconcile their raw keys before applying later steps such as privacy amplification.

The subroutine can be described abstractly as follows.

1. Input. A party holds a classical string $x$, or two honest parties hold correlated strings $x$ and $y$.
2. Encoding or syndrome generation. Redundant information is generated using an error-correcting code. In a communication setting, the sender may encode $x$ into a longer codeword. In an information-reconciliation setting, one party may compute a syndrome or parity-check information for $x$.
3. Transmission or public discussion. The encoded string, syndrome, or parity information is sent over a classical channel. In cryptographic protocols, this communication may be public and authenticated.
4. Decoding. The receiving party uses the redundant information, together with their noisy string $y$, to infer the intended string $x$.
5. Verification. Some protocols add an error-detection or hash-check step to test whether reconciliation succeeded.
6. Output. The output is a corrected classical string $\\\hat{x}$. The subroutine succeeds if $\\\hat{x}=x$, except with a small failure probability.

The parties must agree on the chosen error-correcting code, the decoding algorithm, and the expected error model. The error model may be a bit-flip model, an erasure model, a substitution model over a finite alphabet, or another classical channel model.

The subroutine also assumes that the number or rate of errors is within the correction capability of the chosen code. If the observed noise is too high, the decoder may fail or output an incorrect string.

• Let $\\\Sigma$ be a finite alphabet. For binary strings, $\\\Sigma={0,1}$.
• A block code of length $n$ is a subset $C\\\in \\\Sigma^n$
• The elements of $C$ are called codewords. If $C$ contains $K$ codewords, then it encodes $\\\log_{|\\\Sigma|}(K)$ logical symbols into $n$ physical symbols.
• For a binary linear code, one often writes an $[n,k,d]$ code, where $n$ is the block length, $k$ is the number of encoded information bits, and $d$ is the minimum Hamming distance of the code.
• The Hamming distance between two strings $x,y\\\in \\\Sigma^n$ is 
  $$d_H (x,y) = |\\\{i:x_i \\\neq y_i \\\}| $$
• A code with minimum distance $d$ can detect up to $d-1$ errors and can correct up to $t=⌊ \\\frac{d-1}{2}⌋$ errors under nearest-neighbour decoding.
• For a binary linear code, the parity-check matrix is denoted by $H$. The syndrome of a received word $y$ is $s = H y^T$.

• Reliability. The main purpose of classical error correction is to reduce the probability that honest parties end with different classical strings.
• Redundancy. Error correction works by adding or communicating redundant information. This redundancy makes the corrected data more reliable, but it also creates overhead.
• Rate-efficiency tradeoff. A code with more redundancy can usually tolerate more noise, but it has a lower effective rate. For an $[n,k,d]$ code, the rate is $R=k/n$.
• Failure probability. Decoding may fail or return an incorrect string if the noise exceeds the correction capability of the code or if the decoder is suboptimal.
• Leakage in cryptographic protocols. In protocols such as QKD, syndrome or parity information may leak information about the raw key. This leakage must be included in the security analysis.

Classical error correction can be formulated as an encoding and decoding procedure for a noisy classical channel.

Let $m$ be the intended message. An encoder maps $m$ to a codeword $c \\\in C$. The codeword is transmitted, stored, or otherwise processed, and the receiver obtains a noisy word

$$
y = c + e ,
$$

where $e$ is an error pattern. The decoder applies a map $\\\mathrm{Dec}$ and outputs

$$
\\\hat{m} = \\\mathrm{Dec}(y) .
$$

The subroutine is correct when

$$
\\\hat{m} = m .
$$

In many quantum cryptographic protocols, especially quantum key distribution, the more relevant formulation is information reconciliation. Alice and Bob hold correlated strings $x$ and $y$, where $y$ differs from $x$ in a small number of positions. Alice computes public correction information, often a syndrome

$$
s = Hx^T ,
$$

where $H$ is a parity-check matrix. Alice sends $s$ to Bob over an authenticated classical channel. Bob uses $s$, his string $y$, and the agreed decoder to infer an error pattern $\\\hat{e}$ satisfying

$$
H\\\hat{e}^T = Hy^T – s .
$$

He then corrects his string by setting

$$
\\\hat{x} = y – \\\hat{e} .
$$

If the decoder succeeds, then

$$
\\\hat{x} = x .
$$

If the decoder fails, the protocol may abort or proceed with an incorrect string, depending on whether an additional verification step is included.

The choice of code depends on the protocol requirements. Simple examples include repetition codes and parity-check codes. More efficient examples include Hamming codes, Reed-Solomon codes, BCH codes, LDPC codes, polar codes, and other families of classical error-correcting codes. The appropriate choice depends on the error model, block length, target failure probability, computational cost, and acceptable communication leakage.

Classical error correction is a broad subject with many code families and decoding algorithms. For the purposes of the Quantum Protocol Zoo, the most important role of this subroutine is as a reusable local component in larger quantum-network protocols.

In QKD, classical error correction is usually followed by privacy amplification. Error correction reconciles Alice and Bob’s raw keys, while privacy amplification removes information that may have leaked to an adversary through the quantum channel or the public reconciliation transcript.

The Error Correction Zoo [3] provides a detailed taxonomy of classical, quantum, and classical-quantum error-correcting codes. Its entry on error-correcting codes describes an ECC as a code designed for transmitting classical information through classical channels, and its classical-code lists give many examples of code families that may be used in this subroutine.

1. Victor V. Albert and Philippe Faist, editors, The Error Correction Zoo, 2026.
2. The Error Correction Zoo, “Error-correcting code (ECC).”
3. F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.
4. Shu Lin and Daniel J. Costello, Error Control Coding, 2nd edition, Prentice Hall, 2004.
5. C. E. Shannon, “A Mathematical Theory of Communication,” Bell System Technical Journal, 1948.