Главная страница  |  Описание сайта  |  Контакты
УСТРОЙСТВО ДЛЯ ПЕРЕБОРА ПЕРЕСТАНОВОК
УСТРОЙСТВО ДЛЯ ПЕРЕБОРА ПЕРЕСТАНОВОК

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

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

1. С помощью поисковых систем

   С помощью Google:    

2. Экспресс-поиск по номеру патента


введите номер патента (7 цифр)

3. По номеру патента и году публикации

2000000 ... 2099999   (1994-1997 гг.)

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2012054
Класс(ы) патента: G06F15/419, G06F15/20
Номер заявки: 5004241/24
Дата подачи заявки: 01.07.1991
Дата публикации: 30.04.1994
Заявитель(и): Бабаев Александр Александрович; Кашин Сергей Михайлович; Поляков Александр Алексеевич; Ячкула Николай Иванович
Автор(ы): Бабаев Александр Александрович; Кашин Сергей Михайлович; Поляков Александр Алексеевич; Ячкула Николай Иванович
Патентообладатель(и): Бабаев Александр Александрович; Кашин Сергей Михайлович; Поляков Александр Алексеевич; Ячкула Николай Иванович
Описание изобретения: Изобретение относится к вычислительной технике, предназначено для формирования перестановок переменной длины и может быть использовано для решения широкого класса комбинаторных задач в различных областях науки и техники (см. , например, Курейчик В. М. , Глушань В. М. , Щербаков Л. И. Комбинаторные аппаратные модели и алгоритм в САПР. М. : Радио и связь, 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-го блока деления ггруппы, а группа выходов второго демультиплексора соединена с первыми входами соответствующих элементов ИЛИ второй группы, выходы которых соединены с информационными входами соответствующего блока деления, а вторые входы элементов ИЛИ группы соединены с выходами соответственно последующих блоков деления группы.