Case Study: Building a Burst-Tolerant Channel — Interleaving Hamming Codes to Survive a Scratch

DataField.Dev

Case Study: Building a Burst-Tolerant Channel — Interleaving Hamming Codes to Survive a Scratch

"The purpose of computing is insight, not numbers." — Richard Hamming

Executive Summary

In this build-focused case study you will assemble a complete, working noisy-channel pipeline — encode, corrupt, decode — that recovers a short message even after a burst of consecutive bit-flips wipes out a contiguous chunk of the transmission. You will do it using only the machinery this chapter built: the $\mathrm{Hamming}(7,4)$ code (which corrects one error per block) plus the §38.6 idea that beats bursts without leaving binary at all — interleaving. Interleaving is the trick the chapter named when it described the CD's CIRC scheme: spread the bits of each codeword far apart in time, so that a burst which would have destroyed one codeword instead nicks one bit from each of many codewords — and one bit per codeword is exactly what a Hamming code can fix.

This is the constructive counterpart to Case Study 1's diagnosis. There, a double error inside one block defeated a single-error-correcting code. Here, we take an eight-bit burst — which would obliterate any single Hamming block — and, by reordering bits before transmission, turn it into eight harmless single-bit errors spread across eight blocks, every one of which the decoder repairs. You will build the interleaver, the de-interleaver, a burst-error channel, and the end-to-end driver, hand-deriving the output at each stage. This is essentially the demonstrator the chapter promised for capstone Track D.

Skills applied

Composing the chapter's hamming_encode / hamming_decode into a multi-block message codec.
Designing an interleaver (block-to-column transpose) and its inverse, and proving it spreads bursts.
Modeling a burst-error channel and reasoning about how many errors land in each codeword.
Verifying end-to-end recovery by hand-tracing encode → interleave → burst → de-interleave → decode.
Connecting the construction to Reed–Solomon's burst strategy (§38.6) and the depth/burst trade-off.

Background

The scenario

You are writing the link layer for a cheap optical sensor that streams readings to a base station over an infrared beam. The beam is reliable except when something briefly occludes it — a passing hand, a fleck of dust on the lens — which blanks out a short, contiguous run of bits: a burst error of up to, say, 8 consecutive bits. Isolated single-bit noise is rare; bursts are the real enemy.

A plain Hamming code is the wrong tool, and it is worth being precise about why. $\mathrm{Hamming}(7,4)$ corrects exactly one error per 7-bit block (Case Study 1 belabored this). An 8-bit burst that happens to fall inside one block hits it with up to 7 errors at once — far past the $d_{\min}=3$ budget — and the block is lost (and, worse, may be silently miscorrected). Throwing a stronger per-block code at it would work but is expensive. The elegant, cheap fix is to keep the weak code and rearrange when its bits are sent.

🔗 Connection: This is exactly §38.6's insight, viewed from the binary side. Reed–Solomon beats bursts by counting in symbols so a burst spans few symbol-errors; CD players go further and interleave the symbols (CIRC) so even a long scratch spreads its damage thinly across many codewords. We are building the binary, Hamming-code version of that same idea — and seeing that "spread the damage out" is the structural move, independent of which code does the local correcting.

The plan

We will send a 16-bit message (four 4-bit nibbles) through this pipeline:

Encode: split into four nibbles; Hamming-encode each into a 7-bit codeword. Result: four blocks, $4 \times 7 = 28$ bits.
Interleave: instead of sending block 1, then block 2, …, send column by column — bit 1 of every block, then bit 2 of every block, and so on. Adjacent transmitted bits now come from different blocks.
Channel: a burst flips up to 8 consecutive transmitted bits.
De-interleave: undo the reordering, reassembling the four blocks.
Decode: Hamming-decode each block, correcting up to one error per block. If interleaving did its job, the burst left at most one error in each block, so all four are recovered.

Phase 1: The per-block codec (reuse the chapter's functions)

Start from exactly the chapter's hamming_encode / hamming_decode, composed into nibble-stream functions. Nothing new here — we are building with the toolkit.

def hamming_encode(data):                       # 4 data bits -> 7-bit codeword
    d1, d2, d3, d4 = data                        # positions 3,5,6,7
    p1, p2, p4 = d1 ^ d2 ^ d4, d1 ^ d3 ^ d4, d2 ^ d3 ^ d4
    return [p1, p2, d1, p4, d2, d3, d4]          # positions 1..7

def hamming_decode(code):                        # correct <=1 error; return data bits
    c = code[:]
    s1 = c[0] ^ c[2] ^ c[4] ^ c[6]
    s2 = c[1] ^ c[2] ^ c[5] ^ c[6]
    s4 = c[3] ^ c[4] ^ c[5] ^ c[6]
    syndrome = s4 * 4 + s2 * 2 + s1
    if syndrome:
        c[syndrome - 1] ^= 1
    return [c[2], c[4], c[5], c[6]]

message = [[1,0,1,1], [0,1,0,0], [1,1,1,0], [0,0,1,1]]   # four nibbles
blocks = [hamming_encode(nib) for nib in message]
for nib, blk in zip(message, blocks):
    print(nib, "->", blk)
# Hand-derivation (parities p1=d1^d2^d4, p2=d1^d3^d4, p4=d2^d3^d4):
#   [1,0,1,1]: p1=1^0^1=0,p2=1^1^1=1,p4=0^1^1=0 -> [0,1,1,0,0,1,1]
#   [0,1,0,0]: p1=0^1^0=1,p2=0^0^0=0,p4=1^0^0=1 -> [1,0,0,1,1,0,0]
#   [1,1,1,0]: p1=1^1^0=0,p2=1^1^0=0,p4=1^1^0=0 -> [0,0,1,0,1,1,0]
#   [0,0,1,1]: p1=0^0^1=1,p2=0^1^1=0,p4=0^1^1=0 -> [1,0,0,0,0,1,1]
# Expected output:
# [1, 0, 1, 1] -> [0, 1, 1, 0, 0, 1, 1]
# [0, 1, 0, 0] -> [1, 0, 0, 1, 1, 0, 0]
# [1, 1, 1, 0] -> [0, 0, 1, 0, 1, 1, 0]
# [0, 0, 1, 1] -> [1, 0, 0, 0, 0, 1, 1]

So our four codewords (rows of a $4 \times 7$ grid) are:

$$ \begin{array}{c|ccccccc} & p_1 & p_2 & d_1 & p_4 & d_2 & d_3 & d_4 \\ \hline \text{block 0} & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ \text{block 1} & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ \text{block 2} & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ \text{block 3} & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ \end{array} $$

💡 Intuition: Picture the four codewords stacked as the rows of a grid. Sending them the obvious way means sending row 0 left-to-right, then row 1, and so on — so all 7 bits of block 0 go out consecutively. A burst then lands entirely within one row. The whole trick of the next phase is to send the grid column by column instead, so consecutive transmitted bits come from different rows.

Phase 2: The interleaver — transpose the grid

Interleaving with depth 4 (four blocks) means transmitting the grid in column-major order: column 0 (one bit from each of the four blocks), then column 1, and so on. That is exactly a matrix transpose followed by flattening.

def interleave(blocks):
    """Column-major flatten of a list of equal-length blocks (matrix transpose)."""
    depth, width = len(blocks), len(blocks[0])
    return [blocks[r][c] for c in range(width) for r in range(depth)]

stream = interleave(blocks)
print("transmitted stream (28 bits):")
print(stream)
# Hand-derivation: read the grid DOWN each column, columns left to right.
#   col0: 0,1,0,1   col1: 1,0,0,0   col2: 1,0,1,0   col3: 0,1,0,0
#   col4: 0,1,1,0   col5: 1,0,1,1   col6: 1,0,0,1
# Expected output:
# transmitted stream (28 bits):
# [0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1]

Now look at what interleaving guarantees. In the transmitted stream, the four bits coming from the four different blocks are sent adjacently (positions 0–3 are block-0..3's first bits, positions 4–7 are their second bits, etc.). Equivalently, two bits from the same block are now sent at least depth = 4 positions apart. That spacing is the whole point, and it gives a clean theorem.

Claim (interleaving spreads bursts). With interleaving depth $D$, a burst of $B$ consecutive flipped transmitted bits puts at most $\lceil B / D \rceil$ errors into any single block.

The strategy first. Because consecutive transmitted bits belong to consecutive blocks (cycling with period $D$), any window of $D$ consecutive transmitted positions contains at most one bit from each block. A burst of length $B$ is covered by $\lceil B/D \rceil$ such windows, so it can deposit at most $\lceil B/D \rceil$ bits into any one block. Set $D$ large enough that this is $\le 1$ and every block stays inside the Hamming code's one-error budget.

Proof. Index the transmitted positions $0, 1, 2, \dots$. By construction position $i$ carries a bit of block $i \bmod D$. Fix a block $r$; the transmitted positions carrying its bits are exactly those $i$ with $i \equiv r \pmod D$, i.e. they are $D$ apart. A burst occupies a set of $B$ consecutive positions $\{a, a+1, \dots, a+B-1\}$. Among any $D$ consecutive integers there is at most one congruent to $r$ mod $D$, so the number of burst positions hitting block $r$ is at most the number of length-$D$ windows needed to cover $B$ consecutive integers, which is $\lceil B/D \rceil$. $\blacksquare$

For our pipeline, $D = 4$ and the worst-case burst is $B = 8$, giving $\lceil 8/4 \rceil = 2$ errors per block — which is too many for a $d_{\min}=3$ Hamming code! This is a genuine design finding, and it is the kind of thing you want to discover at the whiteboard, not in production.

⚠️ Common Pitfall: It is tempting to declare victory after building the interleaver. But the parameters must close the loop with the per-block code's correcting power. Depth 4 against an 8-bit burst leaves 2 errors per block, and a Hamming code corrects only 1. The construction is sound; the numbers are not yet. Always finish by checking $\lceil B/D \rceil \le t$ where $t$ is the per-block correction budget.

Phase 3: Fix the parameters, then build the channel

We have two honest options. (a) Reduce the guaranteed burst length to $B = 4$ (claim only single-window bursts), which gives $\lceil 4/4 \rceil = 1$ error per block — within budget. (b) Increase the interleaving depth to $D = 8$ so that an 8-bit burst gives $\lceil 8/8 \rceil = 1$ per block; that requires sending eight blocks per interleaving group (pad the message to eight nibbles). We will demonstrate the cleanest case — option (a), an honest 4-bit burst at depth 4 — so that every block ends up with exactly one error and the recovery is exact. (Option (b) is the "Your Turn" extension.)

Build a burst channel that flips $B$ consecutive transmitted bits starting at a given offset:

def burst_channel(stream, start, length):
    """Flip `length` consecutive bits beginning at index `start`."""
    out = stream[:]
    for i in range(start, start + length):
        out[i] ^= 1
    return out

received = burst_channel(stream, start=8, length=4)   # 4-bit burst at positions 8..11
print("received stream:")
print(received)
# Hand-derivation: flip stream positions 8,9,10,11.
#   stream pos 8..11 were 1,0,1,0  ->  flipped to 0,1,0,1
# Expected output:
# received stream:
# [0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1]

Which blocks did the burst touch? Transmitted positions 8, 9, 10, 11 carry, respectively, block $8 \bmod 4 = 0$, $9 \bmod 4 = 1$, $10 \bmod 4 = 2$, $11 \bmod 4 = 3$ — one bit from each block, exactly as the theorem promised. Specifically, positions 8–11 are column 2 of the grid (recall column $c$ occupies transmitted positions $4c \dots 4c+3$), so the burst corrupts the bit at grid column 2 in every row — one error per block. That is the magic: a contiguous burst became one isolated error in each codeword.

🔄 Check Your Understanding The burst hit transmitted positions 8–11. Using "position $i$ carries block $i \bmod 4$, grid column $\lfloor i/4 \rfloor$," name the (block, column) each flipped bit belongs to.

Answer

Position 8 → block 0, column 2. Position 9 → block 1, column 2. Position 10 → block 2, column 2. Position 11 → block 3, column 2. So every block loses exactly its column-2 bit (which is $d_1$, the data bit at codeword position 3) — one error apiece, the Hamming sweet spot.

Phase 4: De-interleave and decode — recover the message

De-interleaving is the inverse transpose: read the received stream back into a $4 \times 7$ grid in column-major order, then decode each row.

def deinterleave(stream, depth, width):
    """Inverse of interleave: rebuild `depth` blocks of length `width`."""
    return [[stream[c * depth + r] for c in range(width)] for r in range(depth)]

grid = deinterleave(received, depth=4, width=7)
recovered = [hamming_decode(blk) for blk in grid]
for blk, nib in zip(grid, recovered):
    print(blk, "-> decode ->", nib)
print("message recovered:", recovered)
# Hand-derivation:
#   Rebuilt blocks (each = original codeword with its column-2 / position-3 bit flipped):
#     block0: [0,1,0,0,0,1,1]  (orig [0,1,1,...], pos3 flipped)
#     block1: [1,0,1,1,1,0,0]  (orig [1,0,0,...], pos3 flipped)
#     block2: [0,0,0,0,1,1,0]  (orig [0,0,1,...], pos3 flipped)
#     block3: [1,0,1,0,0,1,1]  (orig [1,0,0,...], pos3 flipped)
#   Each has exactly one error at position 3 -> syndrome s4 s2 s1 = 011 = 3 -> flip pos 3.
#     block0 syndrome: s1=0^0^0^1=1, s2=1^0^1^1=1, s4=0^0^1^1=0 -> 011=3  -> fix pos3 -> data [1,0,1,1]
#     block1 syndrome: s1=1^1^1^0=1, s2=0^1^0^0=1, s4=1^1^0^0=0 -> 011=3  -> fix pos3 -> data [0,1,0,0]
#     block2 syndrome: s1=0^0^1^0=1, s2=0^0^1^0=1, s4=0^1^1^0=0 -> 011=3  -> fix pos3 -> data [1,1,1,0]
#     block3 syndrome: s1=1^1^0^1=1, s2=0^1^1^1=1, s4=0^0^1^1=0 -> 011=3  -> fix pos3 -> data [0,0,1,1]
# Expected output:
# [0, 1, 0, 0, 0, 1, 1] -> decode -> [1, 0, 1, 1]
# [1, 0, 1, 1, 1, 0, 0] -> decode -> [0, 1, 0, 0]
# [0, 0, 0, 0, 1, 1, 0] -> decode -> [1, 1, 1, 0]
# [1, 0, 1, 0, 0, 1, 1] -> decode -> [0, 0, 1, 1]
# message recovered: [[1, 0, 1, 1], [0, 1, 0, 0], [1, 1, 1, 0], [0, 0, 1, 1]]

The recovered message — [[1,0,1,1],[0,1,0,0],[1,1,1,0],[0,0,1,1]] — is bit-for-bit identical to the original four nibbles from Phase 1. A 4-bit burst, which would have annihilated a single Hamming block, was fully repaired, because interleaving converted it into four isolated single-bit errors and the Hamming code mopped each one up. The pipeline works end to end.

🚪 Threshold Concept: Where you spend redundancy and how you arrange it are separate levers, and the second is often free. We did not strengthen the code (still plain $\mathrm{Hamming}(7,4)$, still $d_{\min}=3$, still one error per block) — we only changed the order bits go on the wire. That reordering, costing zero extra bits, upgraded a single-error-correcting code into a burst-tolerant one. The deepest systems lesson of coding theory is that structure beats brute force: a good arrangement of cheap protection can outperform expensive protection arranged badly. This is precisely why the CD's CIRC layers interleaving on top of Reed–Solomon (§38.6).

Phase 5: End-to-end driver and a stress check

Wire the five stages into one function and confirm the round trip is the identity for any burst the parameters can handle.

def pipeline(message, burst_start, burst_len, depth):
    blocks = [hamming_encode(nib) for nib in message]
    stream = interleave(blocks)
    received = burst_channel(stream, burst_start, burst_len)
    grid = deinterleave(received, depth, width=7)
    return [hamming_decode(blk) for blk in grid]

msg = [[1,0,1,1], [0,1,0,0], [1,1,1,0], [0,0,1,1]]
ok = pipeline(msg, burst_start=8,  burst_len=4, depth=4) == msg   # column-2 burst
print("4-bit burst at pos 8 recovered:", ok)
ok2 = pipeline(msg, burst_start=12, burst_len=4, depth=4) == msg  # column-3 burst
print("4-bit burst at pos 12 recovered:", ok2)
# Hand-derivation: any aligned 4-bit burst covers exactly one grid column = one bit
#   per block = one error per block, all correctable. Both round trips return msg.
# Expected output:
# 4-bit burst at pos 8 recovered: True
# 4-bit burst at pos 12 recovered: True

Two clean recoveries. And we can predict, without running more cases, exactly where this pipeline breaks: any burst longer than the depth (here $B > 4$) will, by the Phase-2 theorem, drop $\ge 2$ errors into some block, exceeding the Hamming budget — that block will then be miscorrected (the Case Study 1 failure mode). Computation gave us confidence on the cases we traced; the theorem tells us the boundary for all cases at once — theme four of the book, exactly.

🐛 Find the Error: A teammate "simplifies" the system by interleaving with depth 2 instead of 4 to halve the buffering, keeping the 4-bit burst guarantee. Why does this break recovery? Compute $\lceil B/D \rceil$ for $B=4, D=2$.

Answer

$\lceil 4/2 \rceil = 2$ errors per block — over the $d_{\min}=3$ Hamming budget of one. With depth 2, consecutive transmitted bits alternate between only two blocks, so a 4-bit burst deposits two errors into each of two blocks, and those blocks get silently miscorrected. The depth must be at least the burst length (for one error per block with a single-error-correcting code): $D \ge B$.

Discussion Questions

The interleaving theorem gives $\le \lceil B/D \rceil$ errors per block. Restate the full design rule relating burst length $B$, interleaving depth $D$, and the per-block code's correction power $t$, and solve it for the minimum depth $D$ needed to survive a burst of length $B$ with a Hamming code.
Interleaving adds latency: the de-interleaver cannot output block 0 until it has received at least column-by-column data spanning all blocks. Estimate the buffering (in bits) needed for depth $D$ with 7-bit blocks, and explain the latency/burst-tolerance trade-off a CD or streaming codec must make.
We used a block interleaver (a transpose). CDs use a convolutional (delay-line) interleaver. Without the details, argue why "spread same-codeword symbols far apart in time" is the shared principle, and relate it to §38.6's claim that CIRC tolerates a ~2.5 mm scratch.
Compare two ways to survive an 8-bit burst with 4-bit nibbles: (a) interleave depth 8 over plain Hamming, versus (b) no interleaving but a stronger per-block code with $d_{\min} \ge 9$ (so it corrects 4 errors directly, $2t+1 = 9$). Which costs more redundancy? Which adds more latency? When would you pick each?
This entire construction stayed in binary and used a single-error-correcting code. §38.6 says Reed–Solomon over $\mathrm{GF}(2^8)$ is the production answer for bursts. What does RS buy that interleaved Hamming does not, and why do real systems (CDs) still combine RS with interleaving rather than relying on either alone?

Your Turn: Extensions

Option A (depth-8 for an 8-bit burst). Pad the message to eight nibbles and rebuild the pipeline with interleaving depth 8. Confirm by hand-tracing one column-aligned 8-bit burst that each of the eight blocks receives exactly one error and all are corrected. State the new buffering cost.
Option B (detect-the-undecodable). A burst longer than the depth produces $\ge 2$ errors in some block, which a plain Hamming decoder miscorrects silently (Case Study 1). Upgrade each block to the SECDED $(8,4)$ code so that an over-budget block is detected rather than silently wrong, and have the pipeline report which blocks are uncorrectable. Hand-derive the verdict for a 6-bit burst at depth 4.
Option C (random-burst stress test). Write (do not run) a driver that, for fixed depth 4 and burst length 4, tries every aligned burst start position $0, 4, 8, \dots, 24$ and asserts the round trip equals the original message. Predict the result from the Phase-2 theorem before writing the asserts, and state the one starting alignment, if any, that would violate the one-error-per-block guarantee (hint: there is none for aligned 4-bursts at depth 4 — explain why).

Key Takeaways

Interleaving converts burst errors into isolated errors — for free. Reordering bits so same-codeword bits are sent $D$ apart turns a length-$B$ burst into $\le \lceil B/D \rceil$ errors per codeword, costing zero extra redundancy.
Parameters must close with the per-block code. The design rule is $\lceil B/D \rceil \le t$: depth must satisfy $D \ge B/t$. For a single-error Hamming code ($t=1$), depth must be at least the burst length, $D \ge B$.
Build by composing the toolkit. The whole pipeline is hamming_encode/hamming_decode (this chapter) plus a transpose and its inverse — a faithful binary model of the CD's RS-plus-CIRC strategy from §38.6, and the seed of capstone Track D.
Arrangement can beat brute force. A weak code arranged well (interleaved Hamming) survives bursts that would defeat the same code arranged naively — the systems-level reason real codecs layer interleaving on top of their error-correcting code.