Hamming kódok - studopediya
Hamming-kód az úgynevezett (n, k) - kódot, amely ellenőrzi által meghatározott H mátrix (n, k). rendelkező sorok és oszlopok, ahol az oszlopok a H (n, k) mind különböző nem nulla bináris szekvenciájának hossza m (m - bites bináris számok 1-től).
A hossza kódszót egyenlő a Hamming-kódot.
Az adatelemek számának meghatározása.
Így a Hamming-kód teljesen száma határozza meg m - száma szűrés elemek egy kódszó.
Ismerve az a fajta mátrix H (n, k). Meg tudja határozni a korrekciós tulajdonságait (n, k) - Hamming-kódot. Mivel az összes mátrix oszlopait különböző vizsgálatok, nincs két oszlopai H (n, k) nem lineárisan függ. Ezen kívül, minden számot m mindig lehetséges, hogy meghatározza a három mátrix oszlopait H (n, k). amelyek lineárisan függ, például oszlopok, megfelelő számok 1, 2, 3. Így minden olyan (n, k) - Hamming-kód, Dmin = 3.
Hamming-kód egyik néhány példa a tökéletes kódot.
Sőt, mivel (n, k) - Hamming-kód kijavítja egyetlen hiba, minden egyszeres hiba minták (és már csak verzió) kell telepíteni a különböző kapcsolódó osztályok, amelyek száma is megegyezik. Ezért amellett, cosets tartalmazó mintákban egyetlen hiba, nincs más dekódoló asztal és megerősíti, hogy a tökéletesség Hamming-kód.
Fix számú, meg lehet építeni egy Hamming-kód bármilyen hosszúságú () rövidítésével (n, k) - kódot. Rövidülés nem csökkenti a minimális távolság. Annak a ténynek köszönhetően, hogy bármely n egész van Hamming-kód, bármely csoport kódot korrekciójára egyetlen hibák az úgynevezett Hamming-kód.
Példa 5.13. Hamming kódok határozzák paraméterek természetes hossza különböző m értékek. Az eredményeket a mint az asztalnál.
Nyilvánvaló, hogy a minimális hosszának a Hamming-kód, amelynek gyakorlati értéke 3. A növekedés aránya n növekszik és megközelítések 1.
Példa 5.14. Tekintsük a Hamming-kód (7,4). Ez a kód ellenőrzi a mátrix hét háromjegyű bináris számok 1-7:
Egy szempont ezen mátrix azt mutatja, hogy a minimális számú lineárisan függő oszlopok egyenlő 3 (például 1, 2 és 3), és így, Dmin = 3.
Abban az esetben, ha az oszlopok a H mátrix (n, k) - Hamming-kód egy rendezett rekordja m - bites bináris számok, dekódolást végrehajtjuk eredeti módon. Ennek eredményeként az ellenőrzés vonatkozásában kiszámítására egy kódszót, amely egyetlen hibát, a szindróma kapott pontosan megegyezik a szám az elem, amelyben a hiba történt.
Valóban, ha a EI tartalmaz egy egységet a kisülés, hibás megfelelő elem, akkor a szorzás a mátrix H T a H mátrix összes sor megfelelő nullákat T. EI. Ők viszont nullára, és csak a karakterlánc megfelelő „1” EI megőrzi alakját (ez a szekvenciális adat száma kettes számrendszerbeli) a választ.
Példa 5,15. Tegyük fel, a vevő RCD adatátviteli rendszer regisztrálja ezek kombinációja. Számítás ad szindróma
azaz hiba a negyedik elem, és a kódszó-kód (7,4), amely átkerült, a következő:
Az egyszerű transzformációi (n, k) - Hamming-kódot Dmin = 3 lehet beszerezni (n +1, k) - Hamming-kódot Dmin = 4.
Erre a célra egy kódszót ki redundáns elemet, amely az eredmény a paritás-ellenőrző minden eleme a kódszó. Az adatok száma elemek azonos.
ellenőrizze mátrix (n +1, k) - Hamming-kódot Dmin = 4 kapjuk a mátrixból ellenőrzések (n, k) - kód Dmin = 3 bevezetésével további sorok (n +1) -edik egységet.
Mivel a méret a mátrix kód ellenőrzés dmin = 4 egyenlőnek kell lennie, hogy az egyes sorok a kód mátrix ellenőrzések dmin = 3, szükséges hozzá egy nulla elemet, hogy ne zavarják a vizsgálatot korábban kiszabott. ellenőrizze mátrix (n +1, k) - Dmin = 4 kód formájában:
Tekinthető eljárás eredményezett hosszabbítás kódszó által egy számjegyet Dmin megnöveljük 1 egység, úgynevezett kód kiterjesztés (1- nyúlás) .Udlineniyu vethetők alá egyéb kódokat, például a Reed-Solomon-kód.
Példa 5.16. Construct Hamming-kód (8,4) a Dmin = 4-kód-alapú mátrix ellenőrzések (7.4).
Szerint a mátrix nézettel, arra lehet következtetni, hogy a kód (7,4) hajtjuk végre 3 független paritás.
Az egyes sorokban az elemek meghatározza a kódszó által lefedett egy vizsgálat.
Így a mátrix megfelel az alábbi szűrési rendszer kapcsolatok:
Annak érdekében, hogy a kód (8,4) a Dmin = 4 bevezetni egy másik valamennyi eleme egy kódszó, és az ellenőrzés eredményétől van írva, mint a további 8-dik eleme:
Ez az ellenőrzés felel meg egy további (negyedik) sort a H mátrix (8,4). amely nyolc egységek. Annak érdekében, hogy ne zavarják az előző három próba helyett a nyolcadik elem az első három sorban a H mátrix (8,4) azon a helyen, a nyolcadik elem van rögzítve nullák. Így a mátrix kód ellenőrzés (8.4) kaptunk formájában:
Határozza meg az ismert eljárás Dmin (8,4) - a kód. Vizsgálatából azokat az oszlopokat, amelyek összege nulla oszloppal a (7,4) - a kód, akkor látható, hogy azzal a kiegészítéssel, a negyedik sorban általuk megszűnt lineárisan függ. Most a száma lineárisan függő oszlopok kell lennie, még, és legalább 4, pl, 3 első és az utolsó oszlopban. Így a kapott Hamming-kód (8,4) Dmin = 4.
Eddig nem megosztott elemeit kódszó információ és ellenőrzés. A legésszerűbb, úgy tűnik, hogy meg lehet csinálni a következő. Kívánatos módon minden egyes verifikációs kapcsolatban egyedileg határozzuk meg árnyékoló elem eredményeként a paritás ellenőrző sokaságának információs elemek. Ebben az esetben mi lenne képes meghatározni az értékét az ellenőrző elem a legegyszerűbb módon - a megoldás egy lineáris egyenlet egy ismeretlen. Ehhez, sorba rendezett rekordjának oszlopai H (n, k), mint a ellenőrző elem, szükséges, hogy elemeket indexek 2 i. ahol i változik 0 és m -1, mivel ezeket az oszlopokat tartalmaznak, egyetlen egység. Ez utóbbi azt jelzi, hogy az elemek indexek 2 i tartalmaz csak egy scan, és így, akkor lehet venni, mint a paritás.
Példa 5.17. Határozza meg a vizsgálat helye elemek a Hamming-kód (7,4).
Hivatkozás a mátrix látható az előző példában, mivel a szűrés elemek kiválasztott elemeket, amelyek megfelelnek az oszlopok, amely csak egyetlen egységet, azaz első, második és negyedik. Következésképpen, a 4 adatkód elem (7,4) kell foglalják a helyet a 3., 5., 6. és a 7. bitet. Jelen az előző példában, a rendszer lehetővé teszi ellenőrzése kapcsolatok értékének meghatározásához az egyes szűrési elemek értékeinek megfelelően az információs elemek, azaz a értelmesen egyszerű kódot elemeket, amely szükséges, hogy kódolja a Hamming-kód
Ismerve a helyeken a vizsgálati elemek, könnyen vezethet H mátrix (n, k) Hamming-kód, hogy a kanonikus formában.
Ehhez az oszlopokat indexek 2 i. ahol a felvétel a megrendelt oszlopok költözött, hogy az első m oszlopok csökkenő sorrendben a számok. Általánosságban, egy permutációs oszlopok a H mátrix (n, k) vezet ekvivalens (n, k) - kódot. Abban az esetben, Hamming kódok természetes hosszúságú kódot kapott nem azonos, és pontosan egybeesik a forrás.
Példa 5.18. Átalakítás a mátrix a kanonikus formában.
Átrendezése az oszlopok: 4. hely 1-jén, az első helyen, hogy a harmadik, és a harmadik helyen a 4.:
Ez a kanonikus mátrix formájában. Összehasonlítva az eredeti mátrix jelzi, hogy a hely az információ elemek a kanonikus formában oszlopok megfelelnek a 3, 5, 6, 7, és a helyek szűrés elemek - 4. oszlop, 2, 1.
A kapcsolat a tájékoztatás és a redundancia elemek megmaradnak való tekintettel permutációk:
A generátor mátrix G (n, k) a Hamming-kód lehet beszerezni a mátrix H (n, k). Használata tétel 5.3:
A kódoló és dekódoló eszközök erre az osztályra a kódokat kell vizsgálni a tanulmány a ciklikus kódok.
Hatékonyságának értékelésére a Hamming-kódok.
a) Hamming kódok Dmin = 3
Az ilyen kódokat használnak vagy hibák kijavítására multiplicitás t = 1, vagy, hogy garantálja hibadetektálás S = 2 arányt. Ennek megfelelően, a hiba valószínűsége ezekben az esetekben a csatornacsoportnak hiba:
A megbízhatóság a nyereség, mint az egyszerű kódok azonos hossza:
Az ilyen kódok, két módja van - egy fix hibák és hiba észlelése és hiba észlelése csak. A hibaszintjét ezeket az üzemmódokat hiba esetén csoportosítás:
A megbízhatóság a nyereség, mint egy egyszerű kódot az azonos hossza:
Alapján (n, n-1) - kódok Dmin = 2, vagy a Hamming-kódok Dmin = Dmin = 3 és 4 lehet építeni kódok magasabb kijavítása tulajdonságokkal. Erre a célra, valamint a védelem minden egyes továbbított kombinációja a fent ismertetett módon hajtjuk zajmentes kódolás csoportok hasonló továbbított bitek kombinációk. A kódolási folyamat lehet magyarázni segítségével ábra. 5.6.
Kombinációk egyszerű kódot kell továbbítani egy kommunikációs rendszeren keresztül van rögzítve, mint egy asztal - minden kombinációja egyetlen sor a táblázatban (információs szimbólumok). Ezután egy kódoló sorokba és oszlopokba. Általában a kódoláshoz sorok és oszlopok kódolási akkor különböző kódokat. Felesleges elemek hozzáfűződnek soronként (check soronként), és minden oszlopon (az oszlop-ellenőrzés). Ellenőrző ellenőrzések kódoló oszlopon álló redundáns sor elemeit, vagy a kódoló vonalak álló ellenőrzések oszlopok. Későbbi bevezetése redundancia végzik az információ védelmére, blokkok, ábrán látható. 5.6. A kódolási folyamat ábrán bemutatott. 5.7. Az információt, védett két csekket húzott egy doboz. A felesleges ellenőrizze szintű harmadik paralelepipedon alakúak izoláljuk a vastag vonal.
5 e-mail. kombináció
Ennek eredményeként a iteratív kódoló csoportot kódok kapunk, amelyek fontos tulajdonság.
Tétel 5.3. Minimális távolság iteratív kód a termék a minimális távolság a kódot, a kód, annak elemeit.
Valójában, ha abban az esetben két teszt minimális súly kód egyenlő egy, a másik, akkor a iteratív kódot vektor legalább egységek minden sorban és minden oszlopban az elemek, és ezért nem kevesebb egységek.
Hasonló érvelés lehet terjeszteni az esetben, ha nagyobb számú ellenőrzést.
Iteratív kód generációs mátrixot lehet kialakítani az alábbiak szerint.
Let GA - generáló mátrix kód ellenőrzésére használt a sorokat, és gon - generátor mátrix kód ellenőrzésére használjuk az oszlopokat, majd az iteratív kódgenerálást mátrix (GAV) a következő:
Felvétel azt jelenti, hogy a mező „1” van írva a GA mátrix gon mátrix. és ahelyett, hogy a „0” van írva mátrixa nullák amelynek méretei egyenlő a méretek Gon. Például, ha az ellenőrzést sorokban és oszlopokban használt (6, 5) - kód paritásvizsgálathoz a