Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Обращение теоремы кодирования формулируется и доказывается при различной степени общности в гл. 4, 7 и 8. В не очень строгой формулировке она утверждает, что если энтропия дискретного источника в битах в секунду больше, чем С, то независимо от кодирования и декодирования, использованных при передаче выхода источника по каналу,
25
вероятность ошибки при воспроизведении выхода источника на приемном конце не может быть меньше, чем некоторое положительное число, которое зависит от источника и от С. Так же как показано в гл. 9, если R является минимальным числом двоичных символов в секунду, требуемых для воспроизведения источника с заданным уровнем среднего искажения, и если R^> С, то независимо от кодирования и декодирования выход источника не может быть передан по каналу и воспроизведен с этим заданным уровнем среднего искажения.
Наиболее удивительным и важным среди указанных выше результатов является теорема кодирования для канала с шумами, которую мы обсудим сейчас более детально. Предположим, что требуется передать данные по дискретному каналу и что по каналу передается одна входная буква за каждые тс секунд. Предположим также, что двоичные данные поступают на кодер для канала со скоростью R двоичных символов в секунду. Рассмотрим частный вид кодеров для канала, которые называются блоковыми кодерами; блоковый кодер работает следующим образом. Кодер накапливает двоичные символы на входе кодера в течение некоторого фиксированного интервала Т секунд, где Т является конструктивным параметром кодера. Во время этого интервала TR двоичных символов поступают на кодер (для простоты мы пренебрегаем здесь тем, что TR может не быть целым числом). Кодер можно представить себе как устройство, которое имеет список всех 2TR возможных последовательностей TR двоичных символов и сопоставленного каждой из этих последовательностей кодового слова, состоящего из последовательности N = 77т с букв на входе канала. При получении некоторой отдельной последовательности TR двоичных символов кодер отыскивает эту последовательность в списке и передает по каналу соответствующее кодовое слово из списка. Требуется Т секунд, чтобы передать N •— буквенное кодовое слово по каналу, и за это время другая последовательность TR двоичных символов поступит на кодер и начнется передача следующего кодового слова. Простой пример такого кодера представлен на рис. 1.3.3. В этом примере, когда двоичная последовательность 0011... поступает на кодер, то 00 является входом кодера на первом интервале в Т секунд, и в конце этого интервала формируется кодовое слово ахахах и передается за интервал времени в Т секунд. Аналогично 11 является входом кодера на втором интервале времени в Т секунд, и аха^а3—соответствующим кодовым словом, передаваемым в течение третьего интервала времени.
Декодер для такого блокового кодера работает аналогичным образом. Декодер накапливает N принятых символов, поступающих из канала и соответствующих переданному кодовому слову, и строит решения (возможно неправильные) относительно соответствующих TR двоичных символов, которые поступили на'кодер. Можно считать, что эта процедура решения выполняется декодером с помощью списка всех возможных принимаемых последовательностей из N символов и соответствующей каждой из этих последовательностей последовательности из TR двоичных символов.
Для данного дискретного канала и данной скорости R (в двоичных символах в секунду) поступления символов на кодер имеется свобода
26
в выборе, во-первых, Т (или, что эквивалентно, свободе в выборе N — = Т/тс), во-вторых, множества 2ТН кодовых слов и, в-третьих, правила решения. Вероятность ошибки в декодированных двоичных данных, сложность системы и задержка при декодировании зависят от этих выборов. В гл. 5 будет установлено следующее соотношение между параметром Т и вероятностью Ре ошибочного декодирования блока TR двоичных символов. Будет показано, что для широкого класса каналов можно выбрать 2ТН кодовых слов и правило решения таким образом, что
Ре < ехр [—ТЕ (R)}.
Функция Е (R) является функцией R (числа двоичных символов в секунду, поступающих на кодер) и зависит от модели капала, но не зависит от Т. Показывается, что Е (R) убывает с ростом R, но остается по-
Двоичная последа ва -тельность на входе кодера
00
О/
10
11
Кодовое слово на выходе кодера
а/а, а, aza$af а}а, аг а, а2 а}
Рис. 1.3.3. Пример кодера для дискретного канала, TR=2, N=3.
Рис. 1.3.4. График функции E(R) для типичной модели канала.
ложительной при всех R меньших, чем пропускная способность (рис. 1.3.4). Оказывается, что приведенная выше граница для Ре является довольно точной, и не является нецелесообразным рассмотрение ехр [—ТЕ (/?)] в качестве оценки минимальной вероятности ошибки (по всем выборам 2TR кодовых слов и всем правилам решения), которая может быть достигнута при использовании блокового кодера с заданным временем Т. Таким образом, чтобы сделать Ре малой, необходимо выбрать Т большим, и чем R ближе к С, тем больше должно быть Т.
