***** Google.Поиск по сайту:


Лекции по Теоретическим основам цифровой связи   

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

13.1.1. Дискретные источники

Дискретные источники генерируют (или выдают) последовательность символов Х(k), выбранную из исходного алфавита в дискретные промежутки времени kT, где k=1, 2, ... — счетные индексы. Если алфавит содержит конечное число символов, скажем N, говорят, что источник является конечным дискретным (finite discrete source). Примером такого источника является выход 12-битового цифро-аналогового преобразователя (один из 4096 дискретных уровней) или выход 10-битового аналого-цифрового преобразователя (один из 1024 двоичных 10-кортежей). Еще одним примером дискретного источника может послужить последовательность 8-битовых ASCII-символов, введенных с клавиатуры компьютера.

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

Если известно, что вероятность каждого символа Xj есть Р(Хj), можно определить самоинформацию (self-information) I(Xj) для каждого символа алфавита.

                           (13.1)

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

          (13.2)

где Е{Х} — математическое ожидание X. Энтропия источника определяется как среднее количество информации на выход источника. Энтропия источника — это средний объем неопределенности, которая может быть разрешена с использованием алфавита. Таким образом, это среднее количество информации, которое должно быть отправлено через канал связи для разрешения этой неопределенности. Можно показать, что это количество информации в битах на символ ограничено снизу нулем, если не существует неопределенности, и сверху log2(N), если неопределенность максимальна.

                          (13.3)

Пример 13.1. Энтропия двоичного источника

Рассмотрим двоичный источник, который генерирует независимые символы 0 и 1 с вероятностями р и (1 —р). Этот источник описан в разделе 7.4.2, а его функция энтропии представлена на рис. 7.5. Если р = 0,1 и (1 — р) = 0,9, энтропия источника равна следующему.

          (13.4)

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

Отметим, что первая причина, по которой кодирование источника работает, — это то, что информационное содержание N-символьного алфавита, используемое в действительных системах связи, обычно меньше верхнего предела соотношения (13.3). Известно, что, как отмечено в примере 7.1, символы английского текста не являются равновероятными. Например, высокая вероятность конкретных букв в тексте используется как часть стратегии игры Хенгмана (Hangman). (В этой игре игрок должен угадывать буквы, но не их позиции в скрытом слове известной длины. За неверные предположения назначаются штрафы, а буквы всего слова должны быть определены до того, как произойдет шесть неверных предположений.)

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

               (13.5)

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

                               (13.6)

Поэтому средняя на символ энтропия статистически независимого М-кортежа равна следующему.

          (13.7)

Говорят, что дискретный источник имеет память, если элементы источника, образующие последовательность, не являются независимыми. Зависимость символов означает, что для последовательности M символов неопределенность относительно M-го символа уменьшается, если известны предыдущие (М-1) символов. Например, большая ли неопределенность существует для следующего символа последовательности CALIFORNI_? M-кортеж с зависимыми символами содержит меньше информации или разрешает меньше неопределенности, чем кортеж с независимыми символами. Энтропией источника с памятью является следующий предел.

                          (13-8)

Видим, что энтропия М-кортежа из источника с памятью всегда меньше, чем энтропия источника с тем же алфавитом и вероятностью символов, но без памяти.

                  (13.9)

Например, известно, что при данном символе (или букве) "q" в английском тексте следующим символом, вероятно, будет "u". Следовательно, в контексте системы связи, если сказать, что буква "u" следует за буквой "q", то это дает незначительную дополнительную информацию о значении слова, которое было передано. Можно привести и другой пример. Наиболее вероятным символом, следующим за буквами "th", может быть один из таких символов: а, е, i, о, u, r и пробел. Таким образом, дополнение следующим символом данного множества разрешает некоторую неопределенность, но не очень сильно. Формальная формулировка сказанного выше: средняя энтропия на символ М-кортежа из источника с памятью убывает при увеличении длины М. Следствие: более эффективным является групповое кодирование символов из источника с памятью, а не кодирование их по одному. При кодировании источника размер последовательности символов, рассматриваемой как группа, ограничивается сложностью кодера, ограничениями памяти и допустимой задержкой времени.

Чтобы помочь понять цели, преследуемые при кодировании источников с памятью, построим простые модели этих источников. Одна из таких моделей называется Марковским источником первого порядка (first-order Markov source) [1]. Эта модель устанавливает соответствие между множеством состояний (или символов в контексте теории информации) и условными вероятностями перехода к каждому последующему состоянию. В модели первого порядка переходные вероятности зависят только от настоящего состояния. Иными словами, P(Xi+1|Xi, Xi-1, ...) = P(Xi+1|Xi). Память модели не распространяется дальше настоящего состояния. В контексте двоичной последовательности это выражение описывает вероятность следующего бита при данном значении текущего бита.

Пример 13.2. Энтропия двоичного источника с памятью

Рассмотрим двоичный (т.е. двухсимвольный) Марковский источник второго порядка, описанный диаграммой состояний, изображенной на рис. 13.1. Источник определен вероятностями переходов состояний Р(0|1) и P(l|0), равными 0,45 и 0,05. Энтропия источника Xэто взвешенная сумма условных энтропии, соответствующих вероятностям переходов модели.

Рис. 13.1. Диаграмма переходов от состояния к состоянию для Марковской модели первого порядка

            (13.10)

где

и

Априорная вероятность каждого состояния находится с помощью формулы полной вероятности.

Вычисляя априорные вероятности с использованием переходных вероятностей, получим следующее.

При вычислении энтропии источника с использованием равенства (13.10) получим следующее.

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

Пример 13.3. Коды расширения

Алфавит двоичного Марковского источника (пример 13.2) состоит из 0 и 1, появляющихся с вероятностями 0,9 и 0,1, соответственно. Последовательные символы не являются независимыми, и для использования преимуществ этой зависимости можно определить новое множество кодовых символов — двоичные 2-кортежи (коды расширения).

Двоичные 2-кортежи      Символ расширения     Вероятность символа расширения

Двоичные 2-кортежи

Символ расширения

Вероятность символа расширения

00

a

Р(а) = Р(0|0)Р(0) = (0,95)(0,9) = 0,855 11

11

b

Р(b) = Р(1| 1 )Р( 1) = (0,55)(0,1 ) = 0,055

01

c

Р(с) = Р(0| 1 )Р( 1) = (0,45)(0,1 ) = 0,045

11

d

Р(с) = Р(1| 0 )Р( 0) = (0,05)(0,9 ) = 0,045

Здесь крайняя правая цифра 2-кортежа является самой ранней. Энтропия для этого алфавита кодов расширения находится посредством обобщения равенства (13.10).

где Xk — расширение k-гo порядка источника X. Более длинный код расширения, использующий преимущества зависимости соседствующих символов, имеет следующий вид.

Двоичный 3-кортеж     Символ расширения     Вероятность символа расширения

Двоичные 2-кортежи

Символ расширения

Вероятность символа расширения

000

a

Р(а) = Р(0|00)P(00) = (0,95)(0,855) = 0,8123

100

b

P(b) = P(1|00)P(00) = (0,05)(0,855) =0,0428

001

c

P(с) = P(0|01)P(01) = (0,95)(0,045) = 0,0428

111

d

P(d) = P(1|11)P(11) = (0,55)(0,055) =0,0303

110

e

P(e) = P(1|10)P(10) = (0,55)(0,045) = 0,0248

011

f

P(f) = P(0|11)P(1 1) = (0,45)(0,055) =0,0248

010

g

P(g) = P(0|10)P(10) = (0,45)(0,045) = 0,0203

101

h

P(h) = P(1|01)P(01) = (0,05)(0,045) = 0,0023

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

Отметим, что энтропия односимвольного, двухсимвольного и трехсимвольного описаний источника (0,470, 0,412 и 0,408 бит, соответственно) асимптотически убывает к энтропии источника, равной 0,357 бит/входной символ. Напомним, что энтропия источника — это нижний предел в битах на входной символ для этого алфавита (память бесконечна), и этот предел не может быть достигнут с помощью кодирования конечной длины.




***** Яндекс.Поиск по сайту:



© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.