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

 

(iii 643883

Е4иоа Советских

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

Республик (6l) Дополнительное к авт. свил-ву(22) Заявлено 10.01.77 (21}2439332/18-24

{5l) М. Кл.

О 06 ". 15(20 с присоединением заявки № (23) ПрноритетГасударетвеиюй веетет

СССР аа диан азебрвтеа6 н етнрюнй

Опубликовано 25.01.795юллетень МЗ (53) УДК 681.327 (088.8) Дата опубликовании опнсання28.01.79 (72) Автор изобретения

Г. И. Левин

Минский филиал Всесоюзного научно-исследов н проектно-конструкторского институт а" по ав предприятий промьннленности ст оительных материалов (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ,, РАЗМЕЩЕНИЙ И ПЕРЕСТАНОВОК

Изобретение относнтси к области вычислительной техники н может быть ис- пользовано в вычислительных устройстsax и машинах предназначенных дли решении задаМ, основанных на переборе сочетаний, размещений и перестановок.

Одно нз известных устройств содер жит последовательно соединенные кольпевые счетчики, узел блокировки, триггер, элементы ИЛИ и элементы задержки (1I .

1Ь

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

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

И, ИЛИ, триггеры, кереюаочатепь, коммутатор, блок управлении, выходной регистр (2) .

Недост"атком известного устройства ивлиетси его сложность. Наличие двух элементов задержки (одного на входе сброса блоков перебора, другого на уть- равлиющем входе распределители) существенно уменьшает быстродействие устройства.

Целью изобретении ивлиетси повышение быстродействии и упрощение .устройства.

Поставленнаи пель достигаетси тем, что неустройство, дли перебора сочетаний, размещений и перестановок введе. ны блок формирователей и блок делении, причем пусковаа шина устройства сов динена c ïåðâûì входом первого триггера, второй вход которого подключен к первому выходу реверсивного регистра сдвига, выход перви о триггера подклю% чен к первым входам элемента ИЛИ, вто

643883 рого триггера и первого элемента И, второй вход которого подключен к первому выходу Генератора импульсов, Bb- ход первого элемента И подключен к прямому входу раемстра сдвига, второй выход генератора импульсов подключен к первому входу второго элемента И, второй вход которого подключен к выходу м@зого триггера и второму входу элемента ИДИ, выход которого подключен ко входу генератора импульсов, третьи входы первого и второго триггеров через переключатель соединены с соответствующими входамя регистра сдвига, выход второго элемента И соединен с инверсным входом регистра сдвига, выходы зайоминакепей матрицы через последовательно соединенные блок формирователей, коммутатор и блок деления подключены к выходному регистру, выходы блока управленя, соединены с упрквлякящими входами блока деления и коммутатора.

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

)и рактеризуется простотой конструкпйй.

Схема предлагаемого устройства пред-

36 ставлена на чертеже. Оно содержит запомипаккпую матриц 1 регистр сдвига

2, элементы И 3 и 4,.триггеры 5 и 6, генератор тактовых импульсов 7; элемент ИЛИ 8, блок формирователей 9, в которых формируются коды элементтов

Oq вйходной регистр 10, переключатель 11, коммутатор 12, блок деления 13, блок управления 14. Вход триггера 5 соединен с пусковой шиной уст 40 ройства 15.

Количество горизонтальных шин, а следовательно и количество 1разрядов регистра сдвига равно Ф,.„=,. где (Дах; 45 вательности.

Для перебора перестановок (так как k» И } все контакты коммутатора

g2 замкнуты.

Для перебора размещений А и сочетаний С, размыкаются

1.

И контактов коммутатора Х2, начиная с правоГь p83pgga

Соединения горизонтальных и вертикальных шин запоминающей матрицы .

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

2, а вертикальные шины - к входам блока формирователей 9. С выходов М разрядов реверсивного распределителя 2 сделаны отводы, подключаемые через переключатель 11 (с помощью ко горого устанавливается длина последовательности) к входам триггеров 5 и 6.

Работает устройство следующим об разом. В зависимости от типа решаемой задачи, то есть перебора перестановок, размещений или сочетаний, в блок деле ния 13 заносится соответственно одно из чисел «1" (И-К ) или Ъ (И «1с И.В зависимости от размерности генери руемой устройством поспедовательпостн переюночатель 11 устанавливается i положенне t3(! /2, а в коммутаторе 12 . командой с блока управления 14 оФклкь. чаютса разряды с номерами больше к

При подаче пускового сигнала на шину

1 5 перебрасываетсй триггер 5, сигнал с его выхода подается на вход элемента И 3 и через - схему ИДИ 8 занускает генератор имнульсов 7, импульсы которо го через элемент И 3 подаются яа пря.». мой вход регистра сдвжа 2, вымавая тем. самым поочередное срабатывайиэ его разрядов- и появление на горизойтальных шинах запоминающей матрины

1 сигналов, которые йоступают через соединения в узлах матрины 1 и ее вер» тикальные шины на соответствуипаие формирователи <у блока формирователей 9..При срабатываний первого разряда

Р„регистра сдвига 2 сигнал с ъыхола этого разряда подтверждает сос тояние триггера 5. Одновременно этот же сигнал через первую вергик ця,иую шику запоминающей матрийы 1 посту» пит на формирователь О блока 4op мирователей 9 и через коммутатор 12, соответствующий элементу 43, ксщ подается в блок деления 13. Так как в режиме генерирования перестановок в блоке деления 13 записана 3., то код я„проходит на вход выходного ре гистра 10.

При переключении второго, а затем третьего разрядов регистра"сдлп з аналогичным образом на вход виходногэ регистра ХО поступают коды элемещое

43@ и C3g

643883

Поскольку на чертеже показаны зам кнутыми только те контакты коммутатора 12, которые соответствуют формирователям 61 ОЛ я 3 s то на выходном регистре 10 за девать тактов переключения распределителя 2 зафиксируютса члены 0 +g О>, йк О Р, О О1 <Ма

При срабатывании девятого разряда регистра сдвига 2 сигнал через переключатель 11 перебросит триггер 5 в ис 1о ходное состояние, снимая тем самым разрешающий сигнал с элемента И 3 и прекращая подачу импульсов на прямой вход регистра сдвига 2.

Одновременно сигнал с переключателя 15

1 1 перебросит триггер 6, с выхода которого. поступит разрешающий сигнал на элемент И 4, и через элемент ИЛИ 8, подтвердится запуск генератора импульсов 7. Следовательно, импульсы с выхода генератора 7 через элемент И 4 начнут посгупать на реверсивный эход регистра сдвига 2. Переключение разрядов регистра сдвига 2 осушествлаетса при этом в обратном порядке и соглас но информации, записанной в матрице 1, на выходном регистре зафиксируются члены 0 0f Ot„, al Cf„OI@,М, ая О„.

При срабатывании первого р разряда регистра сдвига 2 триггер 5 перебрасывается в исходное состоанйе, перебрасывая своим выходом триггер 6.

В резуна ате чего снимаетси разрешающий сигнал с элемента И 4 и нрекрешаетса поступление импульсов с выхода генератора 7 на реверсивный вход регистра сдвига 2.

Таким образом, на выходной регистр будет выдана последовательность иэ шесгя членов, являющаяся перестановкой трех элементов Oq, С4я, ot.

Аналогично устройство работает при A >3.

В ре киме генерирования размещений в блок делении 13 заносится число

"(и-t )! .

Работа устройства в этом режиме осуществляется аналогично вышеописанному. Однако на выходной регистр поступают Be все И членов генерируе-. мой яефст вки а только >, так

tt как А ", - здесь испольэуетв-В)! ся иэвест зависимость, то есть чисм ло размещений Д равно числу пересуановок, деленное на (h - 4 ) -

И 55

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

В режиме генерирования сочетаний в блок деления 13 заносится число t (tt 1) "и по аналогии с режимом генерирования размещений на выходной регистр выводятся не все tt членов пе-! рестановок а только то есть

Э

Mr!-t ai - к число сочетаний иэ И элементов по к,.ttt °

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

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

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

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

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

М 525100, кл. (j 06 F 15/32, 25.1 2.74.

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

Ж 525948, кл. 9 06 F 7/ОО, 03.09.73.

643883

Составитель И. Нирман

Реиекеор Д. МеиуриШеики Текреа Э. Чуоккк Корректор Л. Грицеико

Заказ 8023/45 Тираж 7Т 9 Подписное

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

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

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