Výsledky výzkumu a další informace nejen
z oblasti přístupových telekomunikačních sítí.
Access server ISSN 1214-9675
Server vznikl za podpory Grantové agentury ČR.
15. ročník
Dnešní datum: 24. 09. 2017  Hlavní stránka | Seznam rubrik | Ke stažení | Odkazy  

Doporučujeme
Knihu o FTTx

Matlab server - on-line výpočty a simulace

E-learning - on-line kurzy

Trainingpoint - školení z oblasti TELCO a ICT

Kontakt
KTT FEL ČVUT
Napište nám

Redakční rada - pokyny pro autory a recenzenty

Copyright

Digitální zpracování signálu

* Samoopravné Reed-Solomonovy kódy

Vydáno dne 11. 10. 2006 (9688 přečtení)

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

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

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


obr_3
(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


obr_4
(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]

obr_5
(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

obr_7
(4)

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

obr_8
(5)

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

obr_9
(6)

Pro přijatou zprávu tedy platí vztah

obr_10
(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_6

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 0 + … + 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]

obr_11
(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

obr_12
(11)

kde první koeficient Λ 0 = 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ý.

obr_13
(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 < it ) 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]

obr_14
(13)

obr_15
(14)

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

obr_16
(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].

obr_17
(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 Λ 1 … Λ ν a je tedy možné nalézt jeho kořeny určující pozici chyb. Pokud chybový polynom vyjádříme vztahem

obr_18
(17)

potom kořeny jsou hodnoty, při níž výsledek polynomu bude nulový, to znamená pokud x = X 1 -1, X 2 -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

obr_19
(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]:

obr_20
(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



Autor:        J. Koton, P. Číka, V. Křivánek
Pracoviště: Vysoké učení technické v Brně

Informační e-mail Vytisknout článek
Projekty a aktuality
01.03.2012: PROJEKT
Výzkum a vývoj nového komunikačního systému s vícekanálovým přístupem a mezivrstvovou spoluprací pro průmyslové aplikace TA02011015

01.01.2012: PROJEKT
Vývoj adaptabilních datových a procesních systémů pro vysokorychlostní, bezpečnou a spolehlivou komunikaci v extrémních podmínkách VG20122014095

09.10.2010: PROJEKT
Výzkum a vývoj datového modulu 10 Gbit/s pro optické a mikrovlnné bezdrátové spoje, FR-TI2/621

09.01.2010: PROJEKT
Sítě s femtobuňkami rozšířené o řízení interference a koordinaci informací pro bezproblémovou konektivitu, FP7-ICT-2009-4 248891

09.11.2008: PROJEKT
Ochrana člověka a techniky před vysokofrekvenčním zářením, FI-IM5/202

20.06.2008: Schválení
Radou pro výzkum a vývoj jako recenzovaný časopis

01.04.2007: PROJEKT
Pokročilá optimalizace návrhu komunikačních systémů pomocí neuronových sítí, GA102/07/1503

01.07.2006: Doplnění sekce pro registrované

12.04.2005: Zavedeno recenzování článků

30.03.2005: Výzkumný záměr
Výzkum perspektivních informačních a komunikačních technologií MSM6840770014

29.11.2004: Přiděleno ISSN

04.11.2004: Spuštění nové podoby Access serveru

18.10.2004: PROJEKT
Optimalizace přenosu dat rychlostí 10 Gbit/s, GA102/04/0773

04.09.2004: PROJEKT
Specifikace kvalitativních kritérií a optimalizace prostředků pro vysokorychlostní přístupové sítě, NPV 1ET300750402

04.06.2004: PROJEKT
Omezující faktory při širokopásmovém přenosu signálu po metalických párech a vzájemná koexistence s dalšími systémy, GA102/03/0434

Web site powered by phpRS PHP Scripting Language MySQL Apache Web Server

NAVRCHOLU.cz

Tento web site byl vytvořen prostřednictvím phpRS - redakčního systému napsaného v PHP jazyce.
Na této stránce použité názvy programových produktů, firem apod. mohou být ochrannými známkami
nebo registrovanými ochrannými známkami příslušných vlastníků.