Глава 2. БЛОКОВЫЕ КОДЫ

1. Передача информации при помощи блоковых кодов

Значительное продвижение в решении задачи безошибочной передачи информации было связано с результатами о блоковых кодах, полученными независимо Шенноном (не опубликовано) и Элайесом [21]. Для удобства изложения мы приведем в этой главе те из их результатов, которые существенны для дальнейшего.

При блоковом кодировании для ДСК передающее и приемное устройства задают кодовую книгу, или упорядоченный перечень всех доступных для передачи сооб щений Для двоичного симметричного канала — это двоичные последовательности из символов:

где все компоненты последовательности суть 0 или 1.

Каждой годной для передачи последовательности - соответствует некоторое двоичное число обозначающее положение в упорядоченном перечне 5. Если в содержится всего

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

Существенный параметр есть скорость передачи информации, отнесенная к одному символу, которая определена равенством (1.3). Пример блокового кода приведен на рис. 4.

Рис. 4. Пример кодовой книги где подлежащие передаче сообщения, а числа, задающие положения

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

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

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

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

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

Если то символ последовательности передан

неверно; тогда полученную последовательность у можно представить в виде

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

Таким образом,

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

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

1. Складывает по модулю 2 последовательность у с каждой из последовательностей из порождая, таким образом, совокупность "шумовых" последовательностей

2. Считает число символов, равных 1, в каждой из последовательностей

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

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

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

Тот факт, что описанное выше правило декодирования совпадает с алгоритмом декодирования по методу максимума правдоподобия, следует просто из закона Байеса:

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

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

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