Устройство для определения экстремального числа

ОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик о 11981987(Я) М. Кл.з С 06 С 7/02 с присоединением зеявки Мо(23) ПриоритетГосударствеииый комитет СССР ио делам изобретений и .открытийОпубликовано 15,12,82. бюллетень йо 46 Дата опубликования описания 1512,82 ФВ. И, Финаеви В.А. Креков; .г .Таганрогский радиотехнический институтим. В.Д. Калмыкова(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНОГО ЧИСЛАИзобретение относится к автоматике и вычислительной технике и может найти пригленение в вычислительных и управляющих устройствах при выполнении операций сравнения по величинам некоторого числа многоразрядных кодовых комбинаций.Известно устройство для сравнения двоичных чисел, содержащее блоки срав О нения, число которых равно числу разрядов сравниваемых кодовых комбинаций, элементы ИЛИ-НЕ и И-НЕ, первый и второй элементы НЕ, причем с первыМи входами блоков сравнения соединены первые входные шины прямого кода первого числа, со вторыми входами соединены вторые входные шины прямого кода второго числа, с третьими входами - третьи входные шины инверсного кода первого числа, с четвертыми входами - четвертые входные шины инверсного кода второго числа соответственно, первые выходы каждого блока сравнения, кроме последнего, соединены с пятыми вхо дами последующего блока сравнения, вторые выходи блоков сравнения соединены со входами элемента ИЛИ-НЕ, первый выход последнего блока сравнения соединен с первой выходной 30 шиной устройства, а третий выход последнего блока сравнения соединен с первым входом элемента И-НЕ, второй вход которого соединен с выходом первого элемента НЕ, а выход - через второй элемент НЕ соединен со второй выходной шиной устройства, третья выходная шина которого соединена с выходом элемента ИЛИ-НЕ и со входом первого элемента НЕ 1 .Недостаток этого устройства состоит в том, что данное устройство сравнивает лишь две кодовые комбинации, а для сравнения и кодовых комбинаций потребуется провести по крайней мере и последовательных операций сравнения, что снижает быстродействие известного устройства.Наиболее близкигл к изобретению является устройство для сравнения о двоичных .чисел, содержащее регистры, первые, вторые и третьи элементы И, триггера, блоки сравнения, элементы ИЛИ н НЕ, причем первая входная шина соединена с нервами входами регистров, первые выходы которых соединены с первыми входами соответствующих первых элементов И, вторые входы которых соединены со вторыми выходам и входами соответ 981987ствующих регистров, третьи входы соединены со второй входной управляющей ьиной и первым входом третьего элемента И, а выходы - с первыми входами соответствующих вторых элементов И, вторые входы которых соеди нены с выходами соответствующих триггеров, а выходы - со входами элемента ИЛЙ, выход которого соединен со вторым входом третьего элемента И, входом элемента НЕ и первыми входа- Ю ми блоков сравнения, вторые входы которых соединены с третьей входной управляющей шиной, а выходы - с первыии входами соответствующих триггеров, вторые входы которых соединены 5 с четвертой входной управляющей шиной а выходная шина устройства соединена с выходом третьего элемента И, третий вход которого соединен с, выходом элемента НЕ 2 . . З)Недостаток известного устройствасостоит в следующем. Процесс сравне-ния двух чисел определяется подачейуправляющих сигналов по второй,третьей и четвертой входным. Управляющим шинам, т.е, затрачивается дополнительно время на процесс анализаи процесс управления. Кроме того,информация в регистры вводйтся пос,ледовательно, что также уменьшает ЗОпроцесс быстродействия устройстваТаким образом недостаток известногоустройства заключается в его низкомбыстродействии,Целью изобретения является повышение быстродействия.Указанная цель достигается тем,что в устройство для определенияэкстремального числа, содержащее и.регистров, и групп элементов И, где 4 Ои - количество сравниваемых чисел,(К) узлов анализа, где К - числоразрядов в сравниваемых числах,причем каждый 1-ый прямой выход каждого -го регистра, где 1=1,2,.и,)=1,2. К соединен с перьми входом1-го элемента И 1-ой группы, 1-ымвходом первой группы 1-ого узла анализа, введено К дешифраторов, каждые1-ые прямой .и инверсный выходы каждого 1-го регистра соединены с 1-ымивходами первой и второй групп соответственно -ого дешиЪратора, каждый1-ый выход каждого 1-го дейифратора,где 1=2,3 .К подключен к 1-омувходу второй группы входов (1-1)-гоузла аналнза, каждый 1-ый выходкаждого е-го узла анализа,. гдев=1,2,(К) соединен .с 1-ым входом третьей группы (в+1)-го узла анализа, каждый 1-ый выход первого дешифратора подключен к 1-ому входутретьей группы первого узла анализа, а каждый 1-ый выход (К)-гоузла анализа соединен со вторымивходами элементов И 1"ой группы и , 65 тем, что дешифраторы состоят из элементов И, группы элементов ИЛИ, причем каждый 1-ый вход первой и второйгрупп входов дешифратора соединен с1-ым входом первого и второго элементов И соответственно, выходы первого и второго элементов И подключены к первому и второму входам соответственно элементов ИЛИ группы,каждый 1-ый вход второй группы входовдешифратора сбединен с третьим входом 1-го элемента ИЛИ группы, выходкаждого 1-го элемента ИЛИ подключенк 1-ому выходу дешифратора, а также тем, что в нем каждый узел анализа содержит группы элементов НЕ, И,ИЛИ, причем каждый 1-ый вход, первойгруппы входов узла соединенс первымвходом 1-го элемента И первой ивторой групп, каждый 1-ый вход второйгруппы входов узла подключен к первому входу 1-го элемента И третьейгруппы и через 1-ый элемент НЕ - кпервому входу 1-го элемента И четвертой группы, выход каждого 1-гоэлемента И третьей и четвертой группсоединен с первым и вторым входом соответственно 1-го элемента ИЛИ первой группы, выход каждого 1-го элемента ИЛИ первой группы подключен кпервому входу 1-го элемента И пятойгруппы, выход каждогоиз которыхсоединен с 1-ым выходом узла, каждый1-ый вход третьей группы входов узла подключен ко второму входу 1-гоэлемента И первой труппы, ко. второмувходу 1-го элемента И второй группы,ко второму входу 1-го элемента Ипятой группы и через 1-ый элементНЕ второй группы - к первому входу1-го элемента ИЛИ второй группы, второй вход которого .соединен с выходом1-го элемента И первой группы, выход каждого 1-го элемента ИЛИ второйгруппы подключен к соответствующемувходу элемента И второй группы, выходкаждого 1-го элемента И второй группы соединен со вторым входом 1-гоэлемента И четвертой группы и через1-ый элемент НЕ третьей группы - совторым входом 1-го элемента И третьей группы.На Фиг. 1 приведена блок-схемаустройства на Фиг. 2 - Функциональная схема дешифратора 1 на фиг, 3 -функциональная схема каждого изблоков сравнения.Устройство содерзнут входные шины1 1 1 к 11 15 10 15 20 25 30 35 40 45 50 55 60 65 элементов ИЛИ 11.1, 11 л 2, .;. 11 п, выходы 12 , 12 а, 12 п. Каждый узел анализа состоит иэ групп элементов И 13 и 14, группы входов узла 15, группы элементов НЕ 16, группы элементов, И 17, группы элементов НЕ 18, группы элементов И 19, группы элементов НЕ 20, группы элементов И 21, группы элементов ИЛИ 22, группы выходов узла 23, группы элементовИЛИ 24.Устройство работает следующим образом.По входным шинам 1. 1 и поступаети кодовых комбинаций, из которых устройство выбора минимального кода должно выбрать минимальную по величине, кодовую комбинацию, причем, если в поступающих по входам 1 а - 1 п кодах имеется р одинаковых по величине и минимальных среди и кодовых комбинаций, то данный случай также должен быть распознан предлагаемым устройством выбора минимального кода. Причем каждая -ая кодовая комбинация подается по входным шинам 11- 1 в соответствующий регистр 2. Кодовые комбинации записываются в ячейки регистра 21- 2 п по входным шинам 1 1- 1 П параллельно во времени, но последовательно по разрядам, т.е. вначале будут одновременно поданы 1 импульсы по входным. шинам 1, Ф 11. 13 .(1, затем по входным шийамл 2 21, 1 , 1 а,1, и т,д. до завершающей подачи импульсов кодовых комбинаций по входным шинамк к к к1 лл1 а 13 г1 лл л ГДЕ К ЧИСЛО разрядов сравниваемых по величине и кодовых комбинаций. Параллельно- последовательной записью кодовых комбинаций в регистры 2 обеспечи- вается последовательное срабатывание во времени дешифраторов состояний 3,1- Зк и узлов анализа 41- 4 и-АлгОритм работы устройства выбора минимального кода состоит в последовательном анализе параллельных (одноименных) разрядов кодовых комбинаций, записанных в регистры 2 - 2с последовательным выявлением больших по величинам кодов в параллельных (одноименных) разрядах, начиная со старшего разряда вплоть до младшего. Причем анализ параллельных разрядов кодовых комбинаций регистров 2 производится как дешифраторами состояний 3- Зк, так и узлами, анализа 4- 4, но выявление кодовых комбинаций, меньших по величине чем наибольшее, производится первым дешифратором состояний 3 и узлами анализа 4- 4 к , причем последний узел анализа 4выявляет минимальные (одну или несколько) кодовые комбинации из и, записанных в регистры 2. Сущность алгоритма работы устройства выбора минимального кода состоит в следующем. Вначале рассмотрим параллельные старшие разряды. а "а ф регистров 2. Очевидно здесь возможны следующие события. Символы всех разрядов а - а 1 равны нулю, символы всех разрядов а - а, равны единице, либо имеются символы равные нулю и единице. В первых двух случаях на выходах 12- 12 дешифратора 3 должнны быть единичные потенциалы, а в третьем случае, единичные потенциалы должны быть на тех выходах 12- 12 а, которые соответствуют по верхнему индексу регистрам 2 в старшие ячейки которых а - ая записаны нулевые знае4чения разрядов кодов, т.е. для рассматриваемого примера с восемью регистрами, единичный потенциал будет на выходах 12, 121, 12, 12, 12, 121, логическую фуйкцию, которая7определяет сигнал на -ом выходе 12 первого дешифратора 3 , можно эайисать в следующем виде2 =О чама ч .,ма уа лал,ла а для определения сигнала на 1-ом выходе )-го дешифратора 3, исходя из метода математической индукции, можно записать следующую логическую функцию1".:а,.ала, л,ла"ма Ла л вй" (1) Равенство 1. =1 является достаточным условием, но не необходимым для определения, что в регистре 2 может быть минимальное число, т.е. дешифратором 3 выделяются регистры 2, в которых символы а равны, О.Первым, определяющим состояние )-го выхода 23 -го блока сравнения 4;, является событие; чему равно состояние -го выхода 23 1(-1) узла анализа 4, а для первого узла анализа 4 состояние )-го выхода 23 определяется состоянием )-го выхода 12, первого дешифратора 3, Вторым, определяющим состояние -го выхода 23 1-го узла анализа 4, является событие, определяемое инверсией эк" виваленции двух высказываний Г и некоторой логической функции,а , которая определяется выражением.чаПричем К; всегда равно нулю, если Глибо а , либо одна из (о) дйзъюнкций, входящий в коньюк- тивнО нормальную форму, равны нулю.Функцию Г, определяющую состояние 3-го выхода -го блока сравнениявходу -го элемента И пятой группыи через 1-й элемент НЕ второй группык первому входу 1-го элемента ИЛИвторой группы, второй вход которогосоединен с выходом" -го элемента Ипервой группы, выход каждого 1-гоэлемента ИЛИ второй группы подключен к соответствуюцему входу элемента И второй группы, выход каждого1-го элемента И второй группы соединен со вторым входом -го элемента И четвертой группы и через -й элемент НЕ третьей группы - со вторым входом 1-го элемента И третьей группы.Источники информации,5 принятые во внимание при экспертизе 1 Авторское свидетельство СССР М 628486, кл. С Об Г 7/02, 1978. 2. Авторское свидетельство СССР Р 620976, кл. 6 06 Г 7/02, 1978 (проО тотип)./68 , Тираж.731 ВНИИПИ Государственногпо делаи изобретени 13035, Москва, Е, Ра Подписноета СССРрытий .аб д.4/5