Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Омский
государственный технический университет

Кафедра
«Автоматизированные системы обработки
информации и управления»

по
лабораторной работе №2

«Исследование
процессов кодирования и декодирования
при передаче дискретных сообщений
кодами Хэмминга»

Итак. Задача. Использовать код Хэмминга для двоичного сообщения, длина слова у которого составляет 16 бит. Исходное сообщение возьмём такое «0100010000111101». То есть в слове 16 «букв», каждая из которых может принимать значение либо «0», либо «1».

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Пример
. Предположим, в канале связи под действием
помех произошло искажение и вместо
0100101 было принято 01001(1)1.

Решение:
Для обнаружения ошибки производят уже
знакомые нам проверки на четность.

Первая
проверка:
сумма П1+П3+П5+П7
= 0+0+1+1 четна.
В младший разряд номера ошибочной
позиции запишем 0.

Вторая
проверка:
сумма П2+П3+П6+П7
= 1+0+1+1 нечетна.
Во второй разряд номера ошибочной
позиции запишем 1

Третья
проверка:
сумма П4+П5+П6+П7
= 0+1+1+1 нечетна.
В третий разряд номера ошибочной позиции
запишем 1. Номер ошибочной позиции 110=
6. Следовательно,
символ шестой позиции следует изменить
на обратный, и получим правильную кодовую
комбинацию.

Код, исправляющий
одиночную и обнаруживающий двойную
ошибки

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

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

Для
этого, кроме указанных выше проверок
по контрольным позициям, следует провести
еще одну проверку на четность для всей
строки в целом. Чтобы осуществить такую
проверку, следует к каждой строке кода
добавить контрольные символы, записанные
в дополнительной колонке (таблица,
колонка 8). Тогда в случае одной ошибки
проверки по позициям укажут номер
ошибочной позиции, а проверка на четность
– на наличие ошибки. Если проверки позиций
укажут на наличие ошибки, а проверка на
четность не фиксирует ее, значит в
кодовой комбинации две ошибки.

Построение кода Хэмминга

Пример: Построить макет кода Хемминга и определить значения корректирующих разрядов для кодовой комбинации k=4, X=0101.

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Согласно таблице минимальное число контрольных символов r=3, при этом n = 7. Контрольный коэффициенты будут расположены на позициях 1, 2, 4. Составим макет корректирующего кода и запишем его во вторую колонку таблицы. Пользуясь таблицей для номеров проверочных коэффициентов, определим значения коэффициентов К1 К2 и К3.

Первая проверка: сумма П1+П3+П5+П7 должна быть четной, а сумма К1+0+1+1 будет четной при К =0.

Вторая проверка: сумма П2+П3+П6+П7 должна быть четной, а сумма К2+0+0+1 будет четной при К2=1.

Третья проверка: сумма П4+П5+П6+П7 должна быть четной, а сумма К3+1+0+1 будет четной при К3=0.

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

Пример . Предположим, в канале связи под действием помех произошло искажение и вместо 0100101 было принято 01001(1)1.

Решение: Для обнаружения ошибки производят уже знакомые нам проверки на четность.

Первая проверка: сумма П1+П3+П5+П7 = 0+0+1+1 четна. В младший разряд номера ошибочной позиции запишем 0.

Вторая проверка: сумма П2+П3+П6+П7 = 1+0+1+1 нечетна. Во второй разряд номера ошибочной позиции запишем 1

Третья проверка: сумма П4+П5+П6+П7 = 0+1+1+1 нечетна. В третий разряд номера ошибочной позиции запишем 1. Номер ошибочной позиции 110= 6. Следовательно, символ шестой позиции следует изменить на обратный, и получим правильную кодовую комбинацию.

Код, исправляющий одиночную и обнаруживающий двойную ошибки

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

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

Для этого, кроме указанных выше проверок по контрольным позициям, следует провести еще одну проверку на четность для всей строки в целом. Чтобы осуществить такую проверку, следует к каждой строке кода добавить контрольные символы, записанные в дополнительной колонке (таблица, колонка 8). Тогда в случае одной ошибки проверки по позициям укажут номер ошибочной позиции, а проверка на четность – на наличие ошибки. Если проверки позиций укажут на наличие ошибки, а проверка на четность не фиксирует ее, значит в кодовой комбинации две ошибки.

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

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

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

Пусть n=4, k=3.

Запишем образующую матрицу:

В информационные разряды записывается единичная матрица размером n×n. Контрольные разряды заполняются так, чтобы в результате расчета контрольных уравнений получались нули.

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

Руководствуясь вышеизложенным алгоритмом, запишем контрольные уравнения:

Допустим, передали комбинацию 3 1 строки: 1 0 1 1 0 1 0, а на приемной стороне получили 1 0 1 0 0 1 0.

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

f2 f1 f0 = 100 =410 – ошибка в четвертом разряде (а4).

После обнаружения ошибки на приемной стороне 4-й разряд принятой кодовой комбинации должен быть инвертирован (операция «НЕ»), в результате ошибка устраняется.

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

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

Код Хэмминга является типичным примером систематического кода. Однако при его построении к матрицам обычно не прибегают. Для вычисления основных параметров кода задается либо количество информационных символов, либо количество информационных комбинаций N = 2k. При помощи формул

вычисляются k и r . Соотношения между n, k и r для кода Хэмминга представлены в таблице

Таблица 5.10 – Соотношения между n, k, r в коде Хэмминга

Зная основные параметры корректирующего кода, определяют: какие позиции кода будут информационными, а какие проверочными. Как показала практика, номера контрольных символов удобно выбирать по закону 2i, где i = 0, 1, 2 и т.д. – натуральный ряд чисел. Номера контрольных символов в этом случае будут соответственно: 1, 2, 4, 8, 16, 32 и т.д.

Затем определяют значения проверочных разрядов (0 или 1), руководствуясь следующим правилом: сумма единиц на проверочных позициях должна быть четной. Если эта сумма четна, то значение контрольного разряда – 0, в противном случае – 1.

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

n = k + r .

Первой строке соответствует проверочный символ a1 второй – a2 и т.д., как показано в таблице.

Таблица 5.11 – Ряд натуральных чисел в двоичном коде

Затем выявляют проверочные позиции, выписывая коэффициенты по следующему принципу:

в первую проверку входят коэффициенты, которые содержат в младшем разряде 1, т.е. a1, a3,, a5 , a7 , a9 ,a11 и т.д.;

во вторую – коэффициенты, содержащие 1 во втором разряде, т.е. и т.д. a2, a3,, a6 , a7 , a10 ,a11 и т.д.;

Читайте также:  КОДЫ ОШИБОК СТИРАЛКИ VESTEL

в третью проверку – коэффициенты, которые содержат 1 в третьем разряде, и т.д.

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

Таблица 5.12 – Таблица проверок

Старшинство разрядов считается слева направо, а при проверке сверху вниз. Порядок проверок показывает также порядок следования разрядов в полученном двоичном коде.

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

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

Построить код Хэмминга для информационной комбинации 0101. Показать процесс обнаружения ошибки.

Количество информационных разрядов k = 4. Находим значения общей длины кодовой комбинации и число контрольных символов: r = 3 и n = 7. Так как общее количество символов кода n = 7, то контрольные коэффициенты займут три позиции: 1, 2 и 4.

Корректирующий код без значений контрольных коэффициентов будет иметь вид:

b1 b2 0 b3 1 0 1.

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

Первая проверка: сумма П1 Å П3 Å П5 Å П7 должна быть четной, а сумма b1 Å 0 Å 1Å 1 будет четной при b1 = 0.

Вторая проверка: сумма П2 Å П3 Å П6 Å П7 должна быть четной, а сумма b2 Å 0 Å 0 Å 1 будет четной при b2 = 1.

Третья проверка: сумма П4 Å П5 Å П6 Å П7 должна быть четной, а сумма b3 Å 1Å 0 Å 1 будет четной при b3 = 0.

Окончательно корректирующий код принимает вид:

0 1 0 0 1 0 1.

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

Первая проверка: сумма П1 Å П3 Å П5 Å П7 = 0 Å 0 Å 1Å 1 четна. В младший разряд номера ошибочной позиции записываем 0.

Вторая проверка: сумма П2 Å П3 Å П6 Å П7 = 1 Å 0 Å 1Å 1 нечетна. Во второй разряд номера ошибочной позиции записываем 1.

Третья проверка: сумма П4 Å П5 Å П6 Å П7 = 0 Å 1 Å 1Å 1 нечетна. В третий разряд номера ошибочной позиции записываем 1.

Номер ошибочной позиции 1102 = 610. Следовательно, символ шестой позиции следует изменить на обратный.

Код Хэмминга

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

Алгоритм кодирования

Добавим к таблице 5 строк (по количеству контрольных битов), в которые поместим матрицу преобразования. Каждая строка будет соответствовать одному контрольному биту (нулевой контрольный бит — верхняя строка, четвёртый — нижняя), каждый столбец — одному биту кодируемого слова. В каждом столбце матрицы преобразования поместим двоичный номер этого столбца, причём порядок следования битов будет обратный — младший бит расположим в верхней строке, старший — в нижней. Например, в третьем столбце матрицы будут стоять числа 11000, что соответствует двоичной записи числа три: 00011.

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

Алгоритм декодирования

Алгоритм декодирования по Хэммингу абсолютно идентичен алгоритму кодирования. Матрица преобразования соответствующей размерности умножается на матрицу-столбец кодового слова и каждый элемент полученной матрицы-столбца берётся по модулю 2. Полученная матрица-столбец получила название «матрица синдромов». Легко проверить, что кодовое слово, сформированное в соответствии с алгоритмом, описанным в предыдущем разделе, всегда даёт нулевую матрицу синдромов.

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

Заметим, что при однократной ошибке матрица синдромов всегда представляет собой двоичную запись (младший разряд в верхней строке) номера позиции, в которой произошла ошибка. В приведённом примере матрица синдромов (01100) соответствует двоичному числу 00110 или десятичному 6, откуда следует, что ошибка произошла в шестом бите.

Результат работы программы

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Полученный мною опыт

  • Работа с C#;
  • Имею представление, что такое самокорректирующийся код;
  • Изучил алгоритм кодирования и декодирования кодом Хэмминга;
  • Работа с одномерными и двумерными массивами;

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

Код
Хэмминга, как и любой (n,
k)-
код, содержит к
информационных и m
= n-k
избыточных (проверочных) бит.

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

Существуют
различные методы реализации кода
Хэмминга и кодов которые являются
модификацией кода Хэмминга. Рассмотрим
алгоритм построения кода для исправления
одиночной ошибки.

1.
По заданному количеству информационных
символов – k,
либо информационных комбинаций N
= 2k
, используя соотношения:

n
= k+m, 2n
(n+1)2k
и
2m
n+1 (14)

вычисляют
основные параметры кода n
и m.

3.
Определяем значения контрольных разрядов
(0 или 1 ) при помощи многократных проверок
кодовой комбинации на четность. Количество
проверок равно m
= n-k.
В каждую проверку включается один
контро-льный и определенные проверочные
биты. Если результат проверки дает
четное число, то контрольному биту
присваивается значение -0, в противном
случае – 1. Номера информационных бит,
включаемых в каждую проверку, определяются
по двоичному коду натуральных n
–чисел
разрядностью – m
(табл.
1, для m
= 4)
или при помощи проверочной матрицы
H(mn),
столбцы которой представляют запись в
двоичной системе всех целых чисел от 1
до 2k
–1
перечисленных в возрастающем порядке.
Для
m = 3
проверочная матрица имеет вид

Количество
разрядов m
– определяет количество проверок.

В
первую проверку включают коэффициенты,
содержащие 1 в младшем (первом) разряде,
т. е. b1,
b3,
b5
и т. д.

Во
вторую проверку включают коэффициенты,
содержащие 1 во втором разряде, т. е. b2,
b3,
b6
и т. д.

В
третью проверку – коэффициенты которые
содержат 1 в третьем разряде и т. д.

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

Читайте также:  Коды ошибок на ниссан x trail

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

Пример
1.
Построить код Хемминга для передачи
сообщений в виде последовательности
десятичных цифр, представленных в виде
4 –х разрярных двоичных слов. Показать
процесс кодирования, декодирования и
исправления одиночной ошибки на примере
информационного слова 0101.

1.
По заданной длине информационного слова
(k
= 4),
определим количество контрольных
разрядов m,
используя соотношение:

при
этом n
= k+m = 7,
т. е. получили (7, 4) -код.

2.
Определяем номера рабочих и контрольных
позиции кодовой комбинации. Номера
контрольных позиций выбираем по закону
2i
.

Для
рассматриваемой задачи (при n
= 7)
номера контрольных позиций равны 1, 2,
4. При этом кодовая комбинация имеет
вид:

3.
Определяем значения контрольных разрядов
(0 или 1), используя проверочную матрицу
(5).

k1

b3
b5
b7
= k1011
будет четной при k1
=
0.

k2

b3
b6
b7
= k2001
будет четной при k2
=
1.

k3

b5
b6
b7
= k3101
будет четной при k3
=
0.

1
2 3 4 5 6 7

Передаваемая
кодовая комбинация: 0 1 0 0 1 0 1

Допустим
принято: 0 1 1 0 1 0 1

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

1)
k1

b3
b5
b7
= 0111 = 1.

2)
k2

b3
b6
b7
= 1101 = 1.

Сравнивая
синдром ошибки со столбцами проверочной
матрицы, определяем номер ошибочного
бита. Синдрому 011 соответствует третий
столбец, т. е. ошибка в третьем разряде
кодовой комбинации. Символ в 3 -й позиции
необходимо изменить на обратный.

Пример
2.
Построить код Хэмминга для передачи
кодовой комбинации 1 1 0 1 1 0 1 1. Показать
процесс обнаружения и исправления
ошибки в соответствующем разряде кодовой
комбинации.

Решение:
Рассмотрим
алгоритм построения кода для исправления
одиночной ошибки.

1.
По заданной длине информационного слова
(k
= 8)
, используя соотношения вычислим основные
параметры кода n
и m.

при
этом n
= k+m = 12,
т. е. получили (12, 8)-код.

При
этом кодовая комбинация имеет вид:

к1
к2
1
к3
1
0 1 к4
1
0 1 1

3.
Определяем значения контрольных разрядов
(0 или 1) путем много-кратных проверок
кодовой комбинации на четность. Количество
проверок равно m
= n-k.
В каждую проверку включается один
контрольный и определенные проверочные
биты.

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

0001
b1
Количество разрядов m – определяет
количество прове-

0110
b6
четная при к2=1

Передаваемая
кодовая комбинация: 1 2 3 4 5 6 7 8 9 10 11 12

1
1 1 1 1 0 1 1 1 0 1 1

Допустим,
принято: 1 1 1 1 0 0 1 1 1 0 1 1

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

Обнаружена
ошибка в разряде кодовой комбинации с
номером 0101, т. е. в 5 -м разряде. Для
исправления ошибки необходимо
проинвертировать 5 -й разряд в кодовой
комбинации.

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Рис.
1. Схема кодера -а
и декодера –б
для простого (7, 4) кода Хэмминга

Рассмотрим
применение кода Хэмминга. В ЭВМ код
Хэмминга чаще всего используется для
обнаружения и исправления ошибок в ОП,
памяти с обнаружением и исправлением
ошибок ECC Memory (Error Checking and Correcting). Код
Хэмминга используется как при параллельной,
так и при последовательной записи. В
ЭВМ значительная часть интенсивности
потока ошибок приходится на ОП. Причинами
постоянных неисправностей являются
отказы ИС, а случайных изменение
содержимого ОП за счет флуктуации
питающего напряжения, кратковременных
помех и излучений. Неисправность может
быть в одном бите, линии выборки разряда,
слова либо всей ИС. Сбой может возникнуть
при формировании кода (параллельного),
адреса или данных, поэтому защищать
необходимо и то и др. Обычно дешифратор
адреса встроен в м/схему и недоступен
для потребителя. Наиболее часто ошибки
дают ячейки памяти ЗУ, поэтому главным
образом защищают записываемые и
считываемые данные.

Наибольшее
применение в ЗУ нашли коды Хэмминга с
dmin=4,
исправляющие одиночные ошибки и
обнаруживающие двойные.

Проверочные
символы записываются либо в основное,
либо специальное ЗУ. Для каждого
записываемого информационного слова
(а не байта, как при контроле по паритету)
по определенным правилам вычисляется
функция свертки, результат которой
разрядностью в несколько бит также
записывается в память. Для 16 -ти разрядного
информационного слова используется 6
дополнительных бит (32- 7 бит, 64 –8 бит).
При считывании информации схема контроля,
используя избыточные биты, позволяет
обнаружить ошибки различной кратности
или исправить одиночную ошибку. Возможны
различные варианты поведения системы:


исправление однократной ошибки и
уведомление системы только о многократных
ошибках;


не исправление ошибки, а только уведомление
системы об ошибках;

Модуль
памяти со встроенной схемой исправления
ошибок –EOS 72/64 (ECC on Simm). Аналог микросхема
к 555 вж 1
-это 16 разрядная схема с обнаружением
и исправлением ошибок (ОИО) по коду
Хэмминга (22, 16), использование которой
позволяет исправить однократные ошибки
и обнаружить все двух кратные ошибки в
ЗУ.

Избыточные
(контрольные) разряды позволяют обнаружить
и исправить ошибки в ЗУ в процессе записи
и хранения информации.

В
составе ВЖ-1 используются 16 информационных
и 6 контрольных разрядов. (DB – информационное
слово, CB – контрольное слово).

При
записи осуществляется формирование
кода, состоящего из 16 информационных и
6 контрольных разрядов, представляющих
результат суммирование по модулю 2
восьми информационных разрядов в
соответствии с кодом Хэмминга.
Сформированные контрольные разряды
вместе с информационными поступают на
схему и записываются в ЗУ.

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

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

Любая
однократная ошибка в 16 разрядном слове
данных изменяет 3 байта в 6 разрядном
контрольном слове. Обнаруженный ошибочный
бит инвертируется.

Задание к лабораторной
работе

1.
Определить длину информационной i
, длину проверочной k
последовательности кода и формируем
код Хэмминга.

2.
Построить порождающую матрицу кода.

3. Построить проверочные матрицы кода
в модифицированном (с проверкой на
четность) виде.
4. Сформировать системы
проверочных и синдромных уравнений.

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

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

1.
Определяем длину информационного
i
и длину
проверочного к
последовательного
кода и формируем код Хэмминга.

Нам
дана длина кода – n.
Информационные и проверочные биты
определим из соотношения:

Т.к.
длина кода n=7,
а длину информационного кода возьмем
равную i=4,
то согласно соотношению (1) количество
проверочных бит k=n-i,
k=3:

Формируем
код Хэмминга: k1
k2
i3
k4
i5
i6
i7
(проверочные
биты стоят на местах: 20,
21,
22,
23
и т.д.):

4.
00100 00010  k2
=
i3

i6
i7

2.
Кодом Хэмминга
называется (n,k)-код, проверочная матрица
которого имеет i
= n-k строк и 2i-1
столбцов, причем столбцами являются
все различные ненулевые последовательности.
Столбец Р – проверка на четность.
Строим
порождающую матрицу кода, которая
состоит из единичной матрицы Ii,
содержащей информационные биты и
прямоугольной матрицы Ki,k,
составленной из проверочных битов:

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

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

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

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

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

Читайте также:  Код предупреждения о фатальной ошибке 10 и статус ошибки Windows schannel 1203

Как видно из
полученного результата – ошибки нет.

Произведение
некоторого кодового слова Gi’,
т.е. с ошибкой, на транспонированную
проверочную матрицу называется синдромом
и обозначается Si:
Gi’·H(n,
k)T=
Si.

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

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

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

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

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

Возьмем произвольный информационный
код: i
= 0110.

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

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

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

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

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

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

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

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

1 Двоичные циклические коды

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

Циклическими
называют
линейные (n,k)-коды,
обладающие
следующим свойством:
для любого кодового слова:

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

существует другое
кодовое слово:

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Для
описания циклических кодов используют
полиномы с фиктивной переменной
X.

Его
можно описать полиномом

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

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

Наибольшая
степень фиктивной переменной X
в
слагаемом с ненулевым
коэффициентом называется степенью
полинома. В вышеприведенном примере
получился полином 4-й степени.

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

Рассмотрим
алгебраические действия над полиномами,
используемые в теории
циклических кодов. Суммирование
полиномов разберем на примере
С(Х)=А(Х)+В(Х).

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Таким
образом, при суммировании коэффициентов
при X
в одинаковой степени
результат берется по модулю 2. При таком
правиле вычитание эквивалентно
суммированию.

Рассмотрим
умножение на примере умножения полинома
(X3+X1+X0)

Х4+
X3+
X2+0*X1+X0

Операция
– обратная умножению -деление. Деление
полиномов выполняется как обычно, за
исключением того, что вычитание
выполняется по модулю 2. Вспомним, что
вычитание по модулю 2 эквивалентно
сложению по модулю 2

Пример
деления полинома X6+X4+X3
на полином
X3+X2+1

X5
+X4
+ 0*X3+
X2

Проверим это на
примере.

Пусть требуется
выполнить циклический сдвиг влево на
одну позицию

В результате должен
получиться полином

В
основе циклического кода лежит образующий
полином r-го
порядка
(напомним, что r-
число дополнительных разрядов). Будем
обозначать
его gr(X).

Образование
кодовых слов (кодирование) КС
выполняется
путем умножения
информационного полинома с коэффициентами,
являющимися информационной
последовательностью
И(Х)
порядка
i<k
на
образующий полином gr(X)

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

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

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

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

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Образующий
полином выбирается таким, чтобы при
данном r
как
можно
большее число отношений ВО(Х)/g(Х)
давало
различные остатки.

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

Этот недостаток
был устранен следующим образом.

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

Эти
дополнительные разряды предлагается
находить по следующей формуле:

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Порядок
полинома ДР(Х)
гарантировано
меньше r
(поскольку
это остаток).

Приписывание
дополнительных разрядов к информационной
последовательности,
используя алгебру полиномов, можно
описать формулой:

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

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

Покажем,
что получаемые по вышеприведенному
алгоритму кодовые
слова являются кодовыми словами
циклического линейного кода. Для
этого нужно убедиться в том, что
произвольное разрешенное кодовое
слово делится на образующий полином
g(X)
без остатка:

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

где
d(Х)
– целая
часть результата деления.

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

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки


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

Декодирование

А теперь представим, что к нам пришло сообщение с ошибкой. Вот оно «100110001100001011101».
Мы знаем, что в него добавлены избыточные биты по алгоритму Хемминга, и нам надо проверить, есть в нём ошибка или нет.

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

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

В первом оставляем нуль, ибо в подконтрольных битах чётное число единиц.

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Вычисляем все остальные контрольные биты по описанному выше алгоритму (мне лень заново его описывать тут), и получаем, что не совпадают контрольные биты под номерами 1 и 8:

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Теперь складываем номера этих контрольных бит: 1 + 8, и получаем 9 — номер бита, в котором закралась ошибка! Ура! Теперь просто меняем девятый бит на обратный — с единицы на нуль, — и получаем исходное сообщение!

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

Сначала в исходное сообщение добавляем контрольные биты и устанавливаем их в нуль.
Контрольные биты располагаются в тех номерах битов, которые равны степеням двойки (ибо алфавит двоичный).
То есть. Два в степени нуль — это единица, два в степени 1 = два, два в степени 2 = четыре, а два в степени 3 = восемь, два в степени 4 = 16
Значит контрольные биты будут находиться в «буквах»(битах) под номерами 1, 2, 4, 8 и 16.

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

В остальные номера бит переписываем исходное сообщение.

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Видно, что длина «слова» из-за такой избыточности увеличилась на пять «букв». В данном случае, конечно. У вас количество дополнительных бит будет зависеть от длины исходного «слова».

Теперь нужно вычислить эти контрольные биты.
Каждый контрольный бит с номером N «контролирует» непрерывную последовательность из N битов, через каждые N битов.

Вот на картинке отмечено иксами (X), какие биты нужно использовать для вычисления первого контрольного бита (с номером «1»)

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Для вычисления контрольно бита нужно просто сложить все «буквы» нашего «слова», которые он контролирует, а затем принять нелёгкое решение: если сумма получилась чётная, то пишем в результате нуль, а если нечётная — единицу.

Вычисляем первый бит.
Складываем биты под номерами 3,5,7,9,11,13,15,17,19,21
Это будет 0 + 1 + 0 + 0 + 0 + 0 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 = 5
Получилось 5 (пять). Сумма нечётная (на два нацело не делится). Значит пишем в первый бит единицу:

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

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

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

То есть будем теперь суммировать биты, начитая с третьего по номеру, и далее те, которые отмечены иксом (X).
Их номера 3, 6, 7, 10, 11, 14, 15, 18, 19.
Это будет 0 + 0 + 0 + 1 + 0 + 0 + 1 + 1 + 1 = 4
Четыре — число чётное, значит оставляем в нашем втором бите нуль.

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Переходим к вычислению третьего контрольного бита. Но это у нас он контрольный — третий. А в сообщении этот бит записан под номером 4 — четыре.

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Значит и использовать будем все попадающие под наше правило биты, начиная с пятого.
А это биты под номерами 5, 6, 7, 12, 13, 14, 15, 20, 21.
Складываем их: 1 + 0 + 0 + 0 + 0 + 0 + 1 + 0 + 1 = 3
В итоге у нас нечётное число, значит пишем в наш контрольный бит единицу.

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

Осталось всего ничего — вычислить два оставшихся контрольных бита, которые под номерами 8 и 16.

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

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

А в 16-м тоже сумма бит получается чётной — оставляем нуль:

Построить код хэмминга для комбинации 101010 показать процесс исправления и обнаружения ошибки

В итоге мы получили слово с кодом Хэмминга, которое содержит избыточные биты (в сумме 21): «100110000100001011101».

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *