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

 

УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНОГО ИЗ П ЧИСЕЛ, содержащее регистры, дешифраторы, регистр результата, группы элементов И, ИЛИ блок анализа, включающий П элементов ИЛИ и m поразрядных узлов анализа , где тчисло.разрядов анализируемых чисел, каждый к-й поразрядный узел анализа, где k 1,2, ...,(п)-1), содержит и элементов И, Ц элементов НЕ и многовходовый элемент И, im -и поразрядный узел анализа включает п элементов И и (П-1) элементов НЕ, причем поразрядном узле анализа,i -и вход поразрядного узла анализа, где 1,2,...,п, подключен к -му информационному входу i -го элемента И и через 1 -ый элемент НЕ - к (+1)-ым информационным входам элементов И с (i + 1)-ro поп -Ь1й и к 1-ому входу многовходового элемента И, выход которого подключен к управляющим входам элементов И (Х+1)-го поразрядного узла анализа , в первом поразрядном узле ана лиза управляющие входы элементов И подключены к выходу первого элемента НЕ, каждый О-и вход №-го поразрядного узла анализа, где р - 1,2, ,(ц-1), соединен с первым информацион1 ым входом р -го элемента И и через р-и элемент НЕ соединен с (р+1)-ым информационным входом элементов И с (р + 1)-го пор -ый, rti-й вход поразрядного узла анализа подключен к

СОЮЗ СО8ЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (19) (11) (S1)4 G 06 Р 7/06

ОПИСАНИЕ ИЗОБРЕТ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ. ГОСУДАРСТ8ЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3703940/24-24 (22) 23.02.84 (46) 07.08.85. Бюл. Р 29 (72) В.Г. Попов (53) 681.323 (088.8) (56) Авторское свидетельство СССР

1(- 664170, кл. G 06 F 7/02, 1976.

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

Р 903864, кл. G 06 F 7/06, 1980. (54)(57) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

ЭКСТРЕМАЛЬНОГО ИЗ П ЧИСЕЛ, содержащее регистры, дешифраторы, регистр результата, группы элементов И, ИЛИ блок анализа, включающий r1 элементов ИЛИ и m поразрядных узлов анализа, где e — число разрядов анализируемых чисел, каждый к-й поразрядный узел анализа, где k = 1,2, ...,(щ-1), содержит 11 элементов И, 11 элементов HE и многовходовый элемент И, Ф -й поразрядный узел анализа включает 11 элементов И и (11-1) Элементов НЕ, причем в 1 -ом поразрядном узле анализа,1 -й вход поразрядного узла анализа, где

1,2,...,ll, подключен к 1 -му информационному входу -го элеменI та И и через i -ый элемент НŠ— к (1+1)-ым информационным входам элементов И с (+1)-ro no ll -ый и к

1-ому входу многовходового элемента И, выход которого подключен к управляющим входам элементов И (1+1)-ro поразрядного узла анализа, в первом поразрядном узле анализа управляющие входы элементов И подключены к выходу первого элемента НЕ, каждый f -й вход Э-го поразрядного узла анализа, где P = 1,2, ...,(l1 1), соединен с первым информационным входом Р --го элемента И и через Р -й элемент НЕ соединен с (p+1)-ûM информационным входом элементов И с (P+1)-го по р -ый, п1-й вход поразрядного узла анализа подключен к (щ+1)-му информационному входу поразрядного 11 -го элемента И, выход 1 -ro элемента И g -го поразрядного узла анализа подключен к 1с -му входу i --ro разрядного элемента ИЛИ, выход > -го элемента

И п1-го поразрядного узла анализа подключен xm -му входу 1 --го элемента ИЛИ, выход которого является

1-ым выходом блока анализа и соединен с учравляющими входами элементов И i --ой группы, информационные входы которых соединены с соответствующими выходами.< -ro регистра, входы которого соединены с входами 1 -го числа устройства, выходы элеI ментов И 1 -ой группы подключены к входам соответствующих элементов

ИЛИ группы, выходы которых соединены с входами регистра результата, выходы которого являются выходами .устройства, первая группа выходов каждого 1 -го регистра соединена с входами i -го дешифратора, о т л и— ч а ю щ е е с я тем, что, с целью уменьшения аппаратных затрат с увеличением разрядности анализируемь1х чисел, устройство дополнительно содержит 11-групп дешифраторов по (t -1) дешифратору в каждой, где

à — число .групп анализируемых разрядов, (г -1) групп элементов И переноса по П элементов И переноса в каждой; (l -1) блоков управления пере1177779 носом и (г — 1) блоков переноса, .каждый блок переноса содержит (5-1) элементов И, где < — число выходов дешифратора, (5-1) элементов НЕ и элементов ИЛИ, причем выход (3-ro элемента ИЛИ, где /3 = 1,2,..., (6 -1), соединен через/3 -й элемент

НЕ с Р -ым управляющим входом элементов И с tI-ro по (5-1)-ый, выход

f-ro элемента ИЛИ, где 3 = 2,3,...,6 соединен с информационным входом (4-1) элемента И,. каждый блок управления переносом содержит элемент

ИЛИ-НЕ, A элементов ИЛИ и 5 групп элементов И по << элементов в каждой причем выходы < -ых элементов И всех групп подключены к информационным входам < -ro элемента ИЛИ, (и+1)-е входы всех элементов ИЛИ соединены с выходом элемента ИЛИ-НЕ, 4 --й выход < -ro дешифратора < -ой группы, где < = 1,2,...,,, соединен с < -ым входом t --го элемента ИЛИ (Г-1)-ro блока переноса и информационными входами< -ых элементов И всех групп (Г-1)-го блока управления переносом, 1

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

Цель изобретения — уменьшение аппаратных затрат с увеличением разрядности анализируемых чисел.

На фиг. 1 показана структурная схема предлагаемого устройства; на фиг. 2 — то же, блока управления переносом; на фиг. 3 — то же, блока анализа; на фиг. 4 — то же, блока !5 переноса.

Устройство (фиг.1) содержит регистры 1<<<,...,1<.. группы дешифраторов

2«,. ° .,21,„,...,2„, блоки 3 <,..., 3„, управления переносом, группы 20

I элементов И 4,...,4„„, блок 5 ана-, лиза, блоки 6,..., 6> < переноса, группы элементов И 7„,...,7<,, групуправляющие входы элементов И -ой группы 2 -го блока управления переносом, где = 1,2,...,(г -1), соединены с выходами ($-1)-го элемента И

Z-ro блока переноса, управляющие входы элементов И первой группы Z -го блока управления переносом подключены к выходу первого элемента ИЛИ

Z-ro блока переноса, выходы 2 --ro дешифратора < -ой группы соединены

Ф с информационными входами < --ro элемента И переноса2 -ой группы и с информационными входами < -ых элементов И всех групп (g-1)-го блока управления переносом, управляющий

I вход < --го элемента И переноса Z -ой группы подключен к выходу < -го элемента ИЛИЕ -ro блока управления пе% реносом, выход < -ro элемента И переноса Ч -ой группы, где Ч = 2,3,..., (< -1), подключен к информационным входам < -ых элементов И всех групп (V-1)-ro блока переноса, выход < -ro элемента И переноса первой группы подключен к < -му входу поразрядного узла анализа блока анализа. пу элементов ИЛИ 8, регистр 9 результата, входы 10<,...,10, устрой- ства, входы 11<,...,11« регистров 1, выходы 12<<,...,12 «ä дешифраторов

2, выходы 131,...,13,, блоков 6 переноса, выходы 14,,...,14 д,..., 14 г+< блоков 3 управления, выходы

15<,<,..., 15< l, 15<< „ групп элементов И 4, выходы 16<,...,16<, блока 5 анализа, выход 17 устройства.

Блок управления 3 переносом (фиг. 2) содержит группу элементов

ИЛИ 18» ...,18«, группы 19 элементов И 20 и элемент ИЛИ-НЕ 21.

Блок 5 анализа (фиг. 3) содержит

m поразрядных узлов 22 анализа, состоящих из элементов НЕ 23, элементов

И 24, многовходового элемента И 25 и элементов ИЛИ 26.

Блок 6 переноса (фиг. 4) содержит группу элементов ИЛИ 27<,...,27 группу элементов И 28<,...,28 < и группу элементов НЕ 29<,...,29 <

1171779

Определение экстремального из чисел производится на основе анализа распределительных кодов с выходов дешифраторов, на входы которых подаются двоичные коды исходных чисел. 5

Пусть n=4 а разрядность исходных чисел k=4.

При а1= 1100, а = 1111, а = 1010, а = 1011 выходные сигналы дешифратоФ ров при преобразовании этих чисел представлены в табл.1, из которой видно, что при проведении анализа одноименных выходов дешифраторов, начиная с младших по номеру, первая "1" находится в 10-и столбце 15 выходов, т.е. наименьшее число находится в третьем регистре. Кроме того, для определения наименьшего числа необходимо 16 поразрядных узлов анализа., 20

Если разделить разряды регистров на группы, то можно сократить объем оборудования. Разделим разряды исходных чисел на две группы. Для данного случая в табл. 2 приведены сигналы дешифраторов.

Из табл. 2 видно, что во второй группе выходов дешифраторов единицы находятся в третьем столбце. По- ЗР этому наименьшее число определяется анализом выходных сигналов первой группы дешифраторов, причем анализировать необходимо одноименные выходы дешифраторов только третьего и четвертого регистров. Первая единица при этом находится в третьем столбце второй части табл. 2. Та ким образом, наименьшее число находится в третьем регистре. При этом 4р общее число выходов дешифраторов равно 8, а для определения наименьшего числа потребуется четыре поразрядных узла для анализа одноименных выходов дешифраторов группы 45 младших разрядов исходных чисел.

Предыдущие группы разрядов регистров используются для определения тех чисел, у которых "1" имеются в выбранной группе одноименных выходов gp дешифраторов. Так, (табл. 2) в первой группе выходов дешифраторов значения "1" в третьем столбце указывают на р1венство кодов в третьем и четвертом регистрах в этой группе и поэтому окончательное реш:. ние о местонахо:кдении наименьшего числа принимается после анализа одноименных выходов дешифраторов только для третьего и четвертого регистров.

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

Пусть у — число выходов дешифраторов. Тогда для 12-разрядного числа необходимо найти минимальное

Х "2 1 "4 уа 1 е у 2 +2 2+2 +2 4

:> х = 12, причем x ) 2.

Установить численные значения для каждого показателя степени х

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

Например, если х = х = х = х4 = 3

2 3 та у = 4 ° 2 = 32. Если х = 3, 4

Известен принцип разделения регистра на группы разрядов при представлении чисел в ЭВМ с плавающей запятой, когда первая группа разI рядов отводится для представления порядка, а вторая группа разрядов для представления нормализованной мантиссы числа.

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

Результат операции сравнения формируется на основе анализа порядков и мантисс чисел. При равных порядках во внимание принимается результат сравнения мантисс. В ЭВИ выполнение операции вычитания производится с использованием двух сумматоров.

В предлагаемом устройстве разделение регистров на группы разрядов преследует цель сокращения оборудования при определении экст- ремального числа с использованием дешифраторов групп разрядов и комбинационных схем для последовательного анализа одноименных выходов дешифратора последующих групп. В соответствии с этим (фиг. 1) вы- . ходы дешифраторов одноименных групп

РазРядов 2,д,2 „,...,2„., „.2 „p анализируются в блоке 6„ 1 перено - са. Каждый блок 61,...,6„, перено1171779

40 .зультата.

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

Для определения наибольшего числа массив исходных чисел принимается во входные регистры и в обратных 45 кодах. Рассмотрим работу устройства при следующих условиях, Пусть каждый регистр 1 разделен на группы по два разряда в каждой. Предположим, что обратный код массива чис- 50 ла имеет следующий вид:. а1 = 11...00! а = 11... 11,..., а = 11... 11, а„ 10...10, а = 10...11, где все разряды промежуточных чисел и разряды в промежуточных группах ука- 55 ванных чисел содержат единицы.

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

Блок переноса (фиг.2) выполнен по приоритетной схеме, управляемой выходными сигналами элементов ИЛИ

27 и НЕ 29. На выходах 13 блока переноса формируется распределительный код, содержащий либо все

"0", либо "1 на одном из его выходов. Этими сигналами в блоке 3 управления определяются "1" в выделенной группе одноименных разрядов в блоке 6 переноса из сигналов дешифраторов. Выходные сигналы 14 блока 3 управления переносом управляют .передачей на анализ в очередной блок переноса сигналов дешифраторов, выделенных для анализа регистров. Если распределительный код выходных сигналов блока 6 переноса содержит все "0", то все выходные сигналы блока 3 управления равны

"1" за счет элемента ИЛИ-НЕ 21.

При этом в очередной блок 6 переноса передаются на анализ выходные сигналы одноименных дешифраторов 2 всех регистров 1. В конечном итоге в блоке 5 анализа (фиг. 3) в соот ветствующем поразрядном узле 22 анализа, выполненном также по приоритетной схеме, определяется элементами НЕ 23 и 25, И 24. и

ИЛИ 26 номер регистра 1, где находится экстремальное число. Элементы И 7 и ИЛИ 8 обеспечивают передачу этого числа в регистр 9 ре10 !

Тогда под третьим номером регистра подразумевается регистр 1„,, под четвертым — регистр 1, под второй группой дешифраторов — r-ая группа всех регистров 1, при этом число входов дешифратора $ = 2 =4.

Выходные сигналы дешифраторов. 2<2

2 „, ... 2„ „ „, 2 поступают в блок

6г переноса. В соответствии с табл. 2 по выходным сигналам дешифраторов r-ой (второй) группы(фиг.4) единичные сигналы будут на входах элементов ИЛИ 27@<), 27, (3}, а нулевые — на выходах элементов ИЛИ

27! и 2 . Единичные сигналы с выходов элементов НЕ 29!, 29z,...,29m z открывают по управляющим входам элементы И 28),282 28,28 . Так как единичным сигналом с выхода элемента ИЛИ 27 .! через элемент НЕ

2 закрывается элемент И 28-, что на выходе 6 переноса формируется код 0,1.0,...,0,0. Это означает, что необходимо проводить дальнейший анализ только тех чисел, информация о местонахождении которых находится в выходных сигналах (S-1)-ой группы выходов r-ых дешифраторов 2.

Определение номеров регистров, где находятся эти числа, производится в блоке 3!, < управления. Так как в последнем единичный сигнал присутствует только на входе 13 (фиг.2) элементы И 20 группы 195 открыты.

Так как (табл. 2) единичные сигналы в ($-1)-ой группе имеются только на (n-1) -ом и и-ом выходах, то они через элементы И 201... 20п группы

19 поступают через элементы ИЛИ

18„,,18„ соответственно на выходы

14„„,14 „ блока управления. По этим сигналам в блок 6„.!- переноса (фиг. 1) на анализ поступают только выходные сигналы дешифраторов 2ь 1, H 2.y ч q-! з т ° P- BHBJIH3HP1noTcH коДЫ чисел, сходящиеся в п-ом и (и-1)-ом входных регистрах 1. Так как по условию в промежуточных группах разрядов содержатся все единицы, то работа блоков 6„,...,6 переноса и блоков 3> <,...,3! управления переносом аналогична работе блоков 6 1 м 3„ 1 . Отличие состоит лишь в том, что в них анализируются (табл. 2)

S-e группы выходов дешифраторов кодов чисел из регистров 1д и 1„!

В конечном итоге на выходе блока 3

1171779

Таблица 1

Код числа

Регистр

Номер выходов дешифраторов

О 1 .2 3 4 5 6 7 8 9 10 11 12 13 14 15

1 1100 О О О О О О О 0 О О 0 1 О О 0 О

2 1111 О О О 0 0 О О О 0 О О О О 1 О О

3 1010 О О 0 О О О О О О 1 О О 0 О 0 О

4 1011 О О О О 0 О О 0 О 0 1 О О О О О

Таблица 2 Номер выходов дешифраторов

Код числа

Регистр

Первая группа

1 1

Вторая группа

1 2

О О

1 0

0 1

О О

1 11 00

2 11 11

3 10 10

4 10 11

О

О

О

О

О

О будут в единичные сигналы на выходах 14> и 149«, а в блок 5 анализа поступят выходные сигналы дешифраторов 2„ и 2д., (табл. 2). Так как в первой группе дешифраторов 2 первая единица находится в группе выходов 15 „.<, то в блоке 5 анализа (фиг. 3) единичный сигнал формируется на выходе элемента И 24 (m-1)-го поразрядного узла анализа, так как он открыт единичными сигналами переноса элемента И 25,9, и элементов НЕ 23„, 1 1 9,23,, „-2

Единичный сигнал с выхода элемента

И 23щ < „< через элемент ИЛИ 26<,9 поступает на выход 149« блока 5 анализа. По этому сигналу открывается группа элементов И 7 <, содержпмое регистра 1„< через эти элементы и далее через группу элементов ИЛИ 8 передается в регистр 9 результата. Таким образом, в регист5 ре 9 результата находится наибольшее число в обратном коде. Например, из массива чисел а < = 3, а = О, а = 5, а = 4 (табл. 2) выбрано наибольшее число а = 5, двоичный обратный код которого имеет вид

1010.

Для выбора наименьшего числа массив Йсходных чисел принимается во входные регистры 2 в прямом коде.

15 При этом устройство работает аналогично рассмотренному, но в регистре

9 результата будет наименьшее число в прямом коде.

1171779

1171779

1171779

1)7)779

-17

1Г

Составитель E. Иванова

Редактор Л. Гратилло Техред О.Ващишина Корректор М. Розман

Заказ 4863/40 Тираж 710 Подписное

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

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

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