УСТРОЙСТВО ДЛЯ ПЕРЕБОРА ПЕРЕСТАНОВОК

Название	УСТРОЙСТВО ДЛЯ ПЕРЕБОРА ПЕРЕСТАНОВОК
Разработчик (Авторы)	Бабаев Александр Александрович, Кашин Сергей Михайлович, Поляков Александр Алексеевич, Ячкула Николай Иванович
Вид объекта патентного права	Изобретение
Регистрационный номер	2012054
Дата регистрации	30.04.1994
Правообладатель	Бабаев Александр Александрович, Кашин Сергей Михайлович, Поляков Александр Алексеевич, Ячкула Николай Иванович
Область применения (класс МПК)	G06F 15/419 (1990.01) G06F 15/20 (1990.01)

Описание изобретения

Изобретение относится к вычислительной технике, предназначено для формирования перестановок переменной длины и может быть использовано для решения широкого класса комбинаторных задач в различных областях науки и техники (см. , например, Курейчик В. М. , Глушань В. М. , Щербаков Л. И. Комбинаторные аппаратные модели и алгоритм в САПР. М. : Радио и связь, 1990, с. 216).

Известны устройства, обеспечивающие генерацию перестановок исходных величин (см. например, авт. св. СССР NN 957215, 995093, 1124319, 1180917, 1190388, 1397933 и др. ). Недостатком этих устройств является невозможность управления очередностью следования генерируемых перестановок.

Наиболее близким по технической сущности к заявляемому является устройство для перебора перестановок, содержащее блок управления и блок декодирования (см. авт. св. СССР N 1410056, кл. G 05 F 15/20, 1988). Данное устройство реализует процедуру преобразования номера перестановки в однозначно соответствующую ему перестановку. Недостатки устройства - зависимость функциональной схемы от числа перестанавливаемых элементов и невозможность генерации перестановок переменной длины.

Цель изобретения - расширение области применения за счет обеспечения генерации перестановок переменного числа элементов.

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

Функциональная схема устройства приведена на чертеже.

Устройство содержит блок 1 управления и блок 2 декодирования. Блок 1 предназначен для формирования определяющего множества чисел в соответствии с выбранным вариантом перестановки и шагом работы устройства, выбора минимального числа из этого множества и подачи его на вход блока декодирования. Блок 1 содержит регистры 3i, триггеры 4i(i= , где n - предельное число элементов перестановок), схему 5 выбора минимального числа и дешифратор 6. Блок 2 декодирования предназначен для преобразования заданного натурального числа в соответствующую ему перестановку требуемого числа элементов. Блок содержит элементы 7i, i= , 8i, i= , 9i, i= задержки регистры 10, 11, 12, i= , демультиплексоры 13, 14, дешифратор 15, элементы ИЛИ 16, 17, 18i, 19i, i= , группу первых и вторых элементов И 20i, i= , блоки 21, i деления, сумматоры 22i, i= .

Устройство имеет также информационные входы 23, 24, вход 25 запуска и информационные выходы 26i, i= .

Работа устройства основана на реализации процедуры преобразования исходного числа m(0≅ m< k! k≅ n) в однозначно соответствующую ему перестановку исходных, предварительно пронумерованных числами 1, 2, . . . , k элементов (см. Бабаев А. А. Процедуры кодирования и декодирования перестановок. Кибернетика, 1984, N 6, с. 75-76).

Перед работой в регистры 3i, i= вносятся числа исходного определяющего множества Io= { 1,2, . . . , n} , причем число Р(Р∈Iо) вносится в регистр 3р, в регистр 11 по входу 23 вносится число переставляемых элементов К≅ n, а в регистр 12 по входу 24 вносится число m(0≅ m≅ k ! ). При этом код числа К с информационных выходов регистра 11 поступает на вход дешифратора 15 и появляется сигнал единичного уровня на К-м управляющем выходе дешифратора, с которого он поступает на инверсный вход первого и вход второго элементов И 20к. Триггеры 4i, i= , находятся в исходном нулевом состоянии. Сигналы с их нулевых выходов поступают на считывающие выходы регистров 3i, i= , и числа исходного определяющего множества Iо с информационных выходов регистра 3iпоступают на соответствующие входы схемы 5 выбора минимального числа. Код минимального из чисел исходного определяющего множества с выхода схемы 5 поступает на объединенные первые информационные входы сумматоров 22i, i= .

Работа устройства начинается с положительного импульса запуска на вход 25 пуска устройства. При этом импульс запуска поступает на вход считывания регистра 10 и на информационный вход демультиплексора 13, с информационных выходов регистра 10 код числа m поступает на информационный вход демультиплексора 14. С К-го выхода демультиплексора 13 сигнал поступает на вход элемента ИЛИ 18k, а с К-го выхода демультиплесора 14 код числа m поступает на вход элемента ИЛИ 19k. С выхода элемента ИЛИ 18k импульс запуска поступает на управляющий вход блока 21kделения, а с выхода элемента ИЛИ 19k код числа m поступает на информационный вход блока 21k деления.

Блоки 21i деления, i= , осуществляют деление числа, поступающего на их информационный вход, на модуль ri= n-i+1. При этом с первого выхода блока деления выдается целая часть от деления поступающего на его вход числа на соответствующий данному блоку постоянный модуль, а с второго - остаток от деления. Поэтому при поступлении на управляющий вход блока 21k деления импульса в нем осуществляется деление числа m на постоянный модуль rk= n-K+1. Целая часть от деления поступает с первого выхода блока 21k на вход элемента ИЛИ 19k-1, а остаток от деления с второго выхода поступает на второй информационный вход сумматора 22k. С выхода элемента ИЛИ 19 целая часть от деления поступает на информационный вход блока деления 21k.

Через время задержки τ1, достаточное для осуществления деления и передачи результатов, импульс появляется на выходе элемента 7k задержки, откуда он через элемент ИЛИ 18k-1 поступает на управляющий вход блока 21k-1 деления и вход элемента 7k-1 задержки. Далее аналогично последовательно через интервал времени τ1 блоками 21i, i= , осуществляется выделение целой части и остатков от деления на постоянный модуль чисел, поступающих с первого выхода блоков 21i деления, i= , соответственно. Через время t1= k . τ1 от момента подачи импульса запуска на вход 25 пуска импульс с выхода элемента 7i задержки поступает на вход элемента 91 задержки и управляющий вход сумматора 221, и в нем осуществляется сложение числа, поступившего с второго выхода блока 211деления, с числом, поступившим от схемы 5 выбора минимального числа.

Через время задержки τ2, достаточное для работы сумматора, поступает сигнал с выхода элемента 91 задержки на считывающий вход сумматора 221, вход разрешения записи регистра 121 и объединенные входы первого и второго элементов И 201. Код суммы с выхода сумматора 221поступает на информационный вход регистра 121 и соответствующий вход элемента ИЛИ 17. С выхода элемента ИЛИ 17 код суммы поступает на вход дешифратора 6 блока 1, а с выхода второго элемента И 20 импульс поступает на вход элемента 82 задержки. В дешифраторе 6 код суммы дешифрируется (величина суммы на выходе сумматора 22i, i= , принадлежит к множеству первых K чисел натурального ряда), и сигнал с соответствующего управляющего выхода дешифратора поступает на единичный вход соответствующего триггера 4i, i= . Триггер переходит в единичное состояние, снимается сигнал со считывающего входа соответствующего регистра 3i, i= , чем моделируется изменение определяющего множества чисел, и на выходе схемы 5 появляется код минимального числа, соответствующего данному измененному определяющему множеству.

Через время задержки τ3, большее длительности импульса запуска, появляется сигнал на выходе элемента 82 задержки, и поступает на вход элемента 92 задержки и управляющий вход сумматора 222. Дальнейшая работа схемы аналогична, и через время t2= К τ2+(K-1) τ3 +t1 от момента подачи импульса запуска появляется сигнал на выходе элемента 9kзадержки, откуда он поступает на объединенные входы элементов И20k. Так как при этом сигнал с k-го выхода дешифратора 15 присутствует на прямом входе первого и на входе второго элемента И 20k, то сигнал на выходе первого элемента И 20k не появляется, а сигнал с выхода второго элемента И20k поступает на соответствующий вход элемента ИЛИ 16 и с его выхода поступает на объединенные нулевые входы триггеров 4i, i= , и считывающие входы регистров 12i, i= . Числа, соответствующие полученной перестановке, поступают с информационных выходов регистров 12i, i= , на информационные выходы 26i, устройства i= .

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

Формула изобретения

УСТРОЙСТВО ДЛЯ ПЕРЕБОРА ПЕРЕСТАНОВОК, содержащее первый регистр, группа информационных входов которого является группой информационных входов устройства, а вход разрешения считывания данных соединен с входом запуска устройства, первую и вторую группы n регистров (n - максимальная длина перестановок), группу n блоков деления, группу n сумматоров, блок выбора минимального числа, первый и второй элементы ИЛИ, две группы из n элементов задержки и первый дешифратор, группа информационных выходов регистров первой группы соединена с группой входов блока выбора минимального числа, выход которого соединен с первым входом сумматоров группы, второй вход сумматоров соединен с выходом соответствующего блока деления группы, а выходы сумматоров группы соединены с входами соответствующих регистров второй группы и соответствующими входами первого элемента ИЛИ, выход которого соединен с входом первого дешифратора, выход второго элемента ИЛИ соединен с входом разрешения считывания регистров второй группы, выходы которых образуют группу информационных выходов устройства, отличающееся тем, что, с целью расширения области применения путем обеспечения генерации перестановок переменной длины, в него введены первая и вторая группы из (n - 1)-го элементов ИЛИ, второй регистр, второй дешифратор, первый и второй демультиплексоры, третья группа из (n - 1)-го элементов задержки и группа из n пар элементов И, группа из n триггеров, нулевые выходы которых соединены с входами разрешения считывания данных регистров первой группы, нулевые входы триггеров группы объединены и соединены с выходом первого элемента ИЛИ, а единичные входы соединены с соответствующими выходами второго дешифратора, информационный вход второго регистра соединен с информационным входом устройства, а выход соединен с входом второго дешифратора и управляющими входами первого и второго демультиплексоров, информационный вход первого демультиплексора соединен с входом запуска устройства, n-й выход которого соединен с управляющим входом n-го блока деления и входом n-го элемента задержки первой группы, группа выходов первого демультиплексора соединена с первыми входами соответствующих элементов ИЛИ первой группы, вторые входы которых соединены с выходами соответственно последующего элемента задержки первой группы, а выход каждого элемента ИЛИ первой группы соединен с управляющим входом соответствующего блока деления и входом соответствующего элемента задержки первой группы, выходы элементов задержки второй группы соединены с первыми входами соответствующих пар элементов И группы, с входом разрешения считывания результата сумматоров группы и входом разрешения записи соответствующих регистров второй группы, второй вход второго элемента И, выполненный инверсным, и второй вход первого элемента И каждой пары элементов И группы соединены с выходами второго дешифратора, выход второго элемента И каждой пары элементов И группы, кроме последней, соединен с входом соответствующего элемента задержки третьей группы, выход которого соединен с тактовым входом сумматоров группы и входом соответствующего элемента задержки второй группы, выходы первых элементов И пар элементов И группы соединены с соответствующими входами второго элемента ИЛИ, вход которого соединен с выходом второго элемента И n-й пары элементов И группы, информационный вход второго демультиплексора соединен с выходом регистра, n-й выход второго демультиплексора соединен с информационным входом n-го блока деления ггруппы, а группа выходов второго демультиплексора соединена с первыми входами соответствующих элементов ИЛИ второй группы, выходы которых соединены с информационными входами соответствующего блока деления, а вторые входы элементов ИЛИ группы соединены с выходами соответственно последующих блоков деления группы.

Изобретение "УСТРОЙСТВО ДЛЯ ПЕРЕБОРА ПЕРЕСТАНОВОК" (Бабаев Александр Александрович, Кашин Сергей Михайлович, Поляков Александр Алексеевич, Ячкула Николай Иванович) отмечено юбилейной наградой (25 лет Российской Академии Естествознания)
Медаль Альфреда Нобеля

Оформление наградных документов и заказ каталога