Определите вектор однократной ошибки для принятой кодовой комбинации 0100111 кода хэмминга 7 4

В
качестве примера (n,k)-кода,
при задании которого используется
матричное представление, рассмотрим
код Хэмминга – код с кодовым расстоянием
d=3,
позволяющий исправлять все одиночные
ошибки. Для кода Хэмминга число разрешённых
кодовых комбинаций равно верхней границе
– 2ⁿ/(n+ 1).
Первые k разрядов
кодовых комбинация используются в
качестве информационных, их число равно:

Данное уравнение имеет
целочисленные решения k=0,1,4,11,26,…,
которые и определяют соответствующие
коды Хэмминга: (3, 1), (7, 4), (15,11) и т.д.
Рассмотрим построение (7, 4)-кода. Для
этого воспользуемся каноническим
представлением порождающей матрицы.
Одним из свойств порождающей матрицы
является то, что для различных кодовых
комбинаций, составленных из информационных
разрядов, должны быть различными и
проверочные разряды. Так как все
вектор-строки единичной подматрицы
матрицы G_n_,_k
различны, то и подматрица проверочных
разрядов должна состоять из различных
ненулевых строк (общее число ненулевых
строк должно быть равно 2^r–1).

Вычтем
из возможного числа ненулевых строк r
строк, образующих единичную матрицу ,
которую следует добавить к транспонированной
подматрице проверочных разрядов при
определении проверочной матрицы. Тогда
останется 2^r–1–r
r-разрядных строк с
числом единиц не меньше двух. Для кода
Хэмминга это число как раз равно числу
информационных разрядов. Для (n,
k)-кода число различных
r-разрядных строк с
числом единиц не меньше двух равно числу
строк в порождающей матрице. Это свойство
позволяет составить непосредственно
один из вариантов порождающей матрицы
(7, 4)-кода, например, такой:

Учитывая связь элементов порождающей
и проверочной матриц, представленных
в канонической форме, имеем:

Проверим способность
разработанного (7, 4) кода исправлять
одиночные ошибки. Пусть передаваемая
кодовая комбинация v
(7,4)-кода образована
путём сложения первой, второй и четвёртой
строк матрицы G_7,4,
тогда v=1101001.

Предположим,
что при передаче по каналу произошла
ошибка в третьем разряде кодовой
комбинации v. В этом
случае на приёмной стороне канала будет
получена кодовая комбинация v‘=1111001.
Умножим принятую кодовую комбинацию
на транспонированную проверочную
матрицу H_7,4:

Отличие от нуля синдрома
говорит о том, что произошла ошибка.
Чтобы определить, в каком разряде кодовой
комбинации произошла ошибка, проверим,
с какой строкой матрицы транспонированной
матрицы H_7,4
совпадает синдром. Как видно, он совпадает
с третьей строкой. Следовательно, ошибка
произошла в третьем разряде кодовой
комбинации. В декодирующих устройствах
систем передачи информации результат
перемножения принятой кодовой комбинации
на проверочную матрицу (синдром ошибки)
используется для автоматического
исправления соответствующего разряда.

13.5 Циклические коды

Циклическим
кодом называется линейный код, который
представляет собой конечное множество,
замкнутое относительно операции
циклического сдвига кодовых векторов,
образующих его. Пусть дан n-мерный
вектор v=a₀a₁…a_n_-1
с координатами из конечного поля F.
Его циклическим сдвигом называется
вектор v‘=a_n_-1a₀a₁…a_n_-2.

Рассмотрим
n-мерное арифметическое
пространство над полем Галуа GF(2).
Каждому вектору a₀a₁…a_n_-1
из GF(2) можно сопоставить
взаимно однозначно многочлен
a₀+a₁x+…+a_n_-1xⁿ^-1
с коэффициентами из GF(2).
Сумме двух векторов a₀a₁…a_n_-1
и b₀b₁…b_n_-1
ставится в соответствие сумма
соответствующих им многочленов,
произведению элементов поля на вектор
— произведение многочлена, соответствующего
этому вектору, на элемент.

Рассмотрим
некоторый многочлен g(x)
из описанного линейного пространства.
Множество всех многочленов из этого
подпространства, которые делятся без
остатка на g(x),
образует линейное подпространство.
Линейное подпространство определяет
некоторый линейный код.

Линейный
код, образованный классом многочленов
C(g(x)),
кратных некоторому полиному g(x),
называемому порождающим многочленом,
называется полиномиальным.

Покажем,
как связаны полиномиальные коды C(g(x))
и циклические коды. Пусть a=a₀…a_n_-1
– некоторое кодовое слово, а соответствующий
кодовый многочлен a(x)=a₀+…+a_n_-1xⁿ^-1.
Циклическому сдвигу a‘
соответствует кодовый многочлен
a‘(x)=a_n_-1+a₀x+…+a_n_-2xⁿ^-1,
который можно выразить через первоначальный:

Поскольку полиномиальный
код должен делиться на g(x),
то для того, чтобы он был циклическим,
многочлен a‘(x)
должен делиться на g(x).
Из этого соображения можно сформулировать
следующую теорему. Полиномиальный код
является циклическим тогда и только
тогда, когда многочлен g(x)
является делителем многочлена xⁿ–1.
В этом случае многочлен g(x)
называется порождающим многочленом
циклического кода.

В
теории кодирования доказывается
следующая теорема: если многочлен g(x)
имеет степень n–k
и является делителем xⁿ–1,
то C(g(x))
является линейным циклическим
(n,k)-кодом.

Многочлен
xⁿ–1 разложим
на множители xⁿ–1 = (x–1)(xⁿ^-1+xⁿ^-1+…+1).
Следовательно, циклические коды
существуют при любом n.
Число циклических n-разрядных
кодов равно числу делителей многочлена
xⁿ–1. Для
построения циклических кодов разработаны
таблицы разложения многочленов xⁿ–1
на неприводимые многочлены, то есть на
такие, которые делятся только на единицу
и на самого себя.

Рассмотрим,
например, какие коды можно построить
на основе многочлена x⁷–1
над полем GF(2). Разложение
многочлена на неприводимые множители
имеет вид

Поскольку можно образовать
шесть делителей многочлена x⁷–1,
комбинируя неприводимые делители,
существует шесть двоичных циклических
кодов. (n,k)-код
определяется, во-первых, значением n,
а во-вторых, значением k=n–s,
s – степень
многочлена-делителя xⁿ–1,
определяющего код. Ниже приведены
делители полинома и соответствующие
им значения k:

x– 1,s=1,k=6;

x³+x²+1,s=3,k=4;

x³+x+1,s=3,k=4;

(x–1)(x³+x²+1)=x⁴+x²+x+1,s=4,k=3;

(x–1)(x³+x+1)=x⁴+x³+x²+1,s=4,k=3;

(x³+x²+1)( x³+x+1)=x⁶+
x⁵+ x⁴+ x³+ x²+
x,s=6,k=1.

(7, 6)-код имеет лишь один проверочный
символ, а (7, 1)-код – лишь один
информационный. Они являются соответственно
кодом с проверкой на чётность и кодом
с повторением.

Как
и обычный линейный код, циклический код
может быть задан порождающей матрицей.
Следовательно, задача состоит в том,
чтобы найти такую матрицу, то есть найти
k линейно независимых
кодовых комбинаций, образующих её.
Воспользуемся для этого свойством
замкнутости циклического кода относительно
операции циклического сдвига. Заметим,
что циклический сдвиг вправо на один
разряд эквивалентен умножению многочлена
g(x)
на x. Тогда порождающую
матрицу можно построить, взяв в качестве
строк порождающий многочлен и k
его циклических сдвигов:

Например, рассмотрим один из
делителей многочлена x⁷–1,
а именно полином g(x)=1+x+x³.
Ему соответствует кодовая комбинация
1101000 (выписаны коэффициенты при степенях
0, 1, …, 6 порождающего многочлена, так
как кодовая комбинация содержит 7
символов). Тогда порождающая матрица
(7,4) имеет вид

Рассмотрим теперь, как с
помощью порождающего многочлена
g(x)=1+x+x³
осуществляется кодирование (7, 4)-кодом.
Возьмём, например, 4-разрядное слово
(0101), которому соответствует многочлен
f(x)=x+x³.
Перемножив эти два многочлена:

f(x)g(x) = (x+x³)(1+x+x³) =x+x²+x³+x⁶,

получим кодовую комбинацию 0111001.
Аналогично можно получить кодовые слова
для всех 4-разрядных двоичных слов.
Однако получившийся код, как видно, не
является разделимым, что неудобно для
практических нужд.

Чтобы
закодировать сообщение h(x)
циклическим кодом C(g(x)),
который является разделимым, нужно
разделить многочлен xⁿ^—^kh(x)
на g(x)
и прибавит остаток от деления к многочлену
xⁿ^—^kh(x).

Для
примера рассмотрим кодовую комбинацию
1101. Этому вектору соответствует полином
h(x)=1+x+x³.
Тогда xⁿ^—^kh(x)=x³+x⁴+x⁶.
Разделим получившийся многочлен на
g(x)=1+x+x³,
получим остаток, равный 0. Тогда кодовый
вектор равен 0001101.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

Корректирующие коды. Начало новой теории кодирования

Проблемы информационной безопасности требуют изучения и решения ряда теоретических и практических задач при информационном взаимодействии абонентов систем. В нашей доктрине информационной безопасности формулируется триединая задача обеспечения целостности, конфиденциальности и доступности информации. Представляемые здесь статьи посвящаются рассмотрению конкретных вопросов ее решения в рамках разных государственных систем и подсистем. Ранее автором были рассмотрены в 5 статьях вопросы обеспечения конфиденциальности сообщений средствами государственных стандартов. Общая концепция системы кодирования также приводилась мной ранее.

Введение

По основному своему образованию я не математик, но в связи с читаемыми мной дисциплинами в ВУЗе пришлось в ней дотошно разбираться. Долго и упорно читал классические учебники ведущих наших Университетов, пятитомную математическую энциклопедию, множество тонких популярных брошюр по отдельным вопросам, но удовлетворения не возникало. Не возникало и глубокое понимание прочитанного.

Вся математическая классика ориентирована, как правило, на бесконечный теоретический случай, а специальные дисциплины опираются на случай конечных конструкций и математических структур. Отличие подходов колоссальное, отсутствие или недостаток хороших полных примеров — пожалуй главный минус и недостаток вузовских учебников. Очень редко существует задачник с решениями для начинающих (для первокурсников), а те, что имеются, грешат пропусками в объяснениях. В общем я полюбил букинистические магазины технической книги, благодаря чему пополнилась библиотека и в определенной мере багаж знаний. Читать довелось много, очень много, но «не заходило».

Этот путь привел меня к вопросу, а что я уже могу самостоятельно делать без книжных «костылей», имея перед собой только чистый лист бумаги и карандаш с ластиком? Оказалось совсем немного и не совсем то, что было нужно. Пройден был сложный путь бессистемного самообразования. Вопрос был такой. Могу ли я построить и объяснить, прежде всего себе, работу кода, обнаруживающего и исправляющего ошибки, например, код Хемминга, (7, 4)-код?

Известно, что код Хемминга широко используется во многих прикладных программах в области хранения и обмена данными, особенно в RAID; кроме того, в памяти типа ECC и позволяет «на лету» исправлять однократные и обнаруживать двукратные ошибки.

Информационная безопасность. Коды, шифры, стегосообщения

Информационное взаимодействие путем обмена сообщениями его участников должно обеспечиваться защитой на разных уровнях и разнообразными средствами как аппаратными так и программными. Эти средства разрабатываются, проектируются и создаются в рамках определенных теорий (см. рис.А) и технологий, принятых международными договоренностями об OSI/ISO моделях.

Защита информации в информационных телекоммуникационных системах (ИТКС) становится практически основной проблемой при решении задач управления, как в масштабе отдельной личности – пользователя, так и для фирм, объединений, ведомств и государства в целом. Из всех аспектов защиты ИТКС в этой статье будем рассматривать защиту информации при ее добывании, обработке, хранении и передаче в системах связи.

Уточняя далее предметную область, остановимся на двух возможных направлениях, в которых рассматриваются два различных подхода к защите, представлению и использованию информации: синтаксическом и семантическом. На рисунке используются сокращения: кодек–кодер-декодер; шидеш – шифратор-дешифратор; скриз – скрыватель – извлекатель.

Рисунок А – Схема основных направлений и взаимосвязи теорий, направленных на решение задач защиты информационного взаимодействия

Синтаксические особенности представления сообщений позволяют контролировать и обеспечивать правильность и точность (безошибочность, целостность) представления при хранении, обработке и особенно при передаче информации по каналам связи. Здесь главные задачи защиты решаются методами кодологии, ее большой части — теории корректирующих кодов.

Семантическая (смысловая) безопасность сообщений обеспечивается методами криптологии, которая средствами криптографии позволяет защитить от овладения содержанием информации потенциальным нарушителем. Нарушитель при этом может скопировать, похитить, изменить или подменить, или даже уничтожить сообщение и его носитель, но он не сможет получить сведений о содержании и смысле передаваемого сообщения. Содержание информации в сообщении останется для нарушителя недоступным. Таким образом, предметом дальнейшего рассмотрения будет синтаксическая и семантическая защита информации в ИТКС. В этой статье ограничимся рассмотрением только синтаксического подхода в простой, но весьма важной его реализации корректирующим кодом.

Сразу проведу разграничительную линию в решении задач информационной безопасности:
теория кодологии призвана защищать информацию (сообщения) от ошибок (защита и анализ синтаксиса сообщений) канала и среды, обнаруживать и исправлять ошибки;
теория криптологии призвана защищать информацию от несанкционированного доступа к ее семантике нарушителя (защита семантики, смысла сообщений);
теория стеганологии призвана защищать факт информационного обмена сообщениями, а также обеспечивать защиту авторского права, персональных данных (защита врачебной тайны).

В общем «поехали». По определению, а их довольно много, понять что есть код очень даже не просто. Авторы пишут, что код — это алгоритм, отображение и ещё что-то. О классификации кодов я не буду здесь писать, скажу только, что (7, 4)-код блоковый.

В какой-то момент до меня дошло, что код — это кодовые специальные слова, конечное их множество, которыми заменяют специальными алгоритмами исходный текст сообщения на передающей стороне канала связи и которые отправляются по каналу получателю. Замену осуществляет устройство-кодер, а на приемной стороне эти слова распознает устройство-декодер.

Поскольку роль сторон переменчива оба этих устройства объединяют в одно и называют сокращенно кодек (кодер/декодер), и устанавливают на обоих концах канала. Дальше, раз есть слова, есть и алфавит. Алфавит — это два символа {0, 1}, в технике массово используются блоковые двоичные коды. Алфавит естественного языка (ЕЯ) — множество символов — букв, заменяющих при письме звуки устной речи. Здесь не будем углубляться в иероглифическую письменность в слоговое или узелковое письмо.

Алфавит и слова — это уже язык, известно, что естественные человеческие языки избыточны, но что это означает, где обитает избыточность языка трудно сказать, избыточность не очень хорошо организована, хаотична. При кодировании, хранении информации избыточность стремятся уменьшить, пример, архиваторы, код Морзе и др.

Ричард Хемминг, наверное, раньше других понял, что если избыточность не устранять, а разумно организовать, то ее можно использовать в системах связи для обнаружения ошибок и автоматического их исправления в кодовых словах передаваемого текста. Он понял, что все 128 семиразрядных двоичных слов могут использоваться для обнаружения ошибок в кодовых словах, которые образуют код — подмножество из 16 семиразрядных двоичных слов. Это была гениальная догадка.

До изобретения Хемминга ошибки приемной стороной тоже обнаруживались, когда декодированный текст не читался или получалось не совсем то, что нужно. При этом посылался запрос отправителю сообщения повторить блоки определенных слов, что, конечно, было весьма неудобно и тормозило сеансы связи. Это было большой не решаемой десятилетиями проблемой.

Построение (7, 4)-кода Хемминга

Вернемся к Хеммингу. Слова (7, 4)-кода образованы из 7 разрядов С j = $(i_1,i_2,i_3,i_4,p_1,p_2,p_3)$ , j = 0(1)15, 4-информационные и 3-проверочные символа, т.е. по существу избыточные, так как они не несут информации сообщения. Эти три проверочных разряда удалось представить линейными функциями 4-х информационных символов в каждом слове, что и обеспечило обнаружение факта ошибки и ее места в словах, чтобы внести исправление. А (7, 4)-код получил новое прилагательное и стал линейным блоковым двоичным.

Линейные функциональные зависимости (правила (*)) вычислений значений символов
$p_i$ имеют следующий вид:

$ p_1 + i_2 +i_3 + i_4 = 0, → p_1 = i_2 + i_3 + i_4,$
$ p_2 + i_1 + i_3 + i_4 = 0, → p_2 = i_1+ i_3 + i_4, (*)$
$ p_3 + i_1 + i_2 + i_4 = 0, → p_3 = i_1+i_2 + i_4. $

Исправление ошибки стало очень простой операцией — в ошибочном разряде определялся символ (ноль или единица) и заменялся другим противоположным 0 на 1 или 1 на 0.
Сколько же различных слов образуют код? Ответ на этот вопрос для (7, 4)-кода получается очень просто. Раз имеется лишь 4 информационных разряда, а их разнообразие при заполнении символами имеет $2^4$ = 16 вариантов, то других возможностей просто нет, т. е. код состоящий всего из 16 слов, обеспечивает представление этими 16-ю словами всю письменность всего языка.

Информационные части этих 16 слов получают нумерованный вид №
( $i_1,i_2,i_3,i_4$ ):

0=0000; 4= 0100; 8=1000; 12=1100;
1=0001; 5= 0101; 9=1001; 13=1101;
2=0010; 6= 0110; 10=1010; 14=1110;
3=0011; 7= 0111; 11=1011; 15=1111.

Каждому из этих 4-разрядных слов необходимо вычислить и добавить справа по 3 проверочных разряда, которые вычисляются по правилам (*). Например, для информационного слова №6 равного 0110 имеем $i_1=0, i_2=1, i_3=1,i_4=0$ и вычисления проверочных символов дают для этого слова такой результат:

$(р_1 = 0, р_2 = 1, р_3 = 1)$
$р_1=i_2 +i_3 +i_4 =1 + 1 + 0(mod2)=2(mod2)=0,$
$р_2=i_1 +i_3 +i_4 =0 + 1 + 0(mod2)=1(mod2)=1,$
$р_3=i_1 +i_2 +i_4 =0 + 1 + 0(mod2)=1(mod2)=1.$

Шестое кодовое слово при этом приобретает вид: $С_6=(i_1,i_2,i_3,i_4,p_1,p_2,p_3)=(0110011).$ Таким же образом необходимо вычислить проверочные символы для всех 16-и кодовых слов. Подготовим для слов кода 16-строчную таблицу К и последовательно будем заполнять ее клетки (читателю рекомендую проделать это с карандашом в руках).

Таблица К – кодовые слова Сj, j = 0(1)15, (7, 4) – кода Хемминга

Описание таблицы: 16 строк — кодовые слова; 10 колонок: порядковый номер, десятичное представление кодового слова, 4 информационных символа, 3 проверочных символа, W-вес кодового слова равен числу ненулевых разрядов (≠ 0). Заливкой выделены 4 кодовых слова-строки — это базис векторного подпространства. Собственно, на этом все — код построен.

Таким образом, в таблице получены все слова (7, 4) — кода Хемминга. Как видите это было не очень сложно. Далее речь пойдет о том, какие идеи привели Хемминга к такому построению кода. Мы все знакомы с кодом Морзе, с флотским семафорным алфавитом и др. системами построенными на разных эвристических принципах, но здесь в (7, 4)-коде используются впервые строгие математические принципы и методы. Рассказ будет как раз о них.

Математические основы кода. Высшая алгебра

Подошло время рассказать какая Р.Хеммингу пришла идея открытия такого кода. Он не питал особых иллюзий о своем таланте и скромно формулировал перед собой задачу: создать код, который бы обнаруживал и исправлял в каждом слове одну ошибку (на деле обнаруживать удалось даже две ошибки, но исправлялась лишь одна из них). При качественных каналах даже одна ошибка — редкое событие. Поэтому замысел Хемминга все-таки в масштабах системы связи был грандиозным. В теории кодирования после его публикации произошла революция.

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

Создатели кодов, долго не могли додуматься до кода, обнаруживающего и исправляющего две ошибки. Идеи, использованные Хеммингом, там не срабатывали. Пришлось искать, и нашлись новые идеи. Очень интересно! Захватывает. Для поиска новых идей потребовалось около 10 лет и только после этого произошел прорыв. Коды, обнаруживающие произвольное число ошибок, были получены сравнительно быстро.

Векторные пространства, поля и группы. Полученный (7, 4)-код (Таблица К) представляет множество кодовых слов, являющихся элементами векторного подпространства (порядка 16, с размерностью 4), т.е. частью векторного пространства размерности 7 с порядком $2^7=128.$ Из 128 слов в код включены лишь 16, но они попали в состав кода не просто так.

Во-первых, они являются подпространством со всеми вытекающими отсюда свойствами и особенностями, во-вторых, кодовые слова являются подгруппой большой группы порядка 128, даже более того, аддитивной подгруппой конечного расширенного поля Галуа GF( $2^7$ ) степени расширения n = 7 и характеристики 2. Эта большая подгруппа раскладывается в смежные классы по меньшей подгруппе, что хорошо иллюстрируется следующей таблицей Г. Таблица разделена на две части: верхняя и нижняя, но читать следует как одну длинную. Каждый смежный класс (строка таблицы) — элемент факторгруппы по эквивалентности составляющих.

Таблица Г – Разложение аддитивной группы поля Галуа GF () в смежные классы (строки таблицы Г) по подгруппе 16 порядка.

Столбцы таблицы – это сферы радиуса 1. Левый столбец (повторяется) – синдром слова (7, 4)-кода Хемминга, следующий столбец — лидеры смежного класса. Раскроем двоичное представление одного из элементов (25-го выделен заливкой) факторгруппы и его десятичное представление:

$0·x^6+0·x^5+1·x^4+1·x^3+0x^2+0x+1=1·2^4+1·2^3+1·2^0=16+8+1=25$

Техника получение строк таблицы Г. Элемент из столбца лидеров класса суммируется с каждым элементом из заголовка столбца таблицы Г (суммирование выполняется для строки лидера в двоичном виде по mod2). Поскольку все лидеры классов имеют вес W=1, то все суммы отличаются от слова в заголовке столбца только в одной позиции (одной и той же для всей строки, но разных для столбца). Таблица Г имеет замечательную геометрическую интерпретацию. Все 16 кодовых слов представляются центрами сфер в 7-мерном векторном пространстве. Все слова в столбце от верхнего слова отличаются в одной позиции, т. е. лежат на поверхности сферы с радиусом r =1.

В этой интерпретации скрывается идея обнаружения одной ошибки в любом кодовом слове. Работа идет со сферами. Первое условие обнаружения ошибки — сферы радиуса 1 не должны касаться или пересекаться. Это означает, что центры сфер удалены друг от друга на расстояние 3 или более. При этом сферы не только не пересекаются, но и не касаются одна другой. Это требование для однозначности решения: какой сфере отнести полученное на приемной стороне декодером ошибочное (не кодовое одно из 128 -16 = 112) слово.

Второе — все множество 7-разрядных двоичных слов из 128 слов равномерно распределено по 16 сферам. Декодер может получить слово лишь из этого множества 128-ми известных слов с ошибкой или без нее. Третье — приемная сторона может получить слово без ошибки или с искажением, но всегда принадлежащее одной из 16-и сфер, которая легко определяется декодером. В последней ситуации принимается решение о том, что послано было кодовое слово — центр определенной декодером сферы, который нашел позицию (пересечение строки и столбца) слова в таблице Г, т. е номера столбца и строки.

Здесь возникает требование к словам кода и к коду в целом: расстояние между любыми двумя кодовыми словами должно быть не менее трех, т. е. разность для пары кодовых слов, например, Сi = 85= $(i_1,i_2,i_3,i_4,p_1,p_2,p_3)$ =1010101; Сj = 25== 0011001 должна быть не менее 3; 85 — 25 = 1010101 — 0011001 =1001100 = 76, вес слова-разности W(76) = 3. (табл. Д заменяет вычисления разностей и сумм). Здесь под расстоянием между двоичными словами-векторами понимается количество не совпадающих позиций в двух словах. Это расстояние Хемминга, которое стало повсеместно использоваться в теории, и на практике, так как удовлетворяет всем аксиомам расстояния.

Замечание. (7, 4)-код не только линейный блоковый двоичный, но он еще и групповой, т. е. слова кода образуют алгебраическую группу по сложению. Это означает, что любые два кодовых слова при суммировании снова дают одно из кодовых слов. Только это не обычная операция суммирования, выполняется сложение по модулю два.

Таблица Д — Сумма элементов группы (кодовых слов), используемой для построения кода Хемминга

Сама операция суммирования слов ассоциативна, и для каждого элемента в множестве кодовых слов имеется противоположный ему, т. е. суммирование исходного слова с противоположным дает нулевое значение. Это нулевое кодовое слово является нейтральным элементом в группе. В таблице Д- это главная диагональ из нулей. Остальные клетки (пересечения строка/столбец) — это номера-десятичные представления кодовых слов, полученные суммированием элементов из строки и столбца.При перестановке слов местами (при суммировании) результат остается прежним, более того, вычитание и сложение слов имеют одинаковый результат. Дальше рассматривается система кодирования/декодирования, реализующая синдромный принцип.

Применение кода. Кодер

Кодер размещается на передающей стороне канала и им пользуется отправитель сообщения. Отправитель сообщения (автор) формирует сообщение в алфавите естественного языка и представляет его в цифровом виде. (Имя символа в ASCII-соде и в двоичном виде).
Тексты удобно формировать в файлах для ПК с использованием стандартной клавиатуры (ASCII — кодов). Каждому символу (букве алфавита) соответствует в этой кодировке октет бит (восемь разрядов). Для (7, 4)- кода Хемминга, в словах которого только 4 информационных символа, при кодировании символа клавиатуры на букву требуется два кодовых слова, т.е. октет буквы разбивается на два информационных слова естественного языка (ЕЯ) вида
$i<4> = <i_1, i_2, i_3, i_4>$ .

Пример 1. Необходимо передать слово «цифра» в ЕЯ. Входим в таблицу ASCII-кодов, буквам соответствуют: ц –11110110, и –11101000, ф – 11110100, р – 11110000, а – 11100000 октеты. Или иначе в ASCII — кодах слово «цифра» = 1111 0110 1110 1000 1111 0100 1111 0000 1110 0000

с разбивкой на тетрады (по 4 разряда). Таким образом, кодирование слова «цифра» ЕЯ требует 10 кодовых слов (7, 4)-кода Хемминга. Тетрады представляют информационные разряды слов сообщения. Эти информационные слова (тетрады) преобразуются в слова кода (по 7 разрядов) перед отправкой в канал сети связи. Выполняется это путем векторно-матричного умножения: информационного слова на порождающую матрицу. Плата за удобства получается весьма дорого и длинно, но все работает автоматически и главное — сообщение защищается от ошибок.
Порождающая матрица (7, 4)-кода Хемминга или генератор слов кода получается выписыванием базисных векторов кода и объединением их в матрицу. Это следует из теоремы линейной алгебры: любой вектор пространства (подпространства) является линейной комбинацией базисных векторов, т.е. линейно независимых в этом пространстве. Это как раз и требуется — порождать любые векторы (7-разрядные кодовые слова) из информационных 4-разрядных.

Порождающая матрица (7, 4, 3)-кода Хемминга или генератор слов кода имеет вид:

Справа указаны десятичные представления кодовых слов Базиса подпространства и их порядковые номера в таблице К
№ i строки матрицы — это слова кода, являющиеся базисом векторного подпространства.

Пример кодирования слов информационных сообщений (порождающая матрица кода выстраивается из базисных векторов и соответствует части таблицы К). В таблице ASCII-кода берем букву ц = <1111 0110>.

Информационные слова сообщения имеют вид:

$i_{k1} = <1111>, i_{k2} = <0110>$ .

Это половины символа (ц). Для (7, 4)-кода, определенного ранее, требуется найти кодовые слова, соответствующее информационному слову-сообщению (ц) из 8-и символов в виде:

$i_{k1} = <1111>, i_{k2} = <0110>$ .

Чтобы превратить эту букву–сообщение (ц) в кодовые слова u, каждую половинку буквы-сообщения i умножают на порождающую матрицу G[k, n] кода (матрица для таблицы К):

Получили два кодовых слова с порядковыми номерами 15 и 6.

Покажем детальное формирование нижнего результата №6 – кодового слова (умножение строки информационного слова на столбцы порождающей матрицы); суммирование по (mod2)

<0110> ∙ <1000> = 0∙1 +1∙0 + 1∙0 + 0∙0 = 0(mod2);
<0110> ∙ <0100> = 0∙0 +1∙1 + 1∙0 + 0∙0 = 1(mod2);
<0110> ∙ <0010> = 0∙0 +1∙0 + 1∙1 + 0∙0 = 1(mod2);
<0110> ∙ <0001> = 0∙0 +1∙0 + 1∙0 + 0∙1 = 0(mod2);
<0110> ∙ <0111> = 0∙0 +1∙1 + 1∙1 + 0∙1 = 0(mod2);
<0110> ∙ <1011> = 0∙1 +1∙0 + 1∙1 + 0∙1 = 1(mod2);
<0110> ∙ <1101> = 0∙1 +1∙1 + 1∙0 + 0∙1 = 1(mod2).

Получили в результате перемножения пятнадцатое и шестое слова из таблицы К. Первые четыре разряда в этих кодовых словах (результатах умножения) представляют информационные слова. Они имеют вид: $i_{k1} = <1111>, i_{k2}= <0110>$ , (в таблице ASCII это только половины буквы ц). Для кодирующей матрицы выбраны в качестве базисных векторов в таблице К совокупности слов с номерами: 1, 2, 4, 8. В таблице они выделены заливкой. Тогда для этой таблицы К кодирующая матрица получит вид G[k,n].

В результате перемножения получили 15 и 6 слова таблицы К кода.

Применение кода. Декодер

Декодер размещается на приемной стороне канала там, где находится получатель сообщения. Назначение декодера состоит в предоставлении получателю переданного сообщения в том виде, в котором оно существовало у отправителя в момент отправления, т.е. получатель может воспользоваться текстом и использовать сведения из него для своей дальнейшей работы.

Основной задачей декодера является проверка того, является ли полученное слово (7 разрядов) тем, которое было отправлено на передающей стороне, не содержит ли слово ошибок. Для решения этой задачи для каждого полученного слова декодером путем умножения его на проверочную матрицу Н[n-k, n] вычисляется короткий вектор-синдром S (3 разряда).

Для слов, которые являются кодовыми, т. е. не содержат ошибок, синдром всегда принимает нулевое значение S =<000>. Для слова с ошибкой синдром не нулевой S ≠ 0. Значение синдрома позволяет обнаружить и локализовать положение ошибки с точностью до разряда в принятом на приемной стороне слове, и декодер может изменить значение этого разряда. В проверочной матрице кода декодер находит столбец, совпадающий со значением синдрома, и порядковый номер этого столбца принимает равным искаженному ошибкой разряду. После этого для двоичных кодов декодером выполняется изменение этого разряда – просто замена на противоположное значение, т. е. единицу заменяют нулем, а нуль – единицей.

Рассматриваемый код является систематическим, т. е. символы информационного слова размещаются подряд в старших разрядах кодового слова. Восстановление информационных слов выполняется простым отбрасыванием младших (проверочных) разрядов, число которых известно. Далее используется таблица ASCII-кодов в обратном порядке: входом являются информационные двоичные последовательности, а выходом – буквы алфавита естественного языка. Итак, (7, 4)-код систематический, групповой, линейный, блочный, двоичный.

Основу декодера образует проверочная матрица Н[n-k, n], которая содержит число строк, равное числу проверочных символов, а столбцами все возможные, кроме нулевого, столбцы из трех символов $2^3 – 1 = 7$ . Проверочная матрица строится из слов таблицы К, они выбираются так, чтобы быть ортогональными к кодирующей матрице, т.е. их произведение — нулевая матрица. Проверочная матрица получает следующий вид в операциях умножения она транспонируется. Для конкретного примера проверочная матрица Н[n-k, n] приведена ниже:

Видим, что произведение порождающей матрицы на проверочную в результате дает нулевую матрицу.

Пример 2. Декодирование слова кода Хемминга без ошибки (е<7> =<0000000>).
Пусть на приемном конце канала приняты слова №7→60 и №13→105 из таблицы К,
u<7> + е<7> = <0 1 1 1 1 0 0 > + <0 0 0 0 0 0 0>,
где ошибка отсутствует, т. е. имеет вид е<7> = <0 0 0 0 0 0 0>.

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

Пример 3. Обнаружение одной ошибки в слове, полученном на приемном конце канала (таблица К).

А) Пусть требуется передать 7 – е кодовое слово, т.е.

u<7> = <0 1 1 1 1 0 0> и в одном третьем слева разряде слова, допущена ошибка. Тогда она суммируется по mod2 с 7-м передаваемым по каналу связи кодовым словом
u<7> + е<7> = <0 1 1 1 1 0 0 > + <0 0 1 0 0 0 0> = <0 1 0 1 1 0 0>,
где ошибка имеет вид е<7> = <0 0 1 0 0 0 0>.

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

Выполним такое умножение для наших исходных (7-го вектора с ошибкой) данных.

В результате такого умножения на приемном конце канала получили вектор-синдром S<n-k>, размерность которого (n–k). Если синдром S<3>= <0,0,0> нулевой, то делается вывод о том, что принятое на приемной стороне слово принадлежит коду С и передано без искажений. Если синдром не равен нулю S<3> ≠ <0,0,0>, то его значение указывает на наличие ошибки и ее место в слове. Искаженный разряд соответствует номеру позиции столбца матрицы Н[n-k, n], совпадающего с синдромом. После этого искаженный разряд исправляется, и полученное слово обрабатывается декодером далее. На практике для каждого принятого слова сразу вычисляется синдром и при наличии ошибки, она автоматически устраняется.

Итак, при вычислениях получен синдром S=<110> для обоих слов одинаковый. Смотрим на проверочную матрицу и отыскиваем в ней столбец, совпадающий с синдромом. Это третий слева столбец. Следовательно, ошибка допущена в третьем слева разряде, что совпадает с условиями примера. Этот третий разряд изменяется на противоположное значение и мы вернули принятые декодером слова к виду кодовых. Ошибка обнаружена и исправлена.

Вот собственно и все, именно так устроен и работает классический (7, 4)-код Хемминга.

Здесь не рассматриваются многочисленные модификации и модернизации этого кода, так как важны не они, а те идеи и их реализации, которые в корне изменили теорию кодирования, и как следствие, системы связи, обмена информацией, автоматизированные системы управления.

Заключение

В работе рассмотрены основные положения и задачи информационной безопасности, названы теории, призванные решать эти задачи.

Задача защиты информационного взаимодействия субъектов и объектов от ошибок среды и от воздействий нарушителя относится к кодологии.

Рассмотрен в деталях (7, 4)-код Хемминга, положивший начало нового направлению в теории кодирования — синтеза корректирующих кодов.

Показано применение строгих математических методов, используемых при синтезе кода.
Приведены примеры иллюстрирующие работоспособность кода.

Литература

Питерсон У., Уэлдон Э. Коды, исправляющие ошибки: Пер. с англ. М.: Мир, 1976, 594 c.
Блейхут Р. Теория и практика кодов, контролирующих ошибки. Пер.с англ. М.: Мир, 1986, 576 с.

Источник

Hamming(7,4)-code

Named after	Richard W. Hamming
Classification
Type	Linear block code
Block length	7
Message length	4
Rate	4/7 ~ 0.571
Distance	3
Alphabet size	2
Notation	[7,4,3]₂-code
Properties
perfect code
v t e

Graphical depiction of the 4 data bits d₁ to d₄ and 3 parity bits p₁ to p₃ and which parity bits apply to which data bits

In coding theory, Hamming(7,4) is a linear error-correcting code that encodes four bits of data into seven bits by adding three parity bits. It is a member of a larger family of Hamming codes, but the term Hamming code often refers to this specific code that Richard W. Hamming introduced in 1950. At the time, Hamming worked at Bell Telephone Laboratories and was frustrated with the error-prone punched card reader, which is why he started working on error-correcting codes.^[1]

The Hamming code adds three additional check bits to every four data bits of the message. Hamming’s (7,4) algorithm can correct any single-bit error, or detect all single-bit and two-bit errors. In other words, the minimal Hamming distance between any two correct codewords is 3, and received words can be correctly decoded if they are at a distance of at most one from the codeword that was transmitted by the sender. This means that for transmission medium situations where burst errors do not occur, Hamming’s (7,4) code is effective (as the medium would have to be extremely noisy for two out of seven bits to be flipped).

In quantum information, the Hamming (7,4) is used as the base for the Steane code, a type of CSS code used for quantum error correction.

Goal[edit]

The goal of the Hamming codes is to create a set of parity bits that overlap so that a single-bit error in a data bit or a parity bit can be detected and corrected. While multiple overlaps can be created, the general method is presented in Hamming codes.

Bit #	1	2	3	4	5	6	7
Transmitted bit	$p_{1}$	$p_{2}$	$d_{1}$	$p_{3}$	$d_{2}$	$d_{3}$	$d_{4}$
$p_{1}$	Yes	No	Yes	No	Yes	No	Yes
$p_{2}$	No	Yes	Yes	No	No	Yes	Yes
$p_{3}$	No	No	No	Yes	Yes	Yes	Yes

This table describes which parity bits cover which transmitted bits in the encoded word. For example, p₂ provides an even parity for bits 2, 3, 6, and 7. It also details which transmitted bit is covered by which parity bit by reading the column. For example, d₁ is covered by p₁ and p₂ but not p₃ This table will have a striking resemblance to the parity-check matrix (H) in the next section.

Furthermore, if the parity columns in the above table were removed

	$d_{1}$	$d_{2}$	$d_{3}$	$d_{4}$
$p_{1}$	Yes	Yes	No	Yes
$p_{2}$	Yes	No	Yes	Yes
$p_{3}$	No	Yes	Yes	Yes

then resemblance to rows 1, 2, and 4 of the code generator matrix (G) below will also be evident.

So, by picking the parity bit coverage correctly, all errors with a Hamming distance of 1 can be detected and corrected, which is the point of using a Hamming code.

Hamming matrices[edit]

Hamming codes can be computed in linear algebra terms through matrices because Hamming codes are linear codes. For the purposes of Hamming codes, two Hamming matrices can be defined: the code generator matrix G and the parity-check matrix H:

${displaystyle mathbf {G^{T}} :={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}}.}$

Bit position of the data and parity bits

As mentioned above, rows 1, 2, and 4 of G should look familiar as they map the data bits to their parity bits:

p₁ covers d₁, d₂, d₄
p₂ covers d₁, d₃, d₄
p₃ covers d₂, d₃, d₄

The remaining rows (3, 5, 6, 7) map the data to their position in encoded form and there is only 1 in that row so it is an identical copy. In fact, these four rows are linearly independent and form the identity matrix (by design, not coincidence).

Also as mentioned above, the three rows of H should be familiar. These rows are used to compute the syndrome vector at the receiving end and if the syndrome vector is the null vector (all zeros) then the received word is error-free; if non-zero then the value indicates which bit has been flipped.

The four data bits — assembled as a vector p — is pre-multiplied by G (i.e., Gp) and taken modulo 2 to yield the encoded value that is transmitted. The original 4 data bits are converted to seven bits (hence the name «Hamming(7,4)») with three parity bits added to ensure even parity using the above data bit coverages. The first table above shows the mapping between each data and parity bit into its final bit position (1 through 7) but this can also be presented in a Venn diagram. The first diagram in this article shows three circles (one for each parity bit) and encloses data bits that each parity bit covers. The second diagram (shown to the right) is identical but, instead, the bit positions are marked.

For the remainder of this section, the following 4 bits (shown as a column vector) will be used as a running example:

${mathbf {p}}={begin{pmatrix}d_{1}\d_{2}\d_{3}\d_{4}\end{pmatrix}}={begin{pmatrix}1\0\1\1end{pmatrix}}$

Channel coding[edit]

Mapping in the example x. The parity of the red, green, and blue circles are even.

Suppose we want to transmit this data (1011) over a noisy communications channel. Specifically, a binary symmetric channel meaning that error corruption does not favor either zero or one (it is symmetric in causing errors). Furthermore, all source vectors are assumed to be equiprobable. We take the product of G and p, with entries modulo 2, to determine the transmitted codeword x:

${displaystyle mathbf {x} =mathbf {G^{T}} mathbf {p} ={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}}{begin{pmatrix}1\0\1\1end{pmatrix}}={begin{pmatrix}2\3\1\2\0\1\1end{pmatrix}}={begin{pmatrix}0\1\1\0\0\1\1end{pmatrix}}}$

This means that 0110011 would be transmitted instead of transmitting 1011.

Programmers concerned about multiplication should observe that each row of the result is the least significant bit of the Population Count of set bits resulting from the row and column being Bitwise ANDed together rather than multiplied.

In the adjacent diagram, the seven bits of the encoded word are inserted into their respective locations; from inspection it is clear that the parity of the red, green, and blue circles are even:

red circle has two 1’s
green circle has two 1’s
blue circle has four 1’s

What will be shown shortly is that if, during transmission, a bit is flipped then the parity of two or all three circles will be incorrect and the errored bit can be determined (even if one of the parity bits) by knowing that the parity of all three of these circles should be even.

Parity check[edit]

If no error occurs during transmission, then the received codeword r is identical to the transmitted codeword x:

${mathbf {r}}={mathbf {x}}$

The receiver multiplies H and r to obtain the syndrome vector z, which indicates whether an error has occurred, and if so, for which codeword bit. Performing this multiplication (again, entries modulo 2):

${mathbf {z}}={mathbf {H}}{mathbf {r}}={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}}{begin{pmatrix}0\1\1\0\0\1\1end{pmatrix}}={begin{pmatrix}2\4\2end{pmatrix}}={begin{pmatrix}0\0\0end{pmatrix}}$

Since the syndrome z is the null vector, the receiver can conclude that no error has occurred. This conclusion is based on the observation that when the data vector is multiplied by G, a change of basis occurs into a vector subspace that is the kernel of H. As long as nothing happens during transmission, r will remain in the kernel of H and the multiplication will yield the null vector.

Error correction[edit]

Otherwise, suppose, we can write

${mathbf {r}}={mathbf {x}}+{mathbf {e}}_{i}$

modulo 2, where e_i is the $i_{{th}}$ unit vector, that is, a zero vector with a 1 in the $i^{th}$ , counting from 1.

${mathbf {e}}_{2}={begin{pmatrix}0\1\0\0\0\0\0end{pmatrix}}$

Thus the above expression signifies a single bit error in the $i^{th}$ place.

Now, if we multiply this vector by H:

${mathbf {Hr}}={mathbf {H}}left({mathbf {x}}+{mathbf {e}}_{i}right)={mathbf {Hx}}+{mathbf {He}}_{i}$

Since x is the transmitted data, it is without error, and as a result, the product of H and x is zero. Thus

${mathbf {Hx}}+{mathbf {He}}_{i}={mathbf {0}}+{mathbf {He}}_{i}={mathbf {He}}_{i}$

Now, the product of H with the $i^{th}$ standard basis vector picks out that column of H, we know the error occurs in the place where this column of H occurs.

For example, suppose we have introduced a bit error on bit #5

${mathbf {r}}={mathbf {x}}+{mathbf {e}}_{5}={begin{pmatrix}0\1\1\0\0\1\1end{pmatrix}}+{begin{pmatrix}0\0\0\0\1\0\0end{pmatrix}}={begin{pmatrix}0\1\1\0\1\1\1end{pmatrix}}$

A bit error on bit 5 causes bad parity in the red and green circles

The diagram to the right shows the bit error (shown in blue text) and the bad parity created (shown in red text) in the red and green circles. The bit error can be detected by computing the parity of the red, green, and blue circles. If a bad parity is detected then the data bit that overlaps only the bad parity circles is the bit with the error. In the above example, the red and green circles have bad parity so the bit corresponding to the intersection of red and green but not blue indicates the errored bit.

Now,

${mathbf {z}}={mathbf {Hr}}={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}}{begin{pmatrix}0\1\1\0\1\1\1end{pmatrix}}={begin{pmatrix}3\4\3end{pmatrix}}={begin{pmatrix}1\0\1end{pmatrix}}$

which corresponds to the fifth column of H. Furthermore, the general algorithm used (see Hamming code#General algorithm) was intentional in its construction so that the syndrome of 101 corresponds to the binary value of 5, which indicates the fifth bit was corrupted. Thus, an error has been detected in bit 5, and can be corrected (simply flip or negate its value):

${mathbf {r}}_{{{text{corrected}}}}={begin{pmatrix}0\1\1\0\overline {1}\1\1end{pmatrix}}={begin{pmatrix}0\1\1\0\0\1\1end{pmatrix}}$

This corrected received value indeed, now, matches the transmitted value x from above.

Decoding[edit]

Once the received vector has been determined to be error-free or corrected if an error occurred (assuming only zero or one bit errors are possible) then the received data needs to be decoded back into the original four bits.

First, define a matrix R:

${mathbf {R}}={begin{pmatrix}0&0&1&0&0&0&0\0&0&0&0&1&0&0\0&0&0&0&0&1&0\0&0&0&0&0&0&1\end{pmatrix}}$

Then the received value, p_r, is equal to Rr. Using the running example from above

${mathbf {p_{r}}}={begin{pmatrix}0&0&1&0&0&0&0\0&0&0&0&1&0&0\0&0&0&0&0&1&0\0&0&0&0&0&0&1\end{pmatrix}}{begin{pmatrix}0\1\1\0\0\1\1end{pmatrix}}={begin{pmatrix}1\0\1\1end{pmatrix}}$

Multiple bit errors[edit]

A bit error on bit 4 & 5 are introduced (shown in blue text) with a bad parity only in the green circle (shown in red text)

It is not difficult to show that only single bit errors can be corrected using this scheme. Alternatively, Hamming codes can be used to detect single and double bit errors, by merely noting that the product of H is nonzero whenever errors have occurred. In the adjacent diagram, bits 4 and 5 were flipped. This yields only one circle (green) with an invalid parity but the errors are not recoverable.

However, the Hamming (7,4) and similar Hamming codes cannot distinguish between single-bit errors and two-bit errors. That is, two-bit errors appear the same as one-bit errors. If error correction is performed on a two-bit error the result will be incorrect.

Similarly, Hamming codes cannot detect or recover from an arbitrary three-bit error; Consider the diagram: if the bit in the green circle (colored red) were 1, the parity checking would return the null vector, indicating that there is no error in the codeword.

All codewords[edit]

Since the source is only 4 bits then there are only 16 possible transmitted words. Included is the eight-bit value if an extra parity bit is used (see Hamming(7,4) code with an additional parity bit). (The data bits are shown in blue; the parity bits are shown in red; and the extra parity bit shown in green.)

Data $({color {blue}d_{1}},{color {blue}d_{2}},{color {blue}d_{3}},{color {blue}d_{4}})$	Hamming(7,4)	Hamming(7,4) with extra parity bit (Hamming(8,4))
Transmitted $({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}})$	Diagram	Transmitted $({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}})$	Diagram
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

E₇ lattice[edit]

The Hamming(7,4) code is closely related to the E₇ lattice and, in fact, can be used to construct it, or more precisely, its dual lattice E₇^∗ (a similar construction for E₇ uses the dual code [7,3,4]₂). In particular, taking the set of all vectors x in Z⁷ with x congruent (modulo 2) to a codeword of Hamming(7,4), and rescaling by 1/√2, gives the lattice E₇^∗

${displaystyle E_{7}^{*}={tfrac {1}{sqrt {2}}}left{xin mathbb {Z} ^{7}:x{bmod {2}}in [7,4,3]_{2}right}.}$

This is a particular instance of a more general relation between lattices and codes. For instance, the extended (8,4)-Hamming code, which arises from the addition of a parity bit, is also related to the E₈ lattice. ^[2]

References[edit]

^ «History of Hamming Codes». Archived from the original on 2007-10-25. Retrieved 2008-04-03.
^ Conway, John H.; Sloane, Neil J. A. (1998). Sphere Packings, Lattices and Groups (3rd ed.). New York: Springer-Verlag. ISBN 0-387-98585-9.

External links[edit]

A programming problem about the Hamming Code(7,4)

Источник

Hamming(7,4)-code

Named after	Richard W. Hamming
Classification
Type	Linear block code
Block length	7
Message length	4
Rate	4/7 ~ 0.571
Distance	3
Alphabet size	2
Notation	[7,4,3]₂-code
Properties
perfect code
v t e

Graphical depiction of the 4 data bits d₁ to d₄ and 3 parity bits p₁ to p₃ and which parity bits apply to which data bits

In quantum information, the Hamming (7,4) is used as the base for the Steane code, a type of CSS code used for quantum error correction.

Goal[edit]

Bit #	1	2	3	4	5	6	7
Transmitted bit	$p_{1}$	$p_{2}$	$d_{1}$	$p_{3}$	$d_{2}$	$d_{3}$	$d_{4}$
$p_{1}$	Yes	No	Yes	No	Yes	No	Yes
$p_{2}$	No	Yes	Yes	No	No	Yes	Yes
$p_{3}$	No	No	No	Yes	Yes	Yes	Yes

Furthermore, if the parity columns in the above table were removed

	$d_{1}$	$d_{2}$	$d_{3}$	$d_{4}$
$p_{1}$	Yes	Yes	No	Yes
$p_{2}$	Yes	No	Yes	Yes
$p_{3}$	No	Yes	Yes	Yes

then resemblance to rows 1, 2, and 4 of the code generator matrix (G) below will also be evident.

So, by picking the parity bit coverage correctly, all errors with a Hamming distance of 1 can be detected and corrected, which is the point of using a Hamming code.

Hamming matrices[edit]

Bit position of the data and parity bits

As mentioned above, rows 1, 2, and 4 of G should look familiar as they map the data bits to their parity bits:

p₁ covers d₁, d₂, d₄
p₂ covers d₁, d₃, d₄
p₃ covers d₂, d₃, d₄

For the remainder of this section, the following 4 bits (shown as a column vector) will be used as a running example:

${mathbf {p}}={begin{pmatrix}d_{1}\d_{2}\d_{3}\d_{4}\end{pmatrix}}={begin{pmatrix}1\0\1\1end{pmatrix}}$

Channel coding[edit]

Mapping in the example x. The parity of the red, green, and blue circles are even.

This means that 0110011 would be transmitted instead of transmitting 1011.

In the adjacent diagram, the seven bits of the encoded word are inserted into their respective locations; from inspection it is clear that the parity of the red, green, and blue circles are even:

red circle has two 1’s
green circle has two 1’s
blue circle has four 1’s

Parity check[edit]

If no error occurs during transmission, then the received codeword r is identical to the transmitted codeword x:

${mathbf {r}}={mathbf {x}}$

Error correction[edit]

Otherwise, suppose, we can write

${mathbf {r}}={mathbf {x}}+{mathbf {e}}_{i}$

modulo 2, where e_i is the $i_{{th}}$ unit vector, that is, a zero vector with a 1 in the $i^{th}$ , counting from 1.

${mathbf {e}}_{2}={begin{pmatrix}0\1\0\0\0\0\0end{pmatrix}}$

Thus the above expression signifies a single bit error in the $i^{th}$ place.

Now, if we multiply this vector by H:

${mathbf {Hr}}={mathbf {H}}left({mathbf {x}}+{mathbf {e}}_{i}right)={mathbf {Hx}}+{mathbf {He}}_{i}$

Since x is the transmitted data, it is without error, and as a result, the product of H and x is zero. Thus

${mathbf {Hx}}+{mathbf {He}}_{i}={mathbf {0}}+{mathbf {He}}_{i}={mathbf {He}}_{i}$

Now, the product of H with the $i^{th}$ standard basis vector picks out that column of H, we know the error occurs in the place where this column of H occurs.

For example, suppose we have introduced a bit error on bit #5

${mathbf {r}}={mathbf {x}}+{mathbf {e}}_{5}={begin{pmatrix}0\1\1\0\0\1\1end{pmatrix}}+{begin{pmatrix}0\0\0\0\1\0\0end{pmatrix}}={begin{pmatrix}0\1\1\0\1\1\1end{pmatrix}}$

A bit error on bit 5 causes bad parity in the red and green circles

Now,

${mathbf {r}}_{{{text{corrected}}}}={begin{pmatrix}0\1\1\0\overline {1}\1\1end{pmatrix}}={begin{pmatrix}0\1\1\0\0\1\1end{pmatrix}}$

This corrected received value indeed, now, matches the transmitted value x from above.

Decoding[edit]

First, define a matrix R:

${mathbf {R}}={begin{pmatrix}0&0&1&0&0&0&0\0&0&0&0&1&0&0\0&0&0&0&0&1&0\0&0&0&0&0&0&1\end{pmatrix}}$

Then the received value, p_r, is equal to Rr. Using the running example from above

${mathbf {p_{r}}}={begin{pmatrix}0&0&1&0&0&0&0\0&0&0&0&1&0&0\0&0&0&0&0&1&0\0&0&0&0&0&0&1\end{pmatrix}}{begin{pmatrix}0\1\1\0\0\1\1end{pmatrix}}={begin{pmatrix}1\0\1\1end{pmatrix}}$

Multiple bit errors[edit]

A bit error on bit 4 & 5 are introduced (shown in blue text) with a bad parity only in the green circle (shown in red text)

All codewords[edit]

Data $({color {blue}d_{1}},{color {blue}d_{2}},{color {blue}d_{3}},{color {blue}d_{4}})$	Hamming(7,4)	Hamming(7,4) with extra parity bit (Hamming(8,4))
Transmitted $({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}})$	Diagram	Transmitted $({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}})$	Diagram
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

E₇ lattice[edit]

${displaystyle E_{7}^{*}={tfrac {1}{sqrt {2}}}left{xin mathbb {Z} ^{7}:x{bmod {2}}in [7,4,3]_{2}right}.}$

References[edit]

^ «History of Hamming Codes». Archived from the original on 2007-10-25. Retrieved 2008-04-03.
^ Conway, John H.; Sloane, Neil J. A. (1998). Sphere Packings, Lattices and Groups (3rd ed.). New York: Springer-Verlag. ISBN 0-387-98585-9.

External links[edit]

A programming problem about the Hamming Code(7,4)

Источник

Определите вектор однократной ошибки для принятой кодовой комбинации 0100111 кода хэмминга 7 4

13.5 Циклические коды

Корректирующие коды. Начало новой теории кодирования

Введение

Информационная безопасность. Коды, шифры, стегосообщения

Построение (7, 4)-кода Хемминга

Математические основы кода. Высшая алгебра

Применение кода. Кодер

Применение кода. Декодер

Заключение

Литература

Goal[edit]

Hamming matrices[edit]

Channel coding[edit]

Parity check[edit]

Error correction[edit]

Decoding[edit]

Multiple bit errors[edit]

All codewords[edit]

E7 lattice[edit]

References[edit]

External links[edit]

Goal[edit]

Hamming matrices[edit]

Channel coding[edit]

Parity check[edit]

Error correction[edit]

Decoding[edit]

Multiple bit errors[edit]

All codewords[edit]

E7 lattice[edit]

References[edit]

External links[edit]

А вот еще интересные материалы:

E₇ lattice[edit]

E₇ lattice[edit]