Устройство для определения экстремального числа Советский патент 1982 года по МПК G06F7/02 

(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕШЕНИЯ ЭКСТРЕМАЛЬНОГО

ЧИСЛА

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

Известно устройство для сравнения двоичных чисел, содержащее блоки сравнения,, число которых равно числу разрядов сравниваемых кодовых комбинаций, элементы ИЛИ-НЕ и И-НЕ, первый и второй элементы НЕ, причем с первы1 «и входа ш блоков сравнения соединены первые входные шины прямого кода первого числа, со вторыми входами соединены вторые входные ишны прямого кода второго числа, с третьими входаг.ш - третьи входные шины инверсного кода первого числа, с четвертыми входагли - четвертые входные цшны инверсного кода второго числа соответственно, первые выходы каждого блока сравнения, кроме последнего, соединены с пятыг-м входами последующего блока сравнения, вторые выходы блоков сравнения соединены со входами элемента ИЛИ-НЕ, первый выход последнего блока сравнения соединен с первой вы5|одной

шиной устройства, а третий выход последнего блока сравнения соединен с первым входом элемента И-НЕ, второй вход которого соединен с выходом первого элемента НЕ, а выход - через второй элемент НЕ соединен со второй выходной шиной устройства, третья выходная шина которого соединена с выходом элемента ИЛИ-НЕ и со входом первого элемента НЕ l3 .

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

Наиболее близким к изобретению

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

25 входная шина соединена с первыми входами регистров, первые выходы которых соединены с пepвыIvШ входами соответствующих первых элементов И, вторые входы которых соединены со

30 вторыми выходаг-1и и вхояа}ля соответствующих региЬтров, третьи входы соединены со второй входной управля щей Ешной и первыг- входом третьего элемента И, а выходы - с первыми входаг соответствующих вторых элементов И, вторые входы которых соед йены с выходаг-га соответствукяцих три геров, а выходы - со входами элемен та ИЛИ, выход которого соединен со вторыгл входом третьего элемента И, входом элемента НЕ и первыми входами блоков сравнения, вторые входУ которых соединены с третьей входной управляющей шиной, а выходы - с пер выг-ш входами соответсувуквдих тригге ров, вторые входы которых соединены с четвертой входной управляющей шиной,, а выходная шина устройства соединена с выходом третьего элемента И, третий вход которого соединен с выходом элемента НЕ 23 . . Недостаток известного устройства состоит в следуквдем. Процесс сравне НИН двух чисел определяется подачей управляющих сигналов по второй, .третьей и Четвертой входным, управля щим шинам, т.е. затрачивается допол нительно время на процесс анализа и процесс управления. Кроме того, информация в регистры вводится пос,ледовательно, что также уменьшает процесс быстродействия устрс ства. Таким образом недостаток известного устройства заключается в его низком быстродействии. Целью изобретения является повышение быстродействия. Указанная цель достигается тем, Что в устройство для охфеделения экстремального числа, содержащее п. регистров, п групп элементов И, где п - количество сравниваемых чисел, (К-1) узлов анализа, где К - число разрядов в сравниваемых числах,причем каждый i-ый прямой выход каходого J-ro регистра, где ,2,...n, ,2,...K соединен с перыдм входом 1-го элемента И j-ой группы, 1-ым входом первой группы j-pro узла ана лиза, введено К дешифраторов, кажды i-ые прямой ,и инверсный выходы каждого J -го регистра соединены с 1 входами первой и второй групп соответственно j-oro дешифратора, кажды 1-ый выход каиедого 1-го деи1ифратора где ,3,...К подключен к 1-ому входу второй группы входов (-1)-го узла анализа, каждый t-ый выход каждого т-го узла анализа, где ,2,...(К-2) с J-ым входом третьей группы (т+1)-го узла ан лиза, каждый i-ый выход первого дешифратора подключен к 1-ому входу третьей группы первого узла анализа, а каждый t-ый выход (К-1)-го узла анализа соединен со вторыми входами элементов И i-ой группы и тем, что дешифраторы состоят из элементов И, группы элементов ИЛИ, причем каждый i-ый вход первой и второй групп входов дешифратора соединен с i-ым входом первого и второго элементов И соответственно, выходы первого и вторбго элементов И подключены к первому и второму входам соответственно элементов ИЛИ группы, каждый i-ый вход второй группы входов дешифратора соединен с третьим, входом i-ro элемента ИЛИ группы, выход каждого i-ro элемента ИЛИ подключен к i-oMV выходу дешифратора, а так же тем, что в нем каждый узел анализа содержит группы эле /1ентов НЕ, И, ИЛИ, причем каждый i-ый вход, первой группы входов узла соединен с первым входом i-ro элемента И первой и второй групп, каждый t-ый вход второй группы входов узла подключен к первоглу входу i-ro элемента И третьей группы и через i-ый элемент НЕ - к первому входу i-го элемента И четвертой группы, выход каждого i-ro элемента И третьей и четвертой групп соединен с первым и вторым входом соответственно i-ro элемента ИЛИ первой группы, выход каждого i-ro элемента ИЛИ первой группы подключен к первому входу i-ro элемента И пятой группы, выход каждого из. которых соединен с i-ыгл выходом узла, каждый f-ый вход третьей группы входов узла подключен ко второму входу i-ro элемента И первой группы, ко второму входу i-ro элемента И второй группы, ко второглу входу i-ro элемента И группы и через i-ый элемент НЕ второй группы - к первому входу . i-ro эле1-1ента ИЛИ второй группы, второй вход которого соединен с выходом 1-го элемента И первой группы, выход каждого 1-го элемента ИЛИ второй группы подключен к соответствующему входу элемента И второй группы, выход каждого i-ro элемента И второй группы соединен со вторым входом i-ro элемента И четвертой группы и через i-ый элемент НЕ третьей группы - со вторым взсодом i-ro элемента И третьей группы. На фиг. 1 приведена блок-схема устройства; на фиг. 2 - функциональная схема дешифратора; на фиг. 3 функциональная схема каждого из блоков сравнения. Устройство содерям входные айны 1 1 1.1 1 lJLj , , . . . Д-К -Ill / J-J f X 1 , 1, ... , регистры 2, 22,...2n, дешифраторы 3, ... 3, узлы 4ii, группы элеанализа 4, 4 ментов И 51 , 5 2 г f . Л f л сН Э , -З-, ... L .9« , . . . 3(4 , ... к .чл f -J и выходные шины устройства Ь, б1,... x-f f-i сЧ /г2 сП сП и ч к л 2 ...О|, .. О;,, О, ...0ц. Каждый дешифратор 3 содержит входы 7 и 8, элементы И 9 и 10, группу

элементов ИЛИ 11, 11, ,;, выходы 12 tf, 122, 12f,. Каждай узе анализа состоит из групп элементов И 13 и 14, группы входов узла 15, группы элементов НЕ 16, группы элементов. И 17, группы элементов НЕ 18 группы элементов И 19, группы элеметов НЕ 20, группы элементов И 21, группы элементов ИЛИ 22, группы выходов узла 23, группы элементов ИЛИ 24.

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

По входным шинам 1 ; 1 j, поступае п кодовых комбинаций, -из которых устройство выбора минимального кода должно выбрать минимальную по величине .кодовую комбинацию, причем, если в поступающих по входам l,- Ifj кодах имеется р одинаковых по величине и минимальных среди п кодовых комбинаций, то данный случай также должен быть распознан предлагаемым устройством выбора минимального код Причем каждая i-ая кодовая комбинация подается по входным шинам l в соответствующий регистр 2. Кодовые комбинации записываиотся в ячейки регистра 2f по входным шинам Ij- IY параллельно во времени, но последовательно по разрядам, т.е. вначале будут одновременно поданы , импульсы по входныг/1 шина 1,1, 1 ... In, затем по входным шинам Ц, Ц, 1, ... 1„ и т.д. до завершаг тей подачи импульсов кодовых комбинаций по входным шинам

llj, 1$ г In Я К - число разрядов сравниваемых по величине п кодовых комбинаций. Параллельнопоследовательной записью кодовых комбинаций в регистры 2 обеспечивается последовательное срабатывание во времени дешифраторов состояний 3j- 3|с и узлов анализа

4i- 4«-f .

Алгоритм работы устройства выбора минимального кода состоит в последовательном -анализе параллельных (одноименных) разрядов кодовых комбинаций, записанных в регистры 2 и с последовательным выявлением больших по величинам кодов в параллельных (одноименных) разрядах начиная со старшего разряда вплоть до младшего. Причем анашиз парашлелных разрядов кодовых комбинаций регистров 2 производится как дешифраторами состояний 3j;, так и узлами. анализа 4,с. , но выявление кодовых комбинаций, меньших по величине чем наибольшее, производится первыг дешифратором состояний 3i и узлами анализа 4к- , причем последний узел анешиза 4j(. выявляет минимальные (одну или несколько) кодовые комбинации из п, записанных в регистры 2.

Сущность алгоритма работы устройства выбора минимального кода состоит в следующем. Вначале рассмотрим параллельные старшие разряды aj-аJ регистров 2. Очевидно здесь возможны

следующие события. Символы всех разрядов а равны нулю, символы всех разрядов aj равны единице, либо имеются символы равные нулю и единице. В первых двух случаях на выходах 12,,- 12j деихифратора 3 должны быть единичные потенциалы, а в третьем случае, единичные потенциалы должны быть на тех выходах 12, которые соответствуют по верхнему

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

на выходах 12, 12, 12, 12, 12, 12, логическую функцию, которая определяет сигнал на i-ом выходе 12 первого дешифратора 3, можно записать в следующем виде

...va a;Aa2A.,.Aa:;,

а для определения сигнала на 1-ом выходе j-ro дешифратора 3, исходя из метода математической индукции, можно записать следующую логическую функцию

ijsa-vaj-Aa A..,Aa vajA5 A..,AQ ()

Равенство f;; 1 является достаточным условием, но не необходим( для определения, что в регистре 2 может быть минимальное число, т.е. дешифратором 3 выделяются регистры 2, в которых символы а. равны,О.

Первыл, определяющим состояние

j-ro выхода 23 i-ro блока сравнения 4, является событие: чему равно состояние j-ro выхода 23у( i-1) узла анализа 4, а для первого узла анализа 4 состояние j-ro выхода 23, определяется состоянием j-ro выхода 12{ первого дешифратора 3. Вторым, определяющим состояние j-ro выхода 23J i-ro узла анализа 4, является

событие, определяемое инверсией эквиваленции двух высказываний f/ и

J некоторой логической функции. /

которая определяется выражением ,lЛ- fl ..}

U)

« ft ;: «N- a :;i--if:.-r.

причем ot,- всегда равно нулю, если f либо , либо одна из (п-1) дизъюнкций, входящий в коныэктивнО нормальную форму, равны нулю. Функцию FJ , определяющую состояние j-ro выхода i-ro блока сравнения 4 (ноль или единицу на выходе 23) записывается в виде i bF liivljc. (г) из уравнения (1), (2) и (3) следуе что FJ всегда равно.нулю, если либ либо f , либо FJ , либо F и т.д. до F равны нулю. Функции (1), (2) и,(3) являются минимальнш1и формами и построенные согласно данных функций схеми дешиф раторов состояний 3 - н узлов ан лиза ,. не обладают избыточностью. Технико-экономическую эффективность предлагаемого устройства выбо ра минимального кода возможно оценить следующим образом. Если оценивать быстродействие предлагаемого устройства исходя из синхронизирующих тактов, то время, необходимое для анализа содержимого регистров 2 и выбора минимального кода, равно Tg(, k-t, где К - число разрядов кода; t - элементарный такт синхронизации. При записи символов а батывает первый дешифратор 3/, при - яП срабатызаписи и СИМВОЛОВ:а 2 °г вают второй деишфратор 32 и первый узел анализа 4 и т.д., а при запис л кодов в регистры 2 символов а срабатывают деишфратор 3, и узел анализа . , т.е. закончится проце выбора минимального кода. В известных устройствах затрачивается время на предварительную запись кодов в регистры-Т kt, на подачу управляющих сигналов по второй и третьей управляющим шинам Т дополнительной последующей подач синхронизирующих сигналов по входно шине Tj , а Т тогда время выбора минимального код в известном устройстве Т„ .,+Тз 5 ktiСледовательно, быстродействие предлагаемого устройства как в пять раз выше, известных Э , Следует отметить, что, если в ре гистры 2 записать инверсные значения анализ ИРУ кодов, то предлагаемое устройство будет осуществлят выбор максимальной по значению кодо вой комбинации. Форг- ла изобретения 1. Устройство для определения экстремального числа, содержшцее п регистров, п rtvnn элементов И, гле п - количество сравниваемых чисел, (k-J) УЗ.ПОВ анализа, где k - чи ло разрядов в сравниваемых числах, причем кансдый 1-й прямой выход каж-дого j-ro регистра, где i-l,2,...n, ,2, ..., k, соединен с первыгл входом i-ro элемента Н j-й группы, i-ым входом первой группы j-ro узла анализа, отличаю 171ееся тем, что/ с целью повышения быстродействия, в него введено k дешифраторов, каждые.i-e прямой и инверсный выходы каждого j-ro регистра соединены с i-ми входги и первой и второй групп соответственно j-ro дешифратора, каясдый i-й выход кахуцого 1-го дешифратора, где ,3, ..., k подключен к i-му входу второй группы входов (l-l)-ro узла анализа , каждый i-й выход кахшого т-го узла анализа, где ,2, ... (k-2) соединен с i-M входом третьей группы (т+1)-го узла анализа, каждый f-й выход первого дешифратора подключен к i-му входу третьей группы первого узла анализа, а каждый i-й выход (k-l)-ro узла анализа соединен со втopы Ш входами элементов И I-и группы. 2. Устройство по п.1, отличающееся тем, что в нем дешифраторы состоят из элементов И группы элементов ИЛИ, причем каящый i-й вход первой и второй групп входов дешифратора соединен с I-м входом первого и второго элементов И соответственно, выход первого и второго элементов И подключен к первому и второму входам соответственно элементов ИЛИ группы, каждый i-й вход второй группы входов дешифратора соединён с тр,етьим входом i-ro элемента ИЛИ группы, выход каждого i-ro элемента ИЛИ подключен к i-му выходу дешифратора. 3. Устройство по П.1, отличающееся тем, что в нем каждый узел анализа содержит группы элементов НЕ, И, ИЛИ, причем каждый i-й вход первой группы входов узла соединен с перзъал входом i-ro элемента И первой и второй групп, каждый i-й вход второй группы входов узла подключен к первому входу i-ro элемента И третьей группы и через i-й элемент НЕ - к первому входу i-ro элемента И четвертой группы, выход каждого i-ro элемента И третьей и четвертой групп соединен с первым и вторым входом соответственно i-го элемента ИЛИ первой группы, выход кахадого i-ro элемента ИЛИ первой группы подключен к первому входу i-ro элемента И пятой группы, выход каждого из которых соединен с 1-м выходом узла, каждый i-й вход третьей группы входов узла подключен ко второму входу i-ro элемента И первой группы, ко второму входу i-ro элемента И второй группы, ко второму

входу i-го элемента И пятой группы и через 1-й элемент НЕ второп группы к первому входу -го элемента ИЛИ второй группы, второй нход которого соединен с выходом i-ro элемента Н первой группы, выход каждого i-ro элемента ИЛИ второй группы подключен к соответствующему входу элемента И второй группы, выход каждого i-ro элемента И второй- группы соединен со вторым входом i-ro элемента

й fi2 я й с С с и с К /f

0| Oj 0 Of 02 69 02 Ьг Of on. Of, Ьп

И четвертой группы и через i-й элемент НЕ третьей группы - со вторым входом i-ro элемента И третьей группы.

Источники информации, принятые во внимание при экспертизе

0 A A- - jj Й ЙГ -.. jjf Л ,- 9

«f l лУ 1 « f 1 1 l / /

fj / 1 /, fg /2 t It n Л