Обработка и передача дискретных сообщений, лекции и материалы, страница 71

Другое граничное соотношение является следствием следующих рассуждений. Если в сферу с радиусом 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 по исправлению, обнаружению, а также совместному обнаружению и исправлению ошибок.