6.2. ТЕОРЕМА КОДИРОВАНИЯ ДЛЯ КОДОВ С ПРОВЕРКОЙ НА ЧЕТНОСТЬ

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

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

Теорема 6.2.1. Рассмотрим ансамбль смежных -кодов, в котором все символы выбираются случайно и независимо равными 0 или 1, причем вероятности этих значений одинаковы. Средняя по этому ансамблю кодов вероятность ошибки для каждого из сообщений при передаче их по ДСК и декодированию по максимуму правдоподобия ограничена неравенством

где выражается через переходную вероятность канала соотношениями (5.6.41) и (5.6.45) и

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

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

при котором принимает любое фиксированное значение. Поскольку существует способов выбора то

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

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

Теперь заметим, что в теореме 5.6.1 предполагалось, что кодовые слова выбирались независимо. Вместе с тем, если внимательно просмотреть доказательство, то можно установить, что в нем использовалась лишь попарная независимость. Таким образом, теорема 5.6.1 применима и к нашему ансамблю. Следовательно, также применима и теорема 5.6.2, из которой непосредственно вытекают выражения для ДСК, приведенные в (5.6.41) и (5.6.45).

Как и в § 5.6, этот результат доказывает существование смежного -кода со средней вероятностью ошибки, по большей мере равной и в силу сделанного замечания, соответствующий код с проверкой на четность, получающийся после устранения фиксированной последовательности обладает той же самой вероятностью ошибки. Так как множество правильно декодируемых шумовых последовательностей не зависит от сообщения, то точно так же для всех сообщений, закодированных этим кодом. Наконец, как было доказано в § 6.1, матрица может быть преобразована в систематическую порождающую матрицу с помощью элементарных операций над строками и, быть может, перестановки некоторых столбцов. Это доказывает следующее следствие.

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

где определяется равенствами (5.6.41) и (5.6.45).

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

Рис. 6.2.1. Отображение двоичных последовательностей во входные буквы канала.

Первой нашей задачей будет построение смежного кода с длиной блока путем использования правила кодирования (6.2.1), где -двоичная матрица размера на двоичная последовательность длины Можно рассматривать двоичные кодовые, слова как последовательности N троек двоичных символов. Затем эти/гронки двоичных символов кодируются во входные буквы канала по правилу, представленному на рис. 6.2.1. Это отображает каждое кодовое слово, представляющее собой последовательность двоичных символов, в кодовое слово канала, представляющее собой последовательность N символов канала.

Для ансамбля кодов, рассмотренных в теореме 6.2.1, каждое кодовое слово является последовательностью независимых равновероятных двоичных символов. Поэтому каждое кодовое слово канала представляет собой последовательность N троичных независимых символов с вероятностями Более того, кодовые слова попарно статистически независимы и поэтому снова можно применять теоремы 5.6.1 и 5.6.2. В результате получаем, что существует код рассматриваемого типа, для которого

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

Тогда для любого двоичных последовательностей длины отображаются во входной символ канала аналогично тому, как на рис. 6.2.1. Как велико должно быть в соотношении (6.2.6), аппроксимирующем зависит от и от того, как близко нужно приблизиться к показателю экспоненты При любых заданных длине сообщения и длине кодового слова в канале N нужно использовать рассмотренный в теореме 6.2.1 ансамбль двоичных кодов с длиной двоичного блока После отображения при помощи описанного выше преобразования двоичных кодовых слов в кодовые слова канала длины N и после использования теоремы 5.6.2 получаем, что существует код, для которого

где определяется соотношением

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