A kalapálás kódja az előadások összefoglalása a 080201 tanfolyam irányába tartozó levelező tanfolyamokon
3.10 Hamming kód
A legelterjedtebb rendszeres lineáris blokk kód a Hamming kód. Ide tartozik a kódok minimális kódszáma dmin = 3. képes egyetlen hibát kijavítani.
Ha egy kódszót egy kommunikációs csatornán keresztül továbbítanak, egyetlen hibája bármelyik elemében előfordulhat. Az ilyen helyzetek száma. Így annak érdekében, hogy meghatározza, hogy hol a hiba történt, a kombinációk száma a vizsgált elemek 2r nem lehet kevesebb, mint a számos lehetséges hiba helyzetek a kódot és a helyzetet, amikor a hiba nem fordul elő, azaz a. E. egyenlőtlensége
Ebből az egyenlőtlenségből következik az egyes hibák kijavításához szükséges ellenőrzési és információs bitek minimális paritása
A Hamming kód alapparamétereinek kiszámításához beállíthatja az ellenőrző elemek számát r. akkor a n ≤ 2 r-1 kódszavak hossza. és az információelemek száma k = n -r. Az r. n és k értékeket a következő táblázat tartalmazza (3.3. táblázat).
A dmin = 3 kódellenőrző mátrix jellemző jellemzője az, hogy oszlopai eltérő n-nullájú, r hosszúságú kombinációk.
Hamming javasolt helymeghatározás oszlopait ellenőrző mátrix úgy, hogy az i-edik oszlopa a mátrix és a kódszó rangszámot felel meg a bináris ábrázolása i. Ezután az egyetlen hibajavító szindróma bináris ábrázolása annak a bitszámnak, amelyben a hiba történt. Ehhez a teszt biteknek nem lehetnek a kódszó jobb oldalán, hanem olyan pozíciókban, amelyeknek a száma két, azaz 20. 21. 22. ..., 2r-1.
Például r = 3 esetében a Hamming kód ellenőrző mátrixának formája van
A ellenőrző mátrix (k, n) -code Hamming tagjai n = 2r-1 sorok és R oszlopok, és a jelentése bináris kombinációja i. ahol i az ellenőrző mátrix oszlopának száma (a kódkombináció bitje).
Szindróma. amely meghatározza a kód ellenőrzési egyenleteit, megtalálható az u = 0 egyenletből.
Például r = 3 esetén a tesztegyenletek rendszere a következő:
Ezért a csekkszámok (ellenőrzőösszegek) mindkettő
^ Az üzenet kódolásához m. mint ui, ahol i nem egyenlő a hatalommal 2. Az üzenet megfelelő bitjeit veszik, és a 2. fokozatú mutatóbiteket a kódellenőrző rendszerből találjuk. A rendszer minden egyes egyenletében csak egy ellenőrző összeg van.
1. példa Kódoljuk az m = (0 1 1 1) (4, 7) -code Hamming üzenetet.
Az ellenőrzési egyenletek rendszeréből az ellenőrző összegek találhatók:
Így a kódszó a szekvencia (0001111).
A Hamming kód dekódolása a következő séma szerint történik. Meghatározzuk az elfogadott S = y szindrómát, ahol az átültetett ellenőrző kódmátrix; y a kapott vektor. Ha a szindróma nulla vektor, úgy tekinthető, hogy a szó átvitt hibák nélkül, egyébként az értéke a szindróma a bináris reprezentációját kategóriában számát, ahol a hiba történt. Ebben az esetben meg kell változtatnia az értéket egy hibás számjegyen, a számjegyeket balról jobbra számítva, 1-től kezdődően.
2. példa Az üzenet kódolása (4, 7) a Hamming kóddal történik. Az y = (0011111) szekvencia elfogadott. Dekódolja a vett vektort.
Meghatározzuk az elfogadott vektor szindrómáját:
a hiba a harmadik helyen történt.
A hiba javítása a harmadik bitben lévő érték megváltoztatásával
Az átvitt üzenetet dekódoljuk
Generálása egy mátrixot (k, n) -code van Hamming mátrix (k × n), ahol az oszlopok számozott nem fok 2 formában almátrix egységet, és a fennmaradó oszlopok a egyenletek ellenőrző kódot. Egy ilyen mátrix a kódolásban másolja a 2. fokozatú pozíciókban lévő üzenetbiteket, és a kód más pozícióit a check digit számítási rendszer szerint töltse.
3. példa Hamming kód-ellenőrző egyenletek (4, 7) egyike a következő:
Ennek megfelelően a kód generáló mátrixának alakja van
Melyek a kódok a zajcsökkentésre vonatkoznak. Milyen közös jellemzőket jellemeznek?
Miért vezeti be a redundanciát zajvédő kódokká?
Mik a zaj-immunító kódok osztályai?
Melyik kód a blokk zavaró kódokra utal. Mikor kell használni?
Hogyan vannak meghatározva a kiegészítés és a szorzás műveletei a GF (2) bináris szimbólumok területén (a modulo 2 kiegészítés és multiplikáció műveletei)?
Milyen kódokat hívnak lineáris blokk kódoknak. Milyen kódok vannak a rendszeresség szempontjából?
Mi a kódolás a paritásellenőrzéssel? Mi a kód redundanciája? Milyen előnyökkel és hátrányokkal jár ez a kód?
Melyik információátviteli csatornát a bináris szimmetrikus csatorna modell írja le.
Mi az eljárás a hibák észlelésére és rögzítésére egy iteratív kóddal? Milyen előnyökkel és hátrányokkal jár ez a kód?
Melyek a lineáris blokkkódok meghatározására? Melyek a kódsor fő részei a lineáris blokk szisztematikus kódnak?
Mi a paritásellenőrzési egyenletrendszer a lineáris blokk kóddal kapcsolatban?
Mi a lineáris blokk kód generáló mátrixa? Milyen tulajdonságai vannak? Mi a generátor mátrix szerkezete?
Hogyan generálható mátrixot használva egy ellenőrző egyenletek rendszerét egy lineáris blokkkódra építve?
Mi a lineáris blokkkód-ellenőrző mátrix? Milyen tulajdonságai vannak?
Mi a lineáris blokkkód ellenőrző mátrixának szerkezete? Az ellenőrző mátrix mely része felel meg az információs szimbólumoknak, és melyik rész az ellenőrzés?
Hogyan használhatja fel az ellenőrző mátrix használatával a lineáris blokkkód ellenőrző egyenleteinek rendszerét?
Hogyan írja le a bináris csatornán a hibavektort? Mi a feladata az átvitt kódszó dekódolása?
Mi a kód blokk szindróma? Hogyan határozzák meg?
Milyen tulajdonságot jellemez az elfogadott vektor szindróma? Milyen esetekben fordul elő a kódszindróma a továbbított sorrend hibáit?
Hogyan lehet észlelni és kijavítani a hibákat lineáris blokkkóddal a kódszindróma használatával?
Hogy van Hamming súlya és távolsága bináris szekvenciákhoz?
Mi a Hamming lineáris blokkkód minimális kódszáma? Hogyan határozzák meg?
Mi a szükséges és elégséges feltétel egy adott többszörösség hibáinak lineáris blokkkóddal történő kimutatására?
Mi a szükséges és elégséges feltétel egy lineáris blokkkód hibájának kijavítására?
Mik a szükséges és elégséges feltételek a zajkibocsátó kód létezésére?
Hogyan van meghatározva a paritás szimbólumok minimális száma meghatározott lineáris blokkkódokkal meghatározott jellemzőkkel?
Hogyan lehet egy lineáris blokkkód generáló mátrixot létrehozni adott jellemzőkkel?
Milyen lineáris blokkkódokat neveznek Hamming kódoknak?
Hogyan határozható meg a Hamming kód információs és ellenőrző szimbóluma.
Hogyan épült a Hamming kód kódszava?
A Hamming bináris kód ellenőrző mátrixának összeállítása.
Mi a Hamming kód használata során a szindróma jelentősége?
Hogyan történik a Hamming kód dekódolása?
Hogyan épül fel a generáló Hamming kódgenerátor?
1 Shannon K. Működik az információelmélet és a kibernetika elméletéről. - M. Külföldi irodalom kiadó, 1963.
2 Jaglom A. Jaglom I. Valószínűség és információ - M. Nauka, 1973.