Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Последнее слагаемое в (4А.22) можно оценить сверху, используя лемму 1:
/(ХхХ2; Ya I Yj, s0) Y^S*. s0) + logi4 =
— ff (Y2 | Yi Sn, So) — H (Y2 [ X2 Sn, Sp) + log Л 'i < H (Y2 I Sn, s0)—И (Y2 I X2 Sn, s0) + log A —
= I s°)1 (Y2’> X2 I s») + log Л < ICi + log A. (4A.26)
Подставляя (4A.24), (4A.25) и (4A.26) в (4A.22), будем иметь NCn< пСп + ICi log А,
или
Г--- log л 1 - log Л ' Г_ log А ]
[с" + Л- j < л Сп + л + 1 Г+ / J
Л’
Из леммы 2 следует, что
im CN= lim
N -* оо
Л’ -> сю
Сд, +
log А
N
= inf N
log А
N
(4А.27)
(4А.28)
(4А.29)
ТЕОРЕМА КОДИРОВАНИЯ ДЛЯ КАНАЛА С ШУМАМИ
5.1. БЛОКОВЫЕ КОДЫ
В предыдущей главе мы показали, что если информация от заданного источника должна быть передана по заданному каналу и если энтропия источника на единицу времени больше, чем пропускная способность канала на единицу времени, то невозможно осуществить сколь угодно надежный прием данных этого источника. В этой главе будет показано, что если энтропия источника меньше, чем пропускная способность, то при определенных условиях можно осуществить сколь угодно надежный прием.
Используемый здесь подход совершенно отличен от того, который был рассмотрен в гл. 4. Там был установлен отрицательный результат: независимо от того, как кодировать и декодировать при скоростях передачи, больших пропускной способности, нельзя избежать некоторой вероятности ошибки. Следовательно, чтобы избежать ошибки, мы должны снизить скорость передачи или улучшить канал. Чтобы доказать это в общем случае, нельзя было накладывать никаких ограничений на кодер и декодер. Для того чтобы показать, что надежная передача возможна при скоростях, меньших пропускной способности, можно уже накладывать какие угодно ограничения на вид кодера и декодера. В действительности такие ограничения часто дают возможность проникнуть в существо методов для достижения надежной передачи.
Первое ограничение, которое будет введено, сводится к тому, что мы разобьем кодер и декодер на кодер и декодер для источника и кодер и декодер для канала (рис. 5.1.1). Кодер для источника преобразует выход источника в поток двоичных символов; кодер для канала— двоичные данные в буквы на входе канала; декодер для канала пытается преобразовать выход канала в первоначальный двоичный поток, а декодер для источника пытается восстановить исходный поток символов источника. Такое разделение имеет очевидные преимущества с практической точки зрения, так как двоичные данные позволяют стандартизировать сочленение источников и каналов. Для теории это разделение имеет даже большую важность, так как оно позволяет отделить задачу передачи в шумах от задачи представления источника. Задача представления источника уже обсуждалась в гл. 3. Поэтому в этой главе (за исключением задач) источник не будет рассматриваться и будет принято предположение, что его выход уже преобразован в двоичные данные.
132
Предположим, что двоичные символы поступают к кодеру для канала со скоростью I двоичный символ за т5 сек и что канал является дискретным во времени и передает один символ за тс сек. В этой главе ограничим наше рассмотрение лишь блоковыми кодерами. Эти кодеры, которые делят поступающий поток двоичных данных на последовательности равной длины, скажем длины L двоичных символов. Имеются М — 2L различных двоичных последовательностей длины L и кодер сопоставляет кодовое слово для каждой из них. Каждое кодовое слово представляет собой последовательность фиксированной длины N букв на входе канала. Число N называется длиной блокового кода, и оно будет равно наибольшему целому числу, меньшему Lrs!xc\
N=\_L%Jx~\ (5.1.1)
Если Lts/tc является целым числом, то время, необходимое для того, чтобы L двоичных символов поступили в кодер, равно времени, тре-
Рис. 5.1.1.
буемому для передачи кодового слова из N символов канала. Если Lts/tc не является целым числом, то иногда нужно будет передавать по каналу «глухой символ», чтобы синхронизировать друг с другом поток двоичных данных и последовательность, передаваемую по каналу. Приемник принимает непрерывный поток символов на выходе канала. Они разделяются на последовательности длины N, соответствующие переданным последовательностям длины N. Декодер делает попытку угадать на основе принятой последовательности длины N, какая из соответствующих последовательностей L двоичных символов имела место. На практике, конечно, может возникать задача синхронизации приемника и передатчика, т. е. задача определения начала блока из N символов. Эта задача не будет здесь рассматриваться, так как ее рассмотрение здесь просто бы затемнило построение кодирования, противостоящего действию шума в канале.
Обозначим М = 2L — число кодовых слов, соответствующих 2L двоичным последовательностям источника, через х1=(дс1)1,
