Introduction
Error correction codes add redundancy to data so that errors introduced during transmission or storage can be detected and corrected. This tool implements two of the most important families: Hamming codes, which correct single-bit errors, and Reed-Solomon codes, which correct multiple symbol errors. Hamming codes are used in ECC memory and satellite communication. Reed-Solomon codes are used in QR codes, CDs, DVDs, and deep-space probes. All computation happens in your browser.
What this tool does
- Encodes data using Hamming(7,4), Hamming(15,11), or Hamming(31,26) codes.
- Decodes and corrects Hamming codewords, reporting the error position.
- Encodes data using Reed-Solomon codes with configurable parity symbols.
- Decodes and corrects Reed-Solomon codewords using Berlekamp-Massey + Forney.
- Reports the number of errors corrected for each decoded codeword.
- Processes all data locally in your browser with no server calls.
How this tool works
For Hamming: enter data bits (0s and 1s) and select a parity bit count. The tool computes parity bits at power-of-2 positions and inserts them into the codeword. For decoding, enter a codeword (possibly with an error) and the tool computes the syndrome to locate and correct any single-bit error. For Reed-Solomon: enter data bytes as hex, choose the number of parity symbols, and the tool computes parity using polynomial division in GF(2^8). For decoding, the tool computes syndromes, runs the Berlekamp-Massey algorithm to find the error locator polynomial, performs a Chien search to find error positions, and applies the Forney algorithm to compute error magnitudes. All computation happens client-side.
How error correction codes work
Hamming codes were invented by Richard Hamming at Bell Labs in 1950. The idea is to place parity bits at positions that are powers of 2 (1, 2, 4, 8, 16, ...) in the codeword. Each parity bit covers all positions whose binary representation includes that power of 2. When a codeword is received, the parity bits are recomputed and combined into a syndrome. A syndrome of 0 means no error. A non-zero syndrome gives the position of the single-bit error directly. Hamming(7,4) encodes 4 data bits into 7 bits, adding 3 parity bits. Hamming(15,11) encodes 11 data bits into 15 bits with 4 parity bits. Hamming(31,26) encodes 26 data bits into 31 bits with 5 parity bits. All Hamming codes can correct exactly one error per codeword. Reed-Solomon codes were invented by Irving Reed and Gustave Solomon in 1960. They operate on symbols (groups of bits) rather than individual bits. A Reed-Solomon code over GF(2^8) uses 8-bit symbols and can correct up to (n-k)/2 symbol errors, where n is the codeword length and k is the number of data symbols. The encoding appends parity symbols computed as the remainder of dividing the data polynomial by a generator polynomial. The generator polynomial is a product of (x - α^i) for i = 0 to n-k-1, where α is a primitive element of GF(2^8). Decoding uses the Berlekamp-Massey algorithm (1968) to find the error locator polynomial from the syndromes, a Chien search to find the roots (which give error positions), and the Forney algorithm to compute error magnitudes. Reed-Solomon codes are used in QR codes (ISO/IEC 18004), CDs (Cross-Interleaved Reed-Solomon Coding), and were used in the Voyager spacecraft's image transmission system.
How to use this tool
- Select a code type: Hamming or Reed-Solomon.
- For Hamming: enter data bits (e.g., 1011 for Hamming(7,4)) and select parity bits.
- For Reed-Solomon: enter data bytes as hex (e.g., 0a14) and set the parity symbol count.
- Select Encode mode. The encoded codeword appears in the output.
- To test error correction: modify one or more bits/symbols in the codeword, switch to Decode, and enter the corrupted codeword.
- The tool corrects the errors and reports how many were found.
Real-world examples
Hamming(7,4) single-bit correction
Data: `1011`. Encoded: `0110011`. Flip bit 3 (position 3) to get `0100011`. Decoding reports 'corrected error at position 3' and recovers the original data `1011`.
Reed-Solomon with 2 errors
Data: `205b0b78d172dc4d43`. With 10 parity symbols, the code can correct 5 errors. Corrupt 2 bytes and the decoder recovers the original data, reporting '2 errors corrected'.
Exceeding the correction capacity
With 10 parity symbols (5-error correction), corrupting 6 or more symbols causes the decoder to report 'too many errors to correct'. This is the fundamental limit of Reed-Solomon: you cannot correct more than (n-k)/2 errors.
Comparison with similar methods
| Method | Complexity | Typical use |
|---|---|---|
| Hamming(7,4) | O(n) syndrome computation | ECC RAM, simple protocols |
| Hamming(31,26) | O(n) syndrome computation | Higher-rate single-error correction |
| Reed-Solomon | O(n^2) Berlekamp-Massey | QR codes, CDs, deep-space communication |
| LDPC | O(n) iterative decoding | 5G, Wi-Fi 6, DVB-S2 |
Limitations or considerations
Hamming codes correct exactly one error per codeword. Two or more errors in a single Hamming codeword will cause incorrect correction or misdetection. Reed-Solomon codes correct up to (n-k)/2 symbol errors — exceeding this limit causes decoding failure. This tool implements Reed-Solomon over GF(2^8) with the standard primitive polynomial 0x11D. The maximum codeword length is 255 symbols. The Berlekamp-Massey implementation is the standard (non-optimized) version. For production use, consider libraries like reed-solomon-js or the implementations in zxing.
Frequently asked questions
What is the difference between error detection and error correction?
Error detection (e.g., CRC, parity) identifies that data has been corrupted but cannot fix it. Error correction (Hamming, Reed-Solomon) identifies and fixes the errors. Correction requires more redundancy than detection.
Why are Reed-Solomon codes used in QR codes?
QR codes (ISO/IEC 18004) use Reed-Solomon error correction so that damaged or partially obscured codes can still be scanned. The correction level (L, M, Q, H) determines how many symbols can be recovered — up to 30% at level H.
What is GF(2^8)?
GF(2^8) is the Galois field with 256 elements. It is used in Reed-Solomon codes because it maps naturally to 8-bit bytes. Addition is XOR, and multiplication uses polynomial arithmetic modulo a primitive polynomial (x^8 + x^4 + x^3 + x^2 + 1, or 0x11D).
Can Hamming codes detect double-bit errors?
Standard Hamming codes detect but cannot correct double-bit errors. An extended Hamming code adds an overall parity bit, enabling detection of double-bit errors and correction of single-bit errors (SECDED: Single Error Correction, Double Error Detection).
Conclusion
The error correction codes tool provides working implementations of Hamming and Reed-Solomon codes. It is useful for studying coding theory, testing error correction in communication systems, and understanding how QR codes and CDs recover from damage. The tool demonstrates the full Reed-Solomon decoding pipeline: syndrome computation, Berlekamp-Massey, Chien search, and Forney algorithm. For production use, consider optimized libraries.