Удк 621 037. 37 О средней длине двоичных биномиальных чисел icon

Удк 621 037. 37 О средней длине двоичных биномиальных чисел




Скачати 90.86 Kb.
НазваУдк 621 037. 37 О средней длине двоичных биномиальных чисел
Дата14.07.2012
Розмір90.86 Kb.
ТипДокументи

УДК 621.3.037.37


О СРЕДНЕЙ ДЛИНЕ ДВОИЧНЫХ БИНОМИАЛЬНЫХ ЧИСЕЛ


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

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


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

Одним из существенных критериев выбора метода кодирования является его сложность, определяемая сложностными характеристиками кодирующих и декодирующих алгоритмов: быстродействием, объемом требуемой памяти, объемом программных и/или аппаратных затрат. Очевидно, что предпочтение получает тот метод кодирования, который при той же эффективности решаемой задачи – защиты информации или ее сжатия – обеспечивает меньшую сложность кодирования. Существуют методы биномиального кодирования, основанные на неравномерных линейных биномиальных числах, не уступающие, а в некоторых случаях превосходящие по эффективности многие широко известные помехоустойчивые или экономичные коды [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 с.


Поступила в редакцию 23 декабря 2004г.

Схожі:

Удк 621 037. 37 О средней длине двоичных биномиальных чисел iconСредняя длина двоичных биномиальных чисел произвольного диапазона кулик И. А., к т. н доц. Сумский государственный университет
И если задача вычисления средней длины указанных чисел для полного диапазона биномиальной системы счисления с параметрами и автором...
Удк 621 037. 37 О средней длине двоичных биномиальных чисел iconСмкэс-2004
Известны системы ограничений для двоичных биномиальных чисел, полученные на основе структурного подхода. Данные системы ограничений...
Удк 621 037. 37 О средней длине двоичных биномиальных чисел iconМетоды сжатия и защиты информации на основе биномиальных кодов борисенко А. А., д т. н., проф. Сумский государственный университет е-mail electron@sumdu edu ua
Диапазон этих систем счисления также представляет биномиальный коэффициент. Известно, что множество всех двоичных чисел длины n можно...
Удк 621 037. 37 О средней длине двоичных биномиальных чисел iconУдк 621. 038 Сжатие кодов с постоянным весом на основе биномиальных чисел
Сумский филиал Национального университета внутренних дел, e- mail chered ukr@ukr net
Удк 621 037. 37 О средней длине двоичных биномиальных чисел iconСложение двоичных чисел Таблица сложения двоичных чисел
Сложение выполняем поразрядно, начиная с младшей цифры. Если получается больше 1, то записывается 0 и 1 добавляется к старшему разряду...
Удк 621 037. 37 О средней длине двоичных биномиальных чисел iconУдк 621 037. 37 Практика биномиального счета
Владение на практике биномиальным счетом позволит более эффективно решать различные переборные задачи, имеющих значение в задачах...
Удк 621 037. 37 О средней длине двоичных биномиальных чисел iconМетод сжатия двоичных сообщений на основе многозначных биномиальных чисел и устройство для его реализации т. А. Протасова, ст преп
Под сжатием информации понимают операцию, в результате которой данному коду или сообщению ставится в соответствие более короткий...
Удк 621 037. 37 О средней длине двоичных биномиальных чисел iconСвойство вложенности двоичных биномиальных систем счисления и. А. Кулик, канд техн наук, доц
С точки зрения практики это позволит, например, разработать адаптивные алгоритмы передачи данных на основе биномиальных кодов
Удк 621 037. 37 О средней длине двоичных биномиальных чисел iconСжатие двоичных кодов на основе биномиальных чисел
Для сжатия равновесных кодов ранее были предложены простые алгоритмы, кото­рые несложно реализовать аппаратными средствами. При этом...
Удк 621 037. 37 О средней длине двоичных биномиальных чисел iconУдк 681. 518 Алгоритмы нумерации двоичных чисел с помощью биномиального счёта
Они способны дать больший коэффициент сжатия информации, позволяющий в процессе сжатия находить ошибки используя для этого ключи,...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи