Важнейшие границы теории кодирования

 

Значительная часть работ по теории кодирования посвящена установлению и исследованию различных границ для кодов и, в частности, границ для кодового расстояния. Указанные границы представляют собой ориентиры, позволяющие объективно судить, насколько успешно решены задачи построения кодов. Наиболее важными и полезными границами кодового расстояния являются границы Хэмминга, Плоткина и Гильберта.

Теорема 5.6.1. (Граница Хэмминга). Для любого двоичного кода, содержащего кодовых слов длины и исправляющего (и менее) ошибок, выполняется соотношение

, (5.6)

где – биномиальный коэффициент.

Иным вариантом представления границы может служить соотношение

,

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

Доказательство. Вычислим «объем» сферы радиуса , изображенной на рис. 5.3, т.е. определим число точек, находящихся внутри сферы,

.

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

Коды, для которых достигается равенство в границе Хэмминга, называются совершенными. Совершенные коды исправляют любую ошибку кратности и менее, но не исправляют и не обнаруживают ни одной ошибки большей кратности. Геометрически эти коды воплощают т. н. «плотную упаковку», когда все двоичных векторов охвачены сферами радиуса без пересечения и свободного пространства. В этой связи совершенные коды также называют плотно упакованными или сферически упакованными. Их совершенство заключается в достижении максимально возможной скорости при фиксированных и . Среди двоичных кодов известны три класса совершенных кодов – тривиальный код с повторением нечетной длины, коды Хэмминга, исправляющие любую однократную ошибку, и код Голея длины 23 и кодовым расстоянием 7 (исправляет любую 3–кратную ошибку и менее).

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

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

Теорема 5.6.2. (Граница Плоткина). Для любого двоичного блокового кода с параметрами выполняется неравенство

. (5.7)

Применяя границу Плоткина (5.7), достаточно просто определить максимально возможное значение кодового расстояния при заданных и , однако задача усложняется, если использовать ее для определения максимального значения (а значит, и скорости ) при фиксированных и . В связи с этим находит широкое применение и другой вариант границы Плоткина.

Теорема 5.6.3. Для любого двоичного блокового кода с параметрами выполняется неравенство

(5.8)

Рассмотрим теперь примеры, иллюстрирующие область применения границ (5.6), (5.8).

Пример 5.6.1. Определить возможный объем и скорость кода с параметрами и .

Согласно границе Хэмминга (5.6)

,

тогда как из границы Плоткина (5.8) получаем

,

и, значит, более точную оценку дает граница Хэмминга. Отсюда

.

Пример 5.6.2. Определить возможный объем и скорость кода с параметрами и .

Действуя аналогично примеру 5.6.2, получаем следующие оценки мощности кода:

– из границы Хэмминга получаем ;

– из границы Плоткина – ,

и, следовательно, .

Из рассмотренных примеров следует, что граница Хэмминга дает лучший результат для высокоскоростных кодов, тогда как граница Плоткина – для низкоскоростных. Обе границы определяют необходимые (но не достаточные) условия существования блоковых кодов. Не выполнение их свидетельствует о невозможности построения кода с заданными значениями . Вследствие этого указанные границы часто называют верхними. Известны более точные, однако и более сложные границы для всего диапазона значений , примером чего может служить граница Элайеса. Существуют и нижние границы, устанавливающие достаточные условия существования кодов с заданными значениями .

Теорема 5.6.3. (Граница Гильберта). Наверняка существует двоичный блоковый код, параметры которого удовлетворяют неравенству

. (5.9)

Замечание. Если целое число, то существует более строгий вариант границы (5.9), называемый границей Варшамова–Гильберта

. (5.10)

Пример 5.6.3. При каком значении наверняка существует двоичный код с параметрами, заданными в примерах 5.6.1–5.6.2.

Из (5.10) непосредственно получаем:

– для примера 5.6.1:

.

– для примера 5.6.2:

.

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

– для 5.6.1 –

– для 5.6.2 – .

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

и , (5.11)

а граница Гильберта принимает вид

, (5.12)

где, как и ранее, – энтропия двоичного ансамбля.

Рис. 5.4 служит графической иллюстрацией асимптотических границ (5.11–5.12). Область, лежащая выше хотя бы одной из границ (5.11), отвечает тем значениям , при которых не существуют коды с указанными параметрами. Не составляет труда определить, что точка пересечения границ Хэмминга и Плоткина, устанавливающая диапазон использования соответствующей границы, отвечает значению . С другой стороны, те значения , которые соответствуют области, лежащей ниже границы Гильберта, гарантируют существование кода. Область, лежащая между двумя упомянутыми зонами, отвечает неопределенной ситуации, для которой точный ответ о существовании кода не может быть дан на основании приведенных границ. Использование более точных границ, о которых упоминалось выше, позволит лишь
уменьшить зону неопределенности.