Устройство для перебора сочетаний
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (1) 5!4295
Союз Советских
Социалистических
Ресоублик (61) Дополнительное к авт. свид-ву (22) Заявлено 12.02.73 (21) 1881582/24 с присоединением заявки № (23) Приоритет
Опубликовано 15.05.76. Бюллетень № 18
Дата опубликования описания 08,07.76 (5i) М. 1 л. G 06Г 15, 20 (осударственный комитет
Совета Министров СССР йо делам изобретений и открытий (53) УД1 681,14(088.8) (72) Автор изобретения
В. В. Епихин (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ
Изобретение относится к устройствам, осуществляющим перебор сочетаний из Л1 элементов по N.
Известные устройства для перебора сочетаний из М элементов по Л содержа- блок управления, блок перезаписи, группы элементов
«И», регистры, триггеры, элементы задержки и элементы «И» и «ИЛИ». Недостатком известных устройств является то, что при значениях N, достигающих величины (М вЂ” 1), объем оборудования становится значительным и возрастает пропорционально величине Л1.
Цель изобретения заключается в упрощении устройства при,переборах сочетаний из большого числа элементов. В описываемом устройстве это достигается тем, что единичный выход триггера перезаписи соединен с упра вляющими входами первой группы элементов «И», информационные входы которых связаны со вторыми входами основного регистра и выходами блока управления, а выходы — с установочными входами запоминающего регистра, выход старшего разряда которого через третий элемент задержки соединен с нулевым входом разрешающего триггера, един ичным входом триггера перезаписи и нулевым входом триггера фиксации двойного пересчета, выходы остальных разрядов — с соответствующ ими входами блока перезаписи, а управляющий вход — с первыми входами первого и второго элементов «И», с нулевым входом дополнительного триггера, с управляloщим входом вспомогательного регистра п выходом четвертого элемента «И», пмпульсньш
5 вход которого связан с шиной тактовых импульсов, а управляющий вход — с едпни шым
Выходом разрешаlощего триггера, единпчныЙ вход которого соединен с выходом пятого э".åмента «И», первым входом элемента «И 1И», 10 управляющими входамп второй группы элементов «И» и через второй элсмепг задержки — с единичным входом триггера фиксации пересчета, нулевой вход которого связан с нулевым входом триггера перезаписи, с первым
15 входом пятого элемента «И» и через первый элемент задержки — с шиной входного импульса, первым входом третьего элемента
«И» FI импульсным входом 0,101<2 управ;1епия, управляющий вход которого связан с шиной
20 «окончание перебора», а установочные входы — с пулевыми выходами основного регистра, единичный выход старшего разряда которого соединен с информационным входом соответствующего элемента «И» второй группы, 25 со вторым входом пятого элемента «И» и третьим входом третьего элемента «И», а остальные выходы — с информационным и входами блока управления и информационными Нходами соответствующих элеме11тов «И» второй
30 группы, выходы которых связаны с ивформаци514295 импульс
3-й импульс онными входами вспомогательного регистра, нулевой выход старшего разряда которого связан со вторым входом первого элемента
«И», а единичный выход старшего разряда— со вторым входом элемента «ИЛИ», выход которого соединен с единичным входом дополнительного триггера, нулевой выход которого связан со вторым входом второго элемента
«И», третий вход которого соединен с единичным выходом триггера фиксации двойного пересчета, а выход — с установочным входом управляющего триггера и выходом первого элемента «И», третий вход которого соединен с ну.левым выходом триггера фиксации двойного пересчета, единичный вход которого связан с выходом третьего элемента «И», второй вход которого соединен с единичным выходом триггера фиксации пересчета, единичный выход управляющего триггера соединен с управляющим входом блока перезаписи, выходы которого связаны с первыми входами основного регистра.
На чертеже представлена функциональная схема устройства, Устройство содержит триггер 1 перезаписи, первую группу элементов «И» 2, запоминающий регистр 3, блок 4 пврезаписи, управляющий триггер 5, основной регистр 6, вторую группу элементов «И» 7, блок 8 управления, вспомогательный регистр 9, первый элемент задержки 10, второй элемент задержки
11, триггер 12 фиксации двойного пересчета, триггер 13 фиксации пересчета, третий элемент «И» 14, первый элемент «И» 15, второй элемент «И» 16, четвертый элемент «И» 17, третий элемент задержки 18, разрешающий триггер 19, пятый элемент «И» 20, дополнительный триггер 21, элемент «ИЛИ» 22, шину
23 тактовых импульсов, шину 24 окончания перебора и шину 25 входного импульса.
Первоначально происходит установка в исходное состояние всех триггеров у.стройства.
В исходном состоянии в «единичном» положении находится только триггер 1 перезаписи.
Остальные триггеры находятся в «нулевом» положении. Для перебора всех сочетаний из М элементов по N производится запись единиц в первые N разрядов основного регистра б.
Дальнейшая работа устройства происходит по тактам Т1, Т и Т0. В такте Т1 с выходов основного регистра б считывается очередное сочетание из М элементов по N и устанавливается в
«нулевое» положение управляющий триггер 5.
В такте Т2 по шине 25 поступает входной импульс. Импульс с шины 25 поступает на вход первого элемента задержки 10, на первый вход третьего элемента «И» 14 и на импульсный вход блока 8 управления. Так как на втором входе третьего элемента «И» 14 нет сигнала (триггер 13 фиксации пересчета находится B «нулевом» положении), то триггер 12 фиксации двойного пересчета остается в «нулевом» положении. Блок управления 8 определяет первый старший разрядосновногорегистра 6, который содержит «единицу» при усло5
65 вии, что следующий за ним разряд содержит
«ноль». В данном случае это Л -й разряд. На
V-м выходе блока управления 8 появляется импульс, который через A-й элемент «И» 2 первой группы осущсствляет запись «единицы» в N-й разряд запоминающего регистра 3 и перезапись единицы из N-го разряда основного регистра б в (N+1)-й разряд ocHQBHoro регистра 6. После этого импульс с выхода первого элемента задержки 10 переводит в «нулевое» положение триггер 1 перезаписи и подтверждает «нулевое» положение триггера 13 фиксации пересчета. Если последний разряд основного регистра 6 находится в «единичном» положении, то импульс с выхода первого элемента 3 задержки 10 через пятый элемент «И»
20 переводит в «единичное» положение разрешающий триггер 19. Так как в данном случае считаем, что в последнем разряде основного регистра б «единица» отсутствует, то после первого импульса, поступившего по шине 25, разрешающий триггер 19 останется в «нулевом» положении.
Таким образом, после первого импульса, поступившего по шине 25, основной регистр 6 находится в состоянии с —
Ш ...И 0100. 00, а в запоминающем регистре 3 в N-м разряде хранится «единица». В этом случае такт Тз может быть пропущен.
При поступлении второго, третьего и других импульсов до (М вЂ” N) -го импульса:в тактах
Т2 по шине 25 все триггеры устройства находятся в «нулевом» положении, и по каждому поступающему по шине 25 импульсу осуществляется продвижение последней «единицы» в основном регистре 6 на один разряд вправо.
Таким образом, после (М вЂ” N) импульсов, поступивших по шине 25, основной регистр 6 имеет следующие состояния:
1 1 1 ... 1 1000 ... 00 — исходное состояние;
М
111...101000...00 — поступил 1-й импульс по шине 25;
111 ... 100100 ... 00 — поступил 2-й по шине 25;
111 ... 100010 ... 00 — поступил по шине 25;
111 ... 100000 ... 10 — поступил (M — N — 1) импульс по шине 25;
111 ... 100000 ... 01 — поступил (М вЂ” N) импульс по шине 25.
В каждом такте Т1 считывается предыдущее положение основного регистра 6. Такты Тз при этом могут быть опущены.
Затем в очередном такте Т считывается сочетание из М элементов по N, которое 1находится в основном регистре б. В данном случае
N сочетание 111...110000....01 в такте Та воМ
514295
Пl ... 10100 01.
55 ао
65 ступает импульс по шине 25. Опять блоком управления 8 осуществляется сдвиг «единицы» из первого старшего разряда основного регистра 6, следутощий разряд после которого находится в «нулевом» положении. В данном случае основной регистр б находится в состоянии
В отличие от предыдущих случаев на втором входе пятого элемента «И» 20 имеется сигнал, так как последний разряд основного регистра 6 наход1ится в «единичном» положении.
Следовательно, импульс с выхода первого элемента задержки 10, поступив на первый вход пятого элемента «И» 20, переводит в
«единичное» положение разрешающий триггер
19 и дополнительный триггер 21 (через элемент «ИЛИ» 22) и осуществляет перезапись содерж имого основного регистра 6 (кроме первого разряда) через вторую группу элементов
«И» 7 во вспомогательный регистр 9, Кроме того, на вход второго элемента задержки 11 поступает импульс, который, после задержки, перебрасывает в «единичное» поло>кение триггер 13 фиксации пересчета.
В такте Тз по шине 23 поступает серия из
M вспомогательных тактовых им» льсов (tI — t;,т), которые через четвертый элемент
«И» 17 поступают на продвижение запоминающего регистра 3 и вспомогательного регистра
9. Кроме того, в каждом такте (t! — t,,) осуществляется перевод в «нулевое» положение дополнительного триггера 21 и опрос первого элемента «И» 15 и второго элемента «И»
16. При продвижении «единицы» в запоминающем регистре 3 осуществляется запись «единицы» или «нуля» в соответствующий разряд основного регистра 6 в зависимости от состояния блока 4 пе резаписи2 управление которым происходит мправляющим триггером 5. Если управлятoщiий триггер 5 находится в «нулевом» положении, то в разряды основного регистра 6 записываются «единицы» и наоборот.
Так как первоначально управлятоптттй триггер 5 находится в «нулевом» положении, то по первому такту t1 происходит запись «едттнипы» в основной репистр 6 (в данном случае в (0+1) разряд, так как в Лт-м раз»яде запоминаю»!его регистра 3 записана «единица») .
Триггер 12 фиксации двойного пересчета находится в «нулевом» положении и пазрешает сборк первого элемента «И» 15. Как только в последнем разряде вспомогательного регистра 9 появляется «ноль», очередным тактовым импульсом (; через первый элемент «И» 15 управляютций триггер 5 перебрасывается "»
«единичттое» поло>кент!с, и уже при продгижспии запоми»атощсго рсг»стра 3»»»iльсом т происходит запись «нуля» в очередной разряд основного регистра 6. В последующие разряды основного регистра 6 по тактам (4т-1 — м) 10
40 записываются «нули». В данном случае «единица» записывается в основной регистр 6 только в (У+1) разряд, а в остальные последующие разряды только «»ул»», В результате получи2м сочетание
N — 2
П 1...1101100...00. лт
В следующем такте Т1 (если в последующем разряде основного регистра б находится
«ноль») импульсом с выхода первого элемента задержки 10 происходит переброс триггера 13 фиксации пересчета в «нулевое» положение, и дальнейшая работа устройства происходит аналогично.
Если перед очередным тактом Т, триггер 13 фикса»»и пересчета наход»тся в «единичном» положе»ии и в последнем разряде основного регист»а 6 находится «единица». то пр» поступлентти тт>!пульса в такте Т2 по шине 25 пеоебрасывается в «единичное» по,ложение тт>.,тггер 12 фиксации двойного пересчета. Тогда переключение управляющего триггепа 5 в
«единичное» положение осуществляется посредством сборки второго элемента «И» 16, который собирается на олин такт t позже, чем собирался бы первый элемент «И» 15. Это необходимо для предотвоацтенття потери одной «единипы» в основном регистре 6, когда в дв 2х подряд пол ченньтх сочетаниях в последнем раз»яде имеется «единица». Рассмотрим это на поимеое. когда в основном регистре 6 было сочетание
Л вЂ” 2
111... 1100... 0101.
ЛГ
После очередных тактов Т1, Т., Т-., триггер
13 фиксации пересчета перебпасывается в
«единичное» положение. Основной регистр 6 имеет сочетание, в котором последний разряд . 222 — 2 содержит «елит»тцу»111... 1100... 0011. В результате этого оказыв ется полготовлеH к срабатыванию третий элемент «И» 14. В очет>елном такте Т2 пост »ает тлч» 2льс тто шине
25 и соабатывает третий э.".емент «И»14, Тттиггео 12 фикса»!ил лвойного пересчета перебрасывается в «единичное» положечие и подготавлттвает к работе второй элемент «И» 16.
Блок управления 8 осуществляет сдвиг «единицы» из (V — 2) разряда основного регистра
6 в 1 — 1) разряд и записывается «единица»
12 (2222 — 2) развя з21»0.2. »1 :атон!его рсгистра 3.
Основной регистр 6 находится в состоянии м — з
111...110100...011. Импульс с выхода первого зт элемента задерхтктт 10 через пятый элемент
«И» 20 перебрасывает в «единичное» положение разрешающий триггер 19 и дополнительный триггер 21 и осуществляет перезапись со514295 держимого основного регистра 6 во вспомогательный регистр 9. В такте Т> начинается продвижение содержимого запоминающего регистра 3 и содержимого вспомогательного регистра 9. Если бы управляющий триггер 5 перебрасывался бы с помощью первого элемента
«И» 15, то в основном регистре 6 потерялась бы одна «единица» за счет того, что из запоминающего регистра 3 было бы разрешено записать две «единицы» (вспомогательный регистр 9 в старших разрядах содержит подряд две «единицы») в (Х вЂ” 1)-й и N-й разряды основного регистра 6, в то время как необходимо записать «единицы» в N-й и (Л +1)-й разряды основного регистра, так как в (N — 1)-м разряде уже имеется «единица», Запись «единиц» в Л1-й и (N+1)-й разряды основного регистра 6 осуществляется в результате того, что триггер 12 фиксации двойного пересчета подготавливает,к срабатыванию второй элемент «И» 16, который еще упр авляется «нуле1вым» выходом дополнительного триггера 21. Дополнительный триггер 21 перебрасывается в «нулевое» положение при опросе второго элемента «И» 16 на один такт
t позже того момента, когда в последнем разряде вспомогательного регистра 9 появится
«ноль». Вследствие этого в основной регистр
6 записывается дополнительная «единица», и тем самым общее число «единиц» в основном регистре 6 равно N, а состояние его будет л — з
111... 11011100 .. 00.
М
В дальнейшем работа устройства происходит аналогично.
Окончание работы устройства происходит, когда все единицы располагаются в старших разрядах основного регистра 6, т. е.
lV
000... 000111... 111.
М
В этом случае в очередном такте Т, происходит считывание этого сочетания. В такте Т импульс поступает с шины 25 на вход блока управления 8. Так как в основном регистре 6 нет ни одной «единицы» после которой находится «ноль», то на шине 24 появляется им пульс, который свидетельствует об окончаниии перебора.
Формула изобретения
Устройство для перебора сочетаний, содержащее блок управления, блок перезаписи, группы элементов «И», регистры, триггеры, элементы задержки и элементы «И» и «ИЛИ», отличающееся тем, что, с целью упрощения устройства, единичный выход триггера перезаписи соединен с управляющими входами первой группы элементов «И», информационные входы которых связаны со вторыми
4О
60 входамн основного регистра и выходами блока управления, а выходы — с установочными входами запоминающего регистра, выход старшего разряда которого через третни элемент залсржкп соединен с нулевым входом разрешающего триггера, единичным входом триггера перезаписи и нулевым входом триггера фиксации двойного пересчета, выходы остальных разрядов — с соответствующими входами блока перезаписи, а управляющий вход — с первыми входами первого,и второго элементов «И», с нулевым входом дополнительного триггера, с управляющим входом вспомогательного регистра и выходом четвертого элемента «И», импульсный вход которого связан с шиной тактовых импульсо в, а управляющий вход — с единичным выходом разрешающего триггера, единичный вход которого соединен с выходом пятого элемента «И», первым входом элемента «ИЛИ», управляющими входами второй группы элементов «И» и через второй элемент задержки — с единичным входом триггера фиксации пересчета, нулевой вход которого связан с нулевым входом триггера перезаписи, с первым входом пятого элемента «И» и через первый элемент задержки — с шиной входного импульса, первым входом третьего элемента «И» и импульсным входом блока управления, управляющий вход которого связан с шиной «окончание перебора», а установочные входы — с нулевыми выходами основного регистра, единичный выход старшего разряда которого соединен с информационным входом соответствующего элемента
«И» второй группы, со вторым входом пятого элемента «И» и третьим входом третьего элемента «И», а остальные выходы — с информапионными входами блока управления и информационными входами соответствующих элементов «И» второй пруппы, выходы которых связаны с информационными входами вспомогательного регистра, нулевой выход старшего разряда которого связан со вторым входом первого элемента «И», а единичный выход старшего разряда — со вторым входом элемента «ИЛИ», выход которого соединен с единичным входом дополнительного триггера, нулевой выход которого связан со вторым входом второго элемента «И», третий вход которого соединен с единичным выходом триггера фиксации двойного пересчета, а выход— с установочным входом управляющего триггера и выходом первого элемента «И», третий вход которого соединен с нулевым выходом триггера фиксации двойного пересчета, единичный вход которого связан с выходом третьего элемента «И», второй вход которого соединен с единичным выходом триггера фиксасии пересчета, единичный выход управляющего триггера соединен с управляющим входом блока перезаписи, выходы которого связаны с первыми входами основного регистра.
514295
Составитель A. Горностаев
Техред А. Камышникова
Редактор Л. Тюрина
Корректор О. Тюрина
Типография, пр. Сапунова, 2
Заказ 1848, 0 Изд. Хе 1343 Тираж 864 Подппснсе
ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д. 4/5
