Материал: ОТС Лекции 1 и 2 часть

Источник создает сообщения, символы аk , которые могут принимать значения от 1 до m. Символы статистически связаны между собой – это исходный код К1. Последовательности из n символов образуют слова, статистические связи между которыми практически отсутствуют.

Осуществим укрупнение алфавита источника, будем кодировать не буквы, а целые слова Аi. Эти слова Аi являются символами нового кода К2. Вероятность символов нового кода К2 равна вероятности слов первичного кода К1 . Т.к. слово состоит из n букв , то энтропия на символ нового кода H2 больше в n раз энтропии на символ старого кода H1 .

Рассмотрим пример, который подробно изложен в описании лабораторной работы №20а. Источник двоичных сообщений A и M производит слова из двух букв (AM, MA, MM, AA); буквы в слове коррелированы, слова - некоррелированы. Статистические характеристики источника следующие:

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

Порядок расчета энтропии источника зависимых сообщений:

1)Определяем общее количество N независимых слов источника. В данном случае их 4, т.к. m =2 , и n =2 (слова состоят из двух букв) , N=22=4.

2)Определяем вероятность каждого слова:

p(AM)=p(A)*p(M/A)=0.7*0.2=0.14;

p(MA)=p(M)*p(A/M)=0.3*0.7=0.21;

p(MM)=p(M)*p(M/M)=0.3*0.3=0.09;

p(AA)=p(A)*p(A/A)=0.7*0.8=0.56;

3) Т.к. слова независимы, то энтропию источника «на слово», т.е. среднее количество информации, приходящееся на одно слово источника, найдем по формуле :

N

Hсл = −∑ pk log pk = − p(АМ) log p(АМ)− p(ММ) log p(ММ) −

k=1

−p(МА) log p(МА)− p(АА)log p(АА) =1.656 [дв.ед.] ;

слово

4) Энтропия на одну букву или символ (n=2):

H=Hсл / n = 0.828 дв.ед/символ

Рассчитаем избыточность нашего источника, т.е. степень отличия энтропии

Так как наш источник создаёт только 2 разных сообщения A и M, т.е. является двоичным источником, то его максимальная энтропия равна Hmax=log2 2 =

= 1 дв.ед./символ. Следовательно, его избыточность равна: R=(1- 0.828)/1=0.172

26

Укрупним алфавит источника и будем кодировать кодом К2 целые слова. Т.к. разных слов – 4, то нужно использовать код с основанием m=4.

АМ – первое слово S1 кодируем символом 0,

МА – второе слово S2 кодируем символом 1,

ММ – третье слово S3 кодируем символом 2,

АА – четвертое слово S4 кодируем символом 3.

Получили новый код К2 с основанием m=4, длиной комбинации n=1, общее число комбинаций N=mn=4.

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

H = = -P(S1) logP(S1) -P(S2) logP(S2) -P(S3) logP(S3) -P(S4) logP(S4) = =1.656 (дв.ед. / сообщение)

Вместо «сообщение» можно употребить термин «буква», т.к. буквами нового источника являются слова первичного источника.

Ранее для исходного первичного источника было H=0.828(дв.ед./ символ). Таким образом мы увеличили энтропию в 2 раза. Определим избыточность нового источника, для которого Нmax=log4=2(дв.ед./ символ) :

R’=1-H/Hmax=1-1.656/2= 0.172

Избыточность осталась та же. Т.о., увеличив энтропию с помощью кода К2, мы не уменьшили избыточность. Это означает, что есть возможность еще более увеличить энтропию.

4.4. Устранение корреляционных связей между символами. Кодирование с предсказанием.

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

Для устранения корреляционных связей между символами можно использовать линейное кодирование с предсказанием (Line Prediction Coding =LPC-кодер).

Слово или сегмент в последовательности из n букв, символов (х1,х2,…,хn) описывается корреляционной матрицей:

Rik - коэффициент корреляции между i-ой и k-ой буквами.

Зная предыдущие буквы, можно предсказать последующие. Предсказанное значение xk запишем в виде:

27

Ошибка предсказания равна:

xk -xk =xk -(c1x1 +c2x2 +......+ck-1xk-1)

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

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

Алгебраическое дополнение Аij элемента аij равно определителю (минору), который получается после вычеркивания строки и столбца, в которых стоит элемент аij .

В линию связи передается ошибка предсказания. Рассмотрим простейший случай предсказания к-го символа по (к-1)-му:

xɶk = ck-1xk-1

где сk-1=R – коэффициент корреляции между к-ым и (к-1)-ым символами. В линию связи передаётся ошибка предсказания:

Дx = xk - xɶk ;

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

4.5.Увеличение энтропии дискретного источника независимых, неравновероятных сообщений с помощью неравномерного кодирования. Алгоритм Хаффмена.

Из вышеприведенного примера видно, что после укрупнения сообщений источника мы имеем те же сообщения. Они были закодированы кодом К2, энтропия которого больше, чем энтропия исходного сообщения, т.е. кода К1 . Символы нового кода независимы, некоррелированы. Однако, энтропия этого кода К2, вообще говоря, не максимальна, так как символы нового кода не равновероятны. Для дальнейшего увеличения энтропии необходимо закодировать символы кода К2 так, чтобы символы нового кода К3 были равновероятны. Это достигается неравномерным кодированием, например, в соответствии с алгоритмом Хаффмена. В соответствии с этим алгоритмом

получим код с префиксными свойствами:

более короткая кодовая комбинация не должна являться началом более длинной комбинации.

Это позволяет осуществить однозначное декодирование без разделительных символов ( в отсутствии помех). Алгоритм Хаффмена предполагает построение «кодового дерева».

28

Алгоритм построения кодового дерева:

а) Расположить исходные сообщения в порядке убывания (невозрастания) вероятностей; б) Объединить два наименее вероятных сообщения в одно, вероятность

которого равна сумме вероятностей объединяемых сообщений (точка объединения сообщений называется «узлом кодового дерева»); в) Повторять шаги а) и б) до тех пор, пока не получим одно сообщение с

вероятностью 1. Эта точка называется «вершиной кодового дерева». Например, кодовое дерево имеет вид рис.4.2 для источника сообщений, заданного в примере.

Рис.4.2.

Алгоритм кодирования слов новым двоичным кодом следующий: -идём от вершины кодового дерева к сообщению,

-если в узле мы идём вверх, то в кодовую комбинацию записывается единица, если вниз – ноль. В результате получим:

S4 => “1” ; S2 => “00” ; S1 => “011” ; S3 => “010” .

Проследите кодирование по кодовому дереву. Мы получили код К3 с префиксными свойствами.

сообщение; S3 - 9 сообщений; S4 - 56 сообщений. В соответствии с новым кодом имеем:

*14 сообщений S1, т.е. 14 символов 0 и 28 символов 1;

*21 сообщение S2, т.е. 42 символа 0;

*9 сообщений S3, т.е. 9 символов 1 и 18 символов 0; *56 сообщений S4, т.е. 56 символов 1.

Таким образом, 100 среднестатистических сообщений содержат: cимвол 0: N0 = 14*1 + 21*2 + 9*2 = 74 штуки;

cимвол 1: N1 = 14*2 +9*1 + 56*1= 93 штуки. Вероятность появления единиц и нулей:

29

Энтропия нового двоичного источника H’’:

H’’ = - p(1) log p(1) – p(0) log p(0)= - 0.557 log0.557–0.443 log0.443 = =0.994 (двоичных ед./символ)

Избыточность нового двоичного источника, существенно уменьшилась: R’’=1-0.994=0.006.

Определим среднюю длину кодовой комбинации:

k=1

рк - вероятность k-того сообщения,комбинации; nk – длина кодовой комбинации k-го сообщения. Для нашей задачи получим:

nср =0.56+ 0.14 3 + 0.21 2 + 0.09 3 = 1.67 (дв.симв. / сообщение)

Можно сделать вывод, что энтропия полученного кода К3 практически максимальна.

4.6. Эффективные способы передачи Описанные методы нашли широкое применение в современных

модификациях ИКМ.

Дифференциальная ИКМ (ДИКМ). Этот способ передачи состоит в вычислении ошибки предсказания. Ошибка предсказания кодируется при меньшем числе уровней квантования. Структурная схема системы связи с ДИКМ показана на рис.4.3. Предсказатель - это трансверсальный фильтр. Его структурная схема показана на рис.4.4.

Предсказатель

Рис.4.3.

30