Среди методов анализа информации, в данной статье представлен анализ распределения плотности информации в битовом блоке данных. Данный метод может быть ориентиром при разработке методов сжатия информации, так как дает оценки как распределена плотность информации в зависимости от состава блока, который определяется количеством нулей и единиц, формирующих битовый блок данных.
Задан входной поток с длиной 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, который занимают перестановки(данные в столбце округлены).
Анализ данных в битовом блоке и перестановки.
Блок длинной 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.
Вывод
На этих примерах и приемах можно построить сжатие в некоторых ситуациях для битового блока. И данный подход можно отнести к статистическим методам сжатия. Но в тоже время словарные методы тоже являются статистическими, но там часто повторяемые участки, хранятся в дополнительной памяти.
Автор: eevg
