О разложении конечного бернуллиевского источника многозначных последовательностей

О РАЗЛОЖЕНИИ КОНЕЧНОГО БЕРНУЛЛИЕВСКОГО

ИСТОЧНИКА МНОГОЗНАЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

А.А. Борисенко, проф.

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

Основное место в теории сжатия занимает задача оптимального кодирования источников сообщений. Они делятся на два класса - комбинаторные и вероятностные. Вероятностные источники в отличие от комбинаторных должны иметь хотя бы два сообщения, отличающиеся друг от друга неравными нулю величинами своих вероятностей. Если при этом вероятности генерируемых знаков в сообщениях источника не зависят от значений предыдущих знаков, то такой источник называется бернуллиевским [1]. Этот источник сравнительно грубо моделирует реальные процессы генерирования информации, но в силу своей эффективности и простоты довольно широко распространен на практике.

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

Рассмотрим обычный конечный стационарный вероятностный бернуллиевский источник, для которого дан алфавит букв сообщений

А=а₁, а₂,..., а_i,..., а_к,

генерируемых источником А, с вероятностями соответственно

(a₁),(a₂),...,(a_i),...,(a_k),

образующими последовательности (слова)

L= (l₁, l₂,..., l_n), lA, =1,2,..., n.

Для такого источника вероятность любой буквы l_i в последовательности L_j не зависит от ее местоположения и предшествующих ей букв и не изменяется в течение неопределенно долгого времени.

Энтропия источника А^*

H(А^*)=log₂P_j, (1)

где P_{j -} вероятность генерирования источником А^* последовательности L_j букв a_i A, j=1,2,...,kⁿ.

Каждая последовательность L_j содержит в определенном порядке r₁ букв а₁, r₂ - букв а₂ и т.д. до r_k букв a_k. При этом

.

Вероятность ее генерирования

P_j = ^r1(a₁) ^r2(a₂) ... ^ri(a_i) ... ^rk(a_k). (2)

Для бернуллииевского источника число последовательностей L_j с вероятностью P_j будет ровно столько, сколько перестановок с повторениями можно получить из r₁, r₂, ..., r _k букв:

П(r ₁, r ₂, ... , r _k) = , (3)

r ₁ 0, r ₂ 0,..., r _i 0,..., r _k 0; r ₁+ r ₂+ ... + r _k = n.

При этом выбор признака множества слов, задаваемого значениями r₁,

r ₂,..., r _k , будет происходить с вероятностью

r₁,r₂,..., r _k = Р_j П(r₁,r₂,...,r _k)= . (4)

Выбор слова L_j уже с этого множества будет происходить с вероятностью

Р_j r₁,r₂,...,r _k = .(5)

Теорема. Энтропия H(А^*) вероятностного стационарного бернуллиевского источника А^* равна сумме энтропий вероятностного бернуллиевского источника В:

Н(В)= log₂ r₁,r₂,...,r _k ,(6)

r_i 0

генерирующего последовательности чисел r₁, r₂,..., r_k, и энтропии комбинаторного источника А:

Н(А В)= log₂ П(r₁,r₂,...,r_k), (7)

т.е. требуется доказать, что

H(А^*) = Н(А В)+Н(В) . (8)

Доказательство. Если источник А^* выдал слово длиной n, то путем элементарного подсчета легко определяются числа r₁, r₂,..., r _k , содержащихся в нем букв a₁, a₂,..., a_к и соответственно с помощью формул (2,4) вычисляется его энтропия Н(В).

Энтропия источника А, при условии, что от источника В получены значения чисел r₁, r₂,..., r _k букв в генерируемом источником А^* слове, равна

Н(А В)= ??H_j r₁,r₂,...,r _k , (9)

r_i 0

где

H_j r₁,r₂,...,r _k = ? r₁,r₂,...,r_k log₂ Р_j r₁,r₂,...,r _k- (10)

энтропия слов L_j, входящих во множество, состоящее из слов, содержащих r₁, r₂,..., r _k букв a₁, a₂,..., a_к .

В соответствии с (5)

H_j r₁,r₂,...,r _k =? х

х = log₂ П(r₁,r₂,...,r_k).

Тогда

Н(А В)= ?log₂ П(r₁,r₂,...,r _k) . (11)

r_i 0

Энтропия объединения

H(А,В) = Н(А В)+Н(В) =

= ?log₂ П(r₁,r₂,...,r _k) ?

r_i 0

?log₂ r₁,r₂,...,r _k =

r_i 0

= ?log₂ Р_j .

r_i 0

Так как каждому значению r₁,r₂,...,r_k соответствует П(r₁,r₂,...,r _k) вероятностей Р_j источника А^*, то

Н(А В)+Н(В)= log₂ Р_j = H(А^*). Теорема доказана

Следствием теоремы является предлагаемый ниже метод оптимального кодирования сообщений равномерными кодами. Его первым шагом является выделение с источника А^* источника В.

Процедура построения источника В состоит в подсчете значений r₁,r₂,...,r _k в генерируемых источником А^* последовательностях букв L. Тем самым определяется класс эквивалентности, к которому относится та или иная генерируемая последовательность L_i, и формируется источник А. Этот класс содержит П(r₁,r₂,...,r_k) последовательностей L, и поэтому полученный источник А генерирует последовательности с вероятностями равными 1/ П(r₁,r₂,...,r _k).

Вторым шагом рассматриваемого метода будет оптимальное кодирование равномерных сообщений источника В одинаковой длины любым известным методом, например, одним из методов нумерационного кодирования [2].

Третий шаг содержит оптимальное кодирование вероятностного источника В одним из известных алгоритмов оптимального неравномерного кодирования [3], для чего нужно определить вероятности r₁,r₂,...,r_k векторов (r₁,r₂,...,r _k).

Четвертый шаг состоит в формировании результирующего сжатого отображения, генерируемой источником А последовательности, что производится путем объединения последовательностей букв от источника А и В в одну последовательность.

В случае К=2 П(r₁, r₂,..., r_k) = П(r₁, r₂) =.

Это значит, что рассматриваемый метод является обобщением соответствующего метода для сжатия двоичных последовательностей [4].

Особенностью предлагаемого метода оптимального кодирования сообщений путем разложения исходного источника А^* на взаимозависимые А и В является то, что влияние источника В с увеличением длины кодируемых сообщений снижается и теоретически при n им можно пренебречь. Тогда эффективность сжатия (оптимального кодирования) будет определяться только эффективностью кодирования источника А, которая при соответствующем распределении вероятностей r₁,r₂,...,r_k может достигать больших значений.

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

SUMMARY

The method of optimum coding of discrete sources of information by means of source decomposition into two mutually complemental ones, one of which determines the letters” number in sequenses, generated by the basic source,and the other one determines the coded messages, which take into account these numbers , is suggested.

Such decomposition gives an opportunity to present one probability source by two sources, one of which is compound , and accordingly to apply a structural methods of information compression for even codes.

СПИСОК ЛИТЕРАТУРЫ

Кричевский Р.Е. Сжатие и поиск информации. -М.: Радио и связь, 1989.- 268 с.

Амелькин В.А. Методы нумерационного кодирования.- Новосибирск: Наука, 1986.- 158 с.

Кузмин И.В., Кедрус В.А. - К.: Вища шк., 1986.- 238 с.

Борисенко А.А. О разложении бернуллиевских источников информации // Вiсник Сумського державного університету.- 1995.-№3. - С. 57-59.