Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Топ:
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного...
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Интересное:
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Дисциплины:
2017-10-11 | 529 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!