Информационное описание дискретного источника

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

Любой дискретный источник характеризуется совокупностью символов. Совокупность символов образует алфавит. Каждый символ х,- описывается вероятностью его появления Р, и статистическими связями с другими символами алфавита - условными вероятностями р(х/12,...,х^), где N -

количество символов в алфавите источника. Информационное описание источника - это количество информации, содержащееся в каждом его символе. Интуитивно понятно, что количество информации должно быть пропорционально величине 1/Р{, т.е. чем меньше величина Р{, тем реже появляется этот символ, тем труднее предсказать его появление и тем самым выше количество информации, несомое этим символом. Однако в качестве количественной меры информации взята величина

Такое представление информации позволяет измерить ее в битах.

Величина средней информации на символ источника называется энтропией источника Н(х) и вычисляется в виде

где М- количество символов в алфавите.

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

Положим, что связь проявляется только между двумя последовательными символами сообщения. Это простейший вид связи. В более общем виде устанавливается связь между символом х, и предшествующими ему рядом, состоящим из «К» предшествующих символов. Такие модели называются Марковскими моделями К-го порядка.

Для Марковской модели второго порядка под количеством информации в символе ху понимается величина, /(х7 | х, )=-к^2 р(ху | х,) где

я(х |х; ) - вероятность появления символа х7 при условии, что перед этим

символом появился символ X,. Средняя информация на символ источника при условии, что в предыдущий момент времени появился символ X/, составит

где N - количество символов в алфавите источника. Величина #(х|х; ) называется условной энтропией источника, полная энтропия источника при этом равна

где P(Xj) - априорная вероятность появления символа х,-. В случае независимых символов р{х. | х,- )= р[х. ) и выражение (1.4) переходит в (1.1). Такой источник называется источником без памяти.

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

где Я- энтропия источника; М - количество символов в сообщении.

Максимальная энтропия, которой может обладать источник, определяется в случае, когда все символы источника взаимно независимы и обладают одинаковой вероятностью. При этом поскольку, /э/) = 1/Яиз выражений ( 1.1 ) и ( 1.2) следует

где N - количество символов алфавита источника. Если символы источника имеют не равные вероятности, то энтропия источника всегда

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

Пример 1. Пусть источник генерирует независимые равновероятные символы «а» и «/?». Р(а)=Р(Ь)=0,5. В этом случае энтропия источника равна

Я = 2-(0,54og22) = 1 бит/символ.

Если сообщение, положим, состоит из ста символов, то среднее количество информации, передаваемое от источника, составляет сто бит.

Пример 2. Пусть Р(а) = 0,1; Р(Ь) = 0,9. Энтропия источника в этом случае равна

Я = - (P(<2)-log2 Р{а) + P(b)-log2 P{b)) = 0,47 бит/символ.

Иными словами, при передаче ста символов среднее количество информации, передаваемое источником, равно 47 бит.

Пример 3. Допустим имеем двоичный источник, в котором символы связаны между собой вероятностями перехода Р(а/Ь) = 0,05 и Р{Ыа) = 0,45. Из выражений (1.3), (1.4) следует, что для данного примера

где хеа, Ь.

Априорные вероятности Р{а) и Р(Ь) находятся с помощью формул полной вероятности:

Вычисления по этим формулам дают:

В итоге из выражений (1.5) имеем: Н(х/а) = 0,993 бит/символ, Р(х/Ь) = 0,286 бит/символ и Н(х) = 0,357 бит/символ.

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

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

bbabaaabbbbbaaab.

Переопределим исходный алфавит источника, образовав новые символы а, р, у, 0 путем попарного объединения старых символов:

Найдем вероятности появления новых символов, и запишем их в табл. 1.1, учитывая, что априорные вероятности появления Р(а) = 0,1; Р(Ь) = 0,9. При составлении табл. 1.1 считается, что крайняя левая буква является первой по времени и что

Таблица 1.1. Пример переопределения алфавита источника

Символы нового алфавита У-(а, Д у в)

Вероятности новых символов

a = bb

P(a)=P(b)P(b/b)=0.9 0.95=0.855

(3= ab

Р( /3)= Р(а) Р(Ь/а)=0Л -0.45=0.045

у= аа

РГу) = Р(а)Р(а/а)=0.1-0.55=0.055

в- Ъа

Р(в) = Р(Ь) •Р(я/6)=0,9-0,05=0,045

Используя равенства (1.3) и (1.4), найдем энтропию нового алфавита

н(уу

где Н(у/а), Н(у/($), Н(у/у), Н(у/0) - условные энтропии нового алфавита.

Учитывая (1.7), находим Н(у) = 0,825 бит/новый символ. Поскольку новый символ состоит из двух старых, то для передачи исходного символа источника в среднем потребуется 0,412 бит.

При объединении символов исходного алфавита в тройки можно показать, что энтропия такого алфавита составит Н(г) = 1,223 или при пересчете к символам исходного алфавита Н{г) = 0,408 бит/исходный символ.

Таким образом, рассмотренные примеры показывают, что энтропии односимвольного, двухсимвольного, трехсимвольного алфавитов описания источника (0,47; 0,412; 0,408 бит/символ соответственно) последовательно убывают. Таким образом, обобщая сказанное, можно утверждать, что средняя энтропия алфавита на символ, состоящего из совокупности М - символов источника с памятью, убывает при увеличении длины М. Однако, средняя энтропия алфавита на символ источника не может быть меньше энтропии источника (в рассмотренном третьем примере энтропия источника составляет 0,357 бит/символ). Как следствие выше сказанного, более эффективным является групповое кодирование символов источника с памятью, а не кодирование их по одному. При кодировании источника размер последовательности символов, рассматриваемых как группа, ограничивается сложностью кодера, ограничениями памяти и допустимой задержкой информации во времени в процессе кодирования.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >