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

 

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

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

Республик (»i 634285 (61) Дополнительное к авт, свид-ву— (22) Заявлено 05,11.75 (21) 2189318/18-24, с присоединением заявки № (23) Приоритет (43) Опубликовано 25.11.78.Бюллетень № 43 (45) Дата опубликования описания ЕЗ. И .78 (51) М. Кл

С 06 F 15/32

Государстаеииый комитет

Соаета Миииотроа СССР

w делам нзооретеинй н открытий (53) УДК 681.327 (088.8) (72} Авторы изобретения

Г. С. Ыирамуа и В. А. Богатырев

Грузинский ордена Ленина и ордена Трудового Красного

Знамени политехнический институт им. В. И. Ленина (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ

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

Известно устройство для перебора сочетаний, содержащее счетчики, регистры, элементы И, ИЛИ (1). Это устройство имеет сложную конструкцию.

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

Целью изобретения является упро:цение устроиства.

Достигается это тем, что устройство содержит второй элемент И, второй элемент задержки, дешифратор, второй регистр сдвиг", первь»1, второй и третий входы которого соединены соответственно с первым и вторым выходами дсшифратора и выходом первого элемептг задержки, выход второго регистра

5 сдвига соединен с первым входом первого регистра сдвига и выходом устройства. пер- вый выход первого регистра сдвига соединен с первым в .одо;1 ьторого элемента И, третий вход первого регистра сдвига соединен с выходом второго элемента задержки, первый

1О выход первого регистра сдвига соединен с первым входом второго элемента И, второй вход которого подключен к нулевому выходу триггера, вы.ход элемента Й через второй элемент задержки подключен к единичному входу триггера, нулевой вход которого под15 ключен к первому входу дешифратора, второй вход которого подключен к второму входу второ о элемента И, третий вход дешифратора подкгпочен к —.ретье.му входу первого регистра сдвига, четвертый вход дешиф2р ратора подключен к выходу первого элемента И.

На чертеже представлено предлагаемое устройство.

634285

Оно содержит распределитель импульсов

1, счетчик 2, элементы задержки 3, элемент

И 4, регистры сдвига 5 и 6, дешифратор 7, триггер 8, элемент И 9.

При переборе сочетаний каждое состояние образуется из предыдущего путем замены крайней справа комбинации «10» на

«01» и сдвиге всех единиц, расположенных правее вплотную к этой комбинации. Г1ри этом для каждого в первоначальном состоянии все единицы должны располагаться в крайних слева позициях, в последнем же состоянии они переходят в крайние справа позиции. Например при m = 6 и и = 3 устройством будут выработаны сочетания: ! 111000 12 011 010

2 110100 13 011001

3 110010 14 010110

4 110001 15 010101

5 0!100 16 010011

6 1010!0 17 001110

7 101001 18 001101

8 100110 19 001011

9 1001 01 20 00011!

10 100011

11 011100

Перед началом работы для перебора всевозможных сочетаний C„, состояний оулевого вектора размерности.m с числом единиц п, пзмеря1ошимся от 1 до mtï =- 1, 2... m в m + 1 разряд распредел-1теля импульсов 1 записывается единица, переписываемяя в

m-ый разряд регистра сдвига 5. В счетчик

2, регистр сдвига 6 и триггер 8 записываются нули.

Каждый раз пр11 поступлении входногo импульса элемента И производится сдвиг, когда на один разряд в регистре сдвига 5, в двух первых разрядах которого происходит анализ кода на комбипац1по «10», при нахождении триггера 8 в нулевом состоянии. В случае отсутствия указанной комбинации и единпць. в первом разряде регистра сдвига 5 на выхода; дешифраторя 7 образуется единица, поступающая па входы

«прием переноса» и «сдвиг>. регистра сдвига 6 и производящая распространснп(в нем единицы на один разряд (запись сди— ницы в последний разряд H перепись ранее находящейся в нем единицы в следующий разряд). Если же в первом разряде регистра сдвига 5 находится ноль, то на выходах дешифратора 7 в этом случае имеются нули и регистр сдвига 6 остается в прежнем состоянии. Таким образом, реализуется подгон единиц, расположенных правее комбинации

«10», вплотную к этой комбинации.

При комбинации «10» в двух первых разрядах регистра сдвига 5 при нулевом состоянии триггера 8, сигналом с выхода элемента

И 9 производится установка двух первых разрядов регистра 5 в состояние «01» и переброс триггера 8 в единичное состояние (линия задержки 3 поставлена для стабиль5

2»

i10

55 ности переходных процессов). 11осле чего содержимое первого разряда через дешифратор 7 поступает на вход «прием переноса», а входной тактирующий импульс на вход

«сдвиг» регистра сдвига 6. Таким образом, содержимое регистра сдвига 5 при последую1цих тактах будет переписано в регистр сдвига 6. Причем анализ двух первых разрядов регистра сдвига 5 не происходит, так как триггер 8 íяходится в единичном состоянии.

При каждом такте происходит увеличение содержимого счетчика 2 на единицу и при записи в нем числа m образование следующего (очередного) булевого вектора заканчивается. В этом случае сигналом с выхода счетчика 2 (c коэффициентом пересчета m) ргали".óåòcÿ выдача содержимого регистра 6 пя выходы устройства и на вход регистра сдвига 5, после чего сигнал(гм с выходя элеме 1та задержки 3 ос ществлястся установка к ли в триггсрс 8 H регистре сдви1Я 6. В результате этого,у(тройство подI oTHâ, .èâHñòcH к получению следу1ошего оулеи в;,го вектора. При 1олучении всех С„состоя : .!t оулсвого вектора при тскущсм и в пос,".Сдсс.с зскторс всс и едини1,:ы располагя1атся в крайних с права позициях (разрядах), вследсгви чс. (. Бри сдвиге содержимого регистра сдвига 5 комбинация «10» не будет обпаружсня и триггер 8 останется в нулевом состоя11ии. С выхода дешифратора 7 при записи Б счстчикс 2 числа ITl и нулевом состояt!H!I триггера 8, поступает сигнал„производящий ряспростране1.ис единицы на один разряд в распре елители импу.1ьсов 1 и с задср>ккой реализуемой с помощью элемента задержки 3, перепись содержимого распредели геля имп1льсов 1 Б рсГHcTp c IBHга 5 и обнуление второго регистра сдвига 6 (РЫДЯЧЯ КОТОРОГО ПРИ Il,, ICIIO. I! COCTOBIIHH григгеря 8 не производится). В результате этоГО 1 с1 Ройс БО Го;!Готов 10110 д.l и Бы Раооти ки все:(С,. сочс(HHliH (1ри c;IpJvtoittc .." значении, определя(мом на рàct;ðåäåëHòå(!å имlt> (IüCOH 1.

При переборе всех у, C,„=-? H = ...m) очстаний (состояний б) левого в:ктора) в п«рвом разряде pact:редслителя импульсов 1

Ооразуется единица, производящая блокировку поступления в устройство входных импульсов с пины.

В !!редлагae:lion устройстве анализатор комбин Il!HH «10» представляст пз сеоя копь1 0! I I < т О ) l, и, > Я с и Р с;1 с, 1! I т е, 1 ь и . 1 I I У, 1 I (. о Б сыму распространения единицы, реализуемую и вп Iå регистра сдвига Б монофазпом кодс: без об:1уления в каждом такте или в

Hit;;e регистр» сдвига в парафазном коде с объединением Бходг последнего разряда и ши ы сдвига.

Предложенное устройство для перебора сочетаний С;„из m элементов при переменном и и<) сравнени10 с пзвсстным харяктерпзустся экономией затрат оборудования.