Лабораторная работа 3
Построение двоичного группового кода (кода Хемминга)
Цели работы:
изучение основных принципов помехоустойчивого кодирования;
построение кода Хэмминга и его оценка;
программная реализация двоичного группового кода.
Теоретические сведения
Код Хемминга – один из наиболее распространенных систематических кодов, имеющих простой и удобный для технической реализации алгоритм обнаружения и исправления одиночной ошибки.
Код Хемминга строится так, чтобы полученный при проверках ре зультат (r1, r2,...rn – k) прямо указал номер искаженного разряда и тем самым упростил декодирование.
Уравнения кодирования для определения проверочных разрядов нахо дят приравниванием проверочных уравнений нулю при отсутствии ошибок. Проверочные разряды различаются внутри кодовой комбинации на местах, соответствующих номеру.
Для вычисления основных параметров кода задается количество либо информационных символов, либо информационных комбинаций: .
При помощи следующих формул вычисляются n и nk:
Соотношение между N, nk и nu для кода Хэмминга представлены в табл. 1.
Таблица 1
N
|
nи
|
nk
|
n
|
nи
|
nk
|
1
|
0
|
1
|
9
|
5
|
4
|
2
|
0
|
2
|
10
|
6
|
4
|
3
|
1
|
2
|
11
|
7
|
4
|
4
|
1
|
3
|
12
|
8
|
4
|
5
|
2
|
3
|
13
|
9
|
4
|
6
|
3
|
3
|
14
|
10
|
4
|
7
|
4
|
3
|
15
|
11
|
4
|
8
|
4
|
4
|
16
|
11
|
5
|
Зная основные параметры корректирующего кода, определяют, какие позиции сигналов будут рабочими, а какие – контрольными. Практика пока зала, что номера контрольных символов удобно выбирать по закону 2i, где i = 0, 1, 2, 3... – натуральный ряд чисел. Номера контрольных символов в этом случае равны 1, 2, 4, 8, 16, 32... Затем определяют значения контрольных ко эффициентов (0 или 1), руководствуясь следующим правилом: сумма единиц на проверочных позициях должна быть четной. Если эта сумма четна – зна чение контрольного коэффициента 0, в противном случае – 1.
Проверочные позиции выбирают следующим образом. Составляют та бличку для ряда натуральных чисел в двоичном коде. Число ее строк равно: n = nи + nk. Первой строке соответствует проверочный коэффициент а1, второй – а2 и т. д.
0001 а1 0101 а5 1001 а9
0010 а2 0110 а6 1010 а10
0011 а3 0111 а7 1011 а11
0100 а4 1000 а8
Затем выявляют проверочные позиции, выписывая коэффициенты по следующему принципу: в первую проверку входят коэффициенты, которые содержат 1 в младшем разряде, т. е. а1, а3, а5, а7, а9, а11 и т. д.; во вторую – содержащие 1 во втором разряде, т. е. а2, а3, а6, а7, а10 и т. д.; в третью – со держащие 1 в третьем разряде, и т. д. Номера проверочных коэффициентов соответствуют номерам проверочных позиций, что позволяет составить об щую таблицу проверок (табл. 2).
Таблица 2
Номер
проверки
|
Проверочные позиции (П)
|
Номер контрол.
символа
|
1
|
1, 3, 5, 7, 11,…
|
1
|
2
|
2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 24,...
|
2
|
3
|
4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22,23,...
|
4
|
4
|
8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28,…
|
|
|
29, 30, 31, 40, 41, 42,...
|
8
|
Пример. Требуется исправить любую одиночную ошибку при переда че комбинации 0101, т. е. nu = 4.
Решение. Согласно табл. 1 минимальное число контрольных символов nk = 3, при этом n = 7. Контрольные коэффициенты будут расположены на по зициях 1, 2, 4. Составляем макет корректирующего кода и записываем его во вторую колонку в табл. 3. Пользуясь табл. 2, определим значения коэффици ентов К1, К2, К3.
Первая проверка: сумма П1 + П3 + П5 + П7 должна быть четной, а сумма К1 + 0 + 1 + 1 будет четной при К1 = 0.
Вторая проверка: сумма П2 + П3 + П6 + П7 должна быть четной, а сумма К2 + 0 + 0 + 1 будет четной при К2 = 1.
Третья проверка: сумма П4 + П5 + П6 + П7 должна быть четной, а сумма К3 + 1 + 0 + 1 будет четной при К3 = 0.
Окончательное значение искомой комбинации корректирующего кода записываем в третью колонку в таблице 3.
Таблица 3
Позиция символов
корректирующего кода
|
Кодовое слово
|
|
без значений контрольных коэффициентов
|
со значениями контрольных коэффициентов
|
1
|
К1
|
0
|
2
|
К2
|
1
|
3
|
0
|
0
|
4
|
К3
|
0
|
5
|
1
|
1
|
6
|
0
|
0
|
7
|
1
|
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.
Номер ошибочной позиции 101 = 6. Следовательно, символ шестой по зиции следует изменить на обратный, и мы получим правильную кодовую комбинацию.
Задание
Ознакомиться с теоретической частью, используя дополнительную литературу.
Построить код Хемминга по заданным исходным данным (число информационных разрядов k).
Составить систему уравнений кодирования для определения прове рочных разрядов для кода Хемминга по пункту 2.
Провести программный контроль выполнения 2 и 3 пунктов на при мере случайных кодовых комбинаций.
Составить отчет.
Контрольные вопросы
На каких позициях проверочные символы в коде Хэмминга?
Что такое информационные и проверочные символы?
Какими графическими и геометрическими способами можно пред ставить коды? Приведите пример.
Что такое кодовое расстояние? Как оно определяется между двумя комбинациями двоичного кода?
Каким соотношением связаны информационные, проверочные сим волы и минимальное кодовое дерево?
|
