Приобретение навыков кодирования сообщений с использованием процедуры Шеннона-Фано и процедуры Хаффмана
Построение бинарного дерева. Формирование кодов для каждого сообщения на основе полученного бинарного дерева процедурами Шеннона-Фано и Хаффмана. Расчет средней длины кодового слова. Вероятностная модель кодируемых сообщений. Процедура Шеннона-Фано.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 12.04.2014 |
| Размер файла | 433,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Приобретение навыков кодирования сообщений с использованием процедуры Шеннона-Фано и процедуры Хаффмана
Задача
На вход канала связи поступают сообщения. Количество передаваемых сообщений известно и известны вероятности поступления каждого из сообщений на вход. Задачей является построение бинарного дерева, формирование кодов для каждого сообщения на основе полученного бинарного дерева процедурами Шеннона-Фано и Хаффмана, а также расчет средней длины кодового слова для каждого случая.
Вариант 1
|
Вероятность |
P1 |
P2 |
P3 |
P4 |
P5 |
P6 |
P7 |
P8 |
|
|
Значение |
0,12 |
0,04 |
0,16 |
0,08 |
0,05 |
0,33 |
0,15 |
0,07 |
Теоретическая часть
Вероятностная модель кодируемых сообщений. Будем считать, что последовательность, которую нужно закодировать составлена из сообщений, принадлежащих некоторому конечному множеству с известным числом элементов N. Появление сообщений в последовательности носит вероятностный характер, т.е. каждому j -му сообщению () можно поставить в соответствие вероятность его появления () - условие нормировки. Сообщения кодируются последовательности двоичных знаков (0 и 1). В качестве критерия экономности кода выступает средняя длина кодового слова, необходимая для кодирования одного сообщения. Экономное кодирование основано на использовании кодов с переменной длиной кодового слова. Для кодирования сообщений будем использовать множество двоичных кодовых слов переменной длины , причем = - длина кодового слова , соответствующего сообщению .
Тогда в качестве критерия эффективности кодирования сообщений множества S кодовыми словами множества K выступает величина , называемая средней длиной кодового слова и определяемая следующим образом:
(1)
Рассмотрим пример. Пусть множество сообщений характеризуется вероятностями появления, определяемыми по следующей формуле:
(2)
(можно проверить, что условие нормировки при этом соблюдается).
Воспользуемся для кодирования данных сообщений кодовыми словами рассмотренного выше префиксного кода так, как это показано в таблице 1.
Таблица 1.
|
Сообщение |
Вероятность |
Кодовое слово |
Длина кодового слова |
|
|
s1 |
1/55 |
111111 |
6 |
|
|
s2 |
2/55 |
111110 |
6 |
|
|
s3 |
3/55 |
11110 |
5 |
|
|
s4 |
4/55 |
1110 |
4 |
|
|
s5 |
5/55 |
1001 |
4 |
|
|
s6 |
6/55 |
1000 |
4 |
|
|
s7 |
7/55 |
110 |
3 |
|
|
s8 |
8/55 |
101 |
3 |
|
|
s9 |
9/55 |
01 |
2 |
|
|
s10 |
10/55 |
00 |
2 |
По формуле (1) получим:
(бит/сообщение).
Если бы мы закодировали сообщения равномерным кодом, то, согласно формуле (1.1 в лекционных материалах) нам потребовались бы кодовые слова длины
(бит/сообщение), т.е. кодирование словами переменной длины оказывается более эффективным.
Заметим, что в приведенном примере кодовые слова ставились в соответствие сообщениям таким образом, что их длина оказывалась обратно пропорциональной вероятности появления каждого из сообщений. Тем самым обеспечивалось наиболее экономное кодирование, поскольку при данном способе распределения значение величины минимально.
Как же выбирать кодовые слова в общем случае, чтобы для заданных вероятностей p1, p2, …, pm обеспечить по возможности меньшую среднюю длину кодового слова, т.е. ?
Заметим, что если
,
то минимальную среднюю длину кодового слова обеспечивает равномерное двоичное кодирование. На каждом шаге двоичного кодирования производится разбиение множества сообщений на два подмножества, причем одному из них приписывается единица, а другому - ноль. Таким образом, на каждом шаге производится кодирование подмножеств равномерным кодом длиной в один двоичный знак. Отсюда следует принцип: нужно стремиться так производить разбиение на два подмножества, чтобы суммарные вероятности подмножеств были одинаковыми или как можно более близкими друг к другу. бинарный кодирование хаффман
Процедура Шеннона-Фано.
В этом алгоритме предварительно производится упорядочивание сообщений по возрастанию или убыванию вероятностей . Разбиение на подмножества производится путем выбора разделяющей границы в упорядоченной последовательности так, чтобы суммарные вероятности подмножеств были по возможности одинаковыми. Кодовое дерево, построенное этим методом для примера в таблице 1, приведено на рис.1. Возле каждой вершины дерева указывается суммарная вероятность соответствующего подмножества.
Выполнив расчеты по формуле (1), получим: =3,145 (бит/сообщение). Таким образом, код, полученный при помощи процедуры Шеннона-Фано, оказывается более экономным, чем код из таблицы 1.
Рис.1. Кодовое дерево в процедуре Шеннона-Фано
Процедура Хаффмана.
Рассмотренная выше процедура Шеннона-Фано является простым, но не всегда оптимальным алгоритмом построения экономного кода. Причина состоит в том, что способ разбиения на подмножества ограничен: вероятности сообщений, отнесенных к первому подмножеству, всегда больше или всегда меньше вероятностей сообщений, отнесенных ко второму подмножеству. Оптимальный алгоритм, очевидно, должен учитывать все возможные комбинации при разбиении на равновероятные подмножества. Это обеспечивается в процедуре Хаффмана.
Процедура Хаффмана представляет собой рекурсивный алгоритм, который строит бинарное дерево "в обратную сторону", т.е. от конечных вершин к корню. Основная идея алгоритма состоит в том, чтобы объединить два сообщения с наименьшими вероятностями - например, p1 и p2 - в одно множество и далее решать задачу с m-1 сообщениями и вероятностями p1' = p1 + p2; p2' = p3; … ; p(m-1)' = pm. Кодовое дерево, построенное процедурой Хаффмана для рассматриваемого примера, приведено на рис.2.
Расчеты по формуле (1) дают среднее значение длины кодового слова =3,145 (бит/сообщение), что совпадает с результатом применения процедуры Шеннона-Фано. Это означает, что для данного примера процедура Шеннона-Фано также оказалась оптимальной.
Рис.2 Кодовое дерево в процедуре Хаффмана
Расчетная часть
Метод Шеннона-Фано
Вариант 1
|
Вероятность |
P1 |
P2 |
P3 |
P4 |
P5 |
P6 |
P7 |
P8 |
|
|
Значение |
0,12 |
0,04 |
0,16 |
0,08 |
0,05 |
0,33 |
0,15 |
0,07 |
1. Упорядочим все сообщения по возрастанию вероятности
P2=0,04; P5=0,05; P8=0,07; P4=0,08; P1=0,12; P7=0,15; P3=0,16; P6=0,33;
2. Строим бинарное дерево
3. Вычислим эффективность кодирования
Метод Хаффмона
Размещено на Allbest.ru
...Подобные документы
Общее число неповторяющихся сообщений. Вычисление скорости передачи информации и пропускной способности каналов связи. Определение избыточности сообщений и оптимальное кодирование. Процедура построения оптимального кода по методике Шеннона-Фано.
курсовая работа [59,4 K], добавлен 17.04.2009Типы сжатия данных: с потерями (lossy) и без потерь (lossless). Сжатие с минимальной избыточностью. Кодирование методом Шеннона-Фано. Проверка работы программы по сжатию файлов формата bmp и xls. Реализация на Delphi алгоритма сжатия Шеннона и Хаффмана.
курсовая работа [2,6 M], добавлен 26.01.2011Изучение методов кодирования Хаффмана, Фано. Модель информационной системы Шеннона. Среднестатистическая информационная емкость сообщений для эргодических источников с заданным распределением частот символов. Формулы Хартли для удельной емкости на символ.
презентация [528,9 K], добавлен 19.10.2014Определение среднего количества информации. Зависимость между символами матрицы условных вероятностей. Кодирование методом Шеннона–Фано. Пропускная способность канала связи. Эффективность кодирования сообщений методом Д. Хаффмана, характеристика кода.
контрольная работа [94,6 K], добавлен 04.05.2015Определение понятий кода, кодирования и декодирования, виды, правила и задачи кодирования. Применение теорем Шеннона в теории связи. Классификация, параметры и построение помехоустойчивых кодов. Методы передачи кодов. Пример построения кода Шеннона.
курсовая работа [212,6 K], добавлен 25.02.2009Разработка программы на языке С#, которая будет заниматься построением бинарного дерева для исходных данных и их редактированием, поиском информации о товарах по заданному ключу. Графические схемы алгоритмов поиска и удаления элемента бинарного дерева.
курсовая работа [796,9 K], добавлен 22.02.2016Анализ эффективности способов кодирования. Средний размер одного разряда и средняя длина кодового слова. Кодирование по методу Хаффмена. Кодирование информации по методу Шенона-Фано. Построение кодового дерево для различных методов кодирования.
контрольная работа [491,4 K], добавлен 15.10.2013Краткий обзор основных теорий сжатия. Концепции идей и их реализация. Сжатие данных с использованием преобразования Барроуза-Вилера. Статический алгоритм Хафмана. Локально адаптивный алгоритм сжатия. Алгоритм Зива-Лемпеля (Welch) и метод Шеннона-Фано.
практическая работа [188,5 K], добавлен 24.04.2014Описание метода сжатия информации на основе двоичных кодирующих деревьев Хаффмана. Среда разработки Delphi версии 7.0. Понятия объектно-ориентированного программирования. Программа, разработанная в Delphi. Реализация на Delphi метода кодирования Хаффмана.
курсовая работа [2,1 M], добавлен 26.03.2013Особенности кодирования информации с помощью метода Хаффмана. Реализация кодера и декодера с использованием статического алгоритма Хаффмана. Структура программы, оценка ее эффективности (степени сжатия) в зависимости от типа и размера сжимаемых файлов.
курсовая работа [136,2 K], добавлен 15.06.2013Рассмотрение нелинейных динамических структур данных в виде бинарного дерева. Построение дерева двоичного поиска. Реализация трех обходов дерева, выведение обходов на экран компьютера. Разработка текста программы. Симметричноправая прошивка дерева.
контрольная работа [81,6 K], добавлен 14.12.2011Исследование особенностей основных файловых менеджеров, разработанных под операционную систему Windows. Изучение порядка заполнения элементов бинарного дерева. Обзор приложения, реализующего графический интерфейс доступа пользователя к папкам и файлам.
курсовая работа [2,9 M], добавлен 11.07.2012Описание процедуры выбора структуры хранения данных. Программная реализация одномерного неоднородного массива. Представление бинарного дерева в виде динамической структуры данных. Изучение способов поиска в упорядоченном дереве. Содержание базы данных.
практическая работа [850,0 K], добавлен 16.04.2015Организация таблицы идентификаторов, ее содержание и назначение. Метод бинарного дерева и цепочек. Проектирование лексического анализатора и схема распознавателя. Построение дерева вывода, синтаксический анализатор. Анализ результатов работы программы.
курсовая работа [1,0 M], добавлен 25.12.2014Схема и коэффициент эффективности дискретного канала. Функции блоков, свойства канальных матриц, информационные характеристики источника сообщений и приемника. Теоремы Шеннона о критической скорости, криптографическому и помехоустойчивому кодированию.
учебное пособие [994,9 K], добавлен 06.05.2011Организация бинарного дерева. Порядок размещения данных в нелинейных структурах. Организация пользовательского интерфейса. Симметричный обход дерева. Параллельная работа обработчиков исключений. Расширенный графический интерфейс и его возможности.
курсовая работа [426,0 K], добавлен 24.06.2013Вычисление количества информации, приходящейся на один символ по формуле Шеннона. Изменения информационной энтропии в текстах экономического, естественнонаучного и литературного содержания. Максимальное количество информации на знак по формуле Хартли.
лабораторная работа [28,2 K], добавлен 06.12.2013Описание и особенности некоторых алгоритмов архивации. Построение кода Хаффмана. Динамический алгоритм построения кода Хаффмана. Обратное восстановление текста. Способы двухступенчатого кодирования информации. Практическая реализация алгоритма LZ77.
курсовая работа [51,7 K], добавлен 24.12.2012Разработка принципов организации информационного обеспечения, структуры входных и выходных сообщений, классификаторов и кодов. Уточнение состава аппаратной платформы. Функциональное назначение проекта, руководство пользователя и описание программы.
курсовая работа [623,3 K], добавлен 18.09.2015Оценка вычислительной сложности программы. Реализация алгоритма кодирования информации Хаффмана. Кодировка теста двоичным кодом и в дереве Хаффмана. Бинарный код символов. Символ и частота его появления в тексте. Вычисление трудоемкости алгоритма.
контрольная работа [21,0 K], добавлен 16.12.2012
