Устройство для перебора сочетаний
Изобретение относится к вычислительной технике. Устройство предназначено для перебрра всех сочетаний из п элементов перебора по k и может быть использовано для построения специализированных вычислительных устройств, предназначенных для автоматизированного решения зддач конструирования радиоэлектронной аппаратуры . Цель изобретения - повышение быстродействия. Устройство содержит группу счетных одноступенчатых Т-триггеров 1-6, Группу элементов ИЛИ 7т10, группу одноступенчатых 0-триггеров 11-16, группу одноступенчатых D-триггеров 17-22, группу элементов И 23-27, группу элементов И 28-33, группу элементов И 34-38, группу элементов ИЛИ 39-42, группу элементов РАВНОЗНАЧНОСТЬ 43-47, группу мажоритарных элементов 48-5I, элемент задержки 52, ключ 53, элемент задержки 54, элемент ИЛИ 55, группу элементов И 56-61, элемент И 62, вход тактовых импульсов 63, вход запуска 64, группу информационных выходов 65-70, выход 71 призрака окончания перебора. 1 ил. (Л
СОЮЗ СОВЕТСНИХ
СОЦИА ЛИСТИЧЕСНИ Х
РЕСПУБЛИН
ОПИСАНИЕ ИЗОБРЕТЕНИЯ К А8ТОРСНОМУ С8ИДЕТЕЛЬСТВУ ГОСУДАРСТ8ЕННЫЙ НОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (2l) 4144317/24-24 (22) 10,11,86 (46) 23.05.88. Бюл. В 19 (71) Таганрогский радиотехнический институт им.В.Д.Калмыкова (72) В.М.Глушань и А.В.Пришибской (53) 681.323 (088.8) (56) Авторское свидетельство СССР В 903891, кл. G 06 F 15/31, 1980. Авторское свидетельство СССР В 1262520, кл. G 06 F 15/20, 1985. (54) УСТРОЙСТВО ЦЛЯ ПЕРЕБОРА СОЧЕТАНИЙ (57) Изобретение относится к вычисР лительной технике . Устройство предназначено для перебрра всех сочетаний иэ п элементов перебора по и может быть использовано для построения специализированных вычислительных устройств, предназначенных „„SU„„1397934 А 1 для автоматизированного решения задач конструирования радиоэлектронной аппаратуры. Цель изобретения — повышение быстродействия. Устройство содержит группу счетных одноступенчатых Т-триггеров 1-6, группу элементов ИЛИ 7 10, группу одноступенчатых 0-триггеров 11-16, группу одноступенчатых 0-триггеров 17-22, группу элементов И 23-27, группу элементов И 28-33, группу элементов И 34-38, группу элементов ИЛИ 39-42, группу элементов РАВНОЗНАЧНОСТЬ 43-47, группу мажоритарных элементов 48-51, элемент задержки 52, ключ 53, элемент задержки 54, элемент ИЛИ 55, группу элементов И 56-61, элемент И 62, вход тактовых импульсов 63, вход запуска 64, группу информационных выходов 65-70, выход 71 признака окончания перебора. 1 ил. 1397934 1О геров 1-6, группу элементов ИЛИ 7-10, 15 группы триггеров 11-16 и 17-22, груп- пу мажоритарных элементов 48-51, эле- 20 Перед началом работы триггеры 1-6, 30 С выхода ключа 53 тактовый импульс 40 также поступает на элемент 54 задерж45 55 Изобретение относится к вычислительной технике и может быть использовано для построения специализированных вычислительных устройств, предназначенных, например, для автоматизированного решения задач конструирования радиоэлектронной .и вы-, числительной аппаратуры. Целью изобретения является повышение быстродействия. На чертеже приведена структурная схема устройства для n = 6. Устройство содеряс т группу тригпы элементов И 23-27, 28-33 и 34-38, группу элементов ИЛИ 39-42, группу элементов РАВНОЗНАЧНОСТЬ 43-47, групмент 52 задержки, ключ 53, элемент 54 задержки, элемент ИЛИ,55, группу элементов И 56-61, элемент И 62, тактовый вход 63, вход 64 запуска, группу информационных выходов 65-70 и выход 71 признака окончания работы устройства. Устройство работает следующим образом. 11-16 и 17-22 по входам R устанавливаются в нулевое состояние, а затем пп входам 52 в триггеры 1 — 3 записываются единицы. При нажатии кнопки "Пуск" с входа 64 единичный потенциал поступает через элемент ИЛИ 55 на прямые динамические входы синхронизации триггеров ll-16 и )7-22, разрешая перезапись единиц в триггеры 11 — 13 и 17 — 19 и через элемент 52 задержки на вход ключа. Длительность задержки элемента 52 определяется временем процесса перезаписи информации из первого регистра триггеров во второй и третий. Положительный порог, пройдя элемент 52 задержки и поступив на ключ 53, открывает его, способствуя прохождению тактовых импульсов с входа 63 через ключ на входы всех элементов И 23-27. Нулевой потенциал на инверсном выходе триггера 17 закрывает все последующие элементы И 24-27, поэтому импульс появляется только на выходе элемента И 23. Пройдя по цепи элементов ИЛИ 39-42, импульс поступает на входы всех элементов РАВНОЗНАЧНОСТЬ 43-47. Так как только триггеры 1l†- 13 находятся в единичном состоянии, импульсы появляются на выходах элементов РАВНОЗНАЧНОСТЬ 43-45, оставляя открытыми элементы И 29-33 и 34-38, а нулевой потенциал с выхода элемента РАВНОЗНАЧНОСТЬ 46 закрывает все последующие элементы И 32-33 и 37-38. С выходов элементов И 28 — 30 импульсы поступают на счетные прямые динамические входы соответствующих триггеров 1 — 3, перебрасывая их в нулевое состояние, и на входы всех мажоритарных элементов 48-51. Так как единичный потенциал присутствует на инверсных выходах триггеров 14-16, а элементы И 37 и 38 закрыты нулевым потенциалом с выхода элемента РАВНОЗНАЧНОСТЬ 46, то открытым остается только элемент И 36, пройдя который, импульс проходит через элемент ИЛИ IO, поступает на вход установки единичного состояния триггера 4 и перебрасывает этот триг" гер в единичное состояние ° На этом заканчивается процесс формирования промежуточного состояния первого регистра и начинается процесс восстановления единиц. Так как на каждый пятивходовой комбинационный мажоритарный элемент 48-51 поступает только три импульса,то импульсы появляются только на выходах мажоритарных элементов 50 и 51. Пройдя через соответствующие элементы ИЛИ 7 и 8, эти импульсы поступают на входы Si установки единичного состояния соответствующих триггеров 1 и 2 и переводят их в единичное состояние. ки, который задерживает импульс на время, равное времени формирования очередного сочетания. Пройдя элемент 54 задержки, импульс поступает на входы всех элементов И 56-61, открывая эти элементы, тем самым разрешая считывание очередной комбинации с информационных выходов 65-70. Одновременно с этим тактовый импульс, пройдя элемент ИЛИ 55 и поступив на входы синхронизации второго и третьего регистров, разрешает перезапись очередной полученной комбинации иэ первого операционного регистра во второй и третий регистры памяти. После формирования последнего сочетания 000111 в первом регистре формируется его промежуточное состояние 000000, при котором открывается эле1397934 Устройство для перебора сочетаний, динен с выходом перв содержащее первую и вторую группы четвертой группы, пе триггеров, четыре группы элементов вого элемента ИЛИ вт И, первую группу элементов ИЛИ, два рым входом первого эл элемента задержки, элемент ИЛИ и ключ группы и первым вход причем вход запуска устройства сое- мента РАВНОЗНАЧНОСТЬ динен с первым входом элемента ИЛИ и элементов РАВНОЗНАЧН входом первого элемента задержки, динены с соответст Э выход которого соединен с пер- ми с второго по и вым входом ключа, выход которо- первой группы и с го соединен с входом второго (n-1)-й элементов И элемента задержки, выход которо- пы, последний вход ro соединен с вторым входом элемента И второй группы с ИПИ, выход которого соединен с входа- ходом m-го элемента ИПИ ми синхронизации триггеров первой пы, первым входом (m группы, прямой выход i-ro триггера та ИЛИ второй группы которой (i=1, и и - количество эле- q-го элемента РАВНОЗНА ментов перебора) соединен с первым вторые входы элементо входом i-го элемента И первой группы, группы соединены с пр инверсный выход j ro триггера (j = с первого по (и-1)-й 2,п) первой группы соединен с первым вой группы, вторые вх входом j""го элемента И второй груп- ИЛИ второй группы сое пы, выход первого элемента И первой ми элементов И с втор „группы соединен со счетным входом четвертой группы, пер первого триггера второй группы, пря- ментов И четвертой гр мые выходы которого соединены с пер- с выходом ключа, остал выми входами элементов И третьей 1-го элемента И четве группы, вторые входы которых соеди- (1 = 1 n - 1) соедин иены с выходом второго эаемента за- выходом 1-ro триггера держки, выходы элементов И третьей и с инверсными выхода группы соединены с информационными первого по 1-й третье с информационными выходами уст- мые выходы триггеров ройства, тактовый вход которого соединены с информаци соединен с вторым входом ключа, триггеров третьей r выход к-ro элемента И второй группы синхронизации которь (=2>п - 2) соединен с первым входом с выходом элемента к-го элемента ИЛИ первой групгы> о т- ный выход и-го триг л и ч а ю щ е е с я тем, что, с группы и прямой вь целью повышения быстродействия, уст- гера третьей группь ройство содержит вторую группу эле- входами элемента И, ментов ИЛИ, третью группу триггеров, соединен с выходом пр элемент И, группу элементов РАВНО- работы устройства, вых ЗНАЧНОСТЬ и группу мажоритарных И с первого по (и- 1)элементов,, причем информационный вход соединены с входами м 1-го триггера первой группы соединен элементов группы, вхо с прямым выходом i-ro триггера вто- та ИЛИ первой группы рой группы, единичный вход m-го ны с выходами мажорит триггера второй группы (m=1>п-2) сое- с первого по (m-(S-1) ВНИИПИ Заказ 2601/49 Тираж 704 Подписное Произв.-полигр. пр-тие, r. Ужгород, ул. Проектная, 4 мент И 62 и на выходе 71 появляется единичный потенциал окончания процесса перебора сочетаний. Этим и завершается процесс перебора всех сочетаний из п=6 по m=3. Формула изобретения 5 I0 55 динен с выходом m-го элемента ИЛИ первой группы, единичный вход р-го триггера второй группы (p m+1,n) соединен с выходом р-го элемента И второй группы, второй вход и-го элемента И первой группы (q 2, и " 1) соединен с выходом ключа, второй вход первого элемента И первой группы соеого элемента И рвым входом перорой группы, втоемента И второй ом первого элегруппы, выходы ОСТЬ группы соевующими входа-й элементов И первого по второй rpynq-го элемента оедииен с вывторой груп+ 1)-го элемени первым входом ЧНОСТЬ группы> в РАВНОЗНАЧНОСТЬ ямыми выходами триггеров пероды элементов динены с выходаого по (n-1)-й вые входы элеуппы соединены ьные входы ртой группы ены с прямым третьей группы ии триггеров с и группы, прявторой группы онными входами руппы, входы rx соединены ИЛИ, инверсгера второй мод n-ro триг1 СОЕДИНЕНЫ С выход которого изнака окончания оды элементов и первой группы ажоритарных ды S-го элемен(S=1,m) соединеарных элементов J-я группы.
