Определение проверочных равенств

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

Рассмотрим в качестве примера опознаватели для кодов предназначенных исправлять единичные ошибки (табл. 5.6).

Таблица 5.6.

Опознаватели одиночных ошибок

Номер разряда Опознаватель
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
10 1010
11 1011
12 1100
13 1101
14 1110
15 1111
16 10000

В принципе можно построить код, усекая эту таблицу на любом уровне. Однако, из таблицы видно, что оптимальными будут коды (7; 4), (15; 11), где первое число равно n, а второе k, и другие, которые среди кодов, имеющих одно и то же число проверочных символов, допускают наибольшее число информационных символов. http://peredacha-informacii.ru/ Усечем эту таблицу на седьмом разряде и найдем номера разрядов, символы которых должны войти в каждое из проверочных равенств.

Предположим, что в результате первой проверки на четность для младшего разряда опознавателя будет получена единица. Очевидно, это может быть следствием ошибки в одном из разрядов, опознаватели которых в младшем разряде имеют единицу. Следовательно, первое проверочное равенство должно включать символы 1, 3, 5 и 7-го разрядов:

a1 a3 a5 a7 = 0.

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

a2 a3 a6 a7 = 0.

Аналогично находим и третье равенство:

a4 a5 a6 a7 = 0.

Чтобы эти равенства при отсутствии ошибок удовлетворялись для любых значений информационных символов в кодовой комбинации, в нашем распоряжении имеется три проверочных разряда. Мы должны так выбрать номера этих разрядов, чтобы каждый из них входил только в одно из равенств. Это обеспечит однозначное определение значений символов в проверочных разрядах при кодировании. Указанному условию удовлетворяют разряды, опознаватели которых имеют по одной единице. В нашем случае это будут первый, второй и четвертый разряды.

Таким образом, для кода (7; 4), исправляющего одиночные ошибки, искомые правила построения кода, т.е. соотношения, реализуемые в процессе кодирования, принимают вид:

a1 = a3 a5 a7;

a2 = a3 a6 a7;

a4 = a5 a6 a7.

Поскольку построенный код имеет минимальное хэммингово расстояние dmin = 3, он в соответствии с dr + 1, может использоваться с целью обнаружения единичных и двойных ошибок. Обращаясь к табл. 5.6, легко убедиться, что сумма любых двух опознавателей единичных ошибок дает ненулевой опознаватель, что и является признаком наличия ошибки, но в этом случае нельзя исправить одиночные ошибки.