Практикум (лабораторный) Лабораторная работа №1. Кодирование информации
Целью лабораторной работы является изучение основных понятий теории информации, некоторых способов кодирования информации, а также идей оптимального и помехозащищенного кодирования.
Требования к содержанию, оформлению и порядку выполнения
Отчет по выполнению лабораторной работы должен содержать: титульный лист, название работы, цель работы и содержательную часть (далее будем рассматривать требования только к содержательной части).
В содержательной части отчета по выполнению лабораторной работы требуется отразить процесс построения оптимальных кодов, расчет энтропии и средней длины оптимального кода для своего варианта. Также требуется сделать вывод о соотношении средней длины кода и энтропии.
Если выполнены дополнительные задания, то эти результаты также следует представить в отчете.
Теоретическая часть
Теоретические сведения, необходимые для выполнения лабораторной работы представлены в разд.2.2 и 2.3.
Общая постановка задачи
В лабораторной работе требуется построить оптимальные коды для восьми сообщений, если заданы вероятности появления каждого из сообщений. Посчитать энтропию и среднюю длину оптимального кода. Варианты заданий представлены в виде таблицы в следующем разделе.
В качестве дополнительных заданий рекомендуется выполнить следующее:
Реализовать алгоритм, представленный блок-схемой на рис.2.3. Указание: для реализации алгоритма использовать любой алгоритмический язык высокого уровня.
Реализовать алгоритм, представленный блок-схемой на рис.2.4. Указание: для реализации алгоритма использовать любой алгоритмический язык высокого уровня. Если в языке есть битовые операции, то обращение целого i в набор
осуществить как с помощью операций
целочисленного деления, получения
остатка от деления, так и с помощью
битовых операций, причем желательно
предложить различные варианты
использования битовых операций для
реализации данного обращения.Построить графики времени работы алгоритмов, реализованных в пунктах 1 и 2. Указание: оба графика построить в одной системе координат. По оси Y откладывать время работы алгоритма, по оси X длину кода. Время работы алгоритма измерять с помощью функций времени используемого языка программирования. При этом выдавать на экран время начала и конца работы алгоритма, вывод кодов заблокировать. Длину кода менять. Рассматривать только те длины кода, при которых время работы алгоритмов составляет не менее одной секунды. Для построения графиков можно воспользоваться системой Excel.
Реализовать алгоритм, представленный блок-схемой на рис.2.5. Указание: для реализации алгоритма использовать любой алгоритмический язык высокого уровня.
Доработать алгоритмы реализованные в пунктах 1,2 и 4 так, чтобы к каждому кодовому слову добавлялся бит четности.
Список индивидуальных данных
Данные для выполнения лабораторной работы сведены в табл.Л1.1.
Таблица Л1.1 |
||||||||
Варианты заданий лабораторной работы №1 |
||||||||
Вариант |
Вероятности появления сообщений |
|||||||
m1 |
m2 |
m3 |
m4 |
m5 |
m6 |
m7 |
m8 |
|
1 |
0,04 |
0,17 |
0,279 |
0,158 |
0,07 |
0,191 |
0,009 |
0,083 |
2 |
0,347 |
0,014 |
0,0673 |
0,291 |
0,0986 |
0,084 |
0,053 |
0,0451 |
3 |
0,185 |
0,058 |
0,0692 |
0,198 |
0,191 |
0,183 |
0,014 |
0,1018 |
4 |
0,279 |
0,091 |
0,0174 |
0,383 |
0,0571 |
0,0936 |
0,0371 |
0,0418 |
5 |
0,291 |
0,096 |
0,285 |
0,183 |
0,001 |
0,0267 |
0,01 |
0,1073 |
6 |
0,311 |
0,081 |
0,0391 |
0,451 |
0,013 |
0,0281 |
0,0537 |
0,0231 |
7 |
0,0971 |
0,037 |
0,0992 |
0,476 |
0,281 |
0,001 |
0,0052 |
0,0035 |
8 |
0,0879 |
0,071 |
0,0893 |
0,625 |
0,0021 |
0,0361 |
0,0632 |
0,0254 |
9 |
0,0098 |
0,021 |
0,183 |
0,0271 |
0,691 |
0,00961 |
0,0439 |
0,01459 |
10 |
0,029 |
0,041 |
0,291 |
0,039 |
0,555 |
0,0142 |
0,0181 |
0,0127 |
11 |
0,471 |
0,039 |
0,0983 |
0,019 |
0,0381 |
0,142 |
0,0993 |
0,0933 |
12 |
0,221 |
0,021 |
0,0895 |
0,4193 |
0,0481 |
0,0987 |
0,0879 |
0,0145 |
13 |
0,003 |
0,039 |
0,0783 |
0,691 |
0,019 |
0,0921 |
0,0634 |
0,0142 |
14 |
0,01 |
0,081 |
0,0894 |
0,391 |
0,291 |
0,099 |
0,0192 |
0,0194 |
15 |
0,02 |
0,072 |
0,0832 |
0,0989 |
0,191 |
0,3891 |
0,117 |
0,0288 |
16 |
0,043 |
0,051 |
0,0673 |
0,295 |
0,219 |
0,2732 |
0,0439 |
0,0076 |
17 |
0,09 |
0,085 |
0,0582 |
0,318 |
0,229 |
0,216 |
0,0017 |
0,0021 |
18 |
0,08 |
0,059 |
0,0482 |
0,719 |
0,0198 |
0,014 |
0,0272 |
0,0328 |
19 |
0,07 |
0,0958 |
0,0938 |
0,1821 |
0,2393 |
0,307 |
0,0096 |
0,0024 |
20 |
0,069 |
0,0781 |
0,193 |
0,3 |
0,0911 |
0,2111 |
0,0439 |
0,0138 |
21 |
0,072 |
0,0272 |
0,295 |
0,0927 |
0,05892 |
0,3719 |
0,0673 |
0,01498 |
22 |
0,031 |
0,087 |
0,382 |
0,381 |
0,0094 |
0,0927 |
0,0047 |
0,0122 |
23 |
0,036 |
0,028 |
0,391 |
0,284 |
0,1927 |
0,0293 |
0,0297 |
0,0093 |
24 |
0,072 |
0,358 |
0,317 |
0,00569 |
0,09156 |
0,068 |
0,0373 |
0,05045 |
25 |
0,083 |
0,41 |
0,0629 |
0,01892 |
0,274 |
0,1 |
0,0321 |
0,01908 |
26 |
0,047 |
0,0721 |
0,0849 |
0,438 |
0,1937 |
0,1321 |
0,0284 |
0,0038 |
27 |
0,091 |
0,0632 |
0,029 |
0,791 |
0,0162 |
0,0082 |
0,000972 |
0,000428 |
28 |
0,083 |
0,0563 |
0,257 |
0,372 |
0,1883 |
0,00592 |
0,02865 |
0,00883 |
29 |
0,082 |
0,0761 |
0,374 |
0,0397 |
0,0869 |
0,3291 |
0,0087 |
0,0035 |
30 |
0,091 |
0,0825 |
0,00928 |
0,03591 |
0,2689 |
0,00778 |
0,291 |
0,21363 |