Устройство для решения задачи назначения

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКРЕСПУБЛИК 9) (11) 5/20 ПИСАНИЕ ИЗОБРЕТЕНИВТОРСНОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ(56) Авторское свидетельство СССР Ф 1206792, кл. С 06 Р 15/20, 1985.Авторское свидетельство СССР У 752326, кл. С 06 Р 7/02, 1979. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ НАЗНАЧЕНИЯ(57) Изобретение относится к области вычислительной техники, может быть использовано и качестве специализированного вычислителя для решения задачи назначения в системах распределенной обработки АСУ и позволяет решить задачу назначения методом максимального столбца (строки). Для это,го на группу информационных входов устройства последовательно подают столбцы (строки) матрицы. Блок сравнения чисел, входящий в состав устройства, выбирает максимальное из чисел столбца и отключает соответст- вующий его положению информационный вход устройства, при этом позиционный код максимального числа запоминается в блоке памяти. В калщой последующей операции выбора максимального числа будут участвовать только те элементы столбца (строки), кото-. рые не были отключены по результатам сепредыдущих операций выбора 2 ил.1 137424Изобретение относится к вычислительной технике и может быть использовано в качестве специализированного вычислителя для решения задачиназначения в системах автоматизированного управления.Целью изобретения является расширение функциональных возможностейустройства за счет решения задачиназначения методом максимальногоэлемента столбца (строки) матрицыстоимости.На фиг. 1 изображена функциональная схема примера реализации устройства; на фиг. 2 - пример решения задачи назначения для матрицы размерности Р=4.Устройство содержит Р регистров,выполненныхна триггерах 1, (М=1, 20,Т; К 1, , Р, где Т в количество разрядов в двоичном представлениикода числа), ТхР узлов 2 , анализа,каждый из которых содержит элементыИ 3-5, группу из Т элементов ИЛИ 6, 25группу из Р элементов ИЛИ 7, Р триггеров 8, группу из Т элементов И-НЕ 9,группу .из Т элементов ИЛИ 10, группуиз Т элементов И 11, вход 12 управления,информационные входы 13, входы 3014 управления Р триггеров 15, Р триггеров 16, Рэлемент И 17, блок 18памяти, счетчик 19, элемент 20 задержки, входы 21 установки в "0", входы22 установки в "1", входы 23 строба,входы 24 чтения, входы 25 сброса, выход 26 конца выбора, выход 27 концарешения, выход 28 информации.Устройство работает следующим образом. 40В исходном состоянии в блоке 18памяти записаны нули. Счетчик 19устанавливается в нулевое состояниесигналом, подаваемым на вход 25,Триггеры 15 и 16 устанавливаются соответственно в нулевое и единичноесостояние сигналами, подаваемымина входы 21 и 22. При подаче на вход23 строба выходными сигналами с прямых выходов триггеров 16 устанавливаются в единичное состояние триггеры 8, Одновременно с выполнениемэтих операций в регистры 1 устройства принимаются коды элементов первого столбца матрицы стоимости. Устройство готово к работе.При подаче на вход 12 сигналаединичного уровня производится пораз, рядный анализ сравниваемых чисел,1 2Если в первом разряде чисел имеются и нули и единицы, то через элементы И 3 и 4 узлов 2 на группу элементов ИЛИ 10, и 6, поступают сигналы единичного уровня. На выходе элемента И-НЕ 9, будет сформирован сигнал нулевого уровня, закрывающий элемент И 11,Через элементы И 5 узлов 2, анализа и элемент ИЛИ 7, относящиеся к тем регистрам, в первом разряде. которых записан "0", сигнал единичного уровня поступает на входы установки в нулевое состояние соответствующих триггеров 8. Соответствующие числа исключаются из дальнейшего сравнения. Элементы И 3 и 4 соответствующих узлов 2 анапиза закрываются, и сигнал единичного уровня будет только на выходе элемента ИЛИ 10,. На выходе элемента И-НЕ 9 формируется сигнал единичного уровня, по которому открывается элемент И 11,. Далее аналогично производится анализ следующего разряда оставшихся сравниваемых чисел.Если в разряде сравниваемых чисел содержатся только нули или только единицы, то на выходе элементаИ-НЕ 9 установится сигнал единичного уровня, открывающий элемент И 11. Производится анализ следующего разряда. После того, как все разряды сравниваемых чисел будут проанализированы, на выходе элемента И 11 формируется сигнал единичного уровня, При этом на выходах 13 , 13., содержится код экстремального числа, а на выхо,дах 14,.14 - позиционный код номеров регистров, содержащих экс.тремальное числоДля рассматриваемого примера (фиг. 3) при Р=4 по окончании первого цикла в единичном состоянии останутся триггеры 8, и 8. Сигнал нулевого уровня с инверсного выхода триггера 8 , поступая на первый вход элемента И 17 закрывает цепь дальнейшего прохождения сигнала, посту- пающего с выхода элемента И 11 на второй вход элемента И 17,. Этот же сигнал поступает на вход синхронизации триггера 15 и вызывает появление на.его прямом выходе сигнала единичного уровня. Сигнал с прямого выхода триггера 15 поступает на вход установки в нулевое состояние триггера 16. Состояние остальных триггеровз 137424 16 не изменится. На шинах входной информации блока 18 будет информация 1,0,0,0. Счетчик 19 устанавливается в "1" сигналом с выхода элемента И 11 . Под действием задержанного5 элементом 20 сигнала, подаваемого на вход записи, производится запись информации в блок 18 памяти. Подачей сигнала на вход 23 обеспечивается 1 О передача содержимого триггеров 16 0,1,1,1 в триггеры 8 (из сравнения исключено первое число). По сигналу с выхода элемента И 11., поступающему на выход 26 конца выбора, в ре ,гистры устройства принимаются коды элементов второго столбца матрицы стоимости. На этом первый цикл работы устройства заканчивается. Второй цикл начинается с установки в нуле вое состояние триггеров 15 сигналом, подаваемым на вход 21. Подачей сигнала на вход 12 начинается сравнение оставшихся элементов второго столбца. В результате сравнения в 25 единичном состоянии остается триггер 8. На первых выходах элементов И 171, 172 и 173 будут сигналы единичного уровня с инверсных выходов триггеров 8 8и 8. Сигнал еди О ничного уровня с выхода элемента И 11 добавляет единицу в счетчик 19 и поступает на второй вход элемента И 17 и вход синхронизации триггера 15, (состояние триггера при этом не меняется). На выходе элемента И 17, появляется сигнал единичного уровня, поступающий на вход синхронизации триггера 15 (состояние триггера также не изменяется) и второй вход 4 О элемента И 17 . На выходе этого элемента имеется сигнал единичного уровня, поступающий на вход синхронизации триггера 15 (состояние триггера не изменяется) и второй вход эле б мента И 17. По сигналу с выхода элемента И 17 устанавливается триггер 15 в единичное состояние. На шинах входной информации набор 0,0,0,1, который запишется в блок 18 памяти, стробирующий сигнал на входе 23 обеспечивает передачу в триггеры 8 содержимого триггеров 16 0,1,1,0 . Из сравнения исключения первое и четвертое число.Аналогично устройство работает вследующих циклах. После выполненияпоследнего цикла на выходе 27 появляется сигнал конца работы устройства.В ЗУ содержится матрицы назначения.Чтение из ЗУ можно выполнить по окончании или в процессе работы устройства (во время сравнения). Формула изобретенияУстройство для решения задачи назначения, содержащее группу из Р регистров, где Р - порядок анализируемой матрицы, и блок сравнения чисел, вход пуска которого является тактовым входом устройства, а информационный выход - информационным выходомустройства, причем К-й информационный вход устройства (К=1Р) подключен к входу К-го регистра группы, о т л и ч а ю щ е е с я тем, что,с целью расширения функциональных возможностей устройства за счет решения задачи назначения методом максимального элемента столбца (строки) матрицы, в него введены группа иэ Рключей, блок памяти, блок синхрониэации и счетчик, причем выход К-го регистра группы подключен к информационному входу К-го ключа группы, выход которого подключен к К-му информационному входу блока сравнения чисел, К-й выход признака "Наибольшее число" подключен к К-му разряду информационного входа блока памяти и куправляющему входу К-го ключа группы, выход признака окончания операции сравнения блока сравнения чисел подключен к тактовому входу блока синхронизации,первый выход синхронизации которого подключен к суммирующему входу счетчика, информационный выход которого подключен к адресному входу блока памяти, второй выход синхронизации блока синхронизации подключен к входу признака записи блока памяти, вход признака чтения которого является входом опроса устройства, а выход - вторым информационным выходом устройства.1374241 оставитель А, Мишехред Л.Сердюков ктор Е каз 604/4 Подпискомитета СССРи открытий 1303 кая наб роектная, 4 едприяти жгор Тираж 704 Государственного делам изобретении осква, Ж, Рауш роизводственно-полиграфнчес Корректор И. Шарош