Reed-Solomonova korekcia chýb
Reed-Solomonova korekcia chýb je kód na korekciu chýb v priamom smere. Funguje na základe prevzorkovania polynómu vytvoreného z údajov. Polynóm sa vyhodnocuje v niekoľkých bodoch a tieto hodnoty sa odosielajú alebo zaznamenávajú. Vzorkovanie polynómu častejšie, ako je potrebné, spôsobuje, že polynóm je nadhodnotený. Pokiaľ prijímač prijme "veľa" bodov správne, môže obnoviť pôvodný polynóm aj v prítomnosti "niekoľkých" zlých bodov.
Reed-Solomonove kódy sa používajú v mnohých rôznych komerčných aplikáciách, napríklad v CD, DVD a Blu-ray diskoch, v technológiách prenosu dát, ako sú DSL a WiMAX, a vo vysielacích systémoch, ako sú DVB a ATSC.
Prehľad
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.
Základná myšlienka
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.
História
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.
