Hammingův kód: Detekce a oprava chyb s příklady

Co je to chyba?

Během komunikace může dojít k poškození přenášených dat. Je pravděpodobné, že bude ovlivněna vnějším hlukem nebo jinými fyzickými poruchami. V takové situaci nemohou být vstupní data stejná jako výstupní data. Tento nesoulad se nazývá „Chyba“.

Chyby dat mohou vést ke ztrátě důležitých nebo zabezpečených dat. Většina datových přenosů v digitálních systémech bude probíhat ve formě „bitového přenosu“. I malá změna může ovlivnit výkon celého systému. Pokud se v datové sekvenci změní 1 na 0 nebo se 0 změní na 1, nazývá se to „bitová chyba“.

Typy chyb

Při přenosu dat od odesílatele k příjemci se vyskytují především tři typy bitové chyby.

• Jednotlivé bitové chyby
• Více bitových chyb
• Shlukové chyby

Jednobitové chyby

Změna provedená v jednom bitu v celé datové sekvenci se nazývá „chyba jednoho bitu“. Výskyt jednobitové chyby však není tak častý. Navíc k této chybě dochází pouze v paralelním komunikačním systému, protože data jsou přenášena bitově v jedné lince. Proto existuje více šancí, že jedna linka může být hlučná.

Více bitových chyb

V datové sekvenci, pokud dojde ke změně ve dvou nebo více bitech datové sekvence z vysílače na přijímač, je to známé jako „vícebitové chyby“.

Tento typ chyby se většinou vyskytuje v sítích sériové i paralelní datové komunikace.

Burst Errors

Změna sady bitů v datové sekvenci je známá jako „Burst error“. Tento typ datové chyby se počítá od změny prvního bitu po poslední změnu bitu.

Co je detekce chyb a oprava chyb?

V digitálním komunikačním systému se chyba přenese z jednoho komunikačního systému do druhého. Pokud tyto chyby nebudou zjištěny a opraveny, budou data ztracena. Pro efektivní komunikaci by se měla systémová data přenášet s vysokou přesností. To se provede tak, že se nejprve identifikují chyby a oni je opraví.

Detekce chyb je způsob detekce chyb, které jsou přítomny v datech přenášených z vysílače do přijímače v datovém komunikačním systému.

Zde můžete použít redundantní kódy k nalezení těchto chyb přidáním k datům, když jsou přenášena ze zdroje. Tyto kódy se nazývají „Kódy zjišťování chyb“.

Existují tři typy kódů detekce chyb:

• Kontrola parity
• Kontrola cyklické redundance (CRC)
• Longitudinal Redundancy Check (LRC)

Kontrola parity

• To je také známé jako kontrola parity.
• Má nákladově efektivní mechanismus pro detekci chyb.
• V této technice je redundantní bit známý jako paritní bit. Je připojen ke každé datové jednotce. Celkový počet 1s v jednotce by měl být sudý, což je známé jako paritní bit.

Kontrola podélné redundance

V této technice detekce chyb je blok bitů organizován v tabulkovém formátu. Metoda LRC vám pomůže vypočítat paritní bit pro každý sloupec. Sada této parity je také odeslána spolu s původními daty. Blok parity vám pomůže zkontrolovat redundanci.

Kontrola cyklické redundance

Kontrola cyklické redundance je sekvence redundantních, která musí být připojena na konec jednotky. Proto by se výsledná datová jednotka měla stát dělitelnou druhým, předem určeným binárním číslem.

V cíli je třeba příchozí data vydělit stejným číslem. V případě, že není žádný zbytek, pak se datová jednotka považuje za správnou a je přijata. V opačném případě to znamená, že datová jednotka je při přenosu poškozena, a proto musí být odmítnuta.

V Hammingově kódu zdroj kóduje zprávu přidáním redundantních bitů do zprávy. Tyto redundantní bity jsou většinou vkládány a generovány na určitých pozicích ve zprávě, aby bylo dosaženo procesu detekce chyb a opravy.

Historie Hammingova kódu

• Hammingův kód je technika vytvořená RWHammingem pro detekci chyb.
• Hammingův kód by měl být aplikován na datové jednotky libovolné délky a používá vztah mezi daty a redundantními bity.
• Pracoval na problému metody opravy chyb a vyvinul stále výkonnější řadu algoritmů nazývaných Hammingův kód.
• V roce 1950 publikoval Hammingův kód, který se dnes široce používá v aplikacích, jako je paměť ECC.

Aplikace Hammingova kódu

Zde jsou některé běžné aplikace používání Hammingova kódu:

• Satelity
• Počítačová paměť
• modemy
• PlasmaCAM
• Otevřete konektory
• Stínící drát
• Vestavěný procesor

Výhody Hammingova kódu

• Metoda Hammingova kódu je účinná v sítích, kde jsou datové toky uvedeny pro jednobitové chyby.
• Hammingův kód poskytuje nejen detekci bitové chyby, ale také vám pomáhá odsadit chybu obsahující bit, aby mohla být opravena.
• Snadné použití Hammingových kódů je činí nejvhodnějšími pro použití v paměti počítače a opravou jediné chyby.

Nevýhody Hammingova kódu

• Jednobitová detekce chyb a opravný kód. Je-li však zjištěna chyba více bitů, může výsledek vést k jinému bitu, který by měl být změněn. To může způsobit další chybování dat.
• Algoritmus Hammingova kódu může vyřešit pouze problémy s jednotlivými bity.

Jak zakódovat zprávu v Hammingově kódu

Proces použitý odesílatelem ke kódování zprávy zahrnuje následující tři kroky:

• Výpočet celkového počtu redundantních bitů.
• Kontrola pozice nadbytečných bitů.
• Nakonec výpočet hodnot těchto redundantních bitů.

Když jsou výše uvedené redundantní bity vloženy do zprávy, je odeslána uživateli.

Krok 1) Výpočet celkového počtu redundantních bitů.

Předpokládejme, že zpráva obsahuje:

• n– počet datových bitů
• p – počet redundantních bitů, které jsou k němu přidány, takže np může indikovat alespoň (n + p + 1) různé stavy.

Zde (n + p) znázorňuje umístění chyby v každé z (n + p) bitových pozic a jeden stav navíc označuje žádnou chybu. Protože p bitů může znamenat 2^p státy, 2^p musí být alespoň rovno (n + p + 1).

Krok 2) Umístění nadbytečných bitů na jejich správnou pozici.

Redundantní bity p by měly být umístěny na bitových pozicích o mocninách 2. Například 1, 2, 4, 8, 16 atd. Označují se jako p₁ (na pozici 1), str₂ (na pozici 2), str₃ (na pozici 4) atd.

Krok 3) Výpočet hodnot redundantního bitu.

Redundantní bity by měly být paritní bity, takže počet 1s je buď sudý nebo lichý.

Dva typy parity jsou?

• Celkový počet bitů ve zprávě je vytvořen sudý se nazývá sudá parita.
• Celkový počet bitů ve zprávě je lichý se nazývá lichá parita.

Zde musí být veškerý redundantní bit, p1, vypočten jako parita. Měl by pokrývat všechny bitové pozice, jejichž binární reprezentace by měla zahrnovat 1 na 1. pozici s výjimkou pozice p1.

P1 je paritní bit pro každý datový bit na pozicích, jejichž binární reprezentace obsahuje 1 na méně důležité pozici, která nezahrnuje 1 Like (3, 5, 7, 9, ….)

P2 je paritní bit pro každý datový bit na pozicích, jejichž binární reprezentace zahrnuje 1 na pozici 2 zprava, nezahrnuje 2 Like (3, 6, 7, 10, 11,…)

P3 je paritní bit pro každý bit na pozicích, jejichž binární reprezentace obsahuje 1 na pozici 3 zprava nezahrnuje 4 Like (5-7, 12-15,…)

Dešifrování zprávy v Hammingově kódu

Přijímač přijímá příchozí zprávy, které vyžadují provedení přepočtů k nalezení a opravě chyb.

Proces přepočtu se provádí v následujících krocích:

• Počítání počtu nadbytečných bitů.
• Správné umístění všech nadbytečných bitů.
• Kontrola parity

Krok 1) Počítání počtu nadbytečných bitů

Pro kódování můžete použít stejný vzorec, počet redundantních bitů

2^p ? n + p + 1

Zde počet datových bitů a p je počet redundantních bitů.

Krok 2) Správné umístění všech nadbytečných bitů

Zde je p redundantní bit, který se nachází na bitových pozicích s mocninami 2, například 1, 2, 4, 8 atd.

Krok 3) Kontrola parity

Paritní bity je třeba vypočítat na základě datových bitů a redundantních bitů.

p1 = parita (1, 3, 5, 7, 9, 11…)

p2 = parita (2, 3, 6, 7, 10, 11…)

p3 = parita (4-7, 12-15, 20-23…)

Shrnutí

• Během komunikace může dojít k poškození přenášených dat
• Tři typy bitové chyby jsou 1) Single Bit Errors 2) Multiple Bit Error 3) Burst Bit error
• Změna provedená v jednom bitu v celé datové sekvenci se nazývá „chyba jednoho bitu“.
• V datové sekvenci, pokud dojde ke změně ve dvou nebo více bitech datové sekvence z vysílače na přijímač, je to známé jako „vícebitové chyby“.
• Změna sady bitů v datové sekvenci je známá jako „Burst error“.
• Detekce chyb je metoda detekce chyb, které jsou přítomny v datech přenášených z vysílače do přijímače v datovém komunikačním systému.
• Tři typy kódů detekce chyb jsou 1) Kontrola parity 2) Kontrola cyklické redundance (CRC) 3) Kontrola podélné redundance (LRC)
• Hammingův kód je linkový kód, který je užitečný pro detekci až dvou okamžitých bitových chyb. Je schopen jednobitových chyb.
• Hammingův kód je technika vytvořená RWHammingem pro detekci chyb.
• Běžné aplikace využívající Hammingův kód jsou satelitní počítačová paměť, modemy, vestavěný procesor atd.
• Největší výhoda metody Hammingova kódu je účinná v sítích, kde jsou datové toky dány pro jednobitové chyby.
• Největší nevýhodou metody Hammingova kódu je, že dokáže vyřešit pouze problémy s jednotlivými bity.
• Proces šifrování a dekódování zprávy můžeme provést pomocí hammingova kódu.