АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Коды Хэмминга

Читайте также:
  1. Код Хэмминга

Код Хэмминга является групповым (n, k)-кодом с минимальным расстоянием d = 3, который позволяет обнаруживать и исправлять однократные ошибки. Для построения кода Хэмминга используется порождающая матрица, которая имеет вид

,

где Ak ´( n k ) - матрица двоичных элементов, Ik - единичная матрица, k – число информационных разрядов кода, n – общее число разрядов кода. Порождающей матрице соответствует проверочная матрица

.

Матрица Ak ´( n k ) содержит k строк, представляющих все возможные двоичные комбинации длины nk с не менее чем двумя единицами. Например, (7, 4)-код Хэмминга из таблицы 7.3 имеет следующие порождающую и проверочную матрицы:

Таблица 7.3

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

Исходный код Код Хэмминга Исходный код Код Хэмминга Исходный код Код Хэмминга Исходный код Код Хэмминга
               
               
               
               

 

Данный код является систематическим. Это значит, что каждую кодовую комбинацию можно представить как

e 1 e 2en kx 1 x 2xk,

где e 1, e 2,..., en k – проверочные символы, x 1, x 2, …, xk – информационные символы. С помощью порождающей матрицы Gk ´ n из исходной кодовой k -символьной комбинации Ck получается n -символьный код Хэмминга Xn следующим образом:

Xn = CkGk ´ n.

Обнаружение ошибок основано на том, что для разрешенных кодовых комбинаций справедливо равенство

.

Поэтому если результат операции (синдром) не будет нулевым, то можно сделать вывод о том, что кодовая комбинация содержит ошибку. В этом случае определяется номер строки транспонированной проверочной матрицы , равной синдрому, который и будет номером разряда кодовой комбинации, содержащим ошибку. Например, пусть вместо комбинации 0011010 была получена комбинация 0111010. Тогда синдром равен

,

что соответствует второй строке проверочной матрицы и, значит, ошибка обнаружена во втором разряде кодовой комбинации. После исправления символа во втором разряде с 1 на 0 получим правильную комбинацию:

0011010.

При построении кода Хэмминга необходимо учитывать, что проверочная матрица H ( nk )´ n не должна содержать одинаковых столбцов, а строки матрицы Ak ´( n k ) должны содержать, по крайней мере, две единицы.


1 | 2 | 3 | 4 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)