5.1.3 Классификация помехоустойчивых кодов

Уже отмечалось, что помехоустойчивые коды подразделены на два обширных класса – блоковые и непрерывные коды. Блоковые коды в свою очередь делятся на разделимые и неразделимые коды. Очень часто в разделимых кодах избыточные и информационные элементы связываются между собой системами линейных проверочных соотношений. Такие разделимые коды принято называть систематическими кодами. В силу того, что избыточные элементы в систематических кодах являются результатом проверки на четность определенных информационных элементов, то часто избыточные элементы кодовой комбинации называют проверочными.

На рис. 5.4 приведена схема, иллюстрирующая рассмотренную классификацию помехоустойчивых кодов.

Помехоустойчивые коды

Блоковые

Несистематические

Неразделимые

Разделимые

Систематические

Непрерывные

Рис.5.4.

5.1.4.Граничные соотношения между характеристиками помехоустойчивых кодов

Одной из важнейших задач построения помехоустойчивого кода с заданными характеристиками является установление соотношения между его способностью обнаруживать или исправлять ошибки и избыточностью, т.е. связь между n – kиd_min. Существует ряд оценок этой связи. Рассмотрим наиболее популярные. Если код предназначен для исправленияt– кратных ошибок, то в каждой из 2^kзащитных зон его разрешенных комбинаций должно находиться поразличных комбинаций, а общая их сумма, естественно, не должна превышать числа 2ⁿ, т.е.

, или , т.е..

Это соотношение принято называть границей Хэмминга.

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

Данная оценка получила называние границы Варшамова – Гилберта.

Граница Хэмминга указывает, при каком минимальном значении n– kможет существовать помехоустойчивый код, гарантийно исправляющийt– кратные ошибки, а граница Варшамова – Гилберта показывает, при каком значенииn– k определенно существует код с такими свойствами.

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

Можно предположить, что существуют такие способы кодирования, которые допускают n-kотличий кодовых комбинаций на остальныхn-kразрядах.

Суммируя сказанное, приходим к следующему граничному соотношению: d_min≤1+n-k

Эта граница была впервые обоснована Синглтономи носит его имя. Коды, для которых справедливоd_min=n-k+1 получили название кодов с максимально достижимым расстоянием (МДР-коды).

5.1.5.Задачи

1. Определить долю необнаруживаемых трансформаций кодовых комбинаций при передаче информации по каналу с помехами обнаруживающим ошибки кодом, имеющим длину кодовой комбинации n= 256 и число избыточных элементов 16.

2. Определить возможности кода Голея, имеющего n=23,k= 12,d_min= 7 по исправлению, обнаружению, а также совместному обнаружению и исправлению ошибок.

3. Для передачи информации с исправлением однократных ошибок применен код, состоящий из двух комбинаций: 001 и 110. Определить состав защитных зон этих комбинаций.

4. Выбран код, состоящий из следующих четырех комбинаций

11010, 01101, 10111, 00001.

Какую из кодовых комбинаций следует заменить на чисто нулевую комбинацию (00000), чтобы код имел d_min=3?