проверочная матрица кода хемминга

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 попал в один из таких смежных классов, то разумнее отказаться от исправления ошибки, ограничившись ее обнаружением.

000068

Алгоритм исправления одиночных ошибок в этом случае удивительно прост. Если вектор и содержит ошибочный символ в i-й позиции, то синдром s(u) этого вектора совпадает с i-м столбцом проверочной матрицы. Таким образом, этот синдром, читаемый как двоичное число, и есть номер ошибочного символа.

Например, из приведенной выше проверочной матрицы для (15,11)-кода Хемминга получается следующая проверочная матрица для расширенного (16,11)-кода:

000069

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

Во втором случае считаем, что допущены две или любое большее четное число ошибок, если 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 img 6cN84Pi5 img oPh5Ufi7

4. 00100 00010  k2 = i3 img 7hkzn9i6 img UbbVdbi7

5. 00101 00100 k4 = i5 img MiSpDRi6 img 0C2oLWi7

G = img

3. Построим проверочную матрицу.

В нашем случае H(8,4)=|K4,4 T , I4|: K4,4 T = img umhfm8

Отсюда получаем проверочную матрицу вида:

H = img gbgrHP

4. Сформируем системы проверочных и синдромных уравнений. Для этого умножим единичную матрицу I8,8 на транспонированную проверочную матрицу H8,4,получим:

img 7bE2cNimg Gz4tkj= img 5bQGXC

5. Сформируем кодовое слово исследуемого кода, введем одиночную ошибку и покажем ее исправление путем вычисления синдрома. Произведение любого кодового слова G1 на транспонированную проверочную матрицу дает нулевой вектор размерности (n-i): Gi·Hn,i T =[00. ]

Возьмем любой код из порождающей матрицы G, умножим на H T и проверим на наличие ошибки:

img CIZfN3img Qcy8YS= img zfHknw

img eCmqimg mrTGV= 1000

6. Код Хэмминга позволяет выявить только одну ошибку.

Показать на примере, что код не гарантирует обнаружение тройных ошибок.

Пусть передано кодовое слово 101111. Сделаем три ошибки и получим код 10100101. Проверим его:

img 6lzuoPimg vEs4 F= 0000

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

7. Произвести первичное декодирование принятого сообщения, закодированного кодом Хэмминга. При этом осуществить обнаружение и исправление ошибок в кодовых словах, используя методику исправления с вычислением синдрома. Возьмем произвольный информационный код: i = 0110.

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

Ki,k = img di4Lfj k = 0110

Полученный код имеет вид:

img pn2Rmg

Декодирование означает исключение проверочных битов. Получим код 0110.

Проверим наш код на наличие ошибок:

img 0VdsGgimg MwXDoI= 0000

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

Введем ошибку и проверим ее при помощи матрицы синдромных уравнений:

img UWofrLimg PDmvL4= 1010

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

Источник

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) Сумы, 2007 Содержание

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

Наиболее распространенным систематическим линейным блочным кодом является код Хэмминга. К нему относятся коды с минимальным кодовым расстоянием dmin=3, способные исправлять однократные ошибки.

При передаче кодового слова по каналу связи возможно возникновение однократной ошибки в любом из его элементов. Количество таких ситуаций 2000175 html m49773fa7. Таким образом, для того чтобы определить место возникновения ошибки, количество комбинаций проверочных элементов 2 r должно быть не меньше количества возможных ошибочных ситуаций в коде плюс ситуация, когда ошибка не возникает, т. е. должно выполняться неравенство

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

Для расчёта основных параметров кода Хэмминга можно задать количество проверочных элементов r, тогда длина кодовых слов n ≤ 2 r -1, а количество информационных элементов k=nr. Соотношения между r, n и k приведены в следующей таблице (табл. 3.3.)

Читайте также:  коды all star tower defense new

Таблица 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 проверочная матрица кода Хэмминга имеет вид

2000175 html 15ca688c.

Проверочная матрица (k, n)-кода Хэмминга составляется из n=2 r -1 строк и r столбцов и представляет собой двоичные комбинации числа i, где iномер столбца проверочной матрицы (разряда кодовой комбинации).

2000175 html m4c035928, 2000175 html 57cdcdfb, 2000175 html 6981c443.

Синдром, определяющий систему проверочных уравнений кода, находится из уравнения u2000175 html m44032320=.

Например, для r=3 система проверочных уравнений будет следующей:

2000175 html m32b120bc

Отсюда проверочные разряды (контрольные суммы) находятся как

2000175 html m1d26a149

^ Чтобы закодировать сообщение m, в качестве u i, где i не равно степени 2, берутся соответствующие биты сообщения, а проверочные разряды с индексами степени 2 находятся из системы проверочных уравнений кода. В каждое уравнение системы входит только одна контрольная сумма.

Пример 1 Закодируем сообщение m=(0 1 1 1) (4, 7)-кодом Хэмминга.

Из системы проверочных уравнений находим контрольные суммы:

Таким образом, кодовым словом будет последовательность (0001111).

Декодирование кода Хэмминга происходит по следующей схеме. Определяется синдром принятой последовательности S=y2000175 html m1e98e93d, где 2000175 html m1e98e93d— транспонированная проверочная матрица кода; y – принятый вектор. Если синдром равен нулевому вектору, то считается, что слово передано без ошибок, иначе значение синдрома соответствует двоичному представлению номера разряда, в котором произошла ошибка. В этом случае нужно изменить значение в ошибочном разряде, считая разряды слева направо, начиная с 1.

Пример 2 Сообщение кодируется (4, 7)-кодом Хэмминга. Принята последовательность y=(0011111). Декодируем принятый вектор.

Определяем синдром принятого вектора:

y2000175 html m44032320= (0011111) 2000175 html 656055ed= (0 1 1)=310,

т. е. ошибка произошла в третьем разряде.

Исправляем ошибку, изменяя значение в третьем бите

Переданное сообщение декодируется как

Порождающей матрицей (k, n)-кода Хэмминга является матрица (k×n), в которой столбцы с номерами не степенями 2 образуют единичную подматрицу, а остальные столбцы соответствуют проверочным уравнениям кода. Такая матрица при кодировании будет копировать биты сообщения в позиции, не степени 2, и заполнять другие позиции кода согласно системе вычисления контрольных разрядов.

Пример 3 Система проверочных уравнений (4, 7)-кода Хэмминга следующая:

Соответственно порождающая матрица данного кода имеет вид

2000175 html m2d9f70.

Список использованной и рекомендуемой литературы

Источник

Проверочная матрица кода хемминга

Код Хэ́мминга — наиболее известный из первых самоконтролирующихся и самокорректирующихся кодов. Построен применительно к двоичной системе счисления. Позволяет исправлять одиночную ошибку (ошибка в одном бите) и находить двойную.

Предположим, что нужно сгенерировать код Хемминга для некоторого информационного кодового слова. В качестве примера возьмём 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
Читайте также:  коды one piece prime

В общем случае количество контрольных бит в кодовом слове равно двоичному логарифму числа, на единицу большего, чем количество бит кодового слова (включая контрольные биты); логарифм округляется в большую сторону. Например, информационное слово длиной 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, откуда следует, что ошибка произошла в шестом бите.

Источник

Поделиться с друзьями
admin
Здоровый образ жизни: советы и рекомендации
Adblock
detector