No title

Vážení zákazníci, dovolujeme si Vás upozornit, že na tuto ukázku knihy se vztahují autorská práva, tzv. copyright. To znamená, že ukázka má sloužit výhradnì pro osobní potøebu potenciálního kupujícího (aby ètenáø vidìl, jakým zpùsobem je titul zpracován a mohl se také podle tohoto, jako jednoho z parametrù, rozhodnout, zda titul koupí èi ne). Z toho vyplývá, že není dovoleno tuto ukázku jakýmkoliv zpùsobem dále šíøit, veøejnì èi neveøejnì napø. umisováním na datová média, na jiné internetové stránky (ani prostøednictvím odkazù) apod. redakce nakladatelství BEN – technická literatura

[email protected]

6.

DETEKCE CHYB

6.1

Lineární binární blokové kódy

Binární blokový kód je lineární, jestliže výsledkem souètu dvou kódových slov je opìt kódové slovo. Pro vytváøení úèinných zpùsobù kódování se nejèastìji používá úprava zprávy vyjádøené v binární podobì. Pøedpis pro úpravy zpráv je vhodné navrhovat jako lineární závislost. Bude se vždy jednat o vztah mezi informaèními (zdrojovými) slovy a kódovými slovy. Tento vztah je výhodné vytvoøit jako jednoznaèný pøedpis pro výpoèet kódového slova ze slova informaèního a jednoznaèný výpoèet pùvodního informaèního obsahu z kódového slova. Praktické zjednodušení synchronizace slov zprávy poskytuje tzv. blokové kódování. Pøi použití systematického binárního blokového kódu je možné rozlišit v kódovém slovì èást, která je pùvodním informaèním slovem (informaèní bity) a èást, která byla kódováním pøidána (zabezpeèovací nebo také kontrolní bity). Zpùsob vytváøení slov je možné zobrazit následovnì: informaèní slovo o délce k bitù u1u2 .... uk je kódováním zpracováváno na kódové slovo o délce n bitù u1u2....ukuk+1uk+2 ... un. Výhodou binárních lineárních kódù je to, že pøedpis pro kódování mùže být vždy popsán jako soustava rovnic, ve kterých jsou použity operace sèítání a násobení binárních èísel. Pravidla platná pro binární èíslice vyjádøené znaky 0 a 1 jsou vyjádøena v tabulkách: n pro sèítání platí

n pro násobení platí

Æ





™





























Tabulka pro násobení binárních èísel odpovídá obvyklým zvyklostem, ale tabulka pro sèítání definuje výsledek 1 + 1 = 0. To ovšem znamená, že v této èíselné soustavì platí 1 = –1. Sèítání binárních èísel v nepolyadických soustavách je tedy totéž, co odeèítání.

Komprese a kódová zabezpeèení v multimediálních komunikacích

71

6.2

Generující matice kódu

Maticový popis kódovacího pøedpisu binárního lineárního kódu je lineární soustava rovnic s binárními koeficienty a aritmetikou. Èasto používaným lineárním binárním kódem je tzv. kontrola parity, který je správnìji nazýván kód celkové parity. Spoèívá v tom, že k binárnímu slovu u1u2....uk pøipojíme pouze jeden znak uk+1, který je vyjádøen rovnicí pro kódování

X N + = X Æ X  ÆÆX N . Protože se jedná o lineární binární kódování, mùžeme použít vyjádøení pomocí maticového popisu. Jeho výhody nebudou zøejmé ihned. Na tomto jednoduchém pøíkladu kódování kódem celkové parity se mùže použití maticového popisu jevit jako zbyteèná komplikace. Oznaème nejdøíve zmìny, které je nutné rozlišovat, je-li posláno kódové slovo u1u2....ukuk+1 komunikaèním kanálem. Pøijaté slovo oznaèíme v1v2...vkvk+1. Pøijaté slovo, které bylo poškozeno chybou, bude w1w2...wkwk+1. Nyní mùžeme definovat chybové slovo pomocí relace w1w2....wkwk+1 = v1v2....vkvk+1 + e1e2....ekek+1, pøitom pro obecné vyjádøení libovolného znaku chybového slova bude platit

Å Y L ¹ Z L HL = ­ . ® Y L = Z L Budeme se zabývat pøípadem, kdy vybraná kódová slova obsahují v informaèních bitech pouze jednu jednièku a ostatní bity jsou nulové. (Z kódových slov je možné vypoèítat další slova kódu). Nyní budeme definovat tzv. generující matici [G] kódu. Tato matice je tvoøena kódovými slovy tzv. báze kódu (jsou lineárnì nezávislá). Chceme-li nalézt kódová slova lineárního binárního kódu, staèí, když nalezneme bázi kódu. Báze kódu je tvoøena slovy, která jsou lineárnì nezávislá. Ostatní slova lineárního kódu mohou být získána sèítáním libovolných dvou slov báze kódu. Matice G typu (k, n) je generující maticí lineárního kódu, jestliže: a) každý její øádek je kódovým slovem, b)

každé kódové slovo je lineární kombinací øádkù,

c) øádky jsou lineárnì nezávislé. Pro paritní systematický kód má generující matice tvar:

72

Komprese a kódová zabezpeèení v multimediálních komunikacích

« à Ã Ã *=à Ã Ã à ì

      á ³       ³       ³ ³       ³ .       ³ ³       ³ã

Není to jediná báze kódu. Báze kódu je tvoøena všemi kombinacemi kódových slov, která jsou lineárnì nezávislá. (Dokonce mohou být seètena dvì stejná slova; to ovšem znamená, že výsledkem je nulové kódové slovo. Z tohoto pravidla plyne, že nulové slovo vždy patøí do lineárního kódu; ze stejného dùvodu však nemùže být obsaženo v generující matici.) Vybraná kódová slova mohou tvoøit jednotkovou matici. Zabezpeèovací bityvá slova vytváøíme podle algoritmu daného kódování. Seøadíme-li takto vytvoøená kódová slova do øádkù a uzavøeme je do matice, získali jsme tzv. generující matici systematického kódu:

[ ]

* = (% . Generující matice má význam pro vytváøení kódu v tom, že souèinem informaèního slova s generující maticí získáme kódové slovo. Tomuto postupu se øíká zakódování, ale èastìji kódování. Kódováním je tedy myšlen pøedpis (algoritmus) pro pøemìnu informaèních slov na slova kódová, ale také operace provádìná podle tohoto algoritmu. Význam slova kódování bude rozlišován podle kontextu, ve kterém je použit. Abychom netvoøili vìtšinou nulová slova, provedeme zestruènìní lineární soustavy rovnic eliminací.

6.3

Kontrolní matice

Opaèný postup nazývaný dekódování se provádí po pøijetí slova z komunikaèního kanálu pomocí tzv. kontrolní matice, která pøedstavuje homogenní soustavu lineárních rovnic. Jestliže kódové slovo v1v2....vkvk+1 (respektive v1v2....vkvn, nebo kód celkové parity obsahuje pouze jeden kontrolní bit) pøijmeme nepoškozené, jedná se o správné øešení lineární soustavy rovnic; její koeficienty tvoøí prvky kontrolní matice. V tom pøípadì platí

«Y  á «á à ³ à ³ ÃY  ³ ó + ¢ à  ³ = ó à ³ à ³. à  ³ ó ÃY ³ ó ¬ Qã ¬ ã Komprese a kódová zabezpeèení v multimediálních komunikacích

73

Vztah mezi generující maticí a kontrolní maticí je popsán pomocí matice B. Kontrolní matice H je definována vztahem:

[

]

+ = - %7 ( ë ,

kde E¢ je jednotková matice.

6.4

Kontrolní matice kódu celkové parity

Provedeme-li výpoèet kontrolní matice pro kód celkové parity, získáme ze sloupcové matice B transponováním øádkovou matici –BT. Záporné znamínko u všech prvkù matice mùžeme s ohledem na shodný výsledek sèítání nebo odeèítání zanedbat.

+ = [     ] . Poslední jednièka, která je k matici –BT pøipojena, je jednotkovou maticí rozmìru 1. Souèinem této matice H se sloupcovým vektorem, který vznikl z vektoru pøijatého slova v1v2....vkvn, získáváme homogenní soustavu rovnic. Tato soustava je tvoøena jedinou rovnicí, která je totožná s definièním vztahem kódu celkové parity, který je tentokrát vyjádøený pro slovo pøenesené komunikaèním kanálem a pøijaté.

Y N + = Y  Æ Y  ÆÆY N . Z poslední rovnice je zøejmé, že nejmenší vzdálenost mezi kódovými slovy kódu celkové parity je vždy d = 2. Zmìnou hodnoty v libovolném informaèním bitu se zmìní také hodnota kontrolního bitu. Odvození generující a kontrolní matice je základním postupem, který bude uplatòován i u dalších lineárních binárních kódù. Pro dekódování je pro kód celkové parity použit implicitní vztah Y  Æ Y  ÆÆY N Æ Y Q =  . Bude-li rovnice homogenní, bude pøijaté kódové slovo bez chyby. Bude-li pravá strana rovnice nenulová, signalizuje to, že bìhem pøenosu došlo k chybì. Požadavky, které jsou v praxi kladeny na rychlost výpoètu pøi kódování a pøi dekódování kódù vedou k použití obvodových øešení kodérù a dekodérù. Program mikropoèítaèe by byl ve složitìjších pøípadech pøíliš pomalý. Obvodová øešení, která využívají efektivity návrhu pomocí programovatelných èíslicových obvodù, jsou dnes již standardizována.

74

Komprese a kódová zabezpeèení v multimediálních komunikacích

6.5

VHDL model kodéru a dekodéru kódu celkové parity

Vìtšina výrobcù dodává programové soubory, které podporují návrh obvodù na úrovni, která poskytuje technologickou nezávislost. To znamená, že návrháø rozhoduje o použité technologii implementace až tehdy, když má návrh obvodu hotový a ovìøený pomocí simulaèních metod. Nástrojem pro technologicky nezávislý návrh je tzv. jazyk VHDL (Very High Speed Integrated Circuit Hardware Description Language). Výrobci dodávají ke svým logickým a hradlovým polím knihovny v jazyce VHDL, které usnadòují automatizovaný pøeklad do implementaèních souborù pro personifikaci obvodù. (podrobnosti viz Pøíloha B.) Návrh obvodu pomocí VHDL je metoda, která je nezávislá na použité implementaèní technologii. Øešení návrhu pomocí jazyka VHDL spoèívá v popisu chování, který je zapsán pomocí modelu obvodu. K tomu se používá alfanumerického souboru sestaveného z prvkù jazyka VHDL. Popis se nazývá model chování a je tvoøen zápisem funkèních vztahù a procedur vyjádøených na úrovni procedurálního jazyka VHDL. Protože jazyk umožòuje pracovat také na úrovni propojení jednotlivých prvkù èíslicových obvodù, je vybaven jednotným rozhraním, které se nazývá entita. Entita tedy popisuje rozhraní mezi navrhovaným modelem obvodu a okolím, které je rovnìž tvoøeno entitami. Model obvodu má pomocí entity urèena pøipojovací místa a souèasnì je definováno, zda se jedná o vstupy, výstupy nebo obojí a to v podobì sbìrnice nebo jinak uspoøádaných vývodù. Rovnìž je v entitì stanoveno, pro jaký typ vývodu (jednotlivý nebo hromadný) je pøipojovací místo urèeno. (17,7<[RUBJDWH,6 3257 LQLQ ,1ELW R 287ELW  (1'[RUBJDWH

K uvedenému popisu rozhraní exclusive-or hradla je popis chování definován jako: $5&+,7(&785(H[RU2)[RUBJDWH,6 %(*,1 R LQ;25LQ$)7(5QV (1'H[RU

Každý popis modelu obvodu v jazyce VHDL mùže být použit jako tzv. knihovní prvek, tedy obvod, který je v dalších modelech pouze deklarován. Pøi simulaci je ovšem nutné, aby knihovní prvek byl dostupný.

Komprese a kódová zabezpeèení v multimediálních komunikacích

75

6.6

Model propojení

Dekodér osmibitového kódu celkové parity je popsán entitou s osmi vstupy a jedním výstupem. Pro popis je použito pøedchozího modelu hradla exclusiveor. Proto je nezbytné, aby v entitì byly deklarovány i vnitøní signály i1 až i7. (17,7<GHFRGHU,6 3257 XXXXXXXX X 6,*1$/LLLLLL (1'GHFRGHU

,1ELW 287ELW  ELW

Popis modelu obsahuje odkaz na hradlo exclusive-or, které je použito v modelu dekodéru kódu celkové parity jako knihovní prvek. $5&+,7(&785(GHFBSDULW\2)GHFRGHU,6 &20321(17[RUBJDWH 3257 LQLQ ,1ELW R 287ELW  (1'&20321(17 %(*,1 Q [RUBJDWH32570$3XXL  Q [RUBJDWH32570$3LXL  Q [RUBJDWH32570$3LXL  Q [RUBJDWH32570$3LXL  Q [RUBJDWH32570$3LXL  Q [RUBJDWH32570$3LXL  Q [RUBJDWH32570$3LXX  (1'GHFBSDULW\

Tento model nazvaný dec_parity je modelem propojení souèástek xor_gate.

6.7

Model chování

Chování modelu však mùže být popsáno i bez použití základních hradel exclusive-or. Popis modelu v tom pøípadì používá operátoru základní logické funkce, která je definována v jazyce VHDL. $5&+,7(&785(EHKDYBGHFBSDULW\2)GHFRGHU,6 %(*,1 X X;25X;25X;25X;25X;25X;25 X;25X$)7(5QV (1'EHKDYBGHFBSDULW\

76

Komprese a kódová zabezpeèení v multimediálních komunikacích

Popis chování se vztahuje ke stejné entitì nazvané decoder. Vnitøní signály deklarované v entitì zùstanou nevyužity. Optimalizace zapojení obvodu dekodéru parity je ponecháno na schopnostech návrhového systému a zejména na možnostech, které nabízí knihovna dodaná výrobcem pro uvažovaný typ obvodu. V tomto pøípadì je èasová odezva AFTER 5 ns pouze odhadem, který musí být pøi podrobnìjší obvodové simulaci upøesnìn na základì použitých knihovních blokù. Nevýhoda nepøesného návrhu je ale zároveò výhodou, protože usnadòuje zaèlenìní dekodéru do návrhu vìtšího obvodového øešení. Snadnìjší je také inovace takto popsaného bloku, protože v modelu chování nemusí být provedeny již žádné zmìny, které by u pøedchozího modelu propojení byly nezbytné, kdyby byl napøíklad použitý jiný typ hradlového pole. Oba typy modelù mají svá opodstatnìní, ale každý má své specifické použití.

6.8

Disková pole – Aplikace kódu celkové parity

K èetným aplikacím kódového zabezpeèení byla v roce 1987 pøipojena metoda zápisu informací do nìkolika diskových jednotek. Místo sekvenèního zápisu, který je obvyklý pøi použití jedné diskové jednotky, je informace do diskového pole zapisována souèasnì do n diskových jednotek. Èinnost vnìjší pamìti se tím zrychlí asi n-krát. Kromì toho však je možné zlepšit spolehlivost diskové pamìti použitím zabezpeèovacího kódu. Metoda souèasného zápisu informace na nìkolik diskù byla navržena pøed deseti lety na Universitì v Berkeley. Byla pojmenována RAID (Redundant Array of Inexpensive Discs). Metoda pøinesla nìkolikanásobné zvýšení rychlosti zápisu a ètení informací ve srovnání s použitím jednoho disku. Navíc však pøinesla zlepšení spolehlivosti diskové pamìti za cenu pomìrnì malé redundance. Ke každé skupinì diskù se totiž pøidává pouze jeden disk jako záložní. Této výhodné vlastnosti se používá v šesti základních konfiguracích diskových polí. Podle toho jsou nazývány i metody v podrobnìjší specifikaci jako RAID 0 až RAID 5. Základní myšlenka je spoleèná všem konfiguracím: informace se rozkládá na nìkolik diskù, pouze zpùsob rozložení je rozdílný. Zpùsob rozkladu informace je charakterizován nejmenší jednotkou, která zùstává pohromadì na jednom disku. Mùže to být jakýkoliv objem informace od jedné slabiky až po celý sektor. Tomuto objemu informace odpovídá i poèet paritních bitù, které jsou zapisovány na záložní diskovou jednotku. Nejjednodušší diskové pole, oznaèované RAID 0 neobsahuje žádnou zálohu. Je používáno pouze pro zrychlení pøístupu k informacím použitím paralelního zápisu a ètení. RAID 1 je v tomto pojetí pouze novým názvem pro již døíve používanou metodu zálohování diskù zrcadlením. Zápis všech informací je pøi tom provádìn na dva disky souèasnì. Je zøejmé, že nadbyteèná informace má v tomto pøípadì stejný objem jako užiteèná informace. Pokud je v tomto pøípadì pro každý disk Komprese a kódová zabezpeèení v multimediálních komunikacích

77

použitý samostatný øadiè, zápis probíhá na oba disky souèasnì. Ke zrychlení zápisu tedy vlastnì nedochází, dochází však k zálohování celého záznamu. Pokud je použito kombinace RAID 0 a RAID 1, jsou ke dvìma øadièùm diskù pøipojena dvì stejnì velká pole diskù, která ovšem nesou stejnou informaci. Nìkdy bývá tato kombinace metod oznaèována jako RAID 6. V systému RAID 2 se pøidané disky používají pro záznam zabezpeèovacích bitù Hammingova kódu, takže velikost redundance je urèována vlastnostmi zvoleného kódu. Pro praktické použití je vhodná konfigurace deseti diskù pro záznam dat a ètyø diskù pro záznam kontrolních bitù kódu. Z celkové kapacity je pro neredundantní informaci využito 71 % záznamové kapacity. Konfigurace RAID 2 je s výhodou používána pro tzv. støediskové poèítaèe. Disková pole RAID 3 až RAID 5 mají øadu spoleèných vlastností. Redundance záznamu je nižší než 20 %, protože ke ètyøem diskùm pro záznam informací se používá jeden záložní obsahující kontrolní bity informací zapsaných na datových discích. Odolnost diskového pole proti poruchám je zajištìna možností rekonstrukce obsahu celého disku, který má poruchu. Dojde-li ke ztrátì jeho obsahu, spustí se proces rekonstrukce, v jehož prùbìhu jsou vypoèítány všechny chybìjící informace jako parita obsahu všech zachovaných diskù. Pøíklad rekonstrukce je uveden v následujícím postupu na obr. 6.1. První ètyøi disky jsou datové, pátý je paritní, takže slabiky zapsané na tento disk vznikly jako parita slabik zapsaných na datové disky. Pøedpokládejme, že tøetí datový disk má poruchu a jeho obsah je tedy nutno rekonstruovat. Rekonstrukce tøí slabik jeho obsahu je popsána v pravé èásti obrázku. Systém RAID 3 používá rozprostøení informace na disky po slabikách a na pøidaný disk zapisuje do kontrolní slabiky paritu slabik zapsaných na datové disky po slabikách a na pøidaný disk zapisuje do kontrolní slabiky paritu slabik zapsaných na datové disky. Pøi zápisu i pøi ètení se informace pøenáší v blocích oznaèovaných jako „jednotka pøenosu informace“ (JPI), jejichž velikost je dána souèinem poètu slabik v jednom sektoru na jednom disku a poètem datových diskù. Pro typickou konfiguraci se ètyømi datovými disky a jedním paritním diskem pøi délce sektoru 512 dostáváme délku JPI 2048 slabik. Systém RAID 3 je výhodný, je-li objem pøenášené informace nejménì roven JPI. Pro menší objemy dat vznikají ztráty èasu, protože vždy je tøeba èíst nebo zapsat celou délku JPI. Aby se odstranily rùznì dlouhé doby hledání sektoru zpùsobené rùzným úhlem natoèení diskù, používá se v této konfiguraci synchronizace všech vøeten diskù.

78

Komprese a kódová zabezpeèení v multimediálních komunikacích