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

(Б) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ

Изобретение относится.к автоматике и вычисл1йтельной технике и может быть использовано для .решения коибинаторных задач при построении коммуУирующих схем, адресных схем запоминающих устройств; а также устройств контроля. Известно устройство для перебора сочетаний, содержащее последовательно включенные счетчики с коэффициентом пересчета,.отличающимся , на единицу, схемы И и ИЛИ,, триггеры. Устройство обеспечивает подсчет числа.сочетаний сГ при всех значен Однако это устройство не осущест ляет перечисления сочетаний. Наиболее близким техническим решением к изобретению является уст ройство для перебора сочетаний, содержащее матрицу ячеек из п строк и п столбцов, каждая ячейка- которой со держ1 т триггер, элемент И и два зле мента ИЛИ, причем в каждой ячейке первый вход первого элемента И соединен с прямым единичным, а второй вход- с инве Ьсным единичным входами триггера, выход первого элемента И подключен к первому входу пер«. вого элемента ИЛИ,, второй вход которого соединен с единичным выходом триггера, выход первого элемента ИЛИ - к первому входу первого элемента И следующей ячейки строки, выход второго элемента ИЛИ соединен с единичным инверсным входом триггера, л первый вход второго элемента ИЛИ г-с выходом второго элемента ИЛИ последующей ячейки столбца 121. Однако такое устройство имеет низкое быстродействие. Цель изобретения - повышение быстродействия устройства. Поставленная цель достигается тем, что в ячейки матрицы, с третьего столбца, введены первый, второй, третий и четвертый вспомогательные элементы И, а в ячейки матрицы, находящиеся на пересечении 1-й строки, i ,2 ,. .. , п, и j-ro столбца, j 1,... ,л-i + 1, введены третий и четвертый элементы ИЛИ, второй, третий и четвертый элементы И , в ячейки первого столбца матрицы введен дополнительный элемент И, причем в каждой ячей ке матрицы, начиная со второй строки, выход третьего элемента ИЛИ соединен с вторым входом второго элемента ИЛИ предыдущей ячейки стол ца и с первым входом второго элемен И предыдущей ячейки строки, первый второй входы третьего элемента ИЛИ соединены соответственно с единичны выходом триггера и выходом второго элемента И, второй вхбд которого п ключен к шине режима, первый вход третьего элемента И подсоединен к единичному выходу триггера, второй вход третьего элемента И - к второму входу третьего элемента И ячейки предыдущего столбца последующей строки и к первой управляющей шине матрицы, в ячейках первой строки матрицы выход третьего элемента И соединен с одним входом четвертого элемента И, другой вход которо го подключен к второй управляющей шине матрицы, выход четвертого элемента И - с первым входом четверто:го элемента ИЛИ, второй вход которо соединен с выходом четвертого элеме та ИЛИ, последующей ячейки строки, в ячейках , начиная с третьего столбца матрицы, выход первого элемента ИЛИ и нулевой выход тригге ра через первый и второй вспомогательные элементы И подключены соответственно к первым входам первого элемента И и к нулевому входу триг гера доследующей ччейки строки, к входам первого , второго , третьего и четвертого вспомогательных элементов И подключен второй вход третьего элемента И ячейки, в ячейках первого столбца матрицы первый вход дополнительного элемента И со динен с шиной режима, второй вход подключен к выходу первого элемента ИЛИ последней ячейки строки, выход дополнительного элемента И через элемент ИЛИ соединен с тактовым входом триггеров ячеек последующей строки. На фиг. 1 изображена структурная схема устройства для перебора с 4 для п 6; на фиг. 2- принцип1иальная схема ячейки устройства для перебора сочетаний. Устройство для перебора сочетаний содержит ячейки 1-36 (фиг.1) , которые включены в матрицу из шести строк и шести столбцов. В состав каждой ячейки матрицы входят триггер 37f элемент И 38, элемент ИЛИ 39 (фиг.2) Вход 0 ячейки матрицы объединен с одним входом элемента И 38 и,единичным входом триггера 37. Другой вход элемента И 38 подключен к еди ничному инверсному входу триггера 37, объединен с выходом 41 ячейки и соединен с выходом элемента ИЛИ t2, один вход которого объединен с входом 3 ячейки, а другой - с входом А4 ячейки.Выход элемента И 38 подключен к одному входу элемента ИЛИ 39, ДРУ гой вход которого связан с единичным: выходом триггера 37 и объединен с выходом 5 ячейки. Выход элемента 1 ИЛИ 39 объединен с выходом 6 ячейки, выход 7 ячейки - с нулевым выходом триггера 37, нулевой.вход KOTQрого объединен с входом 48 ячейки. Вход 4Э ячейки объединен с выходом 50 этой же ячейки и подключен к тактовым входам триггера 37. Выход 45 каждой ячейки матрицы подключен к управляющему входу элемента И 51 (фиг. 1), другой вход которого подсоединен к вертикальной входной шине 52, а выход элемента И 51 подключен к горизонтальной выходной щине 53. Выходы 46, 47 и 50 каждой ячейки матрицы подключены соответственно к входам 40, 48 и 49 следующей в строке ячейки, причем выходы 46 и 47 последней в строке ячейки подсоединены соотвественно через линии 54 задержки и через элементы ИЛИ 55 и И 5б к вхо-дам 40 и 48 первой ячейки в этой же строке. Одни из входов элемента ИЛИ 55 и инверсный вход элемента И 5б подсоединены с шине 57 записи единицы. Выход -41 каждой ячейки матрицы подключен к входу 43 соседней сверху ячейки в столбце. К входу 44 каждой ячейки матрицы подсоединен 1 выход 45 соседней снизу ячейки в столбце. в ячейки 1-21 устройства введен элемент И 58j у которого один вход объединен с входом 59 ячейки, а другой вход - с входом 60 ячейки. Выход элемента И 58 подключен через элемент ИЛИ б1 к выходу 62 ячейки. Вход 60 ячеек 7-19 подключен к шине 63. режима, которая подключается в каждой строке матрицы к одному входу дополнительного элемента И 6, другой вход дополнительного элемента И 64 подсоединен к выходу последней ячейки строки, а выход эле мента И 6 через элемент ИЛИ 65 подключен к входу 4Э первой ячейки соседней снизу строки матрицы. Единичный выход триггера 37 ячеек по ключен, к одному входу элемента И 66, другой вход которого связан с одним входом элемента И 67. Другой вход элемента И 67 объединен с входо 68ячейки..Выход элемента И 67И вход 69ячейки через элемент ИЛИ 70 подсо динены к выходу 71 ячейки матрицы.Вы ход 72 каждой из ячеек 2-21 подключе к входу 73 ячейки, расположенной в соседней нижней строке и в соседнем слева столбце. Выход 71 каждой из ячеек 2-6, 8-11, 13-15, 17,18 и 20 подсоединен к входу б9 соседней слева ячейки в строке. Выходы 46 и 47 ячеек 3-5,9-11,1М5 и 18 подключены через вспомогательные элементы И 74 к входам 40 и 48 nepBofj |пчейки в этой же строке матриц)) и че рез вспомогательные элементы И 75 к входам 40 и 48 .соседней справа яче ки в строке. К входам 73 ячеек 1-6 и входам элементов И 74 и 75 подключены первые управляющие шины 76 матр цы, а к входам 68 ячеек 1-21 подсоединены вторые управляющие щины 77 матрицы. Выходы 72 йчёек 1,7,12,16 и 21 подключены через элементы ИЛИ 78, эдемент И 79 и элемент ИЛИ 80 к индикатору конца 81, к нему же через элементы И 82 и ИЛИ 80 подсоединены выходы 45 ячеек 1,,25,30 и 36. Вход элемента И 79 подключен к шине 63 режима. Устройство функционирует в двух режимах ; перестановок и сочетаний. Для настройки устройства на режим перестановок на шину 63 реиима подается нулевой сигнал, который закрывает элементы И 64 и элементы И 58 в ячейках 7-10, 12-14;- 1б,17,19. Нулевой сигнал, поступающий на пер- управляющие шины 76 матрицы, закрывает элементы И 67 в ячейках , а нулевой сигнал на вторых управляющих шинах 77 матрицы закрывает 55 элемента И б7 в ячейках 1-21 комбинаторной матричной схемы. Схема в режиме перестановок работает следующим образом. На входы ячеек 21,19,16,12, 7,1 первого столбца матрицы подаются сдвинутые относительно друг друга на время х последовательности импульсов: на вход 49 ячейки 7 последовательность с периодом Т, на вход 49 ячейки 1 - запаздывающая относительно предыдущей последовательность с периодом Т, на вход 49 ячейки 12- с периодом 2Т, на вход 49 ячейки 16- с периодом 6Т, на вход 49 ячейки 19 -с периодом 24Т ина вход 49 ячейки i1 - с периодом 120Т. В общем случае период последовательности, поступающей на вход ячейки в 1-той строке матрица, равен Т(1-1 ). В первом такте на шину 57 записи единицы поступает сигнал длительностью ti-1 ), гдеь длительность импульса управляющей . последовательности. В этом такте в ячейки 21, 20,18,15,1,6 записываются единицы. Таким образом, схема реализует базовую перестановку 1, 2,3,4,5,6, т.е. в соответствии с заданной перестановкой, вертикальные входные шины 52 через элемент И 51 подключаются к горизонтальным выходным шинам. Первая слева верти шина подключ ается к первой снизу горизонтальной вторая слева /вертикальная - к второй снизу горизонтальной шине и т.д. Во втором такте единица, записанная в триггер 37 ячейки 7-10 на вход 49 данной ячейки, сдвигается в ячейку 22 этой же , строки. Единица, записанная а триггер 37 ячейки 6, под действием тактового импульса, поступающего через ячейки 1-5 на вход ячейки 6 (фиг.З), проходит через линию 54 задержки, элемент ИЛИ 55, и через элементыИ 38 ячеек 1-4 записывается в триггер 37 ячейки 5, на входы 43 и 44 которой поступают разрешающие нулевые сигна/ш соответственно с выходов 41 и 43 ячейки 11, передающиеся через элемент ИЛИ 42 на диничный инверсный вход триггера 37 чейки 5. Элементы И 38 ячеек 1-4 ткрыты единичными сигналами, поступащими на входы 40 с выходов 45 ячек 21 ,20,18, в триггерах которых аписаны единицы. 79 В результате , во втором такте устройство генерирует перестановку 1,2j3,,6,5. За тактов схема генерирует все 6 перестановок. Последней перестановке 6,5,,3,2,1 соответствует расположение единиц в триггерах 37 ячеек 1,8,И,25,30,36, которое фиксируется с помощью элемен тов И 82, и единичный сигнал через элемент ИЛИ 80 поступает на индика,тор 81 конца. Получение всех п. перестановок иллюстрируется примером для . Базовой перестановкой, из которой последовательно получаются все остальные, является 1,2,3,,5,6, где позиции цифр о перестановке соответствуют номерам выходных горизонтальных шин и порядке возрастания слева направо, а цифры, стоящие на этих позициях, - номерам входных вертикальных шин, подключенных к соответствующим вертикальным входным шинам . Пример Г2k653 1 2 3 5 6 1 2 3 5 6 5 12536A 1253 6 1 2 3 5 t 6 125t63 2 г 5 ( k 125i 36 1 2 3 6 i 5 1 i 3 6 5 t 1256i 3 1 2 i 3 6 5 12563Л 1 2 t 3 5 6 65tt231 1.2 i 5 3 6 65t312 65 321 124635 Работу устройства в режиме сочетаний рассмотрим на примере получен ния всех С 1 сочетаний, где п Е, Устройство осуществляет всевозможны выборки трех вертикальных входных ш из пяти и подключение их к трем вых ным шинам. Для настройки устройства на режим сочетаний на шину 63 режим подается единичный сигнал, который рывает элементы И 64, И 79, элемент И 59 в ячейках 7-10, 12-14,16,17,19 Для установки п«5 на пятую слева, первую управляющую шину 76 атрицы подается единичный сигнал-, который открывает вспомогательные элементы И 74 и закрывает вспомогательные эл менты И 75,подключенные к выходам 46 и 47 ячеек 5,10,14,кроме того,единич ный сигнал через вход ячейки 5 посту . пает на элементы И 66 ячеек 5,10,14 и открывает их. Для установки К«3 на третью свер ху вторую управляющую шину 77 матри 5 м подается единичный сигнал, который оступает через входы 68 ячеек 15 на элементы И 67 и открывает, их. На шину 57 записи единицы подается единичный сигнал длительностью 2Т+Т;, где f - длительность тактирующего импульса. На входы Э ячеек 12,7,1 пода ются сдвинутые относительно друг друга щ время t тактиру ли(ие импульсы. В начальный момент времени триггера 37 всех ячеек 1-36 сброшены в ноль (цепи сброса в ноль не пока.заны). На единичный вход триггера 37 ячейки 12 с шины 57 через элемент ИЛИ 55 и вход тактового сигнала j подаваемого на вход 49, и разрешающего нулевого сигнала, снимаемого с единичных выходов триггеров 37 ячеек 16,19,21 и поступающего через вы ходы 41 и 45 ячейки 1б соответствен но на входы 43 и 44 ячейки 12 устанавливает триггер 37 ячейки 12 в единицу. Единичный сигнал на выходе триггера 37 ячейки 12 через выход 45 ячейки.12 поступает на входы 40 48 ячеек 7 и 1 соответственно и запрещает запись единиц в триггеры 37 ячеек 7 и 1, при этом открываются элементы М 38 ячеек 7 и 1. Единичный сигнал, поступающий на вход 40 ячейки 12, через элемент И 38 не проходит, так как он .закрыт нулевым сигналом, поступающим на входы 43 и 44 ячейки 12. Единичный сигнал, который подан на шину 57 записи единицы, проходит через элемент ИЛИ 55 на вход 40 ячейки 7, через открытый элемент И 38 этой ячейки, через элемент ИЛИ 39 и выход 46, вход 40 ячейки 8 и устанавливает в единицу триггер 37 ячейки 8, на единичный инверсный вход которого подан разрешающий нулевой сигнал с единичных выходов, триггеров 37 ячеек 13,17,20 и 32. Нулевой сигнал с единичных выходов триггеров 37 ячеек 13,17,20 и 32 поступает также на элемент И 38 ячейки 8 и закрывает его, прерывая , таким образом, дальнейшее распространение единичного сигнала, поступающего на вход 40 ячейки 8. Единичннй сигнал с выхода триггера 37 ячейки 8 через выход 45 поступает на вход 44 ячейки 2 и далее на элемент И 38, и единичный вход триггера 37 ячейки 2. Единичный сигнал, поступающий на вход 40 ячейки 1, проходит через рытые элементы И 38, элементы ИЛИ 39 ячеек 1 и 2 и в момент действия такт вого импульса записывается в триггер 37 ячейки 3, так как на единичный инверсный вход триггера подаетс разрешающий нулевой сигнал с выходов триггеров 37 ячеек 33, 28, l8;ii и 9 который закрывает также элемент И 3 ячейки 3 и прерывает распространение единичного сигнала дальше по строке. Таким образом, если входным шинам 52 поставить в соответствие буквы а, Ь, с, d,e,,.f ,то реализуетс сочетание а, Ь,с. Позиции в этом сочетании соответствуют номерам выходных шин (снизу вверх), а буквы обозначению входных-шин, т.е. входная вертикальная шина а t помощью элемента И 51, на который с выхода триггера 37 через выход ячейки 12 подается разрешающий сигнал, подключается к третьей сверху горизонтальной выходной шине 53, входная шина Ь - к второй сверху горизонтальной выходной шине, входная шина с - к первой сверху выходной шине. С этого момента времени тактовые импульсы подаются только на ячейки 1,Z,3, 6. Под действием следующего тактового импульса реализуется сочетание а, Ь, d, т.е. единица, записанная в триггера 37 ячейки 3, сдвигается в триггер 37 ячейки 4, в результате чего единичный сигнал, снимаемый с выхода триггера 37 ячейки А, открывает элемент И 51 и осуществляет подключение соответствующей вертикаль ной входной шины 52 к первой сверху горизонтальной выходной шине 53, под действием следующего тактового импульса единица записывается в триггер 37 ячейки 5 Таким образом, комбинаторная схема реализует сочетание а,Ь. е. Под действием последующего тактового импульса единичный сигнал с выхода 6 ячейки 5 через открытые элементы И 7 поступает . далее через открытый единичный сигнал с шины 63 режима, элемент И б, элемент ИЛИ 65 на вход 3 ячейки JB, и, следовательно, тактовые входы триггера 37 ячейки 8, сдвигая единицу из триггера 37 ячейки 8 в триггер 37 я.чейки, 9. Единичный сигнал с вы.хода триггера 37 ячейки 9 через вы-. ход 5 поступает на вход 59 ячейки 8 и через открытый единичным .сигналом с шины 63 режима элемент И 58, элемент ИЛИ 61 прступает на выход 62, и далее 5510 через вход 40 ячейки 2 на вход эяемента И 38. Кроме того., единичный сиг нал с выхода триггера 37 ячейки 9 выхода открывает элемент И 38 ячейки 3, в результате чего сигнал выхода 46 ячейки 5 через линию задержки 5, элемент ИЛИ 55, и через открытые элементы И 38,ИЛИ 39 ячеек 1-3 запишется в триггер 37 ячейки, . Таким . образом схема реализует перестановку а,с,а. Через тактов е иницы сдвинутся в триггеры 37 ячеек 1А, 10,5, и единичные сигналы с выхода триггеров 37 ячеек Т,10,5 через открытые элементы И 66 ячеек 5, Ю, Ц и от(фытые элементы И 67 , ИЛИ 70 ячеек ,,Й, 13, 12 поступает через элементы ИЛИ 78, И 79, ИЛИ 80 на индикатор конца 81. Работа схемы в режи, ме сочетаний поясняется следующим примером. а Ь с а Ь d а d е а с d асе а d е bed bee b d е с d ё Формула изобретения Устройство для перебора сочетаний, содержащее матрицу ячеек из п строк и п столбцов, каждая ячейка которой содержит триггер, элемент И и два элемента ИЛИ, причем б каждой ячейке первый вход первого элемента И соединен с прямым единичным, а второй вход с инверсным единичным входами триггера, выход первого элемента И соединен с первым входом первого элемента ИЛИ, второй вход которого соединен с единичным выходом триггера, выход первого элемента ИЛИ соединен с первым входом первого элемента И следующей ячейки строки, выход второго элемента ИЛИ соединен с единичным инверсным входом тргиггера, а первый вход второго элемента ИЛИ соединен с выходом второго элемента ИЛИ последующей ячейки столбца, отличающеес я тем, что, с целью повышения быстродействия устройства, в ячейки матрицы, начиная с третьего столбца,введены первый, второй , третий и четвертый вспомогательные элементы И, a в ячейки матрицы, находящиеся н пе|}есечении f-й строки, 1« 1,2 ,... ,п и j-ro столбца, J-1,.. . , п- 1 + 1, введ иы третий и четвертый элементы ИЛИ, второй, третий и четвертый элементы И, в ячейки первого столбца матрицы введен дополнительный элемент И, причем в каждой ячейке матрицы, начиная с второй строки, выход третьего элемента ИЛИ соединен с вторып входом второго элемента ИЛИ предыдув ей ячейки столбца и с. первым входом второго элемента И предыдущей ячейки строки, а перьый и второй входы тре тьего элемента ИЛИ соединены-соответственно с единичным выходом триггера и выходом второго элемента И,вто рой вход которого подключен к шине режима, первый вход третьего элемента И подключен к единичному выходу триггера, второй вход третьего элемента И подключен к второму входу третьего элемента И ячейки предыдущего столбца последующей отро ки и .с первой управляющей шине матри цы, в ячейках первой строки матрицы выход третьего элемента И под- ключен к одному входу четвертого элемента И, другой вход которого под ключен к второй управляющей шине матрицы, выход четвертого элемента И соединен с первым входом четвертого элемента ИЛИ, второй вход которого соединен с выходом четвертого элемента ИЛИ последующей ячейки строки, в ячейках, начиная с третьего столбца матрицы, выход первого элемента ИЛИ .и нулевой выход триггера через первый и второй вспомогательные элементы И подключены соответственно к первым входам первого,элемента И и к нулевому входу триггера последующей ячейки строки, причем к входам первого, второго , третьего и четвертого вспомогательных элементов И подключен второй вход третьего элемента И ячейки, в ячейках первого столбца матрицы первый вход дополнительного элемента И соединен с шиной режима, второйвход подключен к выходу первого элемента ИЛИ последней ячейки строки, выход дополнительного элемента И через элемент ИЛИ соединен с тактовыми входами триггеров ячеек последующей строки. Источники информации, , принятые во внимание при экспертизе 1.Авторское свидетельство СССР If 376606, кл. О Об F 15/20, 1971. 2.Патент США Зб31397,3 0-172, 5,1971 (прототип X