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

Формирователь сочетаний на основе многозначных биномиальных чисел

Протасова Т.А., ст. преп.

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

В настоящее время развивается новое направление в области кодирования, которое в качестве своей основы использует специальные системы счисления с неоднородной структурой [1]. Это направление оказалось особенно эффективно в случае формирования комбинаторных кодов, например, перестановок, композиций, сочетаний, сочетаний с повторениями, равновесных кодов и т.д.

В 80-е годы прошлого столетия изобретено, разработано и запатентовано множество разнообразных устройств, которые преобразовывают двоичные коды в различные комбинаторные конфигурации [2]. Эти устройства, как правило, не являются универсальными и обладают рядом недостатков, которые снижают эффективность их использования в технике. Так, приборы данного типа имеют очень сложный алгоритм формирования комбинаторных конфигураций, что, в свою очередь, приводит к сложности их использования, невысокой надежности в работе и низкому быстродействию.

При построении формирователей комбинаторных конфигураций на основе биномиальных систем счисления решение задачи генерирования разбивается на два этапа: сначала осуществляется преобразование исходного числа позиционной системы счисления в биномиальную систему счисления, а затем выполняется переход из биномиальной системы счисления в требуемый код [3,4]. Такое устройство будет состоять из двух блоков - в первом блоке будет формироваться многозначное биномиальное число, а во втором (параллельно) - все возможные комбинаторные конфигурации.

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

Таблица 1

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

Рассмотрим решение задачи генерирования комбинаторных конфигураций на примере построения сочетаний.

Из раздела комбинаторики [5] нам известно, что:

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

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

(1)

является элементом последовательности, которая образует сочетание .

Доказательство. Так как мощность множеств многозначных чисел вида и сочетаний одинакова [5], то достаточно показать, что отображение , заданное формулой (1), инъективно. Другими словами, разным многозначным числам и ставятся в соответствие различные сочетания и . В самом деле, пусть и - два различных многозначных числа, т.е. . Пусть, далее, - первый слева разряд, в котором отличается от , т.е.

, (2)

. (3)

Покажем, что тогда аналогичные соотношения имеют место для и . Действительно, из правила (1) и соотношений (2)-(3) вытекают цепочки:

, ,

,

которые и означают, что

Утверждение доказано.

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

1. Первая цифра сочетания равна старшей цифре многозначного биномиального числа.

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

3. Вычисляется следующая цифра сочетания .

4. Пункты 2,3 повторяются до тех пор, пока не будет получена последняя k-ая цифра сочетания.

Пример 1. Биномиальное число 1013 преобразовать в сочетание.

; ,

,

В результате будет получено сочетание 1248.

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

Доказательство. Согласно условию утверждения последовательность строится по формулам:

, , (4)

,. (5)

Рассмотрим два различных многозначных числа и , т. е. . Если при этом они различаются уже в старшем разряде, т. е. , то в силу (4). Если же , но , то получим в результате . Утверждение доказано.

Алгоритм преобразования многозначных биномиальных чисел в сочетание из n элементов по k имеет следующий вид.

1. Первая цифра сочетания равна старшей цифре биномиального числа.

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

3. Пункт 2 повторять до тех пор, пока не будет получена последняя k -я цифра сочетания.

Пример 2. Биномиальное число 1013 преобразовать в сочетание:

, ,

,

В результате получено сочетание 1248.

Из двух рассмотренных алгоритмов будем реализовывать второй, так как он проще реализуется. Блок-схема алгоритма функционирования будет иметь вид, представленный на рисунке 1.

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

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

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

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

- выходные регистры, предназначенные для хранения полученных значений разрядов сочетаний.

Рисунок 1 - Блок-схема алгоритма формирования сочетаний

Рисунок 2 - Функциональная схема параллельного преобразования биномиального числа в сочетание

ВЫВОДЫ

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

SUMMARY

Combination generation algorithm based on binomial numbers with multiple alphabet is offered in the article. Evidence of statements that prove offered transformations is given. Possible embedding of the algorithm in the form of block diagram and structure flowchart of the combination composer is considered.

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

1. Борисенко А.А., Онанченко Е.Л., Кобяков А.Н. Системы счисления с биномиальным основанием // Вестник СумГУ. - 1994. - №1. - С. 96-101.

2. Викторов О.В., Лукашевич М.Г., Орел С.И., Романкевич А.М. Комбинаторное устройство. Опубл. в Б.И. 1980.- N32.

3. Протасова Т.А., Онанченко Е.Л., Калигаева О.Л., Калашников В.В., Бугай В.Д. Синтез комбинаторных конфигураций на основе многозначных биномиальных кодов // Вісник Сумського державного університету. - 1997. - №2(8).

4. Протасова Т.А., Онанченко Е.Л. Алгоритмы формирования комбинаторных кодов на основе многозначных биномиальных чисел // Вісник Сумського державного університету. - 1996. - №1(5). - С. 84-88.

5. Сигорский В.П. Математический аппарат инженера. - К.: Технiка, 1975. - 768 с.