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

Союз Советских Социалистических Республик11 И 634285 1) Дополните 2) Заявлено О ное к авт, свид-ву -75 (21) 2189318/18-24 Кл06 Р 15/3 исоединением заявкиПриоритет осударстаеииыи иомитеСоаета Миииотроа СССРоо делам нзооретеинйн открытий ь. И.78 Г. С. 1 дирамуа 2) Авторы изобретения Богатыре узинский ордена Ленина и ордена Трудового Красногонамели политехнический институт им, В, И, Ленина(71) Заявител ТВО ДЛЯ 11 ЕРЕБОРА СОЧЕТАНИЙ 4 УС это тем, что устроиство со элемент И, втогой элемент 1Изобретение относится к вычислительной технике и может быть применено, например, в вычислительных машинах, решаюших комбинаторные згдачи.Известно устройство лля перебора сочетаний, содержащее счетчики, регистры, элементы И, ИЛИ 11. Это устройство имеет сложную конструкцию.Наиболее близким техническим решением к изобретению является устройство для перебора сочетаний, содержащее первый регистр сдвига, счетчик, триггер, первый элемент задержки, первый элемент И, распределитель импульсов, первый выход которого соединен с первым входом первого сдвигаюшего регистра, второй выходс первым входом первого элемента И, второй вход которого подключен к управляюшей шине, выход элемента И подключен к второму входу сдвигаюшего регистра и через последовательно соединенные счетчик и первый элемент задержки подключен к нулевому входу триггера 12.Целью изебретения является упрощение устройства.Достигаетсядержит второй залержки, дешифратор, второй регистр сдвига, первь 1 й, второй и третий входы которого соединены соответственно с первым и вторым выходами лсшифратора и выходом первого элемептг задержки, вь 1 хол второго регистраосдвига соелпнен с первым входом первого регистра сдвига и выходом устройства. пер- вый ныхол первого регистра сдвига соединен с первым вхолом ьторого элемента И, третий вход первого регистра сдвига соединен с выходом второго элемента задержки, первый 10 выход первого регистра сдвига соединен спервым входом второго элемента И, второй вход которого подключен к нулевому выходу триггера, вы.хол элемента Й через второй элемент задержки подключен к единичному входу триггера, нулевой вхол которого подключен к первому входу дешифратора, второй вход которого подключен к второму входу второо элемента И, третий вход дешифратора полкгпочен к третьему входу первого регистра сдвига, четвертый вход дешиф.2 о ратора ООлключен к выходу первого элемента И. На чертеже представлено предлагаемоеустройство.Оно содержит распределитель импульсов 1, счетчик 2, элементы задержки 3, элемент И 4, регистры сдвига 5 и 6, дешифратор 7, триггер 8, элемент И 9.При переборе сочетаний каждое состояние образуется из предыдущего путем замены крайней справа комбинации 10 на 01 и сдвиге всех единиц, расположенных правее вплотную к этой комбинации. Г 1 ри этом для каждого в первоначальном состоянии все единицы должны располагаться в крайних слева позициях, в последнем же состоянии они переходят в крайние справа позиции. Например при гп = 6 и и = 3 устройством будут выработаны сочетания:111000 12 011 0102 110100 13 0110013 110010 14 0101104 110001 15 0101015 0100 16 О 00116 1010 0 17 0011107 10001 18 0011018 100110 19 001019 100 01 20 0001110 10001111 011100Перед началом работы для переооря всевозможных сочетаний С, состояний булевого вектора размерности гп с числом единиц п, измеряошимся от 1 до гпи =- 1, 2 гп в гп + 1 разряд распредел:теля импульсов 1 записывается единица, переписываемяя в и 1-ый разряд регистра сдвига 5. В счетчик 2, регистр сдвига 6 и триггер 8 записываются нули. Каждый раз пр поступлении входного импульса элемента И производится сдвиг, когда на один разряд в регистре сдвига 5, в двух первых разрядах которого происходит анализ кода на комбипацик 10, при нахождении триггера 8 в нулевом состоянии. В случае Отсутствия указанной комбинации и единиць в первом разряде регистра сдвига 5 на выходах дешифраторя 7 образуется единица, поступ аюшая па входы прием переноса и сдвиг регистра сдвига 6 и производяшая распростряненпв нем единицы на один разряд запись див ницы в последний разряд и перепись ранее находящейся в нем единицы в следуюший разряд). Если же в первом разряде регистра сдвига 5 находится ноль, то на выходах дешифратора 7 в этом случае имеются нули и регистр сдвига 6 остается в прежнем состоянии. Таким образом, реализуется подгон единиц, расположенных правее комбинации 10, вплотную к этой комбинации.При комбинации 10 в двух первых разрядах регистра сдвига 5 при нулевом состоянии триггера 8, сигналом с выхода элемента И 9 производится установка двух первых разрядов регистра 5 в состояние 01 и переброс триггера 8 в единичное состояние (линия задержки 3 поставлена для стабиль 5 10 15 20 25 ЗО 35 г О 4550 55 ности перходпых процессов), 1 Осле чего содержимое первого оазряда через дешифратор 7 поступает на вход прием переноса,а входной тактируюший импульс на входсдвиг регистра сдвига 6. Таким образом,содержимое регистра сдвига 5 при последуюцих тактах будет переписано в регистрсдвига 6. Причем анализ двух первых разрядов регистра сдвига 5 не происходит, таккак триггер 8 ня.одится в единичном состоянии,При каждом такте происходит увеличение содержимого счетчика 2 на единицу ипри записи в нем числа гп образование следующего Очередного) булевого вектора заканчивается. В этом случае сигналом с выхода счетчика 2 (с коэффициентом пересчета гп) реализуется выдача содержимого регистра 6 пя выходы уст)Ойсвя и на входрегистра сдвига 5, после чего сигналом свыходя элемента задержки 3 оспествг 5 тсясггвовка нли в триггрс 8 и регистрсдвия 6. В результате этого, устройство под отявливастся к получению сгедуоцего оуле.в;,го вектора. При олучении всех СсостояГ Оулевого вектора при ткуцем и в последи.,: зктор все и едини,ы располагякТся вкрайних справа нзициях (разрядах), вследвие О при сдвиге содеркимого регистра сдвига 5 комбинация 10 не судет обпаружсня и триггер 8 останется в нулевомсостоя ии. С выхода дешифратора 7 призаписи в счстчикс 2 числа гп и нулевомсостоя;и; триггера 8, поступает сигналпроизводящий ряспростране 5 ис единицы наодин ряз;яд в распреелители импульсов 1и с задерккой рсялизуемой с помощью элемента задержки 3, перепись содержимогораспределителя импльсовв регистр с вига 5 и обнуление второго регистра сдвига 6(выдача которого ии н,левом состояниир 5 гера 8 1 е производится 1. В 1 езультзтеэтого сОйствО по;ГотовлснО д,5 выаоотки всех Ссочеанпй при следуОием значении, определяемом на распределителе ими у;ьсо 1.При переборе всех , С; =- 2 и =лп)сочетаний Состояний б левого вектора) впервом разряде распределителя импульсов 1Ооразуется единица, производящая блокировку поступления в устройство входныхимпульсов с пины.В редлагаемом стройстве анализаторкомбиняцги 10 представляст пз себя копьюпктор, .я распределитель импульсовсхему распространения единицы, реализуемую и виде регистра сдвига в монофазпомкодс: бз об:уления в каждом такте или ввде регистр сдвига в парафазном коде собъединением входя последнего разряда ишипы сдьига.Предложенное устройство для переборасочетаний С;из гп элемнтов при переменно. и по сравненпо с известным характерпзутся экономией затпят обордовання.Составитель Г. 11 ирамуаТекред О. Луговая Корректор С. Шекмар Тираж 784 Подписное Редактор Е. ГонцарЗаказ 676347 1 ШР 1 ИПИ Государственного комитета Совета Министров СССР ио делам изобретений и о-крыл ий П 3035, Москва, Ж.35, 1 а; шскав иаб д. 4/5 Филиал ППП Патент, г. Ужгород, ул. Проектная, 4Устройство для перебора сочетаний, содержащее первый регистр сдвига, счетчик, триггер, первый элемент задержки, первый элемент И, распределитель импульсов, пер вый выход которого соединен с первым входом первого сдвигающего регистра, второй выход - с первым входом первого элемента И, второй вход которого подключен к управляющей шине, выход элемента И подключен к второму входу сдвигающего регистра и через последовательно соединенные счетчик и первый элемент задержки подключен к нулевому входу триггера, отличающееся тем, что, с целью упрощения устройства, оно содержит второй элемент И, второй элемент задержки, дешифратор, второй регистр сдвига, первый, второй и третий входы которого соединены соответственно с первым и вторым выходами дешифратора и выходом первого элемента задержки, выход второго регистра сдвига соединен с первым входом первого регистра сдвига и выходом устройства, первый выход первого регистра сдвига соединен с первым входом второго элемента И, третий вход первого регистра сдвига соединен с выходом второго элемента задержки, первый выход первого регистра сдвига соединен с первым входом второго элемента И, второй вход которого подключен к нулевому выходу триггера, выход элемента И через второй элемент задержки подключен к единичному входу триггера, нулевой вход которого подключен к первому входу дешифратора, второй вход которого подключен к второму входу второго элемента И, третий вход дешифратора подключен к третьему входу первого регистра сдвига, четвертый вход дешифратора подключен к выходу первого элемента И.Источники информации, принятые во внимание при экспертизе:1. Авторское свидетельство СССР М 324105, М. Кл.- Ст 06 Г 15/32, 05.12.70,2. Авторское свидетельство СССР Хе 374606, М. Кл. б 06 Г 15/32, 09.06,70.