 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Коды Хэмминга
|
Читайте также: |
Код Хэмминга является групповым (n, k)-кодом с минимальным расстоянием d = 3, который позволяет обнаруживать и исправлять однократные ошибки. Для построения кода Хэмминга используется порождающая матрица, которая имеет вид
,
где Ak ´( n – k ) - матрица двоичных элементов, Ik - единичная матрица, k – число информационных разрядов кода, n – общее число разрядов кода. Порождающей матрице соответствует проверочная матрица
.
Матрица Ak ´( n – k ) содержит k строк, представляющих все возможные двоичные комбинации длины n – k с не менее чем двумя единицами. Например, (7, 4)-код Хэмминга из таблицы 7.3 имеет следующие порождающую и проверочную матрицы:
Таблица 7.3
(7, 4)-код Хэмминга
| Исходный код | Код Хэмминга | Исходный код | Код Хэмминга | Исходный код | Код Хэмминга | Исходный код | Код Хэмминга |
Данный код является систематическим. Это значит, что каждую кодовую комбинацию можно представить как
e 1 e 2… en – kx 1 x 2… xk,
где 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 ( n–k )´ n не должна содержать одинаковых столбцов, а строки матрицы Ak ´( n – k ) должны содержать, по крайней мере, две единицы.
Поиск по сайту: