BCH Codes

Every time you scan a damaged QR code, play a scratched CD, or stream video over a noisy phone line, you rely on a branch of mathematics that was born in three independent labs between 1959 and 1960. Bose, Chaudhuri, and Hocquenghem — the B, C, and H — each arrived at essentially the same construction: a family of error-correcting codes built from polynomial arithmetic over a finite field.

The central promise of a BCH code is striking: given a transmitted block of n bits, you can guarantee to detect and correct up to t arbitrary errors, no matter where they fall. Not just single-bit errors. Not just burst errors. Any pattern of up to t bit-flips anywhere in the block.

The reason this is possible — and the reason it is efficient — is that the codewords are roots of carefully chosen polynomials. When errors corrupt a codeword, they leave algebraic fingerprints called syndromes. Reading those syndromes locates the errors as precisely as solving a small system of equations.

BCH codes sit squarely in the realm of solved problems in coding theory: the encoding and decoding algorithms are efficient (polynomial time), their error-correcting capacity is proven, and they have been deployed in billions of real devices. The challenge was not algorithmic hardness but algebraic ingenuity — and that ingenuity is now textbook material.

Below is a live BCH(15, 5, 3) playground — a code over GF($2^{15}$) that encodes 5 data bits into 15 codeword bits and can correct up to 3 errors. Click Encode to generate a codeword, then use the sliders or Flip random bits to introduce errors, and finally Decode to watch the syndrome decoder locate and fix every corrupted position.

<div class="bch-demo">
  <div class="section">
    <div class="label">{{label_data_bits}}</div>
    <div class="bit-row" id="data-bits"></div>
    <div class="hint-small">{{hint_toggle}}</div>
    <div class="preset-row">
      <button type="button" id="preset1">10101</button>
      <button type="button" id="preset2">11001</button>
      <button type="button" id="preset3">01110</button>
    </div>
  </div>
  <div class="action-row">
    <button type="button" id="btn-encode" class="primary">{{btn_encode}}</button>
  </div>
  <div class="section" id="codeword-section" style="display:none">
    <div class="label">{{label_codeword}}</div>
    <div class="bit-row" id="codeword-bits"></div>
    <div class="hint-small">{{hint_errors_prefix}} <span id="error-count">0</span> {{hint_errors_suffix}}</div>
    <div class="action-row">
      <button type="button" id="btn-flip" class="secondary">{{btn_flip}}</button>
      <button type="button" id="btn-clear-errors" class="ghost">{{btn_clear_errors}}</button>
    </div>
  </div>
  <div class="action-row" id="decode-row" style="display:none">
    <button type="button" id="btn-decode" class="primary">{{btn_decode}}</button>
  </div>
  <div class="section" id="result-section" style="display:none">
    <div class="label">{{label_result}}</div>
    <div id="result-box" class="result-box"></div>
  </div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #1a202c; margin: 0; font-size: 14px; }
.bch-demo { padding: .5rem 0; }
.section { margin-bottom: .9rem; }
.label { font-weight: 700; font-size: .8rem; text-transform: uppercase; letter-spacing: .04em;
          color: #4a5568; margin-bottom: .35rem; }
.hint-small { font-size: .78rem; color: #718096; margin: .3rem 0; }
.bit-row { display: flex; flex-wrap: wrap; gap: 3px; }
.bit { width: 28px; height: 28px; display: flex; align-items: center; justify-content: center;
       font: 700 13px ui-monospace, monospace; border-radius: 6px; cursor: pointer;
       border: 1.5px solid #cbd5e0; user-select: none; transition: all .12s; }
.bit.zero { background: #edf2f7; color: #4a5568; }
.bit.one  { background: #2b6cb0; color: #fff; border-color: #2c5282; }
.bit.error { background: #e53e3e; color: #fff; border-color: #c53030; }
.bit.parity { opacity: .85; }
.bit.fixed { background: #38a169; color: #fff; border-color: #276749; }
.bit.data-bit { cursor: pointer; }
.bit.codeword-bit { cursor: pointer; }
.action-row { display: flex; gap: .5rem; flex-wrap: wrap; margin: .55rem 0; }
.preset-row { display: flex; gap: .4rem; flex-wrap: wrap; margin: .3rem 0; }
button { font: 600 13px system-ui; padding: .38rem .8rem; border-radius: 7px; cursor: pointer;
         border: 1.5px solid; transition: all .12s; }
button.primary { background: #2b6cb0; color: #fff; border-color: #2c5282; }
button.primary:hover { background: #2c5282; }
button.secondary { background: #e53e3e; color: #fff; border-color: #c53030; }
button.secondary:hover { background: #c53030; }
button.ghost { background: #fff; color: #2b6cb0; border-color: #2b6cb0; }
button.ghost:hover { background: #ebf8ff; }
.preset-row button { background: #fff; color: #4a5568; border-color: #cbd5e0;
                     font-family: ui-monospace, monospace; font-size: 12px; }
.preset-row button:hover { background: #edf2f7; }
.result-box { background: #f7fafc; border: 1.5px solid #e2e8f0; border-radius: 9px;
              padding: .7rem .9rem; font-size: .82rem; line-height: 1.65; }
.result-box .ok { color: #276749; font-weight: 700; }
.result-box .err { color: #c53030; font-weight: 700; }
.result-box .mono { font-family: ui-monospace, monospace; background: #edf2f7;
                     padding: 1px 4px; border-radius: 4px; font-size: .78rem; }
.sep { height: 1px; background: #e2e8f0; margin: .35rem 0; }

// Code not found

Notice two things. First, encoding is fast: multiply the data polynomial by the generator polynomial. Second, syndrome decoding is systematic: compute six syndrome values, solve a small linear system (Berlekamp–Massey), and evaluate the error-locator polynomial to pinpoint each bad bit. The decoder finds errors in the same time regardless of where they land.

BCH codes are a solved problem — efficient algorithms for both encoding and decoding have been known since the early 1960s. But the path to that solution required real algebraic depth.

What makes a BCH code work?

A BCH(n, k, t) code over GF(2) is defined by choosing a generator polynomial $g(x)$ whose roots include $2t$ consecutive powers of a primitive element $\alpha$ in the extension field $\mathrm{GF}(2^m)$. Every valid codeword $c(x)$ is a multiple of $g(x)$, so it vanishes at all those roots. When a received word $r(x) = c(x) + e(x)$ contains errors $e(x)$, the syndrome values $S_i = r(\alpha^i)$ equal $e(\alpha^i)$ — they measure exactly the algebraic footprint of the errors, independent of which codeword was sent.

Decoding in three steps:

1. Syndrome computation: evaluate the received polynomial at 2t points — $O(nt)$ field operations.
2. Error-locator polynomial: use the Berlekamp–Massey algorithm (1968) to find a polynomial $\Lambda(x)$ whose roots are the inverses of the error locations. This runs in $O(t^{2})$ field operations.
3. Chien search: evaluate $\Lambda$ at every element of $\mathrm{GF}(2^m)$ to find which positions are errors, then flip those bits. $O(n)$ operations.

The total decoding cost is $O(n \cdot t)$ field multiplications — polynomial in both the block length and the number of correctable errors. No exponential search, no guessing.

The bound: BCH codes are asymptotically good — they approach the Singleton bound and, for many parameters, the Gilbert–Varshamov bound. Reed–Solomon codes, a special case of BCH codes where $n = 2^m - 1$ and $k$ can be freely chosen, achieve the Singleton bound exactly and are the basis of the codes in CDs, DVDs, and QR codes.

Compare this to factoring: there, no efficient algorithm is known and hardness is conjectured. BCH decoding is the opposite — a proven polynomial-time algorithm with an exact guarantee. The difficulty was always in discovering the algebraic structure, not in the computational complexity of using it.

The guarantee that BCH codes offer — correct up to t errors with certainty — makes them ideal anywhere data must survive a noisy channel intact.

• QR codes: every QR code uses Reed–Solomon error correction (a BCH special case) so aggressively that up to 30 % of the code can be obscured or damaged and you can still decode the full message. That is why logos can be placed inside QR codes.
• Optical storage (CDs and DVDs): a standard audio CD uses a two-layer interleaved Reed–Solomon scheme (CIRC) that corrects bursts of up to 4000 consecutive corrupted bits — the equivalent of a 2.5 mm scratch.
• Deep-space communication: NASA's Voyager probes used Reed–Solomon codes to send images across billions of kilometers of electromagnetic noise; later missions added a BCH outer code for extra protection.
• DSL and cable modems: the ITU G.709 and G.993 standards for DSL include BCH outer codes that clean up residual errors left after the inner turbo or LDPC decoder.
• Flash storage and SSDs: as flash cells wear, their error rates climb. Modern SSDs use BCH or LDPC codes with large t values to reclaim data from heavily degraded cells.

The common thread: wherever the channel noise is bounded (you can put an upper limit on how many bits it corrupts per block), BCH codes offer a mathematically guaranteed, computationally efficient fix. Learn BCH and you understand the algebraic backbone that makes digital storage and communication reliable. See also the related ideas in discrete logarithms and factoring, where finite-field arithmetic appears but the problem is hard rather than solved.

BCH codes are one of the cleanest victories in applied mathematics. Starting from a question — how many redundant bits do you need to guarantee correction of t arbitrary errors? — Bose, Chaudhuri, and Hocquenghem built a family of codes whose structure makes both encoding and decoding polynomial-time operations. The Berlekamp–Massey algorithm then turned the algebraic guarantee into a practical decoder fast enough for consumer hardware.

The result is everywhere: the QR code on a product label, the audio data on a CD, the telemetry from a probe billions of kilometres away — all protected by the same finite-field algebra discovered in 1959–1960.

BCH codes are not hard in the computational sense. They are hard in the sense that required genuine mathematical insight: recognizing that error positions are roots of a polynomial, that syndromes give you that polynomial's coefficients, and that finite-field arithmetic makes the whole system solvable. Once the insight exists, the computation is easy — which is exactly what you want from error correction.