ПР5_Отчёт_ЗаболотниковМЕ_9373

.docx

Скачиваний:

Добавлен:

20.06.2023

Размер:

35.61 Кб

Скачать

☆

МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра информационных систем

отчет

по практической работе №5

по дисциплине «Теория информации, данные, знания»

Тема: Эффективное кодирование. Код Шеннона-Фано

Студент(ка) гр. 9373		Заболотников М.Е.
Преподаватель		Писарев И. А.

Санкт-Петербург

2020

Цель работы

Сформулировать ответы на вопросы с указанием источников информации.

Вопросы по теме 5:

1. Дать определение методов эффективного (оптимального) кодирования

2. Основная теорема Шеннона о эффективном кодировании

3. Описать метод Шеннона-Фано

4. Решить две задачи:

А) Закодировать сообщение методом Шеннона-Фано

сообщение	a	b	c	d	e	f	g
вероятность	0.4	0.2	0.2	0.05	0.05	0.05	0.05

Привести в отчете полученный код и показать, как он был получен в виде таблицы с последовательностью расчетов.

Б) Алфавит содержит 7 букв, которые встречаются с вероятностями 0,4; 0,2; 0,1; 0,1; 0,1; 0,05; 0,05. Осуществите кодирование по методу Шеннона-Фано

Выполнение работы

Оптимальное кодирование Шеннона.

В кодировании Шеннона символы располагаются в порядке от наиболее вероятных к менее вероятным. Им присваиваются коды путём взятия первых цифр из двоичного разложения кумулятивной вероятности .

Оптимальное кодирование Шеннона-Фано.

Код строится следующим образом. Кодируемые знаки записываются в таблицу порядке убывания их вероятностей в сообщениях. Затем их разделяют на две группы так, чтобы суммарные вероятности обеих групп были как можно ближе друг к другу. Все знаки одной из групп кодируются, например, нулём, в то время как знаки другой группы – единицей. Эта процедура деления групп на подгруппы продолжается до тех пор, пока в каждой подгруппе не оказывается по одному элементу.

Оптимальное кодирование Хаффмана.

Для реализации данного алгоритма кодирования необходимо сперва взять два наименее вероятных символа в алфавите – эти два символа получат коды с самой большой длиной, отличающиеся последним знаком. Затем эти два символа объединяют, складывая при этом их вероятности. После этого происходит пересортировка вероятностей так, чтобы сохранился порядок убывания. Данную процедуру повторяют до тех пор, пока суммарная вероятность не окажется равной единице.

После проделанной работы строится дерево, корню которого ставится в соответствие узел, вероятность которого равна 1. Далее каждому узлу приписываются два потомка с вероятностями, которые участвовали в формировании этого узла. Процедура выполняется до достижения узлов с вероятностями исходных символов. Единица присваивается узлу с большей вероятностью, ноль – узлу с меньшей вероятностью. Чтобы понять, какой код получился в итоге у какого символа, нужно спуститься от корня к самому нижнему элементу, по пути «собирая» единички и нолики.

Основная теорема об эффективном кодировании:

«В дискретном канале без шума передача информации может быть обеспечена со скоростью, сколь угодно мало отличающейся от пропускной способности канала связи: , где – бесконечно малая величина.»