Министерство образования и науки Украины

Одесский национальный морской университет

Кафедра “Информационные технологии”

Теория информации и кодирования

Расчетно-графическое задание №2

«Оптимальное кодирование»

Выполнила:

студентка КСФ 2к.,2гр.

Реу А.Г.

Проверил:

Ширшков А.К.

Личикаки Н.К.

Одесса 2015

Содержание

1. Назначение оптимального кодирования……………………………………...3

2. Идея сжатия…………………………………………..…………………………3

3. Равномерный двоичный код (РДК)...........................……………….………3-5

4. Оптимальный неравномерный код (ОНК) Шеннона – Фано……………...5-7

5. Оптимальный неравномерный код (ОНК) Хаффмена……………………..7-9

6. Факторы эффективности передачи…………………………………………....9

1. Назначение оптимального кодирования

Оптимальное кодирование – сжатие (компрессия) данных с сохранением их содержания.

Оптимальное кодирование позволяет:

1. Сжимать данные;

2. Сжимать время передачи данных при той же скорости;

3. Уменьшить возможные потери и искажение данных;

4. Архивировать данные, эффективно использовать память.

2. Идея сжатия

В ЭВМ информация кодируется с помощью равномерного двоичного кода, например, стандарт ISO – 7 бит, каждый символ имеет одинаковую битовую длину. Однако одни символы встречаются часто, другие – редко. Клодом Шенноном была предложена идея сжатия данных:

Часто встречающемуся символу назначается минимально короткий двоичный код.

Идея сжатия была применена в азбуке Морзе.

3. Равномерный двоичный код (рдк)

Дано сообщение:

S = Реу_Арина_Геннадьевна, l_S = 21 [симв.].

Составим алфавит:

A = {р, е, у, _, а, и, н, г, д, ь, в}, l_A = 11 [симв.].

Посчитаем вероятности и составим равномерный двоичный код (РДК) для символов алфавита:

i	ai	vi	p(ai)=vi/ls	РДК
1	Р	2	0,09524	0001
2	Е	3	0,14286	0010
3	У	1	0,04762	0011
4	-	2	0,09524	0100
5	А	4	0,19048	0101
6	И	1	0,04762	0110
7	Н	4	0,19048	0111
8	Г	1	0,04762	1001
9	Д	1	0,04762	1010
10	Ь	1	0,04762	1011
11	В	1	0,04762	1100

Рис. 1. Таблица для равномерного двоичного кода (РДК)

l_РДК = 4 [бит];

l_SРДК = l_S *l_РДК = 21*4 = 84 [бит];

Построим корневое бинарное дерево РДК 5-го порядка:

Рис. 2. Корневое бинарное дерево равномерного двоичного кода (РДК) 5-го порядка

Сообщение в РДК: S_РДК =

= 000100100011010001010001011001110101010010010010011101110101101010110010110001110101