Эффективное кодирование

ЛАБОРАТОРНАЯ  РАБОТА № 5

 

ЭФФЕКТИВНОЕ КОДИРОВАНИЕ

 

Цель работы: изучение методик эффективного кодирования.

Общие сведения:

Код Шеннона – Фано

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

 

Код Хаффмана.

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

 

Энтропия.

Энтропия - мера неопределённости какого-либо опыта (испытания), который может иметь  разные исходы, а значит и количество информации. Информационная энтропия - мера неопределённости источника  сообщений, определяемая вероятностям появления тех или иных символов при их передаче.

Ход работы:

Исследование  №1

Код Шеннона – Фано				Код Хаффмана
Знаки	Вероятность	Кодовые комбинации	Ступень разбиения	Кодовые комбинации
Z1	0,24	0000	2	0100
Z2	0,18	0100	3	1110
Z3	0,13	0110	1	1100
Z4	0,13	1000	5	1010
Z5	0,10	1010	4	0010
Z6	0,10	1100	6	0000
Z7	0,06	1110	7	1001
Z8	0,06	1111		1000
H(Z)	2,86
lср	2,88

Представим кодовое дерево (метод  Хаффмана):

 

Представим кодовую таблицу (метод Шеннона – Фано):

 

 

Представим кодовую таблицу (метод  Хаффмана):

Знаки	Исходный алфавит		Промежуточные алфавиты
Z1	0,24	0100	0,24	010	0,24	010	0,25	100	0,31	11	0,44	00	0,56	1
Z2	0,18	1110	0,18	111	0,20	000	0,24	010	0,25	10	0,31	11	0,44	0
Z3	0,13	1100	0,13	110	0,18	111	0,20	000	0,24	01	0,25	10
Z4	0,13	1010	0,13	101	0,13	110	0,18	111	0,20	00
Z5	0,10	0010	0,12	100	0,13	101	0,13	110
Z6	0,10	0000	0,10	001	0,12	100
Z7	0,06	1001	0,10	000
Z8	0,06	1000

 

Исследование  №2

Код Шеннона – Фано				Код Хаффмана
Знаки	Вероятность	Кодовые комбинации	Ступень разбиения	Кодовые комбинации
Z1	0,43	00000	1	00000
Z2	0,16	10000	3	11100
Z3	0,14	10100	2	10100
Z4	0,07	11000	5	11000
Z5	0,07	11010	4	10010
Z6	0,05	11100	6	10000
Z7	0,05	11110	7	11011
Z8	0,03	11111		11010
H(Z)	2,46
lср	2,49

 

Представим кодовое дерево (метод  Хаффмана):

Представим кодовую таблицу (метод  Шеннона – Фано):

 

Представим кодовую таблицу (метод  Хаффмана):

Знаки	Исходный алфавит		Промежуточные алфавиты
Z1	0,43	00000	0,43	000	0,43	0000	0,43	000	0,43	000	0,43	00	0,57	1
Z2	0,16	11100	0,16	1110	0,16	1110	0,16	111	0,16	111	0,31	11	0,43	0
Z3	0,14	10100	0,14	1010	0,14	1010	0,15	110	0,16	100	0,16	10
Z4	0,07	11000	0,08	1101	0,12	1000	0,14	101	0,15	110
Z5	0,07	10010	0,07	1100	0,08	1101	0,12	100
Z6	0,05	10000	0,07	1001	0,07	1100
Z7	0,05	11011	0,05	1000
Z8	0,03	11010

 

 

 

 

Исследование №3

 

Код Шеннона – Фано				Код Хаффмана
Знаки	Вероятность	Кодовые комбинации	Ступень разбиения	Кодовые комбинации
Z1	0.20	0000	2	0100
Z2	0.15	0100	3	1100
Z3	0.15	0110	1	1010
Z4	0.10	1000	5	1000
Z5	0.10	1010	6	1111
Z6	0.10	1011	4	1110
Z7	0.10	1100	7	0010
Z8	0.10	1110		0000
H(Z)	2.95
lср	3.00

 

 

 

 

 

 

 

Представим кодовую таблицу (метод  Шеннона – Фано):

 

 

Представим  кодовое дерево (метод Хаффмана):

 

 

 

 

 

Представим кодовую таблицу (метод  Хаффмана):

Знаки	Исходный алфавит		Промежуточные алфавиты
Z1	0.20	0100	0.20	0100	0.20	010	0.25	100	0.35	11	0.40	00	0.60	1
Z2	0.15	1100	0.20	0000	0.20	000	0.20	010	0.25	10	0.35	11	0.40	0
Z3	0.15	1010	0.15	1100	0.20	111	0.20	000	0.20	01	0.25	10
Z4	0.10	1000	0.15	1010	0.15	110	0.20	111	0.20	00
Z5	0.10	1111	0.10	1000	0.15	101	0.15	110
Z6	0.10	1110	0.10	1111	0.10	100
Z7	0.10	0010	0.10	1110
Z8	0.10	0000

 

 

Вывод: в ходе данной работы было произведено  изучение методик эффективного кодирования.

Лабораторная работа по

теории информации № 5

Лист

 

Иванов М.В, УИТС-11