Устройство для перебора перестановок

 

Изобретение относится к вычислительной технике, предназначено для формирования в произвольной последовательности перестановок и может быть использовано для решения комбинаторных задач, а также в системах контроля для генерации кодовых последовательностей. Цель изобретения - расширение области применения за счет генерации перестановок переменной длины. Устройство содержит два дешифратора, два мультипликатора, два элемента ИЛИ, группу из n(n - максимальная длина генерируемых перестановок) сумматоров, n блоков деления, две группы из n регистров, три группы элементов задержки и группу элементов И. Устройство реализует процедуру преобразования числа m(0 m<k) в соответствующую ему перестановку элементов (k n). 1 ил.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Через время задержки ₃, большее длительности импульса запуска, появляется сигнал на выходе элемента 8₂ задержки, и поступает на вход элемента 9₂ задержки и управляющий вход сумматора 22₂. Дальнейшая работа схемы аналогична, и через время t₂= К ₂+(K-1) ₃ +t₁ от момента подачи импульса запуска появляется сигнал на выходе элемента 9_kзадержки, откуда он поступает на объединенные входы элементов И20_k. Так как при этом сигнал с k-го выхода дешифратора 15 присутствует на прямом входе первого и на входе второго элемента И 20_k, то сигнал на выходе первого элемента И 20_k не появляется, а сигнал с выхода второго элемента И20_k поступает на соответствующий вход элемента ИЛИ 16 и с его выхода поступает на объединенные нулевые входы триггеров 4_i, i= , и считывающие входы регистров 12_i, i= . Числа, соответствующие полученной перестановке, поступают с информационных выходов регистров 12_i, i= , на информационные выходы 26_i, устройства i= .

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

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

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

РИСУНКИ

Рисунок 1