Тема 6. Помехоустойчивое кодирование

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

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

Двоичным вектором длины называется -компонентный вектор		(	), каж-
дая компонента которого	может принимать значение 0 либо 1.
Двоичным кодом	называется множество двоичных векторов.

Двоичный код называется равномерным, если он содержит только векторы одинаковой длины. В противном случае код называется неравномерным.

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

Двоичный код называется натуральным, если он содержит все возможные векторы заданной длины.

Длина двоичного кода равна длине его двоичного вектора.

Мощность двоичного кода — число всех различных векторов кода. Мощность кода обозначается | |.

	Натуральный двоичный код длины имеет мощность, определяемую по формуле
	| |	.
	Расстоянием в смысле Хэмминга между двумя двоичными векторами и		(обозначается
(	)) называется число двоичных компонент, в которых эти векторы отличны друг от друга.
	Весом в смысле Хэмминга двоичного вектора	(обозначается ( )) называется число еди-
ниц в векторе .
	Минимальным расстоянием в смысле Хэмминга кода (обозначается		) называется
наименьшее из всех возможных расстояний Хэмминга для векторов кода .

Ошибкой называется искажение вектора кода. Кратностью ошибки (обозначается ) называется число компонент вектора, искажаемых ошибкой.

Общий подход к обнаружению ошибок

Общий подход к обнаружению ошибок, возникающих в векторах некоторого кода , основан на следующем простом допущении: векторе ошибкой не принадлежит коду . Если это выполняется, то, построив схему, анализирующую принадлежность векторов коду , ошибку можно обнаружить. Очевидно, натуральный двоичный код не обладает обнаруживающей способностью к ошибкам, так как произвольное искажение любого вектора этого кода переводит его в вектор, также принадлежащий натуральному коду. Для получения кода с обнаружением ошибки (например, -кратной) из натурального кода необходимо удалить некоторые векторы, руководствуясь следующим соображением. В натуральном коде выбирается любой вектор. Выбранный вектор относят к коду с обнаружением -кратной ошибки. Все векторы, отстоящие от выбранного на расстоянии Хэмминга из натурального кода, вычёркиваются. Из оставшихся векторов натурального кода снова выбирается один вектор. Выбранный вектор относят к коду с обнаружением -кратной ошибки, а все векторы, отстоящие от выбранного на расстоянии Хэмминга из натурального кода, вычёркивают. Описанную процедуру повторяют до тех пор, пока все векторы натурального кода не будут исчерпаны. В

результате получаем код с обнаружением	-кратной ошибки Очевидно, все векторы такого кода
должны отстоять на расстоянии Хэмминга		, так как векторы с меньшим кодовым расстояни-
ем удалены из натурального кода. Таким образом,		для кода с обнаружением -кратной ошибки
должно соответствовать условию	. Полученное условие относится к одному из основных

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

Общий подход к исправлению ошибок

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

вектор с ошибкой коду не принадлежит;

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

устойчивого кодирования. Для получения кода с коррекцией -кратной ошибки из натурального кода необходимо удалить некоторые векторы, руководствуясь следующими соображениями. В натуральном коде выбирается любой вектор. Выбранный вектор относят к коду с коррекцией -кратной ошибки. Все векторы, отстоящие от выбранного на расстоянии Хэмминга , вычёркивают из натурального кода. Среди оставшихся векторов натурального кода выбирают следующий вектор, относя его к коду с коррекцией -кратной ошибки и т.д. Процедуру повторяют до тех пор, пока все векторы кода не будут исчерпаны.

104

Информационная избыточность помехоустойчивых кодов

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

зано с поиском минимума функции (	)	(	), где — длина систематического кода; —
число информационных разрядов, а		— минимальное расстояние систематического кода в

смысле Хэмминга. Точно определить минимум функции не удаётся. Существуют только верхние и нижние оценки, которые делают это приближённо. К нижней оценке можно отнести так называемую границу Хэмминга:

					1	d
					2		min
		2
			k		Cn
								i
					i 0
где	— число сочетаний из по , а к верхней оценке — границу Варшамова—Гильберта:
		n k			2d		min	1
								i
	2
						Cn i
						i 0
где (	) — число проверочных разрядов систематического кода. Существуют и другие оценки:
граница Плоткина, Элайса и т.д. Для кодов с различными параметрами (									) имеются специаль-

ные таблицы, полученные конкретным просчётом и определяющие минимальное число добавляемых проверочных разрядов.

Код Хэмминга

Современные запоминающие устройства состоят из огромного количества запоминающих элементов, каждый из которых хранит бинарное значение — 0 или 1. При работе подобных устройств могут возникать ошибки, обусловленные воздействием различных факторов. В этом случае для повышения надёжности работы запоминающих устройств используют специальные коды.

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

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

105

передаваемому	-разрядному слову добавляют битов с соответствующим их расположением сре-
ди битов -разрядного слова. Подобные			-разрядные коды (	) были впервые рассмотре-
ны в 1948 г. Р. Хэммингом и с тех пор обычно называются кодами Хэмминга.
Рассмотрим принцип построения кода Хэмминга для 16-разрядного слова данных (						),
исправляющего все одиночные ошибки.
Сначала определим необходимое число проверочных разрядов				(	) из соотноше-
ния:
			,
откуда для	находим	и	.

Далее все биты -разрядного слова нумеруются слева направо начиная с 1, при этом все биты, номера которых равны степени числа 2, являются битами чётности, а остальные — информационными.

В 1, 2, 4, 8 и 16 разрядах данного кода располагаются биты чётности, а в разрядах 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20 и 21 биты данных слова 16-разрядного исходного слова.

Каждый бит чётности используется для контроля лишь определенных разрядов -разрядного слова. Номера контролируемых разрядов для каждого бита чётности приведены в таблице 2.

Таблица 2 — Номера битов чётности и контролируемых ими разрядов слов в коде Хэмминга

	Контрольный разряд/номер бита	Контролируемые разряды
	кода Хемминга
	1/1	1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33…
	2/2	2 3 6 7 10 11 14 15 18 19 22 23 26 27 30 31 34…
	3/4	4 5 6 7 12 13 14 15 20 21 22 23 28 29 30 31 36…
	4/8	8 9 10 11 12 13 14 15 24 25 26 27 28 29 30 31 40…
	5/16	16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 48…
	6/32	32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48…

Как видно из таблицы, в число контролируемых разрядов включается и тот разряд, где расположен сам бит чётности. При этом содержимое бита чётности устанавливается так, чтобы суммарное число единиц в контролируемых им разрядах было чётным.

Код, образованный значениями контрольных разрядов, называют дополнительным кодом. Дополнительный код можно также получить путём инвертирования результата поразрядного сложения (т.е. сложения по модулю 2) номеров тех разрядов кода данных, значения которых равны 1.

Предположим теперь, что из-за воздействия каких-либо возмущающих факторов обнулится одна из единиц в коде Хэмминга. В этом случае номер искажённого разряда определяется суммой номеров неправильных битов чётности.

Определить номер искажённого разряда можно также следующим способом.

После считывания информационного кода данных с искажённым разрядом для него вновь рассчитывается дополнительный код и сравнивается с исходным. Фиксируется код сравнения (по-

106