русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Кодирование при наличие шумов


Дата добавления: 2013-12-23; просмотров: 1435; Нарушение авторских прав


Наиболее интересные и важные результаты были получены при рассмотрении передачи информации по каналам связи с шумами. В этом случае безизбыточное кодирование приведет к безвозвратным потерям информации: искаженный символ нельзя ни обнаружить, ни исправить. Для борьбы с влиянием помех необходимо ввести избыточность в сигнал. Основываясь на интуитивных соображениях, легко прийти к выводу, что при неограниченном повышении требований к малости вероятности ошибки избыточность (при любом способе кодирования) должна неограниченно возрастать, а скорость передачи — стремиться к нулю. Здесь мы имеем яркий пример того, как интуиция может привести к сильному заблуждению. К.Шеннон показал, что «существуют такие способы введения избыточности, при которых обеспечиваются одновременно и сколь угодно малая вероятность ошибки и конечная (отличная от нуля) скорость передачи информации. Причем эта скорость может быть сколь угодно близкой к пропускной способности канала». Это замечательное открытие и привлекло столь большое внимание к теории информации. Воспроизведем упрощенное доказательство указанного утверждения.

Рис.11.1 — Схема передачи по каналу с шумом

Будем считать, что на вход кодера сигналы поступают закодированными безизбыточно. Кодер вносит в сигнал избыточность, увеличивая длительность кодовых слов. Число возможных последовательностей сразу резко увеличивается. Но избыточность и состоит в том, что к отправке предназначаются не все из них, а лишь «разрешенные» (на рис. отмечены черными кружками). Согласно фундаментальному свойству энтропии, число всевозможных последовательностей длины n равно 2nH(X), а число разрешенных к отправке равно 2nH < 2nH(X) (считаем, что энтропия исчисляется в битах); Н — энтропия на символ во множестве разрешенных к отправке последовательностей (»энтропия источника», или «скорость создания информации»), H(X) — энтропия на символ во множестве всевозможных последовательностей. В результате воздействия шумов какие-то из символов отправленной последовательности подменяются другими и на приемный конец поступает другая, отличная от отправленной, последовательность. Поскольку p(x/y) считается известной, каждой принятой последовательности соответствует 2nH(X/Y) возможно отправленных. Декодирование, (т.е. принятие решения о том, какая последовательность была отправлена) можно выразить как разбиение всего множества Y принимаемых последовательностей на 2nH подмножеств, сопоставляемых с разрешенными к отправке. Если, например, принят сигнал i-й группы, то считается, что был послан i-й разрешенный сигнал, который и выдается в «чистом» виде получателю. Итак, в построенной модели проблема выбора кода (способа передачи) состоит в размещении разрешенных последовательностей среди множества всевозможных на передающем конце и в разбиении этого множества из 2nH(X) последовательностей на 2nH подмножеств на приемном конце.



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

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

  2nH/2nH(X) = 2n(H-H(X)). (6)

Средняя вероятность того, что в декодирующем подмножестве из 2nH(X/Y) последовательностей имеется только одна разрешенная, выразится соотношением

  P = {1 - 2n(H-H(X))}2nH(X/Y) - 1. (7)

Это и есть вероятность безошибочного приема. Поскольку

H < C = H(X) - H(X/Y),
H - H(X) = -H(X/Y) - ν, где ν > 0

Отсюда (пренебрегая единицей по сравнению с 2nH(X/Y) находим

P = {1 - 2n(H-H(X))}2nH(X/Y) - 1.

Логарифмируя и применяя правило Лопиталя, легко показать, предел Р = 1, при n стремящемся к бесконечости, т.е. при кодировании достаточно длинными блоками средняя вероятность ошибки может быть сделана сколь угодно малой. Доказательство завершается утверждением, что существуют коды с вероятностями ошибок меньше средней.



<== предыдущая лекция | следующая лекция ==>
Кодирование в отсутствии шумов | Пропускная способность гауссова канала связи


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.005 сек.