Reed–Solomon Codes Explained: Errors, Erasures, QR Codes and Voyager

An RS(n, k) code encodes k data symbols into a codeword of n symbols. With GF(256), one symbol is one byte. Several damaged bits within the same byte still count as one symbol error.

An error is an incorrect value whose location is unknown to the decoder. An erasure has an unknown value at a known location. For an RS code with minimum distance d=n−k+1, the usual guaranteed unique-decoding condition is 2e+s≤n−k, where e counts errors outside the s erased positions.

Having three correct symbols somewhere in the received word does not tell the decoder which three they are. It does not guarantee recovery from four unknown-location errors. For errors alone, the bound is ⌊(n−k)/2⌋: round down when the redundancy is odd. Beyond the guarantee, a decoder may fail or miscorrect to a different codeword.

To keep the arithmetic visible, start with GF(7), not GF(256). Its elements are 0 through 6, and arithmetic uses remainders modulo 7. Turn the data [1, 2, 3] into f(x)=1+2x+3x², then evaluate it at the seven distinct points x=0,1,…,6.

The transmitted word is [1, 6, 3, 6, 1, 2, 2]. This construction does not preserve the original coefficients as a prefix. Three known correct position–value pairs suffice to interpolate the polynomial of degree at most two.

Subtract two different polynomials of degree at most two. Their difference is nonzero and has at most two roots, so their seven-value evaluation words differ in at least five positions. This explains the minimum distance of five and unique correction of two errors. More generally, evaluating polynomials of degree less than k at n distinct points gives minimum distance n−k+1. A code meeting this Singleton bound is called maximum distance separable (MDS).

The evaluation construction needs n distinct field elements. The usual cyclic construction over the nonzero elements of GF(256) uses length 255 as its starting point. That does not impose a universal 255-symbol limit on evaluation constructions that also use zero, or on extended codes.

In GF(2⁸)=GF(256), the eight bits represent the coefficients of a polynomial of degree at most seven over GF(2). Byte 131 (0x83) represents x⁷+x+1. Addition and subtraction are XOR. Multiplication takes a polynomial product and reduces it modulo an irreducible polynomial of degree eight. This is not integer arithmetic modulo 256.

0x83 XOR 0x05 = 0x86
p(x) = x⁸ + x⁴ + x³ + x² + 1 = 0x11D
0x80 × 0x02 = 0x1D   (field multiplication using this p(x))
α = 0x02
α⁰ = 1, α¹ = 2, …, α⁷ = 128, α⁸ = 29, α²⁵⁵ = 1

With this representation using 0x11D, 0x02 is a primitive element: its powers cycle through all 255 nonzero elements. Every nonzero element has a multiplicative inverse. Arithmetic stays within the field, except that division by zero is undefined. Unlike the prime-field GF(7) example, GF(256) addition cannot be replaced by ordinary integer addition.

QR codes and CDs use this 0x11D representation, but it is not universal across RS standards. The field polynomial, primitive element, basis and symbol order must agree. The label RS(255, 223) alone does not specify interoperable encoders.

A systematic encoder preserves the data and appends parity. Consider a cyclic construction over GF(256) with primitive element α and r=n−k consecutive roots. The starting exponent b is another parameter selected by the specification.

g(x) = ∏ (x − α^(b+j))   for j = 0, …, r−1
R(x) = d(x) x^r mod g(x)
c(x) = d(x) x^r − R(x)

Shifting the data polynomial d(x) by r positions and subtracting the remainder makes c(x) divisible by g(x). In characteristic two, subtraction is XOR. Parity generation uses finite-field arithmetic, not ordinary division or floating-point polynomial calculations.

This cyclic representation and the earlier evaluation example are different constructions for understanding RS codes. Do not assume they produce the same bytes for the same input without defining coefficient conventions, coordinate mappings and scaling. Shortened codes can be constructed by inserting specified virtual zero data symbols during encoding and omitting those positions from transmission.

Let v(x) be the received polynomial. Evaluate it at the generator roots to obtain Sⱼ=v(α^(b+j)), for j=0,…,r−1. These are the syndromes. A nonzero syndrome means the received word violates the code constraints. But all-zero syndromes do not prove that the original data arrived unchanged: corruption can turn one valid codeword into another.

1. Compute syndromes and obtain any known erasure locations.
2. Find an error-locator polynomial using a method such as Berlekamp–Massey or the extended Euclidean algorithm.
3. Use a Chien search to find roots, then map them to positions.
4. Calculate error values, for example with Forney’s formula; correct the word and recheck counts, positions and syndromes.

For example, with coefficients ordered as c(x)=Σcᵢxⁱ, define the locator of position i as Xᵢ=αⁱ and Λ(z)=∏(1−Xᵢz). A root is then z=Xᵢ⁻¹=α⁻ⁱ. The root exponent is not automatically the array index. Arrays stored highest-degree coefficient first need another mapping.

Rechecking cannot eliminate every miscorrection. Additional error detection may be appropriate. Deliberate tampering requires authentication mechanisms such as a MAC or digital signature; RS coding does not provide authentication.

QR codes use RS coding over GF(256). In QR terminology, a codeword is eight bits (one byte), corresponding to one RS symbol in the earlier sections. This differs from an entire n-symbol RS codeword. DENSO WAVE gives these approximate restoration rates for total codewords:

These are not allowed percentages of damaged image area or safe logo sizes. Version and level determine the block layout and data/parity counts, so a fixed “redundancy percentage” for each level is also misleading. Apply the correction budget per RS block; parity from different blocks cannot be pooled freely.

Damage to finder patterns or format information, as well as poor capture conditions, can prevent reading. The current standard is ISO/IEC 18004:2024. The percentages here come from DENSO WAVE’s public explanation, not a reproduction of the standard’s full text. See our guide to QR error-correction levels for more detail.

CD’s cross-interleaved Reed–Solomon code (CIRC) uses C2=RS(28, 24) and C1=RS(32, 28). Encoding proceeds from C2 through interleaving to C1; decoding reverses the direction. Each constituent code can correct two unknown-location symbol errors on its own, while the complete system also uses rearrangement and erasure information. ECMA-130 Annex C describes this structure.

For DVD-ROM, ECMA-267 combines column RS(208, 192) and row RS(182, 172) codes. DVD’s arrangement is not CIRC. The 2004 BD-RE white paper describes Blu-ray’s Long Distance Code (LDC) for main data and Burst Indicator Subcode (BIS) for identifying likely burst locations.

Interleaving spreads consecutive damage across codewords. RS coding itself is also suited to bursts because several damaged bits can lie within one byte symbol; interleaving is not a prerequisite for correcting every burst. Real scratch tolerance depends on direction, shape, the reader, data arrangement and decoding strategy. Scratch length alone cannot guarantee perfect recovery.

NASA/JPL’s technical account says Voyager carried an experimental RS data encoder for the greater distances of the Uranus and Neptune encounters. Later operational and software changes should not be described as creating a previously nonexistent encoder entirely in software. Concatenating RS and convolutional coding was one part of improving distant communications, alongside separate work on compression and ground reception.

Chapter 4 of CCSDS 131.0-B-5 (2023) specifies eight-bit symbols and RS correction capabilities of t=8 or 16. For RS(255, 223), the 32 parity symbols provide the usual guarantee of correcting up to 16 unknown-location symbol errors. CCSDS also specifies the field representation and generator roots; the QR parameters discussed earlier are not interchangeable with them.

As checked on October 21, 2026, JAXA’s document list identifies 131.0-B-6, issued in April 2026. B-5 is the reference edition used for the formulas here, not the latest edition. Implementations must consult the applicable current standard and mission specification. These parameters should not be generalized into a claim that particular Mars missions always combine the same RS code with Turbo or LDPC coding.

ETSI EN 300 744 V1.6.2 specifies a shortened RS(204, 188) outer code for DVB-T: 16 parity bytes are added to 188 bytes, allowing correction of up to eight unknown-location byte errors. Interleaving and an inner convolutional code are also used. This describes DVB-T, not every generation of digital broadcasting.

MDS means the minimum distance is as large as possible for the given n and k. It does not mean the best possible performance relative to Shannon capacity once noise statistics and soft-decision information are considered. Turbo and LDPC codes are other options when long blocks, soft information and iterative decoding suit the channel.

Decoding cost also depends on the stage. Let r=n−k be the parity-symbol count, and count each finite-field operation at constant cost. Direct syndrome calculation costs O(nr), and the conventional Berlekamp–Massey locator calculation costs O(r²). For errors-only decoding with capacity t=⌊r/2⌋, a Chien search over n candidate positions costs O(nt). More generally, searching with a locator polynomial of degree ℓ costs O(nℓ); a combined error-and-erasure locator has ℓ=e+s. These operation counts describe separate stages, not measured running times on a particular implementation or device.

• Identify the symbol size and n and k. Distinguish unknown-location errors from known erasures.
• The usual unique-correction guarantee is 2e+s≤n−k. Beyond it, miscorrection is possible as well as failure.
• Match the field polynomial, basis, primitive element, starting root, array order and shortening convention.
• Do not treat zero syndromes as proof of unchanged data or protection against tampering.
• Do not turn QR restoration percentages or optical-disc correction capacity into image-area or scratch-length guarantees.

Work through the GF(7) table first, then move to the parameters of the actual standard. That separates the mathematics from a product’s recovery guarantees. The examples explain principles; they are not complete standards-compliant encoder or decoder implementations.