Reed-Solomon hibajavítás
A Reed-Solomon hibajavítás egy előremenő hibajavító kód. Az adatokból konstruált polinom túlmintavételezésével működik. A polinomot több ponton kiértékelik, és ezeket az értékeket elküldik vagy rögzítik. A polinomnak a szükségesnél gyakrabban történő mintavételezése a polinomot túldeterminálttá teszi. Amíg "sok" pontot helyesen fogad, a vevő "néhány" rossz pont jelenlétében is vissza tudja állítani az eredeti polinomot.
A Reed-Solomon kódokat számos különböző kereskedelmi alkalmazásban használják, például a CD-kben, DVD-kben és Blu-ray lemezekben, az adatátviteli technológiákban, például a DSL és a WiMAX, valamint az olyan műsorszóró rendszerekben, mint a DVB és az ATSC.
Áttekintés
A Reed-Solomon kódok blokk kódok. Ez azt jelenti, hogy egy rögzített bemeneti adatblokkot egy rögzített kimeneti adatblokkká dolgoznak fel. A leggyakrabban használt R-S kód (255, 223) esetében 223 Reed-Solomon bemeneti szimbólum (mindegyik nyolc bit hosszú) 255 kimeneti szimbólummá kódolódik.
- A legtöbb R-S ECC-séma szisztematikus. Ez azt jelenti, hogy a kimeneti kódszó egy része a bemeneti adatokat eredeti formájában tartalmazza.
- A Reed-Solomon szimbólumméretet nyolc bitben választottuk, mivel a nagyobb szimbólumméretű dekódereket a jelenlegi technológiával nehéz lenne megvalósítani. Ez a tervezési döntés arra kényszeríti a leghosszabb kódszó hosszát, hogy 255 szimbólum legyen.
- A szabványos (255, 223) Reed-Solomon kód minden egyes kódszóban legfeljebb 16 Reed-Solomon szimbólum hibáját képes korrigálni. Mivel minden szimbólum valójában nyolc bit, ez azt jelenti, hogy a kód a belső konvolúciós dekóder miatt legfeljebb 16 rövid hibaüzenetet képes korrigálni.
A Reed-Solomon kód, a konvolúciós kódhoz hasonlóan, átlátható kód. Ez azt jelenti, hogy ha a csatornaszimbólumok valahol a vonal mentén megfordultak, a dekóderek akkor is működnek. Az eredmény az eredeti adatok komplementere lesz. A Reed-Solomon kód azonban elveszíti átláthatóságát, ha virtuális nullfeltöltést használnak. Emiatt kötelező az adatok értelmét (azaz igaz vagy kiegészített) a Reed-Solomon dekódolás előtt feloldani.
A Voyager program esetében az R-S kódok közel optimális teljesítményt érnek el, amikor a (7, 1/2) konvolúciós (Viterbi) belső kóddal vannak összekapcsolva. Mivel minden egyes javítandó hibához két ellenőrző szimbólumra van szükség, ez kódszavanként összesen 32 ellenőrző szimbólumot és 223 információs szimbólumot eredményez.
Ezenkívül a Reed-Solomon kódszavakat szimbólumonként átlapolhatjuk, mielőtt konvolúciós kódolásra kerülnének. Mivel ez szétválasztja a szimbólumokat egy kódszóban, kevésbé valószínű, hogy a Viterbi dekóderből érkező kitörés egynél több Reed-Solomon szimbólumot zavar meg bármelyik kódszóban.
Alapgondolat
A Reed-Solomon kód lényege, hogy a kódolt adatokat először polinomként ábrázoljuk. A kód egy algebrai tételre támaszkodik, amely kimondja, hogy bármely k különböző pont egyértelműen meghatároz egy legfeljebb k-1 fokú polinomot.
A feladó meghatároz egy véges mező feletti k - 1 fokú {\displaystyle k-1}
polinomot, amely a k {\displaystyle k}
adatpontokat reprezentálja. A polinom ezután a különböző pontokon történő kiértékelésével "kódolva" van, és ezek az értékek azok, amelyeket ténylegesen elküldünk. Az átvitel során ezen értékek közül néhány megsérülhet. Ezért k-nál több pont kerül ténylegesen elküldésre. Amíg elegendő értéket kapunk helyesen, a vevő le tudja következtetni, hogy mi volt az eredeti polinom, és dekódolni tudja az eredeti adatokat.
Ugyanabban az értelemben, ahogyan egy görbét ki lehet javítani egy résen való interpolációval, a Reed-Solomon-kód képes áthidalni egy adattömbben lévő hibasorozatot, hogy visszanyerje az eredeti görbét rajzoló polinom együtthatóit.
Történelem
A kódot 1960-ban találta fel Irving S. Reed és Gustave Solomon, akik akkoriban az MIT Lincoln Laboratory munkatársai voltak. Alapvető cikkük címe "Polinomial Codes over Certain Finite Fields" volt. Amikor a cikket írták, a digitális technológia még nem volt elég fejlett a koncepció megvalósításához. Az RS-kódok első tömegtermékekben való alkalmazása 1982-ben a kompaktlemez volt, ahol két egymásba ágyazott RS-kódot használnak. Elwyn Berlekamp és James Massey 1969-ben hatékony dekódoló algoritmust dolgozott ki a nagy távolságú RS-kódokhoz. Ma az RS-kódokat merevlemez-meghajtókban, DVD-ken, távközlésben és digitális műsorszórási protokollokban használják.
