Решение любой задачи, помеченной (*), автоматический зачет по курсу



Скачать 87.07 Kb.
Дата13.10.2012
Размер87.07 Kb.
ТипЗадача
2. Эффективное кодирование. Методы Шенона-Фано и Хаффмана

!!!ПРИМЕЧАНИЯ:

1)Нажимайте клавишу F9 - автоматический пересчет отключен.

2)Решение ЛЮБОЙ задачи, помеченной (*), - автоматический зачет по курсу.

Краткое содержание занятия

Закрепление понимания смысла энтропии Шенона. Практическое знакомство с методами генерации оптимальных кодов.
7 задач для самостоятельного решения.
Задача 1. Смысл энтропии Шенона
1.1. Неравномерные коды
Найти энтропию д.с.в. и среднюю длину каждого из приведенных кодов для этой д.с.в.


РЕШЕНИЕ:

;

1) Находим энтропию д.с.в. , как в предыдущем задании:

;

.

2) Вычисляем среднее значение длины кода для источника: или .

1. ; ; бит/символ;

2. ; ; бит/символ;

3. ; ; бит/символ;

4. ; ; бит/символ;

Задачи для самостоятельного решения

1.1.1.
ВАРИАНТЫ:

1)

Д.с.в. равна количеству "орлов", выпавших при бросании двух идеальных монет. Найти энтропию . Придумать минимальный код для и обосновать его минимальность.
2)

Д.с.в. , задана распределением . Найти энтропию . Придумать минимальный код для .
Вычислить среднюю длину кода и обосновать минимальность.
3)

Д.с.в. , задана распределением . Найти энтропию . Придумать минимальный код для . Вычислить среднюю длину кода и обосновать минимальность.
4)

Про д.с.в. известно, что ее значениями являются буквы кириллицы. Призведя ряд последовательных измерений , получен результат . Составить на основании этого результата приблизительный закон распределения вероятностей для и придумать минимальный код для , обосновать его минимальность.
5)

Д.с.в. равна количеству "орлов", выпавших при бросании ТРЕХ идеальных монет. Найти энтропию . Придумать минимальный код для и обосновать его минимальность.
6)

Д.с.в. , задана распределением . Найти энтропию . Придумать минимальный код для . Вычислить среднюю длину кода и обосновать минимальность.
7)

Д.с.в. , задана распределением . Найти энтропию . Придумать минимальный код для . Вычислить среднюю длину кода и обосновать минимальность.
8)

Про д.с.в. известно, что ее значениями являются буквы кириллицы. Призведя ряд последовательных измерений , получен результат . Составить на основании этого результата приблизительный закон распределения вероятностей для и придумать минимальный код для , обосновать его минимальность.
9)

Д.с.в. равна количеству "орлов", выпавших при бросании ПЯТИ идеальных монет. Найти энтропию . Придумать минимальный код для и обосновать его минимальность.
10)

Д.с.в. , задана распределением . Найти энтропию . Придумать минимальный код для . Вычислить среднюю длину кода и обосновать минимальность.
11)

Про д.с.в. известно, что ее значениями являются буквы кириллицы. Призведя ряд последовательных измерений , получен результат . Составить на основании этого результата приблизительный закон распределения вероятностей для и придумать минимальный код для , обосновать его минимальность.
12) см. 2

13) см. 3

14) см. 4

15) см. 5

16) см. 6

17) см. 7

18) см. 8

19) см. 9

20) см. 10

=======================================================================================











Задача 2. Сжатие информации. Метод Шенона-Фано
2.1. Алгоритм Шенона-Фано
Пусть сообщение представляет собой последовательность д.с.в. : . Каждая д.с.в. независима, может принимать значения и , и задана распределением вероятности

;

;

Найти код Шенона-Фано для для д.с.в. , которая является блоками из двух последовательных элементов последовательности д.с.в. . Вычислить энтропию , вычислить - среднюю длину кода Шенона-Фано.
РЕШЕНИЕ:
Для получим:

; , где первая колонка значение, вторая - вероятность этого значения.

1) Сортируем таблицу по возрастанию (или убыванию) вероятностей:

; ;

2) Делим таблицу на две части с "приблизительно" равными вероятностями и верхней части присваиваем бит 0, а нижней - 1:

;

;

3) делим каждую из двух частей снова

;

;

;

4) Повторяем деление для вновь образованных частей, пока есть чего делить...



- это коды Шенона-Фано. Первый столбец - исходные символы, второй - вероятности исходных символов, третий - коды, четвертый - десятичное целое число соответствующее коду, пятый - длина кода.

5) Энтропия , для :



бит/симв.

6) Средняя длина кода



бит/симв.

Задачи для самостоятельного решения
2.1.1. Найти код Шенона-Фано для д.с.в. , заданной распределением вероятности :

и сравнить среднюю длину символа для этого кода с энтропией .

ВАРИАНТЫ:


===============================================================================
2.1.2. Пусть сообщение представляет собой последовательность д.с.в. : . Каждая д.с.в. независима, может принимать значения и , и задана распределением вероятности

;

;

Найти код Шенона-Фано для для д.с.в. , которая является блоками из трех () последовательных элементов последовательности д.с.в. . Вычислить энтропию , вычислить - среднюю длину кода Шенона-Фано.
ВАРИАНТЫ:

1);

2);

3);

4);

5);

6);

7);

8);

9) ;

10) ;

11) ;

12);

13);

14);

15);

16);

17);

18);

19);

20);
=====================================================================================
2.1.3. Найти код Шенона-Фано для д.с.в. , заданную распределением вероятности пропорциональным значению . Значения и сравнить среднюю длину символа для этого кода с энтропией .
ВАРИАНТЫ:


======================================================================================
**2.1.4. Создать программу на MathCAD для кодирования методом Шенона-Фано произвольного файла. Закодированный файл должен быть самодостаточным, т.е. содержать всю необходимую для декодирования информацию.

Программа должна уметь кодировать и декодировать файл.



Задача 3. Сжатие информации. Метод Хаффмана
3.1. Алгоритм Хаффмана

Пусть сообщение представляет собой последовательность д.с.в. : . Каждая д.с.в. независима, может принимать значения и , и задана распределением вероятности

;

;

Найти код Хаффмана для для д.с.в. , которая является блоками из двух последовательных элементов последовательности д.с.в. . Вычислить энтропию , вычислить - среднюю длину кода Хаффмана.
Решение:

Для получим:

; , где первая колонка значение, вторая - вероятность этого значения.
1) Нумеруем узлы, чтобы иметь возможность ссылки на узел и добавляем еще две колонки для хранения структуры дерева.

Третья колонка матрицы - идентификатор строки для ссылки

Четвертая - идентификатор предыдущего левого узла;

Пятая - идентификатор следующего узла.




2) Сортируем таблицу по возрастанию вероятностей:

; ;

3) Объединяем два первых узла в новый узел и помещаем на нужное место - так, чтобы упорядоченность сохранилась





4) Исключаем первые две строки и повторяем объединение на оставшихся





5) Повторяем объединение, пока есть чего объединять...



- дерево Хаффмана.

5) Строим коды



- коды Хаффмана.
6) Энтропия , для :







бит/симв.
7) Средняя длина кода



бит/симв.

3.1. Задачи для самостоятельного решения

3.1.1. Найти код Хаффмана для д.с.в. , заданной распределением вероятности :

, сравнить среднюю длину символа для этого кода с энтропией и средней длиной кода Шенона-Фано.
ВАРИАНТЫ: см. задачу 2.1.1.

=================================================================================
3.1.2. Пусть сообщение представляет собой последовательность д.с.в. : . Каждая д.с.в. независима, может принимать значения и , и задана распределением вероятности

;

;

Найти код Хаффмана для для д.с.в. , которая является блоками из ТРЕХ последовательных элементов последовательности д.с.в. . Вычислить энтропию , вычислить - среднюю длину кода Хаффмана и сравнить со средней длиной кода Шенона-Фано.
ВАРИАНТЫ: см. задачу 2.1.2.

===================================================================================

3.1.3. Найти код Хаффмана для д.с.в. , заданную распределением вероятности пропорциональным значению . Значения , сравнить среднюю длину символа для этого кода с энтропией и со средней длиной кода Шенона-Фано.
ВАРИАНТЫ: см. задачу 2.1.3.

===================================================================================
**3.1.4. Создать программу на MathCAD для кодирования/декодирования методом Хаффмана произвольной строки символов.
**3.1.5. Реализовать на MathCAD демонстрационную программу для ДИНАМИЧЕСКОГО метода Хаффмана. Любой вариант динамического метода.

Похожие:

Решение любой задачи, помеченной (*), автоматический зачет по курсу iconРешение любой задачи, помеченной (*), автоматический зачет по курсу
В предположении, что это дискретная случайная величина (д с в.), имеющая областью значений множество целых чисел и равную вероятность...
Решение любой задачи, помеченной (*), автоматический зачет по курсу iconРешение любой задачи, помеченной (*) автоматический зачет по курсу
Практическое знакомство с методами генерации помехозащищенных кодов. Кодов обнаружения ошибок и кодов исправления ошибок
Решение любой задачи, помеченной (*), автоматический зачет по курсу iconДвойственность в линейном программировании
Для любой задачи лп можно сформулировать двойственную задачу, являющуюся "зеркальным отражением" исходной задачи, т к она использует...
Решение любой задачи, помеченной (*), автоматический зачет по курсу iconУрока геометрии в 8-м классе: "Решение задач. Урок-зачет"
Проверить уровень знаний и умение решать задачи на применение свойств касательных, вписанных и описанных окружностей, медианы тркугольника,...
Решение любой задачи, помеченной (*), автоматический зачет по курсу iconРешение многокритериальной задачи линейного программирования методом ограничений
Лабораторные работы по курсу тпр
Решение любой задачи, помеченной (*), автоматический зачет по курсу iconРешение задачи Коши
Учебно-тематические планы лекционных занятий по курсу «Уравнения в частных производных»
Решение любой задачи, помеченной (*), автоматический зачет по курсу iconВопросы к экзамену по курсу "Введение в акустику"
Звуковые волны. Различные типы задач акустики (задачи о свободных волнах; задачи с начальными условиями; краевые задачи; задачи о...
Решение любой задачи, помеченной (*), автоматический зачет по курсу iconРешение любой задачи 1
Здесь необходимо ориентироваться на те средства, которые предоставляют системы программирования и вычислительная техника, на которой...
Решение любой задачи, помеченной (*), автоматический зачет по курсу iconВведение в комбинаторику
Все это необходимо для изучения и построения формальных моделей и позволяет научиться такому подходу к любой задаче. При этом решение...
Решение любой задачи, помеченной (*), автоматический зачет по курсу iconРешение задач, аналогичных индивидуальным заданиям. Зачет проводится в письменном виде
Зачет осуществляется с учетом рейтинга по индивидуальным заданиям и рейтинга по результатам решения задач на письменном зачете
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org