Устройство для перебора сочетаний Советский патент 1976 года по МПК G06F15/20 

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

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

Устройство содержнт триггер 1 перезаписи, первую группу элементов «И 2, запоминающий регистр 3, блок 4 перезаписи, управляющий триггер 5, основной регистр 6, вторую группу элементов «И 7, блок 8 управления, вспомогательный регистр 9, первый элемент задержки 10, второй элемент задержки И, триггер 12 фиксации двойного пересчета, триггер 13 фиксации пересчета, третий элемент «И 14, первый элемент «И 15, второй элемент «И 16, четвертый элемент «И 17, третий элемент задержки 18, разрешающий триггер 19, пятый элемент «И 20, дополнительный триггер 21, элемент «ИЛИ 22, шину 23 тактовых импульсов, шину 24 окончания перебора и шину 25 входного импульса.

Первоначально происходит устаноВКа в исходное состояние всех триггеров устройства. В исходном состоянии в «единичном положении находится только триггер 1 перезаписи. Остальные триггеры находятся в «нулевом положении. Для перебора всех сочетаний из М элементов но N производится запись единиц в первые N разрядов основного регистра 6. Дальнейшая работа устройства происходит по тактам Гь Tz и Тз. В такте Ti с выходов основного регистра 6 считывается очередное сочетание из М элементов по N и устанавливается в «нулевое положение управляющий триггер 5. В такте Тг по шине 25 поступает входной импульс. Импульс с шины 25 поступает на вход первого элемента задержки 10, на первый вход третьего элемента «И 14 и на импульсный вход блока 8 управления. Так как на втором «входе третьего элемента «И 14 нет сигнала (триггер 13 фиксации пересчета находится в «нулевом положении), то триггер 12 фиксации двойного пересчета остается в «нулевом положении. БлОК управления 8 онределяет первый старший разряд основного регистра 6, который содержит «единицу при уелоВИИ, что следующий за ним разряд содержит «ноль. В данном случае это Л-й разряд. На N-M выходе блока управления 8 появляется имлульс, который через N-E элемент «И 2 первой группы осуществляет запись «единицы в разряд запоминающего регистра 3 н перезапись единицы из разряда основного регистра 6 в (N-}-l)-u разряд основного регистра 6. После этого импульс с выхода первого элемента задержки 10 переводит в «нулевое положение триггер 1 перезаписи и нодтверждает «нулевое ноложение триггера 13 фиксации пересчета. Если последний разряд основного регистра 6 находится в «единичном положе1нии, то импульс с выхода нервого элемента 3 задержки 10 через пятый элемент «И 20 переводит в «единичное положение разрешающий триггер 19. Так как в данном случае считаем, что в последнем разряде основного регистра 6 «единица отсутствует, то после первого импульса, поступившего по шине 25, разрешающий триггер 19 останется в «нулевом положении.

Таким образом, после первого импульса, поступившего по шине 25, основной регистр 6 находится в состоянии

Л---1

iTTTTTTi 0100...00,

м

а в запоминающем регистре 3 в Л-м разряде хранится «единица. В этом случае такт Гз может .быть пропущен.

При поступлении второго, третьего и других импульсов до (М-N)-TO импульса в тактах Т2 по шине 25 все триггеры устройства находятся в «нулевом положении, и но каждому поступающему по шине 25 импульсу осуществляется продвижение последней «единицы в основном регистре 6 на один разряд вправо.

Таким образом, после (М-yV) импульсов, поступивших по шине 25, основной регистр 6 имеет следующие состояния:

N

111 ... 11000... 00 - исходное состояние;

М

111 ... 101000 ... 00 - поступил 1-й имнульс по шине 25;

111 ... 100100 ...00 -поступил 2-й импульс по шине 25;

111 ... 100010 ... 00 - поступил 3-й импульс по шине 25;

111 ... 100000... 10 - поступил (M-N-l) импульс по шине 25;

ifl ... 100000...01 -поступил (M-N) импульс по шине 25.

В каждом такте TI считывается предыдущее положение основного регистра 6. Такты Тз при этом могут быть опущены.

Затем в очередном такте Ti считывается сочетание из М элементов по N, которое находится в основном регистре 6. В данном случае

N

сочетание 111.. .11000001 в такте Га ступает импульс по шине 25. Опять блоком управления 8 осуществляется сдвиг «единицы из первого старшего разряда основного регистра 6, следующий разряд после которого находится В «нулевом положении. В данном случае основной регистр б находится -в состоянии1ТТТГ7Т0100...01. м в отличие от предыдущих случаев на втором входе пятого элемента «И 20 имеется сигнал, так как последний разряд основного регистра б находится в «единичном положеСледовательно, нмнульс с выхода первого элемента задержки 10, поступив на первый вход пятого элемента «И 20, переводит в «единичное положение разрешаюший триггер 19 и дополнительный триггер 21 (через элемент «ИЛИ 22) и осуществляет нерезапись содержимого основного регистра б (кроме нервого разряда) через вторую группу элементов «И 7 во вспомогательный регистр 9. Кроме того, на вход второго элемента задержки П поступает импульс, который, после задержки, перебрасывает в «единичное положение триггер 13 фиксации пересчета. В такте Гз по шине 23 поступает серия из М вспомогательных тактовых ИМПУЛЬСОВ (), которые через четвертый элемент «И 17 поступают на продвижение запоминающего регистра 3 и вспомогательного регистра 9. Кроме того, в .каждом такте ( осуществляется перевод в «нулевое положение дополнительного триггера 21 и опрос первого элемента «И 15 и второго элемента «И 16. При продвижении «единицы в запоминающем репистре 3 осуществляется занись «единицы или «нуля в соответствующий разряд основного регистра б в зависимости от состояния блока 4 перезаписи, управление которым происходит управляющим триггером 5. Если унравляющий триггер 5 находится в «нулевом положении, то в разряды основного регистра б записываются «единицы и наоборот. Так как первоначально управляющий триггер 5 находится в «нулевом ноложении, то по первому такту t происходит запись «единицы в основной репистр б (в данном случае в f.-V-f-l) разряд, так как в .V-м разряде запоминающего регистра 3 записана «единица). Триггер 12 фиксации двойного цересчета находится в «нулевом положении и разрешает сборку первого элемента «И 15. Как только в последнем разряде вспомогательного регистра 9 появляется «ноль, очередным тактовым имнульсом ,- через нервый элемент «И 15 управляющий триггер 5 перебрасывается в «единичное положение, и уже при нродг.ижении запоминающего регистра 3 ИМПУЛЬСОМ /,происходит запись «нуля в очередной разряд основного регистра 6. В последующие разряды основного регистра б по тактам (t+i-tm) записываются «нули. В данном случае «единица записывается в основной регистр 6 только в () разряд, а в остальные последующие разряды только «нули. В результате получим сочетание illTTTlionoo... 00. В следующем такте Ti (если в последующем разряде основного регистра б находится «ноль) импульсом с выхода первого элемента задержки 10 происходит переброс триггера 13 фиксации пересчета в «нулевое положение, и дальнейшая работа устройства происходит аналогично. Если перед очередным тактом Т триггер 13 фиксации пересчета находится в «единичном положении и в последнем разряде основного регистра б находится «единица, то при поступлении импульса в такте Т по шине 25 перебрасывается в «единичное положение тпиггер 12 фиксации двойного нересчета. Тогда переключение управляющего триггера 5 в «единичное положение осуществляется посредством сборки второго элемента «И 16, который собирается на один такт t позже, чем собирался бы первый элемент «И 15. Это необходимо для предотвращения потери одной «единицы в основном регистре б, когда в ДВУХ иодряд цолученных сочетаниях в последнем разряде имеется «единица. Рассмотрим это на примере, когда в основном регистре б было сочетание 1ТТГТ11СЮ...0101. После очередных тактов Т, Ti, Т, триггер 13 фиксации пересчета перебрасывается в «единичное положение. Основной регистр б имеет сочетание, в котором последний разряд содержит «е;1иницу П1 ... ПОО.. . 0011. В результате этого ОКазыврется подготовлен к срабатыванию третий элемент «И 14. В очередном такте TZ поступает импл.дьс по шине 25 и срабатывает третий элемент «И 14. Триггер 12 фиксации двойного пересчета перебрасывается в «единичное положение и подготавливает к работе второй элемент «И 16. Блок управления 8 осуществляет сдвиг «единицы из (.V-2) разряда основного регистра 6 в f.V-1) разряд и занисывается «единица п (N - 2) разряд заполгипаюнгего регистра 3. Основной регистр б находится в состоянии П1. . .110100...on.Имнульс с вьтходанервого Ттг элемента задержки 10 через нятый элемент «И 20 неребрасывает в «единичное положение разрешающий триггер 19 и дополнительный триггер 21 и осуществляет перезапись содержимого основного регистра 6 во вспомогательный регистр 9. В такте TS начинается продвижение содержимого 3anoMH«aioatero регистра 3 и содержимого вспо-могательного регистра 9. Если бы управляющий триггер о иеребрасывался бы с помощью первого элемента «И 15, то iB основном регистре 6 потерялась бы одна «единица за счет того, что из запоминающего регистра 3 было бы разрешено записать две «единицы (вспомогательный регистр 9 в старших разрядах содержит подряд две «единицы) в (jV-1)-й и разряды основного регистра 6, в то время как необходимо записать «единицы в .V-й и ()-й разряды основного регистра, так как в (N-1)-м разряде уже имеется «единица. Запись «единиц в и (Л-|-1)-й разряды основного регистра 6 осуществляется в результате того, что триггер 12 фиксации двойного пересчета подготавливает -к срабатыванию второй элемент «И 16, который еще управляется «нулевым выходом дополнительного триггера 21. Дополнительный триггер 21 перебрасывается в «нулевое положение при опросе второго элемента «И 16 на один такт t позже того момента, когда в последнем разряде вспомогательного регистра 9 появится ««ОЛЬ. Вследствие этого в основной регистр 6 записывается дополнительная «единица, и тем самым Общее число «единиц в основном регистре 6 равно Л, а состояние его будет inTTTf 1011100. .00. м В дальнейшем работа устройства происходит аналогично. Окончание работы устройства происходит, когда все единицы располагаются в старщих разрядах основного регистра 6, т. е. О00...000111.. .111. В этом случае в очередном такте TI происходит считывание этого сочетания. В такте TZ импульс поступает с шины 25 на вход блока управления 8. Так как в основном регистре 6 нет ни одной «единицы после которой находится «ноль, то на шине 24 появляется импульс, который свидетельствует об окончании перебора. Формула изоб|ретения Устройство для перебора сочетаний, содержащее блок управления, блок перезаписи, группы элементов «И, регистры, триггеры, элеМенты задержки и элементы «И и «ИЛИ, отличающееся тем, что, с целью упрощения устройства, единичный выход триггера перезаписи соединен с управляющими входами первой группы элементов «И, информационные входы которых связаны со вторыми входами основного регистра и выходами блока управления, а выходы - с установочными входами запоминающего регистра, выход старшего разряда которого через третий элемент залержки соединен с нулевым входом разрешающего триггера, единичным входом триггера перезаписи и нулевым входом триггера фиксации двойного пересчета, выходы остальных разрядов - с соответствующими входами блока перезаписи, а управляющий вход - с первыми входами первого и второго элементов «И, с нулевым входом дополнительного триггера, с лправляющим входом вспомогательного регистра и выходом четвертого элемента «И, имнульсный вход которого связан с шиной та-ктовых импульсов, а унравляющий вход - с единичным выходом разрешающего триггера, единичный вход которого соединен с выходОМ пятого элемента «И, первым входом элемента «ИЛИ, управляющими входами втооой группы элементов «И и через второй элемент задержки - с единичным входом триггера фиксации пересчета, нулевой вход которого связан с нулевым входом триггера иерезаписи, с первым входом пятого элемента «И и через первый элемент задержки - с шинон входного импульса, первым входом третьего элемента «И и импульсным входом блока управления, управляющий вход которого связан с шиной «окончание перебора, а установочные входы - с нулевыми выходами основного регистра, единичный выход старшего разряда которого соединен с информационным входом соответствующего элемента «И второй группы, со вторым входом пятого элемента «И и третьим входом третьего элемента «И, а остальные выходы-с информанионными входами блока управления и информационными входами соответствующих элементов «И второй группы, выходы которых связаны с информационными входами вспомогательного регистра, нулевой выход старшего разряда которого связан со вторым входом первого элемента «И, а единичный выход старшего разряда - со вторым входом элемента «ИЛИ, выход которого соединен с единичным входом дополнительного триггера, нулевой выход которого связан со вторым входом второго элемента «И, третий вход которого соединен с единичным выходом триггера фиксации двойного пересчета, а выход - с установочным входом управляющего триггера и выходом первого элемента «И, третий вход которого соединен с нулевым выходом триггера фиксации двойного пересчета, единичный вход которого связан с выходом третьего элемента «И, второй вход которого соединен с единичным выходОМ триггера фиксасии пересчета, единичный выход управляющего триггера соединен с управляющим входом блока перезаписи, выходы которого связаны с первыми входами основного регистра.