Reedovy–Solomonovy kódy

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ě.

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.

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í.