Сущность и методы эффективного кодирования.

Под кодированием будем понимать отображение состояний некоторой системы (источника сообщений) с помощью состояний сложного сигнала, который представляет собой последовательность из n элементарных сигналов. Множество Y состояний элементарного сигнала образует алфавит кода размера mу. При my=2 элементарный сигнал имеет два состояния, которые обозначим через 1 и 0. Состояние сложного сигнала описывается последовательностью из нулей и единиц, которая называется кодовым словом. Если кодовые слова имеют разную длину, то код называется неравномерным, а если одинаковую, то код называется равномерным.

Пусть источник сообщений вырабатывает последовательность из k букв, причем xi буква в этой последовательности появляется n раз. Каждой букве xi (i= ) поставим в соответствие кодовое слово с длиной, равной li (посимвольное кодирование). Тогда длина соответствующей последовательности из кодовых слов будет равна

Это равенство можно представить в виде

При неограниченном увеличении числа букв К в последовательности относительная частота появления х{ буквы с вероятностью, равной единице, совпадает со значением вероятности pi появления этой буквы. Поэтому с вероятностью, равной единице, выполняется равенство

- по определению средняя длина кодового слова. Длина последовательности кодовых слов L является случайной величиной, но значительные отклонения ее от среднего значения =К маловероятны при неограниченном возрастании K.

Таким образом, источник сообщений с вероятностью, равной единице, вырабатывает типичные последовательности, длина которых мало отличается от их среднего значения К .

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

 

Для уменьшения избыточности символов необходимо применить эффективное кодирование. Эффективным называется способ кодирования, при котором:

1. Не возникает потери информации.

2. Требуется минимальное количество кодовых символов.

Для выполнения второго условия используются неравномерные коды, где длина кодового слова обратно пропорциональна вероятности его появления в сообщении.

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

Эффективное кодирование достигается благодаря учету априорных статистических характеристик источника информации.

Предельные возможности эффективного кодирования определяются

Алгоритмы эффективного кодирования

Алгоритм Шеннона-Фано.

 

Пусть имеется множество сообщений .

1. Все сообщения располагаются в порядке убывания их вероятностей.

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

3. После этого сообщениям в верхней части ставится в соответствие 1, а в нижней – 0.

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

5. В результате каждому сообщению будет соответствовать своя последовательность из нулей и единиц, т.е. кодовое слово.

 

Пример:

Pi	X
0.5	x1
0.25	x2
0.125	x3
0.125	x4

 

 

Алгоритм Хаффмена.

 

1. Все сообщения располагаются в порядке убывания их вероятностей.

2. Два самых нижних сообщения объединяются в одно событие, вероятность которого равна сумме вероятностей, объединяемых событий, причем верхнему событию ставится в соответствие 1, а нижнему 0.

3. Получился новый массив сообщений с количеством состояний на единицу меньшим по сравнению с предыдущим массивом, если два последних события считать одним более крупным событием. Далее преобразуем этот массив в соответствии с пунктами 1 и 2. Полученный массив вновь подвергаем указанным преобразованиям и т.д. до тех пор, пока не будет исчерпан весь массив.

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

 

Пример:

 

x1=1, x2 = 01, x3 = 001, x4 = 000

 

 

б)Эпсилон-Энтропия. Производительность источника с непрерывным множеством состояний.

ЭПСИЛОН - ЭНТРОПИЯ

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

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

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

Количество взаимной информации между множествами и , определяемое равенством

,

равно энтропии , поскольку неопределенность , с которой значение случайной величины определяет значение случайной величины , равна нулю. Поэтому для воспроизведения значения случайной величины с точностью требуется количество информации, равное .

Пронумеруем все элементы множества числами от 1 до и запишем их в - ичной системе счисления. Минимальное количество разрядов , некоторое при этом потребуется, удовлетворяет неравенству:

.

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

Более универсальной мерой точности воспроизведения по сравнению с является среднеквадратичная ошибка

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

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

Определим e - энтропию как минимальное по количество информации, необходимое для воспроизведения значения случайной величины с заданной точностью при заданном распределении источника:

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

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

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

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

Кроме квантования существует много других способов преобразования непрерывной величины . В частности, множество может представлять собой результаты измерений величины . Пусть непрерывная величина с некоторой погрешностью h воспроизводит нормально распределенную случайную величину : . Тогда при заданной дисперсии погрешности (при заданной среднеквадратичной ошибке) e - энтропия нормальной величины равна [ 8 ]

,

где - дисперсия случайной величины .

 

Билет 11.
а) Предельные возможности эффективного кодирования
б) Пропускная способность гауссова

Билет

(сделала 2 варианта первого вопроса – по лекциям Ломакина и по методичке)