Reed-Solomon Codes

The most widely deployed error correction code in history — from deep space to your pocket

Roadmap

Historical Origins

RS Codes as Non-Binary BCH

Finite Field Arithmetic: GF(2⁸)

GF(2⁸) Worked Examples

RS Code Parameters

The MDS Property

Generator Polynomial

Encoding: Systematic Method

Step-by-Step Encoding: RS(7, 3) over GF(2³)

RS Decoding Pipeline

Syndrome Computation

Berlekamp-Massey Algorithm

def berlekamp_massey(syndromes, t, gf):
    """Berlekamp-Massey algorithm over GF(2^m)."""
    n = 2 * t
    sigma = [1]        # error locator polynomial
    old_sigma = [1]    # previous sigma
    L = 0              # current LFSR length

    for r in range(n):
        # Compute discrepancy
        delta = syndromes[r]
        for j in range(1, len(sigma)):
            delta = gf.add(delta, gf.mul(sigma[j], syndromes[r - j]))

        # Shift old_sigma: multiply by x
        old_sigma = [0] + old_sigma

        if delta == 0:
            continue

        # Update sigma
        new_sigma = list(sigma)
        for j in range(len(old_sigma)):
            if j < len(new_sigma):
                new_sigma[j] = gf.add(new_sigma[j],
                                       gf.mul(delta, old_sigma[j]))
            else:
                new_sigma.append(gf.mul(delta, old_sigma[j]))

        if 2 * L <= r:
            # Length change
            old_sigma = [gf.mul(gf.inv(delta), s) for s in sigma]
            # Pad to account for the shift we already did
            old_sigma = [0] + old_sigma
            L = r + 1 - L

        sigma = new_sigma

    return sigma

BM Algorithm: Worked Example

Forney's Algorithm

Chien Search

def chien_search(sigma, n, gf):
    """Find roots of sigma(x) by exhaustive evaluation."""
    error_positions = []
    for i in range(n):
        # Evaluate sigma at alpha^(-i)
        x_inv = gf.exp_table[(255 - i) % 255]  # alpha^(-i)
        val = 0
        x_power = 1
        for coeff in sigma:
            val = gf.add(val, gf.mul(coeff, x_power))
            x_power = gf.mul(x_power, x_inv)
        if val == 0:
            error_positions.append(i)

    if len(error_positions) != len(sigma) - 1:
        return None  # Decoding failure!
    return error_positions

Erasure & Error+Erasure Decoding

RS(255, 223) in Deep Space

CD/DVD: CIRC

QR Codes & Reed-Solomon

QR codes use RS over GF(256) with p(x) = x⁸ + x⁴ + x³ + x² + 1 — the same field as our examples.

Reed-Solomon in RAID 6

Python: GF(2⁸) Arithmetic

class GF256:
    """Galois Field GF(2^8) with primitive polynomial x^8+x^4+x^3+x^2+1."""
    def __init__(self):
        self.exp_table = [0] * 512  # double-sized for convenience
        self.log_table = [0] * 256
        # Generate tables using primitive element alpha = 2
        x = 1
        for i in range(255):
            self.exp_table[i] = x
            self.log_table[x] = i
            x <<= 1  # multiply by alpha
            if x & 0x100:  # if x >= 256, reduce mod p(x)
                x ^= 0x11D  # p(x) = x^8 + x^4 + x^3 + x^2 + 1
        # Extend exp table for easy mod-free multiplication
        for i in range(255, 512):
            self.exp_table[i] = self.exp_table[i - 255]

    def add(self, a, b):
        return a ^ b  # addition = XOR

    def sub(self, a, b):
        return a ^ b  # same as addition in char 2

    def mul(self, a, b):
        if a == 0 or b == 0: return 0
        return self.exp_table[self.log_table[a] + self.log_table[b]]

    def div(self, a, b):
        if b == 0: raise ZeroDivisionError
        if a == 0: return 0
        return self.exp_table[(self.log_table[a] - self.log_table[b]) % 255]

    def inv(self, a):
        if a == 0: raise ZeroDivisionError
        return self.exp_table[255 - self.log_table[a]]

    def pow(self, a, n):
        if a == 0: return 0
        return self.exp_table[(self.log_table[a] * n) % 255]

Python: RS Encoder

class ReedSolomon:
    """Reed-Solomon encoder/decoder over GF(256)."""
    def __init__(self, n=255, k=223):
        self.n = n
        self.k = k
        self.t = (n - k) // 2  # error correction capability
        self.gf = GF256()
        self.generator = self._build_generator()

    def _build_generator(self):
        """Build generator polynomial g(x) = prod(x - alpha^i)."""
        g = [1]
        for i in range(1, 2 * self.t + 1):
            # Multiply g by (x - alpha^i)
            alpha_i = self.gf.exp_table[i]
            new_g = [0] * (len(g) + 1)
            for j in range(len(g)):
                new_g[j] = self.gf.add(new_g[j], g[j])
                new_g[j + 1] = self.gf.add(new_g[j + 1],
                                             self.gf.mul(g[j], alpha_i))
            g = new_g
        return g

    def encode(self, message):
        """Systematic RS encoding."""
        assert len(message) == self.k
        # Multiply message by x^(n-k)
        msg_padded = message + [0] * (self.n - self.k)
        # Compute remainder of msg_padded / generator
        remainder = list(msg_padded)
        for i in range(self.k):
            if remainder[i] != 0:
                coef = remainder[i]
                for j in range(len(self.generator)):
                    remainder[i + j] = self.gf.add(
                        remainder[i + j],
                        self.gf.mul(self.generator[j], coef))
        # Codeword = message + parity
        parity = remainder[self.k:]
        return message + parity

Python: RS Decoder

def decode(self, received):
    """Decode received RS codeword, correct up to t errors."""
    # Step 1: Compute syndromes
    syndromes = []
    for i in range(1, 2 * self.t + 1):
        s = 0
        for j in range(self.n):
            s = self.gf.add(s, self.gf.mul(received[j],
                            self.gf.pow(self.gf.exp_table[i], j)))
        syndromes.append(s)

    if all(s == 0 for s in syndromes):
        return received[:self.k]  # No errors

    # Step 2: Berlekamp-Massey -> error locator sigma(x)
    sigma = self._berlekamp_massey(syndromes)

    # Step 3: Chien search -> error positions
    positions = self._chien_search(sigma)
    if positions is None:
        raise ValueError("Decoding failure: too many errors")

    # Step 4: Forney's algorithm -> error values
    omega = self._error_evaluator(syndromes, sigma)
    sigma_deriv = self._formal_derivative(sigma)

    # Step 5: Compute error values and correct
    corrected = list(received)
    for pos in positions:
        x_inv = self.gf.inv(self.gf.exp_table[pos])
        # Evaluate omega and sigma' at x_inv
        omega_val = self._poly_eval(omega, x_inv)
        sigma_d_val = self._poly_eval(sigma_deriv, x_inv)
        # Error value
        error_val = self.gf.mul(self.gf.exp_table[pos],
                                self.gf.div(omega_val, sigma_d_val))
        corrected[pos] = self.gf.add(corrected[pos], error_val)

    return corrected[:self.k]

Python: RS Encode/Decode Demo

# Create RS(255, 223) codec
rs = ReedSolomon(n=255, k=223)

# Create a test message (223 bytes)
message = list(range(223))  # [0, 1, 2, ..., 222]

# Encode
codeword = rs.encode(message)
print(f"Message length:  {len(message)}")
print(f"Codeword length: {len(codeword)}")
print(f"Parity bytes:    {len(codeword) - len(message)}")

# Introduce 16 random symbol errors (maximum correctable)
import random
received = list(codeword)
error_positions = random.sample(range(255), 16)
for pos in error_positions:
    received[pos] ^= random.randint(1, 255)  # corrupt byte

errors = sum(a != b for a, b in zip(codeword, received))
print(f"\nErrors introduced: {errors}")

# Decode
try:
    decoded = rs.decode(received)
    if decoded == message:
        print("Decoding SUCCESS - all 16 errors corrected!")
    else:
        print("Decoding produced wrong result")
except ValueError as e:
    print(f"Decoding failed: {e}")

# Test with 17 errors (beyond correction capability)
received2 = list(codeword)
for pos in random.sample(range(255), 17):
    received2[pos] ^= random.randint(1, 255)
try:
    rs.decode(received2)
    print("WARNING: 17 errors decoded (miscorrection!)")
except ValueError:
    print("17 errors correctly detected as uncorrectable")

RS Performance & Comparison

Why RS is "The Most Widely Deployed Code"

Summary