Кодовое расстояние и корректирующая способность кода

Под корректирующей способностью кодапонимается его свойство обнаруживать и/или исправлять ошибку максимальной кратности q. Корректирующая способность кода связана с его кодовым расстоянием.

Расстояниемd_ij между кодами(кодовыми комбинациями) i и j называется число различных разрядов в кодовых комбинациях i и j. Например, если есть коды 01 и 10, расстояние между ними равно 2: они различаются в двух разрядах.

(4.5)

Кодовым расстояниемd для кода, содержащего m кодовых комбинаций, является минимальное расстояние между всеми парами кодовых комбинаций, т.е.

где i¹j, i=1,m; j=1,m.

Для кода из табл. 4.2:

d_ab = 1; d_ad = 2; d_bd = 1; d_ac = 1; d_bc = 2; d_cd = 1.

Тогда d = min{1, 2, 1, 1, 2, 1} = 1. Это означает, что всякая ошибка кратности 1 (и более) переводит исходную кодовую комбинацию в другую кодовую комбинацию, которая также принадлежит коду.

Увеличить кодовое расстояние можно, введя в кодовые комбинации дополнительный разряд (или разряды). Тогда начальные разряды называют информационными, а дополнительный (или дополнительные) – проверочным(проверочными).

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

Вернемся к таблице кодов из табл. 4.2, введем дополнительный разряд и сформируем его значение. Результат – в табл. 4.12.

Таблица 4.12

Исходные символы	Информационные разряды кода	Проверочный разряд кода	Результирующий код
a
b
c
d

Таким образом, полученный код является трехразрядным.

Определим кодовое расстояние полученного кода:

d_ab = 2; d_ad = 2; d_bd = 2; d_ac = 2; d_bc = 2; d_cd = 2.

Тогда d = min{2, 2, 2, 2, 2, 2} = 2.

Пусть передается кодовая комбинация, соответствующая символу c, – 101. Пусть на нее накладывается ошибка кратности 1. Возможные результаты искажения приведены в табл. 4.13.

Таблица 4.13

Передаваемая кодовая комбинация	Ошибка	Принимаемая кодовая комбинация	Результат декодирования
			Невозможно декодировать
			То же
			“-“

В результате данной ошибки получаемые кодовые комбинации невозможно декодировать, так как они отсутствуют в табл. 4.12.

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

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

Сформируем все разрешенные и запрещенные кодовые комбинации для кода из табл. 4.12, при этом используем схему формирования кода Грея (рис. 4.3). Обозначения строк – исходные коды из табл. 4.2, обозначения столбцов – значения проверочных разрядов.

	a
		b
	d
		c

Рис. 4.3. Схема формирования помехозащитного кода из примера

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

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

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

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

До введения проверочного разряда формирование кода из табл. 4.2 можно было представить схемой, показанной на рис. 4.4.

0	a	b
	c	d

Рис. 4.4. Схема формирования кода из примера 4.1

Поскольку символы расположены плотно в схеме, всякое искажение кода приводило к попаданию в другую ячейку с кодом.

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

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

d ³ q + 1. (4.6)

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

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

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

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

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

	a
		b
			d
				c

Рис. 4.5. Схема формирования кода Грея для примера 4.9

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

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). Результат проверок приведен в табл. 4.14.

Таблица 4.14

Передаваемая кодовая комбинация	Ошибка	Принимаемая кодовая комбинация	Результат Декодирования
			Невозможно декодировать
			То же
			“-“
			“-“
			“-“
			“-“
			“-“
			“-“
Продолжение табл. 4.14
			“-“
			“-“

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

В заключение отметим, что существует несколько возможных кодов, решающих задачу из примера 4.9. В самом деле, возможны несколько схем формирования кода, одна из которых показана на рис. 4.6.

		a
	b
			d
				c

Рис. 4.6. Схема формирования кода для примера 4.9 (один из возможных вариантов)