Анализ информации битового блока по количеству нулей и единиц в блоке

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

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

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

где

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

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

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

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

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

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

Таблица 1 — Информация блока длинной 16 бит

Таблица 1 — Информация блока длинной 16 бит

где

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

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

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

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

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

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

Таблица 2 — Информация блока 32 бита

Таблица 2 — Информация блока 32 бита

где

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

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

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

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

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

Рисунок 1 - График распределения количества комбинаций в 32х битном блоке в зависимости от количества единиц в 32х битном блоке.

Рисунок 1 — График распределения количества комбинаций в 32х битном блоке в зависимости от количества единиц в 32х битном блоке.

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

Блок длинной 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.

Вывод

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

© Habrahabr.ru