Среди методов анализа информации, в данной статье представлен анализ распределения плотности информации в битовом блоке данных. Данный метод может быть ориентиром при разработке методов сжатия информации, так как дает оценки как распределена плотность информации в зависимости от состава блока, который определяется количеством нулей и единиц, формирующих битовый блок данных.

Задан входной поток с длиной CT бит. Далее определяется количество нулей и единиц в блоке, тогда можно определить количество комбинаций которые задает данный набор нулей и единиц при заданной длине блока по формуле подсчета перестановок:

N=CT!/(K0!·K1!) (1)

где

N — количество перестановок, определяющие количество комбинаций;

CT — длинна блока в битах, CT=K0+K1;

K1 — количество единиц в блоке;

K0 — количество нулей в блоке.

Данная формула определяет количество перестановок которые дают заданные количество нулей и единиц в битовом блоке.

Например, для 16 бит длины блока комбинации, представляются таблицей:

где

СТ - количество бит в блоке;

K0,K1 - количество нулей и единиц в блоке;

N - количество комбинаций, которые задают нули и единицы в блоке;

Log2(N) - двоичный логарифм, показывающий количество перестановок в битовом виде(данные в столбце округлены);

I% - процент от полного диапазона 2^CT, который занимают перестановки(данные в столбце округлены).

Для 32 бит длины блока оценка комбинации в таблице 2:

где

СТ - количество бит в блоке;

K0,K1 - количество нулей и единиц в блоке;

N - количество комбинаций, которые задают нули и единицы в блоке;

Log2(N) - двоичный логарифм, показывающий количество перестановок в битовом виде(данные в столбце округлены);

I% - процент от полного диапазона 2^CT, который занимают перестановки(данные в столбце округлены).

Данный график показывает, как распределена плотность информации в блоке длинной 32 бита и что основная часть информации в блоке распределена ближе к равенству количества нулей и единиц.

Оценка энтропии Шеннона и комбинаторного подхода

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

Например:

1)Для блока длинной 32 бита и количеством единиц 4: количество комбинаций будет 35960 это ~15,13 бит.

2)Для блока длиной 16 бита и количества единиц 2:

количество комбинаций будет 120 это ~ 6,91 бит.

И при этом вероятности равны:

p(1)(4,32)=4/32=0.125

p(1)(2,16)=2/16=0.125

Значит, по оценке энтропии Шеннона для первого и второго случая энтропия одинаковая, так как вероятности одинаковые. Но в тоже время, если учитывать длину блоков исходных данных, количество информации будет разным.

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

Анализ данных в битовом блоке и перестановки.

Блок длинной n бит содержит 2^n комбинаций, в данной статье приводится описание как в блоке информации длинной n бит распределена плотность информации в зависимость от количества нулей и единиц, которые формируют данный блок. В формуле (1) показано как оценить количество комбинаций которые формируются при заданной длине блока CT и количества составляющих нулей и единиц K0, K1. Показано, что максимальное количество комбинаций и значит плотность информации будет при K0=K1. И в отличии от подхода Шеннона, где количество информации характеризуется вероятностью появления символа, то в данном методе можно точно оценить количество информации для заданного входного блока бит.

И можно сделать вывод, что для битового блока длинной CT бит наиболее более плотное распределение информации при K0=K1 для K0+K1=CT.

Также можно сделать вывод, что количество комбинаций N для заданного K0,K1 меньше чем 2^CT. И значит, что если не было бы необходимости в хранении K0,K1 как исходных данных, то было бы возможно получать сжатие:

sz=(CT!/(K0!·K1!)) / (2^CT) (2)

И если в полном виде, то для сжатия можно сохранять информацию

K0,K1,NPR;

где K0-количество нулей в блоке,

K1-количество единиц в блоке,

NPR — номер перестановки из нулей и единиц для заданных K0,K1.

Функция преобразования битовой строки в номер перестановки

NPR=PR(CT,BSTR);

где

CT - длинна битовой строки BSTR,

BSTR — битовая строка,

NPR — номер перестановки.

Функция преобразования номера перестановки в битовую строку

BSTR=BS(K0,K1,NPR);

где

K0-количество нулей в блоке,

K1-количество единиц в блоке,

NPR — номер перестановки,

BSTR — битовая строка.

NPR будет лежать в диапазоне от 0 до CT!/(K0!·K1!) на чем можно получить сжатие в некоторых случаях.

И также можно задаться определенной длинной блока в кодере и декодере L, тогда, например, можно передавать только K1, а K0 получать по формуле K0=L-K1.

Вывод

На этих примерах и приемах можно построить сжатие в некоторых ситуациях для битового блока. И данный подход можно отнести к статистическим методам сжатия. Но в тоже время словарные методы тоже являются статистическими, но там часто повторяемые участки, хранятся в дополнительной памяти.

А также данный подход к оценкам, можно использовать как метод оценки количества информации в размерности количества перестановок и их изменениях.