Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лекция № 5
Статистическое кодирование дискретных сообщений. Энтропия непрерывного источника. Пропускная способность непрерывного канала связи.
Статистическое кодирование дискретных сообщений
Используя теорему К. Шеннона, сформулированную в предыдущем разде ле, можно увеличить производительность источника дискретных сообщений, если априорные вероятности различных элементов сообщения неодинаковы, К.Шеннон предложил и метод такого кодирования, который получил название статистического или оптимального кодирования. В дальнейшем идея такого кодирования была развита в работах Фано и Хаффмена и в настоящее время широко используется на практике для "сжатия сообщений".
Основой статистического (оптимального) кодирования сообщений являет ся теорема К. Шеннона для каналов связи без помех.
Кодирование по методу Шеннона-Фано-Хаффмена называется оптималь ным, так как при этом повышается производительность дискретного источника, и статистическим, так как для реализации оптимального кодирования необхо димо учитывать вероятности появления на выходе источника каждого элемента сообщения (учитывать статистику сообщений).
Используя определения производительности и избыточности дискретного источника, приведённые можно получить
Из этой формулы видно, что для увеличения производительности нужно уменьшать избыточность χ или среднюю длительность сообщений.
Идея статического кодирования заключается в том, что, применяя неравномерный неприводимый код, наиболее часто встречающиеся сообщения (буквы или слова) кодируются короткими кодовыми словами этого кода, а ред ко встречающиеся сообщения кодируются более длительными кодовыми сло вами.
Рассмотрим принципы оптимального кодирования на приводимом ниже примере. Пусть источник сообщений выдаёт 8 различных сообщений x1…x8 с вероятностями 0,495; 0,4; 0,026; 0,02; 0,018; 0,016; 0,015; 0,01 (сумма вероятно стей равна 1).
Располагаем эти сообщения столбцом в порядке убывание вероятностей.
{xi, p(xi)} Кодовое дерево Код Ni p(x)Ni
------------- -----------------
x1 0,495 0 1 0,495
x2 0,4 10 2 0,8
x3 0,026 1100 4 0,104
x4 0,02 1110 4 0,08
x5 0,018 11010 5 0,09
x6 0,016 11011 5 0,08
x7 0,015 11110 5 0,075
x8 0,01 11111 5 0,05
------------- ---------------------
Рисунок 6 - Статистическое кодирование
Объединяем два сообщения с самыми минимальными вероятностями дву мя прямыми и в месте их соединения записываем суммарную вероятность: p(x7)+p(x8)=0,015+0,01=0,025. В дальнейшем полученное число 0,025 учитыва ем в последующих расчётах наравне с другими оставшимися числами, кроме чисел 0,015 и 0,01. Эти уже использованные числа из дальнейшего расчёта ис ключаются. Далее таким же образом объединяются числа 0,018 и 0,016, получа ется число 0,034, затем вновь объединяются два минимальных числа (0,02 и 0,026) и т.д.
Построенное таким образом кодовое дерево используется для определения кодовых слов нового кода. Напомним, что для нахождения любого кодового слова надо исходить из корня дерева (точка с вероятностью 1) и двигаться по ветвям дерева к соответствующим сообщениям x1…x8 . При движении по верх ней ветви элемент двоичного кода равен нулю, а при движении по нижней - равен единице. Например, сообщению x5 будет соответствовать комбинация 11010. Справа от кодового дерева записаны кодовые слова полученного нерав номерного кода. В соответствии с поставленной задачей, наиболее часто встре чающееся сообщение x1 (вероятность 0,495) имеет длительность в 1 элемент, а наиболее редко встречающиеся имеют длительность в 5 элементов. В двух по следних столбцах рисунка приведено число элементов Ni в кодовом слове и величина произведения p(xi)Ni=∑ p(xi)Ni= 1,774 представляет собой число элементов, приходящееся на одно слово, т.е. в данном случае .
Если бы для кодирования был применён равномерный двоичный код, который чаще всего применяется на практике, число элементов в каждом кодовом слове для кодирования восьми различных сообщений равнялось бы трём (23=8), т.е. .. В рассматриваемом примере средняя длительность кодового слова благодаря применённому статистическому кодированию уменьшилась в 3/1,774=1,72 раза. Во столько же раз увеличилась и производительность источника.
Дальнейшим развитием оптимального статистического кодирования явля ется кодирование кодовых слов. В этом методе применяется также оптимальное кодирование по методу Шеннона-Фано-Хаффмена, однако не к отдельным бук вам, а к кодовым словам( сочетаниямn букв первичного сообщения). Статисти ческое кодирование слов позволяет ещё больше уменьшить среднюю длитель ность сообщений, так как алфавит источника быстро увеличивается с увеличе нием длины слова. Число возможных кодовых слов (алфавит источника после объединения букв) определяется выражением m=kn, где k - алфавит букв первичного сообщения. Пусть, например, у нас имеется двоичный источник с ал фавитомa1 и a2 (например, “1” и “0”). При передаче этих букв по каналу связи используются сигналы длительностью τэ, а =τэ.
Рассмотрим пример, когда p(a1)=0,8 и p(a2)=0,2 (если вероятности p(a1) и p(a2) равны между собой, никакое кодирование не может уменьшить среднюю длительность сообщения). Образуем из элементов a1 и a2 слова из двух букв (n=2), беря различные сочетания из этих букв. Если у нас источник с независимым выбором элементов сообщений, то
p(a1a1)=0,8*0,8=0,64;
p(a1a2)= p(a2a1)=0,8*0,2=0,16;
p(a2a2)=0,2*0,2=0,04.
Применяя к полученным словам кодирование по методу Шеннона-Фано-Хаффмена, получаем кодовое дерево (рисунок 2.6), из которого видно, что новые кодовые слова неравномерного кода имеют длительность τэ, 2τэ и 3τэ.
Средняя длина кодового слова
τсл=0,64τэ+0,16*2τэ+0,16*3τэ+ 0,04*3τэ=1,56τэ.
Но так как каждое слово содержит информацию о двух буквах первичного сообщения, то в расчёте на 1 букву получаем τэ, Отсюда видно, что средняя длина элемента сообщения сократилась по сравнению с первоначальной в 1/0,78=1,38 раза.
a1a1
a1a2
a2a1
a2a2
Рисунок 7 – Алфавит источника после объединения букв
Если усложнить кодирование и использовать n=3, то в этом случае полу чим . Это уже почти предел, дальше уменьшать n уже нецелесооб разно. Чтобы убедиться в этом, рассчитаем производительность источника со общений для всех трёх случаев. Энтропия источника
бит.
Последняя величина близка к предельно возможной величине 1/ τэ.
Статистическое кодирование слов целесообразно применять также в слу чае использования эргодического дискретного источника (источника с корре ляционными связями букв), так как объединение букв в слова приводит к раз рушению корреляционных связей (величина nдолжна быть не менее порядка эргодического источника, а nτэ, соответственно, больше интервала корреляции букв первичного сообщения). Корреляционные связи между буквами транс формируются в различные вероятности появления возможных слов (n -буквен ных сочетаний). При этом необходимо помнить, что вероятность n-буквенных сочетаний определяется не произведением вероятностей отдельных букв, а, в соответствии с теоремой умножения вероятностей надо учитывать также ус ловные вероятности. Так, например, для источника с независимым выбором букв p(a1a1)=p(a1)p(a1), эргодического источника с корреляционными связями букв p(a1a1)=p(a1)p(a1/a1).
Энтропия непрерывного источника
Энтропия дискретного сигнала определялась выражением (2). Для непрерывной случайной величины воспользуемся эти же выражением, заменив вероятность P(x) на W(x)dx
В результате получим
Но логарифм бесконечно малой величины (dx) равен минус бесконечности, в результате чего получаем
H(x)=∞-
Таким образом, энтропия непрерывной случайной величины бесконечно велика. Но т.к. в последнем выражении первое слагаемое (∞) от величины x или от W(x) не зависит, при определении энтропии непрерывной величины это слагаемое отбрасывают, учитывая только второе слагаемое (некоторою “добавку” к бесконечности). Эта добавочная энтропия определяемая формулой
(27)
называется дифференциальной энтропией непрерывной случайной величины.
В дальнейшем слово “дифференциальная” в определении энтропии будем иногда опускать. Как и для дискретных сообщений, существуют следующие разновидности дифференциальной энтропии непрерывной величины.
1. Условная энтропия случайной величины у относительно случайной величины x
, или
(28)
2. Совместная энтропия двух непрерывных случайных величин равна
, или
(29)
Для независимых x и y H(x,y)=H(x)+H(y). Для совместной дифференциальной энтропии непрерывной случайной величины справедливы соотношения (17) и (18)
H(x,y)=H(x)+H(y/x)
H(x,y)=H(y)+H(x/y)
3. Взаимная информация H(x↔y) содержащаяся в двух непрерывных сигналах x и y, определяется формулой (20)
Для независимых x и y H(x↔y)=0
4. Если случайная величина ограничена в объёме V=b-a, то её дифференциальная энтропия максимальна при равномерном законе распределения этой величины
Рисунок 8
Так как эта величина зависит только от разности (b-a), а не зависит от абсолютных величин b и a, следовательно, Hmax(x) не зависит от математического ожидания случайной величины x.
5. Если случайная величина не ограничена в объёме (т.е. может изменяться в пределах от -∞ до +∞), а ограничена только по мощности, то дифференциальная энтропия максимальна в случае гаусcовского закона распределения этой величины. Определим этот максимум в соответствии с (27)
W(x)=
отсюда
Но математическое ожидание m{(x-a)2}= , отсюда получаем
или окончательно
(30)
Следовательно, энтропия зависит только от мощности δ2. Эта важная формула будет использоваться позднее для определения пропускной способности непрерывного канала связи.
Замети, что, как и ранее, Hmax(x) не зависит от математического ожидания a случайной величины x. Это важное свойство энтропии. Оно объясняется тем, что мат. ожидание является не случайной величиной.
Пропускная способность непрерывного канала связи.
Если x(t)-сигнал на входе канала связи, а y(t)=x(t)+ς(t) – сигнал на его выходе(ς(t)-аддитивная помеха), то скорость передачи информации по непрерывному каналу связи будет определяться выражением (23), в котором величину 1/τ надо заменить на 2Fmax=2Fk
(31)
где, как и ранее, H(y) – это энтропия выходного сообщения, H(y,x) – энтропия шума(почему она так называется, будет видно из дальнейшего изложения).
Пропускная способность равна максимально возможной скорости передачи по каналу связи, когда источник сигнала полностью согласован с характеристиками канала связи:
(32)
Максимум H(y) достигается в случае гаусcовского закона распределения величины y. При этом:
(33)
При учёте влияния помехи необходимо рассматривать наихудший случай, когда помеха распределена также по гаусcовскому закону. Условная вероятность P(y/x) – это попросту плотность вероятности W(y/x) случайной величины y при якобы известном заранее xявляется случайной. Но, так как, y(t)=x(t)+ξ(t) можно записать
,
где - дисперсия величины y при известном x, т.е. дисперсия помехи .
Определим условную энтропию H(y/x)
В этом выражении предполагается, что x известно заранее. Таким образом, величина x в привед1нном выражении является попросту математическое ожидание величины y. Однако известно, что энтропия непрерывного случайного процесса от математического ожидания не зависит. Тогда получаем
отсюда видно, почему условная энтропия H(y/x) называется энтропией шума.
Для гауссовского закона распределения помехи максимальное значение энтропии шума, в соответствии (30) будет равно
(34)
Подставляя (33) и (34) в (32) получаем
(35)
Перенося число 2 под знак логарифма, получим . В этом выражении - мощность помехи, а , где Pc – мощность сигнала на выходе канала связи. С учётом этого получаем окончательно формулу для вычисления пропускной способности непрерывного канала связи(формулу Шеннона):
(36)
В заключении отметим следующее. Для достижения скорости передачи информации по непрерывному каналу связи, близкой к пропускной способности канала связи, сигнал x(t) по статической структуре должен быть близок к флуктуационной помехе (белому шуму) с гауссовским законом распределения.
Эпсилон – энтропия
Сигнал на выходе источника (И) непрерывных сообщений(например, микрофона, телефона, датчика температуры и пр.) представляет собой непрерывный случайный процесс, энтропия которого в любом из сечений в общем случае равна бесконечности как это было показано в разделе 2.4. Такое количество информации не может быть передано по реальному каналу связи, пропускная способность которого всегда ограничена. Это и не нужно, так как скорость восприятия информации любым потребителем на выходе канала всегда ограничена его физическими возможностями. Поэтому непрерывный сигнал на выходе канала связи даже без помех отличается от сигнала на входе, так как содержит не всю информацию о нём(причём под каналом связи можно понимать любое преобразование одного ансамбля сигналов в другое: модуляцию, усиление, дискретизацию и пр.). Уже преобразование непрерывного сообщения в сигнал соответствующим устройством(микрофоном или др. датчиком сигнала) связано с потерей части информации, а сигнал отображает сообщении лишь с некоторой точностью
где x(t) - сигнал на входе преобразователя; – сигнал на выходе преобразователя (Пр) или оценка входного сигнала преобразователем, который всегда представляет собой некоторое решающее устройство, работающее по определенному правилу и заданному критерию качества.
|
|
x(t)
Рисунок 9
Критерий качества, как известно, определяется потребителем информации, например, среднеквадратическое отклонение
или дисперсия ошибки
Эпсилон-энтропией Hε(x)(ε-энтропией) называется минимальное количество информации, которое должно содержаться в выходном сигнале о входном сигнале x(t), чтобы этот сигнал можно было восстановить с заданной точностью εср.
где
I(x, )-взаимная информация x и ;
h(x) и h(x/ )-соответственно, дифференциальная энтропия сигнала x(t) и условная энтропия x(t), когда известно; min и max берутся по всевозможным условным ФПВ w(x/ ).
В общем случае, когда сигнал (или сообщение) x(t) является гауссовским с дисперсией , ошибка ε(t) также является гауссовской с дисперсией , а с учётом аддитивного характера ошибки ε(t) условная энтропия h(x/ ) полностью определяется дифференциальной энтропией h(ε). Соответственно, maxh(x/ )=maxh(ε)= .
Тогда ε – энтропия одного сечения гауссовского источника(ε – энтропия одного отсчёта)
hε(x)= - =0,5 .
Величина показывает отношение мощности(дисперсии) сигнала x(t) к мощности(дисперсии) ошибки, при котором среднеквадратическое отклонение сигналов x(t) и не превышает .
Следовательно, производительность источника непрерывных сообщений можно определить как количество информации, которое необходимо передавать в единицу времени, чтобы восстановить сообщение с заданной точностью.
hε(x)=vhε(x),
где v=1/ - скорость передачи отсчетов на выходе источника, – интервал между отсчетами.
Для стационарного сигнала с ограниченным спектром =1/(2Fmax), тогда hε(x)=2Fmaxhε(x).
Если, кроме того, что источник является гауссовским, то
hε(x)= Fmax .
Количество информации, выдаваемое гауссовским источником за время Tc, равно Tchε(x)= TcFmax , что совпадает с формулой для объёма сигнала, когда динамический диапазон сигнала
Dc= .
Это значит, что объём сигнала на выходе источника равен количеству информации, которое содержится в сигнале для его воспроизведения с заданной точностью.
Для канала с пропускной способностью C, на выходе которого подключен источник с производительностью hε(x), теорема К. Шеннона для канала с шумами принимает вид:
Если при заданном критерии точности источника (например, ) его эпсилон-производительность меньше пропускной способности канала hε(x)<C, то существует способ кодирования (преобразования сигнала), при котором неточность воспроизведения сколь угодно близка к ; при hε(x)>C такого способа не существует.
Теорема К. Шеннона определяет предельные возможности согласования источника непрерывных сообщений с каналом связи. Практически это достигается применением помехоустойчивых видов модуляции и кодирования.