Reedovy–Solomonovy kódy
Reed-Solomonova korekce chyb je dopředný kód pro korekci chyb. Funguje na základě převzorkování polynomu zkonstruovaného z dat. Polynom se vyhodnotí v několika bodech a tyto hodnoty se odešlou nebo zaznamenají. Vzorkování polynomu častěji, než je nutné, způsobuje, že polynom je nadměrně určen. Pokud přijímá "mnoho" bodů správně, může přijímač obnovit původní polynom i v přítomnosti "několika" špatných bodů.
Reed-Solomonovy kódy se používají v mnoha různých komerčních aplikacích, například v CD, DVD a Blu-ray discích, v technologiích přenosu dat, jako je DSL a WiMAX, a ve vysílacích systémech, jako jsou DVB a ATSC.
Přehled
Reed-Solomonovy kódy jsou blokové kódy. To znamená, že pevný blok vstupních dat je zpracován na pevný blok výstupních dat. V případě nejčastěji používaného R-S kódu (255, 223) je 223 Reed-Solomonových vstupních symbolů (každý o délce osmi bitů) zakódováno do 255 výstupních symbolů.
- Většina schémat R-S ECC je systematická. To znamená, že určitá část výstupního kódového slova obsahuje vstupní data v původní podobě.
- Byla zvolena velikost Reed-Solomonova symbolu osm bitů, protože dekodéry pro větší velikosti symbolů by bylo obtížné realizovat pomocí současné technologie. Tato konstrukční volba nutí k tomu, aby nejdelší kódové slovo mělo délku 255 symbolů.
- Standardní Reed-Solomonův kód (255, 223) je schopen opravit až 16 chyb Reed-Solomonova symbolu v každém kódovém slově. Protože každý symbol je ve skutečnosti osm bitů, znamená to, že kód může opravit až 16 krátkých sérií chyb způsobených vnitřním konvolučním dekodérem.
Reed-Solomonův kód je stejně jako konvoluční kód transparentní kód. To znamená, že pokud byly symboly kanálu někde na trase invertovány, dekodéry budou stále fungovat. Výsledkem bude doplněk původních dat. Reed-Solomonův kód však ztrácí svou transparentnost, pokud se použije virtuální nulová výplň. Z tohoto důvodu je nutné, aby byl před Reed-Solomonovým dekódováním vyřešen smysl dat (tj. pravý nebo doplněný).
V případě programu Voyager dosahují R-S kódy téměř optimálního výkonu, pokud jsou spojeny s (7, 1/2) konvolučním (Viterbiho) vnitřním kódem. Protože pro každou opravovanou chybu jsou zapotřebí dva kontrolní symboly, vychází z toho celkem 32 kontrolních symbolů a 223 informačních symbolů na jedno kódové slovo.
Reed-Solomonova kódová slova lze navíc před konvolučním kódováním prokládat na základě symbolů. Protože se tím oddělí symboly v kódovém slově, sníží se pravděpodobnost, že výboj z Viterbiho dekodéru naruší více než jeden Reed-Solomonův symbol v jednom kódovém slově.
Základní myšlenka
Hlavní myšlenka Reed-Solomonova kódu spočívá v tom, že kódovaná data jsou nejprve zobrazena jako polynom. Kód se opírá o větu z algebry, která říká, že libovolných k různých bodů jednoznačně určuje polynom stupně nejvýše k-1.
Odesílatel určí polynom stupně k - 1 {\displaystyle k-1}
nad konečným polem, který reprezentuje k {\displaystyle k}
datových bodů. Polynom je pak "zakódován" svým vyhodnocením v různých bodech a tyto hodnoty jsou tím, co je skutečně odesláno. Během přenosu může dojít k poškození některých z těchto hodnot. Proto je ve skutečnosti odesláno více než k bodů. Pokud je přijat dostatečný počet správných hodnot, může příjemce odvodit, jaký byl původní polynom, a dekódovat původní data.
Ve stejném smyslu, v jakém lze opravit křivku interpolací přes mezeru, může Reed-Solomonův kód překlenout řadu chyb v bloku dat a obnovit koeficienty polynomu, který vykreslil původní křivku.
Historie
Kód vynalezli v roce 1960 Irving S. Reed a Gustave Solomon, kteří tehdy pracovali v Lincolnově laboratoři MIT. Jejich stěžejní článek se jmenoval "Polynomiální kódy nad určitými konečnými poli". V době jeho napsání nebyla digitální technologie dostatečně vyspělá, aby bylo možné tento koncept realizovat. První aplikací RS kódů v hromadně vyráběných produktech byl v roce 1982 kompaktní disk, kde se používají dva prokládané RS kódy. Účinný dekódovací algoritmus pro RS kódy s velkou vzdáleností vyvinuli Elwyn Berlekamp a James Massey v roce 1969. Dnes se RS kódy používají v pevných discích, DVD, telekomunikacích a protokolech digitálního vysílání.
