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

113

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

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

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

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

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

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

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

1-е

,.., + 4..,

где

А,:, м

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

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

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

( п.

N; (n-N)

10.

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

Получим последовательность всех сочетаний, используя указанный алгоритм, для (00100)

А, ,

Л(4),,

2

тогда

Л 00111 + 00100 01011,

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

5

0

5

0

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

Устройство работает следующим образом.

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

требует обработки. Сформированное таким образом двоичное число 2-1 подается на входы элементов ИЛИ 5, на другие входы которых подано данное сочетание с прямых выходов регистра 1, и производится суммирование числа 2 -1 с . . Например, если AJ 0110100, 2 -1 0000011, то в результате на выходе элементов ИЛИ 3 имеем А,-., +2 -1 0110111.

Причем в любом случае при суммировании числа 2 -1 не возникает переноса в старшие разряды, так как число 2 -1 имеет едини1Д 1 в L подряд стоящих разрядах, начиная с младшего. Это обстоятельство позволяет вести суммирование чисел 2--1 и А- не в сумматоре, а на элементе ИЛИ, позто- му время суммирования существенно уменьшается.

Получение числа 2 -1 происходит

одновременно с формированием суммы r)L

0

5

i

0

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

С помощью второго логического блока 3 и блока 6 элементов И обеспечивается подключение к входам двигателя 7 кода (L+K) младших разрядов. Действительно, как только на выходах регистра 1 появится очередное сочетание Aj , то единичный потенциал на выходе L+K-ro элемента И 4, который заблокирует через соответствующие элементы ИЛИ 5 элементы И 6, начиная с L+K-ro. Поэтому выбираются только первые L+K разрядов регистра 1, которые через элементы И 6 подключаются к входам сдвигателя 7 кода. Например, при А,. OIOJJSS вход

к . L - сдвигателя 7 кода подключаются младшие разряды. Для того, чтобы информацию, поступившую с выходов элементов И 6, преобразовать в двоичный

код числа 2

К-1

ее необходимо сдви

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

заднему фронту. С появлением А- на

выходе регистра начинается новый цикл работы устройства. Сигналом о переборе сочетаний является появление N единиц подряд в старших разрядах сочетания. В этом случае на выходе элементов 4 И нулевые потенциалы. При этом формируется признак конца работы устройства.

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

50

Время,необходимое для получения одного сочетания,складывается из задержки55 сигналов на элементах и равно (.IS+nJ «tj, где п - число разрядов в коде; tj - время задержки на вентиле (элементе И/ИЛИ).

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

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

lira

.

Зп+9 п+15

3.

5

0

5

5

0

-

0

5

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

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

. . ., 2 (п-2) - номер разряда входа; т у номер разряда выхода, группу элемен- тов И, сдвигатель кода и сумматор, информационный выход которого соединен с информационным входом регистра, прямые выходы с второго по д-й разрядов которого соединены с первыми входами с первого по (п-1)-й элемент И группы соответственно, выходы с первого по {п-2)-и элементов И которой соединены с информационными входами с второго по (п-1)-й разряд сдвигателя кодов, информационный вход первого разряда которого соединен с прямым выходом первого разряда регистра, инверсные выходы с первого по (п-2)-и разрядов которого соединены с четными входами с второго по 2(п-2)-й разрядов соответственно первого логического блока, выход (п- -1)-го элемента И группы является выходом признака конца работы устройства, отличающееся тем, что, с -целью повьш1ения быстродействия, оно содержит второй логический блок, реализующий функцию У|) ... V Xj, формирователь г импульса, выход которого соединен с входом синхронизации регистра, прямые выходы с первого по (п-2)-й разрядов которого соединены с нечетными входами с первого по 2(п-2)-1-й разрядов соответственно первого и второго логических блоков, инверсные выходы с второго по (п-1)-й разрядов регистра соединены с чётными входами с второго по 2(п-2)-й разрядов соответственно второго логического блока, т-е выходы которого соединены с инверсными входами т-х эле513057026

ментов И группы соответственно, вы-разряда первого слагаемого которого

ход (п-2)-го разряда второго логичес-,соединен с выходом п-го разряда регикого блока соединен с (п-1)-м инверс-стра, выход сдвнгателя кода соединен

ным входом элемента И группы, выходс входом второго слагаемого сумматош-го разряда первого логического бло- ,ра, выход признака окончания суммика соединен с входом т-го Первогорования которого соединен с входом

слагаемого сумматора, вход (т+1)-го ,формирователя импульса.

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