2. Коды с и

Из оценки Варшамова — Гильберта следует, что существуют коды, у которых

(XI.2.1)

где и — константы, определяющие точку на кривой, соответствующей нижней границе Варшамова.

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

(XI.2.2)

Действительно, при достаточно больших биномиальное распределение аппроксимируется нормальным. распределением со средним и дисперсией . При этом вероятность правильного приема кодовой комбинации

(XI.2.3)

где по-прежнему

С учетом (XI.2.1) верхний предел интеграла (XI.2.3) можно полагать равным . Используя стандартный прием замены переменных, легко получим

(XI.2.4)

где

(XI.2.5)

и

(XI.2.6)

При значение если дополнительно имеет место условие (XI.2.2), то и, следовательно, вероятность правильного декодирования кодовой комбинации стремится к единице. Если же то, как это следует из (XI.2.6) и, следовательно, .

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

Выполнение условия немедленно приводит к требованию

(XI.2.7)

где

(XI.2.8)

Таким образом, указанная выше задача может быть сформулирована как задача поиска кодов, у которых , а отношение не меньше, чем это требуется по оценке Варшамова.

Обширный класс линейных кодов с отмеченными свойствами может быть найден двустепенной итерацией нескольких простейших кодов. Проиллюстрируем это на двух примерах.

Прежде всего найдем зависимость (XI.2.8) от отношения . На рис. XI.1 представлена кривая, показывающая зависимость от скорости передачи , соответствующей нижней оценке Варшамова. (Эта кривая была построена на основе графика на рис. VI.1.)

В табл. XI.3 показано, каким образом могут быть найдены коды с и (см. рис. (XI.1).

Табл. XI.4. иллюстрирует применение метода Элайеса для отыскания кодов с и .

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

Метод Элайеса позволяет построить коды, удовлетворяющие условию (XI.2.1), хотя и для весьма больших, но все же конечных значений и .

Рис. XI.1. Зависимость — от скорости передачи , соответствующей нижней оценке Варшамова.

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

Таблица XI.3

Таблица XI.4

Это так называемые коды Галлагера [77] с малой плотностью проверок на четность, где каждая проверка охватывает фиксированное небольшое число символов v, причем каждый символ, в свою очередь, входит в небольшое число проверок . Коды Галлагера относятся к случайным кодам, поэтому они здесь не обсуждаются.