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

 

ОП ИСАНИЕ

Союз Советсник

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

Рвснублмн

,922

К АЮТОРСКОМУ СВИДИТВЛЬСТВУ (61) Дополнительйое к авт. саид-ву(Sl)M. Кл. (22) Заявлено 05. 07. 76 (21) 2382011/18-24 с присоединением заявки М(23) Приоритет " а 06 Г 1У20

9еуаараааяяыа камятат

CCCP ае далам язабратаяяй н етарытяя

Опубликоваso 23.04.82; Бюллетень М 15 (53) УДК 681. .327(688.8 ) Дата опубликования описания 23,04,82

МЪ

О. В. Викторов, Ю. С. Вйлинский, Л. Ф. Кар чун = и А. И. Романкевич . y;:i -Киевский ордена Ленина политехнический инс&итуп ; им. 50-летия Великой Октябрьской социалистйч революции (72) Авторы изобретения (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ

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

Известно устройство для перебора сочетаний, содержащее последовательно включенные счетчики с коэф1О фициентом пересчета, отличающимся, на единицу, схемы И и ИЛЙ, триггеры. Устройство обеспечивает подсчет числа сочетаний С при всех знамении ях m, начиная с единицы 03 .

Однако это устройство не осуществляет перечисления сочетаний.

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

ИЛИ - к первому входу первого элемента И следующей .ячейки строки, выход второго элемента ИЛИ соединен с единичным инверсным входом триггера, а первый вход второго элемента " ИЛИ вЂ . с выходом второго элемента ИЛИ последующей ячейки столбца PJ.

Однако такое устройство имеет низкое быстродействие.

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

Поставленная цель достигается тем, что в ячейки матрицы, начиная с третьего столбца, введены первый, второй, третий и четвертый

4 четаний для и = 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.

1 . Выход 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,..., и, и )-го столбца, j =1,...,n-i+1, введены третий и четвертый элемен5 ты ИЛИ, второй, третий и четвертый элементы И, в ячейки первого

< 1л столбца матрицы введен дополнительный элемент И, причем в каждой ячейке матрицы, начиная со второй строки, выход третьего элемента ИЛИ со-. единен с вторым входом второго элемента ИЛИ предыдущей ячейки столбца и с первым входом второго элемента

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

25 строки и к первой управляющей вине матрицы, в ячейках первой строки матрицы выход третьего элемента

И соединен с одним входом четвер того элемента И, другой вход которого подключен к второй управляющей зе шине матрицы, выход четвертого эле" мента И - с первым входом четверто:го элемента ИЛИ, второй вход которого

l соединен с выходом четвертого элемен-; та ИЛИ последующей ячейки строки, в ячейках, начиная с третьего столбца матрицы, выход первого элемента ИЛИ и нулевой выход триггера через первый и второй вспомогательные элементы И подключены соответственно к первым входам первого элемента И и к нулевому входу триггера последующей ячейки строки, к входом первого, второго, третьего и четвертого вспомогательных

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

На фиг. 1 изображена структурная схема устройства для перебора сп5 922755 G

Выход элемента И 58 подключен через элемента И 67 в ячейках 1-21 комбиэлемент ИЛИ 6l к выходу 62 ячейки. наторной матричной схемы.

Вход 60 ячеек 7-19 подключен к шине Схема в режиме перестановок

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

1 ду дополнительного элемента И.64, На входы 49 ячеек 21,19>16,12, другой вход дополнительного эле- 7,1 первого столбца матрицы подаются мента И 64 подсоединен к выходу 46 сдвинутые относительно друг друга последней ячейки строк и, а выход эле- на времЯ Ъ послеДовательности иммента И 64 через элемент ИЛИ 65 1о пУльсов: на вход "9 Ячеики 7 послеподключен к входу 49 первой ячейки довательность с периодом Т, на вход соседней снизу строки матрицы. 49 ячейки 1 - запаздывающая отноЕдиничный выход триггера 37 ячеек под- с тельно пРедыдУщей последоватеЛьключен к одному входу элемента И 66, ность с периодом Т, на вход 49 ячейдругой вход которого связан с од- 15 ки 12- с пеРиодом 2Т, на вход 49 ним входом элемента И 67. Другой ячейки 16 - с периодом 6Т, на вход вход элемента И 67 объединен с входом 49 ячейки 19 - c периодом 24Т и на

68 ячейки.,Выход элемента И 67 и вход вход 49 ячейки 21 " с периодом . 69 ячейки через элемент ИЛИ 70 подсое- 120Т. В общем случае период последодинены к выходу 71 ячейки матрицы.Вы- о вательности, поступающей на вход ход 72 каждой из ячеек 2-21 подключен ячейки в 1-той строке матрица, рак входу 73 ячейки, расположенной в вен T(I-1 )I, В первом такте на шину соседней нижней строке и в соседнем 57 записи единицы поступает сигнал . JiJ слева столбце. Выход 71 каждой из длительностью (и -!) +1„ где L. ячеек 2-6, 8-11, 13-15, 17,IS и 20 д, длительность импульса управляющей подсоединен к входу 69 соседней сле- последовательности. В этом такте в . ва ячейки . в строке. Выходы 46 и ячейки 21, 20, 18, 15, 11,6 записыва47 ячеек 3-5,9-11, 14, 15 и 18 под- ются единицы. Таким образом, схеключены через вспомогательные эле" ма реализует базовую перестановку 1, менты И 74,:к входам 40 и 48 перво11 зо 2,3,4,5,6, т.е. в соответствии с ячейки в этой же строке матрицы и че- заданной пеРестановкой, веРтикальрез вспомогательные элементы Ig 75 - ные входные шины 52 чеРез элемент к входам 40 и 48,соседней справа ячей- И 51 подключаются к горизонтальным ки в строке. K входам 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 подключен к шине 45 ячейки 1-5 на вход ячейки 6 (Фиг.3)

63 режима. проходит через линию 54 задержки,. элемент ИЛИ 55, и через элементы .

Устройство функционирует в двух И 38 ячеек 1-4 записывается в тригрежимах : перестановок и сочетаний. гер 37 ячейки 5, на входы 43 и 44

Для настройки устройства на Режим которой поступают разрешающие нуле50 перестановок на шину 63 режима по- вые сигналы соответственно с дается нулевой сигнал, который закры- выходов 41 и 45 ячейки 11, пе- вает элементы И 64 и элементы И 58 редающиеся через элемент ИЛИ 42 на в ячейках 7-10, 12-14, 16, 17, 19. .единичный ияверсный вход триггера 37

Нулевой сигнал, поступающий íà nep- - ячейки 5. Элементы И 38 ячеек 1-4 вуе управляющие шины 76 матрицы, зак- открыты единичными сигналами, поступа.«55 рывает элементы И 67 в ячейках 1-6, ющими на входы 40 с выходов 45 ячеа нулевой сигнал на вторых управ- ек 21,20,18,15 в триггерах которых ляющих шинах 77 матрицы закрывает записаны едийицы.

5 8 цы подается единичный сигнал, который поступает через входы 68 ячеек 115 на элементы И 67 и открывает, их.

На шину 57 записи единицы подается единичный сигнал длительностью 2Y+g<, где - длительность тактирующего импульса. На входы 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 поступает на входы 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, проходит через отк7 92275

B результате, во втором такте устройство генерирует перестановку

1,2j3 4,6,5. За 720=6I тактов схема генерирует все 6 перестановок. Ilocледней перестановке 6,5,4,3,2,1 соответствует расположение единиц в триггерах 37 ячеек 1,8,14,25,30,36, которое фиксируется с помощью элемен-. тов И 82, и единичный сигнал через элемент ЙЛИ 80 поступает на индика,тор 81 конца.

Получение всех n.I перестановок иллюстрируется примером для и 6, Базовой перестановкой, из которой последовательно получаются все ос- I$ тальные, является,1,2,3,4,5,6, где позиции цифр в перестановке соответствуют номерам выходных горизонтальных шин и порядке возрастания слева направо, а цифры, стоящие на этих 2О позициях, - номерам входных вертикальных шин, подключенных к соответствующим вертикзльным входным шинам.

Пример 25

123456 124653

1234565 125364

123546 125346

I23564 1 25463

123645 12.5436 зо

1.23654 125643

124365 12563,4

124356

1.24536 654231

124563 654312 $$

124635 654321

Работу устройства в режиме сочетаний рассмотрим на примере полученния всех С " сочетаний, где n =,K=3.

Устройство осуществляет всевозможные 4О . выборки трех вертикальных входных шин .из пяти и подключение их к трем выходным шинам. Для настройки устройства на режим сочетаний на шину 63 режима. подается единичный сигнал, который открывает элементы И 64, И 79, элементы

И 59 в ячейках 7-10, 12-14, l6,17,19.

Для установки и *5 на пятую слева первую управляющую шину 76 матрицы . подается единичный сигнал; который открывает вспомогательные элементы

И 74 и закрывает вспомогательные элементы И 75,подключенные к выходам 46 и 47 ячеек 5,10,14,кроме того,единичный сигнал через вход ячейки 5 посту° пает на элементы И 66 ячеек 5,10,14 и

S$ открывает их. для установки К 3 на третью сверху вторую управляющую шину 77 матриа Ь с

abd а d e ас4 а с е а d e

Ьс4

Ь с е

Ь.d e с d e

Устройство для перебора сочетаний, содержащее матрицу ячеек из и строк и и столбцов,,каждая ячейка которой содержит триггер, элемент И и два элемента ИЛИ, причем в каждой ячейке первый вход первого элемента И соединен с прямым единичным, а второй входс инверсным единичным входами триггера, выход первого элемента И соединен с первым входом первого элемента

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

9 9227 рытые элементы И 38, элементы ИЛИ 39

4 ячеек 1 и 2 и в момент действия тактового импульса записывается в триггер 37 ячейки 3, так как на единичный инверсный вход триггера подается 5 разрешающий нулевой сигнал с выходов триггеров 37 ячеек 33, 28, 18,14 и 9, который закрывает также элемент И 38 ячейки 3 и прерывает распространение единичного сигнала дальше по стро- 1о ке. Таким образом, если входным шинам 52 поставить в соответствие, буквы а, Ь, с, d, е,;,f,то реализуется сочетание а, Ь,с. Позиции в этом сочетании соответствуют номерам !5 выходных шин (снизу вверх }, а буквыобозначению входных шин, т.е. входная вертикальная шина, а t помощью элемента И 51, на который с выхода триггера 37 через выход 45 ячейки 12 2в .подается разрешающий сигнал, подключается к третьей сверху горизонтальной выходной шине 53, входная шина

Ь - к второй сверху горизонтальной вйходной шине, входная шина с - к 25 первой сверху выходной шине. С этого момента времени тактовые импульсы подаются только на ячейки 1,2,3,4,5, 6. Под действием следующего тактово" го импульса реализуется сочетание а, 5В

Ь, d, т.е. единица, записанная в триггера 37 ячейки 3, сдвигается в триггер 37 ячейки 4, в результате чего единичный сигнал, снимаемый с выхода триггера 37 ячейки 4, откры- 35 вает элемент И 51 и осуществляет подключение соответствующей вертикаль-, ной входной шины 52 к первой сверху горизонтальной выходной шине 53, под действием следующего тактового импульса единица записывается в триггер 37 ячейки 5. Таким образом, комбинаторная схема реализует сочетание а,Ь. е. Под действием последующего тактового импульса единичный 45 сигнал с выхода 46 ячейки 5 через открытые элементы И 74 поступает далее через открытый единичный сигнал с шины 63 режима, элемент И 64, элемент ИЛИ 65 на вход 49 ячейк14 8, и, следовательно, тактовые входы триггера 37 ячейки 8, сдвигая единицу из триггера 37 ячейки 8 в триггер

37 ячейки, 9, Единичный сигнал с выхода триггера 37 ячейки 9 через вы-, ход 45 поступает на вход 59 ячеики 8

v 55 и через открытый единичным .сигналом с шины 63 режима элемент И 58, элемент

ИЛИ 61 прступает на выход 62, и далее

55 10 через вход 40 ячейки 2 на вход элемента И 38. Кроме того1 единичный сиг нал с выхода триггера 37 ячейки 9 открывает элемент И 38 ячейки 3, в результате чего сигнал выхода 46 ячейки 5 через линию задержки 54, элемент ИЛИ 55, и через открытые элементы И 38,ИЛИ 39 ячеек 1-3 запишется в триггер 37 ячейки 4. Таким, образом, схема реализует перестановку а,с,d. Через С-=10 тактов единицы сдвинутся в триггеры 37 ячеек 14, 10,5, и единичные сигналы с выхода триггеров 37 ячеек 14,10,5 через открытые элементы И 66 ячеек 5, 10, 14 и открытые элементы И 67, ИЛИ 70 яче" ек, 14, 13, 12 поступает через элементы ИЛИ 78, И 79, ИЛИ 80 на индикатор конца 81. Работа схемы в режи, ме сочетаний поясняется следующим примером. формула изобретения 11 9227

И, а в ячейки матрицы, находящиеся на пересечении t-й строки, l 1,2,... р, и j-го столбца, j 1,..., n- 1+1, введены третий и четвертый элементы ИЛИ, второй, третий и четвертый элементы

И, в ячейки первого столбца матрицы введен дополнительный элемент И, причем в каждой ячейке матрицы, начиная с второй строки, выход третьего элемента ИЛИ соединен с вторые входом второго элемента ИЛИ предыдущей ячейки столбца и с. первым входом второго элемента И предыдущей ячейки строки, а первый и второй входы тре" тьего элемента ИЛИ соединены соответственно с единичным выходом триггера и выходом второго элемента Р,второй вход которого подключен .к шине режима, первый вход третьего элемента И подключен к единич- 20 ному выходу триггера, второй вход третьего элемента И подключен к втоРомУ входу третьего элемента И ячейки предыдущего столбца последующей отроки и л первой управляющей шине матри- цы, в ячейках первой строки матрицы выход третьего элемента И подключен к одному входу четвертого элемента И, другой вход которого под ключен к второй управляющей шине матрицы, выход четвертого элемента И

55 соединен с первым"входом четвертого элемента ИЛИ, второй вход которого соединен с выходом четвертого элемента ИЛИ последующей ячейки строки, в ячейках,-начиная с третьего столбца матрицй, выход первого элемента

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

ИЛИ последней ячейки строки, выход дополнительного элемента И через элемент ИЛИ соединен с тактовыми входами триггеров ячеек последующей строки.

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

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

Ю 376606, кл. 9 06 F 15/20, 1971.

2. Патент США и 3631397,340-172, 5, 1971 (прототип

922755

Составитель Л. Карачун

Техаед З.фанта Корректор Н, Ивыдкая

Редактор В ° Иванова

Подлис ное

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

Заказ 3738 Тираж 732

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

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