Определение проверочных равенств
Итак, для любого кода, имеющего целью исправлять наиболее вероятные вектора ошибок заданного канала связи (взаимно независимые ошибки или пачки ошибок), можно составить таблицу опознавателей одиночных ошибок в каждом из разрядов. Пользуясь этой таблицей, нетрудно определить, символы каких разрядов должны входить в каждую из проверок на четность.
Рассмотрим в качестве примера опознаватели для кодов предназначенных исправлять единичные ошибки (табл. 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, он в соответствии с d ≥ r + 1, может использоваться с целью обнаружения единичных и двойных ошибок. Обращаясь к табл. 5.6, легко убедиться, что сумма любых двух опознавателей единичных ошибок дает ненулевой опознаватель, что и является признаком наличия ошибки, но в этом случае нельзя исправить одиночные ошибки.
|