1.5. ВЕРОЯТНОСТЬ ОШИБКИ

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

Определение. Вероятностью ошибки, или вероятностью ошибки на слово, для данной схемы декодирования называется вероятность появления неправильного кодового слова на выходе декодера.

Если имеется кодовых слов которые, как мы предполагаем, используются с равной вероятностью, то

Если мы декодируем, пользуясь стандартным расположением, то ошибка декодирования происходит тогда и только тогда, когда вектор ошибок не является лидером смежного класса, так что

Предположим, что имеется лидеров смежного класса веса Тогда, используя (1.13), получаем

(Так как стандартное расположение обеспечивает декодирование по максимуму правдоподобия, то любая другая схема декодирования будет иметь вероятность ошибки не меньше чем правая часть

Примеры. Для кода (см. рис. 1.7) имеем так что

Для кода имеем так что

Если код имеет минимальное расстояние или то (по теореме 2) он может исправлять ошибок. Поэтому каждый

вектор ошибок веса не более является лидером смежного класса. Другими словами,

Но для значений вычислить а, чрезвычайно трудно, и они известны только для очень немногих кодов.

Если вероятность ошибки в канале очень мала, то . В этом случае в (1.24) можно пренебречь членами с большими и формулы

или

являются полезными аппроксимациями. В любом случае правые части формул (1 26) или (1.27) являются верхними границами для

Совершенные коды. Конечно, если то формула (1.26) становится точной. Такой код называется совершенным.

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

Квазисовершенные коды. Если же теперь при то становится точной формула (1.27). Такой код называется квазисовершенным.

Таким образом, квазисовершенный код, исправляющий ошибок, может исправлять все ошибки веса не более некоторые ошибки веса и не может исправлять ни одной ошибки веса больше, чем Шары радиуса проведенные вокруг кодовых слов, могут пересекаться, и вместе они содержат все векторы длины Мы снова встретимся с квазисовершенными кодами в гл. 6, 9 и 15.

Граница сферической упаковки, или граница Хэмминга. Предположим, что двоичный код длины содержащий кодовых слов, который может исправлять ошибок. Шары радиуса проведенные вокруг всех кодовых слов, не пересекаются. Каждый из этих шаров содержит векторов (см. упражнение 18 (b)). Но число векторов во всем пространстве равно Поэтому мы получаем следующую теорему.

Теорема 6. (Граница сферической упаковки, или граница Хэмминга). Если существует двоичный код длины

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

Аналогично для кода над полем из элементов

Для больших см. теорему 31 гл. 17. Так как при доказательстве этих двух границ не используется линейность кода, то они также справедливы и для нелинейных кодов (см. гл. 2).

По определению код совершенен тогда и только тогда, когда в (1.28) или (1.29) выполняется равенство.

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

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

Упражнение. (23). Показать, что если при декодировании используется стандартное расположение и все сообщения равновероятны, то с и в не зависит от того, какое кодовое слово было послано. В самом деле, если послано кодовое слово и оно декодировано как то

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

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

Пример. Вернемся к стандартному расположению на рис. 1.7. Здесь если находится в первом столбце таблицы (где расположены лидеры смежных классов), если находится во или столбцах, и если находится в последнем столбце. Тогда из (1.32)

Использование этого очень простого кода понизило среднюю вероятность ошибки на символ от 0,01 до 0,0053.

Упражнения. (24). Показать, что при декодировании кода с помощью стандартного расположения

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

Неполное декодирование. Схему неполного декодирования, которая исправляет ошибки кратности не более чем следующим образом можно описать в терминах стандартного расположения. Расположим смежные классы в порядке увеличения веса (т. е. уменьшения вероятности) их лидеров (рис. 1.8).

Рис. 1.8 Неполное декодирование, использующее стандартное расположение

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

Обнаружение ошибок. При обнаружении ошибок декодер ошибется и допустит кодовое слово, отличное от переданного, тогда и только тогда, когда вектор ошибок является ненулевым кодовым

словом. Если код содержит кодовых слов веса то вероятность ошибки равна:

Вероятность же того, что ошибка будет обнаружена и сообщение будет передано еще раз, равна

Пример. Для кода если

Это значение намного меньше, чем вероятность ошибки 0,00136, полученная при декодировании этого кода с помощью стандартного расположения. Вероятность повторной передачи равна переспроса

Задача (нерешенная). (1.1). Найти распределение лидеров смежных классов для любого из известных семейств кодов. Эта задача все еще не решена даже для кодов Рида — Маллера первого порядка (см. гл. 14, а также работы Берлекэмпа и Велча [133], Лечнера [797—799], Сарвейта [1144] и Слоэна и Дика [1233]).