A kalapálás kódjának összefoglalása
Ez a cikk nem rendelkezik elég információval.
A Hamming kódok a leghíresebb és valószínűleg az első önellenőrző és önkorrekciós kódok. Bináris számrendszerre épülnek.
1. Történelem
A közép 1940, Richard Hamming dolgozott a híres Bell Labs a számlálási gép Bell Model V. Ez egy elektromechanikus gép segítségével reléegységeket, ami az arány nagyon alacsony: egy fordulat néhány másodpercen belül. Az adatokat a lyukasztott kártyák segítségével a gépbe vezették, ezért gyakran fordultak elő hibák az olvasási folyamat során. Munkanapokon speciális kódok észlelésére és kijavítani a hibát talált az üzemeltető elismerte a hibát a jelzőlámpa, javított és futtatni a gépen. Hétvégén, amikor nem volt operátor, amikor hiba történt, a gép automatikusan elhagyta a programot, és elkezdett egy másik.
2. Rendszeres kódok
A rendszeres kódok nagy csoportot képeznek a blokk, elválasztható kódok között (ahol az összes szimbólumot fel lehet osztani a tesztelésre és az információkra). A szisztematikus kódok egyik jellemzője, hogy a szimbólumokat az informatikai szimbólumokon végzett lineáris műveletek eredményeként alakítják ki. Ezenkívül bármely megengedett kódkombináció lineáris műveletek eredményeként állítható elő lineárisan független kódszavak készletén keresztül.
3. Önellenőrző kódok
A Hamming kódok önellenõrzõ kódok, vagyis olyan kódok, amelyek automatikusan detektálják az adatátvitel hibáit. Konstrukciójukhoz elegendő, ha minden egyes szóhoz hozzáadunk egy további (vezérlő) bitet, és kiválasztjuk annak a számnak a számát, hogy a számok bármelyikén lévő egységek teljes száma például egyenlő legyen. Egyetlen hiba a továbbított szó bármely mentesítésében (beleértve például a kontrollkategóriát) megváltoztatja az összes egység egyenlőségét. A 2-es számlálók, amelyek a szám bináris számjegyei között található egységek számát veszik figyelembe, jelezhetik a hibák jelenlétét.
Nem lehet tudni, hogy a hiba pontos kategóriája milyen, és ezért nincs módja annak kijavítására. A két, négy vagy akár páratlan számú bit egyidejű hibái észrevétlen maradnak. Azonban kettős, és a négyszeres hibákat nem valószínű.
4. Önmódosítási kódok
Az automatikus hibajavítás lehetséges kódjait önkorrekciónak nevezzük. Az egyszeri hibák kijavítására tervezett önkorrekciós kód létrehozásához egy ellenőrző számjegy nem elegendő. Amint az alábbiakból látható, a k ellenőrző számjegyek számát úgy kell megválasztani, hogy az egyenlőtlenség teljesüljön, vagy ahol m a kódszó alapbitjeinek száma. A m értékeinek az ezen egyenlőtlenséggel összhangban talált m értékeinek k minimális értékeit a táblázatban adjuk meg.
Jelenleg a bináris blokk korrekciós kódok a legfontosabbak. Ilyen kódok használatakor az információt ugyanolyan hosszúságú blokkok formájában továbbítják, és minden blokk egymástól függetlenül kódolva és dekódolva van. Szinte minden blokkkódban a szimbólumok információra és ellenőrzésre oszthatók. Így a kódok összes kombinációja megengedett (amelyre az információ és ellenőrző szimbólumok aránya lehetséges) és tilos.
Az önkorrekciós kódok fő jellemzői a következők:
- Engedélyezett és tiltott kombinációk száma. Ha n a mondatban szereplő karakterek száma, r a blokkban lévő paritás szimbólumok száma, k az információs szimbólumok száma, majd a lehetséges kódszavak száma, a megengedett kódszavak száma és a tiltott kombinációk száma.
- A kód redundanciája. Az érték a korrekciós kód redundanciája.
- A minimális kód távolsága. A legkisebb kódtávolság d az a minimális számú torzított szimbólum, amellyel az egyik megengedett kombináció átkapcsolható egy másikra.
- Az észlelhető és javítható hibák száma. Ha g a kód által korrigált hibák száma, szükséges és elégséges
- A kódok korrekciós képességei.
A Plotkin határ a kód távolság felső határát adja meg
A Hamming-korlát megadja a megengedett kódszavak maximális számát, ahol az n elemek kombinációinak száma i elemekkel. Innen a paritásszimbólumok számának becslésére kaphatunk kifejezést: Az értékeknél a Hamming határ és a Plotkin határ közötti különbség kicsi.
A nagy n-re vonatkozó Varshamov-Hilbert határvonal a paritásszimbólumok számának alsó határát határozza meg, a fenti becslések mindegyike a felső határértéke d-nek nevezi a fix n és k értékeket, vagy a paritásszimbólumok számának alacsonyabb becslését
5. Irodalom
- Peterson W. Weldon E. Hibajavító kódok: Trans. angolul. M. Mir, 1976, 600 c.
- Clark D. Kane D. Kódolás hibajavítással a digitális kommunikációs rendszerekben: Per. angolul. M. Radio and Communication, 1987, 300 p.
6. Hamming kód
A Hamming kódok megalkotása az egyes szimbólumok számának paritásellenőrzésén alapul: egy elemet adunk hozzá a szekvenciához úgy, hogy a szimbólumban az egyes szimbólumok száma egyenletes legyen. A jel itt a modulo 2 hozzáadását jelenti
. - nincs hiba, egyetlen hiba. Ez a kód neve vagy. Az első szám a sorozatban szereplő elemek száma, a második a paritásszimbólumok száma. A paritásszimbólumok minden egyes számához létezik egy klasszikus Hamming kód, amelynek jelölése, azaz. -. Más k értékeknél az úgynevezett csonkolt kódot kapjuk, például az MTK-2 nemzetközi távirat kódot, amelyhez. Megköveteli a Hamming-kódot, amely a klasszikusból csonka. Például vegyük figyelembe a klasszikus Hamming kódot. A tesztszimbólumokat az alábbiak szerint csoportosítjuk:
A jel itt a modulo 2 hozzáadását jelenti.
A kódszó megjelenése így néz ki: =
A dekóder bemenete a kódszót tartalmazza, ahol a szimbólumokat lökettel jelölik, ami az interferencia következtében eltorzulhat. A dekóderben a hibajavító üzemmódban szindrómák sorozata épül fel:
szekvencia szindrómának nevezik.
A szindróma megjelenése így néz ki:
=
A Hamming kód kódszava