Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Топ:
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Интересное:
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Дисциплины:
2017-10-11 | 545 |
5.00
из
|
Заказать работу |
|
|
Определим границы для и б пользуясь эвристическими соображениями, основанными на количестве информации. Очевидно, код будет самым экономным, если каждый символ кодового слова будет переносить максимально возможное количество информации.
Поскольку собственное количество информации, содержащееся в сообщении , равно информационной емкости соответствующего кодового слова будет достаточно, чтобы перенести указанное количество информации, только в том случае, если его минимальная длина li будет находиться в пределах , где - максимальное количество информации, которое может перенести отдельный символ кодового слова.
Усредняя неравенство по всему множеству X сообщений, получим неравенство, определяющее границы для минимальной средней длины кодового слова: .
В данном случае довольно большой интервал изменения возможных значений . Однако при кодировании блоков (слов из n букв xi) средняя длина приближается к значению при неограниченном увеличении длины блока п, что следует из неравенства где - среднее количество символов кодового слова, приходящееся на один блок, а на одну букву в блоке.
Полученные неравенства справедливы для всех однозначно декодируемых кодов.
Алгоритмы эффективного кодирования
Алгоритм Шеннона-Фано.
Пусть имеется множество сообщений .
1. Все сообщения располагаются в порядке убывания их вероятностей.
2. Упорядоченное множество сообщений делится на две части: верхнюю часть и нижнюю часть, причем так, чтобы разность между суммой вероятностей в верхней и нижней части была минимальной.
3. После этого сообщениям в верхней части ставится в соответствие 1, а в нижней – 0.
|
4. Далее аналогичные действия производятся с каждой из частей. Вновь полученные подмножества сообщений снова аналогичным образом делятся на две части и т.д., до получения по одному сообщению в каждом из подмножеств.
5. В результате каждому сообщению будет соответствовать своя последовательность из нулей и единиц, т.е. кодовое слово.
Пример:
Таблица 4.3
pi | X | |||
0.5 | x1 | |||
0.25 | x2 | |||
0.125 | x3 | |||
0.125 | x4 |
Алгоритм Хаффмена.
1. Все сообщения располагаются в порядке убывания их вероятностей.
2. Два самых нижних сообщения объединяются в одно событие, вероятность которого равна сумме вероятностей, объединяемых событий, причем верхнему событию ставится в соответствие 1, а нижнему 0.
3. Получился новый массив сообщений с количеством состояний на единицу меньшим по сравнению с предыдущим массивом, если два последних события считать одним более крупным событием. Далее преобразуем этот массив в соответствии с пунктами 1 и 2. Полученный массив вновь подвергаем указанным преобразованиям и т.д. до тех пор, пока не будет исчерпан весь массив.
4. Геометрически результат можно представить в виде дерева, где кодовое слово, соответствующее выражается последовательностью ветвей с соответствующим сообщением .
Пример:
x1=1, x2 = 01, x3 = 001, x4 = 000
Рис. 4.3. Геометрическая интерпретация алгоритма Хаффмана
|
|
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!