3.5. ПОТЕНЦИАЛЬНЫЕ СВОЙСТВА КОРРЕКТИРУЮЩИХ КОДОВ

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

Утверждение 3.9. Существуют блочные линейные коды над полем кодовое расстояние которых при любой скорости передачи и удовлетворяет неравенству где граница (оценка) Варшамова — Гилберта для -ичных кодов, определяемая равенством

При

а при

Доказательство утверждения 3.9 дано в [35]. В [58] для эта граница несколько улучшена.

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

Существует также верхняя оценка [35, 59].

Утверждение 3.11. Не существует двоичных блочных кодов (линейных или нелинейных), для которых при превосходит величину

где - оценка Бассалыго — Элайеса, а — оценка Плоткина, справедливая при если только .

Аналогичные границы существуют для сверточных кодов, на которых здесь останавливаться не будем [60].

Рассмотрим теперь оценку вероятности ошибочного декодирования, полученную в [24].

Утверждение 3.12. Существуют -ичные линейные блочные коды, для которых вероятность ошибочного декодирования по максимуму правдоподобия в произвольном -ичном канале без памяти (в канале с входами и выходами) при любой скорости передачи, не превосходящей пропускной способности канала с, задаваемой (2.47), оценивается сверху выражением

где

— соответственно экспоненты Галлагера для случайного ансамбля блочных кодов и для ансамбля блочных кодов с выбрасыванием; -распределение вероятностей на входном алфавите канала; матрица переходных вероятностей канала, а

Для определения экспоненты вероятности ошибки необходимо максимизировать задаваемые с помощью (3.34), (3.35) как по 0, так и по Целесообразно вначале проводить максимизацию по Функция не является выпуклой вверх функцией однако она оказывается равной взятому со знаком минус логарифму выпуклой вниз функции. Обозначим

Значение на котором достигается максимум будет максимизировать Теперь, используя выпуклость легко найти максимум на ЭВМ.

Функция также не является выпуклой вниз функцией Однако если матрица вида является неотрицательно определенной, то функция

является выпуклой вниз по Далее, аналогично вычислению

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

Очень важной задачей является возможность реализации потенциальных свойств корректирующих кодов. При этом ключевым является понятие сложности. По традиции принято оценивать раздельно сложность задания кода длины на многоленточной машине Тьюринга и сложность осуществления кодирования и декодирования на функциональных элементах — Подробно эти вопросы рассматриваются в [32, 61].

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

Варшамова — Гилберта и Галлагера, и такие кодирование и декодирование, что

Утверждение 3.14 [55]. Существуют такие двоичные ОК-коды бесконечного порядка, что для всех скоростей 0,19 вероятность ошибочного декодирования в симметричном канале удовлетворяет границе Галлагера, а сложность декодирования удовлетворяет неравенству

Утверждение 3.15 [62]. Почти любой линейный двоичный код (за исключением экспоненциальной малой доли кодов) длины скорости может быть продекодирован в двоичном симметричном канале со сложностью

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

Утверждение 3.16 [63]. Существуют ОК-коды порядка удовлетворяющие границе Варшамова — Гилберта, со сложностью декодирования при

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