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

1

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

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

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

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

Достигается это тем, что устройство содержит второй элемент И, второй элемент

задержки, дешифратор, второй регистр сдвига, первый, второй и третий входы которого соединены соответственно с первым и вторым выходами деилифратора и выходом первого элемента задержки, выход второго регистра сдвига соединен с первым входом первого регистра сдвига и выходом устройства, первый выход первого регистра сдвига соединен с первым входом второго элемента И, третий вход первого регистра сдвига соединен с выходом второго элемента задержки, первый

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

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

Оно содержит распределитель импу.льсов 1, счетчик 2, элементы задержки 3, э;1емент И 4, регистры сдвига 5 и 6, дешифратор 7, триггер 8, элемент И 9.

При переборе сочетаний каждое состояние образуется из предыдущего путем замены крайней справа комбинации «10 на «01 и сдвиге всех единиц, расположенных правее вплотную к этой комбинации. При этом для каждого в первоначальном состоянии единицы должны располагаться в крайних слева позициях, в последнем же состоянии они переходят в крайние справа позиции. Напри.мер при m 6, и п 3 устройством будут выработаны сочетания:

1111000 12 011010

2110100 13 011001

3110010 14 010110

4110001 15 010101

501100 16 010011

6101010 17 001110

7101001 18 001101

8100110 19 001011

9100101 20 000111

10100011

11011100

Перед началом работы для перебора всевозможных сочетаний С„, состояний булевого вектора ра.чмерности .ш с числом единиц п, измеряющимся ст 1 до m/n 1, 2... ni

разряд распределителя импульсов

в m

переписываемая в

записывается единица, сдвига 5. В счетчик т-ый разряд регистра григгер 8 записыва2, регистр сдвига 6 и юте я нули.

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

При комбинации «10 в двух первых разрядах регистра сдвига 5 при нулевом состоянии триггера 8, сигналом с выхода элемента И 9 производится установка двух первых разрядов регистра 5 в состоя1п- е «О и переброс триггера 8 в единичное состояние (линия задержки 3 поставлена для стабильности переходных процессов). После чего содержимое первого разряда через де1пифратор 7 поступает па вход «прием переноса, а входной тактирующий импульс на вход «сдвиг регистра сдвига 6. Таким образом, содержимое регистра сдвига 5 при последующих тактах будет переписапо в регистр сдвига 6. Причем анализ двух первых разрядов регистра сдвига 5 не происходит, так как триггер 8 НЕХ;ОДИТСЯ в единичном состоянии.

При каждом такте происходит увеличение содержимого счетчика 2 на единицу и при записи в нем числа гп образование следующего (очередного) булевого вектора заканчивается. В это.м случае сигналом с выхода счетчика 2 (с коэффициентом пересчета т) реализуется выдача содержимого регистра . 6 иа выходы устройства и на вход регистра сдвига 5, после чего сигналом с выхода элемента задержки 3 осуществляется хстаиовка куля в три1гере 8 и регистре сдвига 6. В результате этсяо,устройство иод1отав, ивается к получению

следующего оулеЕ5ектора. При по.чучении всех С, состояв о го

к:-1Й oy.ieFUjro вектора при теку1дем п в послед1:е,: векторе все п единицы располагаются в крайних справа позициях (разрядах), вследствие чсг:,) при сдвиге содержимого регистра сдвига 5 комбинация «10 не будет обиаружека и триггер 8 останется в нулевом СОСТОЯ1ЩИ. С выхода дешифратора 7 при записи в счетчике 2 числа m и пулевом состоянии триггера 8, поступает сигнал, производящий распространение единицы па один разряд в распределители импульсов 1 и с задержкой реализуемой с помощью элеvieHTa задержки 3, перепись содержимого распределителя и.мпульсов 1 в регистр сдвига 5 и обнуление второго регистра сдвига 6 (выдача которого при нулевом состоянии триггера 8 не производится). В результате этого устройство подготовлепо для выработки всех Сп сочетаний при следующем значении, определяемом иа распределителе импульсов 1.

При переборе всех Х„,Ст 2(п 1 ...ш) сочетаний (состояний булевого вектора) в первом разряде распределителя импульсов 1 образуется единица, производящая блокировку поступления в устройство входных

импульсов с П1ИНЫ.

в предлагаемом устройстве анализатор комбинации «10 представляет из себя копъ1ОН1 т.ор,.а распределитель импульсов 1 - схему распрострапеиия еди1П1цы, реализуемую в виде регистра сдвига в моиофазпом коде без обнуления в каждом такте или в виде регистра сдвига в парафазпом коде с объединением входа последнего разряда и тины сдвига.

Предложенное устройство для перебора сочетапий С ,„ из m элементов при перемекпом п по сравнению с известным характеризуется экономией затрат оборудования. Формула изобретения Устройство для перебора сочетаний, содержащее первый регистр сдвига, счетчик, триггер, первый элемент задержки, первый элемент И, распределитель импульсов, первый выход которого соединен с первым входом первого сдвигающего регистра, второй выход - с nepBbiiM входом первого элемента И, второй вход которого подключен к управляющей шине, выход элемента И подключен к второму входу сдвигающего регистра и через последовательно соединенные счетчик и первый элемент задержки подключен к нулевому входу триггера, отличающееся тем, что, с целью упрощения устройства, оно содержит второй элемент И, второй элемент задержки, дещифратор, второй регистр сдвига, первый, второй и третий входы которого соединены соответственно с первым и вторым выходами дешифратора и выходом первого элемента задержки, выход второго регист ра сдвига соединен с первым входом первого регистра сдвига и выходом устройства, первый выход первого регистра сдвига соединен с первым входом второго элемента И, третий вход первого регистра сдвига соединен с выходом второго элемента задержки, первый выход первого регистра сдвига соединен с первым входом второго элемента И, второй вход которого подключен к нулевому выходу триггера, выход элемента И через второй элемент задержки подключен к единичному входу триггера, нулевой вход которого подключен к первому входу дешифратора, второй вход которого подключен к второму входу второго элемента И, третий вход дешифратора подключен к третьему входу первого регистра сдвига, четвертый вход дешифратора подключен к выходу первого элемента И. Источники информации, принятые во внимание при экспертизе: 1.Авторское свидетельство СССР Л 324105, М. Кл.2 G 06 F 15/32, 05.12.70. 2.Авторское свидетельство СССР Хо 374606, М. Кл.2 G 06 F 15/32, 09.06.70.