Samoopravné Reed-Solomonovy kódy

Pro efektivní přenos dat komunikačním kanálem se používá kódování snižující nadbytečnost přenášených zpráv. Důsledkem je však vysoká citlivost přenosu zpráv na chyby. Potlačení tohoto jevu se docílí použitím protichybového kódování, které záměrně a kontrolovaně zvyšuje nadbytečnost přenášených zpráv.

---

Reed-Solomon codes

Abstract

To effectively transmit communication data in channel coding, which decreases redundancy of transmitted messages, is used. However, because of this transmitted messages have high sensitivity for errors. To reduce this effect anti-error coding can be used, which intentionally and with control increases redundancy of transmitted messages.

---

Úvod

Reed-Solomonovy kódy jsou blokové kódy spadající do třídy BCH kódů. Jsou určeny k detekci a opravě chyb v přenášených digitálních zprávách. Jejich rozsah použití spadá do mnoha kategorií, mezi něž například patří zálohovací média (CD, DVD…), bezdrátové a satelitní komunikace, digitální televize (standard DVB), vysokorychlostní modemy (ADSL, VDSL…) a další. Mezi největší výhody RS kódů patří možnost pracovat jak s bity, tak i se symboly. Typický příklad použití RS kódů je vyobrazen na obr. 1.

Obr. 1 Přenosový řetězec

Vlastnosti Reed-Solomonova kódu

Reed-Solomonovy kódy se označují zkratkou RS (n,k), která charakterizuje daný kód. Parametr k určuje počet m -bitových symbolů vstupujících do kodéru, parametr n udává velikost zprávy vystupující z kodéru. To znamená, že počet paritních symbolů v jednom bloku je n-k. Reed-Solomonův dekodér je schopen opravit maximálně t chybných symbolů. Platí, že 2 t = n-k. Reed-Solomonův kodér tedy na vysílací straně k blokům digitálních dat připojí redundantní bity, pomocí nichž dekodér na přijímací straně opraví vzniklé chyby a tím získá původní data. Počet opravitelných chyb v jednom bloku závisí na parametrech RS kódu. Obecná struktura přenášené zprávy je znázorněná obr. 2.

Obr. 2 Struktura přenášeného bloku

Reed-Solomonův kodér

Zabezpečení RS kódem je, jak už bylo zmíněno, obdobné jako u BCH kódu. Pro zabezpečení je tedy nutné sestavit vytvářecí mnohočlen g ( x ) sestávající se z 2 t členů. Po vytvoření mnohočlenu g ( x ) dochází na samotný proces kódování.

Sestavení vytvářecího mnohočlenu

Nejprve je potřeba sestavit Galoisovo těleso GF, se kterým se dále v průběhu kódování pracuje. Pro daný počet m bitů na jeden symbol je vytvořeno GF(2 ^m ), kde n = q ^m -1 určuje délku kódu. Vytvářecí mnohočlen má poté tvar

(1)

kde α je primitivní element GF.

Kódování

Při kódování k  symbolů se nejprve zpráva nesoucí informaci vyjádří jako vektor

(2)

kde každý koeficient f _k-i ( i = 0,1,…, k ) je m -bitový symbol Galoisova tělesa GF(2 ^m ). Pro kódování potom platí následující vztah [3]

(3)

kde q ( x ) značí výsledek po dělení a r ( x ) je zbytek po dělení.

Vyslanou zprávu můžeme potom vyjádřit polynomem

(4)

Přijatá zpráva vyjádřená jako

(5)

může být napadena chybami popsanými chybovým polynomem

(6)

Pro přijatou zprávu tedy platí vztah

(7)

Reed-Solomonův dekodér

Pro dekódování existuje více algoritmů. Celý proces lze rozdělit do pěti fází:

• Výpočet syndromů (určí zda nastala či nenastala chyba)
• Stanovení lokátoru chyb, jehož kořeny určují místa chyb v přenášené zprávě. Tato fáze může být řešena více způsoby, např. Euklidovým algoritmem, Berlekamp-Maseyovým algoritmem, atd.
• Nalezení kořenů chybového mnohočlenu
• Stanovení hodnoty chyby
• Oprava chyb

Postup dekódování znázorňuje obr. 3.

Obr.3 Postup dekódování

Výpočet syndromů

Prvním krokem při dekódování je nalezení syndromových rovnic. Platí, že zakódovaná zpráva f ( x ) je vždy beze zbytku dělitelná vytvářecím mnohočlenem g ( x ). Jednou z metod určení syndromů S _i je dosazení za proměnné x přijatého polynomu f’ ( x ) z rovnice (5) koeficienty Galoisova tělesa α _i, kde i = 1,2…,2 t. Tím se získají syndromové rovnice.

Pro kořeny mnohočlenu g ( x ) platí vztah

g ( α ) = g ( α 2 )= … = g ( α 2 t ) = 0.

(8)

Při bezchybném přenosu jsou všechny syndromové rovnice nulové. Pro bezchybně přijaté kódové slovo f' ( x ) = c ₀ + … + c _{n -1} x _{n -1} pak platí [3]

S 1 ( α ) = S 2 ( α 2 ) = … = S 2t ( α 2 t ) = 0.

(9)

Při přijetí kódového slova s chybou vznikne soustava syndromových rovnic, pomocí kterých je možno v následujících krocích stanovit počet a polohu chyb a poté tyto chyby i opravit.

Stanovení lokalizačního mnohočlenu

Došlo-li během přenosu k chybě, je nutné ve druhé fázi dekódování sestavit lokalizační mnohočlen tvaru [2]

(10)

kde ν je počet chyb vyskytujících se v právě dekódované zprávě. Jakmile se podaří určit tento polynom a jeho kořeny, je možné vypočítat chybové slovo e ( x ).

Polynom lze rozepsat jako

(11)

kde první koeficient Λ ₀ = 1 (protože Λ(0) = 1). Ostatní koeficienty Λ _i je nutné vypočítat některým z následujících způsobů.

Nalezení koeficientů chybového mnohočlenu

Přímá metoda

Pro nalezení koeficientů lokátoru chyb přímou metodou je zapotřebí sestavit soustavu rovnic (12). V této fázi je počet chyb neznámý.

(12)

Za proměnné ν   se nejprve dosadí maximálně možný počet chyb ν = t, který je daný kód schopen opravit a s danou hodnotou se vypočítá determinant matice syndromů v rovnici. Pokud determinant vyjde nenulový, celkový počet chyb v daném bloku je ν. Jinak se hodnota proměnné ν  redukuje o jednu a výpočet determinantu matice syndromů se opakuje. Tímto způsobem se pokračuje až do té doby, dokud determinant vyjde nenulový. Potom ν  je skutečný počet chyb. Po zjištění počtu chyb se ze soustavy vypočítají koeficienty lokátoru chyb Λ _i (0 < i ≤ t ) a ty se dosadí do rovnice (11). Jestliže vyjdou všechny determinanty nulové, můžeme konstatovat, že počet chyb přesáhl zabezpečovací schopnost daného kódu.

Euklidovský algoritmus

Jiný efektivní způsob získání koeficientů z lokátoru chyb je založen na Euklidovské metodě hledání nejvyššího společného dělitele dvou čísel. Ten využívá vzájemné vztahy mezi chybami a syndromy vyjádřenými ve formě rovnic. Tato metoda patří mezi základní a ke své funkci potřebuje dva nové polynomy: polynom syndromů (13) a polynom pro vyčíslení velikosti chyb(14). [2]

(13)

(14)

Postup nalezení a vyčíslení chyb
Klíčovou rovnici můžeme vyjádřit vztahem

(15)

kde S( x ) je polynom syndromů a Λ( x ) je lokátor chyb. Všechny výrazy stupně x ^{2 t} a vyšší jsou vypuštěny. Řešením je tedy soustava rovnic [2].

(16)

Pro nalezení koeficientů lokátoru chyb existuje řada dalších způsobů, např. Berlekampův algoritmus.

Řešení chybového polynomu – Chienovo vyhledávání

V této fázi jsou již známy koeficienty lokátoru chyb Λ ₁ … Λ _ν a je tedy možné nalézt jeho kořeny určující pozici chyb. Pokud chybový polynom vyjádříme vztahem

(17)

potom kořeny jsou hodnoty, při níž výsledek polynomu bude nulový, to znamená pokud x = X ₁ ^-1, X ₂ ^-1. Takovéto prohledávání, kdy jsou všechny možné kořeny dosazeny do rovnice, je známe jako Chienovo prohledávání. Nalezené kořeny poté určují pozici chyb v polynomu.

Výpočet velikosti chyb (Forneyův algoritmus)

Pro stanovení velikosti chyb Forneyovým algoritmem je zapotřebí znát lokátor chyb Λ( x ) a polynom vyčíslující chyby Ω( x ). Celý postup začíná derivací lokátoru chyb, při němž se zmiňovaný polynom redukuje na

(18)

Rovnice pro výpočet velikosti chyby

Pro výpočet velikosti chyby v daném místě přenášené zprávy se využívá následujícího vztahu [2]:

(19)

Oprava chyb

V poslední fázi jsou již známy pozice chyb a jejich hodnoty v přenášené zprávě. Pomocí těchto výsledků se sestrojí chybové slovo e ( x ), které se následně přičte k přijaté zprávě f’ ( x ) a tím se zpráva opraví.

Implementace RS kódů

Hardwarová implementace

RS kodek je možné implementovat v mnoha komerčně dostupných obvodech. Spousta z nich je přímo uzpůsobena pro RS kodér a dekodér (např. Philips TDA10023HT). V dnešní době se však spíše přistupuje k implementaci do univerzálních čipů FPGA nebo ASIC vzhledem k jejich univerzálnosti a možnosti implementace více procesů na jeden čip.

Softwarová realizace

Donedávna byla softwarová realizace v reálném čase vzhledem ke složitosti výpočtů nereálná. Velké obtíže u této implementace jsou hlavně z důvodu nepodporování Galoisova tělesa a k němu patřících aritmetických operací procesorem [1]. Nicméně dnes dostupné výkonné procesory již umožňují zpracování dat velmi vysokými rychlostmi.

Závěr

V tomto článku byl představen Reed-Solomonův kód, který patří do skupiny blokových kódů a dokáže detekovat a opravit vždy určité množství chyb v jednom bloku zprávy. Díky jeho dobrým vlastnostem je v dnešní době hojně používán v mnoha digitálních zařízeních, mezi něž patří zabezpečení dat v GSM, DVB, či dat na disku CD, DVD. Při výskytu shlukových chyb přesahujících schopnosti kódu se do přenosového řetězce zařazuje blok prokládání dat (interleaver), který zajistí rovnoměrné rozprostření chyb do většího úseku zprávy.

Tento článek vznikl za podpory výzkumného projektu MSM0021630513 "Elektronické komunikační systémy a technologie nových generací ELKOM"

Literatura

[1] Reed-SolomonCodes. [online] 07/2006, poslední revize dostupné z: http://www.4i2i.com/reed_solomon_codes.htm.

[2] CLARKE, C. Reed-Solomon error correction. British Broadcasting Corporation. 2002.

[3] ČÍKA, P., KodekBCH kódu. Diplomová práce. Ústav telekomunikací – FEKT VUT v Brně, 2005.

[4] MORELOS-ZARAGOZA, R. The Art of Error Correcting Coding. 2002. John Wiley & Sons Ltd., ISBN: 0-470-44782-4