Лекция 14-15

План лекции Алфавит, кодирование, код Типы кодирования, однозначное декодирование Метод кодирования Хафмана Метод кодирования Фано Элементы теорий вероятностей и информации – лекция 15 Модель информационной системы Шеннона Среднестатистическая информационная емкость сообщений для эргодических источников с заданным распределением частот символов Формулы Шеннона и Хартли для удельной емкости на символ Избыточность кодирования

Алфавитом называется конечное множество символов Сообщением алфавита А называется конечная последовательность символов алфавита А Множество всех сообщений алфавита А обозначается А* Понятие кода

Кодом называется отображение К : Алф 1* > Алф 2*, согласованное с конкатенацией, т.е. удовлетворяющее равенству К(с 1 с 2...сN) = К(с 1) К(с 2)... К(сN) для любого сообщения с 1 с 2...сN из Алф 1* Значение К(с 1 с 2...сN) называется кодом сообщения с 1 с 2...сN Код К : Алф 1* > {0,1}* называется двоичным кодом Понятие кода

Кодированием сообщения называется вычисление кода сообщения Декодированием (дешифровкой) сообщения называется вычисление его прообраза под действием кода Код К называется однозначно декодируемым, если существует обратная функция К -1 Если вычисление К -1 требует большого количества времени, то говорят не о кодировании, а о шифровании Кодирование и декодирование

Алф 1 = {a,b,c,d} Алф 2 = {0,1} К(а) = 0, К(b) = 01, К(с) = 10, К(d) = 1 К -1 ( ) = {addbba, bссс} – прообраз Данный код не является однозначно декодируемым Пример 1

Алф 1 = {a,b,c,d} Алф 2 = {0,1} К(а) = 0, К(b) = 10, К(с) = 110, К(d) = 111 Почему данный код является однозначно декодируемым? Пример 2

Кодовое дерево Кодовым деревом кода К:Алф 1 ->Алф 2 называется такое дерево Т, с рёбрами помеченными символами из Алф 2, что Любой путь из корня Т совпадает с началом кода какого-то символа из Алф 1 Код любого символа из Алф 1 соответствует какому-то пути из корня Т

Пример кодового дерева Алф 1 = {a,b,c,d} Алф 2 = {0,1} К(а) = 0, К(b) = 01, К(с) = 10, К(d) = 1 Почему у сообщения два прообраза? d c b a

Пример кодового дерева Алф 1 = {a,b,c,d} Алф 2 = {0,1} К(а) = 0, К(b) = 10, К(с) = 110, К(d) = 111 Почему у любого сообщения один прообраз? b a d c 1 1

Префиксный код Код К называется префиксным, если для любых двух сообщений U и V код К(U) не является началом (префиксом) кода К(V) и наоборот Свойства префиксного кода В дереве префиксного кода коды всех символов заканчиваются в листьях Префиксный код позволяет выделять коды символов без использования разделителей

Примеры префиксных кодов Пример 1 Алф 1 = {a,b,c,d} Алф 2 = {0,1} К(a) = 00, K(b) = 01, K(c) = 10, K(d) = 11 Как выглядит кодовое дерево этого кода?

Примеры префиксных кодов Пример 2 Алф 1 = {a,b,c,d} Алф 2 = {0,1} К(а) = 0, К(b) = 10, К(с) = 110, К(d) = 111 Как выглядит кодовое дерево этого кода?

Однозначная декодируемость префиксного кода Теорема Любой префиксный код однозначно декодируем Доказательство Пусть К – префиксный код. Докажем, что у кода S=К(R) любого сообщения R ровно один прообраз Индукция по длине L сообщений R База L = 1 R восстанавливается однозначно в силу префиксности К Что было бы, если бы коды двух разных символов являлись бы префиксом S Шаг L > 1 К согласован с конкатенацией ==> найдётся символ с такой, что S = К(с) S' Что бы было бы, если бы такого символа не было бы или бы он был бы не один бы? К префиксный ==> символ с единственный Длина прообраза S' строго меньше длины прообраза S По предположению индукции S' декодируется однозначно

Алф 1 = {a,b,c,d} Алф 2 = {0,1} К(a) = 0, К(b) = 101, К(c) = 110, К(d) = 1110 Рассмотрим сообщение = K(a) = K(c) = K(b) 0 0 = K(a) K(acba) = Пример

Пример азбука Морзе 1840 Alfred Vail по заказу телеграфной компании Samuel F.B. Morse Двоичный (точка, тире) непрефиксный код – почему? Троичный (точка, тире, пауза) префиксный код – почему? Кодовое дерево азбуки Морзе как двоичного кода для латиницы

Понятие оптимального кода Обозначим Δ – множество кодов Алф 1* -> Алф 2* К – какой-то код из Δ R – произвольное сообщение из Алф 1* L(К, R) – длина R после кодирования p х – число вхождений символа c х в R заодно мы пронумеровали символы из Алф 1, х – номер символа с х Длина кода сообщения R есть L(К,R) = p х L (К, c х ) Код К* называется оптимальным для сообщения R в множестве кодов Δ, если L(К*,R) = min { длина(К,R) | K Δ }

Оптимальный двочиный префиксный код Как быстро построить оптимальный двоичный префиксный код для данного сообщения? Использование Сжатие данных при хранении и передаче Устранение избыточности при шифровании данных Алгоритм построения оптимального двоичного префиксного кода , David A. Huffman, Massachusetts Institute of Technology Оптимальный двоичный префиксный код не зависит от порядка символов в сообщении, только от частот отдельных символов Связь с теорией информации

Свойства оптимального двоичного префиксного кода Пусть R -- сообщение в алфавите Алф 1={c1,…,cn} с x входит в R p x раз (х=1,...,n) К* -- оптимальный двоичный префиксный код для R 1. Если p x = L y (К*) Иначе для кода К(с x ) = К*(с y ), К(с y ) = К*(с x ) и К(с) = К*(с) L(K,R) < L(K*,R) 2. Можно занумеровать символы Алф 1 так, чтобы p 1 >=p 2 >=…>=p n и L(K*,с 1 )

Свойства оптимального двоичного префиксного кода 3. Символов с кодом длины L(K*,с n ) (с самым длинным кодом) не менее двух Иначе удалим последний символ в коде с n -- длина L(K*, R) сократится, префиксность K* сохранится 4. Можно перенумеровать символы так, что К*(с n ) = P 0 и К*(с n-1 ) = P 1 и сохранив условие 2 Следует из свойства 3

Свойства оптимального двоичного префиксного кода 5. Оптимальный двоичный префиксный код к* для сообщения r, полученного из сообщения R заменой самого редкого символа с n на с n-1, и К* связаны соотношениями к*( с n-1 ) = удалить из К*( с n-1 ) последний символ К*( с n ) = к*( с n-1 ) 0 К*( с n-1 ) = к*( с n-1 ) 1 К*( с ) = к*( с ) для остальных символов с L(K*,R) = L(k*,r) + p n + p n-1

Построение дерева оптимального префиксного двоичного кода Вход Кратности p1, …, pn вхождений симолов с 1,..., сn в сообщение Выход Дерево оптимального двоичного префиксного кода для сообщения Алгоритм W = {p1(c1), …, pn(cn)} – множество деревьев Левая скобочная запись, кратности в качестве меток вершин пока в W два или более поддеревьев Найти в W деревья T = x(...) и U = y(...) с минимальными метками x и y W = ( W \ {T, U} ) U { (x+y)(T, U) }

кол около колокола o – 7; к – 4; л – 4; пробел – 2; a – 1. Один из вариантов работы алгоритма Множество W До цикла {7(о), 4(к), 4(л), 2(пробел), 1(а) } После шага 1{7(о), 4(к), 4(л), 3(2(пробел), 1(а)) } После шага 2{7(о), 4(к), 7(4(л), 3(2(пробел), 1(а))) } После шага 3{7(о), 11(4(к), 7(4(л), 3(2(пробел), 1(а)))) } После шага 4{18(7(о), 11(4(к), 7(4(л), 3(2(пробел), 1(а))))) } Пример

пробел окла Дерево после шага 1 Дерево после шага 2 ла

к пробел Дерево после шага 4 0 ола

Пример построения кода по кодовому дереву Пометим дуги, исходящие из каждой вершины дерева, единицей и нулем Проходя путь из корня дерева до символа и выписывая все пометки дуг на этом пути, получим код для этого символа В нашем примере коды будут такими о 0, к 10 пробел 1110 л 110 а 1111 Закодированное сообщение Длина закодированного сообщения L = 39

Для разобранного примера можно построить другое дерево Закодированное сообщение длины L = окл пробел а

Теорема Длина кодового слова в оптимальном префиксном двоичном коде ограничена порядковым номером минимального числа Фибоначчи, превосходящего длину входного текста. Доказательство – в качестве упражнения Следствие При кодировании по алгоритму Хаффмана текстов ASCII размером до 11Tб код любого символа короче 64 битов

Алфавит, кодирование, код Типы кодирования, однозначное декодирование Метод кодирования Хафмана Метод кодирования Фано Элементы теорий вероятностей и информации – лекция 15 Модель информационной системы Шеннона Среднестатистическая информационная емкость сообщений для эргодических источников с заданным распределением частот символов Формулы Шеннона и Хартли для удельной емкости на символ Избыточность кодирования

Роберт Марио Фано р Один из первых алгоритмов сжатия на основе префиксного кода Метод Фано

Упорядочим входной алфавит по возрастанию частот p1

K[i][j] заполняем 0 и 1 по след. правилу Для каждого максимального интервала строк [a, b], у которых в столбце j-1 находятся одинаковые цифры Находим с [a, b] такое, что Sc ближе всего к (Sa+Sb)/2 K[i][j] = 1 для i [a, c], K[i][j] = 0 для i [c+1, b] Метод Фано

А = {a, b, c, d, e} Частоты p a = 0.11, p b = 0.15, p c = 0.20, p d = 0.24, p e = ближе к ближе всех к ( )/2= ближе всех к ( )/2= ближе всех к ( )/2=0.13 PiPi SiSi 0 a b c d e Пример

Свойства кода Фано Кодовое дерево для кода Фано обладает следующим свойством Ребра, исходящие из корня, соответствуют разбиению алфавита на две группы символов, близкие по частоте Ребра, исходящие из вершины следующего «этажа», соответствуют разбиению соответствующей группы на близкие по частоте подгруппы и т. д. Код Фано – префиксный код Почему?

Свойства кода Фано Код Фано неоптимальный Пример Частоты p1=0.4, p2=p3=p4=p5=0.15 Фано: средняя длина кодового слова 2*0.4+(2+2)*0.15+(3+3)*0.15 = 2.3 Хаффман: средняя длина кодового слова 1*0.4+ ( )*0.15 = 2.2 Как выглядят кодовые деревья кода Хаффмана т Фано?

Клод Шеннон 1916 – 2001, основоположник теории информации 1. Упорядочим входные символы по возрастанию частот и образуем частичные суммы Sk как в методе Фано 2. Для каждой частоты pk находим nk т.ч. 1/2^nk pk 2/2^nk 3. Sk разлагаем в двочную дробь 0. d 1 d 2 d 3 …. 4. Первые nk цифр этой дроби задают код для k-го символа Метод Шеннона

nk разложение Skкод p(a) = 0.08 S a = p(b) = 0.12 S b = p(c) = 0.15 S c = p(d) = 0.28 S d = p(e) = 0.37 S d = Пример вычисления na: 0.08 ~= 1/12; 1/2^4 1/12 2/2^4 Пример построения кода Шеннона

Код Шеннона -- префиксный код Почему? Пусть pk – частота вхождения k-го символа в кодируемое сообщение длины N. Кодирование такого сообщения кодом Шеннона дает сообщение длины не более N*(p1*log2(p1) + p2*log2(p2) + … + pn*log2(pn)) Почему? Как Шеннон выбрал длины кодовых слов? Свойства кода Шеннона

Лекция 15

The Bell System Technical Journal Vol. 27, pp. 379–423, 623–656, July, October, 1948 Имеются источник (кодер) и приемник (декодер) Они связаны между собой каналом передачи символов Символы – пример дискретного сигнала Канал не искажает и не теряет символы Какой нужен канал, чтобы передать данное сообщение (последовательность символов) за данное время? За какое время можно передать данное сообщение по данному каналу? За какое время нельзя передать данное сообщение по данному каналу без потерь? Шеннон исследовал также передачу непрерывного сигнала и передачу с шумом Информационная модель Клода Шеннона

Каким должен быть канал, чтобы передать данное сообщение за данное время? За какое время можно передать данное сообщение по данному каналу? Как измерять пропускную способность канала? Если передача всех символов занимает одинаковое время, то используем символы в секунду Как быть, если передача разных символов занимает разное время? Информационная модель Клода Шеннона

Как измерять пропускную способность канала? Если передача всех символов занимает одинаковое время, то можно использовать символы в секунду Как быть, если передача разных символов занимает разное время? Пусть N(T) – число допустимых сообщений, передача которых занимает время T Пропускная способность = предел log2(N(T))/T при Т --> oo Выбор log2 обусловлен математическим и интуитивным удобством Если появляется возможность передавать за время T на один двоичный символ больше, то N(T) возрастает в два раза Пропускная способность – на 1/Т Без скорость, вычисленная без log2, увеличилась бы в два раза Информационная модель Клода Шеннона

За какое время нельзя передать данное сообщение по данному каналу без потерь? Как понять, что источник порождает больше Как измерить скорость, с которой источник порождает информацию? В общем случае – каково минимальное число 0 и 1, необходимых для однозначного восстановления сообщения с помощью подходящего алгоритма -- алгоритмическая сложность Коломогорова – алгоритмически невычислимая величина для произвольных сообщений Информационная модель Клода Шеннона

Как измерить скорость, с которой источник порождает информацию? В процессе передачи сообщения источник "помогает" приемнику выбрать один из символов При условии наличия у приемника и источника общего знания о передаваемом сообщении Какое количество "выбора" содержится в каждом символе? Шеннон рассмотрел случай, когда известны только частоты отдельных символов p1, p2, …, pn Информационная модель Клода Шеннона

Для случая, когда приемник и передатчик знают только частоты отдельных символов p1, p2, …, pn, Шеннон сформулировал три требования к количеству "выбора" H(p1, p2, …, pn) 1. H должна быть непрерывна по pk 2. Значение H(1/n, 1/n, …, 1/n) должна возрастать по числу символов n 3. H(p1, p2, …, pn) = H(p1,..., p n-1 +pn) + (p n-1 +pn)H(p n-1 /(p n- 1 +pn), pn/(p n-1 +pn)) H(1/2,1/3,1/6) = H(1/2,1/2)+1/2H(2/3,1/3) Информационная модель Клода Шеннона

Теорема Все функции, удовлетворяющие условиям 1-3, имеют вид H = - c pk log(pk) Информационная модель Клода Шеннона

Будем говорить, что источник передал приемнику некоторую информацию о происшедшем событии, на основании которой изменилось представление приемника о множестве возможных исходов наблюдаемой величины. Определим количество информации, содержащейся в сообщении т, изменяющем представление приемника о событии с S ДO до S П0CЛЕ по формуле Единицей количества информации является бит. (2)

Пример 1 В семье должен родиться ребенок. Пространство элементарных исходов данной случайной величины {мальчик, девочка}, состоит из двух исходов. Отсутствие априорной информации у приемника (родителей) о поле малыша означает, что S ДO совпадает с этим пространством. Сообщение источника (врача) «у вас родился мальчик» сужает это множество предположений до множества S П0CЛЕ из единственного исхода мальчик. По формуле (12) количество полученной информации определяется как I(m)= -log 2 -log 2 == 1(бит).

log 2 2 = 1 – ? - 1 бит соответствует сообщению о том, что произошло одно из двух равновероятных событий; - требуется один бит для хранения сообщений о двух равновероятных событиях.

Пример 2 Из колоды вытягивается карта. Пространство элементарных исходов 52 карты. В отсутствие изначальной информации пространство предположений S ДO_1 совпадает со всем пространством. Первое сообщение от источника «выпала трефа» сужает его до S ПОСЛЕ_1 из 13 возможных исходов. Второе сообщение «выпала картинка» сужает S ДO_2 =S П0CЛЕ_1 до S П0CЛЕ состоящего из 4 исходов. Третье сообщение «выпала дама треф» сужает S ДO_3 = S П0CЛЕ_3 до S П0CЛЕ_3, состоящего из единственного исхода. Количество информации, содержащееся в первом сообщении равно -log 2 13/52= 2 битам, во втором -log 2 4/13 = 1.5, в третьем -log 2 1/4 = 2 битам. Нетрудно проверить, что суммарное количество полученной информации 5.5 бит, совпадает с количеством информации, которое несло бы сообщение «выпала дама треф» = -log 2 1/52 = 5.5 бит.

Теорема об аддитивности информации Теорема Количество информации, переносимое сообщением m1 && m2 && … && mN, не зависит от порядка отдельных сообщений и равно сумме количеств информации, переносимых сообщениями m1, …, mN по отдельности. Выберем какой-либо порядок передачи сообщений I(W, m1) = log2(P(m1)/P(W)) I(m1, m1&&m2) = log2(P(m1&&m2)/P(m1)) I(m1 && m2 && … && m_N-1, m1 && m2 && … && mN) = log2(P(m1&&…&&mN)/P(m1&&…m_N-1)) Пример о двух источниках: 1 – p(что грань 5)=1; log P после /P до = log 1/1 =0; 2 – p(что грань 5)=1/6; log P после /P до = log 1/1/6 = log 6 2,5 бит. Свойства информации: количество полученной приемником информации зависит от его предварительного знания о событии; количество информации зависит не от события, а от сообщения о нем.

Предположим теперь, что источник является генератором символов из некоторого множества {х 1, х 2,...,х n } (назовем его алфавитом источника). Эти символы могут служить для обозначения каких-то элементарных событий, происходящих в области источника, но, абстрагируясь от них, в дальнейшем будем считать, что рассматриваемым событием является поступление в канал самих символов. Если p(х i ) вероятность поступления в канал символа х i, то Формулы Шеннона, Хартли

Рассмотрим теперь модель, в которой элементарным исходом является текстовое сообщение. Таким образом, Ω это множество всех цепочек символов произвольной длины. По поступившему сообщению т можно посчитать экспериментальную частоту встречаемости в нем каждого символа, где N общая длина сообщения, а n i число повторений в нем символа x i.

Понятно, что анализируя различные сообщения, мы будем получать различные экспериментальные частоты символов, но для источников, характеризующихся закономерностью выдачи символов (их называют эргодическими), оказывается, что в достаточно длинных сообщениях все частоты символов сходятся к некоторым устойчивым величинам которые можно рассматривать как распределение вероятностей выдачи символов данным источником. (4)

Рассмотрим сообщение m, состоящее из n 1 символов x 1, n 2 символов x 2 и т. д. в произвольном порядке, как серию элементарных событий, состоящих в выдаче одиночных символов. Тогда вероятность появления на выходе источника сообщения m равна

Количество информации, переносимой сообщением т длины N, определяется как Количество информации, приходящейся в среднем на каждый символ в сообщении m, есть где N длина сообщения m.

Формула Шеннона Перейдем к пределу по длине всевозможных сообщений (N > ): По формуле (14), вспоминая, что в достаточно большом сообщении p(x i ) = lim N->, получаем (5)

Формула Хартли Величина I 0 (A) характеризует среднее количество информации на один символ из алфавита А с заданным (или экспериментально определенным) распределением вероятностей р(х 1 ), р(х 2 ),..., р(х N ). Рассмотрим случай, когда все символы в алфавите равновероятны: р(х 1) = р(х 2)... = р(х N ) = 1/N. Среднее количество информации, приходящееся на каждый символ такого алфавита, по формуле Шеннона (6)

Событие, которое может произойти или нет, называют случайным. Примеры: попадание стрелка в мишень, извлечение дамы пик из колоды карт, выигрыш билета в розыгрыше лотереи и т. д. На основании отдельно взятого случайного события нельзя научно предсказать, например, какие билеты окажутся выигрышными. Но если провести достаточно большую последовательность испытаний, то можно выявить определенные закономерности, позволяющие делать количественные предсказания.

Определение Пространство элементарных событий (исходов) Ω – множество всех различных событий, возможных при проведении эксперимента. Элементарность исходов понимается в том смысле, что ни один из них не рассматривается как сочетание других событий.

Примеры: 1) Будем бросать монету до тех пор, пока не выпадет герб. После этого эксперимент закончим. «Элементарный исход» этого эксперимента можно представить в виде последовательности р, р, р,..., р, г (где р решка, г герб). Таких последовательностей бесконечно много. Следовательно, в данном случае множество Ω бесконечно. 2) Однократное бросание игральной кости. Будем считать, что возможен только один из 6 исходов, соответствующих падению кости гранями с 1, 2,...,6 очками вверх. Каждый возможный исход удобно обозначать числом выпавших очков. Тогда пространство элементарных событий Ω = {1,2,3,4,5,6}.

Формула ω Ω означает, что элементарное событие ω является элементом пространства Ω. Многие события естественно описывать множествами, составленными из элементарных исходов. Например, событие, состоящее в появлении четного числа очков, описывается множеством S = {2,4,6}. Формула S Ω означает, что событие S является подмножеством пространства Ω. Случайная величина > переменная Элементарный исход > значение переменной Пространство элементарных исходов > область значений Событие > подмножество области значений

Определим формально меру события µ, как отображение из пространства Ω в N, обладающее следующими свойствами: 1) где - пустое множество, т.е. множество, не содержащее ни одного элемента; 2) 3) mu(S1 U S2)=mu(S1)+mu(S2)-mu(S1/\S2)

Введем функцию p(S) вероятности события как численного выражения возможности события S на заданном пространстве элементарных исходов Ω следующим образом: (1) «Желательные» исходы - элементарные исходы, образующие событие S. 0 p(S) 1 р(0) = 0, р(Ω) = 1. Событие с вероятностью 1 содержит все элементарные исходы и, следовательно, происходит наверняка. Событие с вероятностью 0 не содержит ни одного исхода, следовательно, не происходит никогда. Число желательных исходов Число всех возможных исходов

Говорят, что заданы вероятности элементарных событий, если на Ω задана неотрицательная числовая функция p такая, что:

Вероятность того, что при бросании кости выпадет единица, равна Вероятность появления четного числа очков равна Паскаль в письмах к Ферма в 1654 г. писал: «Как велика вероятность, что когда я проснусь ночью и посмотрю на часы, то большая стрелка будет стоять между 15 и 20 минутами?» И в этом же письме приводит рассуждения о том, что вероятность того, что стрелка часов будет находиться в этом промежутке, равна 5/60=1/12.

Теорема о сложении вероятностей Если пересечение событий А и В непусто, то р(А U В) = р(А) + р(В) - р(А В). ( Это следует из аксиомы 3 для меры. ) Пример. Найдем вероятность того, что вытащенная из полной колоды карта окажется пикой или картинкой. Пусть событию А соответствует извлечение из колоды карт пики, событию В картинки. Для каждой карты из колоды вероятность вытащить ее равна 1/52. Число пик в полной колоде равно 13. Следовательно, вероятность события А равна 13/52=1/4. Число картинок равно 16, вероятность события В равна 16/52 = 4/13. События А и В имеют непустое пересечение. Множество АВ cостоит из четырех элементов,следовательно, р(А В) = 4/52 = 1/13. р(А U В) = р(А) + р(В) - р(А В =1/4+4/13-1/13=25/52. Вероятность того, что вытащенная из полной колоды карта окажется пикой или червой равна равна 1/4 + 1/4 = 1/2.

Теорема об умножении вероятностей Рассмотрим теперь серию экспериментов, в которой некоторая случайная величина наблюдается последовательно несколько раз. Последовательные события называются независимыми, если наступление каждого из них не связано ни с каким из других. Например, исходы при бросании кости являются независимыми событиями, а последовательные вытягивания карт из одной и той же колоды без возврата нет. Теорема. Вероятность того, что независимые события S1, S2 произойдут в одной серии испытаний, равна произведению вероятностей событий S1 и S2. Вероятность того, что обе монеты упадут гербом вверх равна 1/2 * 1/ 2 = 1/4.

Определим формально меру события µ, как отображение из пространства Ω в N, обладающее следующими свойствами:

КОНЕЦ ЛЕКЦИИ

Избыточность кодирования Оказывается, что величина I 0 (А) определяет предел сжимаемости кода: никакой двоичный код не может иметь среднюю длину меньшую, чем I 0, в противном случае можно было бы передать некоторое количество информации меньшим числом битов, что невозможно. Таким образом, любой код может быть лишь в большей или меньшей степени избыточным. Относительная избыточность кода характеризуется как отношение числа «избыточных» битов в коде к общей длине кода, то избыточное число битов есть LN * I 0 (A), (сообщение из N символов алфавита А с информационной емкостью I 0 (A), код длины L битов) а удельная избыточность каждого символа кода: (7)

Заметив, что lim N-> L/N - есть средняя длина кодового слова K 0 (A), получим независимое от сообщения соотношение для избыточности кода: Z(K) = 1 – I 0 (A)/K 0 (A). Оптимальный код с нулевой избыточностью является код со средней длиной кодового слова K 0 = I 0 (A) битов или наиболее близкий к нему. Резюме. I 0 (А) показывает, какое в среднем количество двоичных символов нужно для записи всех кодовых слов алфавита А при произвольном кодировании «символ > слово». Для алфавитов с равновероятными символами формула Хартли определяет минимальную необходимую длину кодового слова, например для алфавита ASCII: I 0 (ASCII) = Iog = 8 бит. Таким образом, любой 8-битный код для ASCII будет оптимальным.

Посчитаем информационную емкость кода: длина исходного сообщения N = 18, длина кода L = 39 битов. Удельная информационная емкость алфавита А с распределением Р есть Избыточность кода

Реализация проекта Архиватор должен вызываться из командной строки, формат вызова: harc.exe –[axdlt] arc[.ext] file_1 file_2 … file_n Поддерживаемые операции: a- поместить файл(ы) в архив; x - извлечь файл(ы) из архива; d - удалить файл(ы) из архива; l - вывести информацию о файлах, хранящихся в архиве; t - проверить целостность архива.

Проверка целостности архива _stat, _wstat, _stati64, _wstati64 int _stat(const char* path, struct _stat *buffer); #include CRC32 – проверка контрольных сумм

Построение дерева Хаффмана Вход: A – исходный набор символов, P= - распределение их частот; – W 0 = {,..., } (начальный набор свободных узлов соответствует встречающимся символам); – цикл по i от 0 до N-1 W i = Шаг_построения(W i-1 ); Выход: Дерево Хаффмана, построенное в цикле с корневым узлом, содержащимся в W N.

Алгоритм: 1. Определить алфавит А = { с 1, с 2,..., с n } сообщения S и подсчитать число вхождений p 1, p 2,..., p n в S 2. Построить дерево оптимального префиксного двоичного кода для S используя свойства 1-8 оптимального кода – полученный префиксный двоичный код называется кодом Хаффмана (1951, David A. Huffman, Massachusetts Institute of Technology) 3. Закодировать сообщение S используя код Хаффмана Код Хаффмана

Критерии качества кодирования: минимальная длина кода; однозначное декодирование.

Пусть в области источника происходит наблюдение за некоторой случайной величиной. Приемник может иметь некоторое априорное представление о множестве S до возможных исходов этой величины до того, как произошло наблюдение. Когда ничего не известно заранее, S до принимается за все пространство возможных исходов Ω. Источник передает приемнику сообщение о произошедшем наблюдении, после получения которого множество предположительных исходов у приемника сужается до S П0CЛЕ. Это представление будем называть апостериорным. Информационная модель Клода Шеннона