Анализ информации битового блока по количеству нулей и единиц в блоке
Среди методов анализа информации, в данной статье представлен анализ распределения плотности информации в битовом блоке данных. Данный метод может быть ориентиром при разработке методов сжатия информации, так как дает оценки как распределена плотность информации в зависимости от состава блока, который определяется количеством нулей и единиц, формирующих битовый блок данных.
Задан входной поток с длиной CT бит. Далее определяется количество нулей и единиц в блоке, тогда можно определить количество комбинаций которые задает данный набор нулей и единиц при заданной длине блока по формуле подсчета перестановок:
N=CT!/(K0! ·K1!) (1)
где
N — количество перестановок, определяющие количество комбинаций;
CT — длинна блока в битах, CT=K0+K1;
K1 — количество единиц в блоке;
K0 — количество нулей в блоке.
Данная формула определяет количество перестановок которые дают заданные количество нулей и единиц в битовом блоке.
Например, для 16 бит длины блока комбинации, представляются таблицей:
Таблица 1 — Информация блока длинной 16 бит
где
СТ — количество бит в блоке;
K0, K1 — количество нулей и единиц в блоке;
N — количество комбинаций, которые задают нули и единицы в блоке;
Log2(N) — двоичный логарифм, показывающий количество перестановок в битовом виде (данные в столбце округлены);
I% — процент от полного диапазона 2^CT, который занимают перестановки (данные в столбце округлены).
Для 32 бит длины блока оценка комбинации в таблице 2:
Таблица 2 — Информация блока 32 бита
где
СТ — количество бит в блоке;
K0, K1 — количество нулей и единиц в блоке;
N — количество комбинаций, которые задают нули и единицы в блоке;
Log2(N) — двоичный логарифм, показывающий количество перестановок в битовом виде (данные в столбце округлены);
I% — процент от полного диапазона 2^CT, который занимают перестановки (данные в столбце округлены).
Рисунок 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.
Вывод
На этих примерах и приемах можно построить сжатие в некоторых ситуациях для битового блока. И данный подход можно отнести к статистическим методам сжатия. Но в тоже время словарные методы тоже являются статистическими, но там часто повторяемые участки, хранятся в дополнительной памяти.
