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: 23. 10. 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

* Výběr nejvhodnějšího konvolučního kódu - I

Vydáno dne 12. 03. 2007 (6991 přečtení)

Při přenosu dat se díky zvyšování přenosové rychlosti stále častěji setkáváme s chybami, které mají tendenci shlukovat se. K dispozici jsou konvoluční kódy, které jsou schopny tento přenos dostatečně účinně zabezpečit. Budou srovnány základní konvoluční kódy, které jsou snadno obvodově řešitelné a lze tak jednodušeji simulovat jejich funkci. Předkládaný článek se zabývá návrhem příslušných kódů.


Selection of the optimal convolutional code - I.
Abstract
Because of increasing transfer rate during the data transmission errors, which have a tendency to flock in, appear more frequently. To use are available convolutional code, which are able to secure efficiently enough transmission. Comparison of basic convolutional codes, which have easy realization in basic logical circuits and thanks to that their functions simulation is simple, will be shown. This paper defines proposal of relevant codes.



Poprvé byly představeny konvoluční kódy pro opravu shlukových chyb Hagelbargerem. Dále pak nezávisle na sobě Iwadari a Masery zkonstruovali efektivnější kódy stejného typu. Jejich kódy se stejnou korekční schopností vyžadují kratší ochranné intervaly než Hagelbargerovy kódy. Optimální kódy pro opravu postupných shlukových chyb byly později objeveny nezávisle Berlekampem a Preparatem.

Pro výše uvedené systematické konvoluční kódy bude ukázán návrh kodéru a dekodéru, který je schopen opravit shluk 4 chyb. Díky systematičnosti ve výsledné přenášené kódové kombinaci lze vždy rozlišit prvky informační a zabezpečující. Jednotlivé kódy jsou popsány především vytvářecí blokovou maticí B, pomocí níž lze odvodit jednotlivé prvky kodéru i dekodéru a jejich následné potřebné zapojení. V dalším pokračování článku se navíc budeme zabývat nejlepší variantou mezi těmito kódy.

Při vytváření konvolučního kódu se nám nabízejí dvě základní metody. Kód lze zadat buď pomocí vytvářcího mnohočlenu nebo pomocí vytvářecí matice. U příjemce zprávy se pro nalezení nejpravděpodobnějšího odhadu správné posloupnosti používá u konvolučních kódů Viterbiho algoritmus. Princip algoritmu spočívá ve vyhledávání nejmenší Hammingovy vzdálenosti dekódované poslopnosti od přijaté posloupnosti. Nevýhodou zmiňovaného algoritmu je jeho značná náročnost na počet numerických operací. Uvedený způsob se používá jen pro dekódování kódů s relativně krátkými omezujícími délkami, jelikož závislost počtu prováděných operací má exponenciální charakter. Další metodou k vyhledávání chyb, která bude u jednotlivých kódů v tomto článku použita je princip prahového dekódování. Základním vlastností prahového dekódování je nalezení dostatečného počtu kontrolních operací mezi jednotlivými prvky úseku zprávy, které mají mezi sebou tzv. vztah ortogonality vzhledem k prvku, jehož správnost se po přenosu kontroluje.

Základní Hagelbargerův kód (n0; n0 - 1)

Kód lze určit pomocí blokové matice v dekadickém tvaru BD, která má tvar čtvercové matice rozměru n0 x n0 a v každém řádku je v místě odpovídající prvku na úhlopříčce liché dekadické číslo. Řádky se číslují odspodu a v prvním řádku je trojka, v (n0 - 1) řádku je (2n0 - 1) poslední řádek obsahuje jedničku viz. (1).

konvoluce_1
(1)

Matice BD se pro potřebu dvojkových kódů převádí na blokovou matici ve dvojkovém tvaru B0. Dvojková bloková matice B0 má opět n0 sloupců. Počet řádků je určen součinem n0 a počtem míst potřebných k zapsání největšího čísla, které se v BD vyskytuje. Počet míst dekadického čísla n, potřebných pro jeho zapsání dvojkovým číslem, označujeme L(n), což je nejmenší celé číslo, které vyhovuje nerovnosti:

konvoluce_2
(2)

Dvojková čísla s menším počtem míst mají v matici B0 na nepoužitých místech nuly. První číslo odspodu má vždy pouze dva řádky, protože nuly v místech nepoužitých dvojkových míst by způsobovaly v realizaci kodéru pouze neužitečné časové zpoždění. Pro počet řádků dvojkové matice jde tedy odvodit následující vztah:

konvoluce_3
(3)

Tento kód opravuje shluky chyb délky b bitů:

konvoluce_4
(4)

Mezi těmito shluky chyb musí být v bitovém toku bezchybný úsek – ochranný interval A:

konvoluce_5
(5)

Kód pro opravu shluku chyb b délky až 4 bity potřebuje dodržení ochranného intervalu A minimální délky 47 bitů. Vytvoření zapojení kodéru odvodíme z B0 viz. (1) pomocí souboru vytvářecích mnohočlenů. U vytvářecího mnohočlenu je výstupním tokem čtvrtý sloupec blokové matice. Vstupním tokem je postupně první až třetí sloupec této matice. Hledají se řádky, kde se příslušné dva sloupce liší. Zapojení kodéru jest uvedeno na Obr. 1 a určují jej zabezpečující vytvářecí mnohočleny získané z vytvářecí blokové matice:

konvoluce_6
(6, 7, 8)

konvoluce_7

Obr. 1 - Kodér Hagelbargerova kódu pro korekci 4 chyb

Dekodér Hagelbargerova kódu vychází z obecného schématu dekodéru se syndromovým dekódováním (viz. Obr. 2). Využívá se přímého převodu vektoru syndromu na chybový vektor. Z přeneseného bloku dat se oddělí zabezpečovací prvek, který se sečte mod2 s nově vypočítaným zabezpečovacím prvkem, jenž se vytvořil v kodéru přijímače. Tím vznikne syndromový prvek s, který slouží k nalezení a korekci chyb v dílčích posloupnostech přenesených informačních prvků.

konvoluce_8

Obr. 2 - Dekodér Hagelbargerova kódu pro korekci 4 chyb

Základní Iwadari-Maseryův kód (m*n0; m*k0)

Iwadariho kód je opět popsán vytvářecí blokovou maticí B0, která má n0 sloupců. Sloupce jsou indexovány zleva od ai, řádky se číslují vzestupně zespodu. Na nejvyšším řádku úplně vpravo je umístěna jednička představující zabezpečovací prvek. Následují nulové řádky až do počtu n0. V dalším řádku je umístěna jednička posunutá oproti původní pozici o jedna doleva. Následující řádek má jedničku na stejné pozici. Takto je zajištěna oprava jednoho bitu. Pro opravu dalších je třeba se opět posunout o jednu pozici vlevo a počet vložených nulových řádků mezi dvěma jedničkami ve stejném sloupci vždy vzrůstá o jeden řádek až do celkové velikosti n0. Názorně uvedeno v rovnici (9), kde je obecné schéma vytvářecí matice Iwadariho kódu.

konvoluce_9
(9)

Pro jednotlivé parametry kódu platí:

konvoluce_10
(10)

kde m a k0 jsou definovány:

konvoluce_11
(11, 12)

k0 a n0 představuje počet dílčích vstupních či výstupních paralelních toků. Při návrhu jsou třeba ještě parametry pro korekční schopnost b a ochranný interval A:

konvoluce_12
(13, 14)

V případě překročení mezní zabezpečovací schopnosti nezpůsobuje tento kód nekonečný průnik chyby do vlastní informace. Z vytvářecí blokové matice lze opět vytvořit kodek Iwadariho kódu viz Obr. 3 a 4. Vyjdeme z vytvářecí blokové matice B0 určené ze vztahu (9). Pro vytvoření návrhu zapojení je důležitá syndromová rovnice matice kódu, z níž lze odvodit jednotlivé prvky kodéru. Za předpokladu, že v samotném kodéru nevznikají chyby pak pro zabezpečovací prvek d13 platí:

konvoluce_13
(15)

Uvedená rovnice (15) přímo určuje schéma zapojení kodéru viz Obr. 3.

konvoluce_14

Obr. 3 - Kodér Iwadari-Maseryova kódu pro korekci 4 chyb

Způsob dekódování dat na straně příjemce je naznačen na Obr. 4. Princip dekodéru spočívá ve využití prahového dekódování. K syndromové rovnici pro určitý čas k bitům v ní obsažených je třeba nalézt bity na zabezpečení se podílejících v čase předcházejícím. Za pomocí dvou syndromových rovnic lze provést korekci jednoho bitu. Pro korekci dalších bitů je třeba jít dále „hlouběji do historie“ a určit tak další nezbytné syndromové rovnice. Jejich celkový počet určuje množství potřebných syndromových paměťových buněk. Model dekodéru (viz. Obr. 4.) je sestaven na základě znalostí potřebných rovnic:

konvoluce_15
(16, 17, 18, 19)

konvoluce_16

Obr. 4 - Dekodér Iwadari-Maseryova kódu pro korekci 4 chyb

Základní Berlekamp-Preparatův kód (n0; n0 - 1; m)

Postup objevený nezávisle Berlekampem a Preparatem, vždy přinese kód splňující Gallagerovy meze. Gallager ukázal, že libovolný konvoluční kód o informační rychlosti R má schopnost opravit všechny shluky délky b nebo kratší vzhledem k ochrannému intervalu délky A, jestliže platí:

konvoluce_17
(20)

Tento vztah je znám jako mez kompletní opravy shlukové chyby. Z tohoto důvodu jsou Berlekamp-Preparatovy kódy optimální pro opravu postupných shlukových chyb.

Jedná se o systematický konvoluční kód ke korekci shluků omezených do samostatného bloku úměrného ochranému intervalu m bezchybných bloků (tj. shluk může ovlivnit nanejvýš jeden blok omezené délky). Tento kód by měl mít schopnost postupné opravy shlukových chyb jednoho bloku úměrně ochrannému intervalu m bloků. I tento kód lze popsat vytvářecí maticí B0, jejíž rozměry jsou n0 x 2n0, jež se skládá ze dvou podmatic. První podmatice má jedničky na vedlejší diagonále a druhá podmatice má nad hlavní diagonálou jedničky. Přičemž obě podmatice mají shodný rozměr n0 x n0. Zbylé prvky jsou nulové viz. (21).

konvoluce_18
(21)

Z (20) při podmínce R = (n0 - 1)/n0 dostaneme další parametry kódu:

konvoluce_19
(22)

Bloková vytvářecí matice určuje způsob zapojení kodéru viz. Obr 5. Opět se jedná o systematický konvoluční kód s generačními polynomy:

konvoluce_20
(23, 24, 25)

konvoluce_21

Obr. 5 - Kodér Berlekamp-Preparatova kódu pro korekci 4 chyb

Berlekamp-Preparatovy kódy mohou být dekódovány použitím obecné dekódovací techniky pro konvoluční kódy opravující shlukové chyby zásluhou Masseyho. V uvedeném dekodéru nemůže nastat nekonečné šíření chyby a jeho schéma je uvedeno na Obr. 6.

konvoluce_22

Obr. 6 - Dekodér Berlekamp-Preparatova kódu pro korekci 4 chyb

Závěr

Zabezpečení se dosahuje zvýšením nadbytečnosti na úkor vlastního přenosu užitečné informace. Je tedy velmi důležité najít nejvhodnější řešení, které se ovšem liší případ od případu. Zde uvedená řešení jsou srovnána v pokračování tohoto článku. Avšak chybovostí v systému se zabýváme, až pokud výskyt různých typů chyb překročí únosnou mez. Pomocí konvolučních kódů lze realizovat zabezpečení přenášené posloupnosti nepřetržitým způsobem. Nejpoužívanější typy kódů z této skupiny představují ochranu před shluky chyb různé délky. Druhý díl článku.

Tento článek vznikl za podpory výzkumného projektu FRVŠ - 993 G1 "Simulace zabezpečovacích korekčních kódů a její začlenění do výuky předmětu Datová komunikace".

Literatura

[1] Křivánek, V., Číka, P.: Simulace shlukových chyb v Matlabu. Elektrorevue, 2006, č. 35, str. 1-10. ISSN 1213-1539.
[2] Křivánek, V.: Verification of the Error-Control Security Process by Means of Simulation. International Transactions on Communication and Signal Processing, 2006, vol. 9, no. 1, p. 128-136, ISSN: 1738-9682.
[3] Němec, K.: Kódové zabezpečovací systémy. Teze habilitační práce, ÚTKO FEI VUT Brno, Brno 1999, 34s., ISBN 80-214-1312-3.
[4] Němec, K.: Výběr optimálního protichybového kódu. Elektrorevue, 2006, č. 54., str. 1-9. ISSN 1213-1539.
[5] Shu, L.; Costello, D.: Error Control Coding – Fundamentals and Applications. Prentice-Hall, Inc., Englewood Cliffs, New Jersey 1983, 603 p., ISBN 0-13-283796-X.



Autor:        V. Křivánek, P. Číka
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ů.