Практическая работа №9 по дисциплине: Основы теории информации наименование работы: Решение задач с использованием оптимального кодирования информации

СМОЛЕНСКИЙ КОЛЛЕДЖ ТЕЛЕКОММУНИКАЦИЙ (филиал)
федерального государственного образовательного бюджетного учреждения высшего профессионального образования
«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ
им.проф. М.А. БОНЧ-БРУЕВИЧА»







Практическая работа №9


по дисциплине: Основы теории информации

наименование работы: Решение задач с использованием оптимального
кодирования информации







Для специальности: 230111 Компьютерные сети
Работа рассчитана на 2 часа
Составлена преподавателем: Скряго О.С.

















Смоленск,2014
1. Цель работы: Выработать практические умения по кодированию сообщений оптимальными кодами Шеннона-Фано и Хаффмана.
2. Литература:
2.1. Максимов М.В., Партыка Т.Л., Попов И.И. Архитектура ЭВМ и вычислительных систем. - М. Форум, 2005г
2.2. Крук Б.И., Попантонопуло В.И., Шувалов В.П. Телекоммуникационные системы и сети. Учебное пособие / Под ред. В.П. Шувалова. – М.: Горячая линия – Телеком, 2005г.

3. Подготовка к работе:
3.1. Повторить тему 1.6.
3.2. Подготовить бланк отчета (см.п.7).
3.3. Ответить на вопросы допуска:
3.3.1. Что называется кодированием?
3.3.2. Что называется двоичным кодированием?
3.3.3. Что называется декодированием?

4. Основное оборудование:
4.1. Калькулятор

5. Задание:
5.1. Выполните кодирование сообщения методом Шеннона-Фано.
Таблица 1
№ варианта
Задание

1
Объем алфавита источника сообщений mи = 5 символов. Вероятности появления символов равны р(1)=0,5; р(2)=0,25; р(3)=0,1; р(4)=0,1; р(5)=0,05. Канал передачи идеальный.

2
Объем алфавита источника сообщений mи = 5 символов. Вероятности появления символов равны р(1)=0,4; р(2)=0,35; р(3)=0,11; р(4)=0,09; р(5)=0,05.Канал передачи идеальный.

3
Объем алфавита источника сообщений mи = 5 символов. Вероятности появления символов равны р(1)=0,35; р(2)=0,30; р(3)=0,2; р(4)=0,1; р(5)=0,05. Канал передачи идеальный.

4
Объем алфавита источника сообщений mи = 5 символов. Вероятности появления символов равны р(1)=0,5; р(2)=0,28; р(3)=0,1; р(4)=0,1; р(5)=0,02. Канал передачи идеальный.

5
Объем алфавита источника сообщений mи = 5 символов. Вероятности появления символов равны р(1)=0,5; р(2)=0,2; р(3)=0,15; р(4)=0,1; р(5)=0,05. Канал передачи идеальный.

6
Объем алфавита источника сообщений mи = 5 символов. Вероятности появления символов равны р(1)=0,4; р(2)=0,35; р(3)=0,1; р(4)=0,1; р(5)=0,05.Канал передачи идеальный.

7
Объем алфавита источника сообщений mи = 5 символов. Вероятности появления символов равны р(1)=0,45; р(2)=0,25; р(3)=0,15; р(4)=0,1; р(5)=0,05. Канал передачи идеальный.

8
Объем алфавита источника сообщений mи = 5 символов. Вероятности появления символов равны р(1)=0,45; р(2)=0,3; р(3)=0,2; р(4)=0,03; р(5)=0,02. Канал передачи идеальный.

9
Объем алфавита источника сообщений mи = 5 символов. Вероятности появления символов равны р(1)=0,5; р(2)=0,25; р(3)=0,14; р(4)=0,1; р(5)=0,01. Канал передачи идеальный.

10
Объем алфавита источника сообщений mи = 5 символов. Вероятности появления символов равны р(1)=0,35; р(2)=0,25; р(3)=0,25; р(4)=0,1; р(5)=0,05. Канал передачи идеальный.


5.2. В передаваемом факсимильном сообщении N строк, все строки одинаковы. Выполните кодирование данного сообщения методом Хаффмана и рассчитайте его полный объем. Значение N и заданную последовательность черных и белых серий выберите из таблицы 2 в соответствии с вариантом.
Таблица 2
№ варианта
Строка
N

1
5Б;113Ч;358Б;243Ч;64Б;64Ч;1092Б;531Ч;101Б;28Ч;13Б;905Ч;800Б.
700

2
233Б;115Б;1000Б;385Б;623Ч;2Б;13Ч;1583Б;833Ч;425Б;113Ч;17Б;5Ч.
800

3
64Ч;113Б;58Ч;64Б;387Ч;588Б;13Ч;826Б;1111Ч;925Б;736Ч;100Б;500Ч.
600

4
87Б;678Ч;777Б;666Ч;78Б;69Ч;67Б;34Ч;967Б;543Ч;765Б;46Ч;867Б.
500

5
79Ч;987Б;68Ч;93Б;43Ч;65Б;876Ч;89Б;54Ч;76Б;545Ч;245Б;45Ч.
900

6
75Б;54Ч;853Б;214Ч;985Б;347Ч;925Б;382Ч;394Б;928Ч;743Б;43Ч;634Б.
650

7
835Ч;893Б;485Ч;589Б;584Ч;342Б;12Ч;87Б;67Ч;98Б;103Ч;645Б;44Ч.
750

8
375Ч;56Б;43Ч;654Б;46Ч;79Б;21Ч;65Б;43Ч;86Б;54Ч;86Б;564Ч.
850

9
42Б;72Ч;98Б;83Ч;782Б;683Ч;540Б;20Ч;19Б;60Ч;43Б;73Ч;46Б.
550

10
754Ч;456Б;54Ч;648Б;244Ч;656Б;882Ч;465Б;210Ч;160Б;147Ч;369Б;13Ч.
950


6. Порядок выполнения работы:
6.1. Ознакомиться с заданием.
6.2. Определить номер варианта (в соответствии с номером в журнале).
6.3. Выполнить задания в соответствии с вариантом.
6.4. Ответьте на контрольные вопросы.

7. Содержание отчёта:
7.1. Название и цель работы.
7.2. Указать номер варианта, привести условия задач своего варианта.
7.3. Представить решение задач согласно варианта.
7.4. Ответы на контрольные вопросы.

8. Контрольные вопросы:
8.1. Перечислите требования, предъявляемые к кодированию.
8.2. Поясните классификацию методов кодирования.
8.3. Что такое цена кодирования?
8.4. Поясните метод Шеннона-Фано.
8.5. Поясните метод Хаффмана.
8.6. Перечислите недостатки кода Хаффмана.













Составил преподаватель ____________ Скряго О.С.



9. Приложение:

Метод Шеннона–Фано.

Метод алфавитного, неравномерного, эффективного, адаптивного кодирования был предложен в 1948–49 гг. независимо друг от друга Р. Фано и К. Шенноном.
1) Вычислить вероятности появления каждого из символов исходного сообщения.
2) Упорядочить символы исходного сообщения по убыванию значений их вероятностей появления в сообщении.
3) Разбить полученное упорядоченное множество на два подмножества таким образом, чтобы суммарные вероятности каждого из них были по возможности одинаковыми и близкими к 0,5. При этом сообщениям из одного подмножества в качестве первого символа кодового слова присвоить нуль, а сообщениям из другого – единицу.
4) Каждое из двух подмножеств, полученных на предыдущем шаге, рассмотреть как новое множество и подвергнуть аналогичному разбиению, в результате чего будет получен второй символ кодового слова для каждого символа.
Действия 3) и 4) продолжать шагом до тех пор, пока в рассматриваемых множествах не останется по одному элементу.
Таким образом, основу построения кода Шеннона–Фано составляет процедура дихотомии, т. е. последовательного разбиения множества символов на две части.
Пример. Пусть в текстовом сообщении значения вероятностей появления каждого символа вычислены и представлены в таблице 3 в порядке убывания.
Таблица 3
хi
p(xi)
Процедура разбиения
Кодовая комбинация

х1
0,5
1



1

х2
0,25
0
1


01

х3
0,13
0
0
1

001

х4
0,11
0
0
0
1
0001

х5
0,01
0
0
0
0
0000


На первом шаге сообщение x1 сразу оказывается единственным элементом одного из подмножеств, поскольку его вероятность равна 0,5.
Поэтому с присвоением x1 кодового символа 1 кодирование этого сообщения завершается. Естественно, первый символ всех кодовых слов, отображающих сообщения из второго подмножества, полагается равным 0. Разумеется, конкретное соответствие между упомянутыми символами и подмножествами сообщений несущественно, и с равным успехом можно приписать x1 символ 0, а остальным сообщениям – 1. Второе разбиение приводит к образованию двух подмножеств с равными суммарными вероятностями, первое из которых включает сообщения х2, а второе – все оставшиеся, т. е.х3-х5.
При этом в качестве второго кодового символа 1 приписывается словам первого из подмножеств, тогда как 0 – словам второго. Дальнейшие действия ясны из таблицы и не нуждаются в комментарии.
Алгоритм Шеннона–Фано гарантирует соблюдение требования префиксности, так как каждое разбиение заканчивается присвоением разным подмножествам противоположных символов.

Метод Хаффмана.

Факсимильная связь представляет собой электрический способ передачи графической информации - неподвижного изображения текста или таблиц, чертежей, схем, графиков, фотографий и т.д.
В зависимости от используемого вида модуляции различают факсы 4 групп: 1,2 и 3 группы основаны на аналоговом методе передачи информации.
1 группа- страница текста передавалась 6 минут;
2 группа- время передачи одной страницы до 3 минут.
3 группа- время передачи одной страницы 30-60 секунд, скорость передачи до 14400 бит/с. Возможны две степени разрешения:
1. Стандартное (100 точек на дюйм);
2. Высокое (200 точек на дюйм).
4 группа основана на цифровом методе передачи информации. Разрешение очень высокое (до 400 точек на дюйм), нуждаются в высокоскоростных каналах связи, например ISDN.
В цифровых факсимильных аппаратах ITU-Т Group 3 при сжатии чёрно-белых изображений (один бит на пиксель) может быть использован алгоритм Хаффмана с фиксированной таблицей (одномерный код Хаффмана). Данный алгоритм рассмотрен в рекомендации ITU-Т Т.4 и поддерживается всеми цифровыми факсимильными аппаратами.
Метод Хаффмана относится к вероятностному методу сжатия. В основе этого метода лежит идея построения «дерева», в котором положение символа на ветвях определяется частотой его появления. Каждому символу присваивается код, длина которого обратно пропорциональна частоте появления этого символа. Существуют две разновидности вероятностных методов, различающихся способом определения вероятности появления каждого символа:
статические методы, использующие фиксированную таблицу частоты появления символов, рассчитываемую перед началом процесса сжатия;
динамические или адаптивные методы, в которых частота появления символа все время меняется, и по мере считывания нового блока данных происходит перерасчет начальных значений частоты.
Последовательности подряд идущих чёрных и белых точек в нём заменяются числом, равным их количеству. А этот ряд, в свою очередь, сжимается по методу Хаффмана с фиксированной таблицей.
Набор идущих подряд точек изображения одного цвета называется серией, а длина этого набора точек длиной серии.
В представленных ниже таблицах заданы два вида кодов:
- завершения серий - от 0 до 63 с шагом 1 (таблица 4);
- начальные (дополнительные) - от 64 до 2560 с шагом 64, которые используются, если длина серии превышает 63 (таблица 5)
Приведенные таблицы 4 и 5 построены с помощью классического алгоритма Хаффмана (отдельно для длин черных и белых серий). Значения вероятностей появления для конкретных длин серий получены путем анализа большого количества факсимильных изображений.
Каждая строка изображения сжимается независимо. Считается, что в факсимильном изображении существенно преобладает белый цвет, поэтому и все строки изображения начинаются с белой точки. Если строка начинается с черной точки, то считается, что строка начинается с белой серии с длиной 0 (например, последовательность длин серий 0, 3, 556, 10,... означает, что в этой строке изображения идут сначала 3 черных точки, затем 556 белых, затем 10 черных и т.д. Другая возможная запись – 3Ч, 556Б, 10Ч, ... Каждая строка завершается кодом ЕОL-000000000001).
Поскольку черные и белые серии чередуются, то реально коды белой и черной серий будут работать попеременно.
Признаком окончания факсимильной страницы служит повторение кода ЕОL 6 раз подряд.
Факсимильное сообщение передаётся, используя режим коррекции ошибок (ЕСМ), разбитым на НDLС кадры в соответствии с рекомендациями ITU-Т Т.4. Информационная часть каждого НDLС - кадра содержит 256 байт, за исключением последнего.
Заголовок каждого НDLС - кадра содержит 8 байт, включая контрольную комбинацию длиной 16 бит. При обнаружении ошибки НDLС - кадр передаётся повторно.

Пример:
Исходные данные: Строка - 0Б, 320Ч, 5Б, 79Ч, 56Б, 128Ч, 180Б, 64Ч, 64Б, 832Ч
N-700
Решение:
Строка передаваемого факсимильного изображения 0Б, 320Ч, 5Б, 79Ч, 56Б, 128Ч, 180Б, 64Ч, 64Б, 832Ч.
Сжатие кодом Хаффмана строки факсимильного изображения: 00110101 000000110011 1100 0000001111 000011000 01011001 000011001000 10010 01010101 0000001111 0000110111 11011 00110101 0000001001101 000000000001
1 строка включает в себя 134 бит (l), соответственно объем передаваемого факсимильного изображения будет равен: V= М* l + (6- 1)ЕОL=700* 134 + 5* 12 = 93860бит= 11733 байт,
где: N количество строк, l - длина строки, ЕОL - код завершения строки.
Так как полученное факсимильное сообщение передается разбитым на НDLС кадры, а информационная часть каждого НDLС - кадра содержит 256 байт, то определим количество НDLС - кадров следующим образом:
М = 11733/256 = 46 НDLС - кадров.
Так как заголовок каждого НDLС - кадра содержит 8 байт, то полный объем передаваемого факсимильного изображения найдем как: Vобщ = М * 8 + V = 46 * 8 +11733 = 12101 байт.

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






Таблица 4. Коды завершения
Длина серии

Код подстроки



Длина серии

Код подстроки



белой

черной





белой

черной


0

00110101

0000110111



32

00011011

000001101010


1

00111

010



33

00010010

000001101011


2

0001

11



34

00010011

000011010010


3

1000

10



35

00010100

000011010011


4

1011

011



36

00010101

000011010100


5

1100

0011



37

00010110

000011010101


6

1110

0010



38

00010111

000011010110


7

1111

00011



39

00101000

000011010111


8

10011

000101



40

00101001

000001101100


9

10100

000100



41

00101010

000001101101


10

00111

0000100



42

00101011

000011011010


11

01000

0000101



43

00101100

000011011011


12

001000

0000111



44

00101101

000001010100


13

000011

00000100





















45

00000100

000001010101


14

110100

00000111


46

00000101

000001010110


15

110101

000011000


47

00001010

000001010111
- -


16

101010

0000010111


48

00001011

000001100100


17

101011

0000011000


49

01010010

000001100101


18

0100111

0000001000


50

01010011

000001010010


19

0001100

00001100111


51

01010100

000001010011


20

0001000

00001101000


52

01010101

000000100100


21

0010111

00001101100


53

00100100

000000110111


22

0000011

00000110111


54

00100101

000000111000


23

0000100

00000101000


55

01011000

000000100111


24

0101000

00000010111


56

01011001

000000101000


25

0101011

00000011000


57

01011010

000001011000


26

0010011

000011001010


58

01011011

000001011001



27

0100100

000011001011


59

01001010

000000101011


28

0011000

000011001100


60

01001011

000000101100


29

00000010

000011001101


61

00110010

000001011010


30

00000011

000001101000


62

00110011

000001100110


31

00011010

000001101001


63

00110100

000001100111


Таблица 5 Начальные коды
Длина серии

Код подстроки














Длина серии

Код подстроки



белой

черной





белой

черной


64

11011

0000001111



1344

011011010

0000001010011


128

10010

000011001000



1408

011011011

0000001010100


192

01011

000011001001



1472

010011000

0000001010101


256

0110111

000001011011



1536

010011001

0000001011010


320

00110110

000000110011



1600

010011010

0000001011011
и.. ..


384

00110111

000000110100



1664

011000

0000001100100


448

01100100

000000110101



1728

010011011

0000001100101


512

01100101

0000001101100



1792

00000001000

Совп. с белой


576

01101000

0000001101101



1856

00000001100

-//-


640

01100111

0000001001010


1920

00000001101

-//-

704

011001100

0000001001011


1984

000000010010

-//-

768

011001101

0000001001100


2048

000000010011

-//-

832

011010010


0000001001101


2112

000000010100

-//-

896

011010011

0000001110010


2176

000000010101

-//-

960

011010100

0000001110011


2240

000000010110

-//-

1024

011010101

0000001110100


2304

000000010111

-//-


1088

011010110

0000001110101


2368

000000011100

-//-


1152

011010111

0000001110110


2432

000000011101

-//-


1216

011011000

0000001110111


2496

000000011110

-//-


1280

011011001

0000001010010


2560

000000011111

-//-










HYPER13 PAGE \* MERGEFORMAT HYPER1410HYPER15




HYPER15Основной шрифт абзаца

Приложенные файлы

  • doc f9
    Скряго О.С.
    Размер файла: 184 kB Загрузок: 1

Добавить комментарий