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

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

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

Хамингов код додаје 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 Не Не Не Да Да Да Да

Ова табела описује који бит парности покрива које преносне битове у кодираној речи. На пример, p2 обезбеђује парну парност за битове 2, 3, 6, & 7. Она такође, читајући колоне, детаљно описује који бит преноси који бит парности На пример, d1 је покривено са p1 и p2 али не са p3. Ова табела ће упадљиво личити на матрицу провере парности (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 Хамингов код за 0000 постаје 0000000 00000000 Хамингов код за 0000 постаје 0000000 са екстра битом парности 0
1000 1110000 Хамингов код за 1000 постаје1000011 11100001 Хамингов код за 1000 постаје 1000011 са екстра битом парности 1
0100 1001100 Хамингов код за 0100 постаје 0100101 10011001 Хамингов код за 0100 постаје 0100101 са екстра битом парности 1
1100 0111100 Хамингов код за 1100 постаје 1100110 01111000 Хамингов код за 1100 постаје 1100110 са екстра битом парности 0
0010 0101010 Хамингов код за 0010 постаје 0010110 01010101 Хамингов код за 0010 постаје 0010110 са екстра битом парности 1
1010 1011010 Хамингов код за 1010 постаје 1010101 10110100 Хамингов код за 1010 постаје 1010101 са екстра битом парности 0
0110 1100110 Хамингов код за 0110 постаје 0110011 11001100 Хамингов код за 0110 постаје 0110011 са екстра битом парности 0
1110 0010110 Хамингов код за 1110 постаје 1110000 00101101 Хамингов код за 1110 постаје 1110000 са екста битом парности 1
0001 1101001 Хамингов код за 0001 постаје 0001111 11010010 Хамингов код за 0001 постаје 0001111 са екстра битом парности 0
1001 0011001 Хамингов код за 1001 постаје 1001100 00110011 Хамингов код за 1001 постаје 1001100 са екстра битом парности 1
0101 0100101 Хамингов код за 0101 постаје 0101010 01001011 Хамингов код за 0101 постаје 0101010 са екстра битом парности 1
1101 1010101 Хамингов код за 1101 постаје 1101001 10101010 Хамингов код за 1101 постаје 1101001 са екстра битом парности 0
0011 1000011 Хамингов код за 0011 постаје 0011001 10000111 Хамингов код за 0011 постаје 0011001 са екстра битом парности 1
1011 0110011 Хамингов код за 1011 постаје 1011010 01100110 Хамингов код за 1011 постаје 1011010 са екстра битом парности 0
0111 0001111 Хамингов код за 0111 постаје 0111100 00011110 Хамингов код за 0111 постаје 0111100 са екстра битом парности 0
1111 1111111 Хамингов код за 1111 постаје 1111111 11111111 Хамингов код за 1111 постаје 1111111 са једним екстра битом парности

Референце[уреди]

  1. ^ „History of Hamming Codes“ Приступљено 3. 4. 2008..