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

 

Изобретение относится к вычислительной технике и автоматике. Цель изобретения - увеличение быстродействия - достигается тем, что устройство содержит М элементов И, М счетчиков, М схем сравнения, М + 1 регистров , М 1 сумматоров, М-2 элементов ИЛИ, 2М-3 элементов задержки, генератор тактовых импульсов, что позволяет реализовать переборы М чисел из N-злемвнтного массива в соответствии с математической функцией у CNM. 1 ил.

союз советских

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

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

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) Р.

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4887416/24 (22) 23,10.90 (46) 15.04,93, Бюл, N 14 (72) Ю.Г.Булычев, И.B.Áóðëàé, А,А.Коротун и

С,А. Погон ы шев (56) Авторское свидетельство СССР

Nе 1520535, кл. 6 06 F 15/20, 1988.

Авторское свидетельство СССР № 1401474, кл. G 06 F 15/20, 1986.

Авторское свидетельство СССР

¹ 1363232, кл, G 06 F 15/20, 1986, Изобретение относится к цифровой вычислительной технике и может быть использовано для решения комбинаторных задач.

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

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

Устройство содержит генератор тактовых импульсов (ГТИ) 1, М элементов И

21,,,2м, М + 1 регистров 31„„,3M+1, М схем сравнения 41,...,4м, триггер 5, M счетчиков

61,...,6м, 2м-з элемента задержки 71...„72M-з, М вЂ” 2 элементов ИЛИ 81...,,8M-2, М вЂ” 1 сумматоров 91,...,9м-1, При этом выход ГТИ1 соединен с первым входом первого 21 элемента

И, выход i-ro регистра 3; (i = 1,M) соединен с первым входом !-й 4; схемы сравнения, второй вход первого 21 элемента И соединен с выходом триггера 5, входы установки в единицу и ноль которого соединены соответственно с входом запуска устройства и выходом M-й схемы сравнения 4м, Первый вход j-го элемента И 2j (j = 2,М) соединен с выходом (j-1)-го элемента И и счетным входом i-го счетчика 6;, выход которого соеди„„5U„„ l809444 А1 (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАН ИЙ (57) Изобретение относится к вычислительной технике и автоматике. Цель изобретения — увеличение быстродействия — достигается тем, что устройство содержит M элементов И, M счетчиков, М схем сравнения, М + 1 регистров, M- 1 сумматоров, М вЂ” 2 элементов ИЛИ, 2М-3 элементов задержки, генератор тактовых импульсов, что позволяет реализовать переборы M чисел из N-элементного массива в соответствии с математической функцией у = С1ч . 1 ил. м нен с i-м выходом устройства и вторым входом i-й схемы сравнения 4ь выход k-й схемы сравнения 4 (k = 1, М-1) соединен с вторым входом j-го элемента И 2j, выход которого соединен с входом k-го элемента задержки 7у, выход р-го из которых (р = 1, М-2) соединен с первым входом р-го элемента ИЛИ 8р, выход которого соединен с синхровходом р-го счетчика бр, установочный вход k-ro из д которых соединен с выходом k-ro сумматора 9к, . (р первый и второй входы которого соединены соответственно с выходом (M+1)-го регистра

Зм+1 и входом j-й схемы сравнения 4j, Синхровход (M-1)-го счетчика бм-1 соединен с вы- + ходом (M-1)-го элемента задержки 7М-1 и входом (2М-3)-го элемента задержки 7aM a, второй вход р-го элемента ИЛИ 8р соединен с выходом S-го клемента задержки 7 S = M, );»

2Ы-З), вход t-го из которых 71 (t = М, 2М-4 соединен с выходом i-го элемента ИЛИ 8! (! = 2, M-2), Устройство для перебора сочетаний работает следующим образом. В регистр Зм+1 занесен код единицы. В регистры 31, 32,...,3м, а также в счетчики 61, бр,...,бМ занеI

1009444 сены коды чисел N, N-1,....N-M+1 соответственно, По сигналу "ПУСК" триггер 5, устанавливаясь в единичное состояние, открывает элемент 21 И и на счетный вход счетчика 61 начинают поступать импульсы от ГТИ1. В тот момент, когда содержимое счетчика 61 сравняется с кодом, записанном в регистре 3, на выходе схемы сравнения

41 появится сигнал логической единицы.

Этот сигнал открывает схему "2 И и последующий импульс, проходя через нее, увеличивает на единицу содержимое счетчика 62, а спустя некоторое время, равное времени задержки этого импульса в элементе 71 за держки, оно переписывается, увеличиваясь на единицу в сумматоре 9>, в счетчик 61.

Процесс происходит до тех пор, пока содержимое счетчика 61 не сравняется с содержимым регистра 31, а содержимое счетчика áz не сравняется с содержимым регистра 3z, т,е. с кодом, пропорциональным N-1. В этом случае элементы 2z, 2з И открыты и последующий импульс, проходя через них, увеличивает содержимое счетчика бз на единицу.

Спустя некоторое время задержки, в счетчике 62 записывается содержимое счетчика бз, увеличенное на единицу, и еще спустя такое же время задержки, в счетчик 61 заносится увеличенное на единицу обновленное содержимое счетчика 62.

Процесс продолжается до тех пор, пока содержимое счетчика 6М не станет равным

N-M+1, что соответствует нахождению на выходных шинах 1 .„,M последней кодовой комбинации из Сн возможных, В этом случае сигнал высокого уровня с выхода схемы сравнения 4м опрокидывает триггер 5 и тем самым отключает генератор 1 импульсов от остальной части схемы.

Быстродействие заявляемого устройства определяется (M-2)-мя тактами задержек на элементах 71,...,7M 1, т.е. частота счета равна 1ртр/М, где fr>< — частота генератора тактовых импульсов, М вЂ” количествО перебираемых чисел в N — элементном массиве.

Быстродействие прототипа определяется частотой следования импульсов с выхода делителя 20, которая равна fry/N При решении широкого круга практических задач имеет место условие M «N, таким образом при равных частотах ГТИ быстродействие ки, 2М-6 элементов задержки и триггер, причем выход генератора тактовых импульсов соединен с первым входом первого элемента И, второй вход которого соединен с выходом триггера, входы установки в и1и и иОн которого соединены соответственно с входом запуска устройства и выходом M-й схемы соавнения, первый вход)-го элемента

И O = 2,М) соединен с выходом g — 1)-го

30 элемента И и счетным входом I-ro счетчика, выход которого соединен с I-м выходом устройства и вторым входом i-й схемы сравнения, выход К-й схемы сравнения (К = 1, М вЂ” 1) соединен с вторым входом I-го элемента И, 35 выход которого соединен с входом К-го элемента задержки, выход р-го из которых (р = 1, M — 2) соединен с первым входом р-го элемента ИЛИ, выход которого соединен с синхровходом р-ro счетчика, установочный

40 вход К-го из которых соединен с выходом

К-го сумматора, первый и второй входы которого соединены, соответственно, с выходом (М+1)-ro регистра и выходом j-й схемы сравнения, синхровход(М вЂ” 1)-го счетчика со45 единен с выходом (M-1)-ro элемента задержки и входом М-го элементов задержки, второй вход р-го элемента ИЛИ соединен с выходом о-то епемента задержки (В = M, 2М-З), вход t-го из которых (с = М, 2М-2)

50 соединен с выходом I ãî элемента ИЛИ (! = 2, М2).

20 заявляемого устройства в N/Ì раз выше, чем у прототипа.

Таким образом достигнута цель изобретения — увеличение быстродействия устройства, что способствует более эффективному функционированию сложных цифровых комплексов, а также выгодно отличает заявляемое устройство от прототипа, Формула изобретения

Устройство для перебора сочетаний, содержащее генератор тактовых импульcos, M элементов И (М вЂ” количество перебираемых чисел в N-элементном массиве), М+1 регистров, М схем сравнения, три счетчика, три элемента задержки и М-2 элементов ИЛИ, причем выход i-го регистра (i = 1,M) соединен с первым входом i-й схемы сравнения, о т л и ч а ю щ е е с я тем, что, с целью увеличения быстродействия, оно содержит

М-1 сумматоров, с четвертого по М-й счетчи1809444

Составитель И, Бурлай

Техред М.Моргентал Корректор G. Шекмар

Редактор

Производственно-издательский комбинат "Патейт", г, Ужгород, ул.Гагарина, 101

Заказ 1286 Тираж Подписное

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

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