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

 

Изобретение относится-к вычислительной технике и может быть использовано для построения систем автоматизированного проектирования радиоэлектронной и электронно-вычислительной аппаратуры. Цель изобретения - повышение быстродействия устройства. Поставленная цель достигается тем, что в устройство, содержащее регистр 1, первый логический блок 2, группу 6 элементов И, сдвигатель 7 кода и сумматор 8, введены второй логический блок 3 и формирователь 9 импульса с соответствующими связями. 1 ил. СЛ

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (sg 4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

H АBTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3908538/24-24 (22) 11.06.85 (46) 23.04.87. Бюл. № 15 (71) Таганрогский радиотехнический институт им. В.Д. Калмыкова (72) В.M. Глушань и M.В. Рыбальченко (53) 681.325.22(088.8) (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ (57) Изобретение относится к вычислительной технике и может быть исполь„„SU„„1305702 A1 зовано для построения систем автоматизированного проектирования радиоэлектронной и электронно-вычислительной аппаратуры. Цель изобретения— повышение быстродействия устройства.

Поставленная цель достигается тем, что в устройство, содержащее регистр

1, первый логический блок 2, группу

6 элементов И, сдвигатель 7 кода и сумматор 8, введены второй логический блок 3 и формирователь 9 импульса с соответствующими связями. 1 ил.

1305702

А„=10110

d6=OO001 д,=00011

d8=O00O1 д -00010

А =11001

A =11010

А„=11100. й, =00010

А, =01101

А4 =01110

5 1001 1

А =10101 а,.-00001

54 00101

А =00010

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

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

На чертеже представлена функциональная схема устройства.

Устройство содержит регистр 1, первый и второй 2 и 3 логические блоки, построенные на элементах ИЛИ

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

Принцип работы устройства основан на следующем алгоритме.

Исходным является сочетание, в котором N единиц записаны подряд в младших разрядах (правых). Очередное

i-e сочетание вычисляется по формуле где A„ — предыдущее сочетание; где L — число подряд стоящих нулей, начиная с младшего разряда, до первой единицы в (i-1)-м сочетании;

К вЂ” число подряд стоящих единиц после L нулей до первого очередного нуля.

Рассмотрим на примере перебор сочетаний Сд для случая п=5, N=Ç. ЧисN ло таких сочетаний определяется по формуле

Исходным для данного случая является сочетание А 00111.

Получим последовательность всех сочетаний, используя указанный алгоритм, для A„ L=O, K=3 и д =(4)„ =

=(00100),, тогда

A =A + 4„=00111 + 00100 = 01011.

Аналогичным образом получим все остальные сочетания:

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

Устройство работает следующим образом, Исходное сочетание, содержащее N единиц в младших разрядах, перед началом работы записывается в регистр 1, Как только это сочетание появляется на выходе регистра 1, начинается форКмирование чисел 2 — 1 и 2 . Рассмот— рим некоторое записанное в регистр 1 промежуточное сочетание. При формировании числа 2 -1 на инверсных выхоL дах регистра 1 появляются единичные потенциалы в тех разрядах, которым соответствуют содержащие нули разряды в сочетании, элементы И 4 выбирают только следующие подряд со стороны младших разрядов единичные потенциалы инверсных выходов регистра 1, если тактовые имеются. Причем число элементов И 4 равно п-3, так как наибольшее число подряд стоящих нулей в сочетании будет при N=1, а последним сочетанием, требующим считывания нулей, является 010...0, поэтому следу35 ющее, последнее, сочетание уже не требует обработки, Сформированное таким образом двоичное число 2 -1 поL дается на входы элементов ИЛИ 5, на другие входы которых подано данное

40 сочетание с прямых выходов регистра 1, и производится суммирование числа

2 -1 с А„. . H p ep, e H À;, L

=01 101 00, 2 — 1 = 000001 1, то в ре з ультате на выходе. элементов ИЛИ 3 имеем

45 А. +2 1 01 I0111

Причем в любом случае при сумми1. ровании числа 2 -1 не возникает переноса в старшие разряды, так как число

2 -1 имеет единицы в . подряд стоящих разрядах, начиная с младшего.

Это обстоятельство позволяет вести суммирование чисел 2 †1 А. не в

1 сумматоре, а на элементе ИЛИ, поэтому время суммирования существенно уменьшается. к

Получение числа 2 — 1 происходит одновременно с формированием суммы

2 -1 + А„ „ следующим образом.

1305702

Зп+9

n+15

lim = 3.

С помощью второго логического блока 3 и блока 6 элементов И обеспечивается подключение к входам двигателя 7 кода (L+K) младших разрядов.

Действительно, как только на выходах регистра 1 появится очередное сочетание А;„, то единичный потенциал на выходе L+K-го элемента И 4, который заблокирует через соответствующие элементы ИЛИ 5 элементы И 6, начиная 10 с L+K-ro. Поэтому выбираются только первые L+K разрядов регистра 1, которые через элементы И 6 подключаются к входам сдвигателя 7 кода. На— пример, при А., =0101100 на вход 15 к сдвигателя 7 кода подключаются младшие L+K=4 разряды. Для того, чтобы информацию, поступившую с выходов элементов И 6, преобразовать в двоичный код числа 2 ", ее необходимо сдвинуть на L позиций в сторону младших разрядов, а затем заблокировать (К-1)-разрядов, начиная с младшего.

С выхода сдвигателя 7 кода двоичный код числа 2 " поступает на входы п-разрядного асинхронного сумматора 8, на другие входы которого подано число (2 — 1) + А;„. В результате сумми- рования формируется новое сочетание, а на сигнальном выходе сумматора появляется единичный потенциал, который через формирователь 9 импульсов в виде прямоугольного импульса поступает на синхронизирующий вход регистра 1. Сочетание А; по этому сигналу записывается в регистр 1, причем оно появляется на выходе регистра 1 после окончания импульса, т.е. по его заднему фронту. С появлением А, на выходе регистра начинается новый цикл работы устройства. Сигналом о переборе сочетаний является появление N единиц подряд в старщих разрядах сочетания. В этом случае на выходе всех4 элементов 4 И нулевые потенциалы.

При этом формируется признак конца работы устройства.

Считывание всех сочетаний производится с прямых выходов регистра 1 по единичному синхронизирующему импульсу на выходе 10.

Время, необходимое для получения одного сочетания, складывается из задержки сигналов на элементах и равно (15+n)» где n — число разрядов в коде; — время задержки на вентиле (элементе И/ИЛИ).

Время формирования одного сочетания в известном устройстве составляет (Зп+9) t,.

Таким образом, предельный выигрыш по быстродействию составляет величину

Формула изобретения

Устройство для перебора сочетаний, содержащее и-разрядный регистр, первый логический блок, реализующий функцию У =(Х .X ... Х ) V Х „, где

У, X k=2, 4, ...,2(n-2) — номер разряда входа m= ——

2 номер разряда выхода, группу элементов И, сдвигатель кода и сумматор, информационный выход которого соединен с информационным входом регистра, прямые выходы с второго по и-й разрядов которого соединены с первыми входами с первого по (и-1)-й элемент

И группы соответственно, выходы с первого по (n-2)-й элементов И которой соединены с информационными входами с второго по (n — 1)-й разряд сдвигателя кодов, информационный вход первого разряда которого соединен с прямым выходом первого разряда регистра, инверсные выходы с первого по (n-2)-й разрядов которого соединены с четными входами с второго по

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

m s 2

УХ Х,1Н ... V X> „Х и формирователь импульса, выход которого соединен с входом синхронизации регистра, прямые выходы с первого по (п-2)-й разрядов которого соединены с нечетными входами с первого по 2(п-2)-1-й разрядов соответственно первого и второго логических блоков, инверсные выходы с второго по (n- 1)-й разрядов регистра соединены с четными входами с второго по 2(п-2)-й разрядов соответственно второго логического блока, m-e выходы которого соединены с инверсными входами m-х эле5 1305702 6 ментов И группы соответственно, вы- разряда первого слагаемого которого ход (и-2)-го разряда второго логичес- соединен с выходом и-го разряда регикого блока соединен с (n-1)-м инверс- стра, выход сдвигателя кода соединен ным входом элемента И группы, выход с входом второго слагаемого сумматоm-ro разряда первого логического бло- 5 ра, выход признака окончания суммика соединен с входом ш-го первого рования которого соединен с входом слагаемого сумматора, вход (m+1)-ro формирователя импульса.

Составитель Н. Матвеев

j Редактор Н. Гунько Техред А.Кравчук Корректор Л. Патай

Заказ 1453/47 Тираж 673 Подписное

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

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

Производственно-полиграфическое предприятие, r. Ужгород, ул, Проектная, 4