Error-Correcting Codes

Why Error-Correcting Codes Matters

A checksum can warn that a stored or transmitted record is inconsistent, but a warning alone does not restore the original bytes. Error-correcting codes add structured redundancy so a receiver can identify the original message when the corruption stays within a stated limit. A memory read with one flipped bit can then be repaired without requesting another copy.

The central design idea is to keep valid encodings far apart. A small change should move a valid codeword into a region where it is still closer to its original codeword than to any other. Enough redundancy turns that geometric idea into exact parity checks or finite-field equations.

This lesson implements Hamming $(7,4)$ and its extended $(8,4)$ SECDED version in Python, C++, and Java. It also develops Reed–Solomon and BCH overviews with concrete parameters, finite-field examples, decoding stages, and correction bounds. The runnable programs concentrate on Hamming so the entire encoder, decoder, and failure boundary remain visible.

You will encode a nibble, locate a single flipped bit using its syndrome, repair a byte payload, and detect a double-bit error with SECDED. You will also see a three-bit pattern that causes a wrong correction. That last example is essential: a decoder cannot promise recovery after an unlimited number of changes.

The error model here is substitution at known bit or symbol positions. Inserted/deleted bits, lost block alignment, or missing length information require additional framing or different codes. Nothing here authenticates a sender; the goal is bounded-error recovery.

Core Concepts and Terminology

A block code maps $k$ data symbols to $n$ code symbols. Its rate is $R=k/n$. A symbol may be one bit or an element of a larger finite field, so always state which unit is counted.

The Hamming distance $d(x,y)$ is the number of coordinates where equal-length words differ. The minimum distance $d_{\min}$ is the smallest distance between distinct valid codewords. A membership test can detect every nonzero error affecting fewer than $d_{\min}$ coordinates. Unique decoding can correct up to $$ t=\left\lfloor\frac{d_{\min}-1}{2}\right\rfloor $$ unknown errors. If there are $e$ unknown errors and $v$ erasures, whose locations are known, unique recovery is guaranteed when $$ 2e+v\lt d_{\min}. $$ An erasure is easier than an unknown error because the decoder already knows which coordinate is unreliable.

Hamming layout used by the programs. Number bit positions $1$ through $7$. Place parity bits at $1,2,4$, and data at $3,5,6,7$. For input nibble $d_3d_2d_1d_0$, these four data positions receive the bits from most significant to least significant. Each parity bit makes its selected group XOR to zero: $$ p_1=d_3\oplus d_2\oplus d_0,\qquad p_2=d_3\oplus d_1\oplus d_0,\qquad p_4=d_2\oplus d_1\oplus d_0. $$ Here $\oplus$ is addition modulo two, or XOR. Check $1$ covers positions $1,3,5,7$; check $2$ covers $2,3,6,7$; check $4$ covers $4,5,6,7$. Position $j$ belongs to check $p$ exactly when the corresponding binary index bit is set: j & p != 0.

In the integer representation, position $p$ is bit $p-1$, so position $1$ is the least-significant bit. Diagrams display positions $1$ to $8$ left to right, which is different from the usual most-significant-bit-first rendering of an integer. This explicit convention prevents a correct parity formula from being applied to the wrong layout.

Extended Hamming and SECDED. Append position $8$ so the XOR of all eight bits is zero. Hamming $(7,4)$ has minimum distance $3$; extended Hamming $(8,4)$ has minimum distance $4$. The latter supports single-error correction, double-error detection, abbreviated SECDED, with the decoder policy given below.

Syndrome. For received bits $r_1,\ldots,r_7$, the three check results are $$ s_1=r_1\oplus r_3\oplus r_5\oplus r_7,\quad s_2=r_2\oplus r_3\oplus r_6\oplus r_7,\quad s_4=r_4\oplus r_5\oplus r_6\oplus r_7. $$ Read their numeric label as $s=s_1+2s_2+4s_4$. For a single error in positions $1$ through $7$, that number equals the erroneous position. An overall-parity bit error has syndrome zero but changes total parity.

Scope of a status report. A code's distance and a decoder's policy are related but different. A distance-$4$ membership test detects all one-, two-, and three-bit changes from a valid word. A SECDED decoder also tries to repair single errors; a three-bit change can resemble a single error from a different codeword and therefore be miscorrected. The implementation's statuses must be interpreted with its per-block error bound.

How Error-Correcting Codes Works, Step by Step

Encode Hamming and extended Hamming. Put the nibble's data bits into positions $3,5,6,7$, with parity positions initially zero. Compute the three group XORs and set positions $1,2,4$ so each check is even. If extended mode is selected, set position $8$ to the XOR of the first seven bits, making the total parity even.

Decode plain Hamming. Compute the syndrome. Zero means the received word passes the three checks. For nonzero $s$, flip position $s$, then extract data positions $3,5,6,7$. This repairs every single-bit error in the seven-bit block. A nonzero syndrome alone does not distinguish one error from several, so plain Hamming's automatic correction can miscorrect a two-bit error.

Decode extended Hamming. Compute the same syndrome from the first seven positions and let $p$ be the XOR of all eight received bits. Under the assumption of at most two flipped bits in the block, use these four cases:

• $s=0,p=0$: no repair is needed; report CLEAN.
• $s\ne0,p=1$: flip position $s$ and report CORRECTED.
• $s=0,p=1$: flip the overall-parity bit at position $8$ and report CORRECTED.
• $s\ne0,p=0$: report DETECTED_DOUBLE and return no decoded nibble.

The diagram follows the one-bit case. In all modes the data positions are extracted only after any selected repair. The flowchart shows extended SECDED; plain mode omits total-parity classification.

Reed–Solomon overview: evaluations over a field. Choose a finite field $\mathbb F_q$, $n$ distinct evaluation points, and a message polynomial $m(x)$ of degree less than $k$. Encode its values at those points: $$ c=(m(\alpha_1),\ldots,m(\alpha_n)). $$ The evaluation code has parameters $[n,k,n-k+1]_q$. A nonzero polynomial of degree at most $k-1$ cannot vanish at more than $k-1$ distinct points, which explains its distance. Arithmetic is field arithmetic: in $\mathrm{GF}(2^8)$, multiplication is not ordinary multiplication modulo $256$.

For a complete small example, work over integers modulo $7$, use $k=3$, and evaluate $$ m(x)=1+2x+3x^2 $$ at $x=0,1,2,3,4$. The five transmitted symbols are $(1,6,3,6,1)$. This is a $[5,3,3]_7$ code: it can correct one unknown symbol error, or recover two known erasures. Change the third symbol from $3$ to $4$, receiving $(1,6,4,6,1)$. A decoder may try the ten three-point interpolation subsets and select the unique degree-below-three candidate agreeing with at least four received points. That candidate is the original polynomial; the mismatch identifies evaluation point $2$.

To verify one candidate by hand, use uncorrupted points $0,1,4$. Write it $a+bx+cx^2$. Point $0$ gives $a=1$; the others give $b+c=5$ and $4b+2c=0$ modulo $7$. Subtracting twice the first relation gives $2b=4$, so $b=2$ and $c=3$. This candidate agrees at four points; simply picking three points without validating agreement would not be a complete error decoder.

Practical algebraic RS decoders avoid testing all subsets. A common cyclic-code pathway computes syndromes, solves for an error-locator polynomial using Berlekamp–Massey or the extended Euclidean algorithm, finds error locations, determines field-valued error magnitudes, and verifies the candidate. Erasure locations can be incorporated into the equations. A conventional $[255,223,33]_{256}$ code corrects up to $16$ unknown symbol errors or $32$ known erasures, with mixtures satisfying $2e+v\le32$. Multiple flipped bits within one byte-sized symbol still count as one symbol error.

BCH overview: enforce consecutive roots. Binary primitive narrow-sense BCH codes of length $n=2^m-1$ use a primitive element $\alpha$ of $\mathrm{GF}(2^m)$. To obtain designed distance $\delta$, require codeword polynomials to vanish at $\alpha,\alpha^2,\ldots,\alpha^{\delta-1}$. Their binary generator is the least common multiple of the corresponding minimal polynomials. The BCH bound gives $d_{\min}\ge\delta$.

For a concrete $[15,7,5]_2$ code, represent $\mathrm{GF}(16)$ using primitive polynomial $x^4+x+1$ and choose $\delta=5$. The required minimal-polynomial factors yield $$ g(x)=(x^4+x+1)(x^4+x^3+x^2+x+1) =x^8+x^7+x^6+x^4+1. $$ It has degree $8$, so the data dimension is $15-8=7$, and it corrects two unknown bit errors. A systematic encoder forms $x^8m(x)$ and XORs in its remainder modulo $g(x)$, producing a multiple of $g$. For message polynomial $m(x)=1$, the codeword is $g(x)$ itself, hexadecimal 1D1 in coefficient-bit order.

A binary BCH decoder computes $S_j=r(\alpha^j)$ for the required roots, solves for an error locator, and uses a Chien search to locate roots corresponding to bit positions. Binary error magnitudes are one, so it flips those positions and checks the resulting codeword. Beyond the correction radius, a valid-looking candidate can still be wrong. Guruswami's coding-theory notes develop RS and BCH constructions; MIT's BCH notes give further syndrome-based examples.

flowchart TD
    A["Read one valid eight-bit received word"] --> B["Compute Hamming syndrome s and total parity p"]
    B --> C{"Total parity p is one?"}
    C -->|"Yes"| D{"Syndrome s is zero?"}
    D -->|"Yes"| E["Flip position 8"]
    D -->|"No"| F["Flip position s"]
    E --> G["Extract data; report CORRECTED"]
    F --> G
    C -->|"No"| H{"Syndrome s is zero?"}
    H -->|"Yes"| I["Extract data; report CLEAN"]
    H -->|"No"| J["Report DETECTED_DOUBLE; withhold data"]
    G --> K["Interpret status under the per-block error bound"]
    I --> K
    J --> K

Worked Example with a Full Trace

Encode data nibble A, binary $d_3d_2d_1d_0=1010$, in extended Hamming mode. All positions below are one-based, and position $p$ is integer bit $p-1$.

Every encoding state.

1. Place data: positions $3,5,6,7$ receive $1,0,1,0$. All parity bits initially zero. The integer word is 24 hex, with bits in position order 0 0 1 0 0 1 0 0.
2. Set $p_1=1\oplus0\oplus0=1$. The word becomes 25.
3. Set $p_2=1\oplus1\oplus0=0$. The word remains 25.
4. Set $p_4=0\oplus1\oplus0=1$. The word becomes 2D.
5. The first seven positions contain four ones, so set $p_8=0$ for even overall parity. The final word remains 2D, with bits in position order 1 0 1 1 0 1 0 0.

Introduce and locate one error. Flip position $6$, whose integer mask is $1\ll5=\texttt{20}$ hex. The receiver gets 2D XOR 20 = 0D, with position-order bits 1 0 1 1 0 0 0 0.

Compute all check values from those received bits: $$ s_1=1\oplus1\oplus0\oplus0=0,\qquad s_2=0\oplus1\oplus0\oplus0=1,\qquad s_4=1\oplus0\oplus0\oplus0=1. $$ Thus $s=0+2+4=6$. Total parity is the XOR of three ones, so $p=1$. The SECDED rule selects position $6$. Flip it to recover 2D; the three group checks and total parity now all vanish. Extracting positions $3,5,6,7$ gives 1010, nibble A.

Overall-parity-only error. Flip position $8$ instead, producing AD. The first seven checks still give $s=0$, while total parity is $1$. The decoder flips position $8$ back and recovers the same nibble.

Double error. Flip positions $3$ and $6$ in 2D. The received word is 09. Its syndrome is $3\mathbin{\mathrm{XOR}}6=5$, and total parity is even. The decoder reports DETECTED_DOUBLE and returns data sentinel $-1$. In plain seven-bit mode, the same syndrome would trigger an incorrect flip at position $5$, producing 19 and nibble $4$.

Full byte round trip. Payload byte A5 is split high nibble first. A encodes as 2D and $5$ encodes as D2. Corrupt position $6$ in the first word and position $8$ in the second. Each block has one error, so both are repairable independently; the wrapper reconstructs A5 and records two applied corrections. A two-error condition is measured per codeword, not by counting all errors across the whole payload.

Outside the guarantee. Flip positions $3,5,6$ in original word 2D, receiving 19. Its syndrome is zero and its total parity is one. The decoder treats it as an overall-parity error, flips position $8$, and returns valid word 99 with data $4$. Its status is CORRECTED even though the original data was A. The same received word could really have come from data $4$ with one parity-bit error; the bits alone cannot identify which history occurred.

Implementation in Python, C++, and Java

Each panel is a complete deterministic program implementing plain Hamming and extended SECDED. Use Python 3.9+, C++17, or Java 8+; save the Java panel as Main.java. The Reed–Solomon and BCH sections are mathematical and algorithmic overviews; these panels do not claim to implement their field arithmetic or algebraic decoders.

encode_nibble(value, extended) maps an integer $0$ through $15$ to a codeword. Extended mode is the default in Python/C++; Java takes the Boolean explicitly. decode_word(received, extended) returns a Block containing status, decoded nibble, post-decision word, syndrome, total-parity result, and applied correction position. Plain mode requires a word in $[0,127]$ and reports overall = -1; extended mode accepts $[0,255]$. Correction positions are one-based, with zero meaning no flip.

In DETECTED_DOUBLE, data = -1 and word is the unchanged received word; no repair was attempted. The label is the standard SECDED branch name: outside the two-error assumption, an even higher-weight error may reach that branch too. CLEAN means the checks passed. CORRECTED means one flip was applied under the decoder's model. Neither status proves originality for arbitrary multi-bit corruption.

encode_bytes(payload, extended) accepts up to $4096$ byte values in $[0,255]$, encodes the high nibble then the low nibble, and returns two codeword integers per input byte. decode_bytes(words, extended) accepts up to $8192$ words and requires an even word count. It checks every block and returns a Packet containing aggregate status, payload bytes, the count of applied flips, and all block records. If any block reports DETECTED_DOUBLE, the aggregate data list is empty; the records remain available for inspection.

The aggregate corrections field counts words on which a flip was applied, including when another block caused the payload to be withheld. Outside the error bound, such a flip can be a miscorrection. If no detected-double branch occurs, the aggregate status is CORRECTED when at least one flip was applied and CLEAN otherwise. Empty input is valid and gives a clean empty result.

All bit positions map to integer bit $p-1$. These routines operate on known word boundaries. They add no header, block count, or integrity tag, and they do not detect all lost, duplicated, or reordered codewords. An enclosing format must preserve alignment and length and supply any additional validation required by the application.

Errors raise ValueError, invalid_argument, or IllegalArgumentException with labels NIBBLE, CODEWORD, BYTE, SIZE, or LENGTH as applicable. Python also raises MODE unless the mode is an actual Boolean, and rejects Boolean/floating-point data elements. Python sequence inputs may be lists, tuples, bytes, or bytearray; Java rejects null arrays; C++ uses statically typed vectors. Inputs are never mutated.

Returned integer containers are for clarity. One extended word fits exactly one octet; the plain seven-bit word also occupies an octet if stored that way, with its high bit zero. The wrapper does not pack adjacent seven-bit words into a dense bitstream. C++/Java integer arrays take more memory than those logical wire bytes.

The sample first checks a clean round trip, then prints single-bit repair, parity-bit repair, double-bit rejection, repaired payload A5, and two explicit miscorrections beyond the relevant bound. Python/C++ use assertions for sample checks; Java performs explicit checks even with language assertions disabled.

from dataclasses import dataclass

MAX_PAYLOAD = 4096
DATA_POSITIONS = (3, 5, 6, 7)


@dataclass
class Block:
    status: str
    data: int
    word: int
    syndrome: int
    overall: int
    position: int


@dataclass
class Packet:
    status: str
    data: list[int]
    corrections: int
    blocks: list[Block]


def check_mode(extended):
    if type(extended) is not bool:
        raise ValueError("MODE")


def check_sequence(values, limit, maximum, label):
    if not isinstance(values, (list, tuple, bytes, bytearray)):
        raise ValueError(label)
    if len(values) > limit:
        raise ValueError("SIZE")
    if any(type(v) is not int or not 0 <= v <= maximum for v in values):
        raise ValueError(label)


def encode_nibble(value, extended=True):
    check_mode(extended)
    if type(value) is not int or not 0 <= value <= 15:
        raise ValueError("NIBBLE")
    word = 0
    for j, position in enumerate(DATA_POSITIONS):
        word |= ((value >> (3 - j)) & 1) << (position - 1)
    for parity_position in (1, 2, 4):
        bit = 0
        for position in range(1, 8):
            if position & parity_position:
                bit ^= (word >> (position - 1)) & 1
        word |= bit << (parity_position - 1)
    if extended:
        parity = 0
        for j in range(7):
            parity ^= (word >> j) & 1
        word |= parity << 7
    return word


def decode_word(received, extended=True):
    check_mode(extended)
    maximum = 255 if extended else 127
    if type(received) is not int or not 0 <= received <= maximum:
        raise ValueError("CODEWORD")
    syndrome = 0
    for position in range(1, 8):
        if (received >> (position - 1)) & 1:
            syndrome ^= position
    overall = -1
    if extended:
        overall = 0
        for j in range(8):
            overall ^= (received >> j) & 1
    word, position, status = received, 0, "CLEAN"
    if extended and syndrome != 0 and overall == 0:
        return Block("DETECTED_DOUBLE", -1, received, syndrome, overall, 0)
    if syndrome != 0:
        position = syndrome
    elif extended and overall == 1:
        position = 8
    if position:
        word ^= 1 << (position - 1)
        status = "CORRECTED"
    data = 0
    for p in DATA_POSITIONS:
        data = (data << 1) | ((word >> (p - 1)) & 1)
    return Block(status, data, word, syndrome, overall, position)


def encode_bytes(payload, extended=True):
    check_mode(extended)
    check_sequence(payload, MAX_PAYLOAD, 255, "BYTE")
    words = []
    for value in payload:
        words.extend((encode_nibble(value >> 4, extended),
                      encode_nibble(value & 15, extended)))
    return words


def decode_bytes(words, extended=True):
    check_mode(extended)
    check_sequence(words, 2 * MAX_PAYLOAD, 255 if extended else 127, "CODEWORD")
    if len(words) % 2:
        raise ValueError("LENGTH")
    blocks = [decode_word(word, extended) for word in words]
    corrections = sum(b.status == "CORRECTED" for b in blocks)
    if any(b.status == "DETECTED_DOUBLE" for b in blocks):
        return Packet("DETECTED_DOUBLE", [], corrections, blocks)
    data = [(blocks[i].data << 4) | blocks[i + 1].data
            for i in range(0, len(blocks), 2)]
    return Packet("CORRECTED" if corrections else "CLEAN", data, corrections, blocks)


def show(label, b):
    data = f"{b.data:X}" if b.data >= 0 else "NONE"
    print(f"{label}={b.status} data={data} syndrome={b.syndrome} "
          f"overall={b.overall} position={b.position} word={b.word:02X}")


if __name__ == "__main__":
    payload = [0xA5]
    words = encode_bytes(payload)
    assert decode_bytes(words).data == payload
    print("payload=A5")
    print("encoded=" + " ".join(f"{w:02X}" for w in words))
    code = encode_nibble(0xA)
    show("single", decode_word(code ^ (1 << 5)))
    show("parity", decode_word(code ^ (1 << 7)))
    double = decode_word(code ^ (1 << 2) ^ (1 << 5))
    assert double.status == "DETECTED_DOUBLE" and double.data == -1
    show("double", double)
    damaged = [words[0] ^ (1 << 5), words[1] ^ (1 << 7)]
    restored = decode_bytes(damaged)
    assert restored.data == payload and restored.corrections == 2
    print("restored=" + "".join(f"{v:02X}" for v in restored.data)
          + f" status={restored.status} corrections={restored.corrections}")
    show("plain-double", decode_word(encode_nibble(0xA, False) ^ 4 ^ 32, False))
    show("triple", decode_word(code ^ 4 ^ 16 ^ 32))

#include <cassert>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
using namespace std;

constexpr int MAX_PAYLOAD = 4096;
const vector<int> DATA_POSITIONS = {3, 5, 6, 7};
struct Block {
    string status;
    int data, word, syndrome, overall, position;
};
struct Packet {
    string status;
    vector<int> data;
    int corrections;
    vector<Block> blocks;
};
void check_sequence(const vector<int>& values, size_t limit, int maximum,
                    const string& label) {
    if (values.size() > limit) throw invalid_argument("SIZE");
    for (int v : values) if (v < 0 || v > maximum) throw invalid_argument(label);
}
int encode_nibble(int value, bool extended = true) {
    if (value < 0 || value > 15) throw invalid_argument("NIBBLE");
    int word = 0;
    for (int j = 0; j < 4; ++j)
        word |= ((value >> (3 - j)) & 1) << (DATA_POSITIONS[j] - 1);
    for (int p : {1, 2, 4}) {
        int bit = 0;
        for (int position = 1; position <= 7; ++position)
            if (position & p) bit ^= (word >> (position - 1)) & 1;
        word |= bit << (p - 1);
    }
    if (extended) {
        int parity = 0;
        for (int j = 0; j < 7; ++j) parity ^= (word >> j) & 1;
        word |= parity << 7;
    }
    return word;
}
Block decode_word(int received, bool extended = true) {
    int maximum = extended ? 255 : 127;
    if (received < 0 || received > maximum) throw invalid_argument("CODEWORD");
    int syndrome = 0;
    for (int p = 1; p <= 7; ++p)
        if ((received >> (p - 1)) & 1) syndrome ^= p;
    int overall = -1;
    if (extended) {
        overall = 0;
        for (int j = 0; j < 8; ++j) overall ^= (received >> j) & 1;
    }
    int word = received, position = 0;
    string status = "CLEAN";
    if (extended && syndrome != 0 && overall == 0)
        return {"DETECTED_DOUBLE", -1, received, syndrome, overall, 0};
    if (syndrome != 0) position = syndrome;
    else if (extended && overall == 1) position = 8;
    if (position) {
        word ^= 1 << (position - 1);
        status = "CORRECTED";
    }
    int data = 0;
    for (int p : DATA_POSITIONS) data = (data << 1) | ((word >> (p - 1)) & 1);
    return {status, data, word, syndrome, overall, position};
}
vector<int> encode_bytes(const vector<int>& payload, bool extended = true) {
    check_sequence(payload, MAX_PAYLOAD, 255, "BYTE");
    vector<int> words;
    for (int value : payload) {
        words.push_back(encode_nibble(value >> 4, extended));
        words.push_back(encode_nibble(value & 15, extended));
    }
    return words;
}
Packet decode_bytes(const vector<int>& words, bool extended = true) {
    check_sequence(words, 2 * MAX_PAYLOAD, extended ? 255 : 127, "CODEWORD");
    if (words.size() % 2) throw invalid_argument("LENGTH");
    vector<Block> blocks;
    int corrections = 0; bool detected = false;
    for (int word : words) {
        Block b = decode_word(word, extended);
        corrections += b.status == "CORRECTED";
        detected = detected || b.status == "DETECTED_DOUBLE";
        blocks.push_back(b);
    }
    if (detected) return {"DETECTED_DOUBLE", {}, corrections, blocks};
    vector<int> data;
    for (size_t i = 0; i < blocks.size(); i += 2)
        data.push_back((blocks[i].data << 4) | blocks[i + 1].data);
    return {corrections ? "CORRECTED" : "CLEAN", data, corrections, blocks};
}
string hexadecimal(int value, int digits) {
    ostringstream s; s << uppercase << hex << setw(digits) << setfill('0') << value;
    return s.str();
}
void show(const string& label, const Block& b) {
    cout << label << '=' << b.status << " data="
         << (b.data >= 0 ? hexadecimal(b.data, 1) : "NONE")
         << " syndrome=" << b.syndrome << " overall=" << b.overall
         << " position=" << b.position << " word=" << hexadecimal(b.word, 2) << '\n';
}
int main() {
    vector<int> payload = {0xA5};
    auto words = encode_bytes(payload);
    assert(decode_bytes(words).data == payload);
    cout << "payload=A5\nencoded=";
    for (size_t i = 0; i < words.size(); ++i) {
        if (i) cout << ' ';
        cout << hexadecimal(words[i], 2);
    }
    cout << '\n';
    int code = encode_nibble(0xA);
    show("single", decode_word(code ^ (1 << 5)));
    show("parity", decode_word(code ^ (1 << 7)));
    Block double_error = decode_word(code ^ 4 ^ 32);
    assert(double_error.status == "DETECTED_DOUBLE" && double_error.data == -1);
    show("double", double_error);
    vector<int> damaged = {words[0] ^ 32, words[1] ^ 128};
    Packet restored = decode_bytes(damaged);
    assert(restored.data == payload && restored.corrections == 2);
    cout << "restored=";
    for (int v : restored.data) cout << hexadecimal(v, 2);
    cout << " status=" << restored.status << " corrections=" << restored.corrections << '\n';
    show("plain-double", decode_word(encode_nibble(0xA, false) ^ 4 ^ 32, false));
    show("triple", decode_word(code ^ 4 ^ 16 ^ 32));
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static final int MAX_PAYLOAD = 4096;
    static final int[] DATA_POSITIONS = {3, 5, 6, 7};
    static class Block {
        String status;
        int data, word, syndrome, overall, position;
        Block(String status, int data, int word, int syndrome, int overall, int position) {
            this.status = status; this.data = data; this.word = word;
            this.syndrome = syndrome; this.overall = overall; this.position = position;
        }
    }
    static class Packet {
        String status;
        int[] data;
        int corrections;
        List<Block> blocks;
        Packet(String status, int[] data, int corrections, List<Block> blocks) {
            this.status = status; this.data = data; this.corrections = corrections;
            this.blocks = blocks;
        }
    }
    static void check_sequence(int[] values, int limit, int maximum, String label) {
        if (values == null) throw new IllegalArgumentException(label);
        if (values.length > limit) throw new IllegalArgumentException("SIZE");
        for (int v : values) if (v < 0 || v > maximum) throw new IllegalArgumentException(label);
    }
    static int encode_nibble(int value, boolean extended) {
        if (value < 0 || value > 15) throw new IllegalArgumentException("NIBBLE");
        int word = 0;
        for (int j = 0; j < 4; ++j)
            word |= ((value >> (3 - j)) & 1) << (DATA_POSITIONS[j] - 1);
        for (int p : new int[]{1, 2, 4}) {
            int bit = 0;
            for (int position = 1; position <= 7; ++position)
                if ((position & p) != 0) bit ^= (word >> (position - 1)) & 1;
            word |= bit << (p - 1);
        }
        if (extended) {
            int parity = 0;
            for (int j = 0; j < 7; ++j) parity ^= (word >> j) & 1;
            word |= parity << 7;
        }
        return word;
    }
    static Block decode_word(int received, boolean extended) {
        if (received < 0 || received > (extended ? 255 : 127))
            throw new IllegalArgumentException("CODEWORD");
        int syndrome = 0;
        for (int p = 1; p <= 7; ++p)
            if (((received >> (p - 1)) & 1) != 0) syndrome ^= p;
        int overall = -1;
        if (extended) {
            overall = 0;
            for (int j = 0; j < 8; ++j) overall ^= (received >> j) & 1;
        }
        int word = received, position = 0;
        String status = "CLEAN";
        if (extended && syndrome != 0 && overall == 0)
            return new Block("DETECTED_DOUBLE", -1, received, syndrome, overall, 0);
        if (syndrome != 0) position = syndrome;
        else if (extended && overall == 1) position = 8;
        if (position != 0) {
            word ^= 1 << (position - 1);
            status = "CORRECTED";
        }
        int data = 0;
        for (int p : DATA_POSITIONS) data = (data << 1) | ((word >> (p - 1)) & 1);
        return new Block(status, data, word, syndrome, overall, position);
    }
    static int[] encode_bytes(int[] payload, boolean extended) {
        check_sequence(payload, MAX_PAYLOAD, 255, "BYTE");
        int[] words = new int[2 * payload.length];
        for (int i = 0; i < payload.length; ++i) {
            words[2 * i] = encode_nibble(payload[i] >> 4, extended);
            words[2 * i + 1] = encode_nibble(payload[i] & 15, extended);
        }
        return words;
    }
    static Packet decode_bytes(int[] words, boolean extended) {
        check_sequence(words, 2 * MAX_PAYLOAD, extended ? 255 : 127, "CODEWORD");
        if (words.length % 2 != 0) throw new IllegalArgumentException("LENGTH");
        List<Block> blocks = new ArrayList<>();
        int corrections = 0; boolean detected = false;
        for (int word : words) {
            Block b = decode_word(word, extended);
            if (b.status.equals("CORRECTED")) ++corrections;
            if (b.status.equals("DETECTED_DOUBLE")) detected = true;
            blocks.add(b);
        }
        if (detected) return new Packet("DETECTED_DOUBLE", new int[0], corrections, blocks);
        int[] data = new int[words.length / 2];
        for (int i = 0; i < data.length; ++i)
            data[i] = (blocks.get(2 * i).data << 4) | blocks.get(2 * i + 1).data;
        return new Packet(corrections != 0 ? "CORRECTED" : "CLEAN", data, corrections, blocks);
    }
    static String hexadecimal(int value, int digits) {
        StringBuilder s = new StringBuilder();
        for (int j = digits - 1; j >= 0; --j)
            s.append("0123456789ABCDEF".charAt((value >>> (4 * j)) & 15));
        return s.toString();
    }
    static void show(String label, Block b) {
        System.out.println(label + "=" + b.status + " data="
                + (b.data >= 0 ? hexadecimal(b.data, 1) : "NONE")
                + " syndrome=" + b.syndrome + " overall=" + b.overall
                + " position=" + b.position + " word=" + hexadecimal(b.word, 2));
    }
    public static void main(String[] args) {
        int[] payload = {0xA5};
        int[] words = encode_bytes(payload, true);
        if (!Arrays.equals(decode_bytes(words, true).data, payload))
            throw new AssertionError("round trip failed");
        System.out.println("payload=A5");
        StringBuilder encoded = new StringBuilder();
        for (int word : words) {
            if (encoded.length() != 0) encoded.append(' ');
            encoded.append(hexadecimal(word, 2));
        }
        System.out.println("encoded=" + encoded);
        int code = encode_nibble(0xA, true);
        show("single", decode_word(code ^ 32, true));
        show("parity", decode_word(code ^ 128, true));
        Block double_error = decode_word(code ^ 4 ^ 32, true);
        if (!double_error.status.equals("DETECTED_DOUBLE") || double_error.data != -1)
            throw new AssertionError("double error not rejected");
        show("double", double_error);
        int[] damaged = {words[0] ^ 32, words[1] ^ 128};
        Packet restored = decode_bytes(damaged, true);
        if (!Arrays.equals(restored.data, payload) || restored.corrections != 2)
            throw new AssertionError("repair failed");
        StringBuilder text = new StringBuilder();
        for (int v : restored.data) text.append(hexadecimal(v, 2));
        System.out.println("restored=" + text + " status=" + restored.status
                + " corrections=" + restored.corrections);
        show("plain-double", decode_word(encode_nibble(0xA, false) ^ 4 ^ 32, false));
        show("triple", decode_word(code ^ 4 ^ 16 ^ 32, true));
    }
}

Expected standard output, identical in all three languages:

• payload=A5
• encoded=2D D2
• single=CORRECTED data=A syndrome=6 overall=1 position=6 word=2D
• parity=CORRECTED data=A syndrome=0 overall=1 position=8 word=2D
• double=DETECTED_DOUBLE data=NONE syndrome=5 overall=0 position=0 word=09
• restored=A5 status=CORRECTED corrections=2
• plain-double=CORRECTED data=4 syndrome=5 overall=-1 position=5 word=19
• triple=CORRECTED data=4 syndrome=0 overall=1 position=8 word=99

Complexity, Correctness, and Invariants

Implemented complexity. Each Hamming block has fixed length seven or eight, so encoding or decoding one nibble takes $O(1)$ time and space. For a payload of $b$ bytes, the wrapper processes $2b$ words in $\Theta(b+1)$ time. All valid-input best, average, and worst cases are linear at payload scale. It inspects every block even after a detected error so it can return a complete diagnostic list.

The core decoder's working state is constant. The wrappers retain output words, reconstructed bytes, and block records, so actual storage is $O(b)$, including those results. A streaming implementation can avoid retaining all diagnostic records, but withholding a whole payload until every block passes may still require buffering.

For a general Hamming code with $r$ check bits, length $N=2^r-1$ and dimension $K=N-r$, a direct implementation evaluating all $r$ checks by scanning all positions uses $O(Nr)=O(N\log N)$ bit tests. XORing the indices of set received bits computes the syndrome in $O(N)$ index-word operations when an $r$-bit index fits one machine word. These are generalizations; the provided code intentionally fixes the small layout.

Parity-check invariant. Let $H$ be the binary matrix whose column $j$ is the three-bit binary representation of position $j$, for $j=1,\ldots,7$. Row order corresponds to check labels $1,2,4$. A valid codeword $c$ satisfies $$ Hc^\top=0 $$ over $\mathrm{GF}(2)$. Each parity-position column has only its own check bit set, so setting those parity bits fixes its check without disturbing the others. Extended encoding additionally ensures the XOR of all eight bits is zero.

If received word $r=c\oplus e_j$ has one error in position $j\le7$, then $$ Hr^\top=Hc^\top\oplus He_j^\top=h_j, $$ where $h_j$ is column $j$, the binary label of that position. The decoder's XOR of the indices of set bits computes the same syndrome because the sum is over $\mathrm{GF}(2)$. Flipping the identified bit cancels the error.

Distance and classification. No Hamming column is zero and no two columns are equal, so no valid nonzero codeword has weight one or two. Columns $1,2,3$ XOR to zero, giving a weight-three codeword, so $d_{\min}=3$. Adding overall parity makes all codeword weights even and raises the minimum distance to four.

In extended mode, one error always gives odd total parity; the zero column for position $8$ distinguishes that bit's error from errors in positions $1$ through $7$. Two distinct flips give even parity and a nonzero XOR of their position columns, including the zero column for the overall bit. Thus they reach DETECTED_DOUBLE. With no error both checks vanish. These arguments prove every branch under the at-most-two-flip assumption.

Why the distance bound works. If a received word were within $t$ errors of two different codewords, those codewords would be at distance at most $2t$. This contradicts $2t\lt d_{\min}$. Known erasures remove coordinates where two candidate codewords might differ, leading to the more general condition $2e+v\lt d_{\min}$. Outside the bound, overlapping explanations may exist; a post-repair zero syndrome does not rule them out.

RS and BCH overview costs. Direct RS evaluation encoding uses $O(nk)$ field operations. Erasure-only recovery from $k$ surviving evaluations can use $O(k^2)$ field operations with Newton interpolation. A conventional syndrome/Berlekamp–Massey/Chien-search decoding path for a $t$-error-correcting cyclic RS or BCH code uses about $O(nt+t^2)$ field operations for those stages; representation, magnitudes, and verification add related work. Field-operation cost depends on the extension degree and implementation. Faster algorithms exist, so this is an algorithm-specific baseline rather than a universal complexity for all decoders.

RS achieves distance $n-k+1$ because two distinct degree-below-$k$ message polynomials can agree at at most $k-1$ distinct evaluation points. Binary BCH enforces a set of roots whose designed-distance bound supplies its correction guarantee. Both use the same separation principle as Hamming, with richer algebra to locate more errors.

Variants, Pitfalls, and Optimizations

Do not confuse detection mode with correction mode. A distance-$3$ code can detect up to two errors by rejecting every non-codeword, or correct one by moving to the nearby codeword. It cannot always do both with the same received bits. Similarly, distance-$4$ permits detection-only rejection of up to three errors, while the SECDED policy combines one-error correction with two-error detection. MIT's channel-coding lecture explains these distinct choices.

A clean syndrome is not an originality test. Any valid codeword has zero syndrome. A large enough error can transform one valid codeword into another. The worked four-bit change from 2D to 99 is a direct example. A triple error can instead place the received word one step from another valid word and trigger an apparently successful repair. The implementation deliberately prints that counterexample.

Bit errors and symbol errors are different units. Reed–Solomon over $\mathrm{GF}(256)$ treats each field element as an eight-bit symbol, so several bad bits inside the same symbol still count as one coordinate error. A burst crossing symbol boundaries can damage multiple symbols. Known erasure locations improve the recoverable count; they must actually be supplied reliably to the decoder, not merely guessed.

Finite fields are not integer wraparound. $\mathrm{GF}(7)$ in the miniature RS example is arithmetic modulo the prime $7$. $\mathrm{GF}(2^m)$ instead uses polynomial representations over $\mathrm{GF}(2)$ and reduction by an irreducible polynomial. Addition is XOR, but multiplication and inversion need the agreed field representation. RS and BCH encoders/decoders must also agree on evaluation points or root conventions, symbol order, generator polynomial, and shortening/padding rules.

Hamming and BCH connections. Binary Hamming codes can be viewed, up to coordinate ordering, as single-error-correcting BCH codes. BCH generalizes the consecutive-root approach to larger designed distances. The exact dimension depends on the minimal polynomials and repeated conjugate roots; simply allocating one independent parity field element per listed root can overcount redundancy.

Interleaving and burst errors. Interleave several codewords so a short physical burst is spread across different blocks. This helps only when the channel's burst pattern and the interleaver layout make the per-codeword bound hold. State the depth, ordering, buffering delay, and block boundaries. An interleaver changes the distribution of errors, not the minimum distance of each component code.

Shortening, puncturing, and wider words. Real systems use larger or shortened codes to trade rate, latency, implementation cost, and error coverage. Shortening fixes selected data coordinates and omits them; puncturing omits transmitted coordinates and can reduce distance. Recompute the effective parameters and decoder rules rather than applying this eight-position lookup blindly. Practical memory and storage codes can also be designed around the failure of an entire device or symbol, which is a different error model from one flipped bit.

Status handling and framing. Treat DETECTED_DOUBLE as unusable payload in this API; the wrapper returns no bytes when any block reaches it. Do not discard the status and use a sentinel nibble as data. A block count, ordering, synchronization, and any end-to-end integrity check belong in the surrounding format. Correction does not solve inserted/deleted bits or authenticate a maliciously replaced message.

Implementation traps. Keep one-based mathematical positions separate from zero-based integer shifts. Preserve the nibble bit order, use even parity consistently, include the parity bits when checking received groups, and compute total parity over all eight bits. Verify every one-bit position, including the parity bits themselves; only testing data-bit errors misses important branches.

Practice Problems and Real-World Use

Start by enumerating all sixteen nibble messages. Check that their encodings are distinct and satisfy every parity equation. Then test every received seven-bit and eight-bit word against an independently enumerated codebook: a unique valid codeword within distance one gives the correction result; extended words with no such neighbor are rejected by the SECDED policy.

For every transmitted nibble, apply every error mask and classify results by mask weight. This checks the guarantee and exposes behavior outside it. In particular, one flipped bit must return the original nibble, two flips must be detected in extended mode, and three-bit masks must not be assumed recoverable.

The implementations agree on $4643$ shared operation inputs and their complete block records: $4623$ accepted and $20$ rejected for invalid API input. Returned DETECTED_DOUBLE results are valid diagnostic outputs rather than API exceptions. The independent tests cover all $6144$ transmitted-nibble/error-mask combinations across the two modes. They confirm all guaranteed repairs and detections, and expose $896$ extended three-bit miscorrections and $224$ four-bit changes reported clean. The byte tests include every one-byte payload, randomized blocks, independent single-bit damage in words, and upper size limits. C++ and Java match Python's full results; C++ also ran with address and undefined-behavior sanitizers.

The mathematical overview examples were checked separately: all $343$ message polynomials of the $\mathrm{GF}(7)$ RS example produce a code of minimum distance three; every single-symbol change of the worked codeword and every two-erasure pattern has the expected unique recovery. Enumerating the $128$ codewords generated by the BCH polynomial confirms minimum distance five, its required roots were checked in $\mathrm{GF}(16)$, and all one- and two-bit corruptions of the worked BCH codeword have a unique codeword within distance two.

For applications, choose the code around the failure unit and recovery requirements: isolated bit faults, symbol bursts, known missing fragments, or larger correlated failures. Compare rate, block size, latency, decoding cost, and residual undetected/miscorrected-error behavior. The correction radius is a guarantee under a model, not a promise about every possible damaged input.