Hemingov kod

Binarni Hemingovi kodovi
Hemingov(7,4)-kod (sa $r=3$)
Imenovan po	Ričard Heming
Classification
Type	Linearni blok kod
Parameteri
Dužina bloka	$2^{r}-1$ gde $r\geq 2$
Dužina poruke	$2^{r}-r-1$
Stopa	$1-r/(2^{r}-1)$
Rastojanje	$3$
Veličina alfabeta	2
Notacija	$\left[2^{r}-1,2^{r}-r-1,3\right]_{2}$
Svojstva
perfektan kod

U telekomunikacijama, Hemingovi kodovi su porodica linearnih grešaka i ispravljenih kodova, koji se generališu kao Hemingov (7,4)-kod, a koji je izmislio Ričard Heming 1950. godine. Hemingovi kodovi mogu da detektuju i do dve-bitne greške ili da isprave jedno-bitne greške bez otkrivanja neispravljenih grešaka. Nasuprot tome, jednostavni parni kod ne može da ispravi greške, i može da otkrije samo neparan broj bitova u grešci. Hemingovi kodovi su savršeni kodovi, to jest, oni dostižu najvišu moguću brzinu za kodove sa svojom blok dužinom i minimalnom distancom od 3.

Matematički, Heming kodovi su klasa binarnih linearnih kodova. Za svaki ceo broj $r\geq 2$ postoji kod blok dužine $n=2^{r}-1$ i dužinom poruke $k=2^{r}-r-1$. Otuda je brzina Heming kodova $R=k/n=1-r/(2^{r}-1)$, što je najviše moguće za kodove sa distancom $3$ i blok dužinom $2^{r}-1$. Matrica parne provere Hemingovog koda je konstruisana tako da su navedene sve kolone dužine $r$ koje nisu nule, što znači da je dvostruki Hemingov kod probušeni Hadamardov kod. Matrica parne provere ima svojstvo da su bilo koje dve udvojene kolone linearno nezavisne.

Zbog ograničenja suvišnog dodavanja Hemingovih kodova u podacima, oni mogu samo da otkriju i isprave greške kada je vrednost greške niska. To je slučaj u memoriji računara (ECC memorija), gde su bitne greške izuzetno retke i Hemingovi kodovi su u širokoj upotrebi. U tom kontekstu, prošireni Hemingov kod, koji ima jedan ekstra parni bit, često se koristi. Prošireni Hemingovi kodovi postižu Hemingovu distancu od $4$, čime se omogućava dekoderu da napravi razliku kada se javi najviše jedna bitna greška i kada se jave dve bitne greške. U tom smislu, prošireni Hemingovi kodovi za ispravljanje jedno greške i detektovanje duple greške skraćeno su nazvani SECDED.

Istorija

Heming je radio u Bell laboratorijama 1940. godine na Bel Model V računaru, mašini baziranoj na elektromehaničkom releju sa vremenskim ciklusom u sekundi. Ulaz je hranjen na bušenim karticama, koje bi neminovno pročitale greške. Tokom dana u nedelji, poseban kod bi pronašao greške i fleš svetla tako da su operateri mogli da rešavaju problem. Tokom posle-časovnih perioda i vikendom, kada nije bilo operatora, mašina je jednostavno prelrelazila na sledeći posao.

Kodovi koji su prethodili Hemingovom kodu

Jedan broj jednostavnih kodova za detekciju greške bili su korišćeni pre Hemingovih kodova, ali nijedan nije bio efikasan kao Hemingovi kodovi za isti gorenavedeni prostor.

Parnost

Parnost dodaje jedan bit koji pokazuje da li je broj od 1 bitova u prethodnim podacima bio paran ili neparan. Ako se neparan broj bitova menja u prenosu, poruka će promeniti parnost i greška može biti otkrivena u ovom trenutku. (Treba imati na umu da bit koji se menja može sam da bude paran!) Najčešća konvencija je da parnost vrednosti 1 ukazuje da postoji neparan broj u podacima, a parnost vrednosti 0 ukazuje da postoji paran broj. Ako se još menja broj bitova, provereni bit će će važiti i greška neće biti otkrivena. Štaviše, parnost ne označava koji bit će sadržavati grešku, čak i kada može da se detektuje. Podaci moraju biti u potpunosti odbačeni i ponovo emitovani od nule. Na bučnim prenosnim medijima, uspešan prenos može da traje dugo ili se nikada neće javiti. Međutim, iako je kvalitet provere parnosti loš, jer se koristi samo jedan bit, ovaj metod rezultuje u najmanju ruku u gorenavedenom delu. Osim toga, provera parnosti dozvoljava obnovu pogrešnog bita kada je njegov položaj poznat.

Dva-iz-pet kod

Dva-iz-pet kod je šema kodiranja koja koristi pet digita, koji se sastoje od tačno tri 0 i dve 1. Ovo obezbeđuje deset mogućih kombinacija, dovoljno za predstavljanje brojeva od 0 do 9. Ova šema može da otkrije sve pojedinačne greške bita i sve neparne numerisane greške bita. Međutim, to još uvek ne može da vodi ispravci ove greške.

Ponavljanje

Još jedan kod je u upotrebi u vreme ponavljanja svakog bit podatka nekoliko puta, kako bi se osigurao njegov proboj. Na primer, ako je bitni podatak za slanje 1, n = 3 kod ponavljanja će poslati "111". Ako tri primljena bita nisu identična, došlo je do greške. Ako je kanal dovoljno čist, u najvećem delu vremena će se samo jedan bit promeniti u svaki trostruki. Dakle, 001, 010, 100 i svaki odgovara na 0 bit, dok 110, 101, 011 i odgovaraju na 1 bit, kao da su bitovi računati kao "glasovi" u odnosu na originalan bit. Kod sa ovom sposobnošću rekonstrukcije originalne poruke u prisustvu grešaka je poznat kao kod za ispravljanje grešaka. Ovaj trostruko ponavljajući kod je zapravo najjednostavniji Hammingov kod sa $m=2$, jer postoje 2 parna bita i $2^{2}-2-1=1$ bit podataka.

Takvi kodovi ne mogu korektno da poprave sve greške. U našem primeru, ako kanal prevrne dva bita i prijemnik dobije "001", sistem će detektovati grešku, ali će zaključiti da je originalni bit bio 0, što je netačno. Ako se poveća broj puta, duplira se svaki bit na četiri, i mogu se otkriti sve dve-bitne greške, ali ne mogu da se isprave (glasovi "kravata"); u pet, mogu da se isprave sve dve-bitne greške, ali ne i sve tri-bitne greške.

Osim toga, kod ponavljanja je izuzetno neefikasan, smanjuje protok po tri puta u odnosu na originalan slučaj, a efikasnost opada drastično kako se poveća broj puta svaki bit se duplira u cilju otkrivanja i ispravljanja više grešaka.

Hemingovi kodovi

Ako se više bitova za ispravljanje grešaka uključe u poruci, i ako se ovi bitovi mogu organizovati tako da različiti pogrešni bitovi daju različite rezultate grešaka, onda loš bit može da se identifikuje. U 7-bitnoj poruci, postoji sedam mogućih jedno bitnih grešaka, pa tri bita za kontrolu grešaka mogu potencijalno da preciziraju, ne samo pojavu greške, nego i bit koji je izazvao grešku.

Heming je proučavao postojeće šeme kodiranja, uključujući i dve od pet i generalizovao je njihov koncept. Za početak, on je razvio nomenklaturu za opis sistema, uključujući i broj bitnih podataka i bitova za ispravljanje greške u bloku. Na primer, parnost sadrži jedan bit za bilo koju reč podataka, pa pod pretpostavkom ASCII reči sa 7-bita, Heming je ovo opisao kao (8,7) kod, sa osam bitova ukupno, od kojih su 7 podaci. Primer ponavljanja bi bio (3,1), koji sledi istu logiku. Kod vrednosti koda drugi broj se deli sa prvim, u našem primeru ponavljanja, 1/3.

Heming je takođe uočio probleme sa okretanjem dva ili više bita, i opisao je to kao "rastojanje" (posle njega nazavna Hemingova distanca). Parnost ima distancu 2, i kako se bilo koja dva bita okrenu oni će biti nevidljivi. Ponavljanje (3,1) ima distancu 3, kako tri bita treba da budu okrenuta u istoj trostrukosti da bi se dobio neki drugi kod bez vidljivih grešaka. Ponavljanje (4,1) (svaki bit se ponavlja četiri puta) ima distancu 4, tako da se prevrtanja dva bita može otkriti, ali ne i ispraviti. Kada se tri bita okrenu u istoj grupi ne može da se dogodi situacija u kojoj kod ispravlja prema pogrešnoj kodnoj reči.

Heming je bio zainteresovan za dva problema odjednom; povećanje distance što je više moguće, i u isto vreme povećanje kodne vrednosti što je više moguće. Tokom 1940-ih je razvio nekoliko šema kodiranja koje su dramatično poboljšane na postojećim kodovima. Ključ njegovih sistema je da imaju preklopljene parne bitove, tako da oni uspevaju da provere jedan drugog, kao i podatake.

Opšti algoritam

Sledeći opšti algoritam generiše kod za ispravljanje jedne greške (SEC) za bilo koji broj bitova.

1. Broj bita počinje od 1: bit 1, 2, 3, 4, 5, itd
2. Brojeve bita se pišu binarno: 1, 10, 11, 100, 101, itd
3. Sve bitne pozicije koje su jačine dva (imaju samo jedan 1 bit u binarnom obliku njihovog položaja) jesu parni bitovi: 1, 2, 4, 8, itd (1, 10, 100, 1000)
4. Sve ostale bit pozicije, sa dva ili više bita 1 u binarnom obliku njihovih položaja, su bit podaci.
5. Svaki bit podataka je uključen u jedinstveni skup od 2 ili više parnih bitova, kako je određeno binarnim oblikom njihove pozicije.
   1. Bit parnosti 1 pokriva sve bitne pozicije koje imaju najmanje značajan bitni skup: bit 1 (parnost bita sama po sebi), 3, 5, 7, 9, itd
   2. Bit parnosti 2 pokriva sve bitne pozicije koje imaju drugi najmanje značajan bitni skup: bit 2 (parnost bita sama po sebi), 3, 6, 7, 10, 11, itd
   3. Bit parnosti 4 pokriva sve bitne pozicije koje imaju treći najmanje značajan bitni skup: bitovi 4-7, 12-15, 20-23, itd
   4. Bit parnosti 8 pokriva sve bitne položaje koji imaju četvrti najmanje značajan bitni skup: bitovi 8-15, 24-31, 40-47, itd
   5. U principu svaki bit parnosti pokriva sve bitove gde je bit nad bitovima I u poziciji parnosti i pozicije bita nisu nula.

Oblik parnosti je irelevantan. Čak je parnost jednostavnija sa stanovišta teorijske matematike, ali u praksi ne postoji razlika.

Ovo opšte pravilo može da se vizuelno prikaže na sledeći način:

Pozicija bita		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	...
Šifrovani podaci bita		p1	p2	d1	p4	d2	d3	d4	p8	d5	d6	d7	d8	d9	d10	d11	p16	d12	d13	d14	d15
Parnost bitne pokrivenosti	p1	X		X		X		X		X		X		X		X		X		X
	p2		X	X			X	X			X	X			X	X			X	X
	p4				X	X	X	X					X	X	X	X					X
	p8								X	X	X	X	X	X	X	X
	p16																X	X	X	X	X

Prikazano je samo 20 kodiranih bitova (5 parnost, 15 podataka), ali obrazac se nastavlja unedogled. Ključna stvar u vezi Hemingovih kodova, koja može da se vidi iz vizuelnog uvida, jeste da je bilo koji dati bit uključen u jedinstveni skup parnih bitova. Da bi se proverile greške, treba da se provere sve parnosti bita. Obrazac grešaka, koji se zove sindrom greške, identifikuje bit u greški. Ako su svi bitovi parnosti ispravni, nema greške. Inače, zbir pozicija pogrešnih parnosti bitova identifikuje pogrešan bit. Na primer, ako parnost bita na pozicijama 1, 2 i 8 ukazuje na grešku, tada je bit 1 +2 +8 = 11 u greški. Ako samo jedna parnost bita ukazuje na grešku, parnost samog bita je u greški.

Kao što može videti, ako postoji $m$ parnih bitova, on može da pokrije bitove od 1 do $2^{m}-1$. Ako oduzmemo parnost bita, ostaje $2^{m}-m-1$ bita koji mogu da se koriste za podatke. Kako $m$ varira, tako se dobijaju svi moguće Hemingovi kodovi:

Bitovi parnosti	Ukupan broj bitova	Bitovi podataka	Ime	Brzina
2	3	1	Heming(3,1) (Trostruko ponavljanje koda)	1/3 ≈ 0.333
3	7	4	Heming(7,4)	4/7 ≈ 0.571
4	15	11	Heming(15,11)	11/15 ≈ 0.733
5	31	26	Heming(31,26)	26/31 ≈ 0.839
...
$m$	$2^{m}-1$	$2^{m}-m-1$	Hamming$(2^{m}-1,2^{m}-m-1)$	$(2^{m}-m-1)/(2^{m}-1)$

Ako je, dodatno, uključena ukupna parnost bita (bit 0), kod može da otkrije (ali ne i ispravi) bilo koju dvobitnu grešku, praveći SECDED kod. Ukupna parnost pokazuje da li je ukupan broj grešaka paran ili neparan. Ako osnovni Hemingov kod detektuje grešku, a ukupna parnost pokaže da postoji još veći broj grešaka, javlja se neispravljena 2-bitna greška.

Hemingovi kodovi sa dodatnom parnošću (SECDED)

Hemingovi kodovi imaju minimalnu distancu od 3, što znači da dekoder može da otkrije i ispravi jednu grešku, ali on ne može da razlikuje dvostruku bitnu grešku neke kodne reči iz jedno bitne greške drugačije kodne reči. Dakle, oni mogu da otkriju duple-bitne greške samo ako se nije pokušalo sa korekcijom.

Kao lek za ovaj nedostatak, Hemingovi kodovi mogu da se produže pomoću ekstra parnog bita. Na ovaj način, moguće je povećati minimalnu distancu Hemingovog koda na 4, koji omogućava da dekoder napravi razliku između jedno-bitnih grešaka i dvobitnih grešaka. Tako dekoder može da otkrije i ispravi jednu grešku i istovremeno otkrije (ali ne i ispravi) duplu grešku. Ako dekoder ne pokušava da ispravi greške, tada on može da detektuje do 3 greške.

Ovako proširen Hemingov kod je popularan u računarskim memorijskim sistemima, gde je poznat kao SECDED ("single error correction, double error detection" – "korekcija jedne greške, detekcija duple greške"). Posebno je popularan (72,64) kod, skraćeni (127,120) Hemingov kod plus dodatnih parni bit, koji ima isti prostor kao gornji (9,8) parni kod.

[7,4] Hemingov kod

Grafički prikaz 4 bitnih podataka i 3 parnog bita i koji parni bitovi s eprimenjuju u bitovima podataka

Godine 1950, Heming je uveo [7,4] Hemingov kod. On kodira 4 bitnih podataka u 7 bitova dodavanjem tri parna bita. On može da otkrije i ispravi jednobitne greške. Sa dodatkom ukupne parnosti bita, takođe može da otkrije (ali ne ispravi) dvostruke bitne greške.

Konstrukcija G i H

Matrica $\mathbf {G} :={\begin{pmatrix}I_{k}|-A^{T}\\\end{pmatrix}}$ se zove (Kanonična) generator matrica linearnog (n, k) koda,

i $\mathbf {H} :={\begin{pmatrix}A|I_{n-k}\\\end{pmatrix}}$ se zove matrica za proveru parnosti.

Ovo je konstrukcija G i H u standardnom (ili sistematskom) obliku. Bez obzira na formu, G i H za linearne blok kodove moraju da zadovolje.

$\mathbf {H} \,\mathbf {G} ^{T}=\mathbf {0}$, je sve nulta matrica.

Posle je [7,4,3]=[n,k,d]=[2^m − 1, 2^m−1-m, m]. Matrica provere parnosti H, Hemingovog koda je izrađena pomoću listinga svih kolona dužine m koje su "pair-wise" nezavisne.

Tako H je matrica čija je leva strana u svemu ne nulta n-torka gde redosled n-torke u kolonama matrice nije bitna. Desna strana je samo (n-k) - matrica identiteta.

Tako G se može dobiti iz H uzimajući transponovanje leve strane H sa identitetom matrice k-identiteta na levoj strani G.

Kod generatorske matrice $\mathbf {G}$ i matrica provere parnosti $\mathbf {H}$ su:

$\mathbf {G} :={\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}_{4,7}$

i

$\mathbf {H} :={\begin{pmatrix}1&1&0&1&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1\\\end{pmatrix}}_{3,7}.$

Konačno, ove matrice mogu da mutiraju u ekvivalentne nesistematske kodove pomoću sledećih operacija:

• Permutacije kolona (zamene kolona)
• Elementgarni red operacija (zamena reda sa linearnom kombinacijom redova)

Kodiranje

Primer

Iz gorenavedene matrice imamo 2^k=2⁴=16 kodnih reči. U kodne reči ovog binarnog koda mogu se dobiti od ${\vec {x}}={\vec {a}}G$. Sa ${\vec {a}}=a_{1}a_{2}a_{3}a_{4}$ sa $a_{i}$ postoji u $F_{2}$ (A polje sa dva elementa i to 0 i 1).

Tako su kodne reči sve 4-torke (K-torke).

Zbog toga,

(1,0,1,1) biva kodiran kao (1,0,1,1,0,1,0).

[7,4] Heming kod sa dodatnim parnim bitom

Isti [7,4] gornji primer sa ekstra parnim bitom. Dijagram sa ovim primerom ne odgovara H matrici.

[7,4] Hemingov kod može se lako proširiti na [8,4] kod dodavanjem ekstra parnog bita na vrhu (7,4) kodirane reči (videti Heming (7,4)). Ovo se može sumirati sa revidiranim matricama:

$\mathbf {G} :={\begin{pmatrix}1&1&1&0&0&0&0&1\\1&0&0&1&1&0&0&1\\0&1&0&1&0&1&0&1\\1&1&0&1&0&0&1&0\end{pmatrix}}_{4,8}$

i

$\mathbf {H} :={\begin{pmatrix}1&0&1&0&1&0&1&0\\0&1&1&0&0&1&1&0\\0&0&0&1&1&1&1&0\\1&1&1&1&1&1&1&1\end{pmatrix}}_{4,8}.$

Primećuje se da H nije u standardnom obliku. Za dobijanje G, elementarne redne operacije mogu da se koriste da bi se dobila ekvivalentna matrica za H u sistematskom obliku:

$\mathbf {H} =\left(\left.{\begin{array}{cccc}0&1&1&1\\1&0&1&1\\1&1&0&1\\1&1&1&0\end{array}}\right|{\begin{array}{cccc}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{array}}\right)_{4,8}.$

Na primer, prvi red ove matrice je zbir drugog i trećeg reda H u ne-sistematskom obliku. Kada se koristi sistematska izgradnja za Hemingove gornje kodove, matrica A je očigledna i sistematski oblik G je napisan kao:

$\mathbf {G} =\left(\left.{\begin{array}{cccc}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{array}}\right|{\begin{array}{cccc}0&1&1&1\\1&0&1&1\\1&1&0&1\\1&1&1&0\end{array}}\right)_{4,8}.$

Nesistematski oblik G može da bude redukovani red (korišćenjem osnovnih rednih operacija) da bi odgovarao ovaj matrici.

Dodavanjem četvrtog reda efikasno se izračunava zbir svih kodnih reči bita (podaci i parnost) kao i četvrti parni bit.

Na primer, 1011 je kodiran u 01100110 gde su plave cifre podaci, crvene cifre su parnost iz [7,4] Hemingovog koda, i zelena cifra je parnost dodata sa [8,4] kodom. Zelena cifra čini parnost u [7,4] koda.

Konačno, može se pokazati da se minimalna distanca (udaljenost) povećava sa 3, sa [7,4] kodom, do 4 sa [8,4] kodom. Zbog toga, kod se može definisati kao [8,4] Hemingov kod.

Vidi još

• Hemingovo rastojanje
• Hemingov kod (7,4)

Literatura

• Moon, Todd K. (2005). Error Correction Coding. New Jersey: John Wiley & Sons. ISBN 978-0-471-64800-0. 
• MacKay, David J.C. (2003). Information Theory, Inference and Learning Algorithms. Cambridge: Cambridge University Press. ISBN 978-0-521-64298-9. 
• D.K. Bhattacharryya, S. Nandi. „An efficient class of SEC-DED-AUED codes”. 1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97). str. 410—415. doi:10.1109/ISPAN.1997.645128.