Reed–Solomon coding

Galois field

Reed–Solomon coding in the Quick Response Code is defined over the Galois field GF(2⁸) — 256 elements, each represented by an eight-bit codeword. The field is constructed using the primitive polynomial x⁸ + x⁴ + x³ + x² + 1 (decimal 285), the polynomial used throughout ISO/IEC 18004.

Encoding

Data codewords are treated as the high-order coefficients of a message polynomial. The encoder computes the remainder when this message polynomial is divided by a generator polynomial whose degree equals the required number of error-correction codewords. The remainder coefficients are appended to the data codewords, producing the codeword sequence written into the symbol.

Decoding

On decoding, the receiver evaluates the received polynomial against the generator's roots. Non-zero evaluations indicate the presence of errors. The Berlekamp–Massey algorithm (or an equivalent) is used to determine the error-locator polynomial; Chien search and Forney's formula together recover the error positions and magnitudes. The decoded codewords are then de-interleaved into data and de-masked into the original message.

Capability

A Reed–Solomon code with 2t parity codewords can correct up to t codeword errors. The four error-correction levels of the Quick Response Code (L, M, Q, H) correspond to progressively larger parity allocations and progressively greater error-correction capability, documented at Error correction.