4.3. Граница, основанная на принципа плотной упаковки сфер

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

Теорема 4.5. Любой код длины с минимальным весом или больше должен иметь по крайней мере

проверочных символов.

Эту оценку называют обычно границей Хэмминга. Практически она справедлива и для нелинейных кодов.

Для этого случая тоже можно получить асимптотические формулы. Пусть для простоты Положим

Тогда по теореме 4.5 при

и, используя результаты, приведенные в приложении А, легко показать, что

Это предельное значение границы Хэмминга показано на рис. 4.1.

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

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

где наибольшее целое число, удовлетворяющее соотношению

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

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

Обозначим через границу для надежности, основанную на принципе плотной упаковки сфер:

где функция, определяемая в приложении А. Кроме того,

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

Из этого соотношения следует значение для которое может быть использовано в (4.12) при очень больших значениях Можно получать более тонкие результаты и более точные границы, однако они сложны. Работы [87, 125, 126] и [117] содержат дальнейшие уточнения приведенных оценок.