Применение алгоритма Хаффмана
Решение задачи на увеличение энтропии источника дискретных сообщений с применением алгоритма Хаффмана. Определение энтропии двоичного сигнала, способ получения кодовых комбинаций. Ошибка и её влияние на получаемые сообщения, характеристика кода Хаффмана.
| Рубрика | Математика |
| Вид | лабораторная работа |
| Язык | русский |
| Дата добавления | 20.05.2021 |
| Размер файла | 103,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Лабораторная работа
Тема: Применение алгоритма Хаффмана
Цель работы
Решение задачи на увеличение энтропии источника дискретных сообщений с применением алгоритма Хаффмана.
Задание
1. Построить код Хаффмана для сообщений, появляющихся с вероятностями:
Р(А1)=0,013;Р(А2)=0,186;P(A3)=0,039;Р(А4)=0,3;
Р(А5)=0,084;Р(А6)=0,267; Р(А7)=0,1;Р(А8)=0,011.
2. Определить среднюю длину кодовой комбинацииNсp и энтропиюH источника.
Составить двоичную кодовую последовательность при передаче последовательности сообщений:АА AA. Внести ошибку в полученную кодовую последовательность длиныn в [n-] разряд, и записать декодированную последовательность. Сравнить переданную и принятую последовательность. хаффман энтропия алгоритм кодовый
Решение
1) Для составления кодового древа необходимо выполнить следующие действия:
А ) Расположим исходные сообщения в порядке убывания вероятностей;
Б ) Объединим два наименее вероятных сообщения в одно, вероятность которого равнасумме вероятностей объединяемых сообщений (точка объединения сообщений называется «узлом кодового древа»);
В ) Повторяем шаги А) и Б) до тех пор, пока не получим одно сообщение с вероятностью . Эта точка называется «вершиной кодового дерева».
|
Р(А4) |
0,3 |
0,3 |
0,3 |
0,3 |
0,3 |
0,433 |
0,567 |
1 |
|
|
Р(А6) |
0,267 |
0,267 |
0,267 |
0,267 |
0,267 |
0,3 |
0,433 |
||
|
Р(А2) |
0,186 |
0,186 |
0,186 |
0,186 |
0,247 |
0,267 |
|||
|
Р(А7) |
0,1 |
0,1 |
0,1 |
0,147 |
0,186 |
||||
|
Р(А5) |
0,084 |
0,084 |
0,084 |
0,1 |
|||||
|
Р(АЗ) |
0,039 |
0,039 |
0,063 |
||||||
|
Р(А1) |
0,013 |
0,024 |
|||||||
|
Р(А8) |
0,011 |
Чтобы закодировать исходные сообщения новым кодом, идем от вершины дерева к сообщениям. Если в узлах кодового древа идем вверх, то в кодовую комбинацию пишем «1», а если вниз, то «0».
Кодовое древо примет следующий вид:
Далее выписываем из древа полученные кодовые комбинации:
А1=011001
А2=00
А3=01101
А4=11
А5=0111
А6=10
А7=010
А8=011000
2) Подсчитываем количество «нулей» и «единиц» на тысячу переданных сообщений:
Общее количество символов на тысячу переданных сообщений:
Вычисляем вероятность появления «0» и «1»:
Энтропия нового двоичного кода равна:
Средняя длина кодовой комбинации:
3) В отправленную кодовую последовательность:
А2 А7 A3 А8
[00|010|01101|011000]
Внесем ошибку разрядности[n-2]:
[00|010|01101|0111|00]
На приемной стороне получим:
А2 А7 A3 А5 А2
Результат
|
Энтропия источника: |
Н=0,989 |
|
|
Средняя длина кодовой комбинации: |
Ncp = 2,481 |
|
|
Сообщение без ошибки: |
А2 А7 A3 А8 |
|
|
Сообщение с ошибкой: |
А2 А7 A3 А5 А2 |
Контрольные вопросы
1) Найти характеристику кода Хаффмана
2) Найти определение энтропии двоичного сигнала
3) Принципы построения кодового древа
4) Способ получения кодовых комбинаций
5) Ошибка и её влияние на получаемые сообщения
Приложение
Таблица вариантов для группы СК-19
|
P1 |
P2 |
P3 |
P4 |
P5 |
P6 |
P7 |
P8 |
Передача |
Ошибка |
||
|
1 |
0,12 |
0,23 |
0,095 |
0,015 |
0,068 |
0,213 |
0,221 |
0,038 |
|||
|
2 |
0,004 |
0,008 |
0,016 |
0,032 |
0,064 |
0,128 |
0,256 |
0,492 |
|||
|
3 |
0,01 |
0,1 |
0,001 |
0,321 |
0,123 |
0,2 |
0,025 |
0,22 |
|||
|
4 |
0,25 |
0,125 |
0,075 |
0,175 |
0,225 |
0,05 |
0,005 |
0,095 |
|||
|
5 |
0,07 |
0,501 |
0,009 |
0,065 |
0,204 |
0,006 |
0,05 |
0,095 |
|||
|
6 |
0,24 |
0,032 |
0,08 |
0,248 |
0,064 |
0,114 |
0,086 |
0,136 |
|||
|
7 |
0,064 |
0,008 |
0,016 |
0,512 |
0,256 |
0,004 |
0,128 |
0,012 |
|||
|
8 |
0,027 |
0,021 |
0,243 |
0,009 |
0,049 |
0,081 |
0,003 |
0,567 |
|||
|
9 |
0,04 |
0,4 |
0,004 |
0,06 |
0,006 |
0,3 |
0,003 |
0,187 |
|||
|
10 |
0,003 |
0,017 |
0,07 |
0,049 |
0,7 |
0,007 |
0,014 |
0,14 |
|||
|
11 |
0,2 |
0,002 |
0,02 |
0,04 |
0,004 |
0,4 |
0,3 |
0,034 |
|||
|
12 |
0,06 |
0,216 |
0,072 |
0,288 |
0,12 |
0,084 |
0,016 |
0,144 |
|||
|
13 |
0,125 |
0,05 |
0,5 |
0,005 |
0,25 |
0,025 |
0,01 |
0,035 |
|||
|
14 |
0,081 |
0,162 |
0,054 |
0,064 |
0,009 |
0,27 |
0,036 |
0,324 |
|||
|
15 |
0,372 |
0,158 |
0,207 |
0,069 |
0,009 |
0,039 |
0,053 |
0,093 |
|||
|
16 |
0,05 |
0,3 |
0,015 |
0,1 |
0,01 |
0,075 |
0,2 |
0,25 |
|||
|
17 |
0,432 |
0,123 |
0,012 |
0,001 |
0,321 |
0,021 |
0,032 |
0,058 |
|||
|
18 |
0,02 |
0,203 |
0,567 |
0,025 |
0,009 |
0,101 |
0,045 |
0,03 |
|||
|
19 |
0,12 |
0,48 |
0,03 |
0,005 |
0,24 |
0,05 |
0,015 |
0,06 |
|||
|
20 |
0,053 |
0,35 |
0,028 |
0,105 |
0,029 |
0,035 |
0,21 |
0,19 |
|||
|
21 |
0,113 |
0,2 |
0,324 |
0,012 |
0,045 |
0,236 |
0,006 |
0,064 |
|||
|
22 |
0,61 |
0,002 |
0,015 |
0,068 |
0,125 |
0,114 |
0,009 |
0,057 |
|||
|
23 |
0,005 |
0,458 |
0,024 |
0,147 |
0,069 |
0,264 |
0,014 |
0,019 |
|||
|
24 |
0,312 |
0,168 |
0,008 |
0,036 |
0,079 |
0,231 |
0,144 |
0,022 |
|||
|
25 |
0,038 |
0,701 |
0,006 |
0,042 |
0,124 |
0,007 |
0,057 |
0,025 |
|||
|
26 |
0,25 |
0,125 |
0,005 |
0,325 |
0,075 |
0,025 |
0,015 |
0,18 |
|||
|
27 |
0,402 |
0,009 |
0,088 |
0,167 |
0,125 |
0,091 |
0,114 |
0,004 |
|||
|
28 |
0,003 |
0,357 |
0,159 |
0,258 |
0,056 |
0,108 |
0,044 |
0,015 |
|||
|
29 |
0,03 |
0,4 |
0,011 |
0,111 |
0,07 |
0,177 |
0,001 |
0,2 |
|||
|
30 |
0,012 |
0,144 |
0,372 |
0,046 |
0,1 |
0,006 |
0,064 |
0,256 |
Размещено на Allbest.ru
...Подобные документы
Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма.
курсовая работа [118,7 K], добавлен 30.04.2011Форма для ввода целевой функции и ограничений. Характеристика симплекс-метода. Процесс решения задачи линейного программирования. Математическое описание алгоритма симплекс-метода. Решение задачи ручным способом. Описание схемы алгоритма программы.
контрольная работа [66,3 K], добавлен 06.04.2012Оптимальная настройка параметров "алгоритма отжига" при решении задачи коммивояжера. Влияние начальной температуры, числа поворотов при одной температуре и коэффициента N на результат. Сравнение и определение лучшей функции для расчётов задачи.
контрольная работа [329,9 K], добавлен 20.11.2011Понятие генетического алгоритма и механизм минимизации функции многих переменных. Построение графика функции и ее оптимизация. Исследование зависимости решения от вида функции отбора родителей для кроссинговера и мутации потомков, анализ результатов.
контрольная работа [404,7 K], добавлен 04.05.2015Графы - определение и примеры. Задачи на нахождение всех комбинаций партий в шахматы между игроками, выбора нужной марки для письма, составления двузначного кода из возможных четырех цифр, расположения заданного количества гостей на разноцветных стульях.
презентация [56,9 K], добавлен 27.03.2011Система Ляпунова - случай одной степени свободы. Необходимые и достаточные условия существования периодических решений. Применение алгоритма Ляпунова для построения приближенного периодического решения задачи Коши для системы дифференциальных уравнений.
курсовая работа [243,8 K], добавлен 11.05.2012Теоретические основы метода отсечения, его назначение и функции в решении задач целочисленного линейного программирования. Сущность и практическая реализация первого и второго алгоритма Гомори. Применение алгоритма Дальтона, Ллевелина и Данцига.
курсовая работа [208,1 K], добавлен 12.10.2009Нахождение минимального пути от фиксированной до произвольной вершины графа с помощью алгоритма Дейкстры, рассмотрение основных принципов его работы. Описание блок-схемы алгоритма решения задачи. Проверка правильности работы разработанной программы.
курсовая работа [495,4 K], добавлен 19.09.2011Нахождение полинома Жегалкина методом неопределенных коэффициентов. Практическое применение жадного алгоритма. Венгерский метод решения задачи коммивояжера. Применение теории нечетких множеств для решения экономических задач в условиях неопределённости.
курсовая работа [644,4 K], добавлен 16.05.2010Суть метода Зейделя. Расчет разностных схемам относительно неизвестной сеточной функции. Параллельное решение систем линейных алгебраических уравнений. Процедура построения параллельного алгоритма Зейделя. Оценка ускорения представленного алгоритма.
контрольная работа [98,1 K], добавлен 09.01.2011Численное решение дифференциальных уравнений с помощью многошагового метода прогноза и коррекции Милна. Суммарная ошибка метода Милна. Применение метода Рунге-Кутта для нахождения первых значений начального отрезка. Абсолютная погрешность значения.
контрольная работа [694,0 K], добавлен 27.02.2013Значение и применение комбинаторики. Решение и геометрическое представление комбинаторной задачи "очередь в кассу". Применение метода подсчёта ломаных, определение свойства числа сочетаний. Блуждания по бесконечной плоскости в четырёх направлениях.
курсовая работа [262,5 K], добавлен 05.12.2012Доказательство существования или отсутствия алгоритма для решения поставленной задачи. Определение алгоритмической неразрешимости задачи. Понятия суперпозиции функций и рекурсивных функций. Анализ схемы примитивной рекурсии и операции минимизации.
курсовая работа [79,5 K], добавлен 12.07.2015Способы решения задач дискретной математики. Расчет кратчайшего пути между парами всех вершин в ориентированном и неориентированном графах с помощью использования алгоритма Флойда. Анализ задачи и методов ее решения. Разработка и характеристика программы.
курсовая работа [951,4 K], добавлен 22.01.2014Сущность методов сведения краевой задачи к задаче Коши и алгоритмы их реализации на ПЭВМ. Применение метода стрельбы (пристрелки) для линейной краевой задачи, определение погрешности вычислений. Решение уравнения сшивания для нелинейной краевой задачи.
методичка [335,0 K], добавлен 02.03.2010Предмет вычислительной техники - задачи, которые умеют решать машины. Измерение сложности задачи. Алгоритм сортировки слиянием. Полиномиальные и не полиномиальные задачи. Понятие недетерменированного алгоритма. Графическое представление классификации.
презентация [277,7 K], добавлен 22.10.2013Изучение основных вопросов теории графов и области ее применения на практике. Разработка алгоритма кластеризации по предельному расстоянию и построение минимального остовного дерева каждого кластера. Результаты тестирований работы данного алгоритма.
курсовая работа [362,9 K], добавлен 24.11.2010Остовное дерево связного неориентированного графа. Алгоритм создания остовного дерева, его нахождение. Сущность и главные особенности алгоритма Крускала. Порядок построения алгоритма Прима, вершина наименьшего веса. Промежуточная структура данных.
презентация [140,8 K], добавлен 16.09.2013Назначение, состав и структура арифметическо-логических устройств, их классификация, средства представления. Принципы построения и функционирования АЛУ ЭВМ. Создание блок-схемы алгоритма умножения, определение набора управляющих сигналов, схемное решение.
курсовая работа [134,0 K], добавлен 25.10.2014Задачи оптимального управления системами обыкновенных дифференциальных уравнений. Системы уравнений, определяющие дифференциальную связь между состоянием и управлением. Решение задачи о прилунении космического корабля при помощи дискретных методов.
курсовая работа [188,9 K], добавлен 25.01.2014
