Вы нашли то, что искали?
Главная Разделы

Добавить страницу в закладки ->
Обязательно посмотрите энциклопедию:

Радиоэлектроника, Схемы радиолюбителям


13.1.1. Дискретные источники. Теоретические основы цифровой связи

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

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
Электронная техника, радиотехника и связь. Лекции для преподавателей и студентов. Формальные, технические, естественные, общественные, гуманитарные, и другие науки. Карта сайта

Новосибирск, Екатеринбург, Москва, Санкт-Петербург, Нижний Новгород, Ростов-на-Дону, Чебоксары.

E-mail: formyneeds@yandex.ru