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

Одной из важнейших задач построения помехоустойчивого кода с заданными характеристиками является установление соотношения между его способностью обнаруживать или исправлять ошибки и избыточностью, т.е. связь между 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 получили название кодов с максимально достижимым расстоянием (МДР-коды).

Дата добавления: 2014-01-14