Už kdysi dávno jsem psal o "robotické blbuvzdornosti" tedy o tom, že i do malinkatých robotů je dobré vestavět jisté ochranné prvky, zejména tehdy pokud to nestojí moc práce ani peněz.
Jednou ze součástí takové blbuvzdornosti je spolehlivost posílání dat mezi moduly v robotech. Takže teď odbočím a zopakuju starou větu : KATEGORICKY ZAKAZUJU POUŽÍVAT I2C SBĚRNICI PRO DŮLEŽITÁ DATA. Kdysi jsem doporučoval používat diferenciální sběrnice RS485, CanBus, Robbus, USB, Ethernet atd. Vtip je v tom, že pokud máme i přes použitou sběrnici jsté množství chyb v doručených datech - je čas začít uvažova zda místo surových dat poslaných po sběrnici není čas používat "samoopravné kódy".
Takže přestavte si, že posíláme data poruchovým kanálem - máme celkem 3 možnosti
- vůbec nekontrolujeme správnost - přijmeme vadný paket - robot podle něj jede - škubne a něco rozbije ...
- V datovém paketu máme nějakou kontrolu - paritní bit, kontrolní součet atd.... Takže přijmeme paket - vyloučíme jej jako vadný a čekáme na další, který může být taky vadný, další taky a další ...
- Už při připravě dat pro paket před vysíláním - přidáme "něco navíc" data, která umožní poznat a dokonce i obnovit původní informaci. Pak přijmeme vadný paket, obnovíme jeho data a jedeme dále jakoby se nic nedělo.
Patrně je vám jasné, že samoopravné kódy jsou to nejběžnější kolem nás. Vtip je v tom, že tolik věcí jsme dotlačili až na fyzíkální limity - jako datové toky ve WIFI, kapacitu pevných a flash disků, kapacitu CD/DVD, že chyby v datech na těcho médiích jsou zcela běžné - "ale zákazník to nesmí poznat...."
Takže jsem se kdysi rozhodl, že ovládnu alespoň nějakou formu samoopravného kódovaní, a protože jsem matematický nedouk, tak jsem ovládl jenom tu historicky první a nejjednodušší metodu - což jsou tzv. Hammingovy kódy.
Richard Hamming v roce 1950 zavedl způsob jak výrazně zvýšit spolehlivost děrných štítků a to tím, že ke každým 4 bitům dat přidal 3 bity parity. Jeho 7 bitový kód pak vypadá následovně
| P1 | P2 | D1 | P3 | D2 | D3 | D4 |
Tedy první dva bity jsou parita, pak je jeden datový bit, pak je poslední paritní bit a další tři datové bity.
Malá odbočka k pojmu PARITA. Tedy od pradávných digitálních dob se nejzákladnější kontrola dat dělala tak že k určitému počtu datových bitů se přidal bit navíc - paritní - a jeho hodnota se nastavila tak, aby datový paket měl vždy SUDÝ nebo vždy LICHÝ počet "jedničkových" bitů (proto sudá nebo lichá parita). Pokud tomu tak nebylo bylo jasné, že některý bit se přenosem změnil. Pokud se prohodily vzájemně dva bity - parita zase seděla ačkoliv data byla špatná - ale pravděpodobnost dvou chyb v jednom paketu (bajtu) se považovala za velmi nepravděpodonou.
Paritní bit se spočte prostě tak že uděláte XOR všech datových bitů - výsledek dává SUDOU paritu, pokud výsedek NEGujete dostanete LICHOU paritu.
| / | P1 | P2 | D1 | P3 | D2 | D3 | D4 |
| P1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| P2 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| P3 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
Takže Hammingovy kódy mají 3 paritní bity, které každý počítají paritu z jiné části datového slova ze kterých bitů se počítá který paritní bit máte označeno v tabulce označeno. Tedy pokud XORem budeme počítat jednotlivé paritní bity potom platí
P1 = D1 xor D2 xor D4
P2 = D1 xor D2 xor D3
P3 = D2 xor D3 xor D4
Tak tohle už smrdí maximální černou magií - takže je čas vysvětlovat. Paritní a datové bity jsou totiř rozmístěny tak šikovně, že nám umožňují poznat který bit je špatný. Postup je následující:
- Přijmu datový paket a někam si uložím tři paritní bity.
- Potom si spočtu paritní bity z datových
- Pak tři paritní bity z datového paketu XORuju s vypočtenými paritními bity
- Získám 3 bitové číslo které nabývá hodnot 0-7
- na tuto hodnotu se mohu rovnou dívat jako na pozici chyby - tedy 0 - vše správně 3 - chyba je ve 3 bitu (D1) nebo třeba 4 - chyba je v paritním bitu P3
- takže pokud získám číslo různé od nuly prostě jenom mechanicky XORuju bit na patřičné pozici jedničkou a mám správný paket.
Opět drobní ďáblici v detailech - co když dojde k poruše více než jednoho bitu - pak patrně nepoznám, že i po korekci mám špatný paket.
Toho využívají i technici a nepraktické 7 bitové pakety doplní ještě o jeden paritní bit, který počítá paritu všech 8 bitů - to je tzv Hammingův kód 8/4, který se také nazývá "Single error correcting double error detecting" - tedy jednu chybu opravím dvě chyby poznám.
Jak se pracuje s takovým kódem :
- Dekóduju a opravím bity jako v předchozím postupu
- Pak opravené celé slovo zkontroluju jesti i 4 paritní bit sedí
- Pokud sedí mohu data použít
- Pokud nesedí - je zjevné, že datové slovo bylo poškozeno "beyond repair" (za hranice opravitelnosti) a musím jej vyhodit.
Jak to budeme programovat v praxi ? - nemá smysl smolit s v mikrokontroléru s XORováním bitů takže je dobré:
- Rozdělit odesílaný bajt na 2 4 bitové úseky
- Pro každou možnou 4 bitovou hodnotu mít v tabulce už předem předvypočtenou hodnotu hammingova kódu, který se odešle (je jich jenom 16).
- Při příjmu mít v druhé tabulce předem vypočtenou hodnotu všech 265 hodnot, které mohou přijít spolu s hodnotou jaký 4 bitový "nibble" to vlastně je a u těch kombinací které jsou poškozeny "beyond repair" mít hodnotu třeba 16 - abychom věděli, že tento nibble nesmíme použít.
Osobně jsem používal pro výpočet P1-P3 sudou paritu, ale pro P4 lichou paritu - to proto aby "plochá lajna na lince" tedy hodnoty 00000000 a 11111111 dávaly chybu.
Prográmek v assembleru zase neuvádím (protože se za něj stydím). Místo toho jsem nahrál na ULOŽ.TO excelovskou tabulku, pomocí které jsem si celou věc zkoušel (a vypočetl jsem si pomocí ní obě tabulky do programu). Doporučuju prozkoumat a při trápení se jak to mám udělané - Hammingovy kódy pochopit.
Zbývá už jenom tradiční rada pro brunety : nejsou jenom vysoké kozačky až na stehno - ale jehlové kozačky po kotník a odtamtud černé legíny vedoucí po vašich dlóóóuhých nohách "až k pipně" - taky dovedou chlapem otřást.
Dalík | 5. prosince 2013 v 9:51
Dneska výborný... i když to tak autor asi nezamýšlel, skoro se tu řežu smíchy :D
Teď ještě jaký samoopravný kód vymyslet pro tenhle blogovací systém, aby byly články bez překlepů alespoň v odkazech a tučně zvýrazněných částech - závěrečná "pipna" se mnou taky otřásla :D
Ale abych jenom nerýpal, tak musím říct že "jinak dobrý", a dokonce mě možná autor i pomůže, taky brzo budu řešit nějakou komunikaci.
Pro zajímavost uvádím, že jsem někde četl článek (už bohužel nevím zdroj, ale pokusím se to dohledat), ve kterém se zabývali RAM v počítači a její chybovostí (z hlediska nepoužití ECC, řeč byla o 2GB RAM), a došli k tomu, že v průměru jednou za 1,5 hodiny v ní chybuje nějaký bit. Samozřejmě platí, že čím víc RAM, tím hůře (dnes celkem běžně i 8GB). Poučení je myslím nasnadě - čímů víc RAM a čím důležitější systém, tím spíš RAM s ECC