О средней длине двоичных биномиальных чисел

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

О средней длине двоичных биномиальных чисел

И.А. Кулик, канд. техн. наук, доц.

Постановка проблемы

Одним из существенных критериев выбора метода кодирования является его сложность, определяемая сложностными характеристиками кодирующих и декодирующих алгоритмов: быстродействием, объемом требуемой памяти, объемом программных и/или аппаратных затрат. Очевидно, что предпочтение получает тот метод кодирования, который при той же эффективности решаемой задачи - защиты информации или ее сжатия - обеспечивает меньшую сложность кодирования. Существуют методы биномиального кодирования, основанные на неравномерных линейных биномиальных числах, не уступающие, а в некоторых случаях превосходящие по эффективности многие широко известные помехоустойчивые или экономичные коды [1, 2]. Распространению биномиальных кодов препятствует неизученность целого ряда свойств двоичных биномиальных чисел. В частности, неисследованным является вопрос о средней длине неравномерных биномиальных чисел, решение которого позволит разработать более четкий и математически строгий механизм оценки сложностных характеристик алгоритмов биномиального кодирования/декодирования и, следовательно, обеспечит более объективный подход к сравнению биномиальных кодов с уже известными кодами.

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

определение средней кодовой длины неравномерных биномиальных чисел, генерируемых комбинаторным источником;

определение средней кодовой длины неравномерных биномиальных чисел, генерируемых вероятностным источником Бернулли.

1. Средняя арифметическая длина неравномерных биномиальных чисел

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

Пусть комбинаторный источник генерирует двоичные линейные неравномерные биномиальные числа с параметрами и , где - переменная длина чисел,

, , [1,2].

Числа должны удовлетворять следующим кодообразующим ограничениям

(1)

и

, (2)

а их десятичный эквивалент определяется числовой функцией

,

где .

Согласно [2] ограничения (1, 2) разбивают числа на два непересекающихся класса и , , . Первый класс содержит единиц и нулей, , а второй - нулей и единиц, .

Теорема 1. Средняя арифметическая длина чисел , для заданных и равна

.(3)

Доказательство. Среднее арифметическое длин , чисел определяется как

,(4)

где - общее количество биномиальных чисел, ;

- количество биномиальных чисел разрядности .

Следуя разложению множества неравномерных биномиальных чисел на два класса и , выражение (4) можно представить следующим образом:

,(5)

где и - количества биномиальных чисел длины , относящихся к первому и второму классам соответственно, и .

Для класса биномиальных чисел согласно ограничению (1) и лемме 2 [2]

, , .(6)

Для класса биномиальных чисел согласно ограничению (2) и лемме 3 [2]

, , .(7)

Первая сумма выражения (5) с учетом (6) принимает вид

.

Вторая сумма выражения (5) с учетом (7) принимает вид

.

Используя формулу суммирования биномиальных коэффициентов [3]

,

получим

,

.

В результате при общем числе двоичных биномиальных чисел с параметрами и - [2] выражение (5) среднего арифметического длин биномиальных чисел примет вид

.

Далее, путем вынесения множителя из числа сочетания и множителя из числа сочетания получаем

что и требовалось доказать.

Отметим, что с точки зрения вероятностного подхода к моделированию информационных источников значение , представленное теоремой 1 (3), относится к случаю, когда вероятности появления неравномерных биномиальных чисел равны между собой. Следовательно, информационная нагрузка на каждое такое число является максимальной. Величина такой нагрузки определяется энтропией комбинаторного источника [4]

.

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

бита/разряд,

т.е. несмотря на равновероятность неравномерных биномиальных чисел, их разряды являются недогруженными.

2. Среднее взвешенное по вероятности значение длины неравномерных биномиальных чисел

Более общим случаем задачи об определении средней длины биномиальных чисел является задание на множестве вероятностной меры. В этом случае имеют дело с вероятностными источниками информации. С точки зрения практики наибольший интерес представляет источник информации Бернулли [4]. В двоичном случае данный источник характеризуется тем, что появление нулей и единиц не зависит друг от друга. Использование источника Бернулли в качестве модели реальных источников оправдано прежде всего тем фактом, что при больших разрядностях генерируемых слов размерность решаемых информационных задач остается пропорциональной , а точность моделирования при этом остается достаточно высокой.

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

. (8)

Класс биномиальных чисел , , [2], удовлетворяющих ограничению (1), разбивается на подклассы по количеству принадлежащих двоичных нулей , :

, . (9)

Класс биномиальных чисел , , [2], удовлетворяющих ограничению (2), разбивается на подклассы по количеству принадлежащих двоичных единиц , :

, .(10)

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

.(11)

Доказательство. В соответствии с условием теоремы длина представляет собой случайную величину, принимающую значения от до . Следовательно, среднее значение длины биномиального числа есть математическое ожидание соответствующей случайной величины . Вероятность возникновения длины совпадает с вероятностью появления неравномерного биномиального числа (8). Таким образом

,(12)

где - мощность множества неравномерных биномиальных чисел.

Биномиальные числа (9), имеют одинаковую длину и поскольку их количество . Биномиальные числа (10), также имеют одинаковую длину и поскольку , их количество . Учитывая вышесказанное и вероятности (8), слагаемые в выражении (12) группируем по принадлежности биномиальных чисел подклассам и :

(13)

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

,

что и требовалось доказать.

Для частного случая среднее значение длины неравномерных биномиальных чисел , генерируемых источником информации Бернулли:

.(14)

Теорема 3 Для источника информации Бернулли, генерирующего неравномерные биномиальные числа длины , :

,

когда .

Доказательство. Чтобы определить энтропию для , необходимо использовать известное выражение общего вида для энтропии бернуллиевского источника информации [4] и сгруппировать в нем суммируемые слагаемые по принадлежности подклассам и :

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

.(15)

Согласно условию теоремы , тогда из (15) следует

Сравнивая полученный результат с (14), приходим к выводу, что при , что и требовалось доказать.

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

Заключение

Полученные в разделах 1, 2 соотношения (3, 11) количественно определяют одну из важных характеристик линейных неравномерных биномиальных чисел - их среднюю длину в зависимости от параметров чисел (т.е. соответствующей системы счисления) и параметров источников информации, которые их генерируют. На основе (3, 11) возможна разработка математически более строгих способов оценки сложностных характеристик алгоритмов биномиального кодирования и декодирования, а также получение эффективных способов решения ряда практически важных задач, к числу которых относятся определение степени сжатия нумеруемых биномиальными числами исходных двоичных последовательностей; нахождение информационной избыточности биномиальных чисел и информационной нагруженности их разрядов; определение средней скорости передачи информации, выраженной линейными биномиальными числами, и т.д.

SUMMARY

In the paper the average length of uneven linear binomial numbers is determined for two cases. The first case is that the numbers are generated by a combinatory information source, the second one - the numbers are generated by Bernoulli's information source. The obtained estimations give an opportunity to develop rigorous methods of comparative analysis of binomial codes.

СПИСОК ЛИТЕРАТУРЫ

1. Борисенко А.А. Введение в теорию биномиального счета: Монография. - Сумы: ИТД "Университетская книга", 2004. - 88 с.

2. Борисенко А.А. Биномиальный счет. Теория и практика: Монография. - Сумы: ИТД "Университетская книга", 2004. - 170 с.

3. Кнут Д. Искусство программирования для ЭВМ: Основные алгоритмы. - М.: Изд-во "Мир", 1976. - Т.1. - 736 с.

4. Кричевский Р.Е. Сжатие и поиск информации. - М.: Радио и связь, 1989. - 168 с.