Оценка степени сжатия адресно-векторного кодирования

УДК 621.391

ОЦЕНКА СТЕПЕНИ СЖАТИЯ АДРЕСНО-ВЕКТОРНОГО КОДИРОВАНИЯ


И.А.Кулик, ассист.


Одним из основных показателей, характеризующих кодирование информационного источника, является качество кодирования. При этом  под показателем качества понимается избыточность кода [ 1 ].
В статье [ 2 ] рассматривался вопрос об избыточности адресно-векторного кодирования fav, но не были указаны области его рационального использования. Адресно-векторное кодирование заключается в переходе от векторного к адресному методу кодирования в зависимости от числа k логических единиц в n-разрядном слове. Такой переход осуществляется согласно системе неравенств
, ( 1 )
где = [ n / log2 n ].
Для оценки степени адресно-векторного сжатия возьмем в качестве модели бернуллиевский источник S={ai:ai=n, i=1,...,S}, характеризующийся тем, что появление логической единицы или нуля в двоичной записи ai является независимым событием. Источник Бернулли S хотя и представляет собой достаточно неточную модель реального источника, но для больших n является единственно приемлемым [3].
Рассмотрим три наиболее распространённых случая кодирования fav, для каждого из которых определим области рационального использования адресно-векторного кода, дающих коэффициент сжатия двоичных сообщений больше 1.
1 Адресно-векторное кодирование fav комбинаторного источника Sk={ aj : r(aj)=k, j=1,...,} равновесных комбинаций, где r(aj)- число логических единиц в aj.
Области рационального использования fav для таких источников определяются значениями k , при которых выполняются неравенства условия ( 1 ). В этом случае длины адресных последовательностей без учета служебных слов равны C(fav ,Sk)=k log2 n при 1 k < , или C(fav , Sk)=(n - k) log2 n , когда n - < k n - 1. Отсюда коэффициент сжатия источника Sk
( 2 )
Значение Ksh(Sk) не зависит от распределения вероятностей ð(ai), но, очевидно, зависит от длины n информационного сообщения и k единиц, содержащихся в нем. На рис. 1 приведен график зависимости Ksh(Sk)= =f(k) при n=256 и 1 k 36 . Стрелками ограничены области, когда Ksh(Sk)>1.

Рисунок 1 - График Ksh(Sk)=f(k) при n=256
2 Адресно-векторное кодирование fav вероятностного источника S={ ai :ai= n, i=1,... ,S}, имеющего более чем один класс Sk={ aj : r(aj)=k, j=1, ...,} эквивалентности по числу k логических единиц.
Рассматриваемый случай является общим по отношению к первому, так как здесь k - дискретная случайная величина. Для нахождения областей применения адресно-векторного метода, кроме параметров n и k векторов, необходимо знать распределение вероятностей Ðê появления числа k единиц, что и показывает выражение для стоимости адресно-векторного кода [ 2 ]. Отсюда, чтобы охарактеризовать степень сжатия источника S , следует найти математическое ожидание Ksh(S)=M[Ksh(ai)] коэффициента сжатия двоичного слова ai , то есть
. ( 2 )
У источника Бернулли S величина k имеет биномиальное распределение [ 4 ] , а вероятность ее появления находится в соответствии с выражением Ðê= ðk(1-p)n-k , где ð - вероятность появления двоичной единицы. Примем без доказательства следующее утверждение.

Утверждение 1.

Пусть вероятность, ограничивающая отклонение случайной величины k, P{k - mk } , где - заданное число, 0 < < 1, mk - среднее значение числа k. Тогда для бернуллиевского источника S область использования адресно-векторного кодирования , когда среднее значение Ksh(S)>1 с вероятностью 1- , задается системой неравенств вида
, ( 3 )
где n , ð - параметры информационного источника S.
На рис. 2 представлена графическая зависимость Ksh(S)=f(p) при n=256, где стрелками указаны точки пересечения графика с прямой Ksh(S)=1. Область рационального использования в этом случае

^ Рисунок 2 - График K( S)=f(p) при n=256.
.
3 Адресно-векторное кодирование двоичных сообщений aim от нескольких источников S1,..., Sm, ..., Sl.
Пусть множество Q = { S1, ..., Sm,..., Sl }, которое будем называть информационным потоком, состоит из бернуллиевских источников с различными вероятностями p1 ,..., pm ,..., ðl появления логических единиц. Вероятности p1 ,..., pm ,..., ðl в общем случае различны для источников и зависят от вида передаваемых данных. Очевидно, что разнородность передаваемой информации потока Q определяется распределением вероятностей p(S1),..., ð(Sm),..., ð(Sl) подключения к каналу связи источников S1,..., Sm,..., Sl , где p(S1)+...+ ð(Sm)+...+ ð(Sl)=1. В этом случае коэффициент Ksh(Q) сжатия потока определяется как математическое ожидание значений Ksh(Sm)
( 4 )
При наличии того же характера зависимости от n и чисел k единиц (см. формулу ( 2 )) у коэффициента сжатия появилась дополнительная зависимость от распределения вероятностей p(Sm), m=1,...,l ( 4 ). Примем без доказательства следующее утверждение.

Утверждение 2.

Пусть Q={S1,...,Sm,...,Sl}- информационный поток, состоящий из комбинаторных или бернуллиевских источников, которые генерируют двоичные n-разрядные слова с постоянным числом km единиц или с их математическими ожиданиями mkm соответственно и пусть имеется хотя бы один источник Sm, значения km или pm которого удовлетворяют условиям ( 1 ) или ( 3 ) адресно-векторного кодирования. Тогда при n коэффициент Ksh(Q) сжатия потока Q с распределением вероятностей ð(Sm), m=1,...,l асимптотически равен или больше 1 для любых ð(Sm)> 0.
В целях иллюстрации утверждения 2 рассмотрим случай адресно-векторного кодирования двух комбинаторных источников SÀ и SÂ , где p(SÀ) - вероятность подключения первого источника, а 1p(SÀ)- вероятность подключения второго источника. Условимся, что SÀ и SÂ порождают 256-разрядные двоичные комбинации, при этом все кодовые элементы SÀ содержат kA= 7 единиц, а источника SÂ - kB=128 . Условие адресно-векторного сжатия ( 1 ) для этого случая : 0 k < 32 или 225 < k 256 . Из выражения ( 4 ) коэффициент Ksh(Q) сжатия потока Q={SÀ, SÂ} имеет вид
Ksh(Q)= 4  p(SA) + 0,97  (1- p(SA)).
Решая неравенство Ksh(Q)> 1 относительно p(SA), обнаружим, что для его выполнения необходимо p(SA)> 0,01. А при n данная вероятность стремится к 0: p(SA) 0. Отсюда можно говорить о практической возможности сжатия для всех p(SA), отличных от 0 при больших n . Это означает, что для выполнения неравенства Ksh(Q)>1 при n необходимо и достаточно лишь присутствие в потоке Q сообщений от источника, заведомо удовлетворяющего неравенствам ( 1 ), то есть в данном примере источника SÀ .
В заключение по результатам оценки эффективности сжатия информационных источников адресно-векторным методом можно сделать следующие выводы.
1 Чтобы увеличить среднее значение Ksh(S) коэффициента сжатия двоичных слов бернуллиевского источника необходимо, с одной стороны, увеличить разрядность n сжимаемых комбинаций, а с другой - уменьшить вероятность ð появления единиц в них ( 2 ).
2 Для того чтобы средний коэффициент Ksh(Q) сжатия потока Q , состоящего из сообщений комбинаторных и бернуллиевских источников S1,..., Sm,..., Sl, был больше 1, достаточно существование хотя бы одного источника ( точнее, существование его с очень малой вероятностью ), удовлетворяющего условию ( 3 ).
3 Чтобы увеличить коэффициент Ksh(Q) сжатия информационного потока Q={ S1,..., Sm,..., Sl }, необходимо: а) увеличить число источников потока, удовлетворяющих условиям ( 1 , 3 ); б) увеличить вероятности подключения таких источников к каналу связи; в) увеличить коэффициенты Ksh(ai) сжатия сообщений или их средние значения Ksh(S) по отдельности для каждого источника.

SUMMARY


Estimating of the address-vector compression method is carried out in this article. Address-vector coding is analysed for three wide-distributed cases : the first is when coding a combinatorial source, the second is when coding a Bernoulli source, and the third is when coding a set of the combinatorial and Bernoulli sources. For all the considered cases the conditions of the compression are given.

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


1. Кричевский Р. Е. Сжатие и поиск информации. Москва: Изд-во Радио и связь, 1989.- 168 с.
2. Кулик И. А. Об избыточности адресно-векторного кодирования // Вестник Сумского государственного университета, 1996, № 1(5).-C.90-93.
3. Борисенко А. А. О разложении бернуллиевских источников // Вестник Сумского государственного университета, 1995, № 3.-C. 57-59.
4. Вентцель Е. С., Овчаров Л. А. Теория вероятностей и ее приложения. - Москва: Изд-во Наука, 1988. - 480 с.
Поступила в редколлегию 3 октября 1996 г.Добавить документ в свой блог или на сайт
voprosi-dlya-samostoyatelnogo-izucheniya-rabochaya-programma-po-nevrologii-i-psihiatrii-dlya-specialnosti-040800-kvalifikaciya.html
voprosi-dlya-samostoyatelnogo-kontrolya-konspekt-lekcij.html
voprosi-dlya-samostoyatelnoj-ocenki-kachestva-osvoeniya-disciplini-socialnaya-psihologiya.html
voprosi-dlya-samostoyatelnoj-podgotovki-i-terminologiya-uchebnaya-disciplina-patologicheskaya-anatomiya-i-sudebnaya-veterinarnaya.html
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат