Прямая теорема шеннона для источника общего вида. «Теория информации и кодирования. Теоремы шеннона о кодировании для канала передачи информации

Программа курса

«Теория информации и кодирования»

Лекции читаются на 4-м курсе, VII-семестр,

51 час, лектор доцент

Понятие информации, энтропии. Системы связи. Дискретные источники. Описание источника при помощи случайного процесса. Статистическая независимость. Марковские источники. Эргодичность. Эргодичность бернуллиевского источника.

Вывод формулы энтропии (по Фадееву). Взаимная информация, и её свойства. Свойства энтропии. Теорема о максимальном значении энтропии. Энтропия в единицу времени источника сообщений.

Задача кодирования дискретного источника кодами равной длины. Скорость кодирования. Высоковероятностные множества. Прямая и обратная теоремы кодирования дискретного источника кодами равной длины.

Задача кодирования источника кодами неравной длины. Стоимость кодирования. Однозначно дешифрируемые коды. Префиксные коды. Побуквенное кодирование. Необходимое и достаточное условие однозначной дешифрируемости кода. Полные коды. Теорема кодирования дискретного источника кодами неравной длины. Алгоритмы построения оптимальных кодов (Фано, Шеннона, Хаффмена). Построение бинарного оптимального кода при равновероятностном распределении входных вероятностей. Приложение результатов теории информации при доказательстве нижних и верхних оценок сложности реализации булевых функций в некоторых классах управляющих систем. Метод построения оптимального кода при условии, что неизвестно распределение вероятностей букв источника. Теорема Маркова об однозначной дешифрируемости кода. Адаптивные алгоритмы сжатия информации.

Дискретный канал без памяти. Двоичный симметричный канал. Скорость передачи информации в канале. Пропускная способность канала. Расширенный канал и его пропускная способность. Решающие схемы и группировки наблюдений. Вероятность ошибочной передачи информации. Неравенство Файнстейна. Прямая теорема кодирования канала без памяти. Неравенство Фано. Теорема обработки информации . Обращение теоремы кодирования.

Теория помехоустойчивого кодирования. Критерий максимального правдоподобия. Кодовое расстояние. Коды с проверкой на четность. Порождающая и проверочные матрицы. Синдром. Алгоритм декодирования для кодов с проверкой на четность. Линейные коды и алгоритм их декодирования. Граница Хэмминга. Код Хэмминга. Циклические коды. Кодирования и декодирование циклических кодов.

ЛИТЕРАТУРА

1. Галлагер Р. Теория информации и надежная связь., М., Сов. Радио, 1979.

2. Кричевский Е. Лекции по теории и информации, Новосибирск, НГУ, 1966.

3. Колесник В., Полтырев Г. Курс теории информации, Наука, 1982.

4. Файнстейн А. Основы теории информации, М., ИЛ, 1960.

5. Питерсон В., Уэлдон Ф. Коды, исправляющие ошибки, М., Мир, 1976.

6. Бэрлекамп Алгебраическая теория кодирования, М., Мир, 1971.

При любой производительности источника сообще­ний Н, меньшей, чем пропускная способность канала С, суще­ствует такой способ кодирования, который позволяет обеспечить передачу всей информации, создаваемой источ­ником сообщений, со сколь угодно малой вероятностью ошибки.

Хотя доказательство этой теоремы, предложенной Шен­ноном, в дальнейшем подвергалось более глубокому и строгому математическому представлению, идея его осталась неизменной. Доказывается только существование искомого способа кодирования, для чего находят среднюю вероятность ошибки по всем возможным способам коди­рования и показывают, что она может быть сделана меньше сколь угодно малой величины e. При этом существует хотя бы один способ кодирования, для которого вероятность ошибки меньше средней.

Доказательство теоремы. Пусть H(x) и H(x| y) – априорная и апостериорная энтропии на символ (со стороны приемного конца) для системы, реализующей пропускную способность С канала. В силу свойства Е при достаточно большой длительности (п символов) передачи все возможные любого ансамбля распадаются на высоковероятную и маловероятную группы; при этом о количестве сигналов в соответствующих группах можно сделать следующие утверждения:

а) Группа высоковероятных передаваемых сигналов содержит около 2 пН(х) последовательностей.

б) Группа высоковероятных принимаемых сигналов содержит около 2 пН(у) последовательностей.

в) Каждый высоковероятный принимаемый сигнал мог (с приблизительно одинаковыми вероятностями) произойти от примерно 2 пН(х | у) передаваемых сигналов высоковероятной группы.

г) Каждому отправляемому сигналу из высоковероятной группы может (с приблизительно одинаковыми вероятностями) соответствовать примерно 2 пН(у | х) принимаемых высоковероятных сигналов.

В силу свойства Е энтропии дискретных процессов, при увеличении п все соответствующие e и d будут стремиться к нулю.

Пусть теперь по тому же каналу передается информация со скоростью на входе, равной Н < С. При этом число высоковероятных отправляемых сигналов длиной в п символов будет равно 2 пН < 2 пН(х) . Как уже отмечалось, проблема выбора определенного кода состоит в указании того, какие именно из 2 пН(х) возможных последовательностей выбираются в качестве 2 пН разрешенных к отправке, и как разбиваются на 2 пН подгрупп 2 пН(у) выходных последовательностей. Рассмотрим класс всевозможных кодов, которые получатся, если 2 пН разрешенных последовательностей размещать случайным образом среди 2 пН(х) возможных сигналов высоковероятной группы; найдем среднее значение вероятности ошибки для этих кодов.

Пусть принят некоторый сигнал у к. Вероятность ошибки при этом равна вероятности того, что данный сигнал может происходить более чем от одного из 2 пН разрешенных сигналов. Поскольку код получается случайным (равновероятным) выбором 2 пН последовательностей из 2 пН(х) , то вероятность того, что заданный сигнал на входе канала попадет в число разрешенных, равна

Принятому сигналу у к соответствует 2 пН(х | у) возможно отправленных сигналов. Отсюда средняя вероятность того, что ни один из 2 пН(х | у) сигналов (кроме одного действительно отправленного) не является разрешенным, равна (пренебрегаем единицей по сравнению с пН(х| у))

Это есть средняя вероятность безошибочного приема. Далее, так как Н < С = Н(х) – Н(х| у), то

Н – Н(х) = - Н(х| у) - h, (8.23)

Где h > 0. Подставляя (8.23) в (8.22), получаем

Можно показать , что

т.е. что при случайном кодировании достаточно длинными блоками средняя вероятность ошибки может быть сделана сколь угодно малой. Утверждение о существовании по крайней мере одного кода, дающего вероятность ошибки меньше средней, завершает доказательство.

Отметим, что равенство (8.25) справедливо при любом, сколь угодно малом положительном h. Это означает, что теорема допускает условие Н £ С.

Это и придает особый смысл понятию пропускной способности: пропускная способность оказывается не просто максимально возможной скоростью передачи информации, но максимальной скоростью, при которой еще возможна передача со сколь угодно малой вероятностью ошибки.

Вторая теорема Шеннона о кодировании в присутствии шумов. Для обеспечения достаточной помехоустойчивости приходится вводить в передаваемый сигнал избыточность, уменьшая тем самым скорость передачи информации. Вполне естественно опасение, что при усилении ограничений на малость вероятности ошибки необходимая избыточность будет возрастать, прогрессивно снижая скорость передачи информации, возможно, до нуля. Однако все сомнения снимаются Второй теоремой Шеннона о кодировании для каналов с шумами, которая может быть сформулирована следующим образом:

Теорема. При условии Н £ С среди кодов, обеспечивающих (согласно Первой теореме) сколь угодно малую вероятность ошибки, существует код, при котором скорость передачи информации R сколь угодно близка к скорости создания информации Н.

Скорость передачи информации (на символ) определяется как

R = H – H(x| y), (8.26)

где Н(х| у) – апостериорная энтропия отправленного сигнала на символ, или рассеяние информации в канале.

Доказательство теоремы (см. ) начинается с утверждения о том, что минимальная необходимая избыточность на символ равна Н(х| у) добавочных символов. Далее показывают, что код можно выбрать так, чтобы Н(х| у) была сколь угодно малой величиной.

Обсуждение теорем. В первую очередь отметим фун­даментальность полученных результатов. Теоремы устанавливает теоретический предел возможной эффективно­сти системы при достоверной передаче информации. Опровергнуто казавшееся интуитивно правильным представление о том, что достижение сколь угодно малой вероятности ошибки в случае передачи информации по каналу с помехами возможно лишь при введении бесконечно большой избыточности, т.е. при уменьшении скорости передачи до нуля. Из теорем следует, что помехи в канале не накладывают ограничений на точность пере­дачи. Ограничение накладывается только на скорость передачи, при которой может быть достигнута сколь угодно высокая достоверность передачи.

Теоремы неконструктивны в том смысле, что в них не затрагивается вопрос о путях построения кодов, обес­печивающих указанную идеальную передачу. Однако, обосновав принципиальную возможность такого кодиро­вания, они мобилизовали усилия ученых на разработку конкретных кодов.

Следует отметить, что при любой конечной скорости передачи информации вплоть до пропускной способности сколь угодно малая вероятность ошибки достигается лишь при безгранич­ном увеличении длительности кодируемых последователь­ностей знаков. Таким образом, безошибочная передача при наличии помех возможна лишь теоретически.

Обеспечение передачи информации с весьма малой вероятностью ошибки и достаточно высокой эффектив­ностью возможно при кодировании чрезвычайно длинных последовательностей знаков. На практике степень досто­верности и эффективности ограничивается двумя факто­рами: размерами и стоимостью аппаратуры кодирования и декодирования и временем задержки передаваемого сообщения. В настоящее время используются относитель­но простые методы кодирования, которые не реализуют возможностей, указанных теорией. Однако постоянно растущие требования в отношении достоверности передачи и успехи в технологии создания больших интегральных схем способствуют внедрению для указанных целей все более сложного оборудования.

Следует, однако, иметь в виду, что теоремы для дискретных каналов с шумами, так же как и теорема 2 для каналов без шумов, не утверждает, что кодирование длинных последовательностей сооб­щений является единственным методом эффективного кодирования. Смысл этих теорем состоит в утверждении существования эффективных методов кодирования и в установлении количественных пределов максимально возможной скорости передачи информации. В связи с этим важными являются не только прямые, но и обратные утвер­ждения этих теорем. Из доказательства теорем вытекает лишь, что кодированием достаточно длинных последовательностей сообще­ний всегда можно как угодно близко подойти к максимально воз­можной скорости передачи сообщений (при минимальной вероятности ошибки для каналов с шумами). Последнее, однако, не означает, что не могут существовать другие способы эффективного кодирования. Наоборот, на ряде частных примеров можно показать, что такие способы существуют.

К сожалению, в настоящее время не найдено еще общих спосо­бов построения эффективных кодов для каналов с шумами, удовле­творяющих различным требованиям практики. Постепенно, однако, такие способы выявляются. Весьма интересным и важным является утверждение теоремы о том, что в канале с шумами при сколь угодно малой ненадежности передачи сообщений ( →0) скорость передачи информации может быть как угодно близкой к С С . Ранее господствовало мнение, основанное на интуитивных соображениях, что при этих требованиях скорость передачи информации должна не­ограниченно уменьшаться.

Фундаментальное значение теорем состоит в том, что они по­зволяют, зная предельные (теоретические) значения скорости передачи информации С С , оценить эффективность используемых методов ко­дирования.

Итак, приведенные теоремы являются теоремами существо­вания.

Из доказательства этих теорем не следует, каким образом построить код и произвести декодирование, что­бы вероятность ошибки была как угодно мала, а скорость передачи как угодно близка к пропускной способности ли­нии связи. Теоремы носят асимптотический характер, т.е. не являются конструктивными. Одна­ко уже само знание потенциальных возможностей имеет огромное зна­чение: сравнение характеристик реальных систем с теоретическими пределами позволяет судить о достигнутом уровне и о целесообразности дальнейших затрат на его повышение. Прикладные же вопросы рассматриваются в специальном разделе теории информации – теории кодирования, которая изучает способы построения конкретных ко­дов и их свойства, в частности точные или граничные зависимости вероятностей ошибок от параметров кода.

Обратная теорема Шеннона для каналов с шумами. Обратная теорема указывает условия, которые возникают при передаче информации по каналу с шумами со скоростью, превышающей пропускную способность.

Теорема. Если скорость создания информации Н больше пропускной способности канала С, то никакой код не может сделать вероятность ошибки сколь угодно малой. Минимальное рассеяние информации на символ, достижимое при Н > С, равно Н – С; никакой код не может обеспечить меньшего рассеяния информации.

С доказательством Обратной теоремы Шеннона можно ознакомиться в .

Обратная теорема утверждает, что при Н > С безошибочная передача невозможна; при этом чем больше отношение Н / C, тем больше остаточная неопределенность Н(х| у). Последняя связана с вероятностью ошибки при приеме. Естественно возникает вопрос о том, как связана минимальная вероятность ошибки, достигаемая при наилучшем кодировании, с отношением Н/ С. Для бинарного канала решение приведено в . При к = Н/C < 1 вероятность ошибки e(к ) = 0 согласно первой теореме. При к ® ¥ e(к ) ® 0,5, что означает, что доля передаваемой информации из всей поступающей на вход канала стремится к нулю при к ® ¥; чем быстрее ведется передача, тем меньшее количество информации передается.

Контрольные вопросы

1. Дайте обоснование необходимости введения избыточности при кодировании в канале с помехами.

2. Как определяется среднее количество информации (на один символ), переданной по дискретному каналу с шумами?

3. Как определяется скорость передачи и пропускная способность канала с помехами?

4. Сформулируйте и поясните прямую и обратную теоремы Шеннона о кодировании для канала с помехами.

5. Какие соотношения следуют из теоремы об асимптотической равновероятности достаточно длинных типичных цепочек для стационарных каналов с шумами?

6. Какова причина целесообразности кодирования длинных последовательностей символов?

7. Какой формулой определяется пропускная способность двоичного симметричного канала без памяти, при каком условии пропускная способность этого канала обращается в нуль?

Прямая теорема Шеннона для источника общего вида Не следует путать с другими теоремами Шеннона .

Теоремы Шеннона для источника общего вида описывают возможности кодирования источника общего вида с помощью разделимых кодов. Другими словами, описываются максимально достижимые возможности кодирования без потерь.

Прямая теорема

В применении к побуквенному кодированию прямая теорема может быть сформулирована следующим образом:

В качестве доказательства теоремы исследуются характеристики кода Шеннона-Фано . Данный код удовлетворяет условиям теоремы, и он обладает указанными свойствами.

Обратная теорема

Обратная теорема ограничивает максимальную степень сжатия, достигаемую с помощью кодирования без потерь. В применении к побуквенному кодированию, описывает ограничение на среднюю длину кодового слова для любого разделимого кода.

Для любого разделимого кода с длинами w 1 ,w 2 ,...,w K средняя длина сообщений больше или равна энтропии источника U , нормированный на двоичный логарифм от числа букв D в алфавите кодера:

Литература

• Габидулин, Э. М. , Пилипчук, Н. И. §3.4 Теоремы Шеннона для источника // Лекции по теории информации. - М .: МФТИ , 2007. - С. 49-52. - 214 с. - ISBN 5-7417-0197-3

Wikimedia Foundation . 2010 .

Смотреть что такое "Прямая теорема Шеннона для источника общего вида" в других словарях:

Не следует путать с другими теоремами Шеннона. Теоремы Шеннона для источника общего вида описывают возможности кодирования источника общего вида с помощью разделимых кодов. Другими словами, описываются максимально достижимые возможности… … Википедия

В Википедии есть статьи о других людях с такой фамилией, см. Шеннон. Клод Элвуд Шеннон Claude Elwood Shannon … Википедия

Клод Элвуд Шеннон (англ. Claude Elwood Shannon; родился 30 апреля 1916, Петоцки (Petoskey, Michigan) Мичиган, США, умер 24 февраля 2001, Медфорд, Массачусетс, США) американский математик и электротехник, один из создателей математической теории… … Википедия

Клод Элвуд Шеннон (англ. Claude Elwood Shannon; родился 30 апреля 1916, Петоцки (Petoskey, Michigan) Мичиган, США, умер 24 февраля 2001, Медфорд, Массачусетс, США) американский математик и электротехник, один из создателей математической теории… … Википедия

- (англ. Claude Elwood Shannon; родился 30 апреля 1916, Петоцки (Petoskey, Michigan) Мичиган, США, умер 24 февраля 2001, Медфорд, Массачусетс, США) американский математик и электротехник, один из создателей математической теории информации, в… … Википедия

Клод Элвуд Шеннон (англ. Claude Elwood Shannon; родился 30 апреля 1916, Петоцки (Petoskey, Michigan) Мичиган, США, умер 24 февраля 2001, Медфорд, Массачусетс, США) американский математик и электротехник, один из создателей математической теории… … Википедия

Клод Элвуд Шеннон (англ. Claude Elwood Shannon; родился 30 апреля 1916, Петоцки (Petoskey, Michigan) Мичиган, США, умер 24 февраля 2001, Медфорд, Массачусетс, США) американский математик и электротехник, один из создателей математической теории… … Википедия

Клод Элвуд Шеннон (англ. Claude Elwood Shannon; родился 30 апреля 1916, Петоцки (Petoskey, Michigan) Мичиган, США, умер 24 февраля 2001, Медфорд, Массачусетс, США) американский математик и электротехник, один из создателей математической теории… … Википедия

Для эффективного использования канала (повышения коэффициента нагрузки λ→1) необходимо его согласование с источником информации на входе. Такое согласование возможно как для каналов без помех, так и с помехами, на основании теорем кодирования для канала, предложенных Шенноном.

Теорема о кодировании для канала без помех.

Если источник сообщений имеет производительность [бит/сек], а канал связи – пропускную способность [бит/сек], то можно закодировать сообщение таким образом, чтобы передавать информацию по каналу связи со средней скоростью, сколь угодно близкой к величине , но не превзойти её.

Шеннон предположил и метод такого кодирования, который получил название оптимального кодирования. В дальнейшем идея такого кодирования была развита в работах Фано и Хаффмана. В настоящее время такие коды широко используются на практике (эффективное и оптимальное кодирование).

Прямая теорема Шеннона о кодировании для канала с помехами.

При любой производительности источника сообщения [бит/сек] меньшей, чем пропускная способность [бит/сек], существует такой способ кодирования, который позволяет обеспечить передачу всей информации, создаваемой источником сообщений со сколь угодно малой вероятностью ошибки ε.

Обратная теорема кодирования для канала с помехами.

Не существует способа кодирования, позволяющего вести передачу информацию со сколь угодно малой вероятностью ошибки, если производительность источника сообщений больше пропускной способности канала.

Доказательство теоремы кодирования для канала с помехами довольно объемно математически, поэтому ограничимся общим обсуждением физических аспектов её практического применения:

1. Теорема устанавливает теоретический предел возможной эффективности системы при достоверной передаче информации. Из теоремы следует, что помехи в канале не накладывают ограничений на точность передачи. Ограничения накладываются только на скорость передачи, при которой может быть достигнута сколь угодно высокая достоверность передачи.

При этом достоверность дискретного канала обычно оценивается значением вероятности ошибочного приема одного символа. Чем меньше вероятность ошибки, тем выше достоверность канала. Достоверность в свою очередь характеризует помехоустойчивость информационной системы.

Скорость передачи информации характеризует эффективность системы.

2. Теорема не затрагивает вопрос о путях построения кодов, обеспечивающих указанную идеальную передачу. Обосновав принципиальную возможность такого кодирования, она мобилизовала усилия ученых на разработку конкретных кодов.

3. При любой конечной скорости передачи информации, вплоть до пропускной способности, сколь угодно малая вероятность ошибки достигается лишь при безграничном увеличении длительностей кодируемых последовательностей знаков. Таким образом, безошибочная передача при наличии помех возможна лишь теоретически. Обеспечение передачи информации с весьма малой вероятностью ошибки и с достаточно высокой эффективностью возможна при кодировании чрезвычайно длинных последовательностей знаков.

Информационная емкость дискретного (4.4) и пропускная способность непрерывного (4.7) каналов характеризует их предельные возможности как средств передачи информации. Они раскрываются в фундаментальных теоремах теории информации, которые известны как основные теоремы кодирования Шеннона. Применительно к дискретному каналу она гласит:

Теорема 4.4.1. (Прямая теорема кодирования для ДКБП.) Для дискретного канала без памяти при скоростях кода R , меньших информационной емкости , всегда существует код, для которого средняя вероятность ошибки стремится к нулю с ростом длины кодового слова.

В случае же непрерывного канала она формулируется как

Теорема 4.4.2. (Прямая теорема кодирования для АБГШ-канала). По АБГШ–каналу с неограниченной полосой информация может передаваться со сколь угодно малой вероятностью ошибки, если скорость передачи меньше пропускной способности.

Обратная же теорема утверждает:

Теорема 4.4.3. При скорости передачи
, большей пропускной способности канала связиC , никакой код не обеспечит произвольно малой вероятности ошибки декодирования, т.е. абсолютно надежной передачи сообщений.

Следует отметить, что если обратная теорема доказывается для произвольной модели канала связи, то прямая только лишь для конкретных типов каналов.

Результаты теорем кодирования для канала с шумами в определенной степени неожиданны. В самом деле, на первый взгляд кажется, что уменьшение вероятности ошибок в передаче сообщений требует соответствующего уменьшения скорости передачи и что последняя должна стремиться к нулю вместе с вероятностью ошибок. Такой вывод, в частности, вытекает из рассмотрения многократной повторной передачи символов по каналу как способа уменьшения вероятности ошибок в передаче сообщений. В этом случае при наличии помех в канале связи обеспечить стремление к нулю вероятности ошибки в передаче сообщения можно только при стремлении скорости передачи к нулю.

Однако теорема кодирования показывает, что в принципе можно вести передачу со скоростью, сколь угодно близкой к C , достигая при этом сколь угодно малой вероятности ошибки. К сожалению, теоремы, указывая на принципиальное существование помехоустойчивого кода, не дают рецепта его нахождения. Можно лишь отметить, что для этого необходимо применять коды большой длины. При этом по мере приближения скорости передачи к пропускной способности и уменьшения вероятности ошибок код усложняется вследствие увеличения длины блоков, что приводит к резкому усложнению кодирующего и декодирующего устройств, а также запаздыванию выдачи информации при декодировании. Применяемые в настоящее время способы кодирования, которые будут рассмотрены в дальнейшем, не реализуют потенциальных возможностей системы связи. Единственным исключением служат открытые в последнее время турбо-коды.

1Этот результат справедлив для любых симметричных каналов.