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

 

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

СОЮЗ СОВЕТСНИХ соцИАлистичеяих

РЕСПУ БЛИН (19) (И) А1 (51) 4 G 06 F ° 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ1

К ASTOPCKOMY СВИДЕТЕЛЬСТВУ (21) 3892093/24-24 (22) 13.05.85 (46) 15.10.86. Бюл. У 38 (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) В.М.Глушань, М.И.Пупков, М.В.Рыбальченко и Л.И.Щербаков (53) 681.325.22(088.8) (56) Авторское свидетельство СССР

Ф 643883, кл, С 06 F 15/20, 1977.

Авторское свидетельство СССР

В 1008750, кл. С 06 F 15/31, 1981. (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ (57) Изобретение относится к вычислительной технике. Целью изобретения является повышение быстродействия и сокращение оборудования. Устройство содержит генератор тактовых импульсов, накапливающий сумматор, три группы элементов И, две группы элементов ИЛИ, элемент ИЛИ, три регистра, три элемента задержки и сдвигатель кодов. 2 ил.

1264198

Изобретение относится к вычислительной технике и может быть испольцы не появляются в старших разрядах подряд.

Перед началом работы в накапливающий сумматор 11 записывается исходное. сочетание, т.е. единицы записываются в младшие (верхние по Схеме) разряды, а. регистры 6 и 7 обнуляются °

От генератора 2 единичные импульсы: поступают непосредственно на вход первого элемента И 5, вход первого элемента И 4,. Если в младших разрядах регистра 1 записано L нулей, то пер вый тактовый импульс последовательно появляется на выходах 1. элементов И5 и в 1. разрядах регистра 6 записаны единицы. При нахождении после L нулей первой же единицы распространение тактового импульса по элементам И 5 прекращается независимо от расположения единиц в следующих разрядах регистра 1. Поэтому в остальные разряды регистра 6 записаны нули. зовано для построения специализированных вычислительных устройств, ";" предназначенных, например, для авто-матизированного решения задач конструирования радиоэлектронной и вычислительной аппаратуры.

Цель изобретения — повьш|ение быстродействия и сокращение оборудования. 1б

На фиг.1 представлена функциональная схема устройства, на фиг.2 — схема сдвигателя.

Устройство содержит регистр 1, генератор 2 тактовых импульсов, группу элеме нтов ИЛИ 3, элементы И 4, элементы И 5, регистр 6, регистр 7, сдвигатель 8 кодов, шифратор, элементы И 9, группу элементов ИЛИ 10, накапливающий сумматор 11, элементы

12-14 задержки, элемент ИЛИ 15, элемент ИЛИ 16, элементы И-ИЛИ 17 и 18. элементы И 19-22, В основе принципа работы устройства лежит следующий алгоритм перебора сочетаний. Исходным является сочетание, в котором N единиц з"..ïèñëíû в младших разрядах (правых), Очередное сочетание определяется по формуле

А; = А ., +А,где А., — предыдущее сочетание, а а . = ? 2 — 1, Здесь

-1 (. — число подряд стоящих нулей, начиная с младшего разряда до первой единицы в i-f-м сочетании, К вЂ” число подряд стоящих единиц после L нулей

35 до первого очередного нуля, Рассмотрим на примере перебор ""очетаний из "5" по "3". Число таких сочетаний определяется о формуле:

Таким образом, в регистр 6 записано двоичное число 0...0 11...1, которое в десятичной системе счисления

L равно 2 -1. Причем регистр 6 должен иметь и-2 разрядов. Действительно, максимальное число подряд стоящих нулей в младших разрядах, начиная с нулевого, зависит для заданного и от величины N и при N = 1 оно .будет наибольшим. Так предпоследним сочетанием из п по "1" будет сочетание

0100...0. При этом P = L = n — 2, где Р— число разряцов регистра 6.

Так как следующее сочетание 1000.. 0 —последнее и хотя цля последнего сочетания L = L„„ = n-1, обработка информации об этом сочетании уже не требуется.

После прекращения распространения тактового импульса по элементам И 5 и . 5!

10.

N! (n — N) 1 312!

С

1) происходит переход этого импульса через соответствующий элемент ИЛИ 3 на элемент И 4, соединенный с единичным выходом Е+1-го разряда регистра

1. На единичном выходе этого разряда регистра 1 — единичный потенциал.

Тактовый импульс будет распространяться по элементам И 4 и записываться в соответствующие разряды регистра

7 до тех пор, пока после К подряд стоящих единиц в единичных разрядах регистра 1 не обнаружится первый нуль, Этот нулевой потенциал на единичном выходе Е + К + 1-го разряда регистра 6 блокирует распространение тактового импульса по всем следующим

Исходным для данного случая является сочетание А = 00111. Получают

45 последовательность всех сочетаний

9 используя приведенный алгоритм.

Для A „ L = О, К = 3,,= (4)„ (00100), тогда А = А, + А

00111 + 000100 + 01011. Аналогичным образом получают все остальные сочетания

=00010 А „=01101 Ь„=00001 А =01110 б -00101 А 10011 &5=00010 А 10101

6 =00001 A,=10110 4,--00011 А -11001

4 =00001 А =11010 =00010 А, =11100, Таким образом, произведен перебор всех десяти сочетаний, причем он продолжается до тех пор, пока все едини126 19О элементам И 4. Таким образом, в регистр 7 записывается следующая комбинация нулей и единиц и

n...oi ... o...о .

1.

Максимальное число подряд стоящих единиц определяет необходимое число разрядов регистра 7 и составляет ве- 0 личину п-1, что в случае N = n-1 соответствует начальггому сочетанию.

Для того, чтобы информацию, записанную в регистр 7, можно было преоб-

1 разовать в двоичный код десятичного

К-1 числа 2, ее необходимо сначала сдвинуть на L позиций в сторону младших разрядов, а затем заблокировать

К- 1 разрядов, начиная с младшего. Это

20 осуществляется с помощью сдвигателя

R. Иапример, если единичный потенциал появляется на 3 и 4 выходах регистра

7, то он появляется на вьгходах элементов ИЛИ 16 и И-ИЛИ 17, т,е. проис-. ходит сдвиг единичных потенциалов с

3 и 4 разрядов на 1 и 2 разряды. Единичный потенциал с выхода элемента

И-ИЛИ 17, поступая на инверсный вход элемента И 20, блокирует прохождение единичного потенциала с выхода эле30 мента ИЛИ 16 на выход элемента И 20, но он проходит на выход элемента И

21, так как Hà его инверсный вход поступает нулевой потенциал и он открыт.

Таким образом, на выходах сдвигак-1 теля формируется число 2 в дво- ичном коде. После того, как на выходах регистра 6 появляется число в 40 двоичном коде, оно через элемент ИЛИ

10 поступает на вход сумматора 11, в, котором происходит суммирование предыдущего сочетания с числом 2 -1 по

L сигналу на синхронизирующем входе 45 сумматора, 11. Этот сигнал поступает от генератора 2 тактовых импульсов с задержкой, равной или превышающей время формирования числа в регистре

6. Затем через элемент 13 задержки сигнал поступает на установочный вход . регистра 6 и на входы элементов И 9, Регистр 6 обнуляется, а на вход сумк-,. матора 11 поступает число 2 через элементы И 9 и ИЛИ 10. Через время, необходимое для получечия суммы (А;+

L К .1 1

+ 2 — 1) + 2 = А... единичный импульс через элемент 14 задержки обнуляе1 регистр 7 и переписывает очередное сочетание в регистр 1.

Аналогичным образом процесс продолжается до тех пор, пока не будут перебраны все возможные сочетания, Сигналом о переборе всех сочетаний является появление N единиц подряд в старших разрядах сумматора 11, что используется для формирования единичного потенциала — сигнала окончания на вьгходе последнего элемента И 4.

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

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

ИЛИ, причем информационный вход каждого первого регистра соединен с выходом соответствующего разряда накапливающего сумматора, первые входы элементов И первой группы соединены соответственно с прямыми выходами разрядов первого регистра, вторые входы элементов И первой группы, кроме первого элемента И, соединены соответственно с выходами элементов ИЛИ первой группы, выход генератора тактовых импульсов подключен к второму входу первого элемента И первой группы и через первый элемент задержки— к входу второго элемента задержки и к первому входу элемента ИЛИ, пер— вый вход i — го элемента И второй группы соединен с выходом i-1-ro элемента И второй группы и с первым входом

j-го элемента ИЛИ первой группы (i

2, 3, ..., n-1, j = 1, 2, ..., n-1, где n — число разрядов в сочетании), второй вход j-ro элемента ИЛИ первой группы соединен с выходом 1-го элемента И первой группы (i = 1, 2, и-1, j = 1, 2, ..., и-l), выход иго элемента И первой группы является выходом окончания цикла устройства, 1 04 ЧК

1первый вход первого элемента И второй группы соединен с выходом гpíåðëòtiðÿ тактовьгх импульсов, второй вход каждого элемента И второй группы соединен с инверсным выходом соответствующего разряда первого регистра, информационные входы накапливающего сумматора соединены соответственно с выходами элементов И третьей группы и с выходами элементов ИЛИ второй группы, !О первые входы которых соединены соответственно с выходами разрядов второ,го регистра, à BToph(p. входы подключены к выходам соответствующих элементов И третьей группы, первые входы 15 которых соединены соответственно с выходами сдвигателн, вторые входы элементов И третьей группы и установочный вход второго регистра соединены с выходом второго элемента задержки и с входом третьего элемента задержки, выход которого подключен к установочным входам первого и третьего регистров и к второму входу элемента ИЛИ, выход которого соединен с синхронизирующим входом накапливающего сумматора, выходы разрядов третьего регистра соединены соответственно с входами сдвигателя, входы разрядов второго регистра соединены соответственно с выходами с первого по и-2-й элементов И второй группы, входы разрядов третьего регистра соединены. соответственно с выходами с первого по — 1 — и элементов И первой группы.

1264198

Составителу А.Жеренов

Техред М.Ходанич Корректор А.Тяско

Редактор И. Касарда

Заказ 5564/50 Тираж 671 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4