С В Костель, Е М Скордина, И А Кулик - Определение ограничений для метода биномиального нумерационного сжатия - страница 1

Страницы:
1  2  3 

УДК 519.677

ОПРЕДЕЛЕНИЕ ОГРАНИЧЕНИЙ ДЛЯ МЕТОДА БИНОМИАЛЬНОГО НУМЕРАЦИОННОГО СЖАТИЯ

И.А. Кулик, канд. техн. наук, доцент; С.В. Костель, ассистент; Е.М. Скордина, аспирант,

Сумский государственный университет, г. Сумы

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

Ключевые слова: биномиальное нумерационное кодирование, биномиальный коэффициент, метод наименьших квадратов, коэффициент корреляции.

У статті розглядаються граничні умови для методу біноміального нумераційного стиснення, при яких виконується стиснення інформації. Наводиться доказ існування обмежень щодо кількості одиниць залежно від розміру двійкового повідомлення. Пропонуються співвідношення для знаходження граничного значення числа одиниць.

Ключові слова: біноміальне нумераційне кодування, біноміальний коефіцієнт, метод найменших квадратів, коефіцієнт кореляції.

ПОСТАНОВКА ПРОБЛЕМЫ В работах [1,2] был рассмотрен метод сжатия, основанный на использовании биномиальных чисел. В данном методе сжатия используется нумерационное кодирование с использованием биномиальной числовой функции [3,4]. Нумерационное кодирование преобразует двоичную равномерную последовательность A , состоящую из n битов, в двоичную последовательность B, состоящую из

 

l(k) = \log2 (n + 1)1 + [Zog2 (C' )] (1)

 

двоичных разрядов.

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

 

\log2 (n + 1)1 + \log2 (Ck )]< n. (2)

 

Для случая, когда

 

[log2 (n + 1)l + [log2 (Ck )]= n , (3)

 

сжатие не происходит. Закодированная двоичная последовательность B будет иметь ту же длину, что и исходная A. При выполнении условия

 

\l0g2 (n + 1)1 + \l0g2 (C )1> n (4)нумерационное кодирование при помощи биномиальных чисел будет вносить избыточную информацию, и количество битов в закодированном сообщении B будет превышать количество битов исходного сообщения A.

Поскольку число разрядов n в исходной последовательности A величина постоянная, то возникает задача определения числа единиц k в сообщении, при котором выполняется условие (2) и происходит сжатие информации.

ИСХОДНЫЕ ДАННЫЕ К ИССЛЕДОВАНИЮ Покажем,  что  для  всякого  натурального   n є N   и  целого   k є 0, n справедливо неравенство

 

log2 (ЄЩ )< n . (5)

 

Поскольку функция log2 (x) является положительной и непрерывно возрастающей, можно переписать неравенство (5) в виде

Ck < 2n . (6) Воспользовавшись свойством биномиальных коэффициентов [4]

n

n

2n , (7)

k=0в результате получим очевидное неравенство

 

Єї <£ Єї , (8)

k=0

которое подтверждает истинность неравенства (5). Соотношение

 

T(k) = \log2 (Єї)] (9)

 

определяет количество битов, необходимое для хранения номера двоичной последовательности A длиной n разрядов с количеством k единиц при использовании метода биномиального нумерационного кодирования. Исходя из (5), можно записать, что

 

"log2 (Ck )]< n . (10)

 

Неравенство (10) будет выполняться для всех натуральных n > 2 и

целых k є 0,n. Таким образом, при помощи биномиального нумерационного кодирования можно сжимать равновесные комбинации заданной длины n с постоянным весом k.

Теперь покажем, что для всякого натурального n є N , n > 1 будет справедливо неравенство

log2 (n +1) + log2 (CnJ2 )> n .


(11)

Взяв антилогарифм от обеих частей неравенства (11), получим

(n +1)- Cn2 > 2n . (12) Левую часть неравенства (12) перепишем в виде

 

(n +1)- Cf =2 Cf, (13)

k=0

а правую часть неравенства (12) перепишем в соответствии с (7). В результате получим неравенство

 

2 CJ2 >2 Ck . (14)

к=0 к=0

 

Поскольку СП2 > СП , неравенство (14), а следовательно и неравенство (11), выполняется для всех натуральных n є N , n > 1. Соотношение

 

[log2 (n + 1)] + [log2 (Cl2 )]> n (15)

 

так же верно, поскольку операция округления вверх только увеличивает значения величин в левой части неравенства.

Если     в     формуле     (1)     использовать     минимальное значение

биномиального   коэффициента    CJ,   которое   соответствует значению

параметра к = 0 или к = n , то для всех натуральных n > 1 будет выполняться следующее неравенство:

 

[log2 (n + 1)] + [log2 (С°п )]< n , (16)

 

или

|~log2 (n +1)] < n .

Проанализировав неравенства (5), (15) и (16), приходим к выводу, что функция (1) имеет точки пересечения с линией f (k) = n .

Учитывая, что функция для биномиального коэффициента симметрична   относительно   точки   k = n/ 2   и   согласно   со свойством

симметрии биномиальных коэффициентов (Cn = Cn~k), точек пересечения

Страницы:
1  2  3 


Похожие статьи

С В Костель, Е М Скордина, И А Кулик - Определение ограничений для метода биномиального нумерационного сжатия