Emporio Armani мужские    часы

Emporio Armani мужские часы

Гуманитарные науки

У нас студенты зарабатывают деньги

 Дипломы, работы на заказ, недорого

Дипломы, работы на заказ, недорого

 Cкачать    курсовую

Cкачать курсовую

 Контрольные работы

Контрольные работы

 Репетиторы онлайн по английскому

Репетиторы онлайн по английскому

Приглашаем к сотрудничеству преподователей

Приглашаем к сотрудничеству преподователей

Готовые шпаргалки, шпоры

Готовые шпаргалки, шпоры

Отчет по практике

Отчет по практике

Приглашаем авторов для работы

Авторам заработок

Решение задач по математике

Закажите реферат

Закажите реферат

Курсовой расчет по сопромату Профилактическое обслуживание ПК Электротехника Контрольная по математике Эпоха становления русской живописи

Эффективная организация обмена информации

Второй способ доказательства прямой теоремы Шеннона для канала без шума. Метод Фано. Оптимальные коды

Второй способ доказательства прямой теоремы предполагает другой способ эффективного кодирования, который заключается в следующем: по-прежнему рассматриваем сообщение i представляющее собой последовательность элементарных сообщений uj длинной К. Расположим все сообщения  i в порядке убывания их вероятностей, пусть эти вероятности будут P1 P2    PL, где L=Nuk число сообщений i. Пусть , т.е. Qs накопленная вероятность до Ps-1 включительно. Закодируем сначала все сообщения в двоичную систему. Двоичный код для сообщения s получиться путем записи дробной части разложения Qs, как двоичного числа (при S=1, Qs=0). Разложение производиться до ms позиции, где ms целое число, удовлетворяющее соотношению

(2.7).

Пример: Пусть мы имеем 4 сообщения

1

2

3

4

P(1) = 1/2

P(2) = 1/4

P(3) = 1/8

P(4) = 1/8

Q1 = 0

Q2 = 1/2

Q3 = 3/4

Q4 = 7/8

m1 = 1

m2 = 2

m3 = 3

m4 = 4

код 0

код 10

код 110

код 111

Коды показанные в последней строчке таблицы - это коды Шэннона дробной части. [an error occurred while processing this directive]
Таким образом высоко вероятные сообщения представляются короткими кодами, а маловероятные длинными (это видно из (2.7)). Из этих неравенств вытекает следующая система неравенств (2.8). Оно показывает, что при выборе ms в соответствии с системой неравенств (2.7) вероятность сообщения с номером s Ps не меньше веса последнего младшего разряда двоичного разложения Qs. Вследствие этого код для Q s будет отличаться от всех последующих кодов одной и более из своих ms позиций, т.к. все остающиеся Qi, по крайней мере, на величину больше и поэтому их двоичное разложение отличается от кода для Qs, ходя бы в младшем разряде. Это говорит об однозначности предложенного способа кодирования. Среднее количество символов кода приходящихся на одно сообщение  можно определить, как (2.9), а среднее количество символов кода, приходящихся на одно элементарное сообщение Uk . Умножая все части системы неравенств (2.7) на и усредняя их по ансамблю сообщений i приходим к неравенствам (2.10), но , где Н - энтропия источника укрупненных сообщений  представляющих собой объединение К элементных независимых сообщений Ui (рассматриваем источник без памяти). Поэтому вследствие свойства адетивности энтропии H = K H(U). В свою очередь . Таким образом неравенство (2.10) можно записать в виде (2.11). Неравенство (2.11) показывает, что с неограниченным ростом значение К, среднее количество  символов кода приходиться на одно элементарное сообщение источника, сколь угодно близко приближается к значению энтропии этого источника. Поскольку мы рассматривали двоичный код с объемом алфавита равного 2 и log2M=log22=1 выполнение неравенства (2.11) эквивалентно выполнению условия (2.2), это и доказывает прямую теорему. Полученный результат позволяет дать следующее толкование энтропии: энтропия источника есть наименьшее количество двоичных символов на сообщение, на выходе наилучшего кодера для этого источника при условии, что сообщения могут быть восстановлены по выходу кодера сколь угодно точно. Два рассмотренных варианта доказательства прямой теоремы иллюстрируют два возможных подхода к построению эффективных кодов, основанных на использовании равномерного и неравномерного кодирования. При неравномерном кодировании обеспечивается однозначное декодирование всех сообщений.
Второй способ доказательства мы рассмотрели в той же трактовке, в которой он был дан Шенноном, а именно на основе построения двоичного эффективного кода возможен более общий подход, базируется на построении неравномерного статистического кода с произвольным основанием М непосредственно приводящей к результату (2.2). Такой вариант доказательства дан в книге Колесник-Бондарев.
Предложенный Шенноном метод эффективного кодирования практически совпадает с методом предложенным другим американским ученым Фано по которому сообщение длинны К, записанное в порядке не возрастания вероятностей разделяется на две части так, чтобы суммарные вероятности сообщений в каждой части были по возможности равны. Сообщениям первой части приписывается в качестве первого символа 0, сообщениям второй части 1. Затем каждая из этих частей (если она содержит более одного сообщения) опять делится на две примерно равные части и в качестве второго символа для первой из них берется 0, а для второй 1. Этот процесс повторяется до тех пор, пока в каждой из полученных частей не останется по одному сообщению. Существуют и другие методы эффективного кодирования. Кодирование по методу Шеннона-Фано так же как и другими методами может применятся не только к последовательностям из К элементных сообщений, но и непосредственно к источникам не равновероятных элементарных сообщений. При этом уменьшается выигрыш в эффективности. В том случае, когда левая часть системы неравенств (2.11) обращается в равенство, имеем min=H(U) (2.12). Код, обладающий min называется оптимальным для того, чтобы сообщение источника можно было закодировать двоичным оптимальным кодом необходимо и достаточно, чтобы все вероятности источника сообщения представляли собой числа равные целой отрицательной степени числа 2, т.е. Pi= , где аi - целое. Действительно как видно из неравенства (2.8) в таком случае вероятности Ps при выбранном нами способе определении длины кодового слова ms определятся, как . При этом среднее число символов кода приходящихся на одно сообщение в соответствии с (2.9) равно . В свою очередь энтропия источника сообщений Н равна . Таким образом получили, что с = с min=Н откуда после деления обеих частей последнего равенства на К можно придти к выражению (2.12). Рассуждая аналогичным образом можно показать, что и в случае кодирования сообщений источника неравномерным кодом с произвольным основанием М оптимальный код может быть получен при условии равенства вероятности всех сообщений целым отрицательным степеням числа М, т.е. при , где аi - целое и при этом . Если распределение вероятностей кодированного источника не обладает указанным свойством, эффективный код не будет оптимальным и соответствующая ему    min. Величина  = min/  (2.12а), характеризующая степень близости неравномерного статистического кода к оптимальному называется эффективностью кода. Таким образом нижний предел в условии теоремы, может быть, достигнут лишь при определенном распределении вероятности источника сообщений. Однако приближение к нему может быть сколь угодно близким при увеличении длинны К последовательности кодируемых сообщений. При этом рост эффективности системы передачи информации сопровождается увеличением задержки сообщений.
И так из рассмотренной теоремы вытекает, что для любого источника дискретных сообщений (т.е. характеризуется любым многомерным распределением вероятностей) скорость передачи информации по идеальному каналу может быть сделана сколь угодно близкой к пропускной способности канала при отсутствии потерь информации. При этом приближение тем больше, чем больше длина сообщения К, что указывает на возможность обмена задержки на скорость передачи информации.