Koreksi Kesalahan Reed-Solomon pada QR Codes

Reed-Solomon Error Correction in QR Codes

Error correction is what makes QR codes remarkably resilient. The mathematical engine behind this resilience is Reed-Solomon (RS) error correction, a block code based on finite field arithmetic.

What Reed-Solomon Does

RS codes add redundant codewords to your data. If some codewords are corrupted — by dirt, scratches, fading, or intentional logo placement — the decoder can locate the corrupted positions and reconstruct the original data. An RS code that adds 2t error correction codewords can correct up to t corrupted codewords.

Galois Field Arithmetic

RS codes in QR codes operate over GF(256) — the Galois field with 256 elements. Each element corresponds to one byte (0-255), and the field defines special addition (XOR) and multiplication (using a primitive polynomial) operations. The primitive polynomial for QR codes is:

x^8 + x^4 + x^3 + x^2 + 1 (decimal 285)

All codeword arithmetic — encoding, syndrome calculation, and error correction — uses GF(256) operations.

Generator Polynomials

The encoder creates a generator polynomial whose roots are consecutive powers of the primitive element. For n error correction codewords, the generator polynomial has degree n. The data polynomial is divided by the generator polynomial, and the remainder becomes the error correction codewords.

Codeword Interleaving

Large QR codes split data into multiple blocks, each with its own RS error correction. The codewords from different blocks are then interleaved in the final bit stream. This distributes the impact of localised damage across multiple blocks, improving recovery from large contiguous damage areas.

The Decode Side

When decoding, the scanner:

1. Calculates syndromes — if all syndromes are zero, no errors exist
2. Uses the Berlekamp-Massey algorithm to find the error locator polynomial
3. Applies Chien search to find error positions
4. Uses Forney's algorithm to calculate error magnitudes
5. Corrects the erroneous codewords

Practical Implications

The "correctable" percentage is approximately half the EC codeword percentage because each error requires two EC codewords to locate and fix. If the error positions are already known (erasures), one EC codeword per position suffices.

Key Takeaways

• Reed-Solomon codes add redundant codewords for error detection and correction
• Arithmetic operates in GF(256) using the primitive polynomial x^8+x^4+x^3+x^2+1
• Each correctable error consumes two EC codewords
• Interleaving across blocks distributes localised damage
• RS decoding uses syndromes, Berlekamp-Massey, Chien search, and Forney's algorithm