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

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик

»»»»981987 (61) Дополнительное к авт. свид-ву(22) Заявлено 200381 (2») 3262048/18-24 (54) М. Кл.з

G 06 F 7/02 сприсоединениемзеявки М(23) ПриоритетГосударствеииый комитет

СССР ио делам изобретений и .открытий ($3) УДК 681.325..5»088.8) Опубликовано 15,12.82. бюллетень»»о 46

Дата опубликования описания 151282

» и г

Ф

В. ?(. Финаев и В.A. Креков; „

l;

I, »

Таганрогский радиотехнический институт им. В.-Д. Калмыкова (72) Авторы изобретения (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНОГО

ЧИСЛА

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

Известно устройство для сравнения двоичных чисел, содержащее блоки срав- 0 нения, число которых равно числу разрядов сравниваемых кодовых комбинаций, элементы ИЛИ-НЕ и И-НЕ, первый и второй элементы НЕ, причем с первьпМи входами блоков сравнения соединены первые входные шины пряглого кода первого числа, со вторыми входами соединены вторые входные шины прямого кода второго числа, с третьими входами — третьи входные шины инверсного кода первого числа, с четвертыми входами — четвертые входные шины инверсного кода второго числа соответственно, первые выходы каждого блока сравнения, кроме последнего, соединены с пятыми входами последующего блока сравнения, вторые выходи блоков сравнения соединены со входами элемента ИЛИ-НЕ, первый выход последнего блока сравнения соединен с первой выходной 30 шиной устройства, а третий выход последнего блока сравнения соединен с первым входом элемента И-НЕ, второй вход которого соединен с выходом первого элемента НЕ, а выход — через второй элемент НЕ соединен со второй выходной шиной устройства, третья выходная шина которого соединена с выходом элемента ИЛИ-HE и со входом первого элемента HE (1) .

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

Наиболее близкигл к изобретению является устройство для сравнения и двоичных .чисел, содержащее регистры, первые, вторые и третьи элементы И, триггера, блоки сравнения, элементы ИЛИ н НЕ, причегл первая входная шина соединена с нервами входами регистров, первые выходы которых соединены с первыми входами соответствующих первых элементов И, вторые входы которых соединены со вторыми выходам» и входами соответ981987 ствующих регистров, третьи входы соединены со второй входной управлявшей шиной и первым входом третьего элемента И, а выходы — с первыми входами соответствуюших вторых элементов И, вторые входы которых соеди- 5 нены с выходами соответствуюших триггеров, а выходы — со входами элемента ИЛЙ, выход которого соединен со вторым входом третьего элемента И, входом элемента HE и первыми входа- 10 ми блоков сравнения, вторые входы которых соединены с третьей входной управляюцей шиной, а выходы — с первыии входами соответствующих триггеров, вторые входы которых соединены 15 с четвертой входной управляюцей шиной,. а выходная шина устройства соединена с выходом третьего элемента

И, третий вход которого соединен с, выходом элемента HE (21 . . .®

Недостаток известного устройства состоит в следующем. Процесс сравне- ния двух чисел определяется подачей управляюших сигналов по второй, третьей и четвертой входным. управляю- 5 шим шинам, т.е. затрачивается допол-нительно время на процесс анализа и процесс управления. Кроме того, информация в регистры вводйтся пос,ледовательно, что также уменьшает 30 процесс быстродействия устройства °

Таким образом недостаток известного устройства заключается в его низком быстродействии.

Целью изобретения является повы- 35 шение быстродействия.

Указанная цель достигается тем, что в устройство для определения экстремального числа, содержащее и. регистров, и групп элементов И, где 40

n — количество сравниваемых чисел, (К-1) узлов анализа, где К - число разрядов в сравниваемых числах,причем каждый i-ый прямой выход каждого J-ro регистра, где i=1,2,. ..n 45

)=1,2,...К соединен с перьми входом

i-ro элемента И j-ой группы, i-ым входом первой группы j-oro узла анализа, введено К дешифраторов, каждые

i-ые прямой .и инверсный выходы каждого J-ro регистра соединены с I-ыми входами первой и второй групп соответственно J-oro дешнфратора, каждый

i-ый выход каждого 1-го дейифратора, где l=2 3,. ° .Ê подключен к i-ому входу второй группы входов (I-1)-го узла анализа, каждый i-ый выход каждого а-го узла анализа,. где

m=1,2,...(K-2) соединен .с I-ым входом третьей группы (m+1)-го узла анализа, каждый i-ый выход первого де- 60 шифратора подключен к i-ому входу третьей группы первого узла анализа, а каждый i-ый выход (К-1)-ro узла анализа соединен со вторыми входами элементов И i-ой группы и, б5 тем, что дешифраторы состоят иэ элементов И, группы элементов ИЛИ, причем каждый i-ый вход первой и второй групп входов дешифратора соединен с

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

1-ый вход третьей группы входов узла подключен ко второму входу i-го элемента И первой группы, ко. второму входу i-го элемента И второй группы, ко второму входу i-ro элемента И пятой группы и через i-ый элемент

НЕ второй группы — к первому входу

i-ro элемента ИЛИ второй группы, второй вход которого соединен с выходом

t-го элемента И первой группы, выход каждого i-го элемента ИЛИ второй группы подключен к соответствуюшему входу элемента И второй группы, выход каждого i-го элемента И второй группы соединен со вторым входом i-го элемента И четвертой группы и через

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

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

Устройство сорерлут входные шины

1 1 ° ° ° 1 11 t 1ф t ° ° ° 1

1 % °

1", 1", .: 1, регистры 2, 2,...2„, а дешифраторы 3, 3, ... 3,, узлы анализа 4, 4 ° ..- 4к„4, группы элементов И 5, 5, .;. „, 5

Я

° ° ° 5к ° ° " " ° ..к

1 e e вйходные шийы устройства 6„ 6 бп б бп б б б

Каждый дешифратор 3 содержит входы 7 и 8, элементы И 9 и 10, группу

Э 81987

55

65 элементов ИЛИ 11.„, 11, .;. 11„, выходы 12 q, 12, ...12п. Каждый Узел анализа состоит иэ групп элементов

И 13 и 14, группы входов узла 15, группы элементов HE 16, группы элементов. И 17, группы элементов НЕ 18, группы элементов И 19, группы элементов HE 20, группы элементов И 21, группы элементов ИЛИ 22, группы выходов узла 23, группы элементов ..

ИЛИ 24.

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

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

Причем каждая i-ая кодовая комбинация подается по входным шинам 11- 1п в соответствуищий регистр 2„.. Кодовые комбинации записываются в ячейки регистра 2 - 2п по входным шинам

1 1- 1п параллельно во времени, но последовательно по разрядам, т.е. вначале будут одновременно поданы и ульсы по входны4 .Нам 1!.11. 19, Я

1, затем по входным шийам

7 2

1, 1, 1>, ... 1д и т.д. до завершающей подачи импульсов кодовых комбинаций по входным шинам к к к

1„, 1, 1> ° 1„где К вЂ” число разрядов сравниваемых по величине и кодовых комбинаций. Пафаллельнопоследовательной записью кодовых комбинаций в регистры 2 обеспечи- вается последовательное срабатывание во времени дешифраторов состояний 34- Зк и узлов анализа

41- 4и- °

АлгОритм работы устройства выбора минимального кода состоит в последовательном анализе параллельных (одноименных) разрядов кодовых комбинаций, записанных в регистры

21 в 2 > с последовательным выявлением больших по величинам кодов в параллельных (одноименных) разрядах, начиная со старшего разряда вплоть до младшего. Причем анализ параллельных разрядов кодовых комбинаций регистров 2 производится как дешифраторами состояний 3 - Зк, так и узлами, анализа 4 - 4„ g но выявление кодовых комбинаций, меньших по величине чем наибольшее, производится первым дешифратором состояний 31 и узлами анализа 4а- 4» 4 причем последний узел анализа 4» „ выявляет минимальные (одну или несколько) кодовые комбинации из и записанных в регистры 2.

Сущность алгоритма работы устройства выбора минимального кода состоит в следующем. Вначале рассмотрим параллельные старшие разряды. а -а " ф ф регистров 2. Очевидно здесь возможны следующие события. Символы всех разI рядов а - а 1 равны нулю, символы всех разрядов à„- -а, равны единице, либо имеются символы равные нулю и единице. В первых двух случаях на выходах 12„- 12„ дешифратора 3 должи ны быть единичные потенциалы, а в третьем случае, единичные потенциалы должны быть на тех выходах 12 - 12а, которые соответствуют по верхнему индексу регистрам 2 в старшие ячейки которых а - ап записаны нулевые знаи

4 чения разрядов кодов, т.е. для рассматриваемого примера с восемью ре-. гистрами, единичный потенциал будет на выходах 12„, 12 « 12„, 12, 12, 121, логическую фуйкцию, которая

7 определяет сигнал на i-ом выходе

12 первого дешифратора 3, можно эайисать в следующем виде

1". аа,ua"„ча ч.„ча",ча, л5„n„, лап, а для определения сигнала íà i-oM выходе j-го дешифратора 3, исходя из метода математической индукции, можно записать следующую логическую функцию f =5 ua na n...ëà"uà nà n...nd (}

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

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

j-го выхода 23 i-ro блока сравне9 ния 4 ;, является событие: чему равно состояние j-ro выхода 23 (i-1) узла

3, анализа 4<, а для первого узла анализа 4< состояние )-го выхода 23s определяется состоянием j-ro выхода

12, первого дешифратора 3 . Вторым, определяющим состояние j-го выхода

23 i-го узла анализа 4, является событие, определяемое инверсией эквиваленции двух высказываний f и некоторой логической функции,d,, которая определяется выражением (2 л(Г! ча,, 1л Т!"„ча „Jл„,л(р,",va"„1

Причем а.; всегда равно нулю, если F„„ H6o a„ „, либо одна из (n-1) дйзъюнкций, входящий в коньюктивнО нормальную форму, равны нулю.

Функцию FI, определяющую состояние j ro выхода i-ro блока сравнения

981987

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

4; (ноль или единицу на выходе 23 ) записывается в виде

FÄ = F, „л (f, с ч f,. а<,, j (З) из уравнения (1), (2) и (3) следует, что F всегда равно. нулю, если либо

Г>, либо F, либо F и т.д. до F, л равны нулю.

Функции (1), (2) и,(3) являются минимальныии формами и построенные согласно данных функций схемы дешифраторов состояний 3 — 3„ и узлов анал лиза 41- 4 < л не облада.эт избыточностью.

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

Если оценивать быстродействие предлагаемого устройства исходя из синхронизирующих тактов, то время, необходислое для анализа содержимого регистров 2 и выбора минимального кода, равно ТВд «1<° . с» где К - число разрядов кода; с» — элеслентарный такт синхронизации.

При записи символов а, - а"„, сра1 батывает первый дешифратор 3,, при записи и символов:а - а" — срабатыс вают второй дешифратор З и первый узел анализа 4» и т.д., а при записи символов а - а" кодов в регистры 2

» к срабатывают дешифратор 3„ и узел анализа 4 к.», т.е. закончится процесс выбора минимального кода.

В известных устройствах затрачивается время на предварительную запись кодов в регистры .Т» =kt, на подачу управляющих сигналов по Первой, второй и третьей управляющим шинам

Т дополнительной последующей подаче синхронизирующих сигналов по входной не Т причем тогда время выбора минимального кода в известном устройстве Т и -Т +Т2+Т =

=5 1<с».

Следовательно, быстродействие предлагаемого устройства как минимум

Т у в пять раз выше. известных Э= - -"--5, ТВП

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

1. Устройство для определения экстремального числа, содержащее и регистров, и групп элементов И, гле п — количество сравниваемых чисел,(k-1) узлов анализа, где k — число разрядов в сравниваемых числах, причем каждый i-й прямой выход каж дого j-го регистра, где i 1,2,...n, j=1,2, ..., k, соединен с первым входом i-го элемента И j-й группы, i-ым входом первой группы j-го узла анализа, отличающее с я тем, что» с целью повышения быстродействия, в него введено 1< дешифра10 торов, каждые. i-e прямой и инверсный выходы каждого j-го регистра соединены с i-ми входасли первой и второй групп соответственно j-го дещифратора, каждый i-й выход каждого 1-го дешифратора, где i=2,3, ..., k под15 ключен к i ìó входу второй группы входов (1-1)-го узла анализа, каждый

i-й выход ка><дого е-ro узла анализа, где m12, ... (k2) соединен с

i-м входом третьей группы (m+1)-ro

20 узла анализа, каждый i-й выход первого дещифратора подключен к i-му входу третьей группы, первого узла анализа, а каждый i-й выход (k-1)-ro узла анализа соединен со вторыми

Я5 входами элементов И i é группы.

2. Устройство по п.1, о т л и ч а ю щ е е с я тем, что в нем дешифраторы состоят из элементов И, группы элементов ИЛИ, причем каждый

i-й вход первой и второй групп входов дешифратора соединен с i-м входои первого и второго элементов И соответственно, выход первого и второго элементов И подключен к первому и второму входам соответственно элеслентов ИЛИ группы, каждый i-й вход второй группы входов дешифратора соединен с третьим входом 1-го элемента ИЛИ группы, выход каждого

i-ro элемента ИЛИ подключен к i-му

40 выходу дешифратора.

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

И первой и второй групп, каждый

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

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

I, группы, ко второму входу i-го элемента И второй группы, 1<О второму

981987

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

i-го элемента И -второй группы соединен со вторым входом i-ro элемента

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

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

1. Авторское свидетельство СССР

9 628486, кл. G .06 Г:7/02, 1978.

2. Авторское свидетельство СССР

Р 620976, кл. G 06 F 7/02, 1978 (про-!

О тотип).

981987

12

Составитель В. Велкин

Редактор М. Товтин, Техред A.Áàáèíåö Корректор Н. Король

Заказ 9712/68 . Тираж.731 Подписное

ВНИИПИ Государственного ксвентета СССР по делаи изобретений и открытий

113035, Москва, й-35, Раушская наб., д. 4/5

Филиал ППП "Патент", г. Ужгород, ул. Проектная,. 4