Обнаружение ошибки

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

Разрешенными кодовыми комбинациями называются те, которые присутствуют в исходной кодовой таблице. Например, если сформирован код

Исходные символы	Информационные разряды кода	Проверочный разряд кода	Результирующий код
a	00	0	000
b	01	1	011
c	10	1	101
d	11	0	110

то кодовые комбинации из графы Результирующий код являются разрешенными кодовыми комбинациями. Их количество равно числу исходных символов (m).

Запрещенные кодовые комбинации – это те, которые отсутствуют в исходной кодовой таблице. Их количество  определяется по формуле: 2^r – m, где r – общее число двоичных разрядов (информационные плюс проверочные) в коде.

Сформируем все разрешенные и запрещенные кодовые комбинации для кода из приведенной выше таблицы, при этом используем схему формирования кода Грея:

	0	0
00	a
01		b
11	d
10		c

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

Как видно из последней таблицы, отстояние кодовых комбинаций для исходных символов a, b, c, d равно двум разрядам:

• символы, находящиеся в одном столбце (a и d, b и c), имеют одинаковый проверочный разряд, но находятся в несмежных строках, которые различаются двумя разрядами;

• символы, находящиеся в смежных строках (a и b, b и d, d и c), которые различаются одним разрядом, расположены попарно в разных столбцах, имеющих различное обозначение.

Поэтому при наличии ошибки кратности 1 кодовая комбинация переходит в соседнюю запрещенную.

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

Существует связь между кодовым расстоянием d и минимальной кратностью ошибки q, которую код может обнаруживать:

d ≥ q + 1.                                                

Пример 1. На базе кода из таблицы построить код, обнаруживающий ошибки кратности 2. 

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

Поскольку код для обнаружения ошибки кратностью 1 построен, используем его для обозначения строк схемы, причем с каждой строкой свяжем символ, который соответствует данной кодовой комбинации: так с первой строкой свяжем символ a, со второй – b и т.д. Очевидно, кодовые комбинации в обозначении строк схемы различаются двумя разрядами.

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

С учетом сделанных замечаний схема имеет 4 столбца и 4 строки и представлена ниже:

	00	01	11	10
000	a
011		b
110			d
101				c

Таким образом, построен следующий код:

00000 → a, 01101 → b, 11011 → d, 10110 → c.

Определим кодовое расстояние d построенного кода. Поскольку d_ab = 3; d_ad  = 4;        d_bd = 3; d_ac  = 3; d_bc = 4; d_cd = 3, d_min = {3, 4, 3, 3, 4, 3} = 3.

Проверим, обнаруживает ли построенный код ошибку кратности 2. Для этого зададимся произвольной кодовой комбинацией, например, 01101 (символ b). Результат проверок приведен в таблице:

Передаваемая кодовая комбинация	Ошибка	Принимаемая кодовая комбинация	Результат декодирования
01101	00011	01110	Невозможно декодировать
01101	00101	01000	То же
01101	00110	01011	"-"
01101	01001	00100	"-"
01101	01010	00111	"-"
01101	01100	00001	"-"
01101	10001	11100	"-"
01101	10010	11111	"-"
01101	10100	11001	"-"
01101	11000	10101	"-"

Таким образом, задача решена.