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

1 1374243

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

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

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

На чертеже изображена функциональная схема устройства.16 на входе элемента И 10, выход котороУстройство содержит М счетчиков 1, го соединен с входом параллельной

нен со счетным входом соответствующего счетчика, параллельная запись в счетчик производится только в случае совпадения единичных сигналов

М триггеров 2, группу 3 выходных элементов И, два элемента ИЛИ 4 и 5, первый элемент И 6, М преобразователей 7 кода, М-1 групп 8 элементов 2И-ШШ, три группы 9-11 элементов И три группы 12-14 элементов ИJШ-HEj две группы 15 и 16 элементов ИЛИ, группу 17 элементов И-НЕ, второй элемент И 18, элемент НЕ 19 и два эле- мента 20 и 21 задержки.

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

Работа преобразователя 7 кода опи

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

элемента И 10, выход которого соеди-

на входе элемента И 10, выход которонен со счетным входом соответствующего счетчика, параллельная запись в счетчик производится только в случае совпадения единичных сигналов

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

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

сывается следующими рекуррентными соотношениями:

Y5 Y j: LXgV X.LXj; .LXgV

Y

e t .t где Y; - j-й выход преобразователя

кода;

, - f J вход преобразователя : кода;

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

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

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

В основу работы устройства положены следуклцие принципы: режим работы каждого счетчика 1 (счет либо параллельная запись) определяется сигна выходах элементов И 11 и элементов 2И-ИЛИ 8 появляется только при несовпадении единичных сигналов на входах соответствующих элементов И-НЕ 17 с выходов соответствующих элементов И-НЕ 17 с выходов соответствующих элементов И 9 и с инверсных выходов соответствующих триггеров 2. Сигнал с выхода (р+1)-го элемента И 9 : коммутирует поступление информации

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

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

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

В режиме перебора сочетаний С, где (в данном случае) а m изме- .няется последовательно от 1 до 3, единичньм сигнал установки режима подается на вход 26, устанавливает ю счетчики 1 - 3 и триггеры 4 - 6 в ну

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

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

Шестой тактовый импульс вьщает на выход устройства первое сочетание Cj 01 и прибавляет единицу к состоя- нию счетчика 1. До восьмого такта включительно устройство работает аналогично. При этом на выходе первого элемента И 9 появляется единичный сигнал, открывакяций счетньй вход второго счетчика 1 и вход параллельной записи первого счетчика 1. тактовый импульс вьщает на выход уст

ройства четвертое сочетание С 04, записывает в первый счетчик 1 состояние 2 и прибавляет единицу к состоянию второго счетчика 1. До четырнадцатого такта включительно устройство pa6ojraeT аналогично.

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

С этого момента бор сочетаний с

начинается пере- Шестнадцатый тактовьй импульс выдает на выход устройства первое сочетание Cj.012 и при

5

0 5 0

0

5

бавляет к состоянию первого счетчика 1 единицу. До 24-го такта включительно устройство работает аналогично. Двадцать пятьш тактовый импульс вьщает на выход устройства последнее сочетание 234, на выходе третьего триггера 2 выдает единичное состояние, которое свидетельствует об окончании перебора и блокирует прохождение тактовых импульсов-через элемент И 6.

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

45

50

5 6 7

4

01

02

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

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

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

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

5

0

д

0

5

5

5

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

группы (п-1М-3), вторые входы

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

соответствующего триггера, выход последнего элемента ИЛИ-НЕ третьей груп пы пoдклюfчeн к входу первого элемента задержки, выход которого подключен к синхровходу М-го триггера, вход режима перебора всех сочетаний устрой- ства соединен с входами установки в О счетчиков, с первым входом второго элемента ШШ и входом элемента НЕ, выход второго элемента ИЛИ подключен к вторым входам элементов ИЛИ-НЕ третьей группы, выход элемента НЕ подключен к D-входам всех триггеров, кроме М-го, D-вход которого подключен к выходу второго элемента И, второй вход которого подключен к выходу элемента НЕ, вход режима пе« ребора сочетаний с заданной разрядностью устройства подключен к второ му входу второго элемента ИЛИ, вторым .входам элементов ИЛИ и ИЛИ-НЕ первых и вторызг групп и входу второго элемента задержки, выход которого подключен к второму входу элемента за держки, выход которого подключен к второму входу первого элемента ИЛИ, выход которого соединен с вторыми входами элементов И третьей группы.

3

г.

Г

гз

5

п

I

/3