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

(50 4 С 06 Р 15/20 ИСАНИЕ ИЗОБРЕТЕНИЯ ескии ьченк ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ АВТОРСКОМУ СВИДЕТЕЛЬСТВ(54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРАТАНИЙ 57) Изобретение относится к вычисли ельной технике и может быть исполь,ЯО, 130570 зовано для построения систем автоматизированного проектирования радиоэлектронной и электронно-вычислительной аппаратуры. Цель изобретения -повышение быстродействия устройства.Поставленная цель достигается тем,что в устройство, содержащее регистр1, первый логический блок 2, группу6 элементов И, сдвигатель 7 кода исумматор 8, введены второй логическийблок 3 и формирователь 9 импульса ссоответствующими связями. 1 ил.1305702 2А=10110 а,=00001 а, =00011 д =00001 д -00010 А =11001А =11010А=1 1100,п,Сп 1 ( 1,1) Ь =00010 А =01101 А 4=01110 А =10011 А =10101 а,. =00001 Л =00101 5=00010 Изобретение относится к вычислительной технике и может быть использовано для построения систем автоматизированного проектирования радиоэлектронной и электронно-вычислительной аппаратуры.Цель изобретенйя - повышение быстродействия устройства.На чертеже представлена функциональная схема устройства.Устройство содержит регистр 1, первый и второй 2 и 3 логические блоки, построенные на элементах ИЛИ 4, 4 И и 5, 5, группу 6 элементов И, сдвигатель 7 кода, сумматор 8 и формирователь 9 импульса.Принцип работы устройства основан на следующем алгоритме.Исходным является сочетание, в котором И единиц записаны подряд в младших разрядах (правых). Очередное х-е сочетание вычисляется по формуле где А - предыдущее сочетание;где Ь - число подряд стоящих нулей,начиная с младшего разряда,до первой единицы в (-1)-мсочетании;К - число подряд стоящих единицпосле Ь нулей до первого очередного нуля.Рассмотрим на примере перебор сочетаний Сп для случая п=5, И=З. Число таких сочетаний определяется по формуле Исходным для данного случая является сочетание А=00111.Получим последовательность всех сочетаний, используя указанный алгоритм, для А Ь=О, К=З и д =(4) = =(00100) тогда А,=А+ й=00111 + 00100 = 01011. Аналогичным образом получим всеостальные сочетания: Таким образом, перебор сочетанийпродолжается до тех пор, пока всеединицы не появятся в старших разря 10 дах подряд.Устройство работает следующим образом,Исходное сочетание, содержащее Мединиц в младших разрядах, перед началом работы записывается в регистр 1,Как только это сочетание появляетсяна выходе регистра 1, начинается фор- кмирование чисел 2 -1 и 2 . Рассмотрим некоторое записанное в регистр 120 промежуточное сочетание. При формировании числа 2 -1 на инверсных выходах регистра 1 появляются единичныепотенциалы в тех разрядах, которымсоответствуют содержащие нули разрядыв сочетании, элементы И 4 выбираюттолько следующие подряд со сторонымладших разрядов единичные потенциалы инверсных выходов регистра 1, если тактовые имеются, Причем числоэлементов И 4 равно п-З, так как наибольшее число подряд стоящих нулей всочетании будет при И=1, а последнимсочетанием, требующим считывания нулей, является 0100, поэтому следу 35 ющее, последнее, сочетание уже нетребует обработки, Сформированное таким образом двоичное число 2 -1 подается на входы элементов ИЛИ 5, надругие входы которых подано данное40 сочетание с прямых выходов регистра 1,и производится суммирование числа2 -1 с А . Например, если А;,=0110100, 2 - 1= 0000011, то в результате на выходе элементов ИЛИ 3 имеем45 А; +2 -1= 0110111,Причем в любом случае при суммировании числа 2 -1 не возникает переноса в старшие разряды, так как число 2 -1 имеет единицы в Ь подряд стоящих разрядах, начиная с младшего. Это обстоятельство позволяет вести суммирование чисел 2 -1 и А. не в сумматоре, а на элементе ИЛИ, поэтому время суммирования существенно уменьшается,кПолучение числа 2 - 1 происходит одновременно с формированием суммы 2 -1 + Аследующим образом.1305702 Зп+9и+151 ю = 3. С помощью второго логическогоблока 3 и блока 6 элементов И обеспечивается подключение к входам двигателя 7 кода (Ь+К) младших разрядов. Действительно, как только на выходах регистра 1 появится очередное сочетание А; , то единичный потенциал на выходе Ь+К-го элемента И 4, который заблокирует через соответствующие элементы ИЛИ 5 элементы И 6, начиная 10 с Ь+К-го. Поэтому выбираются только первые Ь+К разрядов регистра 1, которые через элементы И 6 подключаются к входам сдвигателя 7 кода. Например, при А., =0101100 на вход 15ксдвигателя 7 кода подключаются младшие Ь+К=4 разряды. Для того, чтобы информацию, поступившую с выходов элементов И 6, преобразовать в двоичный код числа 2 ", ее необходимо сдвинуть на Ь позиций в сторону младших разрядов, а затем заблокировать (К).разрядов, начиная с младшего, С выхода сдвигателя 7 кода двоичный код числа 2 " поступает на входы п-разрядного асинхронного сумматора 8, на другие входы которого подано число (2 -1) + А; . В результате сумми- рования формируется новое сочетание, а на сигнальном выходе сумматора появляется единичный потенциал, который через формирователь 9 импульсов в виде прямоугольного импульса поступает на синхронизирующий вход регистра 1. Сочетание А; по этому сигналу записывается в регистр 1, причем оно появляется на выходе регистра 1 после окончания импульса, т.е. по его заднему фронту. С появлением А, на выходе регистра начинается новый цикл работы устройства. Сигналом о переборе сочетаний является появление И единиц подряд в старщих разрядах сочетания. В этом случае на выходе всех 4 элементов 4 И нулевые потенциалы. При этом формируется признак конца работы устройства.Считывание всех сочетаний производится с прямых выходов регистра 1 по единичному синхронизирующему импульсу на выходе 10. Время, необходимое для получения одного сочетания, складывается из задержки 55 сигналов на элементах и равно (15+и)где и - число разрядов в коде;- время задержки на вентиле (элементе И/ИЛИ). 4Время формирования одного сочетания в известном устройстве составляет (Зп+9) С Таким образом, предельный выигрыш по быстродействию составляет вели- чину Формула изобретения Устройство для перебора сочетаний, содержащее и-разрядный регистр, первый логический блок, реализующий функцию У=(Х ХХ )Ч Х , где У , Х, - булевы переменные: 1 с=2, 4, ,2(п) - номер разряда входа ш= --1 с2 номер разряда выхода, группу элемен-тов И, сдвигатель кода и сумматор, информационный выход которого соединен с информационным входом регистра, прямые выходы с второго по ц-й разрядов которого соединены с первыми входами с первого по (и)-й элемент И группы соответственно, выходы с первого по (и)-й элементов И которой соединены с информационными входами с второго по (и)-й разряд сдвигателя кодов, информационный вход первого разряда которого соединен с прямым выходом первого разряда регистра, инверсные выходы с первого по (и)-й разрядов которого соединены с четными входами с второго по 2(п)-й разрядов соответственно первого логического блока, выход (и - 1)-го элемента И группы является выходом признака конца работы устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, оно содержит второй логический блок, реализующий функцию У =Х Х, чп УХ Х, нЪ ХХ и формировательимпульса, выход которого соединен с входом синхронизации регистра, прямые выходы с первого по (п)-й разрядов которого соединены с нечетными входами с первого по 2(п)-1-й разрядов соответственно первого и второго логических блоков, инверсные выходы с второго по (и)-й разрядов регистра соединены с четными входами с второго по 2(п)-й разрядов соответственно второго логического блока, ш-е выходы которого соединены с инверсными входами ш-х эле 5 1305702 6ментов И группы соответственно, вы- разряда первого слагаемого которого ход (и)-го разряда второго логичес- соединен с выходом и-го разряда реги- кого блока соединен с (и)-м инверс- стра, выход сдвигателя кода соединен ным входом элемента И группы, выхоД с входом второго слагаемого сумматов-го разряда первого логического бло ра, выход признака окончания суммика соединен с входом ш-го первого рования которого соединен с входом слагаемого сумматора, вход (щ+1)-го , формирователя импульса.1Составитель Н, МатвеевРедактор Н. Гунько Техред А.Кравчук КорректорЛ. ПатайЗаказ 1453/47 Тираж 673 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д. 4/5Производственно-полиграфическое предприятие, г, Ужгород, ул, Проектная, 4