Tématem tohoto dílu bude v∞klad rodiny Hammingov∞ch kódà. Zam╪²íme se p²itom zejména na jejich binární podobu, u které si podrobn╪ vyloºíme zpàsoby detekce a opravy chyb. Ukáºeme si téº ilustrativní p²íklad hardwarové realizace popsaného kódu.
V╪tτina publikací zab∞vajících se problematikou implementace bezpeƒnostních kódà vychází ve svém v∞kladu v╪tτinou ze zajeté τablony, kdy je nejd²íve v╪nován krátk∞ prostor uºit∞m algebraick∞m strukturám a poté jsou vysv╪tlovány jednotlivé rodiny ECC, a to uº bez v╪tτí návaznosti na obecné principy, vyloºené v úvodní pasáºi. Je pravda, ºe takov∞to postup má v∞hodu v tom, ºe ƒtená²e vede nejkratτí cestou p²ímo k návrhu p²ísluτného kodéru a dekodéru a nezab∞vá se p²itom "zbyteƒn∞mi" detaily. Jak jsem uº ²íkal úvodem, má tento seriál slouºit hlavn╪ jako implementaƒní p²íruƒka. To znamená, ºe ani zde se nebudeme zab∞vat p²íliτn∞mi detaily. Na druhou stranu by bylo ale jist╪ τkoda vynechat takové drobnosti, které sice samy o sob╪ nejsou nutné pro praktickou realizaci konkrétního typu ECC, avτak jejichº pochopení umoºní v∞razn╪ kvalitn╪jτí objasn╪ní vτech souvislostí v celém systému, a to za cenu jen nepatrn╪ vyττích nárokà na ƒtená²ovu pozornost.
Hammingovy kódy, kter∞m se budeme za okamºik v╪novat, jsou ideální k tomu, abychom si na nich názorn╪ demonstrovali p²echod od obecné teorie lineárních kódà, kter∞m byl v╪nován minul∞ díl tohoto seriálu, k návrhu konkrétní rodiny kódu s poºadovan∞mi vlastnostmi. Zapomeσme proto nyní na okamºik na to, ºe Hammingovy kódy uº existují. P²edstavme si, ºe neznáme nic jiného neº obecnou teorii ECC a ºe pomocí t╪chto znalostí chceme navrhnout lineární kód, kter∞ bude schopen opravit jednonásobné chyby (bude typu SEC). Takto vybaveni se nyní vydejme na stejnou cestu, na jakou se roku 1950 vydal Dr. Hamming, a stejn╪ jako on tehdy oƒekávejme s nap╪tím, k jak∞m v∞sledkàm nakonec dosp╪jeme.
O minimální váze a matici H
P²edstavme si, ºe máme obecn∞ lineární kód ??typu (n,k) s kontrolní maticí H typu [n-k,n]. Podle tvrzení T3.4 víme, ºe v∞poƒet minimální kódové vzdálenosti dmin(?) màºeme p²evést na hledání minima váhy p²es mnoºinu vτech kódov∞ch slov. Pokusme se nyní toto uºiteƒné tvrzení jeτt╪ rozτí²it s cílem najít a dokázat n╪jakou souvislost mezi minimální kódovou vzdáleností a vlastnostmi matice H.
Pro tento úƒel se jeτt╪ jednou podívejme, jak vypadá proces dekódování p²ijatého slova x. Minule jsme si ²ekli, ºe p²ijatá slova klasifikujeme jako kódová ƒi nekódová na základ╪ jejich syndromu, kter∞ poƒítáme jako s = HxT. Tvrzení T3.5 nám ²íká, ºe slovo x je kódové práv╪ tehdy, kdyº je jeho syndrom s nulov∞. Popiτme si nyní, co vlastn╪ znamená poºadavek na nulov∞ syndrom z pohledu matice H, a zab∞vejme se p²itom pouze rozborem pouºité operace násobení vektoru maticí. Snadno nahlédneme, ºe sloupcov∞ vektor s vlastn╪ p²edstavuje lineární kombinaci vektorà sloupcà matice H. P²ísluτné koeficienty této kombinace jsou p²itom p²edstavovány p²ímo jednotliv∞mi sou²adnicemi vektoru x. Zapíτeme-li toto pozorování formáln╪, potom platí, ºe sT = (s1, s2, ..., sn-k), kde si = ?j=1n hij*xj.
To, co jsme práv╪ získali, je vztah mezi váhou kódového slova a lineární závislostí vektorà tvo²ících sloupce matice H. Tento vztah nám ²íká, ºe pokud existuje nenulové kódové slovo x o váze w(x), potom v p²ísluτné matici H existuje w(x) lineárn╪ závisl∞ch sloupcà - tvrzení T4.1. Uvedená závislost je pochopiteln╪ netriviální.
Dàkaz tohoto tvrzení je snadn∞ a vychází z toho, ºe je-li slovo x kódové, potom má nulov∞ syndrom, coº màºeme zapsat ve tvaru ?j=1n hij*xj = (0,0,...,0). Z této lineární kombinace sloupcà matice H màºeme dále vynechat vτechny vektory, které mají p²ísluτné koeficienty xj nulové; tím nám zbude rovnice, která ²íká, ºe n╪jak∞ch w(x) sloupcà z matice H je lineárn╪ závisl∞ch. Vzhledem k tomu dále, ºe uvaºujeme pouze nenulová slova x, víme, ºe tato závislost je netriviální - dàkaz P4.1.
Práv╪ uvedené tvrzení, které nás upozorσuje na jistou souvislost mezi váhou kódového slova a lineární závislostí sloupcà v matici H, nás spolu s T3.4 p²ímo vybízí k formulaci následujícího st╪ºejního tvrzení: Lineární kód ? s kontrolní maticí H má minimální kódovou vzdálenost dmin(?) = d práv╪ tehdy, kdyº d p²edstavuje nejmenτí celé ƒíslo, pro které v matici H existuje d lineárn╪ závisl∞ch sloupcà - tvrzení T4.2.
Dàkaz tohoto tvrzení je pom╪rn╪ snadn∞, avτak pon╪kud delτí, takºe si jej zde p²edvád╪t nebudeme. Kdo chce, màºe si jej zkusit jako drobné cviƒení. Pro nás je te╘ dàleºité, ºe jeho pomocí màºeme v naτem p²ípad╪, kdy hledáme kód opravující jednonásobné chyby (dmin(?) = 3), formulovat ihned následující pomocné tvrzení: lineární kód j s kontrolní maticí H má minimální kódovou vzdálenost dmin(?) = 3 práv╪ tehdy, kdyº libovolná dvojice sloupcà z matice H je lineárn╪ nezávislá a souƒasn╪ v H existuje n╪jaká trojice lineárn╪ závisl∞ch sloupcà - tvrzení T4.3.
Konstrukce matice H
Z p²edchozího v∞kladu víme, ºe pro náτ kód hledáme takovou kontrolní matici H typu [n-k,n], jejíº parametry odpovídají tvrzení T4.3. Víme dále, ºe sloupce této matice jsou tvo²eny n-k rozm╪rn∞mi aritmetick∞mi vektory, kter∞ch je celkem n. Odtud jiº dostáváme p²ímo návod na sestrojení matice H v∞b╪rem vhodn∞ch n-k rozm╪rn∞ch vektorà.
Vektory pro sloupce matice H budeme vybírat z vektorového prostoru V(r,q). Pro p²ehledn╪jτí zápis jsme si zavedli prom╪nnou r = (n-k), kterou si oznaƒíme jako ²ád hledaného kódu - definice D4.1. Podot∞kám, ºe zavedení vektorového prostoru V(r,q) pro sloupce H není samo-úƒelnou snahou o zesloºit╪ní celého v∞kladu. Vzhledem k tomu, ºe se tu bavíme o jejich lineární závislosti a nezávislosti, nám uº bohuºel nestaƒí chápat je jako pouhé q-nární posloupnosti délky r.
Zam╪²me se nyní na postup, jak∞m z V(r,q) vybereme pot²ebn∞ch n po dvou nezávisl∞ch vektorà. První, co víme, je, ºe v ºádném kroku nesmíme vybrat nulov∞ vektor - ten je totiº s libovoln∞m jin∞m vektorem lineárn╪ závisl∞. Krom╪ této podmínky máme p²i v∞b╪ru prvního sloupce jiº naprosto "volné" ruce. Vybereme tudíº libovoln∞ nenulov∞ vektor v1?V(r,q). V dalτím kroku jsme uº omezeni - màºeme vybrat pouze takov∞ vektor v2?V(r,q), kter∞ není násobkem v1 (jinak by byly v1 a v2 lineárn╪ závislé, coº nechceme). P²i v∞b╪ru v3 si pak musíme stejn∞m zpàsobem dávat pozor na to, aby nebyl násobkem ani jednoho z vektorà v1 a v2. Budeme-li tímto zpàsobem postupovat aº do konce, potom máme jistotu, ºe libovolná dvojice z námi vybran∞ch n vektorà je lineárn╪ nezávislá, takºe je màºeme pouºít jako sloupce matice H. Poznamenejme, ºe se dá snadno dokázat, ºe na takto vybrané mnoºin╪ vektorà existuje taková trojice, která lineárn╪ závislá je - tím jsme splnili i druhou ƒást podmínky v T4.3.
Podle tvrzení T4.3 jsme práv╪ obdrºeli kontrolní matici H kódu, kter∞ màºeme pouºít na opravu jednonásobn∞ch chyb. Zatím vτak nejsme se vτím úpln╪ hotovi; jeτt╪ nám zb∞vá urƒit, jaké má tento kód vlastn╪ parametry. Víme o n╪m sice, ºe je typu (n,k), ale konkrétní hodnoty t╪chto prom╪nn∞ch zatím neznáme. Snadno se màºeme p²esv╪dƒit, ºe parametry námi navrhovaného kódu nemohou b∞t zcela libovolné. Pokud bychom nap²íklad zvolili p²íliτ velkou hodnotu n, která mj. také urƒuje poƒet sloupcà matice H, mohlo by se nám snadno stát, ºe nebudeme z prvkà prostoru V(r,q) schopni vybrat pot²ebn∞ poƒet po dvou nezávisl∞ch vektorà.
Schopnost v∞b╪ru p²ísluτn∞ch vektorà pro sloupce H je v této chvíli prakticky jedin∞m omezením, které musíme respektovat. Pokusme se proto vyjád²it hodnoty (n,k) pomocí ²ádu r. Z obecné teorie lineárních kódà víme, ºe poƒet informaƒních bità k màºeme vyjád²it jako k = n-r. Námi zaveden∞ ²ád r totiº reprezentuje poƒet kontrolních bità kódov∞ch slov. Zb∞vá nám jeτt╪ urƒit hodnotu n. Tu vyjád²íme jako maximální poƒet po dvou nezávisl∞ch vektorà, které jsme schopni vybrat z prostoru V(r,q), následujícím vzorcem: n = (qr-1)/(q-1). Odvození uvedeného vzorce je v podstat╪ "jen" mal∞m procviƒením kombinatoriky, takºe se jím zde nebudeme hloub╪ji zab∞vat.
Hammingàv kód
Práv╪ jsme ukázali, jak∞m zpàsobem màºeme sestrojit konkrétní lineární kód, kter∞ je schopen opravovat jednonásobné chyby a jehoº typ (n,k) je závisl∞ na volitelném parametru, kter∞ jsme oznaƒili jako ²ád daného kódu. Obdobn∞m zpàsobem, jak∞ jsme si tu dnes ukázali, postupoval (moºná s malinko odliτn∞m matematick∞m aparátem) p²ed rovn∞mi padesáti lety i Dr. Hamming. Podle n╪ho se celá rodina lineárních kódà, které jsou konstruovány práv╪ popsan∞m zpàsobem, oznaƒuje jako takzvané Hammingovy kódy.
Jeτt╪ neº se pustíme do dalτí ƒásti v∞kladu, uvedeme si n╪kolik základních vlastností Hammingov∞ch kódà, jejichº návrh jsme si práv╪ popsali. Zaƒneme t²eba hned jejich definicí: q-nární Hammingàv kód ²ádu r je lineární kód typu (n,k), kde n = (qr-1)/(q-1) a k = n-r, s kontrolní maticí H typu [r,n], jejíº sloupce tvo²í po dvou nezávislé vektory z prostoru V(r,q). Minimální kódová vzdálenost vτech Hammingov∞ch kódà je rovna t²em - definice D4.2.
Pokud bychom n╪kdy zapomn╪li postup, jak∞m jsme Hammingovy kódy odvodili, postaƒí nám pamatovat si jejich definici - z té bychom m╪li b∞t schopni dan∞ kód celkem snadno vytvo²it.
Poznamenejme, ºe aƒkoliv uveden∞ popis konstrukce a vlastní definice Hammingov∞ch kódà poƒítá s libovolnou abecedou kódov∞ch slov, v praxi se nejƒast╪ji setkáme s binárními (q = 2) zástupci t╪chto kódà. Tím se nám zjednoduτí v∞razy pro n a k následovn╪: n = 2r-1, k = n-r = 2r-1-r.
Na obrázku vidíme p²íklad binárního Hammingova kódu ²ádu r = 3, kter∞ je podle uveden∞ch vztahà typu (7,4). Generující matice tohoto kódu byla podle tvrzení T3.6 vypoƒtena z matice H, která byla nejd²íve upravena na tvar H = (-BT | En-k). Zde stojí za zmínku fakt, ºe po celou dobu naτich úvah nad konstrukcí Hammingova kódu jsme ani jednou nepouºili matici G - místo toho jsme se op²eli pouze o matici H. Tento fakt je moºné brát jako ukázku toho, ºe matice G a H poskytují do urƒité míry nezávisl∞ pohled na definici hledaného kódu, a je jen otázkou konkrétní situace, kter∞ pohled se nám hodí víc. Jak uvidíme dále, hraje v p²ípad╪ Hammingov∞ch kódà matice H prim.
Dalτí základní, avτak zajímavou vlastností Hammingov∞ch kódà je, ºe jsou perfektní ve smyslu tvrzení T2.4 - tvrzení T4.4. Dàkaz této vlastnosti je moºné provést jednoduch∞m dosazením do uvedené nerovnice a ov╪²ením, ºe pro dvojice ƒísel (n,k) odvozen∞ch od libovolného ²ádu r podle D4.2 p²echází tato nerovnice v rovnici, coº znamená, ºe kaºd∞ Hammingàv kód je perfektní neboli má nejmenτí moºnou nadbyteƒnost.
Detekce a oprava chyb
Vzhledem k tomu, ºe kaºd∞ Hammingàv kód je p²edevτím kódem lineárním, platí pro detekci a opravu vτechna obecná pravidla, která jsme uvedli v minulém díle. Vzhledem k jist∞m specifick∞m vlastnostem Hammingov∞ch kódà màºeme tato obecná pravidla navíc upravit do takové podoby, ve které jsou v praxi snáze realizovatelná.
Pokud jde o zpàsob detekce chyb, zde se nic nezm╪nilo - nejjednoduττí a nejosv╪dƒen╪jτí metodou zàstává i nadále indikace chyby na základ╪ nenulového syndromu p²ijatého slova. Hlavní cíl nasazení Hammingov∞ch kódà vτak bude patrn╪ v aplikacích, které budou provád╪t nejen detekci chyb, ale které budou tyto chyby rovnou i opravovat. Proto nás budou zajímat hlavn╪ postupy pro opravu chyb.
Pon╪kud t╪ºkopádn∞ zpàsob opravy chyb, kter∞ jsme si uvedli minule, màºeme v p²ípad╪ Hammingov∞ch kódà modifikovat do p²ijateln╪jτí podoby, a to díky tomu, ºe se zde zajímáme pouze o opravu jednonásobn∞ch chyb.
Θvaha, kterou pouºijeme pro modifikaci obecné metody, vychází op╪t ze studia chování operace pro v∞poƒet syndromu, kterou jsme pouºili uº b╪hem samotného návrhu Hammingov∞ch kódà. P²edpokládejme, ºe jsme vyslali kódové slovo c a místo n╪ho jsme p²ijali n╪jaké slovo x = c+e, které je zatíºeno chybov∞m vektorem e. Víme, ºe hodnota syndromu potom odpovídá p²ímo chybovému vektoru, neboli s = HeT. Jak jsme si dnes ukázali, operace typu H?T vytvá²ejí lineární kombinace sloupcà matice H. T╪chto kombinací se p²itom "aktivn╪ úƒastní" tolik sloupcà, jaká je váha vektoru??? Dále víme, ºe jsme schopni opravovat pouze jednonásobné chyby, coº znamená, ºe w(e) ? 1. To znamená, ºe do zmín╪né lineární kombinace nevstupuje bu╘ ºádn∞ sloupec matice H (v takovém p²ípad╪ jsme p²ijali kódové slovo), nebo pouze jeden tento sloupec. To znamená, ºe pokud jsme p²ijali slovo zatíºené chybou, potom bude jeho syndrom p²ímo odpovídat sloupci, jehoº umíst╪ní v matici H udává p²ímo pozici chybného znaku v p²ijatém slov╪.
Práv╪ popsané pozorování je moºné vyuºívat mnoha ràzn∞mi zpàsoby. Bu╘to se spokojíme s uº beztak p²íjemn∞m faktem, ºe syndromy p²ímo odpovídají sloupcàm matice H na p²ísluτn∞ch pozicích, anebo se budeme snaºit z tohoto faktu získat maximum. Jako p²íklad si màºeme uvést t²eba binární Hammingàv kód s kontrolní maticí uvedenou na obrázku HW implementace tohoto kódu. Zde jsme provedli takovou permutaci sloupcà, ºe kaºd∞ sloupec zároveσ p²edstavuje binární zápis své vlastní pozice v matici H (vektor (0,0,1) je na první pozici, (1,0,1) na páté atd.). Díky této úprav╪ nyní nenulov∞ syndrom p²ijatého slova p²ímo urƒuje binární zápis pozice, na které k chyb╪ doτlo. Poznamenejme, ºe tato permutace byla provedena na úkor toho, ºe matice H jiº není ve tvaru (-BT | En-k), coº nám ale v tomto p²ípad╪ nevadí.
HW realizace
Zaƒneme nap²íklad konstrukcí kodéru neboli obvodovou realizací p²ísluτného zobrazení ?. Zde màºeme bu╘to vyjít z p²ísluτné generující matice G, anebo staƒí vyuºít toho, co víme o matici H. Jak jsme si uvedli minule, reprezentuje matice H koeficienty soustavu homogenních rovnic, jejichº ²eτení p²edstavuje podprostor vτech kódov∞ch slov. Kódování vysílan∞ch vektorà je proto moºné provád╪t i tak, ºe kaºdému odeslanému vektoru p²i²adíme vºdy jedno konkrétní ²eτení uvedené soustavy rovnic. Hodnost této soustavy je p²itom n-k, coº p²esn╪ odpovídá naτí situaci, kdy si k prom╪nn∞ch volíme (ty poloºíme p²ímo rovny vstupnímu vektoru) a n-k prom╪nn∞ch potom vypoƒteme na základ╪ p²edepsan∞ch rovnic.
Cel∞ postup bude srozumiteln╪jτí, jestliºe si p²ísluτné rovnice dané maticí H vypíτeme tak, jak je uvedeno na obrázku. Zde vidíme, ºe nejsnazτím postupem pro v∞poƒet p²ísluτného kódového slova je nejprve podle vstupního slova (z) stanovit v∞stupní hodnoty na pozicích (3,5,6,7) jako: x3 = z1, x5 = z2, x6 = z3 a x7 = z4 a podle uveden∞ch rovnic potom dopoƒítat pozice (1,2,4) jako: x1 = x3 + x5 + x7, x2 = x3 + x6 + x7, x4 = x5 + x6 + x7.
Prakticky je cel∞ postup kódování uveden na obrázku. Poznamenejme, ºe logické obvody oznaƒené znakem ? znaƒí logické ƒleny XOR, jejichº pouºití vychází z algebraick∞ch vlastností t╪lesa Z2.
P²i dekódování p²ijatého slova je t²eba nejprve urƒit jeho syndrom. Pro tento úƒel se pouºije hardwarová realizace rovnic, které vzniknou rozepsáním operace HxT. Abychom docílili p²ehlednosti a jednoduchosti naτeho schématu, zahrnuli jsme v∞poƒet syndromu do samostatného bloku oznaƒeného jako SYND. Vzhledem k tomu, jak jsme si uspo²ádali matici H, dostáváme na v∞stupu obvodu SYND bu╘ nulu (v takovém p²ípad╪ jsme p²ijali kódové slovo), anebo zde obdrºíme p²ímo ƒíselnou pozici místa, kde doτlo k chyb╪. Vzhledem k tomu, ºe pracujeme nad Z2, provedeme opravu této chyby jednoduτe op╪t pomocí "naxorování" jedniƒkového bitu na p²ísluτnou pozici. Tuto pozici snadno urƒíme pomocí dekodéru jedna z n, kter∞ aplikujeme na v∞stup obvodu SYND.
V╪nujme se nyní ponauƒením, které nám m╪l tento p²íklad poskytnout. Díky tomu, ºe jsme se striktn╪ nedrºeli podmínky na tvar matice H, mohli jsme provést takovou permutaci jejích sloupcà, která nám umoºnila pom╪rn╪ snadnou realizaci obvodu dekodéru. Provedená permutace vτak m╪la i své stinné stránky: podle T3.6 jsme nemohli elegantn╪ urƒit matici G a dále v∞sledn∞ kód nebyl souvisle systematick∞. Nakonec se vτak ukázalo, ºe ani jedna z t╪chto v╪cí nám nevadila, nebo£ bez pouºití matice G jsme se obeτli zcela, a pokud jde o souvislou systematiƒnost, práv╪ jsme si ukázali, ºe pro HW realizaci, kde není problém provád╪t libovolné permutace p²enáτen∞ch slov, bohat╪ postaƒuje podmínka na systematiƒnost dle D2.1.
Záv╪r
Dnes jsme se podrobn╪ podívali na nejznám╪jτí zástupce lineárních kódà, a to na Hammingovu rodinu ECC. Na p²íkladu t╪chto kódà jsme si dále rozτí²ili naτe obecné znalosti lineárních kódà a ukázali jsme si, jak se tyto v╪domosti v praxi aplikují p²i návrhu konkrétních druhà kódování. Dále jsme si zde ukázali hardwarovou realizaci binárního Hammingova kódu, kde jsme upozornili na jeho specifické vlastnosti, které je moºné vyuºít pro jeho efektivní implementaci.
V p²íτtím díle nás ƒeká popis Golayov∞ch kódà, coº je dalτí nejznám╪jτí rodina lineárních kódà.
Tomáτ Rosa (tomas.rosa@decros.cz)
Literatura:
[ROMA92] Roman, S.: Coding and Information Theory, Springer-Verlag, 1992.
