Hamingov kod (7,4)

U teoriji kodiranja Hamingov kod (7,4) je linearni kod za korekciju greške koji kodira 4 bita podataka u 7 bitova tako što dodaje 3 bita parnosti. Hamingov kod (7,4) je deo veće porodice Hamingovih kodova, ali termin Hamingov kod se obično odnosi na ovaj specifični kod koji je 1950. godine uveo Ričard Haming. Svojevremeno, Haming je radio u Bell Labs-u i bio je frustriran greškama čitača za bušene kartice, zbog toga je počeo da radi na kodovima za ispravljanje grešaka.

Hamingov(7,4)-kod
Imenovan po	Ričardu Hamingu
Parameteri
Dužina bloka	7
Dužina poruke	4
Stopa	4/7 ~ 0.571
Rastojanje	3
Veličina alfabeta	2
Notacija	[7,4,3]2-code
Svojstva
savršeni kod

Grafički prikaz 4-bita podataka d₁ do d₄, i 3 bita parnosti p₁ do p₃, i koji bit parnosti koristi koju magistralu podataka

Hamingov kod dodaje 3 dodatna bita provere svakom četvrtom bitu podatka u poruci. Hamingov (7,4) algoritam može da ispravi svaku jedno-bitnu grešku, ili da detektuje sve jednobitne i dvobitne greške. Drugim rečima, minimalno Hamingovo rastojanje između bilo dve kodirane reči je 3, i primljene reči mogu biti ispravno dekodirane ako su na rastojanju od najviše jedane kodne reči koja je prosleđena od pošiljaoca. To znači da za prenos srednjeg slučaja gde se engl. burst greške ne izvršavaju, Hamingov kod (7,4) je efikasan.

Cilj

Cilj Hamingovog koda je da kreira skup parnosti bita koji se preklapaju tako da jedno-bitna greška (vrednost bita je logički je flipovana) u bitu podatka ili parnosti bita može biti detektovana i ispravljena. Dok može da se kreira više preklapanja, opšti metod je predstavljen u Hamingovim kodovima.

Bit#	1	2	3	4	5	6	7
Prenosivi bit	$p_{1}$	$p_{2}$	$d_{1}$	$p_{3}$	$d_{2}$	$d_{3}$	$d_{4}$
$p_{1}$	Da	Ne	Da	Ne	Da	Ne	Da
$p_{2}$	Ne	Da	Da	Ne	Ne	Da	Da
$p_{3}$	Ne	Ne	Ne	Da	Da	Da	Da

Ova tabela opisuje koji bit parnosti pokriva koje prenosne bitove u kodiranoj reči. Na primer, p₂ obezbeđuje parnu parnost za bitove 2, 3, 6, & 7. Ona takođe, čitajući kolone, detaljno opisuje koji bit prenosi koji bit parnosti Na primer, d₁ je pokriveno sa p₁ i p₂ ali ne sa p₃. Ova tabela će upadljivo ličiti na matricu provere parnosti (H) u sedećoj sekciji.

Štaviše, ako su kolone parnosti u gornjoj tabeli uklonjene

	$d_{1}$	$d_{2}$	$d_{3}$	$d_{4}$
$p_{1}$	Da	Da	Ne	Da
$p_{2}$	Da	Ne	Da	Da
$p_{3}$	Ne	Da	Da	Da

zatim sličnost sa redovima 1, 2, & 4 generatora koda matrice (G) ispod, takođe će biti očigledna.

Dakle, pravilno birajući pokrivenost bita parnosti, sve greške sa Hamingovim rastojanjem od 1, mogu da se otkriju i isprave, što je i poenta korišćenja Hamingovog koda.

Hamingove matrice

Hamingovi kodovi se mogu računati u terminima linearne algebre matrice, zato što su Hamingovi kodovi linearni kodovi. Za svrhe Hamingovih kodova, dve Hamingove matrice se mogu definisati: kod generatora matrice G i matrica provere parnosti H:

$\mathbf {G} :={\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&0&0&0\\0&1&1&1\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\end{pmatrix}},\qquad \mathbf {H} :={\begin{pmatrix}1&0&1&0&1&0&1\\0&1&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}.$

Bit pozicija podatka i bit parnosti

Kao što smo u delu iznad As mentioned above, rows 1, 2, & 4 of G should look familiar as they map the data bits to their parity bits:

Sve kodne reči

Pošto je izvor samo 4 bita onda postoji samo 16 mogućih prenosivih reči. Uključena je 8-bitna vrednost ukoliko se koristi dodatni bit parnosti (Bitovi podataka su prikazani u plavoj boji, parnost bita je prikazana u crvenoj boji, i ekstra parnost bita je prikazana u zelenoj boji.)

Podaci $({\color {blue}d_{1}},{\color {blue}d_{2}},{\color {blue}d_{3}},{\color {blue}d_{4}})$	Haming(7,4)		Haming(7,4) sa ekstra bitom parnosti (Haming(8,4))
	Preneseno $({\color {red}p_{1}},{\color {red}p_{2}},{\color {blue}d_{1}},{\color {red}p_{3}},{\color {blue}d_{2}},{\color {blue}d_{3}},{\color {blue}d_{4}})$	Dijagram	Preneseno $({\color {red}p_{1}},{\color {red}p_{2}},{\color {blue}d_{1}},{\color {red}p_{3}},{\color {blue}d_{2}},{\color {blue}d_{3}},{\color {blue}d_{4}},{\color {green}p_{4}})$	Dijagram
0000	0000000		00000000
1000	1110000		11100001
0100	1001100		10011001
1100	0111100		01111000
0010	0101010		01010101
1010	1011010		10110100
0110	1100110		11001100
1110	0010110		00101101
0001	1101001		11010010
1001	0011001		00110011
0101	0100101		01001011
1101	1010101		10101010
0011	1000011		10000111
1011	0110011		01100110
0111	0001111		00011110
1111	1111111		11111111

Spoljašnje veze

• A programming problem about the Hamming Code(7,4)