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

 

Изобретение относится к вычислительной технике и может быть использовано для построения специализированных вычислителей, ориентированных на решение комбинаторных задач. Целью изобретения является повышение быстродействия устройства и расширение функциональных возможностей за счет обеспечения возможности перебора сочетаний с заданной разрядностью. Значение минимального злемента в сочетаниях устанавливается по входам начальной установки. Режим работы счетчиков задается сигналами по входам режима перебора сочетаний, причем собственно перебор сочетаний выполняется последовательно подключаемыми к работе устройства счетчиками. Окончание перебора фиксируется единичным сигналом на прямом выходе триггера, 1 ил., 1 табл.. . S (Л

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК

„„SU„„1374243 А1 (д1) 4 G 06 F 15/30

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

f Iß jTÍ(ч, К А BTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4101806/24-24 (22) 11.06.86 (46) 15.02.88. Бюл. У 6 (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) В.М.Глушань, И.В.Мачульский и Л.И.Щербаков (53) 681.325(088.8) (56) Авторское свидетельство СССР

У 760108, кл. Ь 06 F 15/20, 1980.

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

В 991432, кл. G 06 F 15/20 1983.

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

У 374606, кл. G 06 F 15/32, 1973. (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ (57) Изобретение относится к вычислительной технике и может быть использовано для построения специализированных вычислителей, ориентированных на решение комбинаторных задач. Целью изобретения является повышение быстродействия устройства и расширение функциональных возможностей за счет обеспечения возможности перебора сочетаний с заданной разрядностью. Значение минимального элемента в сочетаниях устанавливается по входам начальной установки. Режим работы счетчиков задается сигналами по входам режима перебора сочетаний, причем собственно перебор сочетаний выполняется последовательно подключаемыми к работе устройства счетчиками. Окончание перебора фиксируется единичным сигналом на прямом выходе триггера.

1 ил., 1 табл.

1374243

15

55

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

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

На чертеже изображена функциональная схема устройства.

Устройство содержит М счетчиков 1, М триггеров 2, группу 3 выходных элементов И, два элемента ИЛИ 4 и 5, первый элемент И 6, M преобразователей 7 кода, М-1 групп 8 элементов

2И-ИЛИ, три группы 9 — 11 .элементов И, три группы 12-14 элементов ИЛИ-НЕ, две группы 15 и 16 элементов ИЛИ, группу 17 элементов И-НЕ, второй элемент И 18, элемент НЕ 19 и два элемента 20 и 21 задержки.

Устройство имеет тактовый вход 22, группы 23 выходов, входы 24 начального состояния, выход 25 признака окончания перебора, вход 26 режима перебора всех сочетаний, вход 27 режима перебора сочетаний с заданной разрядностью, Работа преобразователя 7 кода описывается следующими рекуррентными соотношениями:

LX,V Х ЬХ

, =Х, „LX v Хе, .Хе; еуе = хе э где У вЂ” j-й выход преобразователя

J кода;

Х - — j-й вход преобразователя кода;

1 — разрядность преобразователя.

Устройство работает в двух режимах: в режиме последовательного перебора сочетаний С при всех значенин ях m начиная с единицы, и в режиме перебора сочетаний с фиксированным значением m> равным максимальному, при возможности установки минимального. значения элемента в сочетаниях.

Работа устройства во всех режимах иллюстрируется таблицей.

В основу работы устройства положены следующие принципы: режим работы каждого счетчика 1 (счет либо параллельная запись) определяется сигналом на выходе соответствующего элемента И 9, для каждого счетчика, кроме первого, режим работы зависит и от сигнала на выходе предыдущего по порядку элемента И 9 и предыдущего по порядку триггера, счет в счетчике может произойти только при совпадении единичных сигналов на входе элемента И 10, выход которого соединен со счетным входом соответствующего счетчика, параллельная запись в счетчик производится только в слу" чае совпадения единичных сигналов на входе элемента И 10, выход которого соединен с входом параллельной записи соответствующего счетчика 1.

Режим работы всех счетчиков 1 (параллельная запись) задается также

20 единичным сигналом с входа 26 установки режима перебора всех сочетаний. Выдача очередного состояния счетчикбв 1 на выход 23 устройства осуществляется подачей тактового импульса через элемент И 6 на вторые входы выходных элементов И групп 3, на первые входы которых подаются сигналы состояний с выходов соответствующих счетчиков 1. Состояния на информационных входах триггеров 2 уста навливаются с выхода элемента НЕ 19, а до последнего триггера 2 еще и с выхода последнего элемента И 9 группы через второй элемент И 18. Информация на выходах элементов И 11 и элементов 2И-ИЛИ 8 появляется только при несовпадении единичных сигналов на входах соответствующих элементов И-НЕ

17 с выходов соответствующих элементов И-HE 17 с выходов соответствующих элементов И 9 и с инверсных выходов соответствующих триггеров 2. Сигнал с выхода (р+1)-го элемента И 9 коммутирует поступление информации на входы элементов 2И-ИЛИ р-й группы

8 либо с выходов (р+1) го счетчика 1 (нулевой сигнал), либо с выходов (р+2)-го преобразователя 7 кода (единичный сигнал), (m-1)-я группа 2И-ИЛИ

8 при единичном сигнале с выхода последнего элемента И 9 принимает информацию с входов 24 начальной уста- новки. Запись в триггеры 2 происходит задним фронтом сигнала, а выдача состояния на их выходы — по переднему фронту сигнала с выхода соответствующего элемента И 9 либо с выхода элемента ИЛИ 5. Нулевой сигнал с инверсного выхода М-ro триггера 2 блоки1374243

1 2

34

0 12

0 13

0 14

0 23

01

0 24

02 рует на элементе И 6 прохождение тактовых импульсов, а единичный сигнал с его прямого выхода свидетельствует об окончании перебора.

В режиме перебора сочетаний С„, где (в данном случае) n=5; à m изменяется последовательно от 1 до 3, единичный сигнал установки режима подается на вход 26, устанавливает 10 счетчики 1 — 3 и триггеры 4 — 6 в нулевые состояния, что открывает элемент И 6 для прохождения тактовых импульсов, причем только у первого счетчика 1 счетный вход является 15 открытым.

Первый тактовый импульс выдает на выход устройства первое сочетание С

0 и прибавляет к содержимому первого счетчика 1 единицу, причем тактовый 20 импульс должен закончиться до окончания переходных процессов в счетчике. До четвертого такта включительно устройство работает аналогично. Пятый тактовый импульс выдает на выход устройства пятое сочетание С 4, за1 писывает в первый счетчик 1 состояние 1 (в двоичном коде) с выходов первого преобразователя 7 кода и устанавливает на выходах первого триг- 30 гера 2 единичное состояние. С этого момента начинается перебор сочетай с

Шестой тактовый импульс вьдает на выход устройства первое сочетание и

С 01 и прибавляет единицу к состоянию счетчика 1. До восьмого такта включительно устройство работает аналогично. При этом на выходе первого элемента И 9 появляется единичный 40 сигнал, открывающий счетный вход второго счетчика 1 и вход параллельной записи первого счетчика 1. Девятый тактовый импульс вьдает на выход устройства четвертое сочетание С 04, 46: записывает в первый счетчик 1 состояние 2 и прибавляет единицу к состоянию второго счетчика 1. До четырнад. цатого такта включительно устройство работает аналогично. 50

Пятнадцатый тактовый импульс вьдает на выход устройства десятое соче2 тание С5 34, записывает в первый счетчик 1 состояние 2, а во второй I счетчик 1 — состояние 1 и устанавливает на выходе второго триггера 2 единичное состояние, подключающее к работе устройства третий счетчик 1.

С этого момента начинается перебор сочетаний С . Шестнадцатый тактовый импульс вьдает на выход устройства первое сочетание С . 012 и при3 бавляет к состоянию первого счетчика 1 единицу. До 24-ro такта включительно устройство работает аналогично. Двадцать пятый тактовый импульс выдает на выход устройства последнее сочетание 2 3 4, на выходе третьего триггера 2 выдает единичное состояние, которое свидетельствует об окончании перебора и блокирует прохождение тактовых импульсов. через элемент

И 6.

В режиме перебора сочетаний с фик- сированным значением ш=3 на входы установки подаются единичные сигналы, единичный сигнал установки данного режима подается на вход 27, устанавливает на выходах первых трех преобразователей 7 кода состояния 2, 1, 0 соответственно, открывает входы па" раллельной записи счетчиков и, пройдя через элемент 21 задержки и зле мент ИЛИ 4, записывает в первые три счетчика 1 состояния с выходов соответствующих преобразователей 7 кода соответственно. Задний фронт импульса установки режима, проинвертированный элементами ИЛИ-НЕ 14, выдает:на выходы первых двух триггеров 2 единичные состояния, а на выход третье го триггера 2 — нулевое состояние, открывающее элемент И 6 для прохождения тактовых импульсов. Далее устройство работает аналогично рассмотренному случаю, начиная с шестнадцатого такта (см. таблицу).

У такта Состояние У такта Состояние

5 13742

Продолжение таблицы

Состояние

Ф такта

Состояние

Ф такта

4 5

0 34

03

1 23

22 04

1 24

10

1 34

24.13

2 34

14

23

Формула изобретения

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

Входы 24 начальной установки слу-. жат для установки минимального элемента в сочетаниях. Для этого на них нужно подать в двоичном коде число, на единицу меньше минимального элемента. Например, при подаче на входы установки состояния 0.(минимальный элемент — 1) устройство работает аналогично предыдущему случаю, начиная с 22-ro такта, а при подаче на входы установки состояния 1 (минимальный элемент — 2) на выход устройства выдается всего. одно сочетание, соответствующее 25-му такту работы устройства в режиме перебора сочетаний со всеми ш. Последний рассмотренный режим работы устройства необходим . . в тех случаях, когда перебор сочетаний со всеми m либо сочетаний с минимальным элементом, равным нулю, явля- 40 ется ненужным и резко снижающим,быстродействие всего устройства при решении некоторых комбинаторных задач.

43 пы, вторые входы выходных элементов И всех групп подключены к вы оду первого элемента И, а выходы выходных элементов И К-й группы являются соответствующими выходами К-й группы устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства и расширения его функциональных воэможностей за счет возможности перебора сочетаний с заданной -разрядностью, в него введены

М преобразователей кода, M-1 групп элементов 2И-ИЛИ, три группы элементов И, три группы элементов ИЛИ-НЕ, две группы элементов ИЛИ, группа элементов И-НЕ, второй элемент И, элемент НЕ и два элемента задержки, причем прямые выходы разрядов (р+1)-ro счетчика (р=1,2,...,М-1) подключены к первым входам соответствующих элементов 2И-ИЛИ р-й группы, выходы которых подключены к соответствующим входам (р+1)-го преобразователя кода, выход К-го преобразователя кода под-. ключен к информационному входу К-ro. счетчика, выходы разрядов второго преобразователя кода подключены к первым входам соответствующих элементов.И третьей группы, выходы которых подключены к соответствующим разрядам входа первого преобразователя, вторые входы элементов И третьей . группы подключены к выходу первого элемента И-HE группы, выходы разрядов L-го преобразователя кода (L=

=З,...,M) подключены к вторым входам соответствующих элементов 2И-ИЛИ и-й группы (n-1,...,М-З), вторые входы элементов 2И-ИЛИ (M-1)-й группы являются входами начального состояния устройства, выходы разрядов К-го счетчика подключены к соответствуюпим входам К-го элемента И первой группы, выход которого подключен, / к первым входам К-х элементов ИЛИ-НЕ первой и третьей групп, К-го элемента ИЛИ первой группы и К-го элемента И-НЕ группы, выход (р+1) -ro элемента И первой группы подключен к второму входу р-го элемента ИЛИ-НЕ второй группы и к первому входу

pL-ro элемента ИЛИ второй группы, выход которого подключен к третьим входам элементов 2И-ИЛИ р-й группы, выход р-го элемента ИЛИ-НЕ второй группы подключен к четвертым входам элементов 2И-ИЛИ р-й группы, выход р-го элемента И первой группы подклю43

13742 пы.

7 чен к первому входу (2р+1)-ro элемента И второй группы, а выход М-ro элемента И первой группы соединен с первым входом второго элемента И, выход (2р-1)-ro элемента И второй группы подключен к счетному входу р-ro счет,чика, выход 2р-го элемента И второй группы соединен с входом разрешения записи р-го счетчика, второй вход 1р (2р-1)-го элемента И второй группы подключен к выходу р-го элемента ИЛИНЕ первой группы, первый вход 2р-ro элемента И второй группы соединен с выходом р-ro элемента ИЛИ первой 5 группы, выход (р+1)-го элемента И-НЕ группы подключен к пятым и шестым входам-элементов 2И-ИЛИ р-й группы, инверсный выход К-ro триггера подключен к второму входу К-го элемента 2О

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

s "О" счетчиков, с первым входом второго элемента KIH и входом элемента НЕ, выход второго элемента ИЛИ подключен к вторым входам элементов

ИЛИ-НЕ третьей группы, выход элемента НЕ подключен к D-входам всех триггеров, кроме М-ro, D-вход которого подключен к выходу второго элемента И, второй вход которого подключен к выходу элемента НЕ, вход режима пе ребора сочетаний с заданной разрядностью устройства подключен к второ му входу второго элемента KIH вторым входам элементов ИЛИ и ИЛИ-НЕ первых и вторых групп и входу второго элемента задерики, выход которого подключен к второму входу элемента за дерзки, выход которого подключен к второму входу первого элемента ИЛИ, выход которого соединен с вторыми входами элементов И третьей груп1374243

Составитель Н.Захаревич

Редактор Е.Копча Техред Л.Сердюкова Корректор M.Øàðîøè

Заказ 604/46 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, г,ужгород, ул.Проектная, 4