2.3. Кодирование для исправления ошибок: Основные положения

Все коды, исправляющие ошибки, основаны на одной общей идее: для исправления ошибок, которые могут возникнуть в процессе передачи или хранения информации, к ней добав­ляется некоторая избыточность. По основной схеме (исполь­зуемой на практике), избыточные символы дописываются вслед за информационными, образуя кодовую последователь­ность или кодовое слово {codeword). В качестве иллюстрации на рис. 2.4 показано кодовое слово, сформированное процедурой кодирования блокового кода (blockcode).Такое кодирова­ние называют систематическим (systematic). Это означает, что информационные символы всегда появляются на первых к по­зициях кодового слова. Символы на оставшихся п-к позициях являются различными функциями от информационных сим­волов, обеспечивая тем самым избыточность, необходимую для обнаружения или исправления ошибок. Множество всех кодовых последовательностей называют кодом, исправляющим ошибки (errorcorrectingcode),и обозначают через С.

Рис. 2.4. Систематическое блоковое кодирование для исправления ошибок

2.4. Постановка задачи кодирования

Назначение кодера и декодера канала заключается в обеспечении надежной связи между источником и получателем сообщений и макси­мально возможном уменьшении влияния шумов. Следует упомянуть о некоторых принципиальных возможностях обеспечения высокий надеж­ности передачи. Одна из них связана с передачей в двоичном симме­тричном канале, в котором параметр р — вероятность ошибки не пре­восходит 0,5, двух возможных сообщений — 0 и 1 — с многократным по­вторением каждого и принятием решений по мажоритарному правилу: 0 (1), если в переданной последовательности из n нулей (единиц) более половины оказываются нулями (единицами). В пределе при неогра­ниченном возрастании n вероятность ошибочного декодирования стре­мится к нулю в силу справедливости закона больших чисел. Однако ско­рость передачи информации при таком методе кодирования также стре­мится к нулю, и практической ценности такой метод не представляет.

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

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

Рассмотрим задачу кодирования источника дискретных сообщений А, имеющего энтропию Н(А). Пусть В — множество кодовых блоков, из числа которых выбираются слова, предназначенные для передачи сообщений по каналу связи с помехами; Н(В) — энтропия дискретного ансамбля В. Обозначим через и — ансамбль кодовых слов, появляющихся на выходе канала, и его энтропию. Поскольку при пере­даче сигналов по каналу с помехами существует не нулевая вероятность перехода какой-то части кодовых символов в ложные (с вероятностью р), имеют место следующие неравенства, характеризующие взаимную информацию между этими ансамблями:

(2.1)

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

(2.2)

(2.3)

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

1. Кодом длиной n и объемом М для канала называется множество из М пар , ,где - последовательности длины n, образованные входны­ми сигналами канала и называемые кодовыми словами ( при i ≠ j) и , i = 1,2, ...,М, — решающие области, образованные выходными последовательностями канала, причем при i ≠ j множе­ства и не пересекаются.

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

2. Скоростью кода называется величина

, (2.6)

43

где М — объем и n — длина кодовых слов.

Если бы кодовые слова имели бы одинаковые вероятности появле­ния (например, относились бы к асимптотически равновероятным ти­пичным последовательностям, появляющимся на выходе кодера источ­ника), то величина logM представляла бы максимальное количество информации, которое передавалось бы одним кодовым словом и, сле­довательно, скорость кода представляла бы максимальное количество информации, передаваемое с помощью одного кодового символа. Ско­рость кода измеряется в битах на символ. Число кодовых блоков не может превышать общего числа последовательностей длины п, обра­зованных символами входного алфавита канала. Отсюда следует, что R ≤ logm, где т — мощность алфавита. В двоичном каналеR ≤ 1. Очевидно, что двоичный код длины n, имеющий скоростьR, имеет объем М = 2^nR.

При передаче сообщений по каналу с помехами возможны ошибки декодирования. Обозначим через р,- вероятность ошибочного декоди­рования словаb_i, не оказавшегося в решающей области В_i.

В качестве меры надежности передачи кодовых слов могут быть ис­пользованы либо максимальная вероятность ошибки р_mах = mах{р₁, ...,р_M}. либо средняя вероятность ошибки

Далее сформулируем теоремы Шеннона о кодировании в канале с шумами.

1. Пусть С — пропускная способность дискретного канала без памяти. При любом R< С и любом положительном 6 существует код достаточно большой длины n, максимальная вероятность ошиб­ки которого удовлетворяет неравенствуp_max ≤ δ. (Прямая теорема кодирования).

2. Для всякого R> С найдется положительное число 6 такое, что Pmin ≥ δ для любого n и любого кода. (Обратная теорема кодирования).