Хамингов код (7,4)

Хамингов(7,4)-код
Хамингов(7,4)-код
Именован по	Ричарду Хамингу
Параметери
Дужина блока	7
Дужина поруке	4
Стопа	4/7 ~ 0.571
Растојање	3
Величина алфабета	2
Нотација	[7,4,3]2-code
Својства
	савршени код
	п; р; у;

У теорији кодирања Хамингов код (7,4) је линеарни код за корекцију грешке који кодира 4 бита података у 7 битова тако што додаје 3 бита парности. Хамингов код (7,4) је део веће породице Хамингових кодова, али термин Хамингов код се обично односи на овај специфични код који је 1950. године увео Ричард Хаминг. Својевремено, Хаминг је радио у Bell Labs-у и био је фрустриран грешкама читача за бушене картице, због тога је почео да ради на кодовима за исправљање грешака.^[1]

Графички приказ 4-бита података d₁ до d₄, и 3 бита парности p₁ до p₃, и који бит парности користи коју магистралу података

Хамингов код додаје 3 додатна бита провере сваком четвртом биту податка у поруци. Хамингов (7,4) алгоритам може да исправи сваку једно-битну грешку, или да детектује све једнобитне и двобитне грешке. Другим речима, минимално Хамингово растојање између било две кодиране речи је 3, и примљене речи могу бити исправно декодиране ако су на растојању од највише једане кодне речи која је прослеђена од пошиљаоца. То значи да за пренос средњег случаја где се енгл. burst грешке не извршавају, Хамингов код (7,4) је ефикасан.

Циљ

Циљ Хаминговог кода је да креира скуп парности бита који се преклапају тако да једно-битна грешка (вредност бита је логички је флипована) у биту податка или парности бита може бити детектована и исправљена. Док може да се креира више преклапања, општи метод је представљен у Хаминговим кодовима.

Бит#	1	2	3	4	5	6	7
Преносиви бит	$p_{1}$	$p_{2}$	$d_{1}$	$p_{3}$	$d_{2}$	$d_{3}$	$d_{4}$
$p_{1}$	Да	Не	Да	Не	Да	Не	Да
$p_{2}$	Не	Да	Да	Не	Не	Да	Да
$p_{3}$	Не	Не	Не	Да	Да	Да	Да

Ова табела описује који бит парности покрива које преносне битове у кодираној речи. На пример, p₂ обезбеђује парну парност за битове 2, 3, 6, & 7. Она такође, читајући колоне, детаљно описује који бит преноси који бит парности На пример, d₁ је покривено са p₁ и p₂ али не са p₃. Ова табела ће упадљиво личити на матрицу провере парности (H) у седећој секцији.

Штавише, ако су колоне парности у горњој табели уклоњене

	$d_{1}$	$d_{2}$	$d_{3}$	$d_{4}$
$p_{1}$	Да	Да	Не	Да
$p_{2}$	Да	Не	Да	Да
$p_{3}$	Не	Да	Да	Да

затим сличност са редовима 1, 2, & 4 генератора кода матрице (G) испод, такође ће бити очигледна.

Дакле, правилно бирајући покривеност бита парности, све грешке са Хаминговим растојањем од 1, могу да се открију и исправе, што је и поента коришћења Хаминговог кода.

Хамингове матрице

Хамингови кодови се могу рачунати у терминима линеарне алгебре матрице, зато што су Хамингови кодови линеарни кодови. За сврхе Хамингових кодова, две Хамингове матрице се могу дефинисати: код генератора матрице G и матрица провере парности 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}}.

Бит позиција податка и бит парности

Као што смо у делу изнад As mentioned above, rows 1, 2, & 4 of G should look familiar as they map the data bits to their parity bits:

Све кодне речи

Пошто је извор само 4 бита онда постоји само 16 могућих преносивих речи. Укључена је 8-битна вредност уколико се користи додатни бит парности (Битови података су приказани у плавој боји, парност бита је приказана у црвеној боји, и екстра парност бита је приказана у зеленој боји.)

Подаци $({\color {blue}d_{1}},{\color {blue}d_{2}},{\color {blue}d_{3}},{\color {blue}d_{4}})$	Хаминг(7,4)		Хаминг(7,4) са екстра битом парности (Хаминг(8,4))
	Пренесено $({\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 {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}})$	Дијаграм
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