Institute of Information Science - University of Miskolc

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
===== Hamming távolság =====

A redundancia növelésével automatikus hibajavítás is végezhető. Ha **m** adatbitünk van, akkor ehhez rendeljünk **r** darab redundáns paritásbitet, így a teljes bithossz **n**:

$$ n = m + r. $$

Ha adott két kódszó, pl: ''00101110'' és ''00111110'' és ezek 1 bitben térnek el egymástól, akkor a kódszavak Hamming távolsága 1. 

Ez egy érdekes távolság fajta, mert nem függ attól, hogy a hányadik bit különbözik, és attól sem, hogy ezen a helyen bináris vagy tízes számrendszerbeli szám áll. Tehát pl. 456**3**5263 és 456**1**5263 két szónak is 1 a Hamming távolsága, hiába a hibás helyen még 8-féle más szimbólum is állhatna!

Ennek az a jelentősége, hogy ha két kódszó távolsága **d**, akkor **d** darab egyszeres bithibának kell lennie ahhoz, hogy az egyik kódszó a másikba alakulhasson. 

Például az ''11110001'' és a ''00110000'' Hamming távolsága 3, mert 3 egyszeres bithiba szükséges ahhoz, hogy az egyik a másikba alakulhasson.

**d** egyszeres bithiba felismeréséhez \(d + 1\) távolságú kódolás kell, mert ebben az esetben **d** egyszeres bithiba semmiféleképpen nem alakíthat át egy érvényes kódszót egy másik érvényes kódszóvá.

Az egyszeres bithibák javításához a Hamming-kódokban szükséges paritásbitek számát a következőképpen lehet meghatározni:

Ha a kódolt üzenet **m** adatbitet tartalmaz, akkor legalább **r** paritásbit szükséges, ahol **r** olyan, hogy teljesüljön az egyenlőtlenség:

$$ 2^r \geq m + r + 1. $$
$$ 2^r \geq n + 1. $$

Ez azt jelenti, hogy az **r** paritásbitnek képesnek kell lennie megkülönböztetni a \(m+r+1\) különböző állapotot (beleértve a hibamentes állapotot és az összes lehetséges hibás bitpozíciót).

Ha \( m = 8 \) adatbitet akarunk egyszeres bithibajavítással kódolni, akkor nézzük meg, hány paritásbitre van szükségünk a fenti egyenlőtlenség alapján:

Próbáljuk meg meghatározni \( r \)-t különböző értékekkel:

**\( r = 3 \):**  
   \[
   2^3 = 8 \quad \text{és} \quad m + r + 1 = 8 + 3 + 1 = 12
   \]
Ez nem elég, mert \( 8 < 12 \), tehát 3 paritásbit nem elegendő.

**\( r = 4 \):**  
   \[
   2^4 = 16 \quad \text{és} \quad m + r + 1 = 8 + 4 + 1 = 13
   \]
Ez kielégíti az egyenlőtlenséget, mivel \( 16 \geq 13 \), tehát 4 paritásbit elegendő ahhoz, hogy 8 adatbit esetén egyszeres bithibát javítsunk.

Tehát **8** adatbit esetén **4** paritásbit szükséges az egyszeres bithibák javításához.

A következő táblázatban kiszámítottuk több bithosszra:

^Szó hossza (m)^Paritásbitek száma (r)^teljes bithossz (m+r = n)^hozzáadott bitek %-a^
|8|4|12|50|
|16|5|21|31|
|32|6|38|19|
|64|7|71|11|
|128|8|136|6|
|256|9|265|4|
|512|10|522|2|

Bithibák automatikus javításának elve a következő ábra alapján értelmezhető:

Kódoljuk az ''1101'' üzenetet, képezzünk három halmazt A, B, C és a halmazok AC, AB, ABC, BC közös részeibe írjuk be a biteket. A középső ábrán pedig írjuk be a 3 paritásbitet a halmazokba. A harmadik képen azt mutatjuk be, hogyha hibás bit érkezik, akkor a paritás ellenőrzés megmutatja melyik metszetben van rossz érték.

{{:tanszek:oktatas:infrendalapjai_architekturak:informacio_ellenorzes:pasted:20241113-162231.png}}