7.4. Коды с проверкой на четность

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

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

Коды с проверкой на четность лучше всего определяются в терминах суммирования двоичных символов по модулю 2. Пусть двоичные символы. Их сумма по модулю 2 есть, по определению,

Легко проверить, что сумма по модулю 2 обладает ассоциативным свойством

и, вместе с обычным умножением, дистрибутивным свойством

где с — третий двоичный символ. Кроме того, из соотношения (7.93) следует, что если

то

Другими словами, вычитание по модулю 2 тождественно сложению по модулю 2.

Пусть последовательность из двоичных символов. Назовем весом этой последовательности число символов в ней, равных 1. Из соотношения (7.93) следует, что сумма по модулю символов последовательности равна

Другими словами, сумма по модулю 2 указывает, четен или нечетен вес последовательности.

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

так что число различных сообщений равно

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

образованная следующим образом. Первые символов из и совпадают с символами, составляющими сообщение

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

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

Из выражений (7.102) и (7.103) мы имеем

Это подсказывает следующее определение: при

так что полная матрица коэффициентов принимает вид

Другими словами, первые столбцов матрицы состоят из произвольных двоичных символов, в то время как остальные столбцов образуют единичную матрицу. Тогда выражение (7.104) можно переписать в виде

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

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

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

— выходная последовательность; определим новую последовательность

где

Последовательность известна как проверочная последовательность, соответствующая выходной последовательности Сложение по модулю 2 соотношения (7.107) и (7.110) дает

С другой стороны, мы видим, что

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

представляет собой шум в канале; ее вес есть число входных символов, которые были искажены шумом. Наконец, подстановка вместо в (7.111) дает

Символы проверочной последовательности могут быть найдены в соответствии с равенством (7.110) по сигналу на выходе канала. Символы шумовой последовательности должны удовлетворять системе линейных уравнений (7.114). Так

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

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

Эта операция декодирования приводит к ошибке всякий раз, когда существует шумовая последовательность, удовлетворяющая соотношению (7.114) с весом, меньшим чем вес фактически появившейся шумовой последовательности. Согласно соотношению (7.114), символы проверочной последовательности определяются элементами матрицы и фактически появляющейся шумовой последовательностью. Следовательно, вероятность ошибки не зависит от переданного сообщения. Это — важное свойство кодов с проверкой на четность.

Другое важное свойство кодов с проверкой на четность состоит в том, что при поэлементном сложении по модулю 2 множество входных последовательностей, представляющих сообщения образуют группу. Изложение групповых свойств кодов с проверкой на четность, соответствующее современному уровню исследований, дано в работе [3].

Из выражения (7.106) видно, что коды с проверкой на четность однозначно определяются двоичными символами, а именно элементами первых столбцов матрицы Конечно, эти символы должны храниться в памяти кодера и декодера. Ниже мы опишем коды с проверкой на четность, которые однозначно определяются двоичными символами, и вычислим верхнюю границу их средней вероятности ошибки, когда двоичных символов выбирается случайно и независимо. Этот специальный класс кодов с проверкой на четность будем называть сверточными кодами.

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

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

Для сверточного кода соотношение (7.103) принимает вид

Из выражения (7.118) видно, что для сверточного кода последние символов входной последовательности получаются сверкой сообщения [см. выражение (7.99)] с последовательностью

Рис. 7.5. Сверточный кодер.

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

На вход кодера поступает последовательность двоичных символов, в которой группа из символов сообщения чередуется с группой нулей. Основная часть кодера состоит из регистра сдвига (двоичной линии задержки) с разрядами. Выход разряда соединяется с сумматором по модулю 2 тогда и только тогда, когда На рис. 7.5 Переключатель соединяет сумматор по модулю 2 с выходом, когда в регистре сдвига содержатся все символы некоторого сообщения, а в противном случае соединяет вход непосредственно с выходом. Очевидно, что кодер на рис. 7.5 последовательно порождает символы определенные соотношениями (7.102) и (7.118).

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

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

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

где

произвольное целое число, изменяющееся в пределах

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

Если удовлетворяют соотношению (7.114), то соответствующие пары С, и С, символов должны удовлетворять соотношению

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

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

Независимо от значений, принимаемых слагаемыми в левой части выражения (7.122) для вероятность в ансамбле сверточных кодов того, что условие (7.122) удовлетворяется для любого фиксированного целого равна Действительно, из выражения (7.116) мы имеем

и, по предположению,

Кроме того, как показано ниже, вероятность того, что условие (7.122) удовлетворяется для какого-либо частного не зависит от того, удовлетворяется ли это условие для любого В самом деле, из выражения (7.116) следует, что для любого символ может быть тождествен символу только для Тогда в силу соотношения (7.123) любой символ в выражении умножается на 0, а потому его фактическое значение несущественно. Статистически независимость, отмеченная выше, обеспечивается предположением о статистической независимости символов Отсюда мы можем заключить, что вероятность того, что соотношение (7.122) одновременно удовлетворяется для всех значений и равна

Пусть вес фактически появившейся шумовой последовательности Обозначим через число последовательностей из цифр с весом, не превышающим [См. равенство (7.121).] В соответствии с вышеприведенными соображениями вероятность того, что какая-либо из этих последовательностей вместе с последовательностью будет удовлетворять условию (7.122) равна 0 или С другой стороны, вероятность того, что в действительности наступит одно или более из различных событий не может превысить суммы вероятностей этих событий. Следовательно, вероятность того, что существует

последовательность удовлетворяющая выражению (7.122), веса, не большего удовлетворяет неравенству

Правая часть неравенства (7.126) возрастает с и в конце концов становится больше 1. Поэтому, так как является вероятностью, то удобнее верхнюю границу представить в виде

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

совпадающую с выражением (7.119). Ч. Т. Д.

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

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

где задаются как функции формулами (7.73) и (7.74). Другими словами, верхняя граница средней вероятности ошибки для сверточных кодов совпадает с верхней границей средней вероятности ошибки для более общего ансамбля двоичных кодов, рассмотренного в предыдущем разделе. Этот результат весьма важен, поскольку позволяет рассчитывать на то, что случайно выбранный сверточный код даст примерно ту же вероятность ошибки, что и код, построенный независимой случайной выборкой символов входных последовательностей, приписываемых сообщениям. Следовательно, при использовании

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

Следствие. Рассмотрим ансамбль кодов с проверкой на четность, полученных случайной независимой выборкой символов в первых столбцах матрицы, определенной условием При декодировании по методу максимума правдоподобия средняя вероятность ошибки удовлетворяет неравенству (7.119) предыдущей теоремы.

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