Глава 16. Нумераторы весов

16.1. Соотношения между нумераторами весов и вероятностью отказа от декодирования

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

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

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

Положим

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

Пусть

Согласно (16.12) и многочлен от х степени Разлагая его по формуле Тейлора, получим, что

Используя (16.11) — (16.15), приходим к следующему выражению для вероятности отказа от декодирования:

Формула (16.16), полученная Мак-Вильямс [1963], определяет вероятность отказа от декодирования в случае, когда число меньше половины минимального расстояния кода. Случай соответствует очень неполному алгоритму декодирования, который декодирует лишь тогда, когда полученное слово является кодовым.

К сожалению, нумератор весов не дает полной информации, которую нам бы хотелось иметь о коде. Например, он ничего не говорит о вероятности ошибки декодирования при использовании полного алгоритма декодирования, преобразующего каждое полученное слово в лидер смежного класса. В частности, суженный двоичный KB-код с длиной -укороченный РМ-код второго порядка с длиной 31 имеют один и тот же нумератор весов, хотя, как показывает задача 15.1, распределения весов лидеров смежных классов у этих кодов различны.

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

Все известные результаты о нумераторах весов относятся к нумераторам весов Хэмминга, причем большинство из них касается двоичных кодов. За исключением нескольких тривиальных теорем типа теоремы 13.52, решительно ничего не известно и о нумераторах весов Ли.

Нумераторы весов Ли некоторых двоичных кодов приведены в табл. 16.1; формулы для нумераторов весов некоторых классов двоичных кодов с малыми и большими скоростями собраны в табл. 16.4 и 16.5.