Свойство вложенности двоичных биномиальных систем счисления

Свойство вложенности двоичных биномиальных систем счисления

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

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

- способность порождать различные комбинаторные объекты.

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

, (1)

, (2)

, , , ,

, , , ,

,

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

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

Также рассматриваемые в данной работе вопросы имеют и практическое значение, поскольку их решение позволяет разработать методы и алгоритмы адаптивной (к числу ошибок в дискретном канале) передачи информации на основе биномиальных чисел (кодов) [4]. Адаптивное изменение параметров биномиальных систем счисления и переход к биномиальным числам (кодам) меньшей или большей размерности на основе свойства вложенности позволяет обеспечивать оптимальным соотношение «скорость / верность передачи».

Таким образом, целями данной работы являются:

1) разработка новых методов генерирования сочетаний двоичных единиц по разрядам на основе сочетаний меньшей или большей размерности;

2) дальнейшее исследование взаимозависимости различных биномиальных систем счисления между собой.

При этом решаемые задачи формулируются следующим образом:

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

, , (3)

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

- число двоичных единиц в биномиальных числах , ;

- уровня вложенности , источником которой является подкласс уровня вложенности ;

- уровня вложенности , источником которой является подкласс уровня вложенности ;

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

2. Определить аналитическую связь между параметрами и для и параметрами и для при двух возможных случаях (3).

Все двоичные биномиальные -разрядные числа , , системы счисления уровня вложенности заканчиваются разрядом . Соответственно разряд в записи чисел из подкласса является избыточным, поэтому возможно его исключение. Избыточность разряда обосновывается тем, что:

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

б) при той же мощности исключение приводит к меньшей избыточности.

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

.

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

Следует отметить, что

, (4)

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

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

Тогда с учетом (4) для рассматриваемого случая можно записать

,

,

,

.

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

1 [Установка номера разряда - преобразуемой комбинации, числа двоичных единиц в комбинации (кумулятивное, суммирующее значение), временную переменную в нулевое значение]:

, , .

2 [Ввод параметров и исходной и исходного подкласса ]:

, , .

3 [Ввод двоичного биномиального числа ]:

.

4 [Формирование равновесной комбинации , где «- -» - операция разбиения]: .

5 [Вычисление параметров и вложенной ]:

,

.

6 [Инкрементация номера разряда равновесной комбинации]:

.

7 [При число двоичных единиц всегда равно нулю].

Если , то переход к шагу 9.

8 [Вычисление кумулятивного значения числа единиц в равновесной комбинации ]:

.

9 [Проверка условия ].

Если , то переход к шагу 12.

10 [Формирование двоичного биномиального числа , где «++» - операция конкатенации):

.

11 Безусловный переход к шагу 6.

12 [Вывод полученного числа вложенной системы счисления ]:

.

13 Останов.

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

, (5)

где - функция кодового отображения:

; (6)

- функция преобразования в соответствующую равновесную комбинацию ;

- алгоритм (последовательность операций), обеспечивающий выполнение .

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

Все двоичные биномиальные -разрядные числа , , системы счисления уровня вложенности заканчиваются разрядом . Соответственно разряд является в записи чисел избыточным, поэтому возможно его исключение. Избыточность разряда обосновывается тем, что:

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

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

.

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

С учетом (4) для данного случая можно записать:

,

,

,

.

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

1 [Установка номера разряда преобразуемой комбинации, числа двоичных единиц в комбинации (кумулятивное значение), временную переменную в нулевое значение]:

, , .

2 [Ввод параметров и исходной и исходного подкласса ]:

, , .

3 [Ввод двоичного биномиального числа ]:

.

4 [Формирование равновесной комбинации , где «- -» - операция разбиения]:

.

5 [Вычисление параметров и вложенной ]:

,

.

6 [Инкрементация номера разряда равновесной комбинации]:

.

7 [При число двоичных единиц всегда равно нулю].

Если , то переход к шагу 9.

8 [Вычисление кумулятивного значения единиц в равновесной комбинации ]:

.

9 [Проверка условия ].

Если , то переход к шагу 12.

10 [Формирование двоичного биномиального числа , где «++» - операция конкатенации):

.

11 Безусловный переход к шагу 6.

12 [Вывод полученного числа вложенной системы счисления ]: .

13 Останов.

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

, (7)

где - функция кодового отображения:

; (8)

- функция преобразования в соответствующую равновесную комбинацию ;

- алгоритм (последовательность операций), обеспечивающий выполнение .

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

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

, (9)

а для вложенной

. (10)

Заключение

Рассмотренное в данной работе свойство вложенности двоичных биномиальных систем счисления по классам эквивалентности, определяемое выражениями (5, 6) для случая перехода от и выражениями (7, 8) для случая перехода от , с теоретической точки зрения может явиться основой для разработки новых методов и алгоритмов генерирования различных комбинаторных объектов, в частности, сочетаний двоичных единиц по разрядам. Представляют интерес и системы (9, 10) параметров и для вложенных биномиальных систем счисления, поскольку демонстрируют взаимозависимость биномиальных систем и принадлежащих им чисел соседних уровней вложенности. Очевидно, что такая зависимость простирается на системы счисления и более глубокого уровня вложенности, что требует дальнейшего детального анализа.

С практической точки зрения, разработанные алгоритмы и , реализующие кодовые отображения (5, 7), позволяют разработать новые методы и алгоритмы адаптивной (к числу ошибок в дискретном канале) передачи информации на основе биномиальных чисел (кодов). Адаптивное изменение параметров биномиальных систем счисления и переход к биномиальным числам (кодам) меньшей или большей размерности на основе свойства вложенности позволяют обеспечивать оптимальным соотношение «скорость / верность передачи». Полученные алгоритмы и обладают набором достаточно простых операций, конечны и не предъявляют высоких требований к аппаратно-программным ресурсам при практической реализации.

Список литературы

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

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

3 Кулик И.А. О средней длине двоичных биномиальных чисел / Вiсн. Сум. ун-ту 2004, №12 (71) - с. 106-112.

4 Советов Б.Я., Стах В.М. Построение адаптивных систем передачи информации для автоматизированного управления. - Л.: Энергоиздат. Ленингр. отд-ние, 1982. - 120 с.