Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
*> См. любой учебник по математическому анализу, например, Бьюк (1956) (см. также Фихтенгольц Г. М. Курс математического анализа, т. 1. «Наука», 1964). Причина возникновения вопроса о существовании максимума может быть объяснена попыткой максимизировать функцию хг на открытом интервале 0 < < х < 2. Эта функция не имеет максимума, так как она принимает значения, сколь угодно близкие к 4, но никогда не достигает 4.
91
меньшей пропускной способности. Заметим, что поразительным в теореме кодирования является слово «надежно». То, что информация может быть передана со скоростью, равной пропускной способности, является очевидным, так как для этого нужно лишь просто выбрать соответствующее распределение на входе. Теорема кодирования будет рассмотрена в следующей главе. Здесь мы покажем, что пропускная способность может быть интерпретирована как максимальная средняя взаимная информация на букву, которая может быть передана для последовательности входов и выходов. Далее будет доказано обращение теоремы кодирования, т. е. что надежная передача невозможна для скоростей источника, превосходящих пропускную способность канала.
Теорема 4.2.1. Пусть QN (х) — некоторое произвольное совместное распределение вероятностей, заданное на последовательностях N символов на входе ДКБП. Пусть и 4N являются ансамблями входных и выходных последовательностей и пусть Хъ ..., Хк, Уь ..., Yn обозначают ансамбли, соответствующие отдельным буквам. Тогда
7(Х"; Y")< 2 /(*„; Yn), (4.2.4)
п= 1
I(XN; YN)^NC. (4.2.5)
Равенство в (4.2.4) имеет место, если входы статистически независимы, а равенство в (4.2.5) имеет место, если входы независимы и имеют распределение вероятностей, определенное (4.2.3).
Доказательство.
1(XN; \N) = H(\N) — H(4N \XN), (4.2.6)
Я (Y" | X") = 2 Qn (x) Pn (y | x) log —4— • (4.2.7)
х,У ^(ylX)
Так как канал является каналом без памяти, то можно использовать
(4.2.1), что дает
tf(Y"|X")= 2<Ых)РИу|х) ? log---1 - (4.2.8)
х,у п=1 Р(Уп\хп)
Величина log [1 IP (уп\хп)] является случайной величиной и правая часть (4.2.8) равна среднему значению суммы N случайных величин. Она равна сумме средних значений, независимо от того, являются ли входы статистически независимыми или нет. Но среднее значение log [1 /Р (уп\хп)] равно Н (Yn\Xn), так что
tf(Y"|X")= 2 H(Yn\Xn). (4.2.9)
П= 1
92
Это означает, что одно из выражений в (4.2.6) равно сумме энтропий; займемся теперь другим выражением Н (Y'v). Из (2.3.10) имеем
Л'
H(\N)^ 2 H(Yn). (4.2.10)
П= 1
Подставляя (4.2.9) и (4.2.10) в (4.2.6), получаем
/(X"; Y")<2 \H(Yn)-H(Yn\Xr)], (4.2.11)
л = 1
откуда следует (4.2.4).
Равенства в (4.2.10) и, следовательно, в (4.2.4) имеют место тогда
и только тогда, когда выходные буквы статистически независимы.
Если входные буквы статистически независимы, т. е.
Qn (х) = П Qxn (хп),
то совместная вероятность равна
(хп)Р(Уп\хп)
П
и отсюда следует статистическая независимость выходов.
Определение С означает, что / (Хп; Yn) С при всех п и, таким образом, (4.2.5) следует из (4.2.4). Более того, если входы статистически независимы и выбираются так, чтобы максимизировать каждую информацию / (Хп\ Yn), то / (Хп\ Yn) = С при всех п и (4.2.5) удовлетворяется с равенством. |
Из этой теоремы не нужно делать вывода о том, что следует избегать статистическую зависимость между входными буквами. В действительности все рассматриваемые ниже методы кодирования описывают способы введения статистической зависимости между входными буквами, и некоторые из таких зависимостей необходимы в общем случае для того, чтобы получить надежную передачу.
4.3. ОБРАЩЕНИЕ ТЕОРЕМЫ КОДИРОВАНИЯ
До сих пор источники и каналы обсуждались в терминах понятий различных энтропий и средних взаимных информаций. Однако в большинстве систем передачи данных взаимная информация представляет меньший интерес, чем вероятность того, что буквы источника неправильно воспроизводятся у адресата. Эта вероятность ошибки определяет содержание основной теоремы теории информации — теоремы кодирования. Для широкого класса источников и каналов эта теорема утверждает, что если энтропия источника на единицу времени меньше, чем пропускная способность канала на единицу времени, то вероятность ошибки может быть сделана сколь угодно малой с помощью использования достаточно сложных кодера и декодера. В этом параграфе нас будет интересовать обращение этого результата: если энтропия источника больше, чем пропускная способность, то нельзя достичь произвольно малой вероятности ошибки.
