REED-SOLOMONOVA ZABEZPEČOVACÍHO KÓDU

´ ´ ´ ´I KONVOLUCN ˇ ´IHO A AKCELERATOR PRO DEKODOV AN ˇ ´ ´ REED-SOLOMONOVA ZABEZPECOVACIHO KODU J. Kloub, A. Heˇrm´ anek ´ ˇ v.v.i. Ustav teorie informace a automatizace AV CR, Oddˇelen´ı zpracov´an´ı sign´alu. Abstrakt

Pˇ ri n´ avrhu aplikac´ı pro bezdr´ atov´ y pˇ renos dat je nutn´ e simulovat pˇ renosov´ e kan´ aly vˇ cetnˇ e vznikaj´ıc´ıch poruch pˇ ri pˇ renosu. Pˇ ren´ aˇ sen´ a data jsou zat´ıˇ zena urˇ citou chybou a kvalita jednotliv´ ych opravn´ ych k´ od˚ u je d´ ana mnoˇ zstv´ım chyb, kter´ y je dan´ y k´ od schopen opravit. Vzhledem k sloˇ zitosti algoritm˚ u pro k´ odov´ an´ı a pˇ redevˇ s´ım dek´ odov´ an´ı a opravu vznikl´ ych chyb, m˚ uˇ ze b´ yt simulace na bˇ eˇ zn´ ych PC ˇ casovˇ e velmi n´ aroˇ cn´ a. ˇ Casovou n´ aroˇ cnost simulac´ı lze sn´ıˇ zit pouˇ zit´ım hardwarov´ ych akceler´ ator˚ u. Akceler´ atory vyuˇ z´ıvaj´ı specifick´ a obvodov´ aˇ reˇ sen´ı pro v´ ypoˇ cet d´ılˇ c´ıch probl´ em˚ u simulovan´ eho syst´ emu a urychl´ı tak celkovou dobu simulace. V tomto ˇ cl´ anku je pops´ ana implementace akceler´ ator˚ u pro dek´ odov´ an´ı a opravu dat zabezpeˇ cen´ ych konvoluˇ cn´ım a nebo Reed-Solomonov´ ym k´ odem. Akceler´ atory jsou implementov´ any pomoc´ı obvod˚ u FPGA (Field-programmable gate array) a pomoc´ı sign´ alov´ eho procesoru (DSP – pouze konvoluˇ cn´ı dekoder).

1

´ Uvod

Rozvoj digit´ aln´ıch technologi´ı pˇrinesl moˇznost realizovat komplexn´ı a v´ ykonn´a ˇreˇsen´ı elektronick´ ych syst´em˚ u. V´ ypoˇcetn´ıho v´ ykonu elektronick´ ych syst´em˚ u je dnes vyuˇz´ıv´ano v r˚ uzn´ ych odvˇetv´ıch pˇri zpracov´ av´ an´ı dat pomoc´ı r˚ uzn´ ych numerick´ ych metod. Numerick´e metody umoˇzn ˇuj´ı napˇr´ıklad zabezpeˇcit data proti chyb´am pˇri pˇrenosu komunikaˇcn´ım kan´ alem, kter´ y je zat´ıˇzen ˇsumem vedouc´ım k chyb´am v pˇrenosu. Zabezpeˇcen´ı dat proti chyb´am opravn´ ymi k´ ody (FEC - Forward Error Correction) dnes hojnˇe vyuˇz´ıvaj´ı napˇr´ıklad bezdr´atov´e technologie jako WiFi, BlueTooth, DVB-T, WiMax a dalˇs´ı. Mezi nejˇcastˇeji pouˇz´ıvan´e modern´ı k´odu patˇr´ı napˇr´ıklad blokov´ y konvoluˇcn´ı a Reed-Solomon˚ uv k´od. Pˇri n´avrhu aplikac´ı pro pˇrenos dat je nutn´e cel´ y syst´em simulovat. Pokud je simulace spouˇstˇena na standardn´ım PC, jsou simulaˇcn´ı kroky prov´adˇeny vˇetˇsinou sekvenˇcnˇe v z´avislosti na schopnostech dan´eho poˇc´ıtaˇce. Vzhledem ke sloˇzitosti nˇekter´ ych numerick´ ych metod m˚ uˇze b´ yt simulace pomˇernˇe ˇcasovˇe n´ aroˇcn´ a. Pro urychlen´ı v´ ypoˇctu simulace se n´am nab´ız´ı realizovat nˇekter´e v´ ypoˇcty pomoc´ı akceler´ator˚ u. V n´ asleduj´ıc´ım textu bude pops´ana realizace akceler´ator˚ u pro dek´odov´an´ı konvoluˇcn´ıho k´odu a pro k´ odov´ an´ı a dek´ odov´an´ı Reed-Solomonova k´odu. Struktura ˇcl´ anku je n´ asleduj´ıc´ı: kapitola 2 popisuje prostˇredky pro realizaci akceler´ator˚ u, kapitola 3 popisuje implementaci dekod´eru konvoluˇcn´ıho k´odu, kapitola 4 popisuje implementaci Reed-Solomonova kod´eru a dekod´eru a kapitola 5 uv´ad´ı v´ ysledky jednotliv´ ych implementac´ı akceler´ator˚ u.

2

Prostˇ redky pro HW implementaci akceler´ ator˚ u

Pro akcelerovan´ı v´ ypoˇct˚ u simulace lze pouˇz´ıt r˚ uzn´a obvodov´a ˇreˇsen´ı, jako napˇr´ıklad dedikovan´e z´akaznick´e obvody, mikroprocesory, sign´alov´e procesory, programovateln´e obvody a jin´a ˇreˇsen´ı. ˇ anek popisuje realizaci akceler´ator˚ Cl´ u pomoc´ı obvod˚ u s programovateln´ ymi hradlov´ ymi poli (FPGA - Field-Programmable Gate Array) a s pomoc´ı sign´alov´eho procesoru (DSP - Digital Signal Processor). Obvody FPGA dnes obecnˇe disponuj´ı ˇsirokou ˇsk´alou prostˇredk˚ u pro ˇreˇsen´ı r˚ uzn´ ych typ˚ u v´ ypoˇct˚ u vˇcetnˇe zpracov´ an´ı sign´ al˚ u. V´ ysledn´e aplikace vzniknou pomoc´ı propojen´ı jednotliv´ ych funkˇcn´ıch element˚ u obvodu. Jelikoˇz se jedn´a o obvodov´e ˇreˇsen´ı, m˚ uˇzeme vyuˇz´ıt moˇznosti soubˇeˇzn´eho v´ ypoˇctu datovˇe nez´ avisl´ ych operac´ı. Sign´alov´e procesory b´ yvaj´ı vystavˇeny na harvardsk´e architektuˇre, kde je pamˇet’ programu oddˇelena od pamˇeti dat. Tyto pamˇeti m´ıvaj´ı pˇr´ıstup realizov´an pomoc´ı vlastn´ıch sbˇernic, coˇz zvyˇsuje propustnost syst´emu. Dalˇs´ı zv´ yˇsen´ı v´ ypoˇcetn´ıho v´ ykonu je zajiˇstˇeno pomoc´ı specializovan´ ych jednotek, kter´e dok´ aˇz´ı pracovat paralelnˇe. Jednou z jednotek b´ yv´a i rychl´a n´asobiˇcka podporuj´ıc´ı vektorov´e operace (napˇr´ıklad operace typu A ← A + B ∗ k, kter´a prov´ad´ı jeden krok skal´arn´ıho n´ asoben´ı dvou vektor˚ u v jednom taktu procesoru - pˇr´ıstup k vektor˚ um je umoˇznˇen pomoc´ı nez´avisl´ ych adresn´ıch jednotek).

2.1

Realizace akceler´ atoru pomoc´ı obvodu FPGA

Pro realizaci akceler´ ator˚ u byly zvoleny v´ yvojov´e desky (viz [3], [4], [5]) osazen´e FPGA firmy Altera: Stratix II, Stratix a Cyclone. V´ yvojov´e desky disponuj´ı ethernetov´ ym rozhran´ım, kter´e je vyuˇzito k pˇred´ av´ an´ı dat mezi akceler´atorem a hostitelsk´ ym syst´emem. Ethernetov´e rozhran´ı je na v´ yvojov´ ych desk´ ach implementov´ano pomoc´ı obvodu SMSC LAN91C111 (viz [7]), kter´ y umoˇzn ˇuje komunikovat rychlost´ı 100 Mb/s (Full Duplex). Data jsou mezi akceler´ atorem a hostitelsk´ ym syst´emem pˇred´av´ana pomoc´ı protokolu UDP. Zp˚ usob pˇripojen´ı akceler´ atoru je zn´ azornˇen na obr´azku 1.

2.2

Realizace akceler´ atoru pomoc´ı DSP

V pˇr´ıpadˇe dek´ odov´ an´ı konvoluˇcn´ıho k´ odu je pro akceleraci vyuˇzit sign´alov´ y procesor firmy Texas Instruments TMS320C6416, kter´ y disponuje koprocesorem pro Viterbiho algoritmus. Pro implementaci akceler´ atoru byla zvolena v´ yvojov´a deska osazen´a zm´ınˇen´ ym procesorem (viz [6]). Firma Texas Instrument vyvinula vlastn´ı propriet´arn´ı protokol RTDX (RTDX - Real Time Data Exchange) pro rychlou v´ ymˇenu dat s v´ yvojovou deskou pˇres rozhran´ı JTAG. Protokol RTDX je podpoˇren v prostˇred´ı Matlab (toolbox ”Target for TI6000”). Na zvolen´e v´ yvojov´e desce je rozhran´ı JTAG realizov´ ano pomoc´ı rozhran´ı USB. Data mezi DSP a koprocesorem jsou pˇred´av´ana pomoc´ı DMA pˇrenos˚ u.

3

Implementace dekod´ eru konvoluˇ cn´ıho k´ odu

Konvoluˇcn´ı k´ odov´ an´ı dat lze velmi snadno realizovat obvodov´ ym ˇreˇsen´ım. Z´akladem kod´eru je posuvn´ y registr, kter´ y uchov´ av´ a ˇc´ ast z historie pˇr´ıchoz´ıch dat. Z t´eto historie a z pˇr´ıchoz´ıch dat je odvozen v´ ystup dekod´eru podle generuj´ıc´ıch polynom˚ u. Na obr´azku 2 je zn´azornˇeno zapojen´ı pro konkr´etn´ı parametry k´ odu, kde registry obsahuj´ı historii dat (stav kod´eru). V´ ystupy jsou odvozeny pomoc´ı souˇctu modulo-2 z hodnot urˇcen´ ych polynomy. Potˇrebn´a datov´a redundance pro zabezpeˇcen´ı pˇrenosu dat je odvozena z poˇctu v´ ystup˚ u kod´eru, tedy poˇctem generuj´ıc´ıch polynom˚ u.

Obr´ azek 1: Zp˚ usob propojen´ı akceler´atoru a PC Konvoluˇcn´ı kod´er je charakterizov´an nˇekolika z´akladn´ımi parametry: • R = k´ odov´ y pomˇer R = k/n , kde k je poˇcet k´odov´ ych bit˚ u generuj´ıc´ı n v´ ystupn´ıch bit˚ u • K = poˇcet moˇzn´ ych vazeb z posuvn´eho registru do exkluzivn´ıch souˇct˚ u • G0(x) ... GN-1(x) = polynomy generuj´ıc´ı v´ ystup

Obr´azek 2: Pˇr´ıklad obvodov´e realizace konvoluˇcn´ıho kod´eru (K=4, R=1/2, G0=(1111), G1=(1101)

3.1

Dek´ odov´ an´ı konvoluˇ cn´ıho k´ odu a Viterbiho algoritmus

Pokud uvaˇzujeme, ˇze pˇri pˇrenosu doˇslo k chybˇe a nebo je pouˇzito takzvan´e dˇerov´an´ı konvoluˇcn´ıho k´odu, mus´ıme odhadovat nejpravdˇepodobnˇejˇs´ı zak´odovanou bitovou posloupnost - hled´ame tzv. ”Most Likelihood” ˇreˇsen´ı. Jedn´ım z algoritm˚ u pro urˇcen´ı nejpravdˇepodobnˇejˇs´ı bitov´e posloupnosti je Vitebiho algoritmus. 3.1.1

Viterbiho algoritmus

Viterbiho algoritmus se op´ır´ a o teorii graf˚ u hled´an´ı nejl´epe ohodnocen´e cesty. Graf je tvoˇren vˇsemi moˇzn´ ymi pˇrechody mezi jednotliv´ ymi stavy historie konvoluˇcn´ıho kod´eru, tvoˇr´ıc´ı mˇr´ıˇzku (oznaˇcov´ano tak´e jako trellis). Vzhledem k tomu, ˇze podstatou obvodov´e realizace konvoluˇcn´ıho

kod´eru je posuvn´ y registr, lze velmi snadno urˇcit strukturu pˇrechod˚ u v grafu. Na obr´azku 3 je zn´azornˇeno jak´ ym zp˚ usobem pˇrechody v grafu vznikaj´ı (stavy jsou pro n´azornost oznaˇceny bin´arn´ımi hodnotami).

Obr´ azek 3: Expanze hran grafu mˇr´ıˇzky v ˇcase (pro K=4) Graf zaˇc´ın´ a expandovat od poˇc´ ateˇcn´ıho stavu (stav 000). V kaˇzd´em dalˇs´ım kroku expanduj´ı pr´avˇe dvˇe hrany z dosaˇzen´ ych stav˚ u. Jedna hrana vede do stavu 1XX a druh´a do stavu 0XX, kde XX jsou posunut´e bity hodnoty stavu, z kter´eho hrany vych´az´ı (vˇsimnˇeme si, ˇze nejvyˇsˇs´ı bit n´asleduj´ıc´ıho stavu odpov´ıd´ a zak´ odovan´emu bitu). Takto se tvoˇr´ı kombinace cest, konˇc´ıc´ı vˇzdy v jednom ze stav˚ u mˇr´ıˇzky. Pro v´ ybˇer cesty, kter´ a odpov´ıd´ a pˇrijat´ ym dat˚ um, mus´ıme zav´est pro jednotliv´e hrany metriky. Ohodnot’me jednotliv´e hrany hodnotou, kter´a odpov´ıd´a hodnotˇe v´ ystupu konvoluˇcn´ıho kod´eru ve stejn´em stavu jako je stav mˇr´ıˇzky. Pro jeden stav kod´eru existuj´ı dvˇe moˇzn´e hodnoty v´ ystupu v z´ avislosti na vstupu kod´eru. Pro hranu vedouc´ı do stavu s nejvyˇsˇs´ım bitem rovn´ ym nule odpov´ıd´ a ohodnocen´ı pro vstup roven nule a obdobnˇe i pro vstup rovn´ y jedn´e. V kaˇzd´em kroku vytv´ aˇren´ı grafu porovn´ame ohodnocen´ı hrany se vstupn´ım symbolem. Metrika pro kaˇzdou hranu je vypoˇc´ıt´ ana jako k´odov´a vzd´alenost mezi ohodnocen´ım hrany a vstupn´ım symbolem v dan´em ˇcase (napˇr. Hammingova vzd´alenost). Kaˇzd´a vytvoˇren´a cesta je ohodnocena souˇctem jednotliv´ ych hranov´ ych metrik. Do jednoho stavu mˇr´ıˇzky vedou maxim´alnˇe dvˇe cesty. Cesta s horˇs´ım ohodnocen´ım m˚ uˇze b´ yt ”zapomenuta”. Jsou-li ohodnocen´e cesty totoˇzn´e, vybere se deterministicky jedna z nich (napˇr. vˇzdy ta cesta, kter´a do stavu vede ze stavu s niˇzˇs´ı hodnotou). V kaˇzd´em stavu je uchov´ ana hodnota ohodnocen´ı v´ıtˇezn´e cesty do stavu vedouc´ı (oznaˇcov´ana jako akumulovan´ a metrika). Vlastn´ı dek´ odov´ an´ı dat spoˇc´ıv´ a ve zpˇetn´em pr˚ uchodu grafem po nejl´epe ohodnocen´e cestˇe. Teoreticky se graf m˚ uˇze tvoˇrit v ˇcase do nekoneˇcna. V praxi je graf omezen na ˇcasov´e ok´enko dan´e d´elky. Pˇri zpˇetn´em pr˚ uchodu grafem urˇcuje aktu´aln´ı stav pˇr´ımo v´ ystupn´ı hodnotu. Jak bylo pops´ano v´ yˇse, v´ ystupu odpov´ıd´ a nejvyˇsˇs´ı bit dosaˇzen´eho stavu. Poˇrad´ı bit˚ u v´ ystupu je dek´odov´ano v opaˇcn´em poˇrad´ı, neˇz byla data dek´odov´ana a poˇrad´ı mus´ı b´ yt prohozeno.

Viterbiho algoritmus je pomˇernˇe ˇcasovˇe n´aroˇcn´ y, pokud je implementov´an pomoc´ı softwarov´ ych prostˇredk˚ u. Hardwarov´ a implementace dekod´eru vyuˇz´ıv´a soubˇeˇzn´eho vyhodnocov´an´ı v mˇr´ıˇzkov´em grafu, a tak m˚ uˇze b´ yt dek´odov´an´ı rapidnˇe urychleno.

3.2

Hardwarov´ a implementace Viterbiho dekod´ eru

Jak bylo uvedeno v´ yˇse, byl Viterbi dekod´er implementov´an pomoc´ı obvodu FPGA a pomoc´ı DSP firmy Texas Instruments. Nejdˇr´ıve uved’me z´ akladn´ı blokov´e sch´ema dekod´eru implementovan´eho v obvodu FPGA. Viterbi dekod´er se d´ a rozdˇelit do nˇekolika z´akladn´ıch blok˚ u: • Jednotka pro v´ ypoˇcet metrik jednotliv´ ych hran grafu mˇr´ıˇzky (BMU - Branch Metric Unit). • Jednotka pro pˇriˇcten´ı metrik hran k aktu´aln´ım cest´am a v´ ybˇer nejl´epe ohodnocen´ ych cest konˇc´ıc´ıch v aktu´ aln´ıch uzlech grafu (ACSU - Add-Compare-Select Unit) • Jednotka pro v´ ybˇer uzlu (stavu) do kter´eho vede nejl´epe ohodnocen´a cesta (BSU - Best State Unit) • Jednotka pro zpˇetn´ y pr˚ uchod grafem pro urˇcen´ı odhadovan´e dek´odovan´e posloupnosti (SMU - Survior Management Unit) Na obr´ azku 4 je zn´ azornˇeno blokov´e sch´ema dekod´eru. Jednotka BMU vypoˇc´ıt´ a metriky pro vˇsechny nov´e hrany grafu na z´akladˇe vstupn´ıho symbolu (Hammingova vzd´ alenost). Hranov´e metriky jsou pˇred´any jednotce ACSU, kter´a pˇriˇcte hodnoty k cest´ am vedouc´ıch do aktu´ aln´ıch koncov´ ych uzl˚ u grafu a vybere cesty s lepˇs´ım ohodnocen´ım pro kaˇzd´ y koncov´ y uzel grafu. Ohodnocen´ı vybran´ ych cest (akumulovan´e metriky) si jednotka ACSU zapamatuje. V´ ystupem jednotky ACSU je informace o rozhodnut´ı v´ ybˇeru cest a akumulovan´e metriky. Informace o rozhodov´an´ı (oznaˇcen´e jako ”path metric”) v pr˚ ubˇehu dek´odov´an´ı jsou uchov´ av´ any v jednotce SMU. Jednotka SMU m´ a omezenou pamˇet’ (poˇctem krok˚ u rozhodov´an´ı - oznaˇcme toto omezen´ı ”d´elkou” pamˇeti). D´elka pamˇeti odpov´ıd´a d´elce zpˇetn´eho pr˚ uchodu (”traceback length”). D´elku pamˇeti lze nastavit pomoc´ı parametru pˇred synt´ezou zdrojov´ ych k´odu implementace. Po naplnˇen´ı pamˇeti je jednotkou SMU proveden zpˇetn´ y pr˚ uchod od uzlu (stavu) grafu, kter´ y urˇc´ı jednotka BSU na z´ akladˇe akumulovan´ ych metrik (z´ıskan´e od ACSU). V´ ystupem jednotky SMU je dek´odovan´ a bitov´ a posloupnost. V implementovan´em dekod´eru obsahuje jednotka SMU pamˇeti dvˇe. Bˇehem zpˇetn´eho pr˚ uchodu jsou data ˇctena a vyhodnocov´any z jedn´e pamˇeti a do druh´e pamˇeti jsou souˇcasnˇe zapisov´any nov´e informace od jednotky ACSU. Po dokonˇcen´ı zpˇetn´eho pr˚ uchodu je u ´ˇcel pamˇet´ı zamˇenˇen, a je tak doc´ıleno pr˚ ubˇeˇzn´eho dek´odov´an´ı pˇr´ıchoz´ıch dat. Dekod´er pouˇz´ıv´ a takzvan´e ”hard” dek´odov´an´ı a jedn´a se o takzvan´e hybridn´ı ˇreˇsen´ı. Hybridn´ı ˇreˇsen´ı je kompromisem mezi plnˇe paraleln´ım vyhodnocov´an´ım vˇsech uzl˚ u v jednotce ACSU paralelnˇe a sekvenˇcn´ım vyhodnocen´ım - vyhodnocov´any jsou skupiny uzl˚ u. Toto ˇreˇsen´ı vede ke sn´ıˇzen´ı hardwarov´ ych n´ arok˚ u (zdroje obvodu, pracovn´ı frekvence). ´ ˇ Popisovan´ a implementace Viterbiho dekod´eru v obvodu FPGA vznikla v UTIA AV CR (odd. Zpracov´ an´ı sign´ alu).

Obr´ azek 4: Blokov´e sch´ema Viterbi dekod´eru 3.2.1

Hardwarov´ a implementace Viterbiho dekod´ eru pomoc´ı DSP

Sign´alov´ y procesor TMS320C6416 (DSP) je vybaven koprocesorem pro Viterbiho dek´odov´an´ı (VCP), kter´ y byl navrˇzen pro bezdr´ atov´e standardy IS2000 a 3GPP jehoˇz parametry jsou n´asleduj´ıc´ı: • Podpora dek´ odov´ an´ı pro K = 5, 6, 7 ,8 nebo 9. • Uˇzivatelsky zad´ avan´e koeficienty polynom˚ u. • K´odov´ y pomˇery 1/2, 1/3 nebo 1/4. • Moˇznosti nastaven´ı d´elky a zp˚ usobu zpˇetn´eho pr˚ uchodu pˇri dek´odov´an´ı. Koprocesor prov´ ad´ı pouze vyhodnocov´an´ı moˇzn´ ych cest pr˚ uchodu grafem a jeho zpˇetn´ y pr˚ uchod. Hranov´e metriky mus´ı b´ yt vypoˇcteny na stranˇe DSP a jsou pˇred´av´any pomoc´ı dedikovan´ ych DMA pˇrenos˚ u (EDMA - Enhanced Direct Memory Access). Pro spr´avnou funkci ˇ c EDMA zah´ dek´odov´an´ı je tˇreba nastavit jednotliv´e pˇrenosov´e kan´aly v ˇradiˇci EDMA. Radiˇ aj´ı pˇrenos na z´ akladˇe sign´ al˚ u od periferi´ı a koprocesor˚ u. Koprocesor generuje pˇr´ısluˇsn´e sign´aly v pˇr´ıpadˇe pr´azdn´e vstupn´ı pamˇeti (bufferu) pro hranov´e metriky a v pˇr´ıpadˇe, ˇze je v´ ystupn´ı pamˇet’ (buffer) vyplnˇena dek´ odovan´ ymi daty. J´adro procesoru DSP pracuje nez´avisle na koprocesoru a jeho pracovn´ı frekvence je 1 GHz. Vlastn´ı koprocesor pracuje na ˇctvrtinov´e frekvenci j´adra, tedy na frekcvenci 250 MHz. Na obr´ azku 5 je zn´ azornˇena architektura koprocesoru. Bliˇzˇs´ı informace o koprocesoru lze nal´ezt v [2].

4

Implementace kod´ eru a dekod´ eru Reed-Solomonova k´ odu

Pro Reed-Solomon˚ uv k´ od byl implementov´an kod´er i dekod´er v obvodu FPGA. Reed-Solomonovy k´ody pouˇz´ıvaj´ı operace nad Galoisov´ ymi tˇelesy (GF). Operace nad GF lze v obvodu FPGA implementovat efektivnˇeji neˇz pomoc´ı standardn´ıch v´ ypoˇcetn´ıch jednotek. Pˇrev´aˇznˇe n´asoben´ı GF

Obr´azek 5: Blokov´e sch´ema koprocesoru pro Viterbiho algoritmus (pˇrevzato z [2]) je implementov´ ano pouze pomoc´ı hradel XOR a AND, nam´ısto obecn´e n´asobiˇcky. Operace nad GF na stranˇe PC jsou velmi neefektivn´ı.

4.1

Kod´ er Reed-Solomonova k´ odu

Kod´er pro systematick´ y RS k´ od m˚ uˇze b´ yt realizov´an pomoc´ı line´arn´ıho zpˇetnovazebn´ıho registru LFSR (obr. 6), kter´ y prov´ ad´ı dˇelen´ı generuj´ıc´ım mnohoˇclenem podle vztahu (1). xn−k m(x) = q(x)g(x) + p(x)

(1)

Na vstup registru pˇrich´ az´ı datov´e symboly urˇcen´e k zak´odov´an´ı n´asledovan´e poˇctem 2t nulov´ ych symbol˚ u (coˇz odpov´ıd´ a v´ yrazu x2t m(x)). Na vstup pˇrich´az´ı koeficienty v poˇrad´ı mk , . . . , m1 , m0 . Vˇsechny datov´e cesty na obr´azku jsou osmibitov´e. Pˇred zah´ajen´ım dˇelen´ı je potˇreba vynulovat vˇsechny registry. Po naˇcten´ı vˇsech n symbol˚ u (tj. po n hodinov´ ych cyklech) budou registry obsahovat hodnoty odpov´ıdaj´ıc´ı zbytku po dˇelen´ı generuj´ıc´ım mnohoˇclenem. K operaci zak´ odov´ an´ı jsou potˇreba dvˇe operace nad koneˇcn´ ym tˇelesem, a to sˇc´ıt´an´ı a n´asoben´ı. Seˇcten´ı dvou ˇc´ısel v GF(256) je provedeno pomoc´ı bitov´e operace xor. N´asoben´ı ˇ ısla z GF(256) lze vyj´adˇrit pomoc´ı mnohoˇclenu sedm´eho dvou ˇc´ısel je provedeno n´ asledovnˇe. C´ stupnˇe s koeficienty z GF(2): A(x) = a7 x7 + a6 x6 + a5 x5 + a4 x4 + a3 x3 + a2 x2 + a1 x + a0 ; ai ∈ GF(2), A ∈ GF(256) Operace C = A · B; A, B, C ∈ GF (256), lze vyj´adˇrit v polynomi´aln´ı reprezentaci jako C(x) = A(x) · B(x) = A(x) × B(x)modf (x) = D(x)modf (x),

g0

g1

data, 0,..., 0

D

g2

D

g2t−1

D

Obr´ azek 6: RS kod´er pouˇz´ıvaj´ıc´ı dˇelˇen´ı generuj´ıc´ım polynomem.

D

kde polynomi A(x), B(x), C(x), D(x) jsou definov´any jako:

A(x) = a7 x7 + a6 x6 + · · · + a0 , 7

6

7

6

B(x) = b7 x + b6 x + · · · + b0 ,

(2) (3)

C(x) = c7 x + c6 x + · · · + c0 ,

(4)

14

(5)

D(x) = d14 x

+ d13 x

13

+ · · · + d0

kde , ai , bi , ci , dj ∈ GF (2), mod je operace v´ ypoˇcet zbytku po dˇelen´ı polynomem a × je operace n´asoben´ı polynom˚ u. Uveden´e vztahy pro n´asoben´ı dvou ˇc´ısel plat´ı pro tˇeleso GF(256) s primitivn´ım polynomem f (x) = x8 + x4 + x3 + x2 + 1. d14 d13 d12 d11 d10 d9 d8 d7 d6 d5 d4 d3 d2 d1 d0

= = = = = = = = = = = = = = =

a7 b7 a6 b7 + a7 b6 a6 b6 + a7 b5 + a5 b7 a6 b5 + a5 b6 + a7 b4 + a4 b7 a7 b3 + a6 b4 + a3 b7 + a4 b6 + a5 b5 a3 b6 + a6 b3 + a2 b7 + a7 b2 + a4 b5 + a5 b4 a3 b5 + a7 b1 + a1 b7 + a2 b6 + a5 b3 + a6 b2 + a4 b4 a4 b3 + a1 b6 + a0 b7 + a7 b0 + a2 b5 + a5 b2 + a3 b4 + a6 b1 a6 b0 + a4 b2 + a2 b4 + a1 b5 + a0 b6 + a3 b3 + a5 b1 a4 b1 + a1 b4 + a5 b0 + a3 b2 + a2 b3 + a0 b5 a1 b3 + a2 b2 + a0 b4 + a4 b0 + a3 b1 a1 b2 + a2 b1 + a3 b0 + a0 b3 a0 b2 + a1 b1 + a2 b0 a0 b1 + a1 b0 a0 b0

(6)

V druh´em kroku se provede urˇcen´ı zbytku po dˇelen´ı primitivn´ım mnohoˇclenem, pomoc´ı kter´eho z´ısk´ ame mnohoˇclen sedm´eho stupnˇe. Pomoc´ı operace ”nalezen´ı zbytku po dˇelen´ı” se provede zobrazen´ı patn´ acti bin´ arn´ıch koeficient˚ u d14 , . . . , d0 na osm (c7 , . . . , c0 ). c7 c6 c5 c4 c3 c2 c1 c0

= = = = = = = =

d7 + d11 + d12 + d13 d6 + d10 + d11 + d12 d5 + d9 + d10 + d11 d4 + d8 + d9 + d10 + d14 d3 + d8 + d9 + d11 + d12 d2 + d8 + d10 + d12 + d13 d1 + d9 + d13 + d14 d0 + d8 + d12 + d13 + d14

(7)

N´asoben´ı dvou ˇc´ısel vyˇzaduje 77 hradel XOR, 64 hradel AND. V pˇr´ıpadˇe kod´eru se prov´ad´ı pouze n´ asoben´ı konstantou (tj. koeficienty generuj´ıc´ıho mnohoˇclenu). N´asoben´ı konstantou vyˇzaduje m´enˇe hardwarov´ ych prostˇredk˚ u neˇz obecn´a n´asobiˇcka. Napˇr´ıklad n´asoben´ı ˇc´ıslem 59 vyˇzaduje pouze 28 hradel XOR.

4.2

Dekod´ er Reed-Solomonova k´ odu

Dekod´er je zaloˇzen na Berlekamp-Massey algoritmu pro urˇcen´ı lokalizaˇcn´ıho a evaluaˇcn´ıho mnohoˇclenu a na Forneyho algoritmu pro vyˇc´ıslen´ı velikosti chyb. Tyto algoritmy tvoˇr´ı kitickou

cestu algoritmu. Blokov´e sch´ema dekod´eru je zobrazeno na Obr´azku 7.

data1,...,datan

vypocet syndromu

S1,..,S2t

vypocet lokalizacniho a evaluacniho mnohoclenu (algoritmus Berlekamp−Massey) L(x)

pamet

E(x)

nalezeni pozic chyb (nalezeni korenu lokalizacniho mnohoclenu)

data1,...,datan

P1,...,Pv data1,...,datak oprava chyb M1,...,Mv

vypocet velikosti chyb (Forneyho algoritmus)

Obr´ azek 7: Blokov´e sch´ema RS dekod´eru. Pˇr´ıchoz´ı symboly (na obr´ azku oznaˇceny jako data1 ,...,datan jsou uschov´av´any v pamˇeti RAM. Symboly pˇrich´ azej´ı v poˇrad´ı, v jak´em vych´azej´ı z kod´eru, tj. nejprve datov´e symboly n´asledovan´e kontroln´ımi symboly. Z pˇr´ıchoz´ıch symbol˚ u se poˇc´ıtaj´ı hodnoty syndrom˚ u podle vztahu 8. Vzhledem k n´ aroˇcnosti implementace obecn´ ych mocnin v obvodu FPGA je nutn´e tyto vztahy pˇrev´est podle Hornerova sch´ematu. T´ımto se u ´plnˇe vyhneme mocnˇen´ı, a tak lze v´ ypoˇcet velmi efektivnˇe realizovat v FPGA. Stejn´a reprezentace vztah˚ u je aplikov´an i v dalˇs´ıch kroc´ıch dek´odov´an´ı.

S1 S2 .. .

= R(α0 ) = (e0 + e1 x + · · · + en−2 xn−2 + en−1 xn−1 ) |x=α0 = R(α1 ) = (e0 + e1 x + · · · + en−2 xn−2 + en−1 xn−1 ) |x=α1

(8)

S2t = R(α2t−1 ) = (e0 + e1 x + · · · + en−2 xn−2 + en−1 xn−1 ) |x=α2t−1 Z hodnot syndrom˚ u S1 , . . . , S16 se n´aslednˇe urˇc´ı pomoc´ı algoritmu Berlekamp-Massey (viz A) lokalizaˇcn´ı a evaluaˇcn´ı mnohoˇclen (L(x) a E(x)). Po skonˇcen´ı algoritmu se pokraˇcuje hled´an´ım pozic chyb tak, ˇze se postupn´ ym dosazov´an´ım vˇsech prvk˚ u Galoisova tˇelesa do vztahu 9 hledaj´ı koˇreny mnohoˇclenu. Hled´ an´ı je tedy realizov´ano pouˇzit´ım takzvan´e ”hrub´e s´ıly”. L(x) = 1 + l1 x + l2 x2 + · · · + lv−1 xv−1 + lv xv ; x ∈ 1, 2, · · · , 255

(9)

Po nalezen´ı pozic chyb se pokraˇcuje v´ ypoˇctem velikost´ı chyb pomoc´ı Forneyho algoritmu. Oprava dat v pamˇeti je provedena za podm´ınky, ˇze 1) doˇslo alespoˇ n k jedn´e chybˇe a 2) celkov´ y poˇcet chyb nen´ı vˇetˇs´ı neˇz poˇcet opraviteln´ ych chyb dan´eho k´odu. Implementace kod´eru a dekod´eru byla vyvinuta v r´amci diplomov´e pr´ace [8].

5

V´ ysledky

Zde shrnujeme doc´ılen´e v´ ysledky implementace akceler´ator˚ u pro podporu za prv´e simulace dek´odov´an´ı blokov´eho konvoluˇcn´ıho k´ odu a za druh´e simulace k´odov´an´ı a dek´odov´an´ı ReedSolomonova k´ odu.

V´ ysledky implementace akceler´ atoru pro dek´ odov´ an´ı konvoluˇ cn´ıho k´ odu V´ ysledky implementac´ı Viterbiho dekod´eru jsou zmˇeˇreny pro n´asleduj´ıc´ı parametry dek´odov´an´ı: • Pouˇzito ”Hard” dek´ odov´ an´ı. • D´elka zpˇetn´eho pr˚ uchodu dekod´eru je rovna d´elce dek´odovan´eho r´amce (bez pouˇzit´ı sliding windows). • K=7 • R = 1/2 • G0 = 1111001 • G1 = 1011011 Graf na obr´ azku 8 ukazuje z´ avislost doby dek´odov´an´ı na d´elce datov´eho r´amce pro jednotliv´e implementace akceler´ ator˚ u. Hodnoty doby dek´ odov´ an´ı byly namˇeˇreny v prostˇred´ı Matlab pomoc´ı funkc´ı tic a toc (na PC, CPU Intel Core2 6600 @ 2.4 Ghz, 2 GB RAM; Windows XP SP2), doby dek´odov´an´ı v DSP pomoc´ı ˇc´ıtaˇce procesoru DSP (zahrnuto je v´ ypoˇcet hranov´ ych metrik na stranˇe DSP, pˇrenos pomoc´ı EDMA a doba dek´ odov´ an´ı koprocesoru - viz [2]) a doby dek´odov´an´ı v obvodu FPGA jsou pˇr´ımo urˇceny na z´ akladˇe znalosti struktury implementace dekod´eru a jej´ı mezn´ı pracovn´ı frekvence. Maxim´ aln´ı pracovn´ı frekvence implementace Viterbiho dekod´eru na jednotliv´ ych obvodech FPGA jsou uvedeny v tabulce 1. Hodnoty pracovn´ıch frekvenc´ı jsou z´ısk´any z report˚ u n´astroje Quartus II. Obvod Cyclone nebyl pro implementaci Viterbiho dekod´eru pouˇzit vzhledem k omezen´ ym zdroj˚ um obvodu. Jak bylo zm´ınˇeno v´ yˇse, pouˇz´ıv´ a implementace akceler´atoru ke komunikaci s hostitelsk´ ym ˇ ızen´ı ethernetov´eho rozhran´ı je implementov´ano ve stejn´em obsyst´emem rozhran´ı ethernet. R´ vodu FPGA jako vlastn´ı dekod´er. Maxim´aln´ı pracovn´ı frekvence ˇr´ızen´ı ethernetov´eho rozhran´ı je 50 MHz, a proto je sn´ıˇzena i pracovn´ı frekvence dekod´eru. Optimalizace akceler´atoru pro vyuˇzit´ı maxim´aln´ı moˇzn´e pracovn´ı frekvence dekod´eru bude souˇc´ast´ı dalˇs´ı pr´ace. Na grafu (obr. 8) je z´avislost doby dek´ odov´ an´ı v obvodu FPGA vztaˇzena k pracovn´ı frekvenci 50 MHz. Pr˚ umˇern´ a doba potˇrebn´ a pro odesl´ an´ı (pˇr´ıjem) jednoho ethernetov´eho r´amce byla zmˇeˇrena na zm´ınˇen´em hostitelsk´em syt´emu a jej´ı hodnota je 0,148 ms. V jednom datov´em r´amci je moˇzn´e zaslat aˇz 1272 byt˚ u. Obvod Stratix II (EP2S180F1020C3) Stratix (EP1S10F780C6)

Max. pracovn´ı frekvence 147,74 MHz 100,65 MHz

Tabulka 1: Maxim´ aln´ı pracovn´ı frekvence implementace Viterbiho dekod´eru v obvodu FPGA

Závislost doby dekódování na délce rámce

−3

10

Doba dekódování [s]

DSP + VCP FPGA Maltab

−4

10

−5

10

40

50

60

70

80 90 Délka rámce [b]

100

110

120

Obr´ azek 8: Graf z´ avislosti doby dek´odov´an´ı na d´elce r´amce V´ ykon a latence dekod´eru lze zlepˇsit vzhledem ke zn´am´ ym omezen´ım st´avaj´ıc´ı implementace (optimalizace dekod´eru je souˇc´ ast´ı budouc´ı pr´ace). Komunikace RTDX je zat´ıˇzena pomˇernˇe velkou reˇzi´ı (doba obsluhy komunikaˇcn´ıho kan´alu) na zasl´an´ı jedn´e zpr´ avy. Namˇeˇren´ a pr˚ umˇern´a odezva dek´odov´an´ı jednoho r´amce dat akceler´atorem pˇres RTDX je 0,94 s (souˇc´ ast´ı dalˇs´ı pr´ ace bude optimalizace zp˚ usobu komunikace s akceler´atorem).

V´ ysledky implementace akceler´ atoru pro k´ odov´ an´ı a dek´ odov´ an´ı Reed-Solomonova k´ odu Doby k´odov´ an´ı a dek´ odov´ an´ı byly namˇeˇreny pro k´od RS(255, 239, 8). V tabulce 2 a 3 jsou uvedeny doby k´ odov´ an´ı a dek´ odov´ an´ı v obvodu FPGA a v prostˇred´ı Matlab. Stejnˇe jako v pˇr´ıpadˇe akceler´ atoru pro dek´odov´an´ı konvoluˇcn´ıho k´odu je pracovn´ı frekvence akceler´atoru pro kod´er a dekod´er omezena na 50 MHz. Maxim´aln´ı pracovn´ı frekvence kod´eru a dekod´eru jsou uvedeny v tabulk´ ach Jak je patrn´e z namˇeˇren´ ych hodnot je hardwarov´a implementace Reed-Solomonova kod´eru a dekod´eru o nˇekolik ˇr´ ad˚ u rychlejˇs´ı neˇz implementace v prostˇred´ı Matlab. Podˇ ekov´ an´ı: Tato pr´ ace vznikla za podpory projekt˚ u ˇc´ıslo 1ET100750408 a 1ET300750402 ˇ Grantov´e agentury AV CR.

Doba k´ odov´ an´ı (FPGA) 5,5 µs

Doba k´ odov´ an´ı (Matlab) 1,2834 s

Tabulka 2: Doba k´ odov´ an´ı jednoho vstupn´ıho slova pro k´od RS(255, 239, 8)

Doba dek´ odov´ an´ı (FPGA) 37,4 µs

Doba k´ odov´ an´ı (Matlab) 1,7178 s

Tabulka 3: Doba dek´ odov´ an´ı jednoho vstupn´ıho slova pro k´od RS(255, 239, 8)

Obvod FPGA Stratix II Stratix Cyclone

fmax 138,51 MHz 126,61 MHz 110,5 MHz

Tabulka 4: Maxim´ aln´ı pracovn´ı frekvence kod´eru pro k´od RS(255, 239, 8)

Obvod FPGA Stratix II Stratix Cyclone

fmax 98,35 MHz 72,9 MHz 71,41 MHz

Tabulka 5: Maxim´ aln´ı pracovn´ı frekvence dekod´eru pro k´od RS(255, 239, 8)

Reference [1] Hanzo, L.; Liew, T. H.; Yean, B. L. Turbo Coding, Turbo Equalisation and Space-Time Coding for Transmission over Fading Channels. John Wiley, 2002 ISBN 0-470-84726-3 [2] Texas Instruments. TMS320C64x DSP, Viterbi-Decoder Coprocessor (VCP), Reference Guide [online]. Dostupn´e na WWW: http://focus.ti.com/lit/ug/spru533d/spru533d.pdf [3] Altera. Nios Development Board Reference Manual, Cyclone Edition [online]. Dostupn´e na WWW: http://www.altera.com/literature/manual/mnl_nios2_board_cyclone_1c20.pdf [4] Altera. Nios Development Board Reference Manual, Stratix Edition [online]. Dostupn´e na WWW: http://www.altera.com/literature/manual/mnl_nios2_board_stratix_1s10.pdf [5] Altera. Stratix II EP2S180 DSP Development Board Reference Manual [online]. Dostupn´e na WWW: http://www.altera.com/literature/manual/mnl_stx2_pro_dsp_dev_kit_ep2s180.pdf [6] Texas Instruments. TMS320C6416T DSK, Technical Reference [online]. Dostupn´e na WWW: http://c6000.spectrumdigital.com/dsk6416/V3/docs/dsk6416_TechRef.pdf [7] SMSC. SMSC LAN91C111 Datasheet [online]. Dostupn´e na WWW: http://www.smsc.com/main/datasheets/91c111.pdf ˇ [8] DUSEK, Josef. N´ avrh a implementace opravn´ych k´ od˚ u pro syst´em Orpheus, Praha, 2007. ˇ Diplomov´ a pr´ ace na CVUT FEL. Vedouc´ı diplomov´e pr´ace Ing. Martin Danˇek, Ph.D.

Jan Kloub ´ ˇ v.v.i. UTIA AV CR, Pod Vod´arenskou vˇeˇz´ı 4 Praha 8, 182 08 [email protected] Anton´ın Heˇrm´ anek ´ ˇ UTIA AV CR, v.v.i. Pod Vod´arenskou vˇeˇz´ı 4 Praha 8, 182 08 [email protected]

A

Algoritmus Berlekamp-Massey

Hodnota jak lokalizaˇcn´ıho tak i evaluaˇcn´ıho mnohoˇclenu m˚ uˇze b´ yt nalezena iterativn´ım zp˚ usobem, napˇr. pomoc´ı algoritmu Berlekamp-Massey. P˚ uvodnˇe, tak jak byl algoritmus navrˇzen, slouˇzil jen pro v´ ypoˇcet lokalizaˇcn´ıho mnohoˇclenu, ale lze ho pouˇz´ıt i pro v´ ypoˇcet evaluaˇcn´ıho mnohoˇclenu. V´ ypoˇcet obou mnohoˇclen˚ u pomoc´ı tohoto algoritmu m˚ uˇze b´ yt vyj´adˇren rekurentn´ımi rovnicemi: (i−1)

l di = Si−j j=0 Lj l = δ(i − l ) + (1 − δ)l i−1 " #i " # "i−1 # (i) 1 −di x L (x) L(i−1) (x) = δd−1 (1 − δ)x A(i) (x) A(i−1) (x) i

P

"

E (i) (x) C (i) (x)

#

"

=

1 −di x δd−1 (1 − δ)x i

#"

E (i−1) (x) C (i−1) (x)

(10)

#

Poˇc´ateˇcn´ı podm´ınky jsou L(0) (x) A(0) (x) E (0) (x) C (0) (x) l0

= = = = =

1, 1, 0, 1, 0

(11)

Hodnota δ je definov´ ana jako (

δ=

1, 0,

kdyˇz di 6= 0 a z´aroveˇ n 2li−1 ≤ i − 1 jinak

Symbol L(i) (x), resp. E (i) (x) je hodnota lokalizaˇcn´ıho resp. evaluaˇcn´ıho mnohoˇclenu v i-t´em kroku, obdobnˇe A(i) (x), C (i) (x) jsou hodnoty pro pomocn´ y lokalizaˇcn´ı resp. evaluaˇcn´ı mnohoˇclen, li je stupeˇ n L(i) (x) v i-t´em kroku, di je odchylka (v anglick´e literatuˇre oznaˇcovan´a discrepancy). Na z´ akladˇe odchylky di se urˇc´ı nov´a hodnota L(i) (x), E (i) (x). Lokalizaˇcn´ı a evaluaˇcn´ı mnohoˇclen jsou urˇceny po 2t iterac´ıch, hodnoty se poˇc´ıtaj´ı pro i = 1, 2, . . . , 2t. Nalezen´ı pozic chyb Po dokonˇcen´ı v´ ypoˇctu mnohoˇclenu L(x) je potˇreba nal´ezt jeho koˇreny. To se prov´ad´ı metodou hrub´e s´ıly v literatuˇre naz´ yvan´e Chien search, kter´a spoˇc´ıv´a v tom, ˇze se postupnˇe dosazuj´ı za x vˇsechny prvky z Galoisova tˇelesa GF(2m ) kromˇe nuly, tj. vyˇc´ısluj´ı se hodnoty L(1), L(2), . . . , L(2m − 1) a zaznamen´ avaj´ı se nalezen´e koˇreny mnohoˇclenu, tedy hodnoty, pro kter´e plat´ı L(x) = 0. Pro nalezen´ı pozic chyb Pl je nutn´e koˇreny lokalizaˇcn´ıho mnohoˇclenu zinvertovat a zlogaritmovat, coˇz znamen´a nal´ezt takov´e ˇc´ıslo k, pro kter´e plat´ı Pl = αk , tedy log(Pl ) = log(αk ) = k. V´ ypoˇ cet hodnot chyb Po nalezen´ı pozic chyb je jeˇstˇe potˇreba vypoˇc´ıtat hodnoty velikosti chyb z mnohoˇclenu E(x). V´ ypoˇcet se prov´ ad´ı pomoc´ı Forneyho algoritmu (Forney Algorithm). Hodnota chyby Ml , l ∈

1, . . . , v je urˇcena obecnˇe vztahem: Ml = −

E(Pl−1 ) Pl−1 L0 (Pl−1 )

(12)

L0 (x) znaˇc´ı derivaci lokalizaˇcn´ıho mnohoˇclenu. Derivace mnohoˇclenu w(x) stupnˇe v, w(x) = w0 + w1 x + w2 x + · · · + wv xv je v GF(2m ) definov´ana vztahem L0 (x) = w1 + w3 x2 + w5 x4 + · · · + vwv xv−1 =

v X

jwj xj−1

j=1

V pˇr´ıpadˇe RS k´ odu s koˇreny generuj´ıc´ıho mnohoˇclenu ve tvaru α0 , α1 , . . . , α2t−q lze rovnici 12 pro urˇcen´ı velikosti chyby Ml vyj´ adˇrit Ml =

Pl E(Pl−1 ) v Q

(13)

(1 − Pj Pl−1 )

j=1 j 6= l Pˇri v´ ypoˇctu hodnoty Mi se do evaluaˇcn´ıho mnohoˇclenu dosad´ı inverzn´ı hodnota pozice l-t´e chyby a tato hodnota se vyn´ asob´ı hodnotou pozice l-t´e chyby a n´aslednˇe podˇel´ı souˇcinem v´ yraz˚ u pˇres vˇsechny pozice chyb j rozd´ıln´e od pozice pr´avˇe hledan´e velikosti chyby l. Oprava chyb ˆ(x). Nyn´ı jsou jiˇz zn´ amy vˇsechny hodnoty potˇrebn´e k sestaven´ı odhadu chybov´eho mnohoˇclenu e ˆ(x) tvar e ˆ(x) = αa xk . Napˇr´ıklad pro hodnoty (M1 , P1 ) = (αa , αk ) bude m´ıt chybov´ y mnohoˇclen e ˆ (x) p˚ Chybov´ y mnohoˇclen se seˇcte z mnohoˇclenem pˇrijat´eho slova a z´ısk´a se odhad U uvodnˇe vyslan´eho mnohoˇclenu U (x) ˆ (x) = R(x) + eˆ(x) U (14) Po odstranˇen´ı kontroln´ıch symbol˚ u dostaneme odhad zdrojov´eho mnohoˇclenu m(x) ˆ ˆ (x)/xn−k m(x) ˆ =U