1. Introduction: Two Everyday-Yet-Miraculous Feats of Information Resurrection

In both the furthest reaches of interstellar space and the palm of your hand, modern digital engineering routinely performs what appears to be a violation of physical intuition: reconstructing 100% bit-exact digital information from signals or media that have been severely mutilated by noise, scratches, or physical destruction.

Miracle 1: Voyager 1 & 2 Transmitting Across Billions of Kilometers at $10^{-16}\text{ Watts}$

Launched in 1977, NASA’s Voyager 1 and Voyager 2 spacecraft executed a grand tour of Jupiter, Saturn, Uranus, and Neptune before crossing the heliopause into interstellar space—now more than 24 billion kilometers from Earth.

Consider the physics of Voyager’s radio link. The spacecraft’s S-band/X-band radio transmitter operates at just $23\text{ watts}$—less electrical power than the incandescent lightbulb inside a household refrigerator. By the time that electromagnetic wave expands across a sphere billions of kilometers in radius and reaches the 70-meter dish antennas of NASA’s Deep Space Network (DSN) on Earth, the received signal power has attenuated to roughly $10^{-16}\text{ watts}$ ($0.1\text{ attowatts}$).

At $10^{-16}\text{ watts}$, the signal power is comparable to the random thermal agitation of electrons inside the receiver’s own cryogenic low-noise amplifier (Johnson–Nyquist thermal noise) and cosmic background radiation. If Voyager simply transmitted raw, uncompressed binary pixel values ($0$s and $1$s), thousands of bits per second would be randomly flipped ($0 \leftrightarrow 1$) by thermal fluctuations, turning portraits of Jupiter’s Great Red Spot, Saturn’s rings, and Neptune’s Great Dark Spot into unrecognizable static. Yet Voyager delivered razor-sharp, full-color scientific imagery with virtually zero uncorrectable bit errors.

Miracle 2: A QR Code with $30\%$ of Its Modules Covered by a Coffee Stain or Logo

Now consider a terrestrial miracle you perform almost daily. You point your smartphone camera at a QR Code (Quick Response Code) printed on a café table tent, an outdoor poster, or a product package. Perhaps a coffee ring has stained a corner of the grid, a tear has ripped away a chunk of the paper, or a graphic designer has intentionally plastered a company logo directly over the center $25\%$ to $30\%$ of the QR code’s black-and-white modules.

In naive computing, if you delete $30\%$ of the bytes in a file, the file is irretrievably corrupted. Yet your smartphone camera captures the frame, runs an algebraic algorithm in less than $10\text{ milliseconds}$, and extracts the exact URL, cryptographic payment token, or Wi-Fi credentials with zero bit errors.

  flowchart TD
    subgraph Voyager["Deep-Space Telemetry (Voyager 1 & 2)"]
        V1["Planetary Image Payload (k bits)"] --> V2["Concatenated Encoding (Outer RS + Inner Convolutional/LDPC)"]
        V2 --> V3["23-Watt Transmitter across Billions of km (10⁻¹⁶ W Received)"]
        V3 --> V4["Severe Thermal Noise (AWGN) & Random Bit Flips"]
        V4 --> V5["Soft-Decision Viterbi / Belief Propagation + RS Decoding"]
        V5 --> V6["Razor-Sharp Planetary Portrait (Zero Bit Errors)"]
    end
    subgraph QR["Everyday QR Code Scanning"]
        Q1["URL / Payload Data (k bytes)"] --> Q2["GF(2⁸) Reed-Solomon Encoding (n bytes)"]
        Q2 --> Q3["Coffee Stain or Company Logo Destroys 30% of Modules"]
        Q3 --> Q4["Syndrome Evaluation + Berlekamp-Massey / Euclidean Solver"]
        Q4 --> Q5["Chien Search + Forney Error Evaluation (10 ms)"]
        Q5 --> Q6["100% Bit-Exact Payload Reconstruction"]
    end

How is it mathematically possible to resurrect missing or corrupted data without asking the sender to retransmit?

The answer lies in the marriage of Claude Shannon’s Information Theory (1948) with the geometric, algebraic, and graph-theoretic edifice of Error-Correcting Codes (ECC)—spanning Richard Hamming’s hypercube geometry (1950), Irving Reed and Gustave Solomon’s polynomial interpolation over Galois fields $\mathbb{F}_{2^m}$ (1960), Robert Gallager’s Low-Density Parity-Check (LDPC) belief propagation (1962), and Erdal Arıkan’s Polar codes (2009). In this article, we derive the exact mathematics behind each of these breakthroughs from first principles.

2. Claude Shannon’s 1948 Revolution and the Noisy-Channel Coding Theorem

2.1 The Pre-1948 Dogma and the Failure of Naive Repetition Coding

Before 1948, communication engineers universally believed a seemingly self-evident tragedy: if a communication channel is noisy, the only way to drive the probability of decoding error $P_e$ toward zero is either to increase transmission power to infinity or to slow the information transmission rate $R$ down toward zero.

To see why this belief seemed inescapable, let us analyze the most intuitive error-correcting scheme imaginable: the Repetition Code over a Binary Symmetric Channel (BSC) with crossover (bit-flip) probability $p \in (0, 1/2)$.

Thus, every engineer prior to 1948 concluded that zero error probability and positive transmission rate ($R > 0$) were mutually exclusive.

2.2 Shannon’s Shockwave: Channel Capacity $C$ and the Noisy-Channel Coding Theorem

In July and October 1948, 32-year-old Bell Labs mathematician Claude Elwood Shannon published “A Mathematical Theory of Communication” in the Bell System Technical Journal. In a single stroke, Shannon founded Information Theory and proved that the engineering consensus was completely wrong.

Shannon proved the Noisy-Channel Coding Theorem (Shannon’s Second Theorem):

$$P_e < \varepsilon \quad \left(\lim_{n \to \infty} P_e = 0\right)$$

Conversely, if $R > C$, no encoding or decoding scheme can achieve arbitrarily small error probability; the error probability is bounded away from zero as $n \to \infty$.

This theorem was a conceptual thunderbolt. You do not need to drive the code rate $R$ to zero to achieve error-free communication! As long as your rate $R$ stays below the channel’s speed limit $C$, noise does not limit the accuracy of communication—it only limits the maximum rate $C$ at which completely reliable communication can occur.

2.3 Deriving the Capacity of the Binary Symmetric Channel $C_{\text{BSC}}(p)$

How did Shannon prove that rate $R < 1 - H_2(p)$ is achievable with $P_e \to 0$? Instead of repeating a single bit $n$ times, we group $k = nR$ information bits together and map each of the $2^{nR}$ messages to a length-$n$ codeword in $\mathbb{F}_2^n$. By the Asymptotic Equipartition Property (AEP) (Law of Large Numbers), when a codeword $\mathbf{c}$ is transmitted through $n$ uses of the BSC, the received vector $\mathbf{y}$ will fall with probability approaching $1$ inside a thin spherical shell of radius $np$ around $\mathbf{c}$, containing approximately $2^{n H_2(p)}$ typical noisy sequences.

Since $M = 2^{nR}$, as long as $R < 1 - H_2(p)$, the fraction of space occupied by the noise spheres of all $2^{nR}$ codewords vanishes exponentially as $n \to \infty$! Shannon showed via his brilliant Random Coding Argument (averaging the error probability over all randomly generated codebooks) that at least one codebook in the ensemble must have $P_e \to 0$.

2.4 The AWGN Channel and the Ultimate Shannon Limit ($E_b / N_0 = -1.59\,\text{dB}$)

Pause to appreciate what $E_b / N_0 = -1.59\,\text{dB}$ means: as long as the energy per information bit is at least $69.3\%$ of the noise spectral density $N_0$, error-free communication across the universe is physically possible; below $-1.59\,\text{dB}$, no coding scheme in the cosmos can ever prevent errors.

3. Richard Hamming’s 1950 Geometric Breakthrough: Hamming Distance and the $[7, 4, 3]$ Perfect Code

3.1 From Non-Constructive Existence to Explicit Hypercube Geometry

Shannon’s random coding proof showed that capacity-approaching codes exist, but random codebooks have no algebraic structure: storing and decoding a random codebook of length $n=1000$ and rate $R=0.5$ would require comparing the received vector against $2^{500} \approx 10^{150}$ codewords—far more than the number of atoms in the observable universe ($10^{80}$).

Meanwhile, at Bell Labs, mathematician Richard W. Hamming was frustrated that the Bell Model V relay computer, which used simple parity checks to detect single bit errors on punched cards, would simply halt and abort his weekend batch jobs whenever a single bit flipped. Hamming asked: “If the machine can detect that an error has occurred, why can’t it locate which bit failed and correct it automatically?”

In 1950, Hamming published “Error Detecting and Error Correcting Codes”, introducing a geometric metric on binary hypercubes and constructing the celebrated Hamming $(7,4)$ code.

3.2 Hamming Distance $d_H(\mathbf{u}, \mathbf{v})$ and Minimum Distance $d_{\min}$

We view the set of all binary strings of length $n$ as the $n$-dimensional vector space $\mathbb{F}_2^n$ over the Galois field of two elements $\mathbb{F}_2 = \{0, 1\}$ (with addition and subtraction both equal to bitwise XOR $\oplus$), or geometrically as the vertices of the $n$-dimensional hypercube.

3.3 Disjoint Hamming Spheres: Proving Error Detection, Erasure Correction, and Error Correction

Using the triangle inequality and the geometry of these spheres, we can rigorously prove the three fundamental capabilities of a code with minimum distance $d_{\min}$:

1. Error Detection ($d_{\min} - 1$ errors): Since every pair of distinct codewords $\mathbf{c}_1 \neq \mathbf{c}_2$ is separated by at least $d_{\min}$ bit flips, flipping between $1$ and $d_{\min} - 1$ coordinates of $\mathbf{c}_1$ can never land on another valid codeword $\mathbf{c}_2 \in \mathcal{C}$. Thus, a code of minimum distance $d_{\min}$ is guaranteed to detect any pattern of up to $d_{\min} - 1$ errors.
2. Erasure Correction ($e = d_{\min} - 1$ erasures at known locations): An erasure (symbol ?) occurs when the receiver knows which coordinate indices were lost (e.g., a dropped network packet, a dead disk drive in RAID, or an unreadable sensor pixel), and only needs to determine their values. Because any two distinct codewords $\mathbf{c}_1 \neq \mathbf{c}_2$ differ in at least $d_{\min}$ positions, deleting any $e \le d_{\min} - 1$ coordinates still leaves at least $d_{\min} - e \ge 1$ un-erased coordinate where $\mathbf{c}_1$ and $\mathbf{c}_2$ differ! Hence, any pattern of up to $e = d_{\min} - 1$ erasures can be uniquely and exactly reconstructed.
3. Arbitrary Error Correction ($t = \lfloor(d_{\min} - 1)/2\rfloor$ errors at unknown locations): When the error locations are unknown, a minimum-distance decoder maps a received vector $\mathbf{y}$ to the nearest codeword $\hat{\mathbf{c}} = \arg\min_{\mathbf{c} \in \mathcal{C}} d_H(\mathbf{y}, \mathbf{c})$. This succeeds unconditionally for all error patterns of weight $\le t$ if and only if the Hamming spheres $B_t(\mathbf{c})$ centered at all codewords $\mathbf{c} \in \mathcal{C}$ are pairwise disjoint ($B_t(\mathbf{c}_1) \cap B_t(\mathbf{c}_2) = \emptyset$ for all $\mathbf{c}_1 \neq \mathbf{c}_2$). Proof: Suppose $\mathbf{y} \in B_t(\mathbf{c}_1) \cap B_t(\mathbf{c}_2)$. By the triangle inequality, $$d_H(\mathbf{c}_1, \mathbf{c}_2) \le d_H(\mathbf{c}_1, \mathbf{y}) + d_H(\mathbf{y}, \mathbf{c}_2) \le t + t = 2t$$ Therefore, to prevent any overlap, it is necessary and sufficient that $d_{\min} \ge 2t + 1$, or equivalently: $$t = \left\lfloor \frac{d_{\min} - 1}{2} \right\rfloor$$ More generally, if $t$ unknown errors and $e$ known erasures occur simultaneously, deleting the $e$ erased coordinates reduces the effective minimum distance of the punctured code to at least $d_{\min} - e$, which can then correct $t$ unknown errors whenever $d_{\min} - e \ge 2t + 1$: $$\mathbf{d_{\min} \ge 2t + e + 1}$$

Notice the fundamental rule of coding theory revealed by $d_{\min} \ge 2t + e + 1$: correcting one error at an unknown location costs $2$ units of minimum distance (one to locate where it is, and one to determine what its value is), whereas correcting an erasure at a known location costs only $1$ unit of minimum distance!

A code that achieves the Hamming bound with strict equality—meaning its radius-$t$ Hamming spheres tile the entire space $\mathbb{F}_q^n$ with zero gaps and zero overlaps—is called a Perfect Code.

3.4 The Hamming $(7,4)$ Code: Explicit Matrices $\mathbf{G}, \mathbf{H}$ and Binary Syndrome Decoding

Thus, the $16$ Hamming spheres of radius $1$ (each containing $1$ center codeword plus $7$ single-bit neighbors) partition all $128$ vertices of the 7-dimensional hypercube $\mathbb{F}_2^7$ with $100\%$ efficiency!

then the $j$-th column of $\mathbf{H}_{\text{binary}}$ is literally the 3-bit binary representation of the integer $j$ ($1 = 001_2, 2 = 010_2, \dots, 7 = 111_2$).

For example, using $\mathbf{H}_{\text{binary}}$, if the syndrome evaluates to $\mathbf{s} = (1, 0, 1)^T$, reading $101_2 = 5$ immediately tells the hardware circuit: “Bit #5 is flipped—invert bit #5 and you are done!" By appending one overall parity bit to form the $[8, 4, 4]$ extended Hamming code (SECDED: Single-Error Correcting, Double-Error Detecting), we obtain the exact circuit architecture embedded inside every ECC DRAM memory module protecting cloud servers and workstations against cosmic-ray bit flips today.

4. Irving Reed & Gustave Solomon’s 1960 Masterpiece: Reed-Solomon (RS) Codes over Galois Fields $\mathbb{F}_{2^m}$

4.1 The Achilles’ Heel of Bit-Level Codes: Burst Errors

Why can’t we simply use a Hamming code on a QR code, a Blu-ray disc, or a deep-space link? Because Hamming codes operate on individual bits in $\mathbb{F}_2$, and physical damage in the real world is spatially or temporally correlated—it occurs in Burst Errors.

A fingerprint smudge or coffee stain on a QR code, a $0.5\text{-mm}$ scratch on an optical disc, or an atmospheric fade on a satellite link does not politely flip 1 bit out of every 7; it obliterates dozens or hundreds of consecutive bits in one localized region.

In 1960, Irving S. Reed and Gustave Solomon at MIT Lincoln Laboratory solved the burst-error problem with a breathtaking algebraic insight that remains one of the pillars of modern computing: Reed-Solomon (RS) Codes.

4.2 Grouping Bits into Galois Field Symbols: $\text{GF}(2^8) = \mathbb{F}_2[x]/(x^8 + x^4 + x^3 + x^2 + 1)$

Reed and Solomon’s first stroke of genius was to move from the binary field $\mathbb{F}_2$ to an extension Galois Field (Finite Field) $\mathbb{F}_{2^m} = \text{GF}(2^m)$, where every $m$-bit block (most commonly $m = 8\text{ bits} = 1\text{ byte}$) is treated as a single algebraic symbol.

Why can’t we just do arithmetic modulo $2^8 = 256$ on standard integers? Because the ring $\mathbb{Z}/256\mathbb{Z}$ contains zero divisors (e.g., $16 \times 16 \equiv 0 \pmod{256}$), meaning division is undefined and linear systems of equations cannot be uniquely inverted! By Galois’s theorem, a finite field of order $q$ exists if and only if $q = p^m$ is a prime power.

Arithmetic in $\text{GF}(2^8)$ has remarkable hardware and software properties:

• Addition and Subtraction are identical and equal to bitwise XOR (^): Since coefficients lie in $\mathbb{F}_2$ where $1 + 1 = 0$ and $-1 = +1$, there are no carries! For any $A, B \in \text{GF}(2^8)$, $A + B = A - B = A \oplus B$.
• Multiplication and Division reduce to table lookups via a Primitive Element $\alpha$: The multiplicative group of non-zero elements $\text{GF}(2^8)^\times$ is a cyclic group of order $2^8 - 1 = 255$. The element $\alpha = x$ (byte $\mathtt{0x02}$) is a primitive element whose powers $\alpha^0, \alpha^1, \alpha^2, \dots, \alpha^{254}$ generate all $255$ non-zero bytes (with $\alpha^8 = x^4 + x^3 + x^2 + 1 = \mathtt{0x1D}$ and $\alpha^{255} = 1$). By precomputing a 256-byte discrete logarithm table LOG[A] and antilogarithm table EXP[i], multiplying or dividing any two non-zero bytes takes a single integer addition modulo $255$: $$\alpha^i \cdot \alpha^j = \alpha^{(i + j) \bmod 255}, \qquad \frac{\alpha^i}{\alpha^j} = \alpha^{(i - j) \bmod 255}$$

Look at what this achieves against burst errors: if a scratch or noise spike corrupts 8 consecutive bits inside a single byte, from the perspective of $\text{GF}(2^8)$ that entire 8-bit catastrophe is just one single symbol error!

4.3 The Algebraic Miracle: Polynomial Interpolation and the MDS Singleton Bound

Reed and Solomon’s second stroke of genius was to encode data as the coefficients of a polynomial over $\mathbb{F}_q$ and transmit oversampled evaluations of that polynomial.

Why is this construction miraculous? Because of the Fundamental Theorem of Algebra over Finite Fields:

Theorem (Uniqueness of Polynomial Interpolation & MDS Property of RS Codes): A non-zero polynomial $D(x) \in \mathbb{F}_q[x]$ of degree at most $k - 1$ can have at most $k - 1$ roots in the field $\mathbb{F}_q$. Consequently, if $P(x)$ and $Q(x)$ are two distinct message polynomials of degree $\le k - 1$, their difference $D(x) = P(x) - Q(x)$ is a non-zero polynomial of degree $\le k - 1$ and therefore can vanish ($P(\alpha_i) = Q(\alpha_i)$) at at most $k - 1$ evaluation points. Across $n$ distinct evaluation points, the codewords of $P(x)$ and $Q(x)$ must therefore differ in at least $n - (k - 1) = n - k + 1$ coordinates!

Codes that achieve $d_{\min} = n - k + 1$ are called Maximum Distance Separable (MDS) Codes. Every subset of $k$ coordinates of an $[n, k]$ Reed-Solomon codeword is linearly independent (the corresponding $k \times k$ submatrix of the Vandermonde evaluation matrix $V_{ij} = \alpha_i^{j-1}$ has non-zero determinant $\prod_{1 \le r < s \le k} (\alpha_{i_s} - \alpha_{i_r}) \neq 0$).

Let us translate $d_{\min} = n - k + 1$ into concrete fault tolerance using $2t + e \le d_{\min} - 1 = n - k$:

1. Erasure Recovery (RAID-6 & Cloud Storage): If $e = n - k$ symbols are completely lost at known positions, any $k$ surviving evaluations $(\alpha_{i_1}, y_{i_1}), \dots, (\alpha_{i_k}, y_{i_k})$ uniquely reconstruct the degree-($ via Lagrange Interpolation over $\mathbb{F}_q$: $$P(x) = \sum_{j=1}^{k} y_{i_j} \prod_{\substack{m=1 \\ m \neq j}}^{k} \frac{x - \alpha_{i_m}}{\alpha_{i_j} - \alpha_{i_m}}$$ There is zero wasted redundancy: adding $n - k$ parity symbols protects against the simultaneous failure of any $n - k$ storage nodes!
2. Arbitrary Error Correction (QR Codes & Deep Space): When error locations are unknown, adding $n - k = 2t$ parity symbols corrects any $t = \lfloor(n-k)/2\rfloor$ corrupted symbols anywhere in the block, regardless of whether 1 bit or all 8 bits inside each corrupted byte were flipped!

4.4 Cyclic Generator Polynomials $g(x)$ and Berlekamp-Massey / Euclidean Decoding

In practice (including QR codes, Voyager, and DSL/optical networks), Reed-Solomon codes are implemented in an equivalent dual formulation as Cyclic Systematic BCH-type Codes of length $n \le 2^m - 1$.

  flowchart TD
    R["Received Polynomial y(x) = c(x) + e(x)"] --> S1["Step 1: Compute 2t Syndromes<br/>S_j = y(α^j) = e(α^j) = Σ Y_l X_l^j"]
    S1 --> Z{"Are all S_j == 0?"}
    Z -- "Yes" --> Clean["Zero Errors! Output message bytes directly"]
    Z -- "No" --> S2["Step 2: Solve Key Equation for Error-Locator Λ(x)<br/>(Berlekamp-Massey LFSR Synthesis or Sugiyama Euclidean)"]
    S2 --> S3["Step 3: Chien Search over GF(2⁸)<br/>Find roots Λ(X_l⁻¹) = 0 to pinpoint corrupted indices i_l"]
    S3 --> S4["Step 4: Forney's Algorithm<br/>Compute error magnitudes Y_l = -X_l Ω(X_l⁻¹) / Λ'(X_l⁻¹)"]
    S4 --> Out["XOR Y_l into corrupted bytes y_{i_l} -> Exact Message!"]

  flowchart TD
    subgraph Tanner["Sparse Bipartite Tanner Graph & Sum-Product Belief Propagation"]
        direction TB
        V1["Variable Node v₁ (Channel LLR L₁)"] --- C1["Check Node f₁ (v₁ ⊕ v₂ ⊕ v₄ = 0)"]
        V2["Variable Node v₂ (Channel LLR L₂)"] --- C1
        V2 --- C2["Check Node f₂ (v₂ ⊕ v₃ ⊕ v₅ = 0)"]
        V3["Variable Node v₃ (Channel LLR L₃)"] --- C2
        V4["Variable Node v₄ (Channel LLR L₄)"] --- C1
        V4 --- C3["Check Node f₃ (v₃ ⊕ v₄ ⊕ v₆ = 0)"]
        V5["Variable Node v₅ (Channel LLR L₅)"] --- C2
        V6["Variable Node v₆ (Channel LLR L₆)"] --- C3
        V3 --- C3
    end

  flowchart TD
    subgraph Polar["Erdal Arıkan's Channel Polarization (Polar Codes, 2009)"]
        W["N = 2^m Identical Noisy Channels W (Each Capacity I(W) = C)"] --> K["Kronecker Butterfly Transform G_N = B_N [1 0; 1 1]^{⊗m}"]
        K --> Good["Fraction C of Synthetic Channels W_N^(i)<br/>Capacity I(W_N^(i)) → 1.0 (Perfectly Noiseless!)"]
        K --> Bad["Fraction (1 - C) of Synthetic Channels W_N^(i)<br/>Capacity I(W_N^(i)) → 0.0 (Completely Noisy)"]
        Good --> Unfrozen["Transmit k ≈ N·C Information Bits (Unfrozen Set A)"]
        Bad --> Frozen["Clamp to Known Zeros u_i = 0 (Frozen Set A^c)"]
    end

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175

from typing import List, Tuple

# =====================================================================
# Part 1: Hamming (7, 4) Code over GF(2) - Matrix & Syndrome Decoding
# =====================================================================
def hamming74_verification() -> None:
    print("=== [1] Hamming [7, 4, 3] Code over GF(2) ===")
    # Systematic Generator Matrix G = [I_4 | P] (4x7)
    G = [
        [1, 0, 0, 0, 1, 1, 0],
        [0, 1, 0, 0, 1, 0, 1],
        [0, 0, 1, 0, 0, 1, 1],
        [0, 0, 0, 1, 1, 1, 1],
    ]
    # Parity-Check Matrix H = [P^T | I_3] (3x7) satisfying G * H^T = 0 mod 2
    H = [
        [1, 1, 0, 1, 1, 0, 0],
        [1, 0, 1, 1, 0, 1, 0],
        [0, 1, 1, 1, 0, 0, 1],
    ]

    msg = [1, 0, 1, 1]
    codeword = [sum(msg[i] * G[i][j] for i in range(4)) % 2 for j in range(7)]
    print(f"4-bit Message m        : {msg}")
    print(f"7-bit Codeword c = mG  : {codeword}")

    # Inject a single-bit flip at coordinate index 2
    received = codeword.copy()
    flipped_idx = 2
    received[flipped_idx] ^= 1
    print(f"Received y (idx {flipped_idx} flip): {received}")

    # Compute 3-bit Syndrome s = H * y^T mod 2
    syndrome = [sum(H[r][c] * received[c] for c in range(7)) % 2 for r in range(3)]
    error_col = next(
        (c for c in range(7) if [H[r][c] for r in range(3)] == syndrome), -1
    )
    corrected = received.copy()
    if error_col != -1:
        corrected[error_col] ^= 1
    print(f"Syndrome s = H y^T     : {syndrome} -> Matches column index {error_col}")
    print(f"Corrected Codeword     : {corrected}")
    print(f"Decoded Message        : {corrected[:4]} (Bit-Exact: {corrected[:4] == msg})\n")


# =====================================================================
# Part 2: Galois Field GF(2^8) Arithmetic & Reed-Solomon Decoder
# Irreducible Polynomial: p(x) = x^8 + x^4 + x^3 + x^2 + 1 (0x11D, QR Standard)
# =====================================================================
class GF256:
    def __init__(self, prim_poly: int = 0x11D) -> None:
        self.exp = [0] * 512
        self.log = [0] * 256
        val = 1
        for i in range(255):
            self.exp[i] = val
            self.exp[i + 255] = val
            self.log[val] = i
            val <<= 1
            if val & 0x100:
                val ^= prim_poly

    def add(self, a: int, b: int) -> int:
        # In characteristic 2, addition and subtraction are both bitwise XOR
        return a ^ b

    def sub(self, a: int, b: int) -> int:
        return a ^ b

    def mul(self, a: int, b: int) -> int:
        if a == 0 or b == 0:
            return 0
        return self.exp[self.log[a] + self.log[b]]

    def inv(self, a: int) -> int:
        if a == 0:
            raise ZeroDivisionError("0 has no multiplicative inverse in GF(2^8)")
        return self.exp[255 - self.log[a]]

    def div(self, a: int, b: int) -> int:
        if b == 0:
            raise ZeroDivisionError("Division by zero in GF(2^8)")
        if a == 0:
            return 0
        return self.exp[self.log[a] + 255 - self.log[b]]

    def power(self, a: int, p: int) -> int:
        if p == 0:
            return 1
        if a == 0:
            return 0
        return self.exp[(self.log[a] * p) % 255]

    def poly_eval(self, coeffs: List[int], x: int) -> int:
        # Evaluate P(x) = coeffs[0] + coeffs[1]*x + ... using Horner's rule
        res = 0
        for c in reversed(coeffs):
            res = self.add(self.mul(res, x), c)
        return res

    def solve_linear_system(self, A: List[List[int]], b: List[int]) -> List[int]:
        # Gaussian elimination over GF(2^8)
        n = len(b)
        M = [row[:] + [b[i]] for i, row in enumerate(A)]
        for col in range(n):
            pivot = next(r for r in range(col, n) if M[r][col] != 0)
            M[col], M[pivot] = M[pivot], M[col]
            inv_piv = self.inv(M[col][col])
            for j in range(col, n + 1):
                M[col][j] = self.mul(M[col][j], inv_piv)
            for r in range(n):
                if r != col and M[r][col] != 0:
                    factor = M[r][col]
                    for j in range(col, n + 1):
                        M[r][j] = self.sub(M[r][j], self.mul(factor, M[col][j]))
        return [M[i][n] for i in range(n)]


def reed_solomon_gf256_demo() -> None:
    print("=== [2] Reed-Solomon [n=15, k=9, d_min=7] Code over GF(2^8) ===")
    gf = GF256(0x11D)
    payload = "VOYAGER-1"  # k = 9 bytes
    k = len(payload)
    t = 3                  # Can correct any t = 3 completely destroyed bytes
    n = k + 2 * t          # n = 15 total bytes (6 parity redundancy bytes)

    msg_coeffs = [ord(ch) for ch in payload]
    eval_points = [gf.exp[i] for i in range(n)]  # alpha^0, alpha^1, ..., alpha^(n-1)

    # Encode by evaluating P(x) across the n distinct field elements
    codeword = [gf.poly_eval(msg_coeffs, x) for x in eval_points]
    print(f"Original Payload (k={k}) : '{payload}' -> {msg_coeffs}")
    print(f"GF(2^8) RS Codeword    : {codeword}")

    # Corrupt t = 3 arbitrary bytes (simulating a 24-bit burst stain/scratch)
    received = codeword.copy()
    corrupted_indices = [1, 6, 13]
    received[1] ^= 0xFF
    received[6] ^= 0xA5
    received[13] ^= 0x3C
    print(f"Corrupted Received     : {received} (Destroyed indices: {corrupted_indices})")

    # Welch-Berlekamp Algebraic Decoding over GF(2^8):
    # Find degree-t monic error locator E(x) = e_0 + ... + e_{t-1} x^{t-1} + x^t
    # and degree-(<k+t) polynomial Q(x) such that Q(alpha_i) = y_i * E(alpha_i)
    A_mat, b_vec = [], []
    for i in range(n):
        x, y = eval_points[i], received[i]
        row = [gf.power(x, d) for d in range(k + t)]
        for d in range(t):
            row.append(gf.mul(y, gf.power(x, d)))
        A_mat.append(row)
        b_vec.append(gf.mul(y, gf.power(x, t)))

    sol = gf.solve_linear_system(A_mat, b_vec)
    E_coeffs = sol[k + t :] + [1]

    # Locate roots of E(x) == 0 to identify damaged coordinates
    detected_errors = [i for i, x in enumerate(eval_points) if gf.poly_eval(E_coeffs, x) == 0]
    valid_pairs = [(eval_points[i], received[i]) for i in range(n) if i not in detected_errors]

    # Reconstruct message polynomial P(x) from the first k uncorrupted evaluations
    V_mat = [[gf.power(x, d) for d in range(k)] for x, _ in valid_pairs[:k]]
    y_clean = [y for _, y in valid_pairs[:k]]
    recovered_coeffs = gf.solve_linear_system(V_mat, y_clean)
    recovered_str = "".join(chr(c) for c in recovered_coeffs)

    print(f"Algebraically Located Error Indices (E(x_i)=0): {detected_errors}")
    print(f"Recovered Coefficients : {recovered_coeffs}")
    print(f"Recovered String       : '{recovered_str}' (100% Match: {recovered_str == payload})")


if __name__ == "__main__":
    hamming74_verification()
    reed_solomon_gf256_demo()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

=== [1] Hamming [7, 4, 3] Code over GF(2) ===
4-bit Message m        : [1, 0, 1, 1]
7-bit Codeword c = mG  : [1, 0, 1, 1, 0, 1, 0]
Received y (idx 2 flip): [1, 0, 0, 1, 0, 1, 0]
Syndrome s = H y^T     : [0, 1, 1] -> Matches column index 2
Corrected Codeword     : [1, 0, 1, 1, 0, 1, 0]
Decoded Message        : [1, 0, 1, 1] (Bit-Exact: True)

=== [2] Reed-Solomon [n=15, k=9, d_min=7] Code over GF(2^8) ===
Original Payload (k=9) : 'VOYAGER-1' -> [86, 79, 89, 65, 71, 69, 82, 45, 49]
GF(2^8) RS Codeword    : [90, 206, 134, 152, 232, 6, 204, 198, 250, 20, 108, 195, 192, 240, 199]
Corrupted Received     : [90, 49, 134, 152, 232, 6, 105, 198, 250, 20, 108, 195, 192, 204, 199] (Destroyed indices: [1, 6, 13])
Algebraically Located Error Indices (E(x_i)=0): [1, 6, 13]
Recovered Coefficients : [86, 79, 89, 65, 71, 69, 82, 45, 49]
Recovered String       : 'VOYAGER-1' (100% Match: True)