35. Код Хэмминга.
Среди кодов с исправлением ошибок наибольшее распространение на практике имеет код Хэмминга. Данный код исправляет ошибки кратности 1 и является разделимым. Число информационных разрядов m = ] log2 N[ где N – число сообщений, которые необходимо передать. Длина кода определяется из неравенства
Рассмотрим задачу нахождения кодовой комбинации кода Хэмминга. Для этого рассмотрим одну из разрешенных кодовых комбинаций. Например m = 5, 01101
Для решения этой задачи построим таблицу1:
|
10ый № разряда |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
|
2ый № разряда |
1001 |
1000 |
0111 |
0110 |
0101 |
0100 |
0011 |
0010 |
0001 |
|
Букв.обозн.разряда |
m9 |
к8 |
m7 |
m6 |
m5 |
k4 |
m3 |
k2 |
k1 |
|
Переданная комб. |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
|
Принятая комб. |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
Для определения значений контрольных разрядов определим в каких клетках табл 1 будут размещаться контрольные разряды.
Для контрольных разрядов применяются те разряды десятичный номер разряда( 10ый № разряда) которых равен степени числа 2. остальные клетки из таблицы будут заполнены информационными разрядами.
Для определения значений контрольных разрядов рассмотрим таблицу2:
|
|
|
|
|
|
|
К1 |
0 |
0 |
0 |
1 |
|
К2 |
0 |
0 |
1 |
0 |
|
3 |
0 |
0 |
1 |
1 |
|
К4 |
0 |
1 |
0 |
0 |
|
5 |
0 |
1 |
0 |
1 |
|
6 |
0 |
1 |
1 |
0 |
|
7 |
0 |
1 |
1 |
1 |
|
К8 |
1 |
0 |
0 |
0 |
|
9 |
1 |
0 |
0 |
1 |
|
10 |
1 |
0 |
1 |
0 |
|
11 |
1 |
0 |
1 |
1 |
|
12 |
1 |
1 |
0 |
0 |
|
13 |
1 |
1 |
0 |
1 |
|
14 |
1 |
1 |
1 |
0 |
|
15 |
1 |
1 |
1 |
1 |
Значения контрольных разрядов определяется с помощью суммы по модулю 2 значений тех информационных разрядов, в двоичном номере(2ый №) которых имеется единица в столбцах, в которых эта единица присутствует во втором номере контрольного разряда.
При анализе принятой кодовой комбинации кода Хэмминга используются контрольные суммы. Контрольные суммы образуются путем сложения по модулю 2 значения контрольного разряда и значении информационных разрядов, образующих этот контрольный разряд.
Контрольная сумма ( S ) должна иметь следующие свойства:
1. она образуется как сумма контрольного и соответствующих ему информационных разрядов.
2. в каждую S входит один контрольный разряд и каждый контрольный разряд входит в одну S.
3. контрольная сумма равна 0, если неискажен информационный разряд.
Код Хэмминга обладает избыточностью R = n/m. Выразить m, через n используя соотношения 2m = ( 2n / (n+1)).
n+1=(2n / 2m )= 2n-m
log2 (n+1) = n-m
m = n – log2 ( n+1) R = (n / (n – log2 (n+1)))