Origine e usi più ampi
I codici Reed–Solomon furono descritti da Irving S. Reed e Gustave Solomon nel 1960. Lavorano su simboli interi, di solito byte, e non su singoli bit, il che li rende adatti a gestire danni a raffica come un graffio o una macchia.
La stessa famiglia di codici protegge i dati su CD, DVD e dischi Blu-ray, in alcuni collegamenti televisivi digitali e satellitari e in altri codici a barre 2D, tra cui Data Matrix ECC 200, Aztec Code e PDF417.
Come li usano i codici QR
Un codice QR tratta ogni codeword da 8 bit come un elemento del campo finito GF(256), costruito con il polinomio primitivo x^8 + x^4 + x^3 + x^2 + 1 (esadecimale 0x11D). I codeword di dati vengono divisi per un polinomio generatore e il resto diventa i codeword di correzione degli errori aggiunti in coda.
I codici più grandi dividono i dati in più blocchi, ciascuno con i propri codeword di correzione degli errori. I blocchi vengono poi interfogliati quando i codeword sono collocati nella griglia, così un singolo danno localizzato si distribuisce su molti blocchi invece di sopraffarne uno.
Quanto può correggere
Con n codeword di correzione degli errori in un blocco, un decodificatore può correggere fino a n/2 codeword la cui posizione è sconosciuta, o fino a n codeword la cui posizione è nota, dette cancellazioni. I casi misti seguono la regola per cui ogni errore conta due volte e ogni cancellazione una.
Per questo un codice con un'area pulita e uniforme coperta da un logo può ancora scansionarsi: un lettore intelligente può trattare la regione coperta come cancellazioni, mentre i danni casuali sono più difficili da correggere perché il decodificatore deve prima trovarli.
- Errori sconosciuti: fino alla metà del numero di codeword EC
- Cancellazioni (posizioni note): fino al numero di codeword EC
- Campo: GF(256), polinomio 0x11D
- I blocchi sono interfogliati per distribuire i danni a raffica