kantrium.com | E-Norway.ru | HELFI.ru | MySuomi.com

2. Введение в теорию информации

 

Введение в теорию информации

 

2.1. Количество информации

Информация — это знание чего-то, причем вопрос, является ли это "что-то" истинным — оставим для философов. В нашем случае мы будем иметь дел( просто с сообщениями, составленными из одного или нескольких символов То, что создает эти сообщения, называется источником. Первая попытка ма Тематически определить количество того, что, по предположению, являете: Информацие была предпринята Хартли (Hartley) в 1928 году. Его подхо, [Состоял в следующем. Пусть источник производит одиночный символ, на Пример, s, который входит в состав полного набора возможных символьны: значений {si sn}. Пусть информация, задаваемая этим символом, буде обозначена как i1. Если источник производит l символов, то, интуитивно, результирующая информация должно быть равна l x i1 Хартли связал количе ство информации с числом возможных выходов, так как он чувствовал, чт чем больше у источника таких выходов, тем больше информации передаете в форме знания того, что произошло. Одиночный символ может иметь n возможных значений, а если у нас l таких символов, то получаем nl возможных комбинаций. Если мы говорим, что информация — это функция числа возможных выходов, то мы имеем

pic12

Единственная функция, которая удовлетворяет оооим этим уравнениям,— это логарифм, так что Хартли определил меру информации источника с п различными символами как /= logw. Чаще всего используются логарифмы с основанием 2, которые дают единицу измерения информации, называемую бит, хотя существует и другая единица — наш (nat), когда вместо двоичных используются натуральные логарифмы (с основанием ё). Единица бит означает, что информация, задаваемая / двоичными символами, равна

pic13

где P(S) — вероятность появления одного символа, а все символы равновероятны.Это довольно простое определение, но оно справедливо только тогда, когда все сообщения равновероятны. Однако обычно это не так. Поскольку интуитивно информация зависит от вероятности, то для уточнения этого определения мы должны использовать концепцию вероятности. Если событие является очрнь вероятным или не очень, то, как правило, мы можем предсказать, каков будет результат. Это также означает, что количество информации, содержащейся в фактически известном результате, уменьшается. Чтобы подойти к уточненному математическому представлению информации, которая учитывает вероятностный фактор, мы должны слегка изменить наш взгляд на нее. Вместо того чтобы говорить, что информация — это знание, мы говорим, что информация—уменьшение (снятие) неопределенности. Существует четкая методика измерения неопределенности — теория вероятности. Если мы определим меру неопределенности, то сможем использовать ее для определения информации. Этот подход был использован Шенноном в 1948 году.Мера неопределенности (обозначим ее как Н(х)) должна иметь следующие свойства:

  • если два эксперимента имеют равновероятные результаты, то тот эксперимент, у которого больше возможных значений, имеет большую неопределенность, т. е. Н(x1) > Н(х2), если эксперимент х1 имеет больше равновероятных  результатов, чем x2-  Например,  неопределенность  при бросании игральной кости (6 возможностей, каждая с вероятностью 1/6) больше, чем при бросании монеты (2 возможности, с вероятностями 1/2). Обратите внимание— последний случай соответствует неопределенности в определении информации Хартли;
  • сли имеются два независимых эксперимента, неопределенность относительно результатов обоих экспериментов должна быть равна сумме неопределенностей результатов каждого индивидуального эксперимента;
  • если результаты эксперимента разделены на две группы, то неопределенность всего эксперимента должна быть равна сумме неопределенностей каждой из групп, взвешенных вероятностями соответствующих групп.

Два первых свойства требуют чтобы как, и прежде мера Н(х) была основана На логарифмах. Третье свойство потребовало от Шеннона добавления вероятностных множителей. Он определил неопределенность, или энтропию случайного события (величины) X, которое может иметь п возможных результате (значений), получаемых в результате экспериментов с вероятностями р1,...,pn  как

pic14

Энтропия, которая является неопределенностью события X, имеет следующие свойства:

  • она максимальна, когда каждый возможный результат равновероятен;
  • упорядочивание различных вероятностей не имеет значения;
  • энтропия равняется нулю только тогда, когда нет никакой неопределенности (то есть когда вероятность каждого из результатов равна 1);
  • добавление события с вероятностью 0 к набору возможных значений случайной величины не изменяет энтропию;
  • энтропия увеличивается с числом возможных экспериментальных результатов (число событий, бросков игральной кости имеет больше энтропии, чем число бросков монеты);
  • энтропия является непрерывной функцией ее аргументов;
  • энтропия двух независимых событий равна сумме энтропии индивидуальных событий;
  • если набор возможных результатов экспериментов разбить на группы, то для получения результирующей энтропии нужно значения энтропии ин-дивидуальных групп умножить на их статистические веса.

Некоторые из этих свойств показаны на рис. 2.1, где изображена энтропия Двоичного случайного события (имеющего только два возможных значения), кЬк функция вероятностей. Она имеет максимум, равный 0,5, в точке р = 0,5 (в этой точке одинаково вероятно, что событие произойдет, как и то, что оно не произойдет). Кроме того, видно, что энтропия равна нулю как для события, происходящего всегда (р = 1), так и для события, не происходящего никогда (р = 0).

Энтропия и информация связаны следующим образом:

pic15

 

2.2. Взаимная информация

Итак, информация— это уменьшение (снятие) неопределенности. Отсюда следует, что, строго говоря, когда речь заходит об информации, необходимо рассматривать два события: одно "исходное", рассматриваемое перед получением информации, и другое "предначертанное", рассматриваемое после того как информация получена (предполагается, что второе событие дает информацию о первом). Иначе говоря, насколько меньшую неопределенность мы получим относительно первого события, получив определенные знания о втором. Термин взаимная информация часто используется для того чтобы подчеркнуть, что требуется рассматривать два события.Рассмотрим два событиями Y. Информация обX, передаваемая событием Y, равна I(Х;Y)=H{X)- Н(Х|Y). H(Х)— это неопределенность события X. H(X|Y) — неопределенность события X при условии, что Y— известно, и то, насколько меньше становится эта неопределенность по сравнению с первоначальной, когда происходит событие Y и определяет их взаимную информг цию. Если X и Y независимы, то H(Х|Y) = H(Х), так что I(X; Y)=0, и Y не дает никакой информации об X. Обратите внимание, что I(X; Y) = I(Y; X). Эти соотношения показаны графически на рис. 2.2.

pic16

 

2.3. Источники информации

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

pic17

Строка символов, произведенная таким источником S1...Sm где все символы принадлежат одному и тому же распределению вероятностей. Энтропи этого источника определяется как

pic18

где сумма берется по всем к и рк > 0. Набор допустимых символов называете алфавитом.

Бросание монеты или игральной кости формирует источник без памяти, т.е. каждый бросок не зависит от предыдущих. Если имеется некоторая зависмость от предыдущих результатов, то говорят, что источник имеет память.

Большинство реальных источников имеют память. Например, символы на странице имеют память, потому что они не независимы. Так за буквой "q" (английском языке) почти всегда будет следовать буква "u". Источники с памятью — это обычно не индивидуальные символы, а скорее группы символов, которые формируют различные сообщения. Каждая буква английского языка — это символ, но только некоторые группы символов формируют правильные (допустимые) комбинации выходов источника. Энтропия такого источника рассчитывается по сообщениям, а не по символам. Если некоторые из возможных комбинаций символов не формируют правильных сообщений, то говорят, что они избыточны (например, "thear").

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

 

2.4. Кодирование

Источники обычно не производят индивидуальных сообщений в удобной форме. Разговорный язык, например, состоит из нескольких сотен тысяч слов (в случае английского языка — из многих миллионов слов), и иметь отдельный символ для каждого из них непрактично. Решение состоит в том, чтобы отображать сообщения на более управляемый набор кодовых символов (значений). Этот процесс называется кодированием.

Алфавит кода может быть тем же самым или отличным от исходного алфавита. Часто, но не обязательно, это двоичный алфавит.

 

2.4.1. Свойства кодов

Код называют разборчивым (distinct), если все кодовые слова различны. Код называют однозначно дешифруемым (uniquely decipherable), если любая конечная строка из закодированной строки соответствует по крайней мере одному сообщению.

Код называют моментальным (instantaneous), или префиксно-свободным (prefix-free), если никакое кодовое слово не является префиксом какого-либо другого кодового слова, что делает код также и однозначно дешифруемым.

Для проектирования кодов можно использовать так называемое дерево решений.

Необходимым и достаточным условием моментального кода является неравенство Крафта. Оно утверждает, что для моментального кода сумма размеров алфавита D в степени индивидуальных длин слов li, должна быть меньше или равна pic19 . Для однозначно дешифруемого кода такое жеусловие определяется неравенством Макмиллана, так что однозначно дешифруемый код существует только тогда, когда существует также и мгновенный код. Это неравенство часто называют неравенством Крафта-Макмиллана.

pic20

Рис. 2.3. Кодовое дерево

 

Для проектирования кода можно использовать кодовое дерево (рис. 2.3). Начинаясь в корне, дерево разветвляется для каждого возможного кодового Символа. Каждый узел в дереве соответствует набору кодовых символов и, Следовательно, возможному кодовому слову. Код является однозначно дешифруемым, если каждый исходный символ представлен отдельным узлом. Код является моментальным, если каждый исходный символ представлен конечным узлом (то есть листом) дерева. На рис. 2.3 узел А — корневой. Моментальный код может быть сформирован из узлов В, F, G, J, К, L и М Или их подмножеств. На рисунке показаны коды 0, 100, 101, 1100, 1101 и 1111. Если бы не было одного из промежуточных узлов (скажем, D), то при Удалении нижележащих кодовых слов этого узла (F и G, например) код перестал бы быть моментальным. Моментальный код можно расширять с приведением его к форме нового мгновенного кода, только путем добавления к промежуточному узлу концевых узлов. Добавление узла D прибавляет к коду D — 1 новых кодовых слов (так как добавляется D новых концевых вершин, а Исходный узел больше не может использоваться в качестве кодового слова, потому что он больше не является концевым).

 

2.4.2. Минимальные разрядности кода

Если источник (без памяти) имеет энтропию Н, то любой однозначно дешифруемый код для этого источника с алфавитом из D символов должен иметь длину (разрядность) по меньшей мере Н|logD(= Lmin), и существует код с длиной <=(l + H|logD). Это утверждение называется теоремой помехоустойчивого кодирования, потому что она определяет самый короткий возможный код, который полностью описывает источник (и поэтому не производит никаких искажений или шума). Для частного случая двоичных кодов длина должна быть больше или равна энтропии в битах.

 

2.4.3. Избыточность и эффективность

Избыточность кода определяется как относительная разность между средней и минимальной длиной кодовых слов, т. е. как

pic21

Близко связанным понятием является эффективность кода (обозначается как η), которая определяется как Lmin/Lcp и обычно выражается в процентах. Обратите внимание, что избыточность кода равна 1 - n, и если код имеет эффективность 100%, то у него нет никакой избыточности. Для случая двоичного кода Lmin = Н, так что можно упростить эти уравнения:избыточность= (Lcp - H/Lcp, η) = H/Lcp.

 

2.4.4. Типы кодирования

Существует четыре типа кодирования, хотя многие авторы говорят только о трех. Математики обычно забывают кодирование линии передачи, в то время как инженеры-электронщики имеют тенденцию забывать криптографическое кодирование.

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

 

2.5. Кодирование источника

Если мы хотим эффективно передавать информацию, то для того чтобы сохранять низкую среднюю длину сообщения, нужно кодировать наиболее вероятные сообщения с помощью коротких кодовых слов. Когда мы знаем исходные характеристики источника, очень полезными оказываются стратегии кодирования Шеннона-Фано и Хаффмана. Когда мы не знаем характеристик источника, можно использовать другие методики, такие как групповое кодирование (run length encoding), используемое в факсимильной связи, и кодирование Лемпеля-Зива (Lempel-Ziv coding), используемое в архиваторax pkzip, и т. д.

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

 

2.5.1. Квантование

Чтобы было возможно передавать сигнал, находящийся в аналоговой форме, Содержащиеся в нем данные необходимо некоторым образом обработать — оцифровать. Например, измерения расстояний — неизбежно аналоговые, но для передачи их обычно оцифровывают. Ширина монеты в один пенни — 20,20... мм, является бесконечным дробным числом, но стоит только это число ограничить некоторым конечным числом цифр, измерение становится оцифрованным. Таким образом значения 20,2 мм и 20 мм являются выборочными значениями ширины монеты.

 

2.5.2. Точность квантования

Когда производится выборка аналогового сигнала, он квантуется, т. е. оценивается его ближайшими дискретными значениями. Если мы делаем измерения ширины монеты с точностью до одного десятичного знака, то нашими выборочными значениями будут 20,0 мм, 20,1 мм, 20,2 мм, и т. д. Разность между соседними квантованными значениями определяет шаг квантования. Разность между фактическим и квантованным значением называют ошибкой квантования, которую обозначают символом е. Максимальное значение этой ошибки равно половине шага квантования (рис. 2.4).

pic22

Отношение сигнал-шум (SNR, Signal to Noise ratio)— это отношение мощности сигнала к мощности шума. Шумом в этом случае является ошибка квантования. Мы не знаем точного значения ошибки на конкретной выборке, но мы можем сделать разумное предположение, что все значения в диапазоне изменения входного сигнала являются равновероятными. Для шага квантования d ошибка находится в диапазоне (-d/2, d/2). При возведении в квадрат и усреднении это дает мощность шума d2/12 (рис. 2.5, а). Следовательно, мощность шума пропорциональна квадрату шага квантования. Альтернативно, если мы имеем сигнал с q уровнями квантования, то ошибка квантования обратно пропорциональна q2 (рис. 2.5, б) Чем больше количество уровней квантования, тем выше SNR, но тем больше имеется различных информационных символов. Пороги квантования не обязательно должны быть равномерно распределенными, и чаще всего — это не так. В звуковых системах уровни располагаются по логарифмической шкале, так что на низких уровнях их имеется больше, чем на высоких.

pic23

 

2.5.3. Частота дискретизации

Для изменяющихся во времени величин, подобных электрическим сигналам, в дополнение к точности каждой выборки существует еще одна проблема — частота дискретизации, или скорость выборки (sampling rate). Если частота дискретизации слишком низка, то мы не будем способны восстанавливать сигнал по выборкам. 

Рассмотрим рис. 2.6. Исходный сигнал представлен черной линией, и показанные выборки позволяют должным образом восстановить сигнал. Од-нако, если мы возьмем только каждую вторую выборку, то результатом вос-становления будет серая линия, в которой многие детали исходного сигнала потеряны. Чем выше частота дискретизации, тем больше требуется выборок, и придется передавать большее количество сигнальных значений (символов). Ключевой вопрос состоит в том, сколько требуются выборок, чтобы полно-стью описать сигнал. Ответ на этот вопрос требует понимания индивидуаль-ных компонентов, из которых состоит сигнал. Мы можем расчленять сигнал на различные частотные компоненты с помощью анализа Фурье.

pic24

 

2.5.4. Ряды Фурье

С помощью этих рядов почти любой периодический сигнал можно представить в виде ряда синусоидальных сигналов. Сила этого подхода состоит в том, что если мы определим отклик цепей на синусоиды различных частот, то сможем вычислить, как эти цепи будут реагировать на соответствующий сигнал. Синусоидальные составляющие сигнала, называемые его спектром, формируют представление сигнала в частотной области. Это очень мощный подход к проектированию цепей. Хотя представление сигналов в частотной области напрямую соответствует физическим объектам в форме волн, например, когда речь идет об электромагнитных излучениях (радиоволнах, свете и т. д.), но важно помнить, что представление сигнала в частотной области — это в своей основе математическая модель. Таким образом, мы можем выполнять частотный анализ сигналов, которые изменяются не только во времени, но по другим параметрам, например, в пространстве.

 

2.5.5. Вычисление частотного спектра

Почти любой периодический сигнал можно представить в виде суммы ряда Фурье. Существует две главных формы ряда Фурье— экспоненциальная и тригонометрическая. Они эквивалентны вследствие того, что pic25

Для экспоненциальной формы сигнал формируется из

pic25

Для реальных сигналов можно также использовать тригонометрическую форму

pic27

качестве примера рассмотрим треугольный сигнал, где у = х/2 в интервале от -п до п. На рис. 2.7 показаны три первых члена ряда Фурье для этого сигнала, а также сумма двух и трех первых членов. С учетом трех первых членов основная форма сигнала проявляется уже достаточно четко. На рис. 2.8 показано приближение, учитывающее 30 первых членов ряда Фурье.

pic28

Хотя не каждый возможный периодический синнал имеет представление в виде ряда Фурье, одно из условий такого представления (которое является достаточным, но не необходимым) состоит в том, что интеграл квадрата Функции должен быть конечным. Такое же условие имеет место и для ности сигнала (сигнала с конечной мощностью на периоде). Все реальные сигналы должны иметь конечную мощность, так что все реальные сигналы имеют представления в виде ряда Фурье.Ряд Фурье непрерывной функции также является непрерывным. Если неходки сигнал не является непрерывным, то для ряда Фурье наблюдается эффект Гиббса, когда ряд Фурье сходится в средней точке разрыва.

Ряд Фурье имеет примерно 18-процентные выбросы на концах разрыва с колебаниями, которые имеют ту же частоту, что и самый высокочастотный компонент в ряде Фурье. Энергия этих выбросов, называемых "ушами Гиббса", уменьшается при N -> оо , а их амплитуда не уменьшается. Треугольный сигнал на рис. 2.8 имеет разрыв, так что "уши Гиббса" присутствуют, но они еще лучше видны на прямоугольном сигнале (рис. 2.9). Обратите внимание, что никакой реальный сигнал не имеет разрывов, т. к. это потребовало бы, чтобы ны двигались с бесконечной скоростью, что невозможно. Однако ческая форма, которую мы используем для представления реального сигнала, может иметь разрывы для того, чтобы аппроксимировать сигнал (примером такой формы является ступенчатая функция).

pic29

pic30

 

2.5.6. Частотный спектр

Члены ряда Фурье можно использовать для того, чтобы определять частотный спектр периодических сигналов. Частотный спектр — это график частотных компонентов и их амплитуд. Частотный спектр периодических сигналов называется линейчатым, т. к. он имеет компоненты в точках 1/Т, 2/Т, 3/Т и т. д. (где Т— период сигнала). Самая низкая из этих частот 1/Т, называется основной частотой.Линейчатым спектром обладают сигналы, которые являются истинно периодическими, т. е. простираются от -∞ до ∞. Хотя реальные сигналы не обладают этим свойством, но часто мы можем считать их истинно периодическими в пределах той временной области, в которой мы их рассматриваем.Тогда возникает следующий вопрос: как следует обрабатывать непериодические сигналы? Можно вычислять их частотную характеристику, используя преобразование Фурье. Преобразование Фурье определяется так:

pic31

Обратите внимание, что преобразование Фурье— непрерывная функция, и поэтому апериодический сигнал имеет непрерывный спектр, а не линейчатый, как у периодических сигналов.

Уместно отметить два специальных преобразования. Первое — преобразование импульса, т. е. дельта-функции δ(f), которая равна 1 в точке t = 0, и равна 0 в других точках оси времени. Ее преобразование Фурье выглядит так:

pic32

В более общем случае F(Aδ(t)) = А, так что частотным спектром импульса .является константа, содержащая все частоты

.Вторая функция, стоящая упоминания, — это спектр прямоугольного импульса. Рассмотрим импульс с амплитудой А в интервале -T/2 до T/2 и значением 0 в остальных точках.

pic33

Взаимосвязь между частотной и временной областью подчеркивается тем фактом, что константа амплитуды А является преобразованием дельта-функции величины в точке f = 0, т. е. dc' -компонентом. Кроме того, импульс sinc временной области имеет прямоугольный (масштабированный) отклик в частотной области.

 


 

1 dc (direct current) — постоянная часть импульсного компонента. — Пер.

 

Некоторые свойства преобразований Фурье показаны в табл. 2.1. Умножение во временной области соответствует свертке в частотной области, и наоборот. Повторение во временной области соответствует выборке в частотной области (с масштабным коэффициентом), и наоборот.

 

2.5.7. Минимальная скорость выборки

Из изложенного следует, что выборке (sampling) сигнала во временной области соответствует его повторение (repeating) в частотной области. Поэтому, если частота выборки больше чем удвоенная полоса частот сигнала, то мы можем восстанавливать исходный сигнал, потому что его повторения не будут перекрываться с исходным сигналом. Следовательно, если аналоговый сигнал имеет полосу частот W, то требуется выборка со скоростью, по крайней мере, 2W(или больше).

pic34

Восстановление сигнала выполняется путем удаления высокочастотных копий частотного спектра с помощью идеального низкочастотного фильтра. Прямоугольный частотный отклик соответствует функции sine во временной области. Обратите внимание — поскольку эта функция имеет бесконечный отклик, то все физические системы будут обладать некоторыми искажениями.

 

2.5.8. Импульсно-кодовая модуляция (ИКМ)

Импульсно-кодовая модуляция (PCM, Pulse Code Modulation) — это название процесса выборки аналогового сигнала и замены его дискретными выборками, взятыми в определенные моменты времени. Чем больше делается выборок, тем выше частота соответствующих значений (символов) сигнала. Кроме того, чем более точно выполняются выборки, тем больше число возможных символов. Символы часто представляются строками двоичных цифр, поэтому чем больше число выборок и выше их точность, тем выше битовые скорости передачи.

 

2.5.9. Кодирование источников без памяти

Кодирование Шеннона-Фано

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

Кодирование Хаффмана

Процесс кодирования Хаффмана выполняется следующим образом. Символы сообщения, которые нужно закодировать, перечисляются в порядке убывания вероятности (то есть символы с самой высокой вероятностью должны быть в верхней части этого списка). Если используется двоичный кодовый алфавит, то две ветви с самыми низкими вероятностями объединяются (со сложением их вероятностей), но перед этим одна из них маркируется как 0, а другая — как 1. Затем эти ветви вновь упорядочиваются по вероятности и процесс повторяется. Процесс продолжается до тех пор, пока не останется только одна ветвь. Затем считываются кодовые слова, причем чтение выполняется в обратном порядке от последнего элемента с добавлением в кодовое слово встречающихся по пути нулей и единиц.

Например, возьмем систему со следующими вероятностями: А 0,25; В 0,3; С 0,35; D 0,1. Ранжируем их так:

  • С —0,35;
  • В —0,3;
  • А —0,25;
  • D —0,1.

Самые маленькие вероятности у элементов А и D (0,25 и 0,1 соответственно).

Самые маленькие вероятности у элементов А и D (0,25 и 0,1 соответственно). Они объединяются в одну ветвь AD, ветвь А маркируется как 0, а ветвь D— как (рис. 2.10), и выполняется их новое упорядочивание по убыванию вероятности:

  • С —0,35;
  • AD —0,35;
  • В —0,3.

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

Затем объединяются компоненты AD и В, причем AD помечается как 0, а В — как 1. Это приводит к следующему списку:

  • ADB — 0,65;
  • С —0,35,

в котором объединены компоненты AD и В, список переупорядочен, компонент ADB маркирован как 0, а С — как 1, что дает только одну ветвь, на этом процесс заканчивается. Извлечение кодовых слов выполняется следующим образом (начиная с последнего столбца, в обратном порядке):

  • А: 0 — от ветви ADB (последний столбец), 0 — от ветви AD (средний столбец) и 0 — от ветви А (первый столбец), что дает первое кодовое слово: ООО;
  • В: 0 — от ветви ADB, 1 — от ветви В (средний столбец), что дает второе кодовое слово: 01;
  • С: 1 — от ветви С (последний столбец), что дает третье кодовое слово: 1;
  • D: 0 — от ветви ADB, 0 — от ветви В (средний столбец) и 1 — от ветви D (первый столбец), что дает последнее кодовое слово: 001.

Весь процесс кодирования показан на рис. 2.10.

pic35

Чтобы использовать кодирование Хаффмана для кодовых алфавитов, состоящих из большего количества символов, нужно выполнить небольшую модификацию этапа группировки: вместо объединения двух самых маловероятных компонентов перед переходом к следующему этапу нужно объединять п таких компонентов, где п — число символов кодового алфавита. Эти символы следует использовать для нумерации последних ветвей дерева на различных этапах процесса построения кодов Хаффмана. Отсюда следует, что на каждом этапе этого процесса удаляются (n -1) входов (элементов) списка. Поскольку в конце концов мы остаемся с элементом, помечаемым как 1, то в предыдущем списке мы должны иметь 1 + (n - 1) элементов, в его предшественнике должно быть 1 + 2 (n - 1) элементов, и т. д. Если число элементов, с которых мы начинаем процедуру, не равно 1 (mod n - 1), то нужно прибавлять дополнительные фиктивные элементы с вероятностью 0. Число таких дополнительных элементов равно такому наименьшему числу, при котором новое общее число элементов оказывается конгруэнтным 1 (mod n - 1).

 

2.5.10. Кодирование источников с памятью

Кодирование (сжатие), использующее алгоритмы Хаффмана и Шеннона-Фано, хорошо работает для источников, производящих символы с довольно ограниченным алфавитом, но оно не работает, когда алфавит достаточно велик и каждый символ используется несколько раз. Например, изображение может состоять из многих миллионов пикселов, каждый из которых будет иметь немного разный цвет. В этом случае можно использовать память источника. Для таких целей были разработаны другие типы сжатия. Основные типы сжатия приведены в табл. 2.2.

Сжатие происходит без потерь, если источник может быть точно восстановлен по сжатым данным. Сжатие с потерями в процессе кодирования отбрасывает некоторую информацию, так что источник не может быть точно восстановлен. Так, например, при сжатии изображения происходит уменьшение количества различаемых цветов. Сжатая версия изображения будет отличаться от исходной, но при должным образом спроектированной системе компрессии она должна восприниматься пользователем почти так же, как исходная.

pic36

Таблица 2.2 (окончание)

Основа кодирования Тип кодирования Тип кодирования Тип сжатия
Кодирование на основе синтаксиса (в информатике это называется кодированием источника). Приводит к  потерям (хотя некоторые дифференциальные схемы (см.*) могут приводить к потерям при их комбинациях с кодированием на основе символов) Преобразующее   кодирование FFT
DCT
Дифференциальное кодирование Дифференциальная ИКМ*
Дельта-модуляция
Адаптивно-дифференциальная ИКМ*
Векторное  квантование CELP (для речи)
Фрактальное (для изображений)

Подавление нулей

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

Групповое кодирование

Это расширение предыдущего метода, когда группы любых смежных символов изображения заменяются соответствующим одиночным символом и числом его повторений. Чисто черно-белое изображение, например, можно кодировать просто посылками нужного количества пар, состоящих из числа белых пикселов, за которым следует число черных. Например, пиксельная последовательность 1111111000000110000010000000000010 кодируется как 07625119021. Блок из одиннадцати нулей расщепляется на два и представляется как 902, поскольку в противном случае 11 нулей были бы перепутаны с последующим числом единиц (1). Таким образом, здесь 9 является самым большим допустимым количественным значением для нулевых символов.

Подстановка образцов

В этой методике сжатия общие последовательности символов заменяются специальным мета-символом, представляющим всю последовательность. Форма подстановки образцов, например, ЕС вместо Европейского Сообщества, называется акронимом. Два широко используемых алгоритма для подстановки образцов были разработаны Зивом и Лемпелем (Ziv, Lempel) в 1977 и 1978 годах. В алгоритме 1977 года первые несколько символов передаются без сжатия, а затем следующие символы проверяются по предварительно переданному набору. Если некоторый образец уже был предварительно послан, то вместо последовательности символов посылается ее позиция и длина. Алгоритм 1978 года, улучшенный относительно алгоритма 1977 года, начинает работу с создания словаря, содержащего все символы из алфавита источника, и затем добавляет к нему новые элементы переданных строк.

Дифференциальное сжатие

Здесь кодируется разность между предыдущим и текущим символами, а не сам символ. Если имеются взаимосвязи между символами (например, выборками сигнала), то разность может быть существенно меньше, чем абсолютное значение, и следовательно, ее проще кодировать. Эту методику можно улучшить, используя адаптивное дифференциальное кодирование, где ко- дирующее устройство предсказывает следующий символ и посылает разность между предсказанием и фактическим значением. Простая форма дифференциального кодера — дельта-модулятор, который для увеличения или уменьшения вывода посылает только один бит.

Сжатие на основе преобразования

Цель этого вида кодирования состоит в том, чтобы преобразовать сигнал в Другую область, где он может быть представлен более эффективно, и сжать его в этой области. Например, если сигнал из временной области преобразовать в частотную, и если у него нет высокочастотных компонентов, то для пересылки этой информации необходимо меньшее количество коэффициентов. Прямое и обратное преобразования не будут вызывать никаких искажений сигнала, если данные не усечены каким-нибудь способом, так что трансформационное кодирование в чистой форме происходит без потерь.

В общем случае в пределах целевого диапазона находится несколько компонентов, иногда небольших. При сжатии незначащие компоненты отбрасываются с помощью процесса называемого "квантованием". Чем больше количество отбрасываемых компонентов, тем больше коэффициент сжатия, но тем больше и искажения.

Векторное квантование

Векторное квантование заменяет источник восстановленным сигналом, состоящим из компонентов, определяемых кодером. Речевое кодирующее устройство (CELP-кодер), используемое в мобильном радио, имеет очень низкую битовую скорость (до 2,4 Кбит/с) и использует кодовую таблицу (книгу) шифров речевых звуков, которая может быть отрегулирована путем изменения параметров. Эти-то параметры, а не сами звуки, и посылаются кодером получателю. Та же методика используется при фрактальном сжатии изображений, когда вместо точной копии самого изображения посылаются специальные изображения — фракталы вместе с инструкциями по их использованию. Фракталы— это произвольные образцы, которые находятся (в различных формах) в исходном изображении.

Примеры сжатия

Далее приведены примеры сжатия различных сигналов рассмотренными способами.

  • Факс. Факсы 3-й группы используют групповое кодирование и кодирование Хаффмана. Отсканированное изображение содержит 1145 строк, состоящих из 1728 белых и черных пикселов. Для каждой строки сначала выполняется групповое кодирование, а затем для полученных таким способом чисел используется кодирование Хаффмана. Этот процесс заменяет два миллиона исходных битов четвертью миллиона кодовых битов.
  • Текст. Алгоритм Лемпеля-Зива хорошо работает с текстами, обычно обеспечивая уменьшение исходного размера на 20—25%. Отметим, что  здесь не происходит уменьшения до уровня, близкого к истинной энтропии речи, потому что алгоритм рассматривает т
  • Речь. Стандартный речевой ITU-кодер имеет полосу пропускания 4 кГц и скорость 8000 8-разрядных выборок/секунду (64 Кбит/с). Современные CELP-кодеры могут обеспечивать такое же качество звука (называемого качеством телефонной связи) при скорости 8Кбит/с. Однако, поскольку CELP-кодеры используют кодовые таблицы звуков, согласованных только с речью, качество других звуков (например, музыкальных) невысоко. ITU-кодер будет работать на любом звуковом источнике с полосой пропускания до 4 кГц.
  • Изображения. Для статичных изображений часто используется формат GIF, который уменьшает цветовую глубину до 256 цветов и затем использует алгоритм Лемпеля-Зива, чтобы выполнить сжатие без потерь. В формате JPEG3 используется дискретное косинусное преобразование на блоках 8x8 пиксел. Оно уменьшает результирующие компоненты, усекая незначительные высокочастотные компоненты ("квантование"). Для наиболее важного DC-компонента используется дифференциальное кодирование, а для максимально возможного сжатия остающихся компонентов— групповое кодирование и, наконец, кодирование Хаффмана, или арифметическое кодирование. В формате MPEG4 для максимального уменьшения битовой скорости передачи используется конечное преобразование Фурье совместно с системой эталонных и прогнозирующих фреймов. Для прогнозирующих фреймов передаются только различия. Формат MPEG-1 дает качество, близкое к качеству видеофильмов, при скорости выше 1 Мбит/с. Формат MPEG-2 дает качество, близкое к качеству радиовещания, при скорости выше 2 Мбит/с, и используется новыми цифровыми телевизионными службами. Формат MPEG-4 разработан для очень низких битовых скоростей (менее 64 Кбит/с), и используется, например, для видеоконференций. Здесь возможны чрезвычайно низкие битовые скорости.

Практическое сжатие — JPEG

Хорошим примером практического сжатия является стандарт сжатия изображений JPEG. Для максимально возможного* сжатия изображения в нем используется трансформационное, дифференциальное и групповое кодирование. Изображения разбивается на блоки размером 8x8 пиксел и затем на каждом из этих блоков используется двумерное дискретное косинусное преобразование. Если изображение цветное, то преобразование применяется к каждому каналу цветности отдельно.Квантование в JPEG выполняется путем деления каждого из коэффициентов на массив предопределенных значений размером 8x8. При этом предпочтение отдается низкочастотным компонентам, и оставляется только целая часть от такого деления. Это означает, что правая нижняя часть массива заполнится нулями. Наиболее значимым будет левый верхний компонент, который и представляет dc-значение (среднее значение данных в блоке размером 8x8 пиксел). Чтобы ввести еще большее сжатие, используется дифференциальное кодирование этого значения, и затем коэффициенты считываются по диагонали так, чтобы нулевые значения были в максимально возможной степени сгруппированы вместе. Наконец, чтобы сжать последовательности нулей, выполняется групповое кодирование.

 

 


 

2 GIF, Graphic Interchange Format — формат обмена графическими данными. — Пер.

3 JPEG, Joint Photographic Experts Group — формат объединенной группы фото-экспертов. — Пер.

4 MPEG — Motion Picture Experts Group — формат группы киноэкспертов. — Пер.

 

 

 

 

ПечатьE-mail

Яндекс.Метрика