Reed-Solomon Error Correction

Why error correction matters

Radio-frequency communication is noisy. When a reader interrogates an RFID tag, the response signal can be corrupted by metal interference, overlapping tag responses, distance, moisture, or electromagnetic noise. Without error correction, a single flipped bit would make the entire tag unreadable.

Error correction codes add redundant data to the original message so that the receiver can detect - and often fix - errors without asking for a retransmission. The same principle applies to 2D barcodes like GS1 DataMatrix and QR Codes , where part of the symbol can be physically damaged yet still scan correctly.

What is Reed-Solomon?

Reed-Solomon (RS) is a block error-correcting code invented by Irving S. Reed and Gustave Solomon in 1960. It works on symbols (groups of bits) rather than individual bits, which makes it especially effective at correcting burst errors - clusters of consecutive corrupted bits, exactly the type of error common in RF communication and damaged barcodes.

A Reed-Solomon code is described by its parameters:

For example, RS(255, 223) uses 255 symbols per block, of which 223 are data and 32 are parity. It can correct up to 16 symbol errors - meaning up to 16 out of 255 symbols can be completely wrong and the original data is still recoverable.

How it works (simplified)

Reed-Solomon operates over finite fields (Galois fields), which are mathematical structures where addition, subtraction, multiplication, and division all work within a fixed set of values. Here is the process at a high level:

1. Encoding: The data symbols are treated as coefficients of a polynomial. This polynomial is divided by a special generator polynomial, and the remainder becomes the parity symbols. The parity is appended to the data.
2. Transmission: The full block (data + parity) is transmitted over the RF link or printed as a barcode pattern.
3. Syndrome calculation: The receiver evaluates the received polynomial at specific points. If all syndromes are zero, there are no errors. Non-zero syndromes indicate errors.
4. Error location: The Berlekamp-Massey algorithm (or Euclidean algorithm) finds the error locator polynomial, whose roots identify which symbols are corrupted.
5. Error correction: The Forney algorithm calculates the error magnitudes - how much each corrupted symbol is off by. The receiver subtracts the errors to recover the original data.

The key insight is that Reed-Solomon can pinpoint both the position and the value of each error, without any prior knowledge of which symbols were corrupted.

Error correction in RFID

The EPC Gen2 air interface protocol (ISO 18000-63) uses several layers of error protection:

CRC-16

Every EPC memory bank includes a 16-bit CRC (Cyclic Redundancy Check) stored in the first 16 bits of the tag. When the reader receives the tag's response, it recalculates the CRC over the received data and compares. If the CRCs don't match, the reader knows there was an error and can re-query the tag. CRC is error detection only - it cannot correct errors, but it is fast and catches the vast majority of single and multi-bit errors.

Forward error correction on the air interface

During the reader-to-tag and tag-to-reader communication, the Gen2 protocol applies forward error correction at the physical layer. The specific coding depends on the link rate and modulation scheme:

The Gen2 protocol relies primarily on CRC detection plus retransmission rather than full Reed-Solomon correction on the air interface. This is a deliberate design choice: RFID tags have extremely limited power and silicon area, so the correction burden is placed on the reader (which has ample processing power) through re-queries.

Reed-Solomon in tag memory

Some advanced RFID tags (particularly high-memory tags used in aerospace, automotive, and pharmaceutical applications) include Reed-Solomon error correction on their internal memory. This protects against bit rot and memory degradation over the tag's lifetime - which can be 10+ years in harsh environments. The tag's internal controller encodes the memory contents using RS codes and automatically corrects errors during read-back.

Reed-Solomon in barcodes

While RFID uses CRC + retransmission as its primary strategy, 2D barcodes rely heavily on Reed-Solomon because there is no "retransmission" - the barcode is a printed symbol that must be decoded in a single scan, even if it is partially damaged.

This is why a QR code can still scan even with a logo placed over its centre - the Reed-Solomon code treats the obscured modules as errors and corrects them from the remaining data.

Detection vs correction

There is a fundamental trade-off between detecting and correcting errors. With 2t parity symbols, a Reed-Solomon code can either:

• Correct up to t errors (positions unknown - must be found and fixed)
• Detect up to 2t errors (positions unknown - only flagged, not fixed)
• Correct up to 2t erasures (positions known - e.g., a barcode scanner knows which modules are unreadable)

Most implementations use a hybrid approach: correct what you can, flag the rest. RFID readers take this further by simply retransmitting - if CRC detects an error, the tag is queried again. A barcode scanner does not have this luxury, so it must correct in a single pass.

Practical implications for RFID deployments

• Read reliability: Even in noisy RF environments, RFID systems achieve 99.9%+ read accuracy because CRC catches errors and the reader retries automatically. The user never sees the retransmissions.
• Tag longevity: Tags with internal RS protection can survive memory degradation for years in extreme temperatures, vibration, and UV exposure.
• Dense tag populations: When hundreds of tags respond simultaneously, collisions corrupt some responses. The Gen2 anti-collision protocol (slotted ALOHA) combined with CRC detection allows the reader to separate and re-query collided tags.
• Barcode fallback: In dual-technology deployments (RFID + barcode), the barcode's Reed-Solomon correction provides a backup read path. If the RFID tag is damaged, the barcode can still be scanned - and vice versa.

Source

I.S. Reed, G. Solomon, "Polynomial Codes over Certain Finite Fields", Journal of the Society for Industrial and Applied Mathematics, Vol. 8, No. 2, 1960. The EPC Gen2 air interface CRC and encoding are specified in GS1 EPC UHF Gen2 Air Interface Protocol (ISO 18000-63). QR Code error correction is defined in ISO/IEC 18004. DataMatrix error correction is defined in ISO/IEC 16022.