Reed-Solomon 부호: QR 오류 정정의 수학 원리

Reed-Solomon Codes: The Math Behind QR Error Correction

This guide explores the mathematical foundations of Reed-Solomon (RS) error correction as used in QR codes. RS codes are the engine that makes QR codes resilient to damage.

Galois Field GF(256)

All RS arithmetic in QR codes operates over GF(256) — a finite field with exactly 256 elements (0 to 255). This field is constructed using the primitive polynomial:

p(x) = x^8 + x^4 + x^3 + x^2 + 1 (binary: 100011101, decimal: 285)

Each field element can be represented as a polynomial of degree 7 or less with binary coefficients, or equivalently as a single byte.

Field Operations

Addition in GF(256) is XOR — no carrying, no overflow: - 83 + 202 = 83 XOR 202 = 153

Multiplication uses log/antilog tables derived from the primitive element alpha = 2: - a * b = antilog[(log[a] + log[b]) mod 255] - Special case: any element times 0 equals 0

Generator Polynomial

For n error correction codewords, the generator polynomial is:

g(x) = (x - alpha^0)(x - alpha^1)...(x - alpha^(n-1))

This polynomial has degree n, and its roots are consecutive powers of alpha. The encoder divides the data polynomial by g(x), and the remainder becomes the EC codewords.

Encoding Process

1. Represent data as a polynomial d(x) with coefficients being the data codewords
2. Multiply d(x) by x^n (shift left by n positions)
3. Divide x^n * d(x) by the generator polynomial g(x)
4. The remainder r(x) is the EC codewords
5. The transmitted codeword is x^n * d(x) - r(x) (which equals x^n * d(x) XOR r(x))

Syndrome Calculation

At decode time, calculate syndromes S_i by evaluating the received polynomial at each root of g(x):

S_i = r(alpha^i) for i = 0, 1, ..., n-1

If all syndromes are zero, no errors occurred. Non-zero syndromes indicate errors that need correction.

Error Location and Correction

The Berlekamp-Massey algorithm finds the error locator polynomial sigma(x) from the syndromes. Chien search evaluates sigma(x) at all field elements to find error positions. Forney's algorithm computes error magnitudes at those positions.

The correction capacity is: - t errors (unknown positions): requires 2t EC codewords - e erasures (known positions): requires e EC codewords - Mixed: 2t + e <= n (total EC codewords)

Key Takeaways

• GF(256) uses primitive polynomial x^8+x^4+x^3+x^2+1
• Addition is XOR; multiplication uses log/antilog tables
• Generator polynomial roots are consecutive powers of alpha
• Encoding divides data by the generator polynomial
• Decoding uses syndromes, Berlekamp-Massey, Chien search, and Forney's algorithm