Reed‑Solomonova korekcia chýb

Reed-Solomonove kódy sú blokové kódy. To znamená, že pevný blok vstupných údajov sa spracuje na pevný blok výstupných údajov. V prípade najčastejšie používaného kódu R-S (255, 223) je 223 vstupných symbolov Reed-Solomona (každý dlhý osem bitov) zakódovaných do 255 výstupných symbolov.

• Väčšina schém R-S ECC je systematická. To znamená, že určitá časť výstupného kódového slova obsahuje vstupné údaje v pôvodnej podobe.
• Bola zvolená veľkosť Reed-Solomonovho symbolu osem bitov, pretože dekodéry pre väčšie veľkosti symbolov by bolo ťažké implementovať pomocou súčasnej technológie. Táto konštrukčná voľba núti najdlhšie kódové slovo k dĺžke 255 symbolov.
• Štandardný Reed-Solomonov kód (255, 223) je schopný opraviť až 16 Reed-Solomonových symbolových chýb v každom kódovom slove. Keďže každý symbol je v skutočnosti osem bitov, znamená to, že kód dokáže opraviť až 16 krátkych sérií chýb spôsobených vnútorným konvolučným dekodérom.

Reedov-Solomonov kód, podobne ako konvolučný kód, je transparentný kód. To znamená, že ak boli symboly kanála niekde na trase invertované, dekodéry budú stále fungovať. Výsledkom bude doplnok pôvodných údajov. Reed-Solomonov kód však stráca svoju transparentnosť, ak sa použije virtuálna nulová výplň. Z tohto dôvodu je povinné, aby sa pred Reed-Solomonovým dekódovaním vyriešil zmysel údajov (t. j. pravý alebo doplnený).

V prípade programu Voyager dosahujú kódy R-S takmer optimálny výkon, keď sú spojené s (7, 1/2) konvolučným (Viterbiho) vnútorným kódom. Keďže na každú chybu, ktorá sa má opraviť, sú potrebné dva kontrolné symboly, výsledkom je celkovo 32 kontrolných symbolov a 223 informačných symbolov na jedno kódové slovo.

Okrem toho sa Reed-Solomonove kódové slová môžu pred konvolučným kódovaním prekladať na základe symbolov. Keďže sa tým oddeľujú symboly v kódovom slove, znižuje sa pravdepodobnosť, že výbuch z Viterbiho dekodéra naruší viac ako jeden Reed-Solomonov symbol v ktoromkoľvek kódovom slove.

Hlavnou myšlienkou Reed-Solomonovho kódu je, že kódované údaje sa najprv zobrazia ako polynóm. Kód sa opiera o vetu z algebry, ktorá hovorí, že ľubovoľných k rôznych bodov jednoznačne určuje polynóm stupňa najviac k-1.

Odosielateľ určí polynóm stupňa k - 1 {\displaystyle k-1} nad konečným poľom, ktorý reprezentuje k {\displaystyle k} dátových bodov. Polynóm je potom "zakódovaný" jeho vyhodnotením v rôznych bodoch a tieto hodnoty sa skutočne posielajú. Počas prenosu sa niektoré z týchto hodnôt môžu poškodiť. Preto sa v skutočnosti posiela viac ako k bodov. Pokiaľ sa prijme dostatočný počet hodnôt správne, prijímač môže odvodiť, aký bol pôvodný polynóm, a dekódovať pôvodné údaje.

V rovnakom zmysle, v akom je možné opraviť krivku interpoláciou cez medzeru, môže Reed-Solomonov kód preklenúť sériu chýb v bloku údajov a obnoviť koeficienty polynómu, ktorý vykreslil pôvodnú krivku.

Kód vynašli v roku 1960 Irving S. Reed a Gustave Solomon, ktorí boli v tom čase členmi Lincolnovho laboratória MIT. Ich zásadný článok mal názov "Polynomiálne kódy nad určitými konečnými poľami". V čase jeho napísania nebola digitálna technológia dostatočne pokročilá na implementáciu tohto konceptu. Prvou aplikáciou RS kódov v hromadne vyrábaných produktoch bol v roku 1982 kompaktný disk, kde sa používajú dva preložené RS kódy. Účinný dekódovací algoritmus pre kódy RS na veľké vzdialenosti vyvinuli Elwyn Berlekamp a James Massey v roku 1969. Dnes sa RS kódy používajú v pevných diskoch, DVD, telekomunikáciách a protokoloch digitálneho vysielania.