Теория информации лабы Бурькова. Теория информации
 Скачать 0.93 Mb.
|
|
избыточности. Ин- 42 формационная избыточность показывает относительную недогруженность на символ алфавита и является безразмерной величиной Кроме общего понятия избыточности есть частные виды избыточности. Из- быточность, обусловленная неравновероятным распределением символов в сооб- щении (6.3) Избыточность, вызванная статистической связью между символами сооб- щения (6.4) Полная информационная избыточность D = Ds + Dp – DsDp (6.5) Для данного способа кодирования характерна избыточность. Это объясня- ется тем, что в результате неравномерного распределения качественных призна- ков этого кода не может быть задана одной цифрой на основании статистических испытаний. При передаче десятичных цифр двоичным кодом максимально загру- женными бывают только те символы вторичного алфавита, которые передают значения, являющиеся целочисленными степенями двойки. В остальных случаях тем же количеством символов может быть передано большее количество цифр (сообщений). Фактически для передачи сообщения достаточно иметь длину кодо- вой комбинации (6.6) 43 где N – общее количество передаваемых сообщений. L можно представить как где m1 и m2 – соответственно качественные признаки первичного и вторичного алфавитов. Поэтому для цифры 5 в двоичном коде L > log5/log2 = 2,32 дв. симво- ла. Однако эту цифру надо округлить в большую сторону до ближайшего целого числа, так как длина кода не может быть выражена дробным числом. В общем случае избыточность от округления Для нашего примера D0 = (3-2,32)/3 = 0,227. Таким образом, избыточность может быть заложена как в первичном алфа- вите, так и в природе кода, составленного во вторичном алфавите. Избыточность – не всегда нежелательное явление. Для повышения помехо- устойчивости кодов избыточность необходима и ее вводят искусственно в виде добавочных символов. (6.9) Наиболее эффективным способом уменьшения избыточности является по- строение оптимальных кодов. Оптимальными называются коды, которые имеют практически нулевую избыточностью. Оптимальные коды имеют ми- нимальную среднюю длину кодовых слов - L. Верхняя и нижняя границы L оп- ределяются из неравенства 44 где Н – энтропия первичного алфавита, m – число качественных признаков вто- ричного алфавита. Под термином «оптимальный код» понимают коды с практически нулевой избыточностью, так как сравнивают длину кодовой комбинации с энтропией ис- точника сообщений, не учитывая взаимозависимость символов. С учетом взаимо- зависимости символов эффективность кодирования никогда не будет 100%, т.е. При построении оптимальных кодов наибольшее распространение получи- ли методы Шеннона-Фано и Хаффмана. 6.3 Задание Задача 1. Сообщения составляются из алфавита a, b, c, d. Вероятность появ- ления букв в текстах равна соответственно: pa = 0,2; pb = 0,3; pc = 0,4; pd = 0,1. Найти избыточность сообщений, составленных из данного алфавита. Залача 2. Чему равна минимальная длина кодовых слов для передачи 16, 128, 57, 10, 432 сообщений в восьмиричном и в двоичном кодах. Задача 3. Пусть алфавит источника содержит шесть элементов {А, Б, В, Г, Д, Е}, появляющихся с вероятностями Р(А)=0,15, Р(В)=0,1, Р(Б)=0,25, Р(Г)=0,13, Р(Д)=0,25, Р(Е)=0,12. Найти энтропию такого источника, среднее число символов на одну букву при кодировании методом Ш-Ф. Задача 4. Закодировать методом Шеннона-Фано блоки «мы все учились по- немногу чему-нибудь и как-нибудь». Каково среднее число символов на знак? Задача 5. Сообщение состоит из последовательности букв А, B и С, вероят- ности которых не зависят от предыдущего сочетания букв и равны Р(А)=0,7, Р(В)=0,2, Р(С)=0,1. Провести кодирование по алгоритму Шеннона-Фано отдель- 45 ных букв и двухбуквенных сочетаний. Сравнить коды по их эффективности и из- быточности. Задача 6. Закодировать сообщение методом Шеннона-Фано «Теория ин- формацииКодированияМодуляции». Задача 7. Построить код Шеннона-Фано для системы из семи букв: A, B, C, D, E, F, G, вероятности появления которых соответственно 0,1; 0,2; 0,05; 0,3; 0,05; 0,15; 0,15. Определить среднее количество разрядов на одну букву. Декоди- ровать этим кодом последовательность: 10011101001000111101110101111000. 6.4 Контрольные вопросы 1 Что понимают под кодированием сообщения? Приведите примеры про- стейших кодовых сообщений. 2 Дать определение равномерных кодов. Привести пример. 3 Поясните принцип кодирования методом Шеннона-Фано. Привести пример. 4 В чем заключается процесс декодирования сообщения? Привести при- мер. 5 Пояснить сущность понятия «избыточность кода». Дать характеристику видов избыточности. 6 Привести и пояснить формулу для вычисления длины кодовой комби- нации. Привести пример. 7 Поясните за счет чего, обеспечивается сжатие информации при приме- нении эффективного кодирования. 8 Чем определяется минимальная длина кодовой комбинации при приме- нении эффективного кодирования? 9 Что такое оптимальный код? Какой параметр определяет оптимальность кода? Привести пример. 10 В каких случаях избыточность кода является полезным явлением? При- вести примеры. 46 7 Лабораторная работа № 7. Эффективное кодирование. Метод Хаффмана 7.1 Цель работы Освоение кодирования сообщений методом Хаффмана. 7.2 Теоретические сведения Эффективное кодирование – это такой способ кодирования, при котором получается наименьший объем передаваемой информации и избыточность мини- мальна. Для кодирования символов исходного алфавита используются двоичные ко- ды переменной длины: чем больше частота символа, тем короче его код. Эффективность кода определяется средним числом двоичных разрядов для кодирования одного символа. При эффективном кодировании существует предел сжатия, ниже которого не «спускается» ни один метод эффективного кодирования – иначе будет потеряна информация. Этот параметр определяется предельным значением двоичных разрядов возможного эффективного кода (7.1) где n – мощность кодируемого алфавита, fi- частота i-го символа кодируемого ал- фавита. Метод Хаффмана относитсяк методу эффективного кодирования. Если имеются сообщения входного алфавита А {x1, x2,…, xn} c заданными вероятно- стями p1, p2, …, pn. Рассмотрим метод кодирования Хаффмана. 1. Необходимо расположить все сообщения в столбик в порядке убывания вероятностей их появления. 2. Затем два самых маловероятных сообщения объединить в одно y, которое имеет вероятность равную сумме вероятностей события x n-1 , x n т.е., p n-1 + p n . В 47 результате получаются сообщения x1, x2, x n-2 , y вероятности которых p1, p2, p n-2 , p n-1 +p n 3. Необходимо повторять шаги 1 и 2 до тех пор, пока не получится единст- венное сообщение, вероятность которого равна 1. 4. Построить дерево, проводя линии, объединяющие сообщения и образую- щие последовательности подмножества. В этом дереве отдельные сообщения яв- ляются концевыми узлами. Соответствующие им кодовые слова можно опреде- лить, приписывая правым ветвям объединения символ 1, а левым – 0 (или наобо- рот). Пример. Построить код Хаффмана для следующих данных: Решение. Расположим сообщения в столбец в порядке убывания их вероят- ности 48 На основании полученной таблицы можно построить кодовое дерево (риcунок 7.1). Рисунок 7.1 – Кодовое дерево 7.3 Задание Задача 1. 1.Построить код Хаффмана для ансамбля сообщений Определить характеристики кода. Задача 2. Построить код Хаффмана для ансамбля сообщений Определить характеристики эффективного кода. Задача 3. Построить код Хаффмана для ансамбля сообщений Определить характеристики кода и скорость передачи сообщений по каналу при условии, что длительность двоичного символа Сравнить с обычным двоичным кодированием. Задача 4. Закодировать методом Хаффмана блоки «мы все учились понем- ногу чему-нибудь и как-нибудь». 49 Каково среднее число символов на знак? Сравнить с ответом задачи № 4, выпол- ненной по методу Шеннона-Фано. Задача 5. Задан алфавит из трех символов с вероятностями 0,75; 0,1; 0,15. Произвести кодирование отдельных букв и двухбуквенных сочетаний по методу Хаффмана. Для полученных кодов найти средние длины и коэффициенты опти- мальности. 7.4 Контрольные вопросы 1 Поясните назначение и цели эффективного кодирования. 2 Что такое средняя длина кодовой комбинации? Как ее определить? 3 За счет чего при эффективном кодировании уменьшается средняя длина кодовой комбинации? 4 До какого предела может уменьшиться длина кодовой комбинации при эффективном кодировании? 5 При каком распределении букв первичного алфавита оптимальный не- равномерный код оказывается самым эффективным? 6 К какому типу алгоритмов кодирования относится метод Хаффмана, дать пояснение. 7 Приведите пояснение метода Хаффмана на примере. 8 Какая информация необходима для восстановления сообщения, закоди- рованного по методу Хаффмана? 9 Какой код наиболее эффективный: по методу Хаффмана или Шеннона- Фано? Привести пример. 10 Привести случаи, когда метод Хаффмана не способен уменьшить размер данных. 50 Список использованных источников 1 Балюкевич, Э.Л. Основы теории информации: учебно-практическое пособие / Э.Л. Балюкевич. – М.: Евразийский открытый институт, 2008. – 216 с. 2 Задачи кодирования сообщений. Код Шеннона-Фэно. Алгоритм Шеннона – Фано. [Электронный ресурс]. – Режим доступа: https://intellect.ml/18- 8-zadachi-kodirovaniya-soobshhenij-kod-shennona-feno-algoritm-shennona-fano-7001 3 Зверева, Е.Н. Сборник примеров и задач по основам теории информации и кодирования сообщений / Е.Н. Зверева, Е.Г. Лебедько. – СПб: НИУ ИТМО, 2014. – 76 с. 4 Метод сжатия Хаффмана. Кодирование методом Хаффмана. [Электронный ресурс]. – Режим доступа: http://life- prog.ru/view_programmer.php?id=2 5 Кудряшов, Б.Д. Теория информации / Б.Д. Кудряшов - Санкт- Петербург: СПбГУ ИТМО, 2010. - 188 с. 6 Куприянов, А. И. Основы защиты информации: учеб. пособие для вузов / А. И. Куприянов, А. В. Сахаров, В. А. Шевцов.- 3-е изд., стер. - М. : Академия, 2008. - 254 с. 7 Осокин, А.Н. Теория информации: учебное пособие / А.Н. Осокин, А.Н. Мальчуков. Томск: Изд-во Томского политехнического университета, 2014. – 208 с. 8 Фурсов, В.А. Теория информации: учебник / В.А. Фурсов. - Самара: Изд-во Самар.,гос. аэрокосм, ун-та, 2011. - 128 с. 9 Хохлов, Г. И. Основы теории информации: учеб. пособие / Г.И. Хохлов. - М. : Академия, 2008. - 172 с. |