ГЛАВА 14. КОМПОЗИЦИЯ И ХАРАКТЕРИСТИКИ КОНТРОЛИРУЮЩИХ ОШИБКИ КОДОВ

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

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

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

14.1. РАСПРЕДЕЛЕНИЯ ВЕСОВ

Мы знаем, что если линейный блоковый код имеет минимальное расстояние , то существует хотя бы одно кодовое слово веса Иногда нас не удовлетворяет столь малая информация; мы хотим знать, сколько кодовых слов имеют вес и каковы веса других кодовых слов. Например, в табл. 5.3 были приведены веса слов двоичного -кода Голея.

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

Пусть число кодовых слов веса I линейного -кода. Распределением весов кода называется -мерный вектор с компонентами Очевидно, что если минимальное расстояние кода равно то равны нулю, отлично от нуля. Более глубокая характеристика кода требует дополнительного анализа.

Аналитическое описание распределения весов кода — трудная задача, но для важного случая кодов Рида —Соломона (или любого кода с максимальным расстоянием) аналитическое решение известно. Настоящий параграф служит введением в эту зздачу. В нем получена формула числа кодовых слов каждого веса для кода с максимальным расстоянием. В случае произвольного линейного кода такую формулу мы дать не сможем, но некоторые общие соображения приведем. Будет выведено тождество Мак-Вильямс, связывающее распределение весов кода с распределением весов дуального кода. Тождество Мак-Вильямс полезно в тех случаях, когда дуальный код достаточно мал, так что его распределение весов можно найти на ЭВМ.

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

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

Доказательство. Код с минимальным расстоянием может восстанавливать любые стертых символов. Так как для кодов с максимальным расстоянием то теорема доказана.

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

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

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

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

Теорема 14.1.2. Распределение весов -кода над с максимальным расстоянием определяется формулами при и

при

Доказательство. При теорема очевидна. Дальнейшее доказательство распадается на три шага.

Шаг 1. Разобьем совокупность целых чисел от 0 до на два непересекающихся подмножества где состоит из I целых чисел, и будем рассматривать лишь те кодовые слова, которые содержат нулевые компоненты в позициях с номерами из и ненулевые компоненты во всех других позициях. Пусть число таких кодовых слов веса Для произвольного кода

поэтому необходимо лишь доказать, что

Чтобы доказать это равенство, установим одно неявное соотношение, связывающее при меньших I, и I, больших

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

В множестве I позиции, принадлежащих можно выбрать любое подмножество V позиций. Число кодовых слов веса V с ненулевыми компонентами в этих позициях равно Следовательно,

Это неявное соотношение рекуррентно связывает и 1 и т. д. Разрешив это рекуррентное соотношение, мы получим явную формулу для

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

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

Дополнительные слагаемые, включенные в эту сумму, соответствуют отрицательным степеням и не вносят вклад в Свернем ее, используя формулу бипома Ныотона:

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

Это и завершает доказательство.

Следствие 14.1.3. Распределение весов -кода над с максимальным расстоянием дается соотношениями при и

при

Доказательство. Воспользуемся тождеством

и перепишем доказываемое равенство в виде

Последнее равенство вытекает из теоремы 14 1.2.

Рис. 14.1. (см. скан) Распределение весов -кода Рида-Соломона.

Следствие 14.1.3 полезно при нахождении распределения весов кодов Рида — Соломона, например распределения весов -кода Рида-Соломона, приведенного на рис. 14.1. Даже для таких кодов Рида-Соломона небольшой мощности число кодовых слов веса I может быть очень большим. Вот почему, вообще говоря, практически невозможно найти распределение весов кода простым перебором кодовых слов.

В случае кодов, не являющихся кодами с максимальным расстоянием, не существует правила, аналогичною теореме 14 1.2.

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

В настоящее время наиболее сильным инструментом являются выражения, устанавливающие связь между распределением весов линейного кода и распределением весов его дуального кода — так называемые тождества Мак-Вильямс. Тождества Мак-Вильямс справедливы для любого линейного кода; они вытекают из векторной структуры линейного кода и из того факта, что дуальный коду код является ортогональным дополнением Прежде чем переходить к выводу тождеств Мак-Вильямс, мы должны вернуться к изучению абстрактных конечномерных векторных пространств, начатому в § 2.6. Необходимо ввести понятия пересечения и прямой суммы двух подпространств и доказать их некоторые свойства.

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

Теорема 14.1.4.

Доказательство. Базис подпространства состоит из VI векторов. Этот базис может быть расширен до базиса добавлением базисных векторов и до базиса V добавлением базисных векторов. Все эти базисные векторы в совокупности образуют базис подпространства Таким образом,

откуда следует теорема.

Теорема 14.1.5.

Доказательство. Подпространство содержится в и поэтому содержится в Аналогично содержится в Следовательно, содержится в другой стороны, запишем элемент из как и обозначим через любой элемент из Тогда и, следовательно, содержится в - Отсюда следует, что эти два множества совпадают.

Пусть представляют собой распределения весов линейного кода и его дуального кода соответственно. Определим нумераторы весов кода равенствами

Следующая теорема связывает эти два многочлена и позволяет вычислить один из них, если известен другой.

Теорема 14.1.6. Нумератор весов линейного -кода над и нумератор весов дуального ему кода связаны соотношением

Доказательство. Рассмотрим код и дувльный ему код Доказательство состоит из двух частей. В первой части мы докажем, что

для . Во второй части мы докажем, что это равенство эквивалентно утверждению теоремы.

Часть Дня заданного разобьем целые числа от 0 до на два непересекающихся подмножества где подмножество состоит из элементов. Пусть V образует -мерное подпространство векторного пространства состоящее из всех векторов с нулевыми компонентами в позициях с номерами из Тогда является -мерным подпространством, состоящим из всех векторов с нулевыми компонентами в позициях номерами из

В силу теоремы 14.1.5

поэтому

С другой стороны, но теореме 14.1.4

Из этих равенств следует, что

Теперь заметим, что при каждом выборе существует векторов в векторов

ассмотрим совокупность всех таких Пересчитаем екторы в каждом которые могут быть получены из некоторого подмножества принадлежащего совокупности Число пересчитанных векторов равно причем многие из них входят в подсчет несколько раз. Диалогично пересчитав все векторы в каждом которое получается из принадлежащего имеем

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

Аналогично можно сосчитать векторы в Тогда предыдущее равенство иереходит в равенство

Так как произвольно, первая часть доказательства завершена.

Часть 2. Исходя из выводов первой части, запишем тождество для многочленов

Переменим порядок суммирования

вспомнив, что если Используя формулу бинома Ныотона, имеем

Наконец, сделав подстановку получим

или

что завершает доказательство теоремы.

В заключение параграфа укажем на простое применение этой теоремы. Из табл. 1.1 следует, что распределение весов -кода Хэмминга равно

так что нумератор весов имеет вид

Соответствующий дуальный код — это двоичный циклический код, известный иод названием симплексного. Корнями его порождающего многочлена

являются Согласно теореме 14.1.6, нумератор весов симплексного кода удовлетворяет равенству

откуда следует, что

Симплексный -код имеет одно кодовое слово веса 0 и семь кодовых слов веса 4.