Хамингов код (7,4)
У теорији кодирања Хамингов код (7,4) је линеарни код за корекцију грешке који кодира 4 бита података у 7 битова тако што додаје 3 бита парности. Хамингов код (7,4) је део веће породице Хамингових кодова, али термин Хамингов код се обично односи на овај специфични код који је 1950. године увео Ричард Хаминг. Својевремено, Хаминг је радио у Bell Labs-у и био је фрустриран грешкама читача за бушене картице, због тога је почео да ради на кодовима за исправљање грешака.[1]
Хамингов(7,4)-код | |
---|---|
Именован по | Ричарду Хамингу |
Параметери | |
Дужина блока | 7 |
Дужина поруке | 4 |
Стопа | 4/7 ~ 0.571 |
Растојање | 3 |
Величина алфабета | 2 |
Нотација | [7,4,3]2-code |
Својства | |
савршени код | |
Хамингов код додаје 3 додатна бита провере сваком четвртом биту податка у поруци. Хамингов (7,4) алгоритам може да исправи сваку једно-битну грешку, или да детектује све једнобитне и двобитне грешке. Другим речима, минимално Хамингово растојање између било две кодиране речи је 3, и примљене речи могу бити исправно декодиране ако су на растојању од највише једане кодне речи која је прослеђена од пошиљаоца. То значи да за пренос средњег случаја где се енгл. burst грешке не извршавају, Хамингов код (7,4) је ефикасан.
Циљ
уредиЦиљ Хаминговог кода је да креира скуп парности бита који се преклапају тако да једно-битна грешка (вредност бита је логички је флипована) у биту податка или парности бита може бити детектована и исправљена. Док може да се креира више преклапања, општи метод је представљен у Хаминговим кодовима.
Бит# 1 2 3 4 5 6 7 Преносиви бит Да Не Да Не Да Не Да Не Да Да Не Не Да Да Не Не Не Да Да Да Да
Ова табела описује који бит парности покрива које преносне битове у кодираној речи. На пример, p2 обезбеђује парну парност за битове 2, 3, 6, & 7. Она такође, читајући колоне, детаљно описује који бит преноси који бит парности На пример, d1 је покривено са p1 и p2 али не са p3. Ова табела ће упадљиво личити на матрицу провере парности (H) у седећој секцији.
Штавише, ако су колоне парности у горњој табели уклоњене
Да Да Не Да Да Не Да Да Не Да Да Да
затим сличност са редовима 1, 2, & 4 генератора кода матрице (G) испод, такође ће бити очигледна.
Дакле, правилно бирајући покривеност бита парности, све грешке са Хаминговим растојањем од 1, могу да се открију и исправе, што је и поента коришћења Хаминговог кода.
Хамингове матрице
уредиХамингови кодови се могу рачунати у терминима линеарне алгебре матрице, зато што су Хамингови кодови линеарни кодови. За сврхе Хамингових кодова, две Хамингове матрице се могу дефинисати: код генератора матрице G и матрица провере парности H:
Као што смо у делу изнад 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-битна вредност уколико се користи додатни бит парности (Битови података су приказани у плавој боји, парност бита је приказана у црвеној боји, и екстра парност бита је приказана у зеленој боји.)
Референце
уреди- ^ „History of Hamming Codes”. Архивирано из оригинала 25. 10. 2007. г. Приступљено 3. 4. 2008.