Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Топ:
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Интересное:
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Дисциплины:
2017-10-11 | 534 |
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. Геометрическая интерпретация алгоритма Хаффмана
|
|
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!