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

ОЮЗ СОВЕТСКИХОЦИАЛИСТИЧЕСКИХЕСПУБЛИК 8094 Р 1520 ГОСУДАРСТВЕННОЕ ПАТЕНТВЕДОМСТВО СССР(ГОСПАТЕНТ СССР) ИСАНИЕ ИЗОБРЕТЕН ЛЯ ПЕРЕБОРА СОЧЕ(21) 4887416/24(54) УСТРОЙСТВО ТАН ИЙ(57) Изобретение ной технике и авт - увеличение быс тем, что устройств М счетчиков, М схе ров, М суммато 2 Мэлементов з вых импульсов, чт переборы М чисел ва в соответствии циейу= Си . 1 иМ отун и.Бурлай, А,А тельство СССРЕ 15/20, 1988.тельство СССРГ 15/20, 1986.тельство СССРР 15/20, 1986,нен с 1-м выходом устройства и вторым входом 1-й схемы сравнения 4 ь выход к-й схемысравнения 4 (1 = 1, М) соединен с вторымвходом 1-го элемента И 2), выход которогосоединен с входом 1-го элемента задержки 7 ьвыход р-го из которых (р = 1, М) соединенс первым входом р-го элемента ИЛИ 8 р,выход которого соединен с синхровходомр-го счетчика бр, установочный вход К-го из акоторых соединен с выходом М-го сумматора 9 к,первый и второй входы которого соединенысоответственно с выходом (М+1)-го регистраЗм+1 и входом 1-й схемы сравнения 4), Синхровход (М)-го счетчика бмсоединен с вы- +ходом (М)-го элемента задержки 7 М.1 ивходом (2 М)-го элемента задержки 72 м-з,второй вход р-го элемента ИЛИ 8 р соединенс выходом Я.го клемента задержки 7 о = М, );2 Ы-З), вход Т-го из которых 7 с (с = М, 2 М соединен с выходом 1-го элемента ИЛИ 81( = 2, М),Устройство для перебора сочетанботает следующим образом. В регистзанесен код единицы. В регистр323 м, а также в счетчики 61, 62,600 О ий ра р Зм+1 ы,31 м зане АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Изобретение относится к цифровой вычислительной технике и может быть использовано для решения комбинаторных задач.Цель изобретения - увеличение быстродействия.На чертеже представлена структурная схема предлагаемого устройства.Устройство содержит генератор тактовых импульсов (ГТИ) 1, М элементов И 212 м, М+ 1 регистров 31,3 м+1, М схем сравнения 414 м, триггер 5, М счетчиков 61,.,6 м, 2 м-з элемента задержки 71.72 м-з, М - 2 элементов ИЛИ 81,8 М, М - 1 сумматоров 919 М, При этом выход ГТИ 1 соединен с первым входом первого 21 элемента И, выход -го регистра 31 ( = 1,М) соединен с первым входом 1 ый 4; схемы сравнения, второй вход первого 21 элемента И соединен с выходом триггера 5, входы установки в единицу и ноль которого соединены соответственно с входом запуска устройства и выходом Я-й схемы сравнения 4 м, Первый вход)-го элемента И 2 0 = 2,М) соединен с выходом (-1)-го элемента И и счетным входом 1-го счетчика 6 выход которого соедиотносится к вычислительоматике. Цель изобретения тродействия - достигается о содержит М элементов И, м сравнения, М + 1 регистров, М - 2 элементов ИЛИ, адержки, генератор тактоо позволяет реализовать из М-элементного массис математической функсены коды чисел й, М.Й-М+1 соответственно, По сигналу "ПУСК" триггер 5, устанавливаясь в единичное состояние, открывает элемент 21 И и на счетный вход счетчика 61 начинают поступать импульсы от ГТИ 1, В тот момент, когда содержимое счетчика 61 сравняется с кодом, записанном в регистре 3, на выходе схемы сравнения 41 появится сигнал логической единицы. Этот сигнал открывает схему "2 И и последующий импульс, проходя через нее, увеличивает на единицу содержимое счетчика 62, а спустя некоторое время,равное времени задержки этого импульса в элементе 71 за держки, оно переписывается, увеличиваясь на единицу в сумматоре 91, в счетчик 61. Процесс происходит до тех пор, пока содержимое счетчика 61 не сравняется с содержимым регистра 31, а содержимое счетчика 62 не сравняется с содержимым регистра 32, т,е, с кодом, пропорциональным й. В этом случае элементы 22, 2 з И открыты и последующий импульс, проходя через них, увеличивает содержимое счетчика бз на единицу. Спустя некоторое время задержки, в счетчике 62 записывается содержимое счетчика 6 з, увеличенное на единицу, и еще спустя такое же время задержки, в счетчик 61 заносится увеличенное на единицу обновленное содержимое счетчика 62.Процесс продолжается до тех пор, пока содержимое счетчика 6 м не станет равным й-М+1, что соответствует нахождению на выходных шинах 1 М последней кодовой комбинации из Сн возможных, В этом случае сигнал высокого уровня с выхода схемы сравнения 4 м опрокидывает триггер 5 и тем самым отключает генератор 1 импульсов от остальной части схемы.Быстродействие заявляемого устройства определяется (М)-мя тактами задержек на элементах 717 м, т.е. частота счета равна бпи/М, где 1 ги - частота генератора тактовых импульсов, М - количествО перебираемых чисел в г 4 - элементном массиве. Быстродействие прототипа определяется частотой следования импульсов с выхода делителя 20, которая равна 1 рти/й. При решении широкого круга практических задач имеет место условие М М, таким образом при равных частотах ГТИ быстродействиеки, 2 Мэлементов задержки и триггер, причем выход генератора тактовых импульсов соединен с первым входом первого элемента И, второй вход которого соединен с 25 выходом триггера, входы установки в и 1 и ииОн которого соединены соответственно с входом запуска устройства и выходом М-й схемы сравнения, первый вход)-го элемента И= 2,М) соединен с выходом 0 - 1)-го 30 элемента И и счетным входом 1-го счетчика,выход которого соединен с 1-м выходом устройства и вторым входом 1-й схемы сравнения, выход К-й схемы сравнения (К = 1, М - 1) соединен с вторым входом 1-го элемента И, 35 выходкоторого соединен с входом К-гоэлемента задержки, выход р-го из которых (р = 1, М - 2) соединен с первым входом р-го элемента ИЛИ, выход которого соединен с синхровходом р-го счетчика, установочный 40 вход К-го из которых соединен с выходомК-го сумматора, первый и второй входы которого соединены, соответственно, с выходом (М+1)-го регистра и выходом )-й схемы сравнения, синхровход(М - 1)-го счетчика со единен с выходом (М)-го элемента задержки и входом М-го элементов задержки, второй вход р-го элемента ИЛИ соединен с выходом о-то клемента задержки (В = Зх 1, 2 М-З), вход т-го из которых (с = М, 2 М) 50 соединен с выходом 1-го элемента ИЛИ ( = 2, М). 5 10 15 20 заявляемого устройства в М/М раз выше, чем у прототипа.Таким образом достигнута цель изобретения - увеличение быстродействия устройства, что способствует более эффективному функционированию сложных цифровых комплексов, а также выгодно отличает заявляемое устройство от прототипа,Формула изобретения Устройство для перебора сочетаний, содержащее генератор тактовых импульсов, М элементов И (М - количество перебираемых чисел в й-элементном массиве), М+1 регистров, М схем сравнения, три счетчика, три элемента задержки и Мэлементов ИЛИ, причем выход -го регистра ( = 1,М) соединен с первым входом 1-й схемы сравнения, о т л и ч а ю щ е е с я тем, что, с целью увеличения быстродействия, оно содержит Мсумматоров, с четвертого по М-й счетчи1809444 Составитель И, Бу Техред М.Моргента орректор О. Ше дакто оизводственно-издательский комбинат "Патейт", г, Ужгород, ул.Гагарина, 10 каэ 1286 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5