Устройство для перебора сочетаний

(5)М. Кл присоединением заявки Г 15/20 аараюай квинтетИВРам взебрвтвяяйн втавытяй. И. Романкевич икторов, Ю О. В Киевский. ордена Ленина политехнический иногитуим. 50-летия Великой Октябрьской социалистйчреволюции(71) Заяв УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ тое нвенияении хем естИзобретение отн в матике и вычислите к может быть использ ре комбинаторных задао коммутирующих схем с запоминающих устро же устройств контроля.Известно устройство для перебо" ра сочетаний, содержащее последовательно включенные счетчики с коэффициентом пересчета, отличающимся, на единицу, схемы И и ИЛЙ, тригге" ры, Устройство обеспечивает подсчет числа сочетаний С при всех значени ях в , начиная с единицы И .Однако это устройство не осуществ ляет перечисления сочетаний.Наиболее близким техническим р аением к изобретению является у ройство для перебора сочетаний, содержащее .матрицу ячеек иэ и строк и п столбцов, каждая ячейка которой со держит триггер, элемент И и два эле-. мента ИЛИ, причем в каждой ячейке первый вход первого элемента И соединен с прямйм единичным, а второйвход- с инверсным единичным входа.ми триггера, выход первого элемента И подключен к первому входу пера вого элемента ИЛИ второй вход которого соединен с единичным выходом триггера, выход первого элемента ИЛИ - к первому входу первого элемента И следующей .ячейки строки, выход второго элемента ИЛИ соединен с единичным инверсным входом триггера, а первый вход второго эле" мента " ИЛИ в , с выходом второго элемента ИЛИ последующей ячейки столбца 23.Однако такое устройство имеет низкое быстродействие.Цель изобретения " повышение быстродействия устройства.Поставленная цель достигается тем, что в ячейки матрицы начиная с третьего столбца, введены первый, второй, третий и четвертый554четаний для и = 6; на фиг. 2- принципиальная схема ячейки устройствадля перебора сочетаний,УстРойство для перебора сочетанийсодержит ячейки 1-36 (Фиг. 1) , которые включены в матрицу из шестистрок и шести столбцов В состав каждой ячейки матрицы входят триггер 37,элемент И 38, элемент ИЛИ 39 (фиг.2)Вход 40 ячейки матрицы объединен содним входом элемента И 38 и, единичным входом триггера 37. Другойвход элемента И 38 подключен к единичному инверсному входу триггера37, объединен с выходом 41 ячейкии соединен с выходом элемента ИЛИ 42,один вход которого объединен с входом43 ячейки, а другой - с входом 44ячейки. Выход элемента И 38 подключенк одному входу элемента ИЛИ 39, дру-,гой вход которого связан с единичным".выходом триггера 37 и объединен с выходом 45 ячейки. Выход элемента 1ИЛИ 39 объединен с выходом 46 ячейки, выход 47 яцейки - с нулевым выходом триггера 37, нулевой .вход которого объединен с входом 48 ячейки.Вход 49 ячейки объединен с выходом"50 этой же ячейки и подключен к так"товым входам триггера 37.Выход 45 каждой ячейки матрицыподключен к управляющему входу эле"мента И 51 (фиг, 1), другой входкоторого подсоединен к вертикальной входной шине 52, а выход элемента И 51 подклдчен к горизонтальной выходной шине 53. Выходы 46,47 и 50 каждой ячейки матрицы подключены соответственно к входам 40,48 и 49 следующей в строке ячейки,причем выходы 46 и 47 последней встроке ячейки подсоединены соотвественно через линии 54 задержки ичерез элементы ИЛИ 55 и И 56 к вхо-.дам 40 и 48 первой ячейки в этой жестроке. Одни из входов элементаИЛИ 55 и инверсный вход элементаИ 56 подсоединены с шине 57 записиединицы, Выход 41 каждой ячейкиматрицы подключен к входу 43 соседнейсверху ячейки в столбце, К входу 44каждой ячейки матрицы подсоединен:выход 45 соседней снизу ячейки встолбце.В ячейки 1-21 устройства введен элемент И 58, у которого одинвход объединен с входом 59 ячейки,а другой вход - с входом 60 ячейки. 3 9227есйомогательные элементы И, а вячейки матрицы, находящиеся на пересечении 1-й строки, 1 =1,2и, и -го столбца, 1 =1,. и+1,введены третий и четвертый элемен 5ты ИЛИ, второй, третий и четвертыйэлементы И , в ячейки первого1 лстолбца матрицы введен дополнительный элемент И, причем в каждой ячейке матрицы, начиная со второй стро рки, выход третьего элемента ИЛИ со-.единен с вторым входом второгоэлемента ИЛИ предыдущей ячейки столбца и с первым входом второго элемента: И предыдущей ячейки строки, первый ивторой входы третьего элемента ИЛИсоединены соответственно с единичнымвыходом триггера и выходом второго .элемента И второй .вход, которого подключен к шине режима, первый входготретьего элемента И подсоединен кединичному выходу триггера, второйвход третьего элемента И - к второму входу третьего элемента И ячейки предыдущего столбца последующей25строки и к первой управляющей винематрицы, в ячейках первой строкиматрицы выход третьего элементаИ соединен с одним входом четвертого элемента И, другой вход которо"го подключен к второй управляющейзешине матрицы, выход четвертого эле"мента И - с первым входом четвертого элемента ИЛИ, второй вход которогосоединен с выходом четвертого элемен-;та ИЛИ Р последующей ячейки строки, в ячейках , начиная с третьего столбца матрицы, выход первогоэлемента ИЛИ и нулевой выход триггера через первый и второй вспомогательные элементы И подключены соответственно к первым входам первогоэлемента И и к нулевому входу триггера последующей ячейки строки, квходом первого , второго , третьего и четвертого вспомогательных45элементов И подключен второй входтретьего элемента И ячейки, в ячейках первого столбца матрицы первыйвход дополнительного элемента И соединен с шиной режима, второй вход 5 Вподключен к выходу первого элемента ИЛИ последней ячейки строки, выход дополнительйого элемента И через элемент ИЛИ соединен с тактовымвходом триггеров ячеек последующейстроки,На фиг. 1 изображена структурная схема устройства для перебора со-,5 922755 6Выход элемента И 58 подключен через элементц И 67 в ячейках 1-21 комбиэлемент ИЛИ 61 к выходу 62 ячейки. наторной матричной схемы.Вход 60 ячеек 7-19 подключен к шине Схема в режиме перестановок63. режима, которая подключается в работает следующим образом.каждой строке матрицы к одному входу дополнительного элемента И.64, На входы 49 ячеек 21,1916,12,другой вход дополнительного эле,1 первого столбца матрицы подаютсямента И 64 подсоединен к выходу 46 сдвинутые относительно друг другапоследней ячейки строки, а выход эле- на время Ъ последовательности иммента И 64 через элемент ИЛИ 65 10 пульсов: на вход 49 ячейки 7 послеподключен к входу 49 первой ячейки довательность с периодом Т, на входсоседней снизу строки матрицы. 49 ячейки 1 - запаздывающая отноЕдиничный выход триггера 37 ячеек под стельно предыдущей последовательключен к одному входу элемента И 66ность с периодом Т, на вход 49 ячейдругой вход которого связан с од ки 12- с периодом 2 Т, на вход 49ним входом элемента И 67. Другой ячецки 16 - с периодом 6 Т, на входвход элемента И 67 объединен с входом 49 ячейки 19 - с периодом 24 Т и на 68 ячейки.,Выход элемента И 67 и вход вход 49 ячейки Й 1 " с периодом . 69 ячейки через элемент ИЛИ 70 подсое Т. В общем случае период последодинены к выходу 71 ячейки матрицы.Вы о вательности, поступающей на вход ход 72 каждой из ячеек 2-21 подключен ячейки в 1-той строке матрица, рак входу 73 ячейки, расположенной в вен Т(1-1 )1, В первом такте на шинусоседней нижней строке и в соседнем 57 записи единицы поступает сигнал.н слева столбце. Выход 71 каждой из длительностью (и - +1 где ь ячеек 2-6, 8-11, 13-15, 17, 18 и 20 5 длительность импульса управляющей подсоединен к входу 69 соседней сле-последовательности. В этом такте в . ва ячейки . в строке. Выходы 46 и ячейки 21, 20,18,15,11,6 записыва ячеек 3-5,9-11,14,15 и 18 под- ются единицы. Таким образом, схе" ключены через вспомогательные эле" ма реализует базовую перестановку 1, менты И 74,:к входам 40 и 48 перво 11 зо 2,34,5,6, т.е. в соответствии с ячейки в этой же строке матрицы и че- заданной перестановкой, вертикаль" рез вспомогательные элементы И 75 - ные входные шины 52 через элемент к входам 40 и 48,соседней справа ячей- И 51 подключаются к горизонтальным ки в строке, к входам 73 ячеек 1-6 выходным шинам, Первая слева верти- и входам элементов И 74 и 75 подклю- кальная шина:подключается к первой35цены первые управляющие шины 76 матри- снизУ горизонтальной вторая слева цы, а к входам 68 ячеек 1-21 подсое- вертикальная - к второй снизу горидинены вторые управляющие шины 77 эонтальной шине и т.д. Во втором так 1матрицы. Выходц 72 ячеек 1,7,12,16 и ,те единица, записанная в триггер 37 21 подключены через элементы ИЛИ 78, 4 О ячейки 7-10 на вход 49 данной ячейэдемент И 79 и элемент ИЛИ 80 к ин- ки сдвигается в ячейку 22 этой же ,дикатору конца 81, к нему же через строки. Единица, записанная в триггер элементы И 82 и ИЛИ 80 подсоединенц 37 ячейки 6, под действием тактово" выходы 45 ячеек 1,8, 14,25,30 и 36. го импульса, поступающего через Вход элемента И 79 подключен к шине ячейки 1-5 на вход ячейки 6 (фиг 3)63 режима. проходит через линию 54 задержки,.элемент ИЛИ 55, и через элементыУстройство шункционирует в двух И 38 ячеек 1-4 записывается в тригрежимах : перестановок и сочетаний, гер 37 ячейки 5, на входы 43 и 44 Для настройки устройства на режим . которой поступают разрешающие нуле 5 Оперестановок на шину 63 режима по- . вце сигналы соответственно с дается нулевой сигнал, который закры" выходов 41 и 45 ячейки 11, ле-вает элементы И 64 и элементы И 58 редающиеся через элемент ИЛИ 42 на в ячейках 7-10, 12-14, 16, 17, 19. .единичный ияверсный вход триггера 37 Нулевой сигнал, поступающий на пер- . ячейки 5. Элементы И 38 ячеек 1-4 вфе управляющие шины 76 матрицы, зак- открыты единичными сигналами, поступа 55рывает элементы И 67 в ячейках 1-6, ющими на входы 40 с выходов 45 ячеа нулевой сигнал на вторых управ- . ек 21,20,18,15 в триггерах которых ляющих шинах 77 матрицы закрывает записаны едийицц.5 8цы подается единичный сигнал, который поступает через входы 68 ячеек 1- 15 на элементы И 67 и открывает, их.На шину 57 записи единицы подаетсяединичный сигнал длительностью 21+где- длительность тактирующего импульса. На входы 49 ячеек 12,7,1 подаются сдвинутые относительно другдруга на времят тактирующие импульсы. В начальный момент времени триггера 37 всех ячеек 1-36 сброшеныв ноль (цепи сброса в ноль не показаны). На единичный вход триггера37 ячейки 12 с шины 57 через элемент ИЛИ 55 и вход тактового сигнала, подаваемого на вход 49, и разрешающего нулевого сигнала, снимаемого сединичных выходов триггеров 37 ячеек 16,19,21 и поступающего через вы".ходы 41 и 45 ячейки 16 слответственно на входы 43 и 44 ячейки 12устанавливает триггер 37 ячейки 12 вединицу. Единичный сигнал на выходетриггера 37 ячейки 12 через выход45 ячейки. 12 поступает на входы 4048 ячеек 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, проходит через отк 7 92275В результате , во втором тактеустройство генерирует перестановку1,23,4,6,5. За 720=6 тактов схемагенерирует все 6 перестановок. Последней перестановке 6,5,4,3,2,1 соответствует расположение единиц втриггерах 37 ячеек 1,8,14,25,30,36,которое фиксируется с помощью элемен"тов И 82, и единичный сигнал черезэлемент ЙЛИ 80 поступает на индика в,тор 81 конца.Получение всех и, перестановокиллюстрируется примером для и 6,Базовой перестановкой, из которойпоследовательно получаются все остальные, является,1,2,3,4,5,6, гдепозиции цифр в перестановке соответствуют номерам выходных горизонтальных шин и порядке возрастания слеванаправо, а цифры, стоящие на этих 20позициях, - номерам входных вертикальных шин, подключенных к соответствующим вертикзльным входным шинам.Пример 223456 1246531234565 125364123546 125346123564 125463123645 125436 эо123654 125643124 365 1 2 5 6 3,41243561.24536 654231124563 654312 зз124635 654321Работу устройства в режиме сочетаний рассмотрим на примере полученния всех С " сочетаний, где и = ,К=3.Устройство осуществляет всевозможные 4 Овыборки трех вертикальных входных шиниз пяти и подключение их к трем выходным шинам. Для настройки устройствана режим сочетаний на вину 63 режима.подается единичный сигнал, который открывает элементы И 64, И 79, элементыИ 59 в ячейках 7-10, 12-14, 16, 17, 19.Для установки ина пятую слевапервую управляющую шину 76 матрицы .подается единичный сигнал; которыйоткрывает вспомогательные элементыИ 74 и закрывает вспомогательные элементы И 75,подключенные к выходам 46и 47 ячеек 5,10,14,кроме того,единичный сигнал через вход ячейки 5 поступает на элементы Ибб ячеек 5,10,14 иЯоткрывает их.для установки К 3 на третью сверху вторую управляющую шину 77 матриа Ь с а Ь д аде асд асе а д е Ьсд Ь с е Ьде сд е Устройство для перебора сочетаний, содержащее матрицу ячеек из и строк и и столбцов, каждая ячейка которой содержит триггер, элемент И и два элемента ИЛИ, причем в каждой ячейке первый вход первого элемента И соединен с прямым единичным, а второй входс инверсным единичным входами триггера, выход первого элемента И соединен с первым входом первого элемента ИЛИ, второй вход которого, соединен с единичным выходом триггера, выход пер" вого элемента ИЛИ соединен с первым входом первого элемента И следующей ячейки строки, выход второго элемента ИЛИ соединен с единичным инверсным входом триггера, а первый вход второго элемента ИЛИ соединен с выходом второго элемента ИЛИ последующей ячейки столбца, о т л и ч а ю. щ е е .- с я тем, что, с целью повышения быстродействия устройства, в ячейки матрицы, начиная с третьего столбца,введены. первый, второй , третий и четвертый вспомогательные элементы 9 9227 рытые элементы И 38, элементы ИЛИ 394ячеек 1 и 2 и в момент действия тактового импульса записывается в триггер 37 ячейки 3, так как на единичный инверсный вход триггера подается з разрешающий нулевой сигнал с выходов триггеров 37 ячеек 33, 28, 18;14 и 9, который закрывает также элемент И 38 ячейки 3 и прерывает распространение единичного сигнала дальше по стро" 1 о ке. Таким образом, если входным шинам 52 поставить в соответствие, буквы а, Ь, с, д, е, Г ,то реализуется сочетание а, Ь,с. Позиции в этом сочетании соответствуют номерам 5 выходных шин (снизу вверх ), а буквыобознацению входных шин, т.е. входная вертикальная шина, а с помощью элемента И 51, на который с выхода триггера 37 церез выход 45 ячейки 12 ув .подается разрешающий сигнал, подключается к третьей сверху горизонтальной выходной шине 53, входная шина Ь - к второй сверху горизонтальной вйходной шине, входная шина с- к 2 первой сверху выходной шине. С этого момента времени тактовые импульсы подаются только на ячейки 1,2,3,4,5, 6. Под действием следующего тактово" го импульса реализуется сочетание а, зв Ь, д, т.е. единица, записанная в триггера 37 ячейки 3, сдвигается в триггер 37 ячейки 4, в результате чего единичный сигнал, снимаемый с выхода триггера 37 ячейки 4, откры- зз вает элемент И 51 и осуществляет подключение соответствующей вертикаль., ной входной шины 52 к первой сверху горизонтальной выходной шине 53 под действием следующего тактового импульса единица записывается в триггер 37 ячейки 5. Таким образом, ком- ю бинаторная схема реализует сочетание а,Ь. е. Под действием последующего тактового импульса единичный сигнал с выхода 46 ячейки 5. через открытые элементы И 74 поступает далее через открытый единичный сигнал с шины 63 режима, элемент И 64, элемент ИЛИ 65 на вход 49 ячейки 8, и, следовательно, тактовые входы триггера 37 ячейки 8, сдвигая едини" цу из триггера 37 ячейки 8 в триггер 37 яцейки, 9, Единичный сигнал с выхода триггера 37 ячейки 9 через вы-, ход 45 поступает на вход 59 ячеики 8ю Я и через открытый единичным, сигналом с шины 63 режима элемент И 58, элемент ИЛИ 61 прступает на выход 62, и далее 55 10через вход 40 ячейки 2 на вход элемента И 38. Кроме того 1 единичный сиг нал с выхода триггера 37 ячейки 9 открывает элемент И 38 ячейки 3, в результате чего сигнал выхода 46 ячейки 5 через линию задержки 54, элемент ИЛИ 55, и через открытые элементы И 38,ИЛИ 39 ячеек 1-3 запишется в триггер 37 ячейки 4. Таким, образом, схема реализует перестановку а,с,д. Через С.-=10 тактов ериницы сдвинутся в триггеры 37 ячеек 14, 10,5, и единичные сигналы с выхода триггеров 37 ячеек 14,10,5 через открытые элементы И 66 ячеек 5, 10, 14 и открытые элементы И 67 , ИЛИ 70 яче" ек, 14, 13, 12 поступает через элементы ЙЛИ 78, И 79, ИЛИ 80 на индикатор конца 81. Работа схемы в режи, ме сочетаний поясняется следующим примером. формула изобретения11 9227 И, а в ячейки матрицы, находящиеся на пересечении 1-й строки, 1 щ 1,2, , р, и -го столбца, 1 1 и- +1, введены третий и четвертый элементы ИЛИ, второй, третий и четвертый элементы з И, в ячейки первого столбца матрицы введен дополнительный элемент И, причем в каждой ячейке матрицы, начиная с второй строки, выход третьего элемента ИЛИ соединен с вторые 16 входом второго элемента ИЛИ предыдущей ячейки столбца и с, первым входом второго элемента И предыдущей ячейки строки, а первый и второй входы тре" тьего элемента ИЛИ соединены соот ветственно с единичным выходом триг" гера и выходом второго элемента Р,второй вход которого подключен .к шине режима, первый вход третьего элемента И подключен к единич ному выходу триггера, второй вход третьего элемента И подключен к вто- РомУ входу третьего элемента И ячейки предыдущего столбца последующей отроки и л первой управляющей шине матри-цы, в ячейках первой строки матрицы выход третьего элемента И подключен к одному входу четвертого элемента И, другой вход которого под ключен к второй управляющей шине матрицы, выход четвертого элемента И Б 12соединен с первым"входом четвертого элемента ИЛИ, второй вход которого соединен с выходом четвертого элемен" та ИЛИ последующей ячейки строки, в ячейках,.начиная с третьего столбца матрицй, выход первого элемента ИЛИ .и нулевой выход триггера через первый и второй вспомогательные эле" менты И подключены соответственно к первым входам первого,элемента И и к нулевому входу триггера последующей ячейки строки, причем к входам первого, второго , третьего и четвертого вспомогательных элементов И подключен второй вход третьего элемента И ячейки в ячейках первого столбца матрицы первый вход дополнительного элемента И соединен с шиной режима, второй. вход подключенк выходу первого элемента ИЛИ последней ячейки строки, выход дополнительного элемента И через элемент ИЛИ соединен с тактовыми входами триггеров ячеек последующей строки.1 Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство 8 ССР Ю 3766 аб, кл. г Об Г 1 Б/2 О, 1971. 2. Патент США йф 3631397,340-172,5, 1971 (прототипИванов едакто Подписи Тираж 732рственного комитета СССРизобретений и открытийа, 3-35, Раушская наб., д 738 ВНИИПИ Госуд по делам 113035, МоскЗака илиал ППП "Патент", г. Ужгород, ул. Проектная, 1