Hammingova koda: definicija, popravljanje napak in primer (7,4)

Hammingova koda: jasna definicija, kako odkriva in popravlja napake, praktičen primer (7,4) ter razlaga paritetnih bitov in nastajanja kod.

Hammingova koda je blokovna koda, ki popravlja napake. Imenovana je po Richardu Hammingu, ki jo je razvil v petdesetih letih prejšnjega stoletja, ko je delal s stroji, ki so imeli releje in so za branje podatkov uporabljali luknjane kartice. Zaradi napak pri prenosu ali branju so morali podatke takrat pogosto popravljati ročno, Hamming pa je iskal avtomatiziran način za odkrivanje in popravljanje enobitnih napak.

Hammingove kode se pogosto uporabljajo v digitalni obdelavi signalov in v telekomunikacijah ter kot ECC (error‑correcting code) v pomnilniških modulih. Temeljijo na vpeljavi dodatnih paritetnih bitov, ki zagotavljajo redundanco. Paritetni bit pove, ali je določena skupina bitov soda ali liha; v Hammingovi kodi je vsak bit podatkov pokrit z več paritetnimi biti. To omogoča zanesljivo odkrivanje napak in popravljanje enobitnih napak v kodni besedi.

Pravila in splošne formule

Če uporabimo k paritetnih bitov, je skupna dolžina kodne besede

2 k - 1 {\displaystyle 2^{k}-1}

To pomeni N = 2^k − 1. Število uporabnih (informacijskih) bitov v kodni besedi je N − k = 2^k − k − 1. Pogosto se zapisuje oblika (N,n), kjer je N skupna dolžina kodne besede, n pa število podatkovnih bitov. Pri k = 3 dobimo N = 7 in n = 4, torej kodo (7,4).

Paritetni biti običajno zasedejo položaje, ki so potence števila 2 (1, 2, 4, 8, ...). Podatkovni biti se vstavijo v preostale položaje. Vsak pariterni bit nadzoruje (udeležuje se pri izračunu paritete) tiste položaje, katerih binarna predstavitev ima v ustreznem bitu enico. Standardna konvencija je uporaba sode (even) paritete, lahko pa se uporablja tudi liha (odd) pariteta — pomembno je le, da sta kodiranje in dekodiranje usklajena.

Primer: Hamming (7,4) — kodiranje

Hamming (7,4) uporablja 3 paritetne bite (p1, p2, p3) in 4 podatkovne bite (d1–d4). Položaji 1..7 so običajno razporejeni takole:

• položaj 1: p1 (paritetni bit)
• položaj 2: p2 (paritetni bit)
• položaj 3: d1 (podatkovni bit)
• položaj 4: p3 (paritetni bit)
• položaj 5: d2 (podatkovni bit)
• položaj 6: d3 (podatkovni bit)
• položaj 7: d4 (podatkovni bit)

Paritetna pravila (za sodo pariteto):

• p1 pokriva položaje z LSB = 1: 1, 3, 5, 7
• p2 pokriva položaje z drugim bitom = 1: 2, 3, 6, 7
• p3 pokriva položaje z tretjim bitom = 1: 4, 5, 6, 7

Primer kodiranja podatkovnih bitov d = 1011 (d1=1, d2=0, d3=1, d4=1):

• Vstavimo podatke v položaje 3,5,6,7: _ _ 1 _ 0 1 1
• Izračunamo p1 = parity(3,5,7) = parity(1,0,1) = 0 (soda)
• Izračunamo p2 = parity(3,6,7) = parity(1,1,1) = 1 (ker 3 enice je liho, p2=1, da je skupaj sredu parno)
• Izračunamo p3 = parity(5,6,7) = parity(0,1,1) = 0
• Končna kodna beseda (p1 p2 d1 p3 d2 d3 d4) = 0 1 1 0 0 1 1 → 0110011

Popravljanje napak: sindrom in popravek

Med prenosom lahko pride do napake (najpogosteje obravnavamo enobitne napake). Pri sprejemu prejmemo kodno besedo in ponovno izračunamo paritete. Rezultat preverjanja paritet (oz. vektor, imenovan sindrom) pove, kateri bit je v neskladju. Sindrom s1,s2,s3 sestavimo tako, da vsak s_i predstavlja rezultat paritetnega preverjanja za ustrezen paritetni bit. Če so uporabljene sode paritete, je s_i = 0, če je izbrana skupina sodih bitov, in 1, če je liha.

Pri zgornjem primeru domnevajmo, da se med prenosom spremeni bit na položaju 5 (0 → 1). Prejeta beseda: 0 1 1 0 1 1 1 (0110111). Izračun sindroma:

• s1 = parity(1,3,5,7) = parity(0,1,1,1) = 1
• s2 = parity(2,3,6,7) = parity(1,1,1,1) = 0
• s3 = parity(4,5,6,7) = parity(0,1,1,1) = 1

Sestavimo sindrom kot binarno število s3 s2 s1 = 101₂ = 5 → točno kaže položaj napake (položaj 5). Sprejemnik nato izmeni ta bit (flip), s čimer se koda popravi na prvotno 0110011, in iz nje izvleče podatke d1..d4 = 1011.

Krata Hammingova koda (3,1) in omejitve

Najkrajša Hammingova koda je (3,1) (k = 2 paritna bita, N = 3). Možni veljavni kodeksi pri sodi pariteti so 000 in 111. Če med prenosom nastane enobitna napaka (npr. 001, 010 ali 100), bodo ti vzorci s sindromom pripisani najbližji veljavni kodi (000). Podobno 011, 101 in 110 vodijo do popravka v 111. To ilustruje princip popravila enobitnih napak.

Omejitve:

• Hammingove kode so zasnovane za popravljanje enobitnih napak (single‑error correction, SEC). Pri dvojnem bitnemu napaki lahko koda pogosto napako zazna (odvisno od konfiguracije), a je ne more zanesljivo popraviti.
• Hammingova koda ima razdaljo Hamming d = 3, zato lahko zazna do d−1 = 2 napak ali popravi (d−1)/2 = 1 napako.

Razširitve in praktične uporabe

Običajna razširitev je dodajanje enega dodatnega paritetnega bita za celotno kodno besedo (t. i. Hamming + parity), kar omogoča SECDED: Single Error Correct, Double Error Detect — torej popravljanje enobitnih napak in zaznavanje dvobitnih napak. Take sheme se pogosto uporabljajo v pomnilniških modulih (ECC RAM), komunikacijskih protokolih in v sistemih, kjer so napake redke, a kritične.

Kodiranje in dekodiranje Hammingovih kod je razmeroma enostavno za strojno izvedbo (preproste logične operacije), zato so metode učinkovite tudi v strojni opremi z omejenimi stroškovnimi omejitvami.

Vprašanja in odgovori

V: Kaj je Hammingova koda?

V: Kako deluje Hammingova koda?

V: Kdo je izumil Hammingovo kodo?

V: Za kaj je Richard Hamming uporabil svoj izum?

V: Kaj se zapiše kot (N,n), ko govorimo o Hammingovi kodi?

V: Katera je najkrajša možna Hammingova koda?

Išči po črki