Introduction

In 1948 Claude Shannon proved something both thrilling and maddening: every noisy channel has a capacity, a maximum rate at which you can send data with vanishing error. Push below that rate with a clever enough code and your message arrives perfectly; push above it and no code on Earth can save you.

The maddening part? Shannon's proof was non-constructive. It promised that near-perfect codes exist without telling anyone how to build a practical one. For nearly fifty years the best engineers fell well short of the limit — there was always a stubborn gap of several decibels between theory and practice.

Then, in the 1990s and 2000s, three families of codes — turbo, LDPC, and polar — closed that gap to a fraction of a decibel. They are the reason your phone, your Wi-Fi, your satellite TV, and the rovers on Mars can speak clearly through a storm of noise.

Repair a Noisy Message

Here is a tiny error-correcting code at work. Type a short message; the encoder adds parity bits that tie groups of message bits together with constraints. Then hit Add noise to flip random bits the way a real channel would — and watch the decoder use those parity constraints to figure out which bit is the liar and flip it back.

<p class="hint">A real code adds <b>parity bits</b> tied to the data by simple rules. Here each row of 4 data bits becomes a 7-bit Hamming codeword. Press <b>Add noise</b> to flip a random bit, then <b>Decode</b> to watch the parity checks locate the lie and repair it. Single-bit errors are always fixed.</p>
<label class="msg">Message:
  <input id="text" type="text" maxlength="6" value="HI" />
</label>
<div class="legend">
  <span><i class="sw data"></i> data bit</span>
  <span><i class="sw par"></i> parity bit</span>
  <span><i class="sw flip"></i> corrupted</span>
  <span><i class="sw fix"></i> repaired</span>
</div>
<div id="grid" class="grid"></div>
<div class="status" id="status">Encoded and clean. Add some noise.</div>
<div class="btns">
  <button id="noise" type="button">Add noise</button>
  <button id="decode" type="button">Decode</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.msg { display: block; font-size: .9rem; font-weight: 600; margin: 0 0 .6rem; }
.msg input { font: 600 14px ui-monospace, monospace; padding: .35rem .5rem; margin-left: .4rem;
             border: 1px solid #adb1b8; border-radius: 6px; width: 8rem; text-transform: uppercase; }
.legend { display: flex; flex-wrap: wrap; gap: .8rem; font-size: .78rem; color: #444; margin: 0 0 .6rem; }
.legend span { display: inline-flex; align-items: center; gap: .3rem; }
.sw { width: 13px; height: 13px; border-radius: 3px; display: inline-block; border: 1px solid #99a; }
.sw.data { background: #e8eef3; } .sw.par { background: #fde8c4; }
.sw.flip { background: #e63946; } .sw.fix { background: #2a9d54; }
.grid { display: flex; flex-direction: column; gap: 5px; margin: .3rem 0 .6rem; }
.row { display: flex; gap: 5px; }
.bit { width: 38px; height: 38px; display: flex; align-items: center; justify-content: center;
       font: 700 16px ui-monospace, monospace; border-radius: 7px; border: 1px solid #cdd9e3; }
.bit.data { background: #e8eef3; color: #1d3557; }
.bit.par  { background: #fde8c4; color: #8a5a12; }
.bit.flip { background: #e63946; color: #fff; border-color: #c92f3c; }
.bit.fix  { background: #2a9d54; color: #fff; border-color: #1f7d41; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; } .status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Hamming(7,4): 4 data bits -> 7-bit codeword with 3 parity bits. Any single
// bit flip is detected AND located by 3 parity checks (a "syndrome"), then
// corrected. This is the toy ancestor of LDPC/turbo/polar codes, which scale
// the same parity-check idea to thousands of overlapping constraints.
// Bit layout (1-indexed): p1 p2 d1 p4 d2 d3 d4  -> positions 1..7
//   Parity p covers positions whose index has that parity bit set:
const COVER = { 1:[1,3,5,7], 2:[2,3,6,7], 4:[4,5,6,7] };

function encodeNibble(d){ // d = [d1,d2,d3,d4]
  const cw = new Array(8).fill(0); // 1..7 used
  cw[3]=d[0]; cw[5]=d[1]; cw[6]=d[2]; cw[7]=d[3];
  for(const p of [1,2,4]){
    let s=0; for(const pos of COVER[p]) if(pos!==p) s^=cw[pos];
    cw[p]=s;
  }
  return cw.slice(1); // positions 1..7 -> array of 7
}
// syndrome decode: returns {pos, corrected[]} ; pos=0 means no error detected.
function decodeWord(w){ // w = 7-bit array (positions 1..7)
  const cw=[0,...w]; let syn=0;
  for(const p of [1,2,4]){ let s=0; for(const pos of COVER[p]) s^=cw[pos]; if(s) syn+=p; }
  const out=cw.slice();
  if(syn>=1 && syn<=7) out[syn]^=1; // flip the located bit
  return { pos: syn, corrected: out.slice(1) };
}
function dataOf(w){ const cw=[0,...w]; return [cw[3],cw[5],cw[6],cw[7]]; }

// --- message <-> bits ---
function msgToWords(txt){
  const words=[]; if(!txt) txt=' ';
  for(const ch of txt){
    let code = ch.charCodeAt(0) & 0xFF;
    const hi=[(code>>7)&1,(code>>6)&1,(code>>5)&1,(code>>4)&1];
    const lo=[(code>>3)&1,(code>>2)&1,(code>>1)&1,code&1];
    words.push(encodeNibble(hi)); words.push(encodeNibble(lo));
  }
  return words;
}
const PAR_POS=new Set([1,2,4]); // 1-indexed parity positions
let words=[], flips=[], fixes=[];

function build(){
  const txt=document.getElementById('text').value.toUpperCase().slice(0,6) || ' ';
  words=msgToWords(txt); flips=words.map(()=>-1); fixes=words.map(()=>-1);
  render(); setStatus('Encoded and clean. Add some noise.','');
}
function render(){
  const g=document.getElementById('grid'); g.innerHTML='';
  words.forEach((w,wi)=>{
    const row=document.createElement('div'); row.className='row';
    w.forEach((b,i)=>{
      const pos=i+1; const d=document.createElement('div');
      let cls='bit '+(PAR_POS.has(pos)?'par':'data');
      if(flips[wi]===pos) cls='bit flip';
      if(fixes[wi]===pos) cls='bit fix';
      d.className=cls; d.textContent=b; row.appendChild(d);
    });
    g.appendChild(row);
  });
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

function addNoise(){
  fixes=words.map(()=>-1);
  // flip exactly one random bit in one random word
  const wi=Math.floor(Math.random()*words.length);
  const pos=1+Math.floor(Math.random()*7);
  words[wi][pos-1]^=1; flips=words.map(()=>-1); flips[wi]=pos;
  render(); setStatus('A channel flipped one bit (red). Now decode.','bad');
}
function decode(){
  let repaired=0, badword=-1;
  const newWords=words.map((w,wi)=>{
    const r=decodeWord(w);
    if(r.pos!==0){ repaired++; badword=wi; fixes[wi]=r.pos; flips[wi]=-1; }
    return r.corrected;
  });
  words=newWords; render();
  // recover text
  let txt='';
  for(let i=0;i<words.length;i+=2){
    const hi=dataOf(words[i]), lo=dataOf(words[i+1]);
    let code=0; [...hi,...lo].forEach((b,k)=>{ code|=b<<(7-k); });
    txt+=String.fromCharCode(code);
  }
  if(repaired===0) setStatus(fmt('No errors detected. Message reads: ""%txt%"', { txt: txt }),'ok');
  else setStatus(fmt('Parity checks located & repaired %repaired% bit(s) (green). Recovered: ""%txt%"', { repaired: repaired, txt: txt }),'ok');
  console.log('decoded message:', JSON.stringify(txt), '| repaired bits:', repaired);
}
document.getElementById('noise').addEventListener('click',addNoise);
document.getElementById('decode').addEventListener('click',decode);
document.getElementById('reset').addEventListener('click',build);
document.getElementById('text').addEventListener('input',build);
build();
Result
Console

This little demo is a Hamming code, the great-grandparent of the modern families. Real LDPC and turbo codes do the same thing on a vastly larger scale: thousands of overlapping parity checks, decoded by passing "soft" probabilities back and forth until the bits settle on a consistent answer. The more checks overlap, the closer you can crowd against the noise.

The Real Story

What makes these codes special is not that they correct errors — every code does that — but how close to Shannon's limit they get, with decoding that's actually fast enough to run.

  • LDPC (low-density parity-check). Invented by Robert Gallager in his 1962 MIT thesis, then ignored for thirty years as too costly for the hardware of the day. Rediscovered in the mid-1990s, they use a sparse web of parity checks decoded by belief propagation — bits and checks exchange probabilities until a consensus emerges. Well-designed LDPC codes land within ~0.0045 dB of capacity.
  • Turbo codes. Announced by Berrou, Glavieux and Thitimajshima in 1993, they stunned the field by getting within ~0.5 dB of the limit. Their trick: two simple codes plus an interleaver, decoded by two sub-decoders that trade hints back and forth — the "turbo" feedback loop.
  • Polar codes. Proved by Erdal Arikan in 2009 to provably achieve capacity as the block length grows — the first codes with a clean mathematical proof of optimality. They "polarize" a channel into nearly-perfect and nearly-useless sub-channels, then send data only on the good ones.

None of this is an open problem anymore. Shannon's limit is achieved, not merely approached in the polar case, and matched to within a hair in practice by LDPC. The hard part was never whether — Shannon settled that in 1948 — it was finding codes you can actually decode in real time, and these three families did it.

Where It Matters

These codes are not lab curiosities — they are the invisible infrastructure of modern communication:

  • 5G mobile. The standard uses LDPC for data channels and polar codes for control channels — the only commercial deployment of polar codes to date.
  • Wi-Fi, satellite TV and Ethernet. LDPC powers Wi-Fi 6, the DVB-S2 satellite standard, and 10-gigabit Ethernet.
  • Deep space. Turbo and LDPC codes let probes like the Mars rovers and the New Horizons mission send back images from billions of kilometers on a whisper of power.
  • Storage. Modern hard drives and flash/SSD memory use LDPC to read data reliably off media that gets noisier as it shrinks.

Underneath them all sits the same idea that powers Reed–Solomon codes: add structured redundancy so the receiver can reconstruct what the channel destroyed — only here, pushed right up against the boundary set by Shannon entropy.

Conclusion

For half a century Shannon's limit was a promise no one could keep — a line everyone knew was reachable but no one could reach. Turbo, LDPC and polar codes kept the promise. Today we communicate within a fraction of a decibel of the absolute maximum that physics and information theory allow.

That is a rare thing in science: a problem fully solved. The next time your phone holds a call at the edge of coverage, or a rover beams a photo across the solar system, it is doing something Shannon proved was possible in 1948 and that took three brilliant ideas — and fifty years — to actually pull off. The same redundancy trick lives in Reed–Solomon codes; the limit it races against is Shannon entropy.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/ldpc-turbo-polar/Content licensed under CC BY-NC 4.0.