Cтраница 3
Заметим, что это последнее равенство включает положительное утверждение теоремы кодирования гл. [31]
Важность понятия пропускной способности канала основана прежде всего на теореме кодирования для канала с шумами и ее обращении. Грубо говоря, эта теорема кодирования, справедливая для широкого класса каналов, утверждает, что если пропускная способность канала равна С бит в секунду и если двоичные данные поступают на вход кодера этого канала ( см. рис. 1.1.2) со скоростью ( в двоичных символах в секунду) R С, то с помощью соответствующим образом построенных кодера и декодера можно воспроизводить двоичные символы на выходе декодера со сколь угодно малой вероятностью ошибки. Этот результат точно сформулирован и доказан в гл. Далеко идущее значение этой теоремы будет обсуждаться ниже в этом параграфе, однако до гл. Если объединить этот результат с теоремой кодирования для источников, которая была указана в предыдущем параграфе, то найдем, что если дискретный источник имеет энтропию ( в битах в секунду) меньшую, чем С, то выход источника может быть воспроизведен на приемном конце с произвольно малой вероятностью ошибки с помощью использования соответствующего кодирования и декодирования. Аналогично для недискретного источника, если R является минимальным числом двоичных символов в секунду, требующихся, чтобы воспроизвести выход источника с данным уровнем среднего искажения, и если R С, то выход источника может быть передан по каналу и воспроизведен с этим уровнем искажения. [32]
Значение энтропии буквы источника определяется, главным образом, теоремой кодирования для источника, которая рассматривается в гл. Она утверждает, что если Я - энтропия буквы источника в дискретном источнике без памяти, то последовательность на выходе источника не может быть представлена двоичной последовательностью, использующей в среднем меньше чем Я двоичных символов на букву источника, но она может быть представлена двоичной последовательностью, использующей в среднем сколь угодно близкое к Я число двоичных символов на букву источника. Некоторое ощущение справедливости этого результата может быть получено, если заметить, что в случае, когда для некоторого целого L источник имеет алфавит из 2L равновероятных букв, то энтропия буквы источника равна L бит. Вместе с тем, если заметить, что всего имеется 2L различных последовательностей из L двоичных символов, то можно понять, что каждая из этих последовательностей может быть сопоставлена различным буквам алфавита источника, представляя, таким образом, выход источника с помощью L двоичных символов на букву источника. [33]
В настоящей главе доказывается очень частный случай основной теоремы: теорема кодирования без шума, когда проблемы, связанные с шумом, игнорируются. После того, как эта теорема к ее доказательство станут понятными, более ясным станет и доказательство основной теоремы; в этих щелях нужно лишь использовать ряд предварительных результатов из гл. [34]
В первой главе вводятся основные понятия теории информации и доказываются теоремы кодирования. Во второй главе веденные понятия применяются для распознавания образов. Приводятся алгоритмы вычисления информативности признака и кластерного анализа в пространстве признаков. Третья глава посвящена реляционным базам данных. Основное внимание уделяется синтезу баз данных на основе декомпозиции. В четвертой главе анализируется связь между словами и графами. Рассматриваются основные алгоритмы на графах, которые находят применение при сжатии информации, распознавании образов и синтезе баз данных. [35]
Добрушиным ( 1959) был предложен общий подход к доказательству теоремы кодирования для источников с заданным уровнем верности. По существу, при таком подходе для доказательства теоремы кодирования достаточно установить информационную устойчивость источника. [36]
VE) с точностью воспроизведения WfE - Эта формулировка прямого утверждения теоремы кодирования является одной из наиболее общих. Информационная устойчивость последовательности сообщений и каналов всегда имеет место в большом числе практически интересных частных случаев. [37]
Исторически, этот результат принадлежащий Вольфовицу, был назван сильным обращением теоремы кодирования, а результат теоремы 4.3.1, принадлежащий Фано - слабым обращением теоремы кодирования. Так как результат, полученный Вольфовицем, не следует из теоремы 4.3.4, которую мы назвали обращением теоремы кодирования, то мы будем называть результаты, изложенные здесь, теоремой обращения по Вольфовицу или обращением теоремы кодирования для блокового кодирования. [38]
Кроме того, техника оценки вероятностей без объединения типов больше подходит для получения универсальных теорем кодирования. Интуитивно ясно, что универсальность кодирования означает, что коды должны быть построены совершенно независимо от распределений вероятностей, управляющих системой, поэтому возможности кода оцениваются посредством целого спектра его характеристик для различных возможных распределений. Теорема 2.15 является первой универсальной теоремой кодирования в этой книге. Очевидно, что два кода не обязательно сравнимы с точки зрения универсального кодирования. Поэтому в некоторой степени неожиданно, что для класса ДИБП с фиксированным алфавитом X существуют коды, универсально оптимальные в том смысле, что для любого ДИБП эти коды обладают асимптотически той же самой вероятностью ошибки, что и код, являющийся наилучшим для этого конкретного ДИБП. [39]
Вернемся теперь к проблеме надежной передачи ДИБП по ДКБП, иллюстрируемой рис. 2.1. Комбинируя теоремы кодирования для источника и канала, полученные до сих пор, мы можем дать ответ на проблему ПМСП, поставленную на интуитивном уровне во введении. А именно, совмещая коды для источника и канала, мы покажем, что ПМСП равна отношению скорости при уровне искажения Д и пропускной способности канала. [40]
В соединении с теоремой 9.2.2 результат (9.5.8) эквивалентен для дискретных источников без памяти обращению теоремы кодирования для. Для того чтобы достигнуть вероятность ошибки на символ источника, равную d, канал должен иметь пропускную способность, по крайней мере, равную правой части (9.5.8), или, что эквивалентно, для канала такой пропускной способности, d - нижняя граница вероятности ошибки на символ. [41]
Доказанная теорема играет основную роль в теории много-терминальных систем без памяти, особенно при доказательстве теорем кодирования для сетей, в которые входит несколько источников информации. [42]
В частном случае канала без шума с D буквами во входном и выходном алфавитах условие (4.3.22) является просто обращением теоремы кодирования для источника. Оно отличается от (3.1.20) тем, что ограничивает снизу вероятность ошибки на символ, а не вероятность ошибки в блоке. [43]
Таким образом, мы описали простой алгоритм генерирования кодовых слов, при помощи которого можно достаточно хорошо приблизиться к границам, задаваемым теоремой кодирования. К сожалению, проблема нахождения алгоритмов декодирования является не такой простой. [44]
RH & ( U), то при любом кодировании объема М отрезка сообщения длины L среднее искажение рд удовлетворяет неравенству р.е. Эта теорема кодирования обобщается и на более общий класс И. [45]