Комбинаторное устройство

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТИЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) 3аявленр . 211278 (21) 2701809/18-24

5ЦМ K„ç с присоединением заявки Hо

G 06 F 7/00

Государственный квинтет

СССР по ACJIRM изобретений н открытий (23).приоритет

Опубликовано 150201, ЬюллЕтЕнь Их 6 (5Щ УДК 681. 3 (088.8) Дата опубликования описания 1502pl

О. В. Викторов, М.Г. Лукашевич, С.И. Орел и AМ.. :;7ЯИФФкевнч 7 од йЯ

° Е. ? (g

iz,/Дл(гЯЦ г, (72) Авторы изобретения (71) Заявитель

Киевский политехнический институт им. 50-тйггия- Великой

Октябрьской социалистической революции (54) КОМБИНАТОРНОЕ УСТРОЙСТВО

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

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

Недостаток устройства в том, что он не осуществляет генерацию перестановрк.

%ниболее близким техническим решением к изобретению является комбииаторное устройство, содержащее в 1«том 20 (i--l,...,й) разряде регистр, три элемента И, элемент ИЛИ, причем выход ре истра каждого разряда соединен с первым входом первого элемента И того же разряда, выход которого соединен с первым входом элемента ИЛИ, выход которого соедйнен с первым входом второго элемента И следующего разряда, и первым входом регистра следую щего разряда, а второй вход соеди- ЗО нен с выходом второго элемента И того же разряда, второй вход которого соединен с первым входом третьего элемента И того же разряда и вторым входом первого элемента И того же разряда, выход третьего элемента И каждого разряда соединен со вторым входом регистра того же разряда. Устройство содержит крОме того дешифратор (2).

Недостатком его является низкое быстродействие.

Цель изобретения — повышение быст родействия.

Цель достигается тем, что устрдй: ство содержит М-4 распределителя, N-3 кольцевых сдвиговых регистров, группу элементов И, первую группу из N-2 элементов .ИЛИ, вторую группу элементов ИЛИ, причем первый и последний выходы первого распределителя соединены с первым входом третьего элемента И соответственно первого и последнего разрядов устройства и с первыми входами соответственно первого и N-2 элементов группы ИЛИ. Каждый остальной выход первого распределителя сое динен с первым входом соответствующего элемента ИЛИ первой группы и со вторыми входами следующего элемента

805302

ИЛИ первой группы, выходы элементов

ИЛИ группы соединены с первыми входами третьих эпементов И соответствующих разрядов, вторые входы которых соединены между собой и являются тактовым входом устройства, входы первого распределителя, кроме последнего, соединены с выходами следующего распределителя и выходами i-òoãî кольцевого регистра сдвига, входы последнего распределителя соединены с выходами двух последних кольцевых регистров сдвига, управляющий вход каждого кольцевого регистра сдвига соединен с выходом соответствующего элемента И группы, нервый вход которого соединен с выходом следующего элемента И группы, а второй вход соединен с выходом соответствующего элемснта ИЛИ второй группы, первый и второй входы которого соединены с первы... и последним выходами соответ- 20 ствующего кольцевого регистра.

На чертеже схематически показано устройство.

Оно содержит регистры 1-6, элементы И 7-12, элементы И 13-18, элемен- 25

-..ы ii 19-24, элементы ИЛИ 25-30, кольцевые рсгистры сдвига 3J — 33, распределители 34-35, триггеры управления сдвигом 36-38, тактовый вход 39 устройства, выход 40 распределителя, элемент ИЛИ 41, выход 42 распределителя, элемент ИЛИ 43, выход 44 раса пределителя, выход 46 распределителя, элемент, ИЛИ 45, элемент ИЛИ 47, выход 48 распределителя, входы 49-57 распределителя, выходы 58-66 распре— делителя, входы 67-84 распределителя, элементы И 85-90, элемент ИЛИ 91, элементы И 92 н 93, элементы .ИЛИ 9499, элементы И 100-111, элементы

ИЛИ 112-118, элементы И 119-126. 40

Комбинаторное устройство работает . следующим образом.

В первом такте работы устройства регистры 1-6 устанавливаются соот"3", "4", "5". На информационные выходы регистров 1-6 поступают соответственно сигналы 000, 001, 016, 011, 100, 101. Таким образом, в первом так те работы устройства реализуется пер- M вая перестановка "012345" (см. таблицу), где номера позиций цифр в ерестановке соответствуют номерам регистров, а цифры, стоящие на этих позициях, соответствуют десятичной записи двоичных кодов состояний соответствующих регистров.

Регистр 31 устанавливается в состояние 00010, регистр 32 — в состояние 000010 регистр 3 3 — в состояние 0000010 (см. таблицу). 60

На входы распределителя 34 с выходов кольцевого регистра 31 поступают соответственно сигналы 0,0,0,1,0. .ta входы элемента ИЛИ 112 с входов

68 и 71 распределителя 34 поступают 65 нулевые сигналы, а единичный сигнал с входа 70 распределителя 34 поступает через элемент ИЛИ 113 на вход каждой из схем И 107, 109-111.

На входы 79-84 распределителя 35 с выходов сдвигающего регистра .32 поступают соответственно сигналы

0,0,0,0,1,0.

Йулевой сигнал с входа 79 через выход 59 этого распределителя и вход

50 поступает на вход каждого из эле-, ментов И 102, 104, 106, 108, 110, 111

Нулевой сигнал с входа 84 распределителя 35 через выход 65 этой схемы и вход 56 распределителя 34 поступает на вход каждого из элементов И 100,.

101, 103, 105, 107, 109. Нулевые сигналы с выходов первого и последнего разряда сдвигающего регистра 33 поступают, соответственно на входы 72 и 78 распределителя сигналов 35. С выхода 72 этой схемы нулевой сигнал поступает на вход каждого из элементов И 120, 124, 125, а также через выход 58 распределителя 35 и вход 49 распределителя 34 поступает на вход каждого из элементов И 101, 104, 105, 108, 109, 111. С входа 78 распределителя 35 нулевой сигнал поступает на вход каждого из элементов

И 119, 121, 123, 125, а также через выход 66 распределителя 35 и вход 57 распределителя 34 поступает на вход каждого из элементов И 100, 102, 103, 106, 107, 110.

Таким образом, все элементы И 100111, 119-126 закрыты нулевыми сигналами на входах, и сигналы из регистров 31 и 32 через распределители 34 и 35 соответственно не поступают.

Нулевой сигнал с выхода второго разряда регистра 33 через вход 73, элемент ИЛИ 114, выход 60, вход 51, элемент ИЛИ 95, выход 40 закрывает элементы И 7 и 19 и открывает. элемент И 13. Нулевой сигнал с выхода третьего разряда сдвигающего регистра 33 через вход 74 распределителя сигналов 35, элемент ИЛИ 115, выход 61, вход 52 распределителя сигналов 34, элемент ИЛИ 96, выход 42, элемент ИЛИ 41 закрывает элементы

И 8 и 20 и открывает элемент И 14.

Нулевой сигнал с выхода четвертого разряда регистра 35 через вход 75 распределителя 35, элемент ИЛИ 116, выход 62, вход 53 распределителя сиг. налов 34, элемент ИЛИ 9"., выход 44, элемент ИЛИ 43 закрывает элементы

И 9 и 21 и оТкрывает элемент И 15.

Нулевой сигнал с выхода пятого разряда регистра 33 через вход 76 распределителя 35, элемент ИЛИ 117, выход 63, вход 54 распределителя 34, элемент ИЛИ 98, выход 46, элемент

ИЛИ 45 закрывает элементы И 10 и 22 и открывает элемент И 16. Единичный сигнал с выхода шестого разряда регистра 33 через вход 77 распредели805302

60 теля 35, элемент ИЛИ 118, выход 64, вход 55 распределителя 34, элемент

ИЛИ 99, выход 48, элемент ИЛИ 47 открывает элементы И 11 и 23 и закрывает элемент И 1.7. Кроме того, единичный сигнал, поступающий с выхода 48 распределителя 34, открывает элементы И 12 и 24 и закрывает элемент И 18;

Триггеры управления сдвигом 36-38 устанавливаются в нулевое состояние (см. таблицу), и на первые входы элементов И 85, 88 и 92 поступают нулевые сигналы, а на первые входы элементов И 86, 89 и 93 поступают единичные сигналы с соответствующих выходов триггеров, благодаря чему в ре)5 гистрах разрешается левый сдвиг.

Нулевые сигналы с выходов первого и последнего разрядов регистра 33 через элемент ИЛИ 94 поступают на вход элемента И 90 и закрывают его. Нуле- 20 вые сигналы с выходов первого и последнего разрядов сдвигающего регистра 32 через элемент ИЛИ 91 поступают на вход элемента И 87 д закрывают

его. 25

Во втором такте работы устройства тактовый сигнал поступает на вход каждого из элементов И 19-24, и единичные сигналы с выходов открытых элементов И 23 и 24 поступают на так- З0 товые входы регистров 5 и б. Код 100 с информационного выхода регистра 5 через открытые элементы И 11, 13-16 и элементы ИЛИ 25-29 поступает на вход установки регистра 6. Код 101 с информационного выхода регистра б через открытый .элемент И 12 и элемент ИЛИ 30 поступает на вход установки регистра 5. Регистры 5 и б устанавливаются соответственно в состояния "5" и "4". Информация в дру- 40 гих,регистрах фиксируется нулевыми сигналами из тактовых входов. . Таким образом, во втором такте работы устройства реализуется перестановка "012354". 45

Кроме того, во втором такте тактовый сигнал поступает на вторые входы элементов И 92 и 93, единичный сигнал с выхода элемента И 93 поступает в цепь левого сдвига регистра 33, 50 и единица в этом регистре сдвигается на один разряд влево.

В третьем такте работы устройства тазовый сигнал 39 поступает на вход каждого из элементов И 19-24. Единичный сигнал с выхода пятого разряда регистра 33 через элементы ИЛИ 117 и 98 распределителей 35 и 34 соответственно, элементы ИЛИ 45 и 47 и ох крытые схемы И 22 и 23 поступает на тактовые входы регистров 4 и 5, обеспечивая обмен информацией между этими регистрами.

Таким образом, в третьем такте работы устройства реализуется перестановка "012534". Кроме того, единица б5 в регистре 33 сдвигается на один р»: ряд влево.

В.следующих трех тактах работы устройства реализуются последовательно перестановки "015234", 051234" и "501234". Единица в регистре 33 сдвигается влево и в шестом такте сдвигается в первый разряд регистра

33. Единичный сигнал с выхода первого разряда сдвигающего регистра 33 поступает на единичный вход триггера 38 управления сдвигом, триггер 38 управления сдвигом устанавливается в единичное состояние, и в регистре

33 разрешается .первый сдвиг. Кроме того, единичный сигнал с выхода первого разряда. регистра 33 через элемент ИЛИ 94 открывает элемент И 90, а также поступает на вход 72 распределителя 35 и открывает элементы

И 120, 122, 124, 126.

В седьмом такте работы устройства тактовый сигнал с шины 39 тактовых сигналов поступает на вход каждого из элементов И 19-24. Единичный сигнал с выхода пятого разряда регистра- 32 через открытый элемент ИЛИ 118 распределителя 35 сигналов, элемент

ИЛИ 99 распределителя 34 сигналов поступает на выход 48, обеспечивая обмен информацией между регистрами

5 и б. Реализуется перестановка

"501243". Кроме того, тактовый сигнал с входа тактовых сигналов 39 поступает в цепь правого сдвига регистра

33, а через открытые схемы И 90 и 89— в цепь левого сдвига сдвигающего регистра 32. Единица в сдвигающем регистре 33 сдвигается на один разряд вправо, а единица в сдвигающем регистре 32 — на один разряд влево.

В тридцатом такте работы устройства реализуется перестановка

"540123", единица в регистре 32 находится в первом разряде этого регистра, а единица в регистре 33 сдвигается в первый разряд этого регистра.

Единичный сигнал.с выхода первого разряда регистра 33 поступает на единичный вход триггера 38 управления сдвигом, этот триггер устанавливается в единичное состояние, и в регистре 33 разрешается правый сдвиг.

Элементы И 87 и 90 открыты единич. ными сигналами, поступающими через элементы ИЛИ 91 и 94 соответственно с выходов первых разрядов, регистров

32 и 33. Единичные сигналы с выходов первых разрядов регистров 32 и 33 через распределители 35 поступают соответственно на входы 50 и 49 схемы распределителя 34 сигналов и открывают в ней элементы И 104, 108, 111.

В тридцать первом такте работы устройства тактовый сигнал с шины

39 тактовых сигналов поступает на вход каждого из элементов и 19-24.

805302

"01?345"

"012354"

"012534"

"501234

1000000

00010

"501243"

0100000 а

00010

"540123"

1000000

"530132"

00100.

0100000.

Единичный сигнал с выхода четвертого разряда сдвигающего регистра 31 через элемент,ИЛИ 113, открытый элемент ИЛИ 111, элемент ИЛИ 99 схемы 1распределения сигналов 34 поступает на выход 48 этой схемы, обеспечивая обмен информацией между регистрами 5 и 6. Реализуется перестановка

"540132".

Кроме того, тактовый сигнал с шины тактовых сигналов 39 через открытые элементы И 90 и 88 поступает в цепь правого сдвига сдвйгающего регистра 32, через открытые элементы

И 90, 87. и 86 — в цепь левого сдвига сдвигающего регистра 31, а через открытый элемент И 92 — в цепь правого 15 сдвига сдвигающего регистра 33. Единица в сдвигающем регистре 31 сдвигается на один разряд влево, а единицы в сдвигающих разрядах 32 и 33 — на один разряд вправо. 20

В семьсот девятнадцатом такте ра-, боты устройства реализуется перестановка "102354", единицы в сдвигающих регистрах 31 и 32 находятся в последних разрядах этих регистров, а единица в сдвигающем регистре 33 сдвигается в предпоследний разряд этого регистра.

В семьсот двадцатом такте работы устройства тактовый сигнал с шины тактовых сигналов поступает на вход каждого из элементов И 19-24. Единичный сигнал с выхода предпоследнего разряда сдвигающего регистра 33 через элементы ИЛИ 118 и 99, соответственно схем распределения сигналов 35 и 34 поступает на выход 48 схемы распределения сигналов 34, обеспечивая обмен информацией между регистрами

5 и 6. Реализуется последняя перестановка "102345", а единица в сдвигающем регистре 33 сдвигается в последний разряд этого регистра.

В таблице показаны состояния регистров, триггеров управления сдэигом и кольцевых регистров.

00010

805302

:Продолжение таблицы

Состояния триггеров управления

Состояние регистра

Номер такта

Состояния кольцевых регистров сдвигом

00001

"102354"

0 000001

719

00001

000001

0000001

"102345"

720

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

Известное устройство обеспечивает перечисление перестановок, но обладает существенным недостатком — низким быстродействием, Для перечисления gQ всех Р = n! перестановок требуется

n" тактов работы.

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

n i перестановок за n тактов работы. Так, для реализации Р6 = 720 перестановок шести элементов предлагаемому ксмбинаторному устройству требуется 720 тактов работы, в то время как известному устройству требуется

46 656 тактов.

Комбинаторное устройство, содержащее в i òoì (=1,...,Н) разряде регистр, три элемента И, элемент ИЛИ, причем выход регистра каждого разря- 4Q да соединен с первым входом первого е элемента И того же разряда, выход которого соединен с первым входом элемента ИЛИ, выход которого соединен с первым входом второго элемен- 45 .та И следующего разряда, и первым входом регистра следующего разряда, а второй вход соединен с выходом второго элемента И того же разряда, второй вход которого соединен с первым входом третьего элемента И того же разряда и вторым входом первого элемента И того же разряда, выход третьег®,элемента И каждого разряда соедийен со вторым входом регистра того же разряда, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, устройство содержит (й -4) распределителя, N-3 кольцевых сдвиговых регистров, группу элементов И, первую группу элементов ИЛИ, вторую группу элементов ИЛИ, причем первый и последний выходы первого распределителя соединены с первым входом третьего элемента И соответственно первого и последнего разрядов устройства и с первыми входами соответственно первого и последнего элементов ИЛИ первой группы, остальные выходы первого распределителя соединены с первыми входами соответствующих элементов ИЛИ первой группы и со вторыми входами следующего элемента ИЛИ первой группы, выходы элементов ИЛИ первой группы соединены с первыми входами третьих элементов И соответствующих разрядов, вторые входы которых соединены между собой и являются тактовым входом устройства, входы j òoão (j=1,...,й-3) распределителя, кроме последнего, соединены с выходами следующего распределителя и выходами

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

Источники информации, принятые во внимание при экспертизе

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

Р 374606, кл. 6 06 F 15/32, 1970.

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

Ф 446057, кл. G 06 F 7/38, 1972.

805302

Заказ 10903/71

Тираж 756 Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

Составитель Е. Пупырев

Редактор N. Циткина Техред T. Маточка . Корректор М. Вигула