Вернер М. Основы кодирования (2004), страница 9

Найдите энтропию источника.3. Проведите кодирование Хаффмана для блоков, состоящих изтрех двоичных символов.4. Какой эффективностью обладает кодирование?Решение.1. Переходные вероятности рис. 5.9 равнытг(А/А)=0,9 ir{B/A)=0,lтф4/В)=0,3 IT{B/B) = 0,7.(5.106)Стационарное значение вероятности состояния А определяется, исходя из следующих равенствР(А) = 1 - Р{В)Р(А) = 0,9 -Р(А)+ 0,3 -Р{В),поэтому,Р{А) = 0,9 • Р{А) + 0,3 • (1 - Р(А))Р(А)-[1 -0,9 + 0,3] = 0,3Р(А) = 3/4.(5.107)(5.108)Из этого следует, чтоР{В) = 1/4.(5.109)5.5. Кодирование стационарных марковских источниковТаблица 5.2. Кодирование Хаффмана для марковского источника с памятью г = 2 и длиной блока 4.Гимволыpt10019/4100106/4101006/41Кодо вая конструкцияn'nООП3/4111003/4101012/4111102/4111112/41ОНО2/4101112/410O—j 410102/41°-t11011/41°~П210111/411000000000000105510/4111110inn55-5/4111017000010110ют100°°0оно011100°nо1:2зз444444Кодовое слово11'—т.]ji>11Jl__J7I151010111001000101п,Р,18/4118/4]18/4]12/4112/418/418/418/418/4110/415/41--== 4!.!».0.744бит412.

Энтропия источника определяется какН{А)= -0,9 log2 0,9-0,1 log2 0,1 = 0,469битН{В)= -0,71og2 0,7 - 0,31og20,3 = 0,811битНХ(Х) = Р{А) • Н(А) + Р(В) • Н(В) = 0,572 бит.(5.110)3. Вероятности блоков, состоящих из трех двоичных символов, равныР(ААА)Р(ААВ)Р(АВА)Р(АВВ)Р(ВАА)Р(ВАВ)Р(ВВА)Р(ВВВ)= Р(А)= Р(А)= Р(А)= Р(А)= Р(В)= Р(В)= Р{В)= Р(В)-7г(А/А) • ж(А/А) = 0,6075• ж{А/А) • ж{В/А) = 0,0675• ж{В/А) • IT(A/B) = 0,0225• к(В/А) • ж{В/В) = 0,0525• тг{А/В) • -п{А/А) = 0,1225• п(А/В) • тг{В/А) = 0,0525• п(В/В) • п(А/В) = 0,0075• п(В/В) • ж(В/В) = 0,0675.Кодирование Хаффмана представлено на рис. 5.10.(5.111)Глава 5.

Стационарные дискретные источники с памятьюВероятностьБлок состоянияААА0,6075ВВВ 0,1225ААВ0 0675ВАЛ 0,0675ABBКодовоеслово000 0 2425 1,000,39250.120,1510,0825°п 0,03 11010011010100,0525 O-jJ10111110ВВА0,0525ABA0,0225RARППП7Ч11110Рис. 5.10. Кодирование Хаффмана.4. Средняя длина кодового слова определяется какп = 1/3(0,6075 + 3(0,1225 + 0,0675)++ 4(0,0675 + 0,0525 + 0,0525)+(5.112)+ 5(0,0225 + 0,0075)) = 0,6725,следовательно, эффективность кодирования равна•пНж(х)0,572 _п0,6725ос(5.113)5.6.

ВыводыВ приведенных ниже таблицах читатель может найти важнейшиеутверждения и связь марковских цепей и марковских источников.5.6. ВыводыТаблица 5.3. Марковские цепи.Марковским процессом называется стохастический процесс, в котором настоящее известно, а будущее не зависит от прошлого.Дискретный по времени и состояниям марковский процесс называется марковской цепью.

Его реализацией является последовательностьсостоянийS, €S={SI,S2,...,SN].Цепь Маркова является гомогенной, если переходные вероятностимежду состояниями не зависят от выбора временной точки отсчета,следовательно,n(j/i) = P(Sj/Si) для j,i = 0,1,2,3,..., N.• Гомогенная марковская цепь полностью определяется матрицей переходных вероятностей Птг(1/2)7г(2/1)тг(2/2)n(2/N)и начальным распределением• Эквивалентом матрицы переходных вероятностей является 1т>афсостояний с узлами, путями и весом путей, соответствующим состояниям, переходам между состояниями и переходным вероятностямРис. 5.11.• Распределение состояний гомогенной марковской цепи на п -ом шагеопределяется какр„ = р 0 П " .74Глава 5. Стационарные дискретные источники с памятьюТаблица 5.4. Марковские цени, (продолженеие)Гомогенная цепь Маркова стационарна, если распределение состояний постоянно во времени.

В этом случае начальное распределение является собственным вектором переходной матрицы, т.еро = РоП.Гомогенная цепь Маркова регулярна, если существует пределПх= lim П " ,причем, все строки Пос равны предельному распределению рос.Предельное распределение р^ является единственным стационарным распределением регулярной цепи Маркова.Таблица 5.5. Стационарные Марковские источники.Конечный дискретный марковский источник с памятью г полностью определяется следующими условиями:Задано непустое множество состояний S = {Si,S2,...

,SN}, причем, S содержит все векторы длины г;Каждое состояние Si 6 S соответствует дискретному источнику без памяти салфавитом X, = {xi, X2, • • •, хм} и вероятностями jVbix символов алфавитаСостояние S[n] = (х[п — г],х[п — г + 1],... ,х[п — 1]) из г последовательныхсимволов и очередной символ х[п] образуют новое состояние s[n+l] = (х[п —Задано начальное распределение состояний ро = (ро(1),Ро(2),... ,po(N)).Энтропия стационарного марковского источника с памятью г определяетсякак математическое ожидание условных энтропии подисточниковпри этом условная энтропия г-ого подисточника, соответствующего состоянию г равнамH(X\Si) = - £ p S j (x m )log 2 (P S i (x m )) бит.m=lГЛАВА 6СЖАТИЕДАННЫХ6.1.

ВведениеЗадачей сжатия данных является минимизация технических затратна хранение или передачу информации путем оптимального кодирования источников. При этом различают два понятия:• Несущественная информация - это информация, которой можно пренебречь при передаче. Примером может служить традиционная телефония. В телефонных каналах передача информации осуществляется в полосе 3,4 кГц. Все остальные спектральные составляющие отбрасываются, при этом существенная часть передаваемой-информации теряется.

Ясно, что первоначальный речевой сигнал не может быть полностью восстановлен на приемном конце. В этом случае говорят о кодировании с потерями.• Под избыточностью понимают неоднократное повторение в сообщении необходимой для приемника информации. Избыточность может быть устранена без потери информации. Примером является кодирование Хаффмана. Такое кодирование называют кодированием без потерь.Важнейшими примерами сжатия данных являются цифровое радиовещание (Digital Audio Broadcasting, DAB) и цифровое телевидение (Digital Video Broadcasting, DVB)[19]. Обе системы работаютна основе кодирования аудио и видео сигналов, использующего стандарты MPEG (Motion Pictures Experts Group).

Кодирование аудиосигнала основано на психологической модели восприятия речи, которая использует скрытые спектральные и временные эффекты, приэтом в сигнальном блоке происходит удаление невоспринимаемой наслух части аудиосигнала (несущественной информации). Аналогичные эффекты используются также при кодировании видеосигнала (вчастности, психологический эффект движения). Кодирование изображений позволяет достичь еще большей степени сжатия.Глава 6.

Сжатие данныхСтепень сжатия определяется затратами для передачи или хранения информации без сжатия fco и затратами с использованиемнекоторого метода сжатия ктКО — КтG.(6.1)fcoСтепень сжатия зависит от используемого алгоритма и свойств источника. Приведем некоторые численные примеры степеней сжатия,достигаемых на практике :-до 80 % для текстовых данных (в формате редактора Word 97 спомощью программы сжатия ZIP);-87,5 % при переходе от РСМ-телефонии со скоростью 64 кбит/секк передаче информации по рекомендации ITU G.725 со скоростью 8кбит/сек;-90 % при кодировании информации стереофоничских аудио компакт дисков со скоростью 2-16 бит-44 кГц = 1408 кбит/сек методом,использующим стандарт сжатия MPEG (Advanced Audio Coding) соскоростью 112 кбит/сек и почти равнозначным качеством речи.Следующим примером является энтропия немецкого литературного текста.

Результаты частотного анализа представлены на рис.6.1. Если рассматривать буквы изолированно, то получим энтропию,приблизительно равную 4,7 бит/букву. Объединяя буквы в блоки,мы используем уже такие очевидные связи, как слоги, слова и т.д.,поэтому, для блоков очень большой длины асимптотически достижимая граница равна Г, 6 бит/букву.ЭнтропияO—rj4,7 бит/символ1,6 бит/символ-——пв 1Длина блок•+-*•л = 10Р и с .

6.1. Энтропия немецкого литературного языка какфункция длины блокаАлгоритмы сжатияданных можно разделить на три группы:1. Статические алгоритмы, например, кодирование Хаффмана.Сжатие немецкого литературного текста методом Хаффмана,по сравнению с сжатием информации, состоящей из произволь-6.2. Арифметическое кодированиеных стандартных символов ASCII, позволяет достичь приблизительно 50 % выигрыша.2. Адаптивные алгоритмы, например, модифицированное кодирование Хаффмана. Здесь распределение вероятностей символов вначале полагается равномерным, а потом меняется вовремени по мере накопления статистики.3.

Динамические алгоритмы, например кодирование, используемое в рекомендации ITU V42. bis.Основная проблема энтропийного кодирования заключается втом, что оно предполагает знание распределения вероятностей символов. Очень часто статистика символов заранее неизвестна и эффективному кодированию должен предшествовать частотный анализ. Здесь на помощь приходят универсальные алгоритмы.• Универсальные алгоритмы сжатия, являющиеся по своей сути адаптивными, не нуждаются в априорной статистике. Такоеэффективное кодирование начинается сразу же после поступления информации на вход кодера.• Кроме этого, существуют «быстрые» алгоритмы с относительно простой технической сложностью.• Каждый из предполагаемых алгоритмов помогает достичь высокой степени сжатия.В качестве примера методов сжатия, рассмотрим два важнейшихалгоритма: арифметическое кодирование, лри котором производитсядинамический частотный анализ и универсальный алгоритм ЛемпеляЗива.