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

со

kU 1C

t

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

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

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

Устройство содержит Р регистров, выполненных на триггерах 1 (, ...,Т; , ..., Р, где Т - количество разрядов в двоичном представлении кода числа), ТхР узлов 2, анализа, каждый из которЫх содержит элементы И 3-5, группу из Т элементов ИЛИ 6, группу из Р элементов ИЛИ 7, Р триггеров 8, группу из Т элементов И-НЕ группу .из Т элементов ИЛИ 10, группу из Т элементов И 11, вход 12 управЕсли в первом разряде чисел имеются и нули и единицы, то через элементы И 3 и 4 узлов 2 на группу элементов ИЛИ 10, и 6/ поступают сигналы единичного уровня. На выходе элемента И-НЕ 9, будет сформирован сигнал нулевого уровня, закрывающий элемент И 11. Через элементы. И 5 узлов 2 „ анализа и элемент ИЛИ 7ц , относящиеся к тем регистрам, в первом разряде- которых записан О, сигнал единичного уровня поступает на входы установки в нулевое состояние соответствующих триггеров 8. Соответствующие числа исключаются из дальнейшего сравнения. Элементы И 3 и 4 соответствующих узлов 2 анадиза закрьшаются, и сигнал единичного уровня будет только на выходе элемента ИЛИ 10, . На выходе элемента И-НЕ 9 формируется сигнал единичного уровня, по которому открывается элемент И 11. Далее аналогично производится анализ следующего разряда оставшихся сравниваемых чисел.

Если в разряде сравниваемых чисел содержатся только нули или только ь единицы, то на выходе элемента И-НЕ 9

Изобретение относится- к области вычислительной техники, может быть использовано fi качестве специализированного вычислителя для решения задачи назначения в системах распределенной обработки АСУ и позволяет решить задачу назначения методом максимального столбца (строки). Для это- го на группу информационных входов устройства последовательно подают столбцы (строки) матрицы. Блок сравнения чисел, входящий в состав устройства, выбирает максимальное из чисел столбца и отключает соответст- вующий его положению информационный вход устройства, при этом позиционный код максимального числа запоминается в блоке памяти. В каждой последующей операции выбора максимального числа будут участвовать только те элементы столбца (строки), которые не были отключены по результатам предыдущих операций выбора. 2 ил. W

ления, информационные входы 13, входы 30 установится сигнал единичного уров14 управления Р триггеров 15, Р триг- . геров ID, Р-1 элемент И 17, блок 18 памяти, счетчик 19, элемент 20 задержки, входы 21 установки в О, -входы

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

22 установки в 1, входы 23 строба, 35 выходе элемента И 11 формируется

входы 24 чтения, входы 25 сброса, выход 26 конца выбора, выход 27 конца решения, выход 28 информации.

Устройство работает следующим образом.

В исходном состоянии в блоке 18 памяти записаны нули. Счетчик 19 устанавливается в нулевое состояние сигналом, подаваемым на вход 25. Триггеры 15 и 16 устанавливаются соответственно в нулевое и единичное состояние сигналами, подаваемыми на входы 21 и 22. При подаче на вход 23 строба выходными сигналами с прямых выходов триггеров 16 устанавливаются в единичное состояние триггеры 8. Одновременно с выполнением э.тих операций в регистры 1 устройства принимаются коды элементов первого столбца матрицы стоимости. Устройство готово к работе.

При подаче на вход 12 сигнала единичного уровня производится пораз- ,.рядный анализ сравниваемых чисел.

40

сигнал единичного уровня. При этом на выходах 13,, . .., 13 содержится код экстремального числа, Я на выхо ,дах 14, ..., 14Р - позиционный код номеров регистров, содержащих экстремальное число . .

45

50

55

Для рассматриваемого примера (фиг. 3) при по окончании первого цикла в единичном состоянии останутся триггеры 8 и 8. Сигнал нулевого уровня с инверсного выхода триггера 8 , поступая на первый вход элемента И 17,, закрывает цепь дальнейшего прохождения сигнала, посту- пающего с выхода элемента И 11 на второй вход элемента И 17,. Этот же сигнал поступает на вход синхронизации триггера 15., и вызывает появление на.его прямом выходе сигнала еди ничного уровня. Сигнал с прямого выхода триггера 15i портупает на вход установки в нулевое состояние тригге ра 16 . Состояние остальных триггеро

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

выходе элемента И 11 формируется

сигнал единичного уровня. При этом на выходах 13,, . .., 13 содержится код экстремального числа, Я на выхо- ,дах 14, ..., 14Р - позиционный код номеров регистров, содержащих экстремальное число . .

5

0

5

Для рассматриваемого примера (фиг. 3) при по окончании первого цикла в единичном состоянии останутся триггеры 8 и 8. Сигнал нулевого уровня с инверсного выхода триггера 8 , поступая на первый вход элемента И 17,, закрывает цепь дальнейшего прохождения сигнала, посту- пающего с выхода элемента И 11 на второй вход элемента И 17,. Этот же сигнал поступает на вход синхронизации триггера 15., и вызывает появление на.его прямом выходе сигнала единичного уровня. Сигнал с прямого выхода триггера 15i портупает на вход установки в нулевое состояние триггера 16 . Состояние остальных триггеров

13

16 не изменится. На шинах входной информации блока 18 будет информация 1,0,0,0. Счетчик 19 устанавливается в 1 сигналом с выхода элемента И 11. Под действием задержанного элементом 20 сигнала, подаваемого на вход записи, производится запись информации в блок 18 памяти. Подачей сигнала на вход 23 обеспечивается передача содержимого триггеров 16 {О,1,1,1} в триггеры 8 (из сравнения исключено первое число). По сигналу с выхода элемента И 11, поступающему на выход 26 конца выбора, в ре- ,гистры устройства принимаются коды элементов второго столбца матрицы стоимости. На этом первый цикл работы устройства заканчивается. Второй цикл начинается с установки в нуле- вое состояние триггеров 15 сигналом, подаваемым на вход 21. Подачей сигнала на вход 12 начинается сравнение оставшихся элементов второго столбца. В результате сравнения в единичном состоянии остается триггер 8. На первых выходах элементов И 17, 17 и 17 будут сигналы единичного уровня с инверсных выходов триггеров 8,, 82 и 8. Сигнал еди- ничного уровня с выхода эл&мента И 11 добавляет единицу в счетчик 19 и поступает на второй вход элемента И 17 и вход синхронизации триггера 15 (состояние триггера при этом не меняется). На выходе элемента И 17, появляется сигнал единичного уровня, поступающий на вход синхронизации триггера 15. (состояние триггера также не изменяется) и второй вход элемента И 17. На выходе этого элемента имеется сигнал единичного уровня, поступакиций на вход синхронизации триггера 15з (состояние триггера не изменяется) и второй вход эле- мента И 17. По сигналу с выхода, элемента И 17, устанавливается триггер 15 в единичное состояние. На шинах входной информации набор 0,0,0,1, который запишется в блок 18 памяти, стробирующий сигнал на входе 23 обеспечивает передачу в триггеры 8 содержимого триггеров 16 0,1,1,0. Из

сравнения исключения первое и четвертое число.

Аналогично устройство работает в следующих циклах. После выполнения последнего цикла на выходе 27 появляется сигнал конца работы устройства. В ЗУ содержится матрицы назначения. Чтение из ЗУ можно выполнить по окончании или в процессе работы устройства (во время сравнения).

Формула изобретения Устройство для решения задачи назначения, содержащее группу из Р регистров, где Р - порядок анализируемой матрицы, и блок сравнения чисел, вход пуска которого является тактовым входом устройства, а информационный выход - информационным выходом устройства, причем К-й информационный вход устройства (,...,Р) подключен к входу К-го регистра группы, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет решения задачи назначения методом максимального элемента столбца (строки) матрицы, в него введены группа из Р ключей, блок памяти, блок синхронизации и счетчик, причем выход К-го регистра группы подключен к информационному входу К-го ключа группы, выход которого подключен к К-му информационному входу блока сравнения чисел, К-й выход признака Наибольшее число подключен к К-му разряду информационного входа блока памяти и к управляющему входу К-го ключа группы выход признака окончания операции сравнения блока сравнения чисел подключен к тактовому входу блока синхронизации, первый выход синхронизации которого подключен к суммирующему входу счетчика, информационный выход которого подключен к адресному входу блока памяти, второй выход синхронизации блока синхронизации подключен к входу признака записи блока памяти, вход признака чтения которого является входом опроса устройства, а выход - вторым информационным выходом устройства.