Cтраница 1
Теорема кодирования для источника ( теорема 3.1.1) была получена Шенноном ( 1948), который развил большинство концепций этой главы. Шеннон также установил теорему для случая, когда буквы источника имеют неравные длительности и когда источник является марковским. Кодирование для источника, обладающее свойством синхронизации, было изучено Голомбом, Гордоном и Велчем ( 1958), Кендаллом и Ридом ( 1962), Истманом ( 1965), Шоль-цем ( 1966) и другими. [1]
Теорема кодирования для канала с шумами принадлежит Шеннону ( 1948) и, несомненно, является самым значительным результатом в теории информации. Впервые Файнстейн ( 1955) показал, что Ре стремится к нулю экспоненциально по N при фиксированной скорости R С. Граница случайного кодирования, граница сферической упаковки и тот факт, что они экспоненциально совпадают при скоростях, близких к пропускной способности, были впервые получены Элайсом ( 1955) в частных случаях двоичного симметричного канала и двоичного канала со стиранием. Фано ( 1961) использовал методы случайного кодирования, развитые Шенноном, и производящих функций моментов, для получения показателя экспоненты случайного кодирования Ет ( R) и для эвристического вывода границы сферической упаковки для общего дискретного канала без памяти. Единственная граница сферической упаковки, которая пока что получена, для каналов с конечным числом состояний, принадлежит Кеннеди ( 1963) и относится к одному классу двоичных каналов. [2]
Теорема кодирования для непрерывных по амплитуде источников также вполне аналогична соответствующей теореме для дискретных источников. UV) опять рассматривается ансамбль независимо выбранных кодовых слов, каждая буква в котором выбирается в соответствии с вероятностной мерой на V. Лемма 9.3.1 применима здесь без изменений. Если источник и тест-канал описываются совместной плотностью вероятности, то доказательство леммы может быть модифицировано просто заменой всех сумм интегралами и всех вероятностей плотностями. [3]
Теорема кодирования для дискретных постоянных источников при заданном критерии качества была доказана К. [4]
Обращение теоремы кодирования формулируется и доказывается при различной степени общности в гл. [5]
Обращение теоремы кодирования применимо здесь, так же как и для дискретных каналов. Точнее, имеет место следующая теорема. Ее доказательство опускается, так как оно, в сущности, повторяет доказательства, приведенные в гл. [6]
Обращение теоремы кодирования для источника, данное в теореме 9.2.2, применимо без изменения для источников и мер искажения, рассмотренных здесь. Однако сама теорема кодирования требует некоторых дополнительных рассмотрений. Сначала установим вспомогательный результат, который полезен сам по себе. [7]
Обращение теоремы кодирования получается теперь точно таким же образом, как это было для каналов без обратной связи. [8]
Докажем теперь позитивную теорему кодирования, соответствующую негативным утверждениям теоремы 1, а именно докажем, что возможно приблизиться к нижней границе искажений при заданном отношении числа п букв сигнала к t буквам сообщения. [9]
При доказательстве теоремы кодирования, не зависящей от начального состояния, возникает задача, которая формально совпадает с аналогичной задачей для составного канала. Составным каналом называется канал, который описывается множеством различных переходных распределений вероятностей Р ( у х), где частное значение i неизвестно передатчику и приемнику. Развитый здесь подход ( который применим только, когда А конечно) для простоты использует предположение, что начальные состояния имеют равные вероятности. [10]
При доказательстве теоремы кодирования для кодов с проверкой на четность удобно ввести в рассмотрение несколько более широкий класс кодов, которые по причинам, объясняемым в следующем параграфе, назовем смежными кодами. [11]
Устанавливая справедливость теоремы кодирования и ее обращения при большой степени общности, представленные выше результаты Дают слабое указание на то, как вычислять ET ( R) или С. [12]
Следующее доказательство теоремы кодирования не позволяет получить точную границу вероятности ошибки, найденной в § 5.6, но выявляет с большей ясностью значение пропускной способности канала. [13]
Намеченное доказательство теоремы кодирования для канала с шумом является неудовлетворительным с практической, иЬи конструктивной, точки зрения. Используемые в нем блоковые коды трудно строить и, как правило, трудно исследовать. [14]
Обратная часть теоремы кодирования доказывается по существу точно так же, как и в случае конечного алфавита. Предполагается только, что допустимым кодирующим функциям, отображающим сообщения на входные сигналы, соответствуют измеримые подмножества пространства сообщений. Если не сделать этого предположения, то вообще невозможно даже определить понятие среднее искажение. Замена в соответствующих неравенствах сумм, определенных в пространстве А на интегралы, приводит к доказательству соответствующей обратной теоремы. [15]