Глава 13. ЭЛЕМЕНТЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ

13.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ПОНЯТИЯ

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

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

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

Примеры двоичных векторов длины три!

Определение. Двоичным кодом называется множество двоичных векторов.

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

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

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

Пример. Натуральный двоичный код, состоящий из векторов длины три, имеет вид: .

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

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

Заметим, что натуральный двоичный код длины имеет мощность, определяемую по формуле

Определение. Расстоянием в смысле Хэмминга между двумя двоичными векторами (обозначается ) называется число двоичных компонент, в которых эти векторы отличны друг от друга.

Пример.

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

Пример.

Векторы различаются в четырех компонентах. Следовательно

Определение. Весом в смысле Хэмминга двоичного вектора (обозначается ) называется число единиц в векторе

Прщмер.

Определение. Минимальным расстоянием в смысле Хэмминга кода (обозначается называется наименьшее из всех возможных расстояний Хэмминга для векторов кода С.

Пример.

Следовательно,

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

Пример. Предположим, при передаче сообщения ожидается появление вектора За счет искажений при передаче вместо вектора появляется вектор Следовательно, кратность ошибки

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

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

Рассмотрим построение кода с обнаружением однократной ошибки из натурального двоичного кода С длины три:

Отнесем вектор 000 к коду . Векторы и 001, образуемые из вектора 000 искажением одного разряда, вычеркнем из кода Среди оставшихся векторов кода выбираем вектор относя его к коду Векторы образуемые из вектора искажением одного разряда» вычеркиваем из кода Продолжаем процедуру до тех пор, пока не исчерпаем все векторы кода . В результате получим код имеющий и обнаруживающий ошибку кратности

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

Таблица 13.1

функции имеет вид

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

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

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

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

если код корректирует ошибку кратности то любые два вектора кода при искажении ошибкой кратности не должны давать один и тот же вектор с ошибкой.

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

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

Рис. 13.1

Таблица 13.2

Рассмотрим построение кода с исправлением однократной ошибки из натурального двоичного кода длины три: Отнесем к коду вектор а все векторы, отстоящие от него на расстоянии вычеркнем из натурального кода. Очевидно, это будут векторы В натуральном коде остался единственный вектор 111, который отнесем к коду Получен код «коррекцией однократной ошибки. Схема коррекции ошибок для данного кода может быть построена следующим образом. Пронумеруем разряды вектора кода слева направо в порядке возрастания номеров. Тогда булевы функции коррекции ошибки могут быть заданы следующей таблицей истинности (табл. 13.2). Аналитическое выражение для функций имеет вид

Если то ошибки отсутствуют. Если то необходимо проинвертировать (для получения правильного вектора) третий разряд вектора и т. д. Функции определяют процедуру корректирования ошибок.

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

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

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

где — число сочетаний из по а к верхней оценке — границу Варшамова Гильберта

где — число проверочных разрядов систематического кода. Существуют и другие оценки: граница Плоткина, Элайса и т. д. Для кодов с различными параметрами имеются специальные таблицы, полученные конкретным просчетом и определяющие минимальное число добавляемых проверочных разрядов.