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

носом и (г-о блоков переноса, .каж дый блок переноса содержит (5-1) элементов И, где 5 - число выходов дешифратора, (5-1) элементов НЕ и 6 элементов ИЛИ, причем выход элемента ИЛИ, где /3 1,2,..., (5-1), соединен через/3-и элемент НЕ с В-ым управляющим входом элементов И с /3-го по (5-1)-ый, выход i-ro элемента ИЛИ, где { 2,3,,..,5 соединен с информационным входом (-f-1) элемента И,, каждыйблок управления переносом содержит элемент ИЛИ-НЕ, Ti элементов ИЛИ и 5 групп элементов И по Г) элементов в каждой причем выходы i -ых элементов И всех групп подключены к информационным входам i-ro элемента ИЛИ, (п+1)входы всех элементов ИЛИ соединены с выходом элемента ИЛИ-НЕ,i -и выход г-го дешифратора i -ой группы, где i 1,2,...,5 соединен с 1 -ым входомt-го элемента ИЛИ (р-1)-го блока переноса и информационными входами -ых элементов И всех групп (г-1)-го блока управления переносом.

управляющие входы элементов И 1 -ой группы -го блока управления переносом, где 1,2, . . ., (г-1), соединены с выходами (i-1)-ro элемента И 2-го блока переноса, управляющие входы элементов И первой группы -го блока управления переносом подключены к выходу первого элемента ИЛИ 2-го блока переноса, выходы -го дешифратора -ой группы соединены с информационными входами i -го элемента И переноса -ой группы и с информационными входами i -ых элементов И всех групп ()-ro блока управления переносом, управляющий вход i -го элемента И переноса Z-ой группы подключен к выходу i -го элемента ИЛИ2 -го блока управления переносом, выход 1 -го элемента И переноса V-ой группы, где V 2,3,..., (Р-1), подключен к информационным входам 1 -ых элементов И всех групп (V-l)-ro блока переноса, выход i -го элемента И переноса первой группы подключен к i -му входу поразрядного узла анализа блока анализа.

УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНОГО ИЗ П ЧИСЕЛ, содержащее регистры, дешифраторы, регистр результата, группы элементов И, ИЛИ блок анализа, включающий П элементов ИЛИ и 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-й вход поразрядного узла анализа подключен к

1

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

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

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

Устройство (фиг.1) содержит регистры 1ц,,... ,1,р, группы дешифраторов 2,, ,. . . ,2 ,. . ., 2, блоки 3 ),..., Эр, управления переносом, группы элементов И 4, ,...,4г,+ , , блок 5 анлиза, блоки 6,,..., бз,., переноса, группы элементов И 7 , . .., 7 , группу элементов ИЛИ 8, регистр 9 результата, входы 11)(,..., 10 устройства, йходы 11,,...,11„ регистров 1, выходы 12;|, ,.. ., 12 П.2 дешифраторов

2, выходы 13, . ..,13р., блоков 6 переноса, выходы 14, , ..., 14и., ,- 14г+1 блоков 3 управления, выходы 15,,, ,. ..,15,. 1,15,,„ групп элементов И 4, выходы I6f,...,16f, блока 5

анализа, выход 17 устройства.

Блок управления 3 переносом (фиг. 2) содержит группу элементов ИЛИ 18,,...,18ц, группы 19 элементов И 20 и элемент ШШ-НЕ 21. .

Блок 5 анализа (фиг. 3) содержит m поразрядных узлов 22 анализа, состоящих из элементов НЕ 23, элементов И 24, многовходового элемента И 25 и элементов ИЛИ 26.

Блок 6 переноса (фиг. 4) содержит группу элементов ИЛИ 27, ,...,275 группу элементов И 28 j, . . . ,285-1 и группу элементов НЕ 29, ,... ,295-1 3 Определение экстремального из чи сел производится на основе анализа распределительных кодов с выходов дешифраторов, на входы которых подаются двоичные коды исходных чисел Пусть , а разрядпость исхо дных чисел . При а, 1100, а2 1111, а 1010 а, 1011 выходные сигналы дешифрато ров при преобразовании этих чисел представлены в табл.1, из которой видно, что при проведении анализа одноименных выходов дешифраторов, начиная с младших по номеру, первая 1 находится в 10-м столбце выходов, т.е. наименьшее число находится в третьем регистре. Кроме того, для определения наименьшего числа необходимо 16 поразрядных узлов анализа. Если разделить разряды регистров на группы, то можно сократить объем оборудования. Разделим разряды исходных чисел на две группы. Для данного случая в табл. 2 приведены сигналы дешифраторов. Из табл. 2 видно, что во второй группе выходов дешифраторов единицы находятся в третьем столбце. Поэтому наименьшее число определяется анализом выходных сигналов пер вой группы дешифраторов, причем анализировать необходимо одноименны выходы дешифраторов только третьего и четвертого регистров. Первая единица при этом находится в третьем столбце второй части табл. 2. Таким образом, наименьшее число находится в третьем регистре. При этом общее число выходов дешифраторов равно 8, а для определения наименьш го числа потребуется четыре поразрядных узла для анализа одноименных выходов дешифраторов группы младших разрядов исходных чисел. Предьщущие группы разрядов регистров используются для определения те чисел, у которых 1 имеются в выбранной группе одноименных выходов дешифраторов. Так, (табл. 2) в первой группе выходов дешифраторов значения 1 в третьем столбце указывают па равенство кодов в третьем и tjeTBepTOM регистрах в этой группе и поэтому окончательное решение о местонахо:кдепии наименьшего числа принимается после анализа одноимен794ных выходов дешифраторов только для третьего и четвертого регистров. Затраты оборудования зависят от выбора количества групп и числа рязрядов регистров в группе. Причем наименьший объем оборудования достигается при равном числе разрядов в группах. Показать это можно следующим образом. Пусть у - число выходов дешифраторов. Тогда для 12-разрядного числа необходимо найти минимальное зд1ачеиие у 2 , где .21 X 12, причем xj 2. Установить численные значения для каждого показателя степени х возможно перебором их величин. Но значение у минимально и при ътнимальных значениях каждого из слагаемых, которое могут быть достигнуты лишь при равных показателях х, . Например, если х - з то у 32. Если Х2 3, X 2, х - 4, то у 36. Известен принцип разделения регистра на группы разрядов при представлении чисел в ЭВМ с плавающей запятой, когда первая группа разрядов отводится для представления порядка, а вторая группа разрядов для представления нормализованной мантиссы числа. При сравнении двух чисел, заключающемся в определении.экстремального из них, операция сводится к выполнению операции вычитания чисел с последующим анализом результата. Результат операции сравнения формируется на основе анализа порядков и мантисс чисел. При равных порядках во внимание принимается результат сравнения мантисс. В ЭВМ выполнение операции вычитания производится с использованием двух сумматоров. В предлагаемом устройстве раз- деление регистров на группы разрядов преследует цель сокращения оборудования при определении экстремального числа с использованием дешифраторов групп разрядов и комбинационных схем для последовательного анализа одноименных выходов дешифратора последующих групп. В соответствии с этим (фиг. 1) вы- ходы дешифраторов одноименных групп разрядов 2,2 ,2др, .. .,2.,. .2 „,f, анализируются в блоке 6р.,- переноса. Каждый блок 6,...,6р,,- переноса обеспечивает определение группы одноименных разрядов распределительных кодов в соответствии с табл. 2, в которых имеются значения 1. . Блок переноса (фиг.2) выполнен по приоритетной схеме, управляемой выходными сигналами элементов ИЛИ 27 и НЕ 29. На выходах 13 блока переноса формируется распределительный код, содержащий либо все О, либо на одном из его выходов . Этими сигналами в блоке 3 управления определяются 1 в выделенной группе одноименных разрядов в блоке 6 переноса из сигналов дешифраторов. Выходные сигналы 14 блока 3 управления переносом управляют .передачей на анализ в очередной блок переноса сигналов дешифраторов, выделенных для анализа регистров . Если распределительный код выходных сигналов блока 6 переноса содержит все О, то все выходные сигналы блока 3 управления равны 1 за счет элемента ИЛИ-НЕ 21. При этом в очередной блок 6 переноса передаются на анализ выходные сигналы одноименных дешифраторов 2 всех регистров 1. В конечном итоге в блоке 5 анализа (фиг. 3) в соответствующем поразрядном узле 22 анализа, выполненном также по приоритетной схеме- определяется элементами НЕ 23 и 25, И 24- и ИЛИ 26 номер регистра 1, где находится экстремальное число. Элементы И 7 и ИЛИ 8 обеспечивают передачу этого числа в регистр 9 ре.зультата.

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

Для определения наибольшего числ массив исходных чисел принимается во входные регистры и в обратных кодах. Рассмотрим работу устройства при следующих условиях. Пусть каждый регистр 1 разделен на группы по два разряда в каждой. Предположим, что обратный код массива числа имеет следующий вид: а, 11...0 З.Л h- ll e«llj

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

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

Выходные сигналы депш(раторов. 22f,. . .2.., j2n.г- поступают в блок 6j,. переноса. В соответствии с табл. 2 по выходным сигналам дешифраторов г-ой (второй) группы(фиг.4) единичные сигналы будут на входах элементов ИЛИ 27) , 279-1 (Э), а нулевые - на выходах элементов ИЛИ 27j| и . Единичные сигналы с выходов элементов НЕ 29, 292 ,29д. открывают по управляющим входам элементы И 28 )|, 282, ...,285.2 28д.. - как единичным сигналом с выхода элемента ИЛИ 27. через элемент НЕ 2 закрывается элемент И 285.,, что на выходе 6 переноса формируется код 0,1.00,0. Это означает,

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

Определение номеров регистров, где находятся эти числа, производится в блоке управления. Так как в последнем единичный сигнал присутствует только на входе 13 (фиг.2) элементы И 20 группы 195-1 открыты. Так как (табл. 2) единичные сигналы в (8-1)-ой группе имеются только на (п-1)-ом и п-ом выходах, то они через элементы И 20 ц., , 20,, группы 195-1 поступают через элементы ИЖ IBn-ijIS соответственно на выходы 14п.1,14 блока управления. По этим сигналам в блок 6|,./ переноса (фиг. 1) на анализ поступают только выходные сигналы дешифраторов 2., и 2,,.ц 2, ) т.е. анализируются коды чисел, сходящиеся в п-ом и (п-1)-ом входных регистрах 1. Так как по условию в промежуточньпс группах разрядов содержатся все единицы, то работа блоков 6р,| ,...,б переноса и блоков Зр, ,...,3 управления переносом аналогична работе блоков 6,. м 3f.. . Отличие состоит лишь в том, что в них анализируются (табл. 2) S-e группы вькодов дешифраторов кодов чисел из регистров Ip и „., . Б конечном итоге на выходе блока 3

Будут в единичные сигналы на выходах 14( и lAj,., , а в блок 5 анализа поступят выходные сигналы дешифраторов 2, и 2.,| (табл. 2). Так как в первой группе дешифраторов 2 первая единица находится в группе выходов 15 (fj, , то в блоке 5 анализа (фиг. 3) единичный сигнал формируется на выходе элемента И 24., (m-l)-ro поразрядного узла анализа, так как он открыт единичными сигналами переноса элемента И 25.2 и элементов НЕ 23., ,.,.,23., . Единичный сигнал с выхода элемента И 23j.| . через элемент РШИ 26t).j поступает на выход блока 5 анализа. По этому сигналу открывается группа элементов И 7f,i , содерО О

о о 1 1

О О 0. О

о о

жимое регистра 1 j,., через эти элементы и далее через группу элементов t-ШИ 8 передается в регистр 9 результата. Таким образом, в регистре 9 результата находится наибольшее число в обратном коде. Например, из массива чисел aj 3, а О, а 5, 4 (табл. 2) выбрано наибольшее число а 5, двоичный

обратный код которого имеет вид 1010.

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

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

Таблица 1

Таблица 2

о 1

о о 1 о

о о о о

1

о о о

о 1

i.|b-j:

г1

I

Ji.f

К2 .

Фи&. /5r-/./