Čo je Hammingov kód: História, práca a jej aplikácie

Čo je Hammingov kód: História, práca a jej aplikácie

V digitálnych systémoch sa prenášané údaje pre komunikácia sa môže poškodiť v dôsledku vonkajšieho hluku a iných fyzických porúch. Ak sa prenášané údaje nezhodujú s danými vstupnými údajmi, nazýva sa to „chyba“. Chyby údajov môžu vymazať dôležité údaje v digitálnych systémoch. Prenos údajov bude prebiehať vo forme bitov (0 a 1) v digitálnych systémoch. Ak sa zmení ktorýkoľvek z bitov, môže to mať vplyv na výkon celého systému. Ak sa bit „1“ zmení na bit „0“ alebo naopak, nazýva sa to bitová chyba. Existujú rôzne typy chýb ako jednobitové chyby, viacnásobné chyby a chyby prasknutia. V tomto článku sa venujeme korekcii a detekcii chýb a hammingovému kódu.



Čo je detekcia a oprava chýb?

V digitálnej komunikácii dôjde k strate údajov, ak dôjde k chybe v prenose informácií z jedného systému / siete do iného systému / siete. Je preto dôležité vyhľadávať a opravovať chyby. Nejaká chyba detekcia a korekčné metódy sa používajú na detekciu a opravu chýb pre efektívnu komunikáciu. Ak sa použijú tieto metódy, údaje sa dajú preniesť s vyššou presnosťou.


Detekcia chýb je definovaná ako metóda použitá na detekciu chýb prenášaných z vysielača / odosielateľa do prijímača v digitálnych systémoch. K údajom sa počas prenosu pridávajú kódy nadbytočnosti, aby sa našli chyby. Nazývajú sa kódy na zisťovanie chýb.



Oprava chyby je oprava údajov prenášaných z vysielača do prijímača. Opravu chyby je možné vykonať dvoma spôsobmi.

Oprava spätnej chyby

Pri tomto type korekcie chyby prijímač požaduje od odosielateľa spätný prenos údajov, ak zistí chybu.



Dopredná oprava chyby

ak dáta prijaté prijímačom nájdu chybu, vykoná kódy na opravu chýb, aby údaje automaticky opravil a obnovil.


Ak existuje „m“ počet dátových bitov a „r“ počet nadbytočných bitov, potom bude kombinácia informácií 2r.

2r> = m + r + 1

Typy kódov detekcie chýb

Chyby v prijatých dátach možno zistiť pomocou 3 typov kódov detekcie chýb. Sú to kontrola parity, kontrola cyklickej redundancie (CRC) a kontrola pozdĺžnej redundancie.

Kontrola parity

Redundantný bit nazývaný paritný bit sa pridá, aby sa počet bitov stal párnym alebo nepárnym v prípade párnej alebo nepárnej parity. Prijímač počíta počet bitov (1) v rámci a pridáva paritný bit. Toto sa nazýva kontrola parity. Ak je počet čísiel 1 v rámci párny, použije sa párna parita pridaním bitu „1“ s nulovou hodnotou. Podobne z počtu 1 je nepárnych, potom sa nepárna parita použije pridaním bitu s hodnotou „1“.

Detekcia chýb

detekcia chýb

Preto sa používa na zabezpečenie toho, aby rámec / dátum prijatý prijímačom zo zdroja nebol poškodený. Pri tomto type detekcie chýb by počet jednotiek 1 mal byť dokonca v prijatom rámci. Je to veľmi lacné z hľadiska všetkých typov detekcie chýb.

Kontrola pozdĺžnej nadbytočnosti (LRC)

ak sú sady / bloky bitov usporiadané, potom je možné na kontrolu paritného bitu v každom rámci použiť metódu LRC. Pomáha poslať sadu paritných bitov spolu s pôvodnými údajmi a skontrolovať nadbytočnosť.

Kontrola cyklickej redundancie

jeho typ sa používa na detekciu údajov / rámcov prijatých zo zdroja, ktoré sú platné alebo nie. Zahŕňa binárne rozdelenie údajov, ktoré sa majú odosielať, a používa polynómy (na generovanie deliteľa). Predtým prenosu , operáciu delenia vykoná odosielateľ na dátach / bitoch / rámci za účelom výpočtu zvyšku.

Kontrola cyklickej redundancie

kontrola cyklickej redundancie

Počas prenosu skutočných údajov od odosielateľa pridá zvyšok na koniec skutočných údajov. Kombinácia skutočných údajov a zvyšku sa nazýva kódové slovo. Údaje sa prenášajú vo forme kódových slov. Ak v tomto procese dôjde k poškodeniu údajov, prijímač ich odmietne, inak ich prijme.

Čo je Hammingov zákonník?

Hammingov kód je definovaný ako lineárny kód, ktorý sa používa v procese detekcie chýb až na 2 stredné chyby. Je tiež schopný detegovať jednobitové chyby. V tejto metóde sú nadbytočné bity pridané k dátam / správe odosielateľom na zakódovanie údajov. Na vykonanie detekcie a korekcie chýb sa tieto nadbytočné bity pridajú na určité pozície pre proces korekcie chyby.

Hammingov kód

hammingov kód

História Hammingových kódov

V roku 1950 vynašiel Richard W. hamming Hammingove kódy na detekciu a opravu chýb v dátach. Po vývoji počítačov s vyššou spoľahlivosťou zaviedol hammovacie kódy pre kódy na opravu 1-chyby a neskôr rozšíril až na 2-chybové kódy. Hammingove kódy sa vytvárajú, pretože kontrola parity nedokáže zistiť a opraviť chyby v dátach. Hammingove kódy sa vkladajú do ľubovoľnej dĺžky dát medzi skutočnými dátami a nadbytočnými bitmi. Vyvinul rad algoritmov na prácu s problémami metód korekcie chýb a tieto kódy sa často používajú v pamäti ECC.

Proces kódovania správy pomocou Hammingovho kódu

Proces kódovania správy pomocou hammingového kódu odosielateľom obsahuje 3 kroky.

Krok 1: Prvým krokom je výpočet počtu nadbytočných bitov v správe

  • Ak napríklad správa obsahuje „n“ počet bitov a do správy sa pridá „p“ počet nadbytočných bitov, potom „np“ označuje (n + p + 1) rôzne stavy.
  • Kde (n + p) predstavuje miesto chyby v každej bitovej polohe
  • 1 (stav navyše) predstavuje žiadnu chybu.
  • Pretože „p“ označuje 2 ^ p (2p) stavy, ktoré sa rovnajú (n + p + 1) stavom.

Krok 2: Umiestnite nadbytočné bity do presnej / správnej polohy

'P' bity sú vložené do bitových pozícií, ktoré sú silou 2 ako 1, 2, 4, 8, 16 atď. Tieto bitové pozície sú označené ako p1 (pozícia 1), p2 (pozícia 2), p3 (pozícia 4) atď.

Krok 3: Vypočítajte hodnoty nadbytočných bitov

  • Tu sa paritné bity používajú na výpočet hodnôt nadbytočných bitov.
  • Paritné bity môžu v správe označiť číslo 1 ako párne, alebo nepárne.
  • Ak je celkové číslo 1 v správe párne, použije sa párna parita
  • Ak je celkové číslo 1 v správe nepárne, použije sa nepárna parita.

Proces dešifrovania správy v Hammingovom kóde

Proces dešifrovania správy prijatej od odosielateľa prijímateľom pomocou hammingovho kódu zahrnuje nasledujúce kroky. Tento proces nie je nič iné ako prepočet na zistenie a opravu chýb v správe.

Krok 1: Spočítajte počet nadbytočných bitov

Vzorec na kódovanie správy pomocou nadbytočných bitov je,

2p≥ n + p + 1

Krok 2: opravte polohy všetkých nadbytočných bitov

„P“ číslo nadbytočných bitov je umiestnené v bitových pozíciách sily 2, napríklad 1,2,4,8,16,32 atď.

Krok 3: kontrola parity (nepárna parita a párna parita)

Paritné bity sa počítajú na základe počtu číslic 1 v dátových bitoch a nadbytočných bitoch.

Napríklad

Parita p1 by bola 1, 3, 5, 7, 9, 11,…

Parita p2 by bola 2, 3, 6, 7, 10, 11,…

Parita p3 by bola 4–7, 12–15, 20–23,…

Výhody Hammingovho zákona

Hlavná výhoda použitia hammingového kódu je nákladovo efektívna, ak dátový tok obsahuje jednobitové chyby.

  • Môže poskytovať detekciu chýb a tiež označuje bit, ktorý obsahuje chybu korekcie.
  • Hammingove kódy sa veľmi ľahko a najlepšie používajú v pamäti počítača a pri jednobitových opravách a detekcii chýb.

Nevýhody Hammingovho kódu

  • Najlepšie je iba na jednobitovú opravu a detekciu chýb. Ak dôjde k chybe viacerých bitov, môže sa poškodiť celá.
  • Hammingov kódový algoritmus dokáže vyriešiť iba jednobitové chyby.

Aplikácia Hammingových kódov

Hammingove kódy sa používajú v

  • Výpočtový
  • Telekomunikácie
  • Kompresia dát
  • Riešenie hlavolamov a turbo kódov
  • Satelity
  • Plazmová CAM
  • Tienené drôty
  • Modemy
  • Pamäť počítača
  • Otvorte konektory
  • Vložené systémy a procesor

Časté otázky

1). Môže Hammingov kód zistiť 2-bitové chyby?

Hammingove kódy dokážu detekovať a opraviť až 2-bitové chyby v dátovom toku

2). Ako opravíte Hammingov kód?

Hammingove kódy sa vkladajú do ľubovoľnej dĺžky údajov medzi skutočnými údajmi a nadbytočnými bitmi. Tieto kódy sú miesta s minimálnou vzdialenosťou 3 bitov

3). Aký je paritný kód?

Paritný kód alebo paritný bit pridáva bit do prijatého rámca (údaje obsahujú čísla 1 a 0), aby celkový počet bitov (1) bol párny alebo nepárny.

4). Aká je Hammingova vzdialenosť medzi údajmi?

Hammova vzdialenosť medzi dvoma rôznymi dátovými tokmi rovnakej dĺžky nie je číslo 1.

Hammanovu vzdialenosť medzi dvoma dátovými reťazcami rovnakej dĺžky je možné vypočítať pomocou operácie XOR.

Napríklad a = 11011001

b = 10011101

Hammingovu vzdialenosť je možné vypočítať ako,

11011001 ⊕ 10011101 = 01000100 (počet 1 bitov sú 2)

Hammingova vzdialenosť označuje počet číslic 1 vo výslednom toku údajov

Takže d (11011001, 10011101) = 2

Podobne 010 ⊕ 011 = 001, d (010, 011) = 1.

5). Je Hammingov kód cyklický?

Áno, Hammove kódy sú ekvivalentné cyklickým kódom, ktoré možno použiť ako kódy na zisťovanie chýb.

Jedná sa teda o korekciu a detekciu chýb, typy detekcie chýb, Hammingove kódy , proces šifrovania a dešifrovania správy pomocou Hammových kódov, aplikácie Hammových kódov, výhody a nevýhody Hammingových kódov. Je tu pre vás otázka: „Aké sú možnosti detekcie a opravy chýb?“