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

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

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

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

Устройство содержит генератор тактовых импульсов (ГТИ) 1, М элементов И 21,..,2м, М + 1 регистров 31,...,3м-н, М схем сравнения 41,-...,4м. триггер 5, М счетчиков 6i,...,6w, 2м-з элемента задержки 7i,...,72M-3, М-2 элементов ИЛИ 81,...,8м-2, М-1 сумматоров 9ь...,9м-1. При этом выход ГТИ1 соединен с первым входом первого 2i элемента И, выход i-ro регистра 3i (i 1 ,М) соединен с первым входом 1-й А схемы сравнения, второй вход первого 2т элемента И соединен с выходом триггера 5, входы установки в единицу и ноль которого соединены соответственно с входом запуска устройства и выходом M-й схемы сравненид 4м. Первый вход J-ro элемента И 2j (j 2,M) соединен с выходом (j-1)-ro элемента И и счетным входом i-ro счетчика 6j, выход которого соединен с i-м выходом устройства и вторым входом i-й схемы сравнения 4i, выход k-й схемы сравнения 4k (к 1, М-1) соединен с вторым входом j-ro элемента И 2j, выход которого соединен с входом k-ro элеме нта задержки 7k. выход р-го из которых (р 1, М-2) соединен с первым входом р-го элемента ИЛИ 8р, выход которого соединен с синхровходом р-го счетчика 6р, установочный вход k-ro из которых соединен с выходом k-ro сумматора 9k, первый и второй входы которого соединены соответственно с выходом (М+1)-го регистра Зм+1 и входом j-й схемы сравнения 4j. Синх- ровход (М-1)-го счетчика 6м-1 соединен с выходом (М-1)-го элемента задержки 7м-1 и входом (2М-3)-го элемента задержки 72М-3, второй вход р-го элемента ИЛИ 8Р соединен с выходом S-ro элемента задержки 7§(Зл-М. 2М-3), вход t-ro из которых 7t (t М 2М-4) соединен с выходом 1-го элемента ИЛИ 8| (1 2, М-2).

Устройство для перебора сочетаний работает следующим образом. В регистр Зм+1 занесен код единицы. В регистры ,31, 32,....Зм. а также в счетчики 6i, 62,...,6м зане00

о ю

Ьь

сены коды чисел N, N-1.....N-M+1 соответственно. По сигналу ПУСК триггер 5, устанавливаясь в единичное состояние, открывает элемент 2i И и на счетный вход счетчика 6i начинают поступать импульсы от ГТИ1. В тот момент, когда содержимое счетчика 6i сравняется с кодом, записанном в регистре 3j, на выходе схемы сравнения 4i появится сигнал логической единицы. Этот сигнал открывает схему 22 И и последующий импульс, проходя через нее, увеличивает на единицу содержимое счетчика 62, а спустя некоторое время, равное времени задержки этого импульса в элементе 7i задержки, оно переписывается, увеличиваясь на единицу в сумматоре 9i, в счетчик 6i. Процесс происходит до тех пор, пока содержимое счетчика 6т не сравняется с содержимым регистра 3i, а содержимое счетчика 62 не сравняется с содержимым регистра 32, т.е. с кодом, пропорциональным N-1. В этом случае элементы 22, 2з И открыты и последующий импульс, проходя через них, увеличивает содержимое счетчика 6з на единицу. Спустя некоторое время задержки, в счетчике 6а записывается содержимое счетчика 6з, увеличенное на единицу, и еще спустя такое же время задержки, в счетчик 6i заносится увеличенное на единицу обновленное содержимое счетчика 62.

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

Быстродействие заявляемого устройства определяется (М-2)-мя тактами задержек на элементах 71,...,7м-1, т.е. частота счета равна тгти/М, где fr™ - частота генератора тактовых импульсов, М - количество перебираемых чисел в N - элементном массиве. Быстродействие прототипа определяется частотой следования импульсов с выхода делителя 20, которая равна tY™/N. При решении широкого круга практических задач имеет место условие М « N, таким образом при равных частотах ГТИ быстродействие

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

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

Устройство для перебора сочетаний, содержащее генератор тактовых импульсов, М элементов И (М - количество перебираемых чисел в N-элементном массиве), М+1 регистров, М схем сравнения, три счетчика, три

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

М-1 сумматоров, с четвертого по M-й счетчики, 2М-6 элементов задержки и триггер, причем выход генератора тактовых импульсов соединен с первым входом первого элемента И, второй вход которого соединен с

выходом триггера, входы установки в 1 и О которого соединены соответственно с входом запуска устройства и выходом М-й схемы сравнения, первый вход J-rp элемента И 0 2,М) соединен с выходом (j - 1)-го

элемента И и счетным входом 1-го счетчика, выход которого соединен с i-м выходом устройства и вторым входом i-й схемы сравнения, выход К-й схемы сравнения (К 1, М - 1) соединен с вторым входом 1-го элемента И,

выход которого соединен с входом К-го элемента задержки, выход р-го из которых (р 1, М-2) соединен с первым входом р-го элемента ИЛИ, выход которого соединен с синхровходом р-го счетчика, установочный

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

соедиден с выходом 1-го элемента ИЛИ (I 2, М-2).

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