12. Декодирование по синдрому и еще раз о коде Хемминга
Слово «синдром» означает обычно совокупность признаков, характерных для того или иного явления. Такой же примерно смысл имеет понятие «синдром» и в теории кодирования. Синдром вектора, содержащего, быть может, ошибки, дает возможность распознать наиболее вероятный характер этих ошибок. Правда, определение, которое мы приводим ниже, не сразу позволяет это увидеть. Синдромом вектора и называется вектор s(u), определяемый равенством:
Пусть теперь вектор u не является кодовым, тогда этот вектор обязательно содержит ошибочные символы. Вектор и можно представить тогда в виде суммы посланного кодового вектора υ (который пока не известен) и вектора ошибки е:
Важным обстоятельством является то, что синдромы принятого вектора u и вектора ошибки совпадают. Действительно,
На языке теории групп это означает, что U есть смежный класс по подгруппе V (пространство Ln и его кодовое подпространство V можно рассматривать соответственно как группу и ее подгруппу относительно операции сложения векторов).
Сказанное позволяет сделать следующие выводы:
1. Два вектора имеют одинаковый синдром тогда и только тогда, когда они принадлежат одному смежному классу по кодовому подпространству. Таким образом, синдром вектора однозначно определяет тот смежный класс, которому этот вектор принадлежит.
2. Вектор ошибки e для вектора u нужно искать в силу равенства (2) в том же смежном классе, которому принадлежит и сам вектор u.
Разумеется, указание смежного класса, которому принадлежит вектор e, еще не определяет самого этого вектора. Естественно выбрать в качестве в тот вектор смежного класса, для которого вероятность совпадения с е наибольшая. Такой вектор называют лидером смежного класса. Если предположить, что большее число ошибок совершается с меньшей вероятностью, то в качестве лидера следует взять вектор наименьшего веса данного класса и в дальнейшем лидер будет пониматься именно в этом смысле.
При реализации алгоритма декодирования по синдрому составляют таблицу, в которой указываются синдромы si и лидеры ei соответствующих им смежных классов. Алгоритм декодирования заключается тогда в следующем:
1. Вычисляем синдром s(u) принятого вектора u.
2. По синдрому s(u) = si определяем из таблицы лидер ei соответствующего смежного класса.
3. Определяем посланный кодовый вектор υ как разность
Может случиться, что в некоторых смежных классах окажется более одного лидера. Если искаженный вектор u попал в один из таких смежных классов, то разумнее отказаться от исправления ошибки, ограничившись ее обнаружением.
Алгоритм исправления одиночных ошибок в этом случае удивительно прост. Если вектор и содержит ошибочный символ в i-й позиции, то синдром s(u) этого вектора совпадает с i-м столбцом проверочной матрицы. Таким образом, этот синдром, читаемый как двоичное число, и есть номер ошибочного символа.
Например, из приведенной выше проверочной матрицы для (15,11)-кода Хемминга получается следующая проверочная матрица для расширенного (16,11)-кода:
В первом случае считаем, что произошла одиночная ошибка, и ее положение определяется номером столбца, с которым совпадает синдром.
Во втором случае считаем, что допущены две или любое большее четное число ошибок, если s(u) ≠ 0. Если же s(u) = 0, то, как обычно, полагаем, что ошибок при передаче не было.
разное / ИТ / лабораторная 6 / Хэмминг
Омский государственный технический университет
Кафедра «Автоматизированные системы обработки информации и управления»
по лабораторной работе №2
«Исследование процессов кодирования и декодирования при передаче дискретных сообщений кодами Хэмминга»
Задание к лабораторной работе:
2. Построить порождающую матрицу кода. 3. Построить проверочные матрицы кода в модифицированном (с проверкой на четность) виде. 4. Сформировать системы проверочных и синдромных уравнений. 5. Сформировать кодовое слово исследуемого кода, ввести одиночную ошибку и показать ее исправление путем вычисления синдрома. 6. Показать на примере, что код не гарантирует обнаружение тройных ошибок.
7. Произвести первичное декодирование принятого сообщения, закодированного кодом Хэмминга. При этом осуществить обнаружение и исправление ошибок в кодовых словах, используя методику исправления с вычислением синдрома.
Результаты выполнения работы
1. Определяем длину информационного i и длину проверочного к последовательного кода и формируем код Хэмминга.
Нам дана длина кода – n. Информационные и проверочные биты определим из соотношения:
Т.к. длина кода n=7, а длину информационного кода возьмем равную i=4, то согласно соотношению (1) количество проверочных бит k=n-i, k=3:
3. 00011 00001 k1 = i3 
i5 
i7
4. 00100 00010 k2 = i3 
i6 
i7
5. 00101 00100 k4 = i5 
i6 
i7
G = 
3. Построим проверочную матрицу.
В нашем случае H(8,4)=|K4,4 T , I4|: K4,4 T = 
Отсюда получаем проверочную матрицу вида:
H = 
4. Сформируем системы проверочных и синдромных уравнений. Для этого умножим единичную матрицу I8,8 на транспонированную проверочную матрицу H8,4,получим:
= 
5. Сформируем кодовое слово исследуемого кода, введем одиночную ошибку и покажем ее исправление путем вычисления синдрома. Произведение любого кодового слова G1 на транспонированную проверочную матрицу дает нулевой вектор размерности (n-i): Gi·Hn,i T =[00. ]
Возьмем любой код из порождающей матрицы G, умножим на H T и проверим на наличие ошибки:
= 
= 1000
6. Код Хэмминга позволяет выявить только одну ошибку.
Показать на примере, что код не гарантирует обнаружение тройных ошибок.
Пусть передано кодовое слово 101111. Сделаем три ошибки и получим код 10100101. Проверим его:
= 0000
Как видно из полученного результата, проверяемый код не содержит ошибок, хотя на самом деле в нем три ошибки.
7. Произвести первичное декодирование принятого сообщения, закодированного кодом Хэмминга. При этом осуществить обнаружение и исправление ошибок в кодовых словах, используя методику исправления с вычислением синдрома. Возьмем произвольный информационный код: i = 0110.
Вычислим для него проверочные биты. Для этого из порождающей матрицы берем прямоугольную матрицу, состоящую из проверочных битов, и находим k:
Ki,k = 
k = 0110
Полученный код имеет вид:
Декодирование означает исключение проверочных битов. Получим код 0110.
Проверим наш код на наличие ошибок:
= 0000
Вычисленный синдром показывает на то, что код ошибки не содержит.
Введем ошибку и проверим ее при помощи матрицы синдромных уравнений:
= 1010
Вычисленный синдром указывает на ошибку в третьей позиции.
Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) Сумы, 2007 Содержание
3.10 Код Хэмминга
Наиболее распространенным систематическим линейным блочным кодом является код Хэмминга. К нему относятся коды с минимальным кодовым расстоянием dmin=3, способные исправлять однократные ошибки.
При передаче кодового слова по каналу связи возможно возникновение однократной ошибки в любом из его элементов. Количество таких ситуаций 
. Таким образом, для того чтобы определить место возникновения ошибки, количество комбинаций проверочных элементов 2 r должно быть не меньше количества возможных ошибочных ситуаций в коде плюс ситуация, когда ошибка не возникает, т. е. должно выполняться неравенство
Из этого неравенства следует минимальное соотношение проверочных и информационных разрядов, необходимое для исправления однократных ошибок
Для расчёта основных параметров кода Хэмминга можно задать количество проверочных элементов r, тогда длина кодовых слов n ≤ 2 r -1, а количество информационных элементов k=n—r. Соотношения между r, n и k приведены в следующей таблице (табл. 3.3.)
Таблица 3.3
| k | 1 | 1 | 2 | 3 | 4 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 11 | 12 | 12 |
| r | 2 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 5 | 5 | 6 |
| n | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
Характерной особенностью проверочной матрицы кода с dmin=3 является то, что ее столбцы – различные ненулевые комбинации длины r.
Например, для r=3 проверочная матрица кода Хэмминга имеет вид
.
Проверочная матрица (k, n)-кода Хэмминга составляется из n=2 r -1 строк и r столбцов и представляет собой двоичные комбинации числа i, где i – номер столбца проверочной матрицы (разряда кодовой комбинации).
, 
, 
.
Синдром, определяющий систему проверочных уравнений кода, находится из уравнения u
=.
Например, для r=3 система проверочных уравнений будет следующей:
Отсюда проверочные разряды (контрольные суммы) находятся как
^ Чтобы закодировать сообщение m, в качестве u i, где i не равно степени 2, берутся соответствующие биты сообщения, а проверочные разряды с индексами степени 2 находятся из системы проверочных уравнений кода. В каждое уравнение системы входит только одна контрольная сумма.
Пример 1 Закодируем сообщение m=(0 1 1 1) (4, 7)-кодом Хэмминга.
Из системы проверочных уравнений находим контрольные суммы:
Таким образом, кодовым словом будет последовательность (0001111).
Декодирование кода Хэмминга происходит по следующей схеме. Определяется синдром принятой последовательности S=y
, где — транспонированная проверочная матрица кода; y – принятый вектор. Если синдром равен нулевому вектору, то считается, что слово передано без ошибок, иначе значение синдрома соответствует двоичному представлению номера разряда, в котором произошла ошибка. В этом случае нужно изменить значение в ошибочном разряде, считая разряды слева направо, начиная с 1.
Пример 2 Сообщение кодируется (4, 7)-кодом Хэмминга. Принята последовательность y=(0011111). Декодируем принятый вектор.
Определяем синдром принятого вектора:
y = (0011111) 
= (0 1 1)=310,
т. е. ошибка произошла в третьем разряде.
Исправляем ошибку, изменяя значение в третьем бите
Переданное сообщение декодируется как
Порождающей матрицей (k, n)-кода Хэмминга является матрица (k×n), в которой столбцы с номерами не степенями 2 образуют единичную подматрицу, а остальные столбцы соответствуют проверочным уравнениям кода. Такая матрица при кодировании будет копировать биты сообщения в позиции, не степени 2, и заполнять другие позиции кода согласно системе вычисления контрольных разрядов.
Пример 3 Система проверочных уравнений (4, 7)-кода Хэмминга следующая:
Соответственно порождающая матрица данного кода имеет вид
.
Список использованной и рекомендуемой литературы
Проверочная матрица кода хемминга
Код Хэ́мминга — наиболее известный из первых самоконтролирующихся и самокорректирующихся кодов. Построен применительно к двоичной системе счисления. Позволяет исправлять одиночную ошибку (ошибка в одном бите) и находить двойную.
Предположим, что нужно сгенерировать код Хемминга для некоторого информационного кодового слова. В качестве примера возьмём 15-битовое кодовое слово x1…x15, хотя алгоритм пригоден для кодовых слов любой длины. В приведённой ниже таблице в первой строке даны номера позиций в кодовом слове, во второй — условное обозначение битов, в третьей — значения битов.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | x15 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Вставим в информационное слово контрольные биты r0…r4 таким образом, чтобы номера их позиций представляли собой целые степени двойки: 1, 2, 4, 8, 16… Получим 20-разрядное слово с 15 информационными и 5 контрольными битами. Первоначально контрольные биты устанавливаем равными нулю. На рисунке контрольные биты выделены розовым цветом.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | x15 | |||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
В общем случае количество контрольных бит в кодовом слове равно двоичному логарифму числа, на единицу большего, чем количество бит кодового слова (включая контрольные биты); логарифм округляется в большую сторону. Например, информационное слово длиной 1 бит требует двух контрольных разрядов, 2-, 3- или 4-битовое информационное слово — трёх, 5…11-битовое — четырёх, 12…26-битовое — пяти и т. д.
Добавим к таблице 5 строк (по количеству контрольных битов), в которые поместим матрицу преобразования. Каждая строка будет соответствовать одному контрольному биту (нулевой контрольный бит — верхняя строка, четвёртый — нижняя), каждый столбец — одному биту кодируемого слова. В каждом столбце матрицы преобразования поместим двоичный номер этого столбца, причём порядок следования битов будет обратный — младший бит расположим в верхней строке, старший — в нижней. Например, в третьем столбце матрицы будут стоять числа 11000, что соответствует двоичной записи числа три: 00011.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | x15 | |||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | |||||||||||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ||||||||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ||||||||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |||||||||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ||||||||||||
| 1 | 1 | 1 | 1 | 1 |
В правой части таблицы мы оставили пустым один столбец, в который поместим результаты вычислений контрольных битов. Вычисление контрольных битов производим следующим образом. Берём одну из строк матрицы преобразования (например, r0) и находим её скалярное произведение с кодовым словом, то есть перемножаем соответствующие биты обеих строк и находим сумму произведений. Если сумма получилась больше единицы, находим остаток от его деления на 2. Иными словами, мы подсчитываем сколько раз в кодовом слове и соответствующей строке матрицы в одинаковых позициях стоят единицы и берём это число по модулю 2.
Если описывать этот процесс в терминах матричной алгебры, то операция представляет собой перемножение матрицы преобразования на матрицу-столбец кодового слова, в результате чего получается матрица-столбец контрольных разрядов, которые нужно взять по модулю 2.
Например, для строки r0:
r0 = (1·0+0·0+1·1+0·0+1·0+0·0+1·1+0·0+1·0+0·0+1·1+0·0+1·1+0·1+1·1+0·0+1·0+0·0+1·0+0·1) mod 2 = 5 mod 2 = 1.
Полученные контрольные биты вставляем в кодовое слово вместо стоявших там ранее нулей. По аналогии находим проверочные биты в остальных строках. Кодирование по Хэммингу завершено. Полученное кодовое слово — 11110010001011110001.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | |
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | x15 | ||||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | ||||||||||||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ||||||||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ||||||||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |||||||||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |||||||||||||
| 1 | 1 | 1 | 1 | 1 | 1 |
Алгоритм декодирования по Хэммингу абсолютно идентичен алгоритму кодирования. Матрица преобразования соответствующей размерности умножается на матрицу-столбец кодового слова и каждый элемент полученной матрицы-столбца берётся по модулю 2. Полученная матрица-столбец получила название «матрица синдромов». Легко проверить, что кодовое слово, сформированное в соответствии с алгоритмом, описанным в предыдущем разделе, всегда даёт нулевую матрицу синдромов.
Матрица синдромов становится ненулевой, если в результате ошибки (например, при передаче слова по линии связи с шумами) один из битов исходного слова изменил своё значение. Предположим для примера, что в кодовом слове, полученном в предыдущем разделе, шестой бит изменил своё значение с нуля на единицу (на рисунке обозначено красным цветом). Тогда получим следующую матрицу синдромов.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| r | r1 | x1 | r2 | x2 | x3 | x4 | r3 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | r4 | x12 | x13 | x14 | x15 | ||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ||||||||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | s | |||||||||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | s1 | 1 | ||||||||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | s2 | 1 | |||||||||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | s3 | |||||||||||||
| 1 | 1 | 1 | 1 | 1 | s4 |
Заметим, что при однократной ошибке матрица синдромов всегда представляет собой двоичную запись (младший разряд в верхней строке) номера позиции, в которой произошла ошибка. В приведённом примере матрица синдромов (01100) соответствует двоичному числу 00110 или десятичному 6, откуда следует, что ошибка произошла в шестом бите.
