3.3. Нижняя граница Варшамова — Гилберта

В разд. 1.4 выше были получены верхние границы для произвольных блоковых кодов. Здесь мы получим нижнюю границу Варшамова — Гилберта, которая гарантирует существование линейного кода с заданным числом проверочных символов и заданным минимальным расстоянием число информационных символов которого больше определенной величины (вначале Гилберт получил эту границу для блоковых кодов [14]; Варшамов улучшил результат Гилберта, получив аналогичную границу для линейных кодов [15, 16]).

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

Используя функцию из неравенства Чернова, неравенство (3.7) можно заменить следующим:

В частности, при последнее неравенство имеет вид

Доказательство. Как следует из теоремы 3.1, построение матрицы любые столбцов которой линейно независимы, эквивалентно построению кода с минимальным расстоянием, не меньшим Построим матрицу удовлетворяющую указанному выше свойству, следующим образом. Вначале произвольным образом выберем в множестве - {нулевой вектор} 1-й столбец матрицы Н.

В качестве 2-го столбца матрицы возьмем произвольный вектор из не являющийся произведением Если в существует хотя бы один вектор, не являющийся линейной комбинацией то выберем один из этих векто

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

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

Из этого неравенства и границы Чернова получаются неравенства (3.8) и (3.8).

На фиг. 3.1 показано поведение верхних границ Плоткина, Хэмминга и Элайса, а также нижней границы Варшамова — Гилберта при достаточно больших (здесь по вертикальной оси откладывается скорость кода а по горизонтальной — отношение минимального расстояния [8].

Вывод неравенства (3.7), как мы видели выше, допускает любой способ выбора векторов удовлетворяющих условиям теоремы 3.1. Поэтому если задан линейный -код с минимальным весом параметры которого удовлетворяют неравенству (3.7), то к проверочной матрице этого кода всегда можно добавить еще один столбец, не нарушая при этом условий теоремы 3.1. Другими словами, сохраняя постоянным и число проверочных символов, и минимальный вес и увеличивая число информационных символов, можно расширить исходный код. Как показывают несложные расчеты, минимальный вес почти всех линейных кодов близок к величине, гарантируемой неравенством (3.7) [8]. Из неравенства (3.8) следует, что при фиксированном отношении существуют линейные коды, для которых отношение больше Здесь следует заметить, что для БЧХ-кодов, обладающих хорошими свойствами с точки зрения кодирования и декодирования, при фиксированном отношение

стремится к нулю (см. разд. 4.1). За исключением кодов Юстесена [14], все известные к настоящему времени алгебраические коды обладают этим недостатком. Однако и для кодов Юстесена отношение значительно меньше величины, гарантируемой границей Варшамова — Гилберта. Построение лежащих на границе Варшамова — Гилберта (или близко к ней) кодов, способ построения которых можно было бы задать явно (конструктивно) и которые обладали бы хорошими процедурами кодирования и декодирования, является одной из нерешенных проблем теории кодирования.

Фиг. 3.1.

Так как параметры двоичных БЧХ-кодов с длиной порядка нескольких тысяч являются не столь уж плохими [8] по сравнению с параметрами, задаваемыми (3.8), то исследование асимптотических свойств кодов при больших длинах представляет главным образом теоретический интерес.