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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК в) 4 С 06 Р 15/30 ОПИСАНИЕ ИЗОБРЕТЕНИЯ 13,яяЯН(ч К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) Авторское свидетельство СССРУ 760108, кл. С 06 Р 15/20, 1980.Авторское свидетельство СССРВ 991432, кл. Ь 06 Р 15/20 1983.Авторское свидетельство СССРУ 374606, кл. С 06 Р 15/32, 1973.(54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ(57) Изобретение относится к вычислительной технике и может быть исполь 801374243 А 1 зовано для построения специализированных вычислителей, ориентированных на решение комбинаторных задач, Целью изобретения является повышение быстродействия устройства и расширение функциональных возможностей за счет обеспечения возможности перебора сочетаний с заданной разрядностью. Значение минимального элемента в сочетаниях устанавливается по входам начальной установки, Режим работы счетчиков задается сигналами по входам режима перебора сочетаний, причем собственно перебор сочетаний выполняется последовательно подключаемыми к работе устройства счетчиками. Окончание перебора фиксируется единичным сигналом на прямом выходе триггера, 1 ил 1 табл.1374243 1 2 14 34 15 0 12 16 0 13 17 0 14 18 0 23 19 01 0 24 20 02 рует на элементе И 6 прохождение тактовых импульсов, а единичный сигналс его прямого выхода свидетельствуетоб окончании перебора.5В режиме перебора сочетаний С,где (в данном случае) п=5; а ш изменяется последовательно от 1 до 3,единичный сигнал установки режимаподается на вход 26, устанавливает 10счетчики 1 - 3 и триггеры 4 - 6 в нулевые состояния, что открывает элемент И 6 для прохождения тактовыхимпульсов, причем только у первогосчетчика 1 счетный вход является 15открытым.Первый тактовый импульс выдает навыход устройства первое сочетание С0 и прибавляет к содержимому первогосчетчика 1 единицу, причем тактовый 20импульс должен закончиться до окончания переходных процессов в счетчике. До четвертого такта включительноустройство работает аналогично, Пятый тактовый импульс вьдает на выход 25устройства пятое сочетание С 4, записывает в первый счетчик 1 состояние 1 (в двоичном коде) с выходовпервого преобразователя 7 кода и устанавливает на выходах первого триггера 2 единичное состояние. С этогомомента начинается перебор сочетаний С,Шестой тактовый импульс вьдаетна выход устройства первое сочетание2С 01 и прибавляет единицу к состоянию счетчика 1. До восьмого тактавключительно устройство работает аналогично. При этом на выходе первогоэлемента И 9 появляется единичный 40сигнал, открывающий счетный вход второго счетчика 1 и вход параллельнойзаписи первого счетчика 1. Девятыйтактовый импульс вьдает на выход устройства четвертое сочетание С 04, 45записывает в первый счетчик 1 состояние 2 и прибавляет единицу к состоянию второго счетчика 1. До четырнад. цатого такта включительно устройствоработает аналогично. 50 Пятнадцатый тактовый импульс вьдает на выход устройства десятое сочетание С 34, записывает в первый2счетчик 1 состояние 2, а во второй счетчик 1 - состояние 1 и устанавливает на выходе второго триггера 2 единичное состояние, подключающее к работе устройства третий счетчик 1,С этого момента начинается перебор сочетаний С . Шестнадцатый тактовый импульс вьдает на выход устройзства первое сочетание С . 012 и прибавляет к состоянию первого счетчика 1 единицу, До 24-го такта включительно устройство работает аналогично, Двадцать пятый тактовый импульсвыдает на выход устройства последнеесочетание 2 3 4, на выходе третьеготриггера 2 выдает единичное состояние, которое свидетельствует об окончании перебора и блокирует прохождение тактовых импульсов. через элементИ 6.В режиме перебора сочетаний с фик-сированным значением ш=3 на входыустановки подаются единичные сигналы,единичный сигнал установки данногорежима подается на вход 27, устанавливает на выходах первых трех преобразователей 7 кода состояния 2, 1, Осоответственно, открывает входы па"раллельной записи счетчиков и, пройдя через элемент 21 задержки и злемент ИЛИ 4, записывает в первые трисчетчика 1 состояния с выходов .соответствующих преобразователей 7 кодасоответственно. Задний фронт импульса установки режима, проинвертированный элементами ИЛИ-НЕ 14, выдает навыходы первых двух триггеров 2 единичные состояния, а на выход третье"го триггера 2 - нулевое состояние,открывающее элемент И 6 для прохождения тактовых импульсов. Далее устройство работает аналогично рассмотренному случаю, начиная с шестнадцатого такта (см. таблицу),У такта Состояние У такта Состояние,13 2 34 25 14 12 23 13 Формула изобретения Устройство для перебора сочетаний, содержащее М счетчиков (где М - максимальная разрядность сочетаний), М триггеров, М групп выходных элементов И, два элемента ИЛИ, первый элемент И; причем первый вход первого .элемента И является тактовым входом устройства, выход первого элемента И подключен к первому входу первого элемента ИЛИ, прямые выходы разрядов К-го счетчика (где К=1М) подключены к первым входам соответствующих выходных элементов И К-й груп 20Входы 24 начальной установки слу-. жат для установки минимального элемента в сочетаниях. Для этого на нихнужно подать в двоичном коде число, на единицу меньше минимального элемента. Например, при подаче на входы установки состояния 0,(минимальный элемент - 1) устройство работает аналогично предыдущему случаю, начинаяс 22-го такта, а при подаче на входы установки состояния 1 (минимальный элемент - 2) на выход устройства выдается всего. одно сочетание, соответствующее 25-му такту работы устройства в режиме перебора сочетаний со всеми ш. Последний рассмотренный режим работы устройства необходим . в тех случаях, когда перебор сочетаний со всеми ш либо сочетаний с минимальным элементом, равным нулю, явля ется ненужным и резко снижающим,быстродействие всего устройства при решении некоторых комбинаторных задач,43пы, вторые входы выходных элементов И всех групп подключены к выоду первого элемента И, а выходы выходных элементов И К-й группы являются соответствующими выходами К-й группы устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства и расширения его функциональных воэможностей за счет возможности перебора сочетаний с заданной разрядностью, в него введены М преобразователей кода, Мгрупп элементов 2 И-ИЛИ, три группы элементов И, три группы элементов ИЛИ-НЕ, две группы элементов ИЛИ, группа элементов И-НЕ, второй элемент И, элемент НЕ и два элемента задержки, причем прямые выходы разрядов (р+1)-го счетчика (р=1,2М) подключены к первым входам соответствующих элементов 2 И-ИЛИ р-й группы, выходы которых подключены к соответствующим входам (р+1)-го преобразователя кода, выход К-го преобразователя кода под-. ключен к информационному входу К-го. счетчика, выходы разрядов второго преобразователя кода подключены к первым входам соответствующих элементов.И третьей группы, выходы которых подключены к соответствующим разрядам входа первого преобразователя, вторые входы элементов И третьей группы подключены к выходу первого элемента И-НЕ группы, выходы разрядов Ь-го преобразователя кода (Ь= =ЗМ) подключены к вторым входам соответствующих элементов 2 И-ИЛИ и-й группы (пМ-З), вторые входы элементов 2 И-ИЛИ (М)-й группы являются входами начального состояния устройства, выходы разрядов К-го счетчика подключены к соответствующим входам К-го элемента И первой группы, выход которого подключен, к первым входам К-х элементов ИЛИ-НЕ первой и третьей групп, К-го элемента ИЛИ первой группы и К-го элемента И-НЕ группы, выход (р+1) -го элемента И первой группы подключен к второму входу р-го элемента ИЛИ-НЕ второй группы и к первому входу р -го элемента ИЛИ второй группы, выход которого подключен к третьим входам элементов 2 И-ИЛИ р-й группы, выход р-го элемента ИЛИ-НЕ второй группы подключен к четвертым входам элементов 2 И-ИЛИ р-й группы, выход р-го элемента И первой группы подклю1374243 7чен к первому входу (2 р+1)-го элемента И второй группы, а выход М-го элемента И первой группы соединен с первым входом второго элемента И, выход (2 р)-го элемента И второй группы подключен к счетному входу р-го счет,чика, выход 2 р-го элемента И второй группы соединен с входом разрешения записи р-го счетчика, второй вход 1 О (2 р)-го элемента И второй группы подключен к выходу р-го элемента ИЛИНЕ первой группы, первый вход 2 р-го элемента И второй группы соединен с выходом р-го элемента ИЛИ первой 5 группы, выход (р+1)-го элемента И-НЕ группы подключен к пятым и шестым входам элементов 2 И-ИЛИ р-й группы, инверсный выход К-го триггера подключен к второму входу К-го элемента 2 О И-НЕ группы, прямой выход р-го триггера подключен к третьему входу (2 р+1)-го элемента И второй группы, прямой выход М-го триггера является выходом признака окончания перебора 25 устройства, а инверсный выход М-го триггера подключен к второму входу первого элемента И, выход каждого элемента ИЛИ-НЕ третьей группы, кроме последнего, соединен с синхровходом соответствукзцего триггера, выход последнего элемента ИЛИ-НЕ третьей груп-.пы подключен к входу первого элементазадерзаси, выход которого подключенк синхровходу М-го триггера, вход режима перебора всех сочетаний устройства соединен с входами установкив "О" счетчиков, с первым входом второго элемента ИЛИ и входом элемента НЕ, выход второго элемента ИЛИподключен к вторым входам элементовИЛИ-НЕ третьей группы, выход элемента НЕ подключен к В-входам всех триггеров, кроме М-го, 0-вход которогоподключен к выходу второго элемента И, второй вход которого подключенк выходу элемента НЕ, вход резима перебора сочетаний с заданной разрядностью устройства подключен квторому входу второго элемента ИПИ, вторымвходам элементов ИЛИ и ИЛИ-НЕ первыхи вторых групп и входу второго элемента задерики, выход которого подключен к второму входу элемента задерзки, выход которого подключен квторому входу первого элемента ИЛИ,выход которого соединен с вторымивходами элементов И третьей группы.