Устройство для перебора сочетаний, размещений и перестановок Советский патент 1988 года по МПК G06F7/06 

4 4

1

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

Цель изобретения - повышение быстродействия при формировании сочетаний и размещений.

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

Устройство содержит группу счетчиков 12,.. о, 1 , группу сумматоров 25,...,2, образукяцих лестничную структуру, группу элементов И 3,.о 3fj, регистр 4 сдвига, элементы ЗАПРЕ 5 и 6, переключатель 7, генератор 8 перестановок, регистр 9, дешифратор 10 (кода Джонсона), N групп элементов И 1.1. ,. о о, 11 , группу элементов ИЛИ 12.,,„„о,12ц(, дешифратор (N-пози- ционного кода).13, регистр 14, схему 15 сравнения.

Дешифратор 10 реализует функцию

„n-.l

,,х,) V F. (х

h

,,х), ,

1,

если Z. X,2 i-1

О, е.сли 1 X 2 j

Устройство работает в трех режимах: генерации сочетаний (информация снимается с выходов сумматоров), перестановок (информация снимается с выхода генератора 8) и размещений (информация снимается с выхода дешифратора 13)с Перестановки получаются в режиме генерации размещений при , так как .

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

В исходном состоянии счетчики 1,.,о,1 устанавливаются в нулевое состояние, .в первьш разряд регистра 4 записывается 1, а во все остальные - О, тактовая шина устройства через переключатель 7 соединяется с тактовым входом устройства. Так как в регистр 9 записано число , то на счетные входы (V) счетчиков 1,

1

N-1

И на входы (II) переносо

Q

5

0 5

сумматоров 2

0

5

0

5

0

5

N

2.1 и .2 с дешифратора 10 подаются единичные сигналы. Поэтому на выходе сумматора 2 , устанавливается код 1, на выходе сумматора 2|. - код 2 и на выходе сумматора 2 j - код З

По переднему фронту первого тактового импульса через открытый элемент И 3|g в счетчик 1 записывается 1. Поэтому на выходе сумматора 2 установится код Таким образом, по первому тактовому импульсу на выходах всех сумматоров устанавливается сочетание Второй и третий тактовые импульсы поступают через открытый элемент И 3ц, на счетчик 1|, устанавливая в нем последовательно коды 2 и 3. Соответственно этому на выходах сумматоров 2 , N-I

и

2 устанавливаются сочетания 125 и 126. После установления на выходе сумматора 2 кода 6 в схеме 15 сравнения происходит сравнение кодов и на ее выходе появляется единичньй сигнал Поэтому элемент ЗАПРЕТ 6 от- крьшается и по заднему фронту третье- то тактового импульса, который поступает на вход синхронизации (с) регистра 4, происходит сдвиг 1 с первого выхода регистра 4 на второй,

В результате этого открываются элемент И 3 ,, и по переднему фронту четвертого тактового импульса счетчик 1 устанавливается в О, а в счетчик 1 -i записывается 1. Поэтому на выходах сумматоров 2 ,2 , 2 .i и 2, устанавливается сочетание 134. Поскольку на выходе схемы 15 сравнения теперь единичного сигнала нет, то открьшает- ся элемент ЗАПРЕТ 5 и по заднему фронту четвертого тактового импульса, который поступает на вход регистра 4, происходит установка его в исходное состояние. Поэтому пятьй и шестой тактовые импульсы вновь поступают через открытый элемент И 3 на счетчик f, Б результате на выходах сумматоров 2 ,. , 2 ,.1 и 2 последовательно устанавливаются сочетания 135 и 136. Появление кода 6 на выходе сумматора 2 вызывает срабатывание схемы 15 сравнения и появление на ее выходе единичного сигнала. Поэтому через открытьш элемент ЗАПРЕТ 6 по заднему фронту шестого тактового импульса проходит сдвиг 1 с первого выхода регистра 4 на второй.

31

Поэтому седьмой тактовьй импульс проходит через открытый элемент И 3jj.i и передним фронтом сбрасывает в О счетчик 1., и добавляет 1 в

Nсчетчике 1|, i

В результате этого в счетчиках 1, 1 N-1 n- i соответственно записываются коды О, 2, О, а на выходах сумматоров устанавливается сочетание 145.

Задний фронт седьмого тактового импульса через открытый элемент 5 устанавливает по входу R регистр 4 в исходное состояние. Поэтому повос мому тактовому импульсу в счетчик 1 записывается 1, а на выходах сумматоров устанавливается сочетание 146. При этом срабатывает схема 15 сравнения, единичным сигналом с ее выхода открывается элемент 6 и по заднему фронту восьмого тактового импульса 1 с- первого выхода регистра 4 сдвигается на второй его выхо

Девятый тактовый импульс проходит через открытьй элемент И 3,., и по переднему фронту сбрасывает в О счетчик 1HJ и добавляет 1 в счетчик 1 f,, , в котором фиксируется код 3. В результате этого на выходах сумма- торов устанавливается сочетание 156, на выходе схемы сравнения вырабатывается единичный сигнал и по заднему фронту тактового импульса, которьй поступает через открытьй элемент ЗАПРЕТ 6 на вход синхронизации регистра 4, происходит сдвиг 1 с второго его выхода на третийо Поэтом десятьй тактовьй импульс теперь поступает через открытьй элемент И и передним фронтом сбрасывает в О счетчик 1., и записывает Г в счетчик 1 1 о На выходах сумматоро в результате устанавливается сочетание 234, а задний фронт десятого импульса через открытьй элемент ЗАПРЕТ 5 регистр 4 по входу R устанавливает в исходное состояние.

Аналогичным образом устройство работает до поступления 18-го такто- вого импульсао При поступлении 18-го тактового импульса в счетчиках i, 1N-1 N-1 фиксируются соответствен) ii-itt noil

НО коды о

Г

, на выходах

сумматоров устанавливается сочетание 356 и 1 передвигается на третий выход регистра 4 о Передний фронт 19-го тактового и тульса через открытьй элемент И 3. ij сбрасывает в О

0

4

д n

5 Q

g

0

5

5

744

счетчик 1,j., и к coдepжимo ry- счетчика 1 J добавляет 1 и в нем фиксируется код 3. Поэтому на выходах сумматоров устанавливается сочетание 456, срабатывает схема 15 сравнения и по заднему фронту 19-го тактового импульса через открытьй элемент ЗАПРЕТ 6 происходит сдвиг 1 с 3-го выхода регистра 4 на 4-й. Двадцатый импульс передним фронтом через открытьй элемент И 3|у. сбрасывает в О счетчик 1.5 , а счетчик 1 ц/,, единицу не записывает, так как на его разрешающем входе стоит нулевой потенциал. Поэтому на выхрдах сзт маторов устанавливается сочетание 123. Задний фронт 20-го импульса через открытьй элемент ЗАПРЕТ 5 устанавливает регистр 4 в исходное состояние. После этого формирование сочетаний повторяется.

В режиме генерации размещений тактовая шина устройства через переключатель 7 подключается к выходу генератора 8 перестановок, а размещения снимаются с выходов дешифратора 13 Принцип формирования размещений состоит в следующем. Каждое новое сочетание формируется аналогично описанному ранее, но не тактовым импульсом, а импульсом с выхода генератора 8 перестановок. После этого генератор 8 осуществляет полньй перебор перестановок в пространственно-временной форме, т.е. при каждой серии из трех входных тактовых и тульсов соответствует очередность появления импульсов на первых трех выходах генератора 8 перестановок.

Данная очередность импульсов представлена в табл.2 о

Сигналы с выходов генератора 8 перестановок управляют работой элементов И 11;,,...,11щ, выполняющих роль коммутаторов. Если, например, на выходах сумматоров 2,...,2д| импульсом с выхода генератора перестановок установлено сочетание 136, то в соответствии с 1-и перестановкой к входам дешифратора 13 через

элементы И 11f(, 11.1 и . последовательно подключены сумматоры 2, N-i ы-г i соответственно этому единичньй сигнал последовательно появляется на 1-м, 3-м и 6-м выходах дешифратора 13. Затем на выходах генератора 8 формируется 2-я перестановка, в соответствии с которой к входам дешифратора 13 последовательно подключаются сумматоры 2.

-N-г

2м-1

-л/ а единичньй сигнал последовательно появляется на 1-м, 6-м и 3-м выходах. Так происходит до тех пор, пока не переберутся все перестановки. Сигнал об окончании перебора всех перестановок появляется на выходе генератора 8. По этому сигналу формируется новое сочетание и процесс перебора перестановок повторяется для данного сочетания до тех

пор, пока не переберутся все сочета- 15 выход последнего элемента И (Н+1)-й

группы, выход 1-го элемента которой соединен с тактовым входом i-го счетчика группы (,N) и входом сброса (i+1)-ro счетчика группы, выходы К- го счетчика группы (,N) соединены с входами первой группы К-го сумматора группы, входы второй группы которого соединены с выходами (К-1)-го сумматора группы и первыми входами элементов И j-й группы (,N+1), выходы элементов И с второй по (N+ 4-1)-ю групп соединены с входами элементов ИЛИ группы, выходы которых и

Изобретение относится к вычислительной технике и предназначено для решения комбинаторных задач. Цель изобретения - повьппение быстродействия при формировании сочетаний и размещений. Оно содержит группу счетчиков, группу сзт маторов, группу элементов И, регистр сдвига, элементы ЗАПРЕТ, переключатель, генератор перестановок, регистры, два дешифратора, N групп элементов И, группу эле- ментовРШИ, схему сравнения.„Устройство предназначено для генерации кодовых последовательностей, для построения специализированных вычислительных устройство 1 ил.-,2 табл.

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

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

Устройство для перебора сочетаний размещений и перестановок, содержащее группу счетчиков, первый регистр первую группу элементов И, первый дешифратор, группу элементов ИЛИ и схему сравнения, отличающееся тем, что, с целью повьшения быстродействия при формировании сочетаний и размещений, оно содержит второй регистр, два элемента ЗАПРЕТ, группу сумматоров N групп элементов И, генератор перестановок, регистр сдвига и второй дешифратор, причем тактовый вход устройства соединен с одноименньм входом генератора перестановок и через переключатель с первыми входами элементов И первой группы и с инверсным входом первого элемента ЗАПРЕТ, с прямым входом второго элемента ЗАПРЕТ, выходы которых соединены соответственно с входом сброса и тактовым входом регистра сдвига, выходы которого соединены с вторыми входами элементов И первой

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

которого соединены с входами первого регистра, выходы которого соединены с входами второго дешифратора и информационными входами генератора перестановок, тактовьш выход которого

соединен с переключателем, а i-й выход генератора перестановок соединен с вторыми входами элементов И j-й группы, К-й выход второго дешифратора соединен со счетным входом К-го счетчика группы и входом переноса К-го сумматора группы, входы второй группы первого сумматора группы соединены с первым выходом второго дешифратора, выходы последнего сумматора группы

соединены с первыми входами элементов И (Ы+1)-й группы и входами первой группы схемы сравнения, входы второй группы которой соединены с выходами второго регистра, входы которого сое-

динены с информационными входами второй группы устройства, выход схемы сравнения соединен с прямым входом первого элемента ЗАПРЕТ и инверсным входом второго элемента ЗАПРЕТ,

аблица 1

140U7 8

Продолжепие табл.1

1

vvy V