Forward Error Correction

Every time you stream a video, join a video call, or download a file, your data travels as a stream of packets. Networks are not perfectly reliable: routers drop packets under load, radio links lose bursts to interference, and satellite links add hundreds of milliseconds of delay. Asking the sender to resend a lost packet costs a full round-trip — an eternity on high-latency or one-way links like deep-space probes.

Forward Error Correction (FEC) sidesteps the problem entirely. Instead of sending $k$ data packets and hoping all arrive, the sender transmits $n > k$ coded packets — the original data plus redundant parity packets computed from it. The receiver can reconstruct the missing data from any $k$ of the $n$ packets, even if $n - k$ were lost in transit.

The simplest version uses XOR: if you send packets $A$, $B$, and $A \oplus B$, then losing any one of the three lets you recover it from the other two. Richer codes scale this idea: Reed–Solomon, used in CDs and QR codes since the 1960s, and LDPC codes, used in Wi-Fi and 5G, extend the same principle to large blocks with near-optimal efficiency.

FEC is a solved problem in the sense that Shannon's channel capacity theorem (1948) tells us exactly how much redundancy a noisy channel requires. Practical codes that achieve that limit with polynomial-time encoding and decoding took decades more to find, but they now underpin every wireless standard you use.

Below the sender holds three data packets. A parity packet is computed as the XOR of all three. Together they form a coded block of four packets. The channel randomly drops one packet — click Drop a packet to simulate a loss.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="block" id="sender-block">
  <div class="block-label">{{label_sender}}</div>
  <div class="packets" id="sender-packets"></div>
</div>
<div class="arrow-row">
  <div class="arrow-label">{{label_channel}}</div>
  <div class="channel-line" id="channel-line"></div>
</div>
<div class="block" id="receiver-block">
  <div class="block-label">{{label_receiver}}</div>
  <div class="packets" id="receiver-packets"></div>
</div>
<div class="status" id="status"></div>
<div class="btns">
  <button id="btn-drop" type="button">{{btn_drop}}</button>
  <button id="btn-recover" type="button" disabled>{{btn_recover}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.block { background: #f0f4f8; border: 1px solid #cdd9e3; border-radius: 10px; padding: .5rem .7rem .6rem; margin-bottom: .3rem; }
.block-label { font-size: .75rem; font-weight: 700; text-transform: uppercase; letter-spacing: .06em; color: #5a7088; margin-bottom: .4rem; }
.packets { display: flex; gap: .4rem; flex-wrap: wrap; }
.pkt { width: 72px; height: 56px; border-radius: 8px; display: flex; flex-direction: column; align-items: center; justify-content: center; font: 700 13px ui-monospace, monospace; border: 2px solid transparent; transition: all .25s; position: relative; }
.pkt .pkt-label { font-size: .65rem; font-weight: 600; text-transform: uppercase; letter-spacing: .05em; opacity: .7; }
.pkt .pkt-val { font-size: 1rem; margin-top: .15rem; }
.pkt.data { background: #dbeafe; border-color: #93c5fd; color: #1e3a5f; }
.pkt.parity { background: #ede9fe; border-color: #c4b5fd; color: #3b0764; }
.pkt.dropped { background: #fee2e2; border-color: #fca5a5; color: #7f1d1d; opacity: .7; }
.pkt.recovered { background: #d1fae5; border-color: #6ee7b7; color: #064e3b; }
.pkt.missing { background: #f3f4f6; border-color: #d1d5db; color: #9ca3af; border-style: dashed; }
.arrow-row { display: flex; flex-direction: column; align-items: center; margin: .3rem 0; }
.arrow-label { font-size: .7rem; color: #888; margin-bottom: .1rem; }
.channel-line { width: 90%; height: 2px; background: #adb1b8; position: relative; }
.channel-line::after { content: ''; position: absolute; right: 0; top: -4px; border: 5px solid transparent; border-left-color: #adb1b8; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin: .5rem 0; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button:disabled { opacity: .4; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice what happened: the receiver got only three of the four packets, yet it reconstructed the missing one by XOR-ing the others — no retransmission needed. The asymmetry is the point: sending one extra packet costs 25 % extra bandwidth but eliminates the latency of a round-trip that could be hundreds of milliseconds on a satellite link or a deep-space channel.

FEC sits at the intersection of information theory and algorithm design.

• Shannon's theorem (1948) proved that for any channel with a fixed noise level there exists a code that transmits reliably at up to the channel's capacity — but the proof was non-constructive: it said good codes exist without saying how to build them.
• Reed–Solomon codes (1960) are the first widely deployed family. They treat $k$ data symbols as a polynomial of degree $k-1$, evaluate it at $n$ points, and send those values. Any $k$ evaluations uniquely reconstruct the polynomial — so any $n - k$ erasures are correctable. Encoding is $O(n \log n)$ with the Fast Fourier Transform; decoding is $O(n^2)$ naively or $O(n \log^2 n)$ with advanced algorithms.
• LDPC codes (Gallager, 1962; rediscovered 1990s) use sparse parity-check matrices and iterative belief-propagation decoding. They approach Shannon capacity with near-linear time encoding and decoding — a breakthrough that earned LDPC a place in Wi-Fi 802.11n, 5G NR, and DVB-S2.
• Polar codes (Arıkan, 2009) are the first family with a rigorous mathematical proof of achieving capacity. They use a recursive butterfly transform and successive cancellation decoding in $O(n \log n)$.
• Raptor codes extend the idea to the rateless (fountain) setting: the sender generates an unlimited stream of coded packets and the receiver stops once it has collected enough — without either party knowing the channel loss rate in advance.

The complexity of decoding is central: a code is only practical if a receiver can decode in real time. All modern codes achieve this, though the gap between theory and practice in the high-noise regime is still an active research area. This is quite different from problems like P vs NP where no efficient algorithm is known — here efficiency has been achieved, and the open questions are about shaving the last few percent off overhead.

FEC is one of the most pervasive techniques in all of engineering:

• Wireless standards: every Wi-Fi, 4G, and 5G frame uses LDPC or turbo codes to survive radio interference without retransmission.
• Streaming and broadcast: DVB-S2 satellite TV and video-conferencing codecs use FEC so a burst of dropped packets doesn't freeze your screen.
• Deep-space communication: NASA's Voyager probes and Mars rovers use Reed–Solomon plus convolutional codes. At distances where a round-trip signal takes hours, retransmission is not an option.
• Storage: SSDs, RAID arrays, and optical discs (CD, DVD, Blu-ray) use Reed–Solomon to recover from bit rot and physical scratches.
• QR codes: the colored squares you scan contain enough redundancy that up to 30 % of the code can be obscured and the data still decodes — the same algebra that fixes packet loss fixes a torn corner.
• Content delivery networks: streaming platforms use erasure codes across server replicas so one server going down doesn't interrupt playback.

You can also see the connection to information theory: the question of how much redundancy is necessary is fundamentally a question about what information can be recovered from partial observations — the same kind of reasoning behind compression and probabilistic algorithms.

Forward error correction flips the script on packet loss. Instead of treating a dropped packet as an error to be fixed by asking the sender again, FEC treats it as an expected event and encodes the data so that any sufficient subset of packets is enough to reconstruct everything.

The math — from XOR parity to Reed–Solomon polynomials to LDPC belief propagation — is elegant and fully understood. Shannon told us in 1948 how much redundancy a channel needs; decades of coding theory gave us practical families that achieve it. The result is the invisible backbone of every wireless call, every satellite broadcast, and every deep-space mission: reliable communication over an unreliable world.