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

Для состояния Si имеемHi (X/Z = Si) = 0 бит.(5.97)Так как подисточник 2 постоянно вырабатывает символ «1», энтропия в состоянии S2 равнаH2{X/Z = S2) = 1 бит.(5.98)Подисточники 3 и 4 обладают энтропией соответственно-I Iog 2 J«0,918(5.99)В результате получаем энтропию источника с г = 2, равную4г=1= — ( 8 + 12-0,918+ 12-0,811) бит « 0,701 бит.41(5.101)Итак, мы видим, что по сравнению с марковским источником с памятью г = 1, энтропия уменьшилась.5.5.

Кодирование стационарных марковскихисточниковПрежде всего напомним теорему кодирования источников, сформулированную в теореме 5.2.1. В этой теореме рассматриваются блоки,содержащие L символов. Теорема утверждает, что в случае, когдаL стремится к бесконечности, для блоков длины L существует префиксный код, в котором средняя длина кодового слова на один символ как угодно близка к совместной энтропии Hi(X).В случае марковского источника с памятью г, совместная энтропия для блока длины L = г является предельным случаем и теоремакодирования может быть сформулированна следующим образом:Глава 5.

Стационарные дискретные источника с памятьюТеорема 5.5.1. Теорема кодирования стационарных марковских источников с памятью г и энтропией Н^х).Для блока длины L > г существует D-ичный префиксный код, вкотором средняя длина кодового слова п удовлетворяет неравенствуLИз разложения марковского источника на иодисточники без памяти непосредственно вытекает стратегия оптимального кодирования.Если начальные состояния известны, то при кодировании источников все последующие состояния однозначно определены. При этомв передатчике и приемнике для каждого множества нодисточниковвозможно провести кодирование и декодирование Хаффмана, учитывая распределение вероятностей символов и состояний.Практическая реализация кодов Хаффмана показывает, что длядостижения существенного кодового выигрыша, необходимо кодировать блоки достаточно большой длины. Кроме этого, базовые состояния всегда должны определяться г символами для того, чтобыпереход к блокам большей длины был относительно несложным.Предлагаемая простая стратегия полностью учитывает памятьисточника и, следовательно, в предельном случае, позволяет получить оптимальный префиксный код.Кодирование стационарного марковского источника X с памятью г и энтропией, равной Н^Х).1.

Объединить в блоки / = г + 1 символов источника.2. Провести кодирование Хаффмана для блоков.3. Если средняя длина кодового слова на символ существенно отличается от энтропии НЖ(Х), то увеличить длину блока за счетпоследующих символов. Провести кодирование Хаффмана дляблоков большей длины. Продолжить этот процесс до удовлетворительного приближения средней длины кодового слова кэнтропии.Пример: Кодирование марковского источника с памятью г = 2(продолжение).Проверим эффективность предложенного алгоритма на численном примере из предыдущего раздела.5.5. Кодирование стационарных марковских источниковВ соответствии с памятью источника г = 2, объединим в блокикаждые три символа источника и проведем кодирование Хаффмана.Необходимые вероятности состояний для блоков определяютсястационарным распределением вероятностей (5.58) и матрицей переходных вероятностей (5.58) или графом состояний (рис.

5.7). Вероятность блока 001, например, равнаРш = -P(SI)TT(3/1) = Роо(1)тг(3/1) = 9/41 • 1 = 1-.(5.103)Можно так же заметить, что блок 000 никогда не появляется и, следовательно, не должен кодироваться.Из таблицы 5.1. находим, что средняя длина кодового слова насимвол равна 0,911.

Поэтому эффективность кодирования относительно малаПутем построения блоков большей длины, эффективность кодирования может быть существенно повышена. Повторим кодированиеХаффмана для блоков, длина которых равна 4 (табл. 5.2). Из таблицы 5.1. следует, что средняя длина кодового слова на символ равна0, 744. Эффективность кодирования уже равна4Яоо(ж)0,701= -П~ * 0 ^ 4 " ° ' 9 4(5105)и мы, в основном, реализовали большую часть возможностей кодирования, однако, дальнейшим увеличением длины блока можно увеличить выигрыш от кодирования.Пример: Марковский источник первого порядка.На рис. 5.9 задан граф состояний марковского источника первогопорядка.1.

Дополните недостающие вероятности рис. 5.9 и найдите стационарное распределение вероятностей состояний.Р и с . 5.9. Граф состояний марковского источника первогопорядка.Глава 5. Стационарные дискретные источники с памятьюТаблица 5.1. Кодирование Хаффмана для марковского источника с памятью г = 2 и длиной блока 3.Символы Pi0019/411009/410108/411104/411114/41Oil4/411013/410000Кодовая конструкцияКодовое словоо0о000OfliL170i1518°1 711л,"iPi00218/4110218/41010324/41по312/41111312/41оно416/410111412/41л _ 1 112_бит" 3 41 ~0,9112.

Найдите энтропию источника.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 кГц. Все остальные спектральные составляющие отбрасываются, при этом существенная часть передаваемой-информации теряется. Ясно, что первоначальный речевой сигнал не может быть полностью восстановлен на приемном конце. В этом случае говорят о кодировании с потерями.• Под избыточностью понимают неоднократное повторение в сообщении необходимой для приемника информации.