Introduction

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.

Try It: Encode, Corrupt, Decode

Below is a live BCH(15, 5, 3) playground — a code over GF(2152^{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">Data bits (5 bits)</div>
    <div class="bit-row" id="data-bits"></div>
    <div class="hint-small">Click bits to toggle, or use presets:</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">Encode →</button>
  </div>
  <div class="section" id="codeword-section" style="display:none">
    <div class="label">Codeword (15 bits) — 5 data + 10 parity</div>
    <div class="bit-row" id="codeword-bits"></div>
    <div class="hint-small">Errors introduced: <span id="error-count">0</span> / 3 max</div>
    <div class="action-row">
      <button type="button" id="btn-flip" class="secondary">Flip random bits</button>
      <button type="button" id="btn-clear-errors" class="ghost">Clear errors</button>
    </div>
  </div>
  <div class="action-row" id="decode-row" style="display:none">
    <button type="button" id="btn-decode" class="primary">Decode →</button>
  </div>
  <div class="section" id="result-section" style="display:none">
    <div class="label">Syndrome decoding 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// BCH(15, 5, 3) over GF(2^4).
// Generator polynomial g(x) = x^10 + x^8 + x^5 + x^4 + x^2 + x + 1
// (roots include alpha, alpha^2, alpha^3, alpha^4, alpha^5, alpha^6
//  where alpha is a root of the primitive polynomial p(x) = x^4 + x + 1)
// This is the standard BCH(15,5,3) that corrects up to 3 errors.

// ── GF(16) arithmetic ──────────────────────────────────────────────
// p(x) = x^4 + x + 1, primitive element alpha (power representation)
const GF_EXP = new Uint8Array(31); // alpha^i mod p(x), i=0..29, repeat
const GF_LOG = new Uint8Array(16); // log table: GF_LOG[a] = i s.t. alpha^i = a
(function buildGF(){
  let x = 1;
  for(let i = 0; i < 15; i++){
    GF_EXP[i] = x; GF_LOG[x] = i;
    x <<= 1;
    if(x & 16) x ^= 0b10011; // x^4 + x + 1
  }
  for(let i = 15; i < 31; i++) GF_EXP[i] = GF_EXP[i-15];
  GF_LOG[0] = 255; // undefined
})();
function gfMul(a, b){
  if(!a || !b) return 0;
  return GF_EXP[(GF_LOG[a] + GF_LOG[b]) % 15];
}
function gfPow(a, n){
  if(!a) return 0;
  return GF_EXP[(GF_LOG[a] * n) % 15];
}
function gfInv(a){ return a ? GF_EXP[(15 - GF_LOG[a]) % 15] : 0; }

// ── BCH(15,5,3) generator polynomial ──────────────────────────────
// g(x) = (x^4+x+1)(x^4+x^3+x^2+x+1)(x^2+x+1)  — over GF(2)
// = x^10 + x^8 + x^5 + x^4 + x^2 + x + 1
// Coefficients as array index=degree, g[0]=constant term
const G = [1,1,1,0,1,1,0,0,1,0,1]; // g[0..10], degree 10

// ── Polynomial multiply over GF(2) (XOR) ─────────────────────────
function polyMulBin(a, b){
  const res = new Uint8Array(a.length + b.length - 1);
  for(let i=0;i<a.length;i++) for(let j=0;j<b.length;j++) res[i+j] ^= a[i]&b[j];
  return res;
}
function polyModBin(a, b){
  // polynomial division, remainder only, coefficients in GF(2)
  const r = Array.from(a);
  const db = b.length - 1;
  for(let i = r.length-1; i >= db; i--){
    if(r[i]){
      for(let j=0;j<=db;j++) r[i-db+j] ^= b[j];
    }
  }
  return r.slice(0, db);
}

// ── Encode ─────────────────────────────────────────────────────────
// Systematic: codeword = [parity(10) | data(5)]  (index 0=LSB)
// parity = data * x^10 mod g(x)
function encode(dataBits){
  // dataBits: array of 5 bits, index 0 = most significant
  // represent data polynomial: data[0]*x^4 + ... + data[4]*x^0
  const data = new Uint8Array(15); // 15 coefficients, shifted by 10
  for(let i=0;i<5;i++) data[i+10] = dataBits[4-i]; // data in high positions
  const parity = polyModBin(data, G); // 10 coefficients
  const cw = new Uint8Array(15);
  for(let i=0;i<10;i++) cw[i] = parity[i];
  for(let i=0;i<5;i++) cw[i+10] = dataBits[4-i];
  return cw; // index 0=x^0 coefficient
}

// ── Syndrome computation ──────────────────────────────────────────
// S_i = r(alpha^i) in GF(16), i=1..6
function syndromes(cw){
  const S = new Uint8Array(7); // S[1..6]
  for(let i=1;i<=6;i++){
    let val = 0;
    for(let j=0;j<15;j++) if(cw[j]) val ^= gfPow(GF_EXP[1], i*j);
    S[i] = val;
  }
  return S;
}

// ── Berlekamp–Massey to find error-locator polynomial ─────────────
// Input: S[1..2t], Output: Λ[0..e] with Λ[0]=1, roots are inverses of error positions
function berlekampMassey(S, t){
  let Lambda = [1], B = [1], L = 0, m = 1, b = 1;
  for(let r = 1; r <= 2*t; r++){
    let delta = S[r];
    for(let i = 1; i <= L; i++) delta ^= gfMul(Lambda[i]||0, S[r-i]);
    if(!delta){ m++; }
    else if(2*L < r){
      const oldLambda = Lambda.slice();
      const coeff = gfMul(delta, gfInv(b));
      while(Lambda.length < B.length + m) Lambda.push(0);
      for(let i = 0; i < B.length; i++) Lambda[i+m] ^= gfMul(coeff, B[i]);
      L = r - L; B = oldLambda; b = delta; m = 1;
    } else {
      const coeff = gfMul(delta, gfInv(b));
      while(Lambda.length < B.length + m) Lambda.push(0);
      for(let i = 0; i < B.length; i++) Lambda[i+m] ^= gfMul(coeff, B[i]);
      m++;
    }
  }
  return Lambda;
}

// ── Chien search: find roots of Λ ─────────────────────────────────
function chienSearch(Lambda){
  const positions = [];
  for(let i=0;i<15;i++){
    // evaluate Λ at alpha^(-i) = alpha^(15-i)
    const ai = GF_EXP[(15-i)%15];
    let val = 0, power = 1;
    for(let k=0;k<Lambda.length;k++){
      val ^= gfMul(Lambda[k], power);
      power = gfMul(power, ai);
    }
    if(val === 0) positions.push(i);
  }
  return positions;
}

// ── Decode ─────────────────────────────────────────────────────────
function decode(cw){
  const S = syndromes(cw);
  const allZero = S.slice(1).every(v=>v===0);
  if(allZero) return { errors: [], corrected: cw.slice(), ok: true };
  const Lambda = berlekampMassey(S, 3);
  const errPos = chienSearch(Lambda);
  const corrected = cw.slice();
  for(const p of errPos) corrected[p] ^= 1;
  const S2 = syndromes(corrected);
  const ok = S2.slice(1).every(v=>v===0);
  return { errors: errPos, corrected, ok };
}

// ── UI State ────────────────────────────────────────────────────────
let dataBits = [1,0,1,0,1];
let codeword = null;
let receivedWord = null;
let errorPositions = new Set();

function renderDataBits(){
  const row = document.getElementById('data-bits'); row.innerHTML = '';
  for(let i=0;i<5;i++){
    const b = document.createElement('div');
    b.className = 'bit data-bit ' + (dataBits[i] ? 'one' : 'zero');
    b.textContent = dataBits[i];
    b.title = fmt(`Bit %i% (click to toggle)`, { i: i });
    b.addEventListener('click', () => {
      dataBits[i] ^= 1;
      codeword = null; receivedWord = null; errorPositions = new Set();
      renderDataBits();
      document.getElementById('codeword-section').style.display = 'none';
      document.getElementById('decode-row').style.display = 'none';
      document.getElementById('result-section').style.display = 'none';
    });
    row.appendChild(b);
  }
}

function renderCodeword(){
  if(!receivedWord) return;
  const row = document.getElementById('codeword-bits'); row.innerHTML = '';
  document.getElementById('error-count').textContent = errorPositions.size;
  for(let i=14;i>=0;i--){
    const b = document.createElement('div');
    const isErr = errorPositions.has(i);
    const isParity = i < 10;
    b.className = 'bit codeword-bit ' + (isErr ? 'error' : (receivedWord[i] ? 'one' : 'zero')) + (isParity ? ' parity' : '');
    b.textContent = receivedWord[i];
    b.title = (isParity ? `Parity` : `Data`) + ' bit x^' + i + (isErr ? ' (ERROR)' : '');
    b.addEventListener('click', () => {
      receivedWord[i] ^= 1;
      if(errorPositions.has(i)) errorPositions.delete(i); else errorPositions.add(i);
      renderCodeword();
      document.getElementById('result-section').style.display = 'none';
    });
    row.appendChild(b);
  }
}

function setPreset(bits){
  dataBits = bits.slice();
  codeword = null; receivedWord = null; errorPositions = new Set();
  renderDataBits();
  document.getElementById('codeword-section').style.display = 'none';
  document.getElementById('decode-row').style.display = 'none';
  document.getElementById('result-section').style.display = 'none';
}

document.getElementById('preset1').addEventListener('click', () => setPreset([1,0,1,0,1]));
document.getElementById('preset2').addEventListener('click', () => setPreset([1,1,0,0,1]));
document.getElementById('preset3').addEventListener('click', () => setPreset([0,1,1,1,0]));

document.getElementById('btn-encode').addEventListener('click', () => {
  codeword = encode(dataBits);
  receivedWord = codeword.slice();
  errorPositions = new Set();
  document.getElementById('codeword-section').style.display = '';
  document.getElementById('decode-row').style.display = '';
  document.getElementById('result-section').style.display = 'none';
  renderCodeword();
});

document.getElementById('btn-flip').addEventListener('click', () => {
  if(!codeword) return;
  if(errorPositions.size >= 3){ return; }
  const available = [];
  for(let i=0;i<15;i++) if(!errorPositions.has(i)) available.push(i);
  const needed = Math.min(1, available.length, 3 - errorPositions.size);
  // pick random positions
  for(let k=0;k<needed;k++){
    const idx = Math.floor(Math.random() * available.length);
    const pos = available.splice(idx,1)[0];
    receivedWord[pos] ^= 1;
    errorPositions.add(pos);
  }
  renderCodeword();
  document.getElementById('result-section').style.display = 'none';
});

document.getElementById('btn-clear-errors').addEventListener('click', () => {
  if(!codeword) return;
  receivedWord = codeword.slice();
  errorPositions = new Set();
  renderCodeword();
  document.getElementById('result-section').style.display = 'none';
});

document.getElementById('btn-decode').addEventListener('click', () => {
  if(!receivedWord) return;
  const {errors, corrected, ok} = decode(receivedWord);
  const resultSection = document.getElementById('result-section');
  const resultBox = document.getElementById('result-box');
  resultSection.style.display = '';

  const S = syndromes(receivedWord);
  const sVals = Array.from({length:6},(_,i)=>S[i+1].toString(16).toUpperCase()).join(', ');
  const errBits = errors.map(p=>'x^'+p).join(', ') || `none`;
  const recoverData = corrected.slice(10).reverse().join('');
  const origData = dataBits.join('');

  if(ok && errors.length === 0){
    resultBox.innerHTML = fmt(`<span class="ok">✓ No errors detected.</span><div class="sep"></div>
      Syndromes S₁…S₆: <span class="mono">%sVals%</span> (all zero — codeword is valid)<br>
      Decoded data: <span class="mono">%recoverData%</span>`, { sVals: sVals, recoverData: recoverData });
  } else if(ok){
    resultBox.innerHTML = fmt(`<span class="ok">✓ %length% error(s) corrected!</span><div class="sep"></div>
      Syndromes S₁…S₆: <span class="mono">%sVals%</span><br>
      Error locator Λ(x) roots → error positions: <span class="mono">%errBits%</span><br>
      After correction, all syndromes = 0 ✓<br>
      Recovered data: <span class="mono">%recoverData%</span>
      %v%`, { length: errors.length, sVals: sVals, errBits: errBits, recoverData: recoverData, v: recoverData === origData ? ' <span class="ok">(matches original!)</span>' : '' });
  } else {
    resultBox.innerHTML = fmt(`<span class="err">✗ Too many errors (>%length% found) — cannot guarantee correction.</span><div class="sep"></div>
      Syndromes S₁…S₆: <span class="mono">%sVals%</span><br>
      BCH(15,5,3) corrects up to 3 errors; this message may be unrecoverable.`, { length: errors.length, sVals: sVals });
  }

  // Show corrected codeword
  const corrRow = document.createElement('div');
  corrRow.innerHTML = '<div class="sep"></div>Corrected codeword: ';
  const bits = document.createElement('span');
  bits.style.fontFamily = 'ui-monospace,monospace';
  bits.style.fontSize = '.8rem';
  for(let i=14;i>=0;i--){
    const span = document.createElement('span');
    const wasErr = errorPositions.has(i);
    span.textContent = corrected[i];
    span.style.color = wasErr ? '#276749' : '#4a5568';
    span.style.fontWeight = wasErr ? '700' : '400';
    bits.appendChild(span);
  }
  corrRow.appendChild(bits);
  resultBox.appendChild(corrRow);
  console.log(`BCH decode | errors at:`, errors, '| syndromes:', Array.from(S).slice(1));
});

renderDataBits();
Result
Console

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.

The Real Complexity

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)g(x) whose roots include 2t2t consecutive powers of a primitive element α\alpha in the extension field GF(2m)\mathrm{GF}(2^m). Every valid codeword c(x)c(x) is a multiple of g(x)g(x), so it vanishes at all those roots. When a received word r(x)=c(x)+e(x)r(x) = c(x) + e(x) contains errors e(x)e(x), the syndrome values Si=r(αi)S_i = r(\alpha^i) equal e(αi)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)O(nt) field operations.
  2. Error-locator polynomial: use the Berlekamp–Massey algorithm (1968) to find a polynomial Λ(x)\Lambda(x) whose roots are the inverses of the error locations. This runs in O(t2)O(t^{2}) field operations.
  3. Chien search: evaluate Λ\Lambda at every element of GF(2m)\mathrm{GF}(2^m) to find which positions are errors, then flip those bits. O(n)O(n) operations.

The total decoding cost is O(n⋅t)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=2m−1n = 2^m - 1 and kk 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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/bch-codes/Content licensed under CC BY-NC 4.0.