Главная Обратная связь

Дисциплины:






Теорема о существовании предельной условной энтропии для стационарной случайной последовательности. Средняя энтропия на один символ для стационарной случайной последовательности



Трм. Для любой стационарной случайной последовательности:

.

Опр. Случайная последовательность стационарна, если её n-мерные и условные вероятности не зависят от времени:

Док-во . Из определения стационарности: ,qed.

Трм. Для любой стационарной случайной последовательности

Док-во ,qed.


13. Блочное кодирование. Теорема Шеннона о кодировании независимых сообщений в отсутствии помех для блочного кодирования

Покажем что блочное кодирование позволяет сколь угодно близко подойти к нижней границе неравенства

Разобьём исходное сообщение на блоки из n букв и будем рассматривать эти блоки как буквы нового алфавита (расширенный алфавит)

Букв в расширенном алфавите Mn

Для этого расширенного алфавита применим теорему Шенона

т.к блоки независимы, то

H(X1…Xn)=H(X1)+…H(Xn)=nH(X)

Посчитаем число букв алфавита кода, котр. Мы будем использовать для нового алфавита

nà¥

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

 

14.Оптимальное кодирование. Коды Шенона-Фано и Хафмана.

Признаки оптимального кода:

1. Каждый символ кодового алфавита для опт. Кода должен доставлять максимальное кол-во информации Равной ёмкости алфавита (log m) поэтому вероятность использования символов кода –одинакова.

2. Совокупность кодовых символов будет давать максимальное количество информации когда символы в кодовых словах стат. Независимы.

Способы кодирования.

1) Код Шенона-Фано.

1. Все сообщения записываются в порядке убывания их вероятности

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

3. Для всех сообщений входящих в первую группу берём один и тот же знак (например 0) а для второй группы другой(напр.1)

4. Затем повторяем то же самое для каждой группы сообщений.

Эта операция продолжается до тех пор, пока в каждой подгруппе не останется по 1 исходному сообщению.

Замечания:

1. Из самого построения кода Шенона-Фано видно что он пытается удовлетворить признакам оптимального кода

2. Код является обратимым(т.е никакое кодовое слово не является началом более длинного)

2) Код Хафмана:

1. Два наименее вероятных сообщения объединяются в одно, причём ему приписывается суммарная вероятность объединяемых букв и составляется новый сжатый алфавит А1 из М-1 буквы

2. Процесс сжатия продолжается до тез пор, пока не придём к алфавитам АМ-2 или АМ-1 Получился граф в виде дерева с внутренними вершинами



3. начинаем справа и каждой ветви, выходящей из внутреннего узла ставится в соответствие 0 или 1

4. Кодовое слово, соотв. Буквам исходного алфавита можно получить пройдя обходы дерева справа до соотв. Данной букве концевого узла.

Замечания:

1. Код является обратимым(т.е никакое кодовое слово не является началом более длинного)

2. Если вер-ти у разных букв одинаковы то их можно объединить в произвольном порядке коды при этом получатся разные но их экономичность (средняя длина) будут одинаковы.

3. целое, то можно показать что все внутренние узлы будут полные т.е у каждого узла выходит напр. По 3 ветви

4. не целое то из внутренних узлов кодового дерева должен быть неполный. Можно доказать что в оптим. Кодовом дереве неполный узел должен принадлежать последнему этапу ветвления (последний узел – справа налево)

r – остаток от деления и последнему узлу нужно приписать r+1 ветвь

 





sdamzavas.net - 2019 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...