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

(56) Авторское9 664170, кл. САвторское свР 903864, кл. С ол. Р 29 8.8)видетельст06 Р 7/02,СССР 976. ССР 980. детельство 06 Р 7/06,. ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ОПИСАНИЕ ИЗОБРЕ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(54)(57) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНОГО ИЗ П ЧИСЕЛ, содержащее регистры, дешифраторы, регистр результата, группы элементов И, ИЛИ блок анализа, включающий и элементов ИЛИ и в поразрядных узлов анализа, где в - число разрядов анализируемых чисел, каждый к-й поразрядный узел анализа, где 1( = 1,2,, Ь)-1), содержитэлементов И,элементов НЕ и многовходовый элемент И, Ф -й поразрядный узел анализа включает 1) элементов И и (1)-1) Элементов НЕ, причем в 1 -ом поразрядном узле анализа,1 -й вход поразрядного узла. анализа, где1,2й, подключен к 1 -му информационному входу 1 -го элемен 1та И и через 1 -ый элемент НЕ - к (1+1)-ым информационным входам элементов И с (1+1)-го по П -ый и к 1-ому входу многовходового элемента И, выход которого подключен к управляющим входам элементов И 5+1)-го поразрядного узла анализа, в первом поразрядном узле анализа управляющие входы элементов И подключены к выходу первого элемента НЕ, каждый-й вход 1-го поразрядного узла анализа, где ) - 1,2(-1), соединен с первым информационным входом-го элемента И и через-й элемент НЕ соединен с (1)+1)-ым информационным входом элементов И с (19+1)-го по-ый, и)-й вход поразрядного узла анализа подключен к (щ+1)-му информационному входу поразрядного )1 -го элемента И, выход 1 -го элемента И ф-го поразрядного узла анализа подключен к 1( -му входу-го разрядного элемента ИЛИ, выход 1 -го элемента И и)-го поразрядного узла анализа подключен кап -му входу 1 -го элемента ИЛИ, выход которого является 1-ым выходом блока анализа и соединен с учравляющими входами элементов И 1 -ой группы, информационные входы которых соединены с соответствующими выходами. -го регистра, входы которого соединены с входами; -го числа устройства, выходы элементов И 1 -ой группы подключены к входам соответствующих элементов ИЛИ группы, выходы которых соединены с входами регистра результата, выходы которого являются выходами; устройства, первая группа выходов каждого 1 -го регистра соединена с входами 1 -го дешифратора, о т л и - ч а ю щ е е с я тем, что, с целью уменьшения аппаратных затрат с увеличением разрядности анализируемь 1 х чисел, устройство дополнительно содержит 1)-групп дешифраторов по (Г) дешифратору в каждой, где Г - число .групп анализируемых разрядов, (Г -1) групп элементов И переноса по 1) элементов И переноса в каждой; (Г) блоков управления пере1171779 носом и (г) блоков переноса, .каждый блок переноса содержит (5-1) элементов И, где 5 - число выходов дешифратора, (5-1) элементов НЕ и 5 элементов ИЛИ, причем выход 3-го элемента ИЛИ, где /3 = 1,2 (6 -1), соединен через/3 -й элемент НЕ с-ым управляющим входом элементов И с -го по Я)-ый, выход 1-го элемента ИЛИ, где 1 = 2,3б соединен с информационным входом Я) элемента И,. каждый блок управления переносом содержит элемент ИЛИ-НЕ, О элементов ИЛИ и 5 групп элементов И по й элементов в каждой причем выходы 1 -ых элементов И всех групп подключены к информационным входам-го элемента ИЛИ, (и+1)-е входы всех элементов ИЛИ соединены с выходом элемента ИЛИ-НЕ, 1 -й выход г -го дешифратора 1 -ой группы, где= 1,25, соединен с-ым входом 1 -го элемента ИЛИ (Г) -го блока переноса и информационными входами 1 -ых элементов И всех групп (Г)-го блока управления переносом,1Изобретение относится к автоматике и вычислительной технике и может быть использовано при реализации технических средств цифровых систем контроля, систем обработки 5 данных и автоматизированных систем управления.Цель изобретения - уменьшение аппаратных затрат с увеличением разрядности анализируемых чисел.На фиг. 1 показана структурная схема предлагаемого устройства; на фиг, 2 - то же, блока управления переносом; на фиг. 3 - то же, блока анализа; на фиг. 4 - то же, блока 15 переноса.Устройство (фиг.1) содержит регистры 1,,1 группы дешифраторовЧ2,..,212, блоки 31 3, управления переносом, группы 20элементов И 4 , ,4 , блок 5 ана-, лиза, блоки 6, 6 переноса, группы элементов И 717, групуправляющие входы элементов И 1 -ой группы 7, -го блока управления переносом, где Х = 1,2(г -1), соединены с выходами (1-1)-го элемента И У-го блока переноса, управляющие входы элементов И первой группы 2 -го блока управления переносом подключены к выходу первого элемента ИЛИ Х-го блока переноса, выходы 2 -го дешифратора-ой группы соединеныс информационными входами-го элемента И переноса 2 -ой группы и с информационными входами-ых элементов И всех групп (,-1)-го блока управления переносом, управляющийвход-го элемента И переноса Е -ой группы подключен к выходу 1 -го элемента ИЛИЕ -го блока управления пе%реносом, выход-го элемента И переноса Ч -ой группы, где Ч = 2,3 (Г), подключен к информационным входам-ых элементов И всех групп (Ч)-го блока переноса, выход 1 -го элемента И переноса первой группы подключен к-му входу поразрядного узла анализа блока анализа. пу элементов ИЛИ 8, регистр 9 результата, входы 10110, устрой-ства, входы 11111 п регистров 1, выходы 12112 я,2 дешифраторов 2, выходы 13113 блоков 6переноса, выходы 14114 дф 14 г+ блоков 3 управления, выходы 15 1, 15, 15 . групп элементов И 4, выходы 1616 блока 5 анализа, выход 17 устройства.Блок управления 3 переносом (фиг. 2) содержит группу элементов ИЛИ 181 18 , группы 19 элементов И 20 и элемент ИЛИ-НЕ 21.Блок 5 анализа (фиг. 3) содержит ш поразрядных узлов 22 анализа, состоящих из элементов НЕ 23, элементов И 24, многовходового элемента И 25 и элементов ИЛИ 26.Блок 6 переноса (фиг. 4) содержит группу элементов ИЛИ 2727 группу элементов И 28128. и группу элементов НЕ 29,29.Определеие экстремального из чисел производится на основе анализараспределительных кодов с выходовдешифраторов, на входы которых подаются двоичные коды исходных чисел. 5Пусть п=4, а разрядность исходных чисел 1=4.При а= 1100, а= 1111, а = 1010,а = 1011 выходные сигналы дешифратоФров при преобразовании этих чисел 10представлены в табл.1, из которойвидно, что при проведении анализаодноименных выходов дешифраторов,начиная с младших по номеру, первая "1" находится в 10-и столбце 15выходов, т.е. наименьшее число находится в третьем регистре, Крометого, для определения наименьшего числа необходимо 16 поразрядных узлов анализа. , 20Если разделить разряды регистровна группы, то можно сократить объемоборудования. Разделим разряды исходных чисел на две группы. Дляданного случая в табл. 2 приведены 25сигналы дешифраторов,Из табл. 2 видно, что во второй группе выходов дешифраторов единицы находятся в третьем столбце. По этому наименьшее число определяется анализом выходных сигналов первой группы дешифраторов, причем анализировать необходимо одноименные выходы дешифраторов только третьего и четвертого регистров. Первая единица при этом находится в третьем столбце второй части табл. 2. Таким образом, наименьшее число находится в третьем регистре. При этом 40 общее число выходов дешифраторов равно 8, а для определения наименьшего числа потребуется четыре поразрядных узла для анализа одноименных выходов дешифраторов группы 45 младших разрядов исходных чисел. Предыдущие группы разрядов регистров используются для определения тех чисел, у которых "1" имеются в выбранной группе одноименных выходов 50 дешифраторов. Так, (табл. 2) в первой группе выходов дешифраторов значения "1" в третьем столбце указывают на р.венство кодов в третьем и четвертом регистрах в этой груп пе и поэтому окончательное решение о местонахо:кдепии наименьшего числа принимается после анализа одноименных выходов дешифраторов толькодля третьего и четвертого регистров.Затраты оборудования зависят отвыбора количества групп и числарязрядов регистров в группе. Причем наименьший объем оборудованиядостигается при равном числе разрядов в группах. Показать это можно следующим образом.Пусть у - число выходов дешифраторов. Тогда для 12-разрядногочисла необходимо найти минимальноеХ 2 3 4значение у = 2 +2 +2 +2, гдех = 12, причем х; ) 2.Установить численные значениядля каждого показателя степени хвозможно перебором их величин. Нозначение у минимально и при минимальных значениях каждого из слагаемых, которое могут быть достигнуты лишь при равных показателях х,.Например, если х = х= х = х, = 32та у = 42 = 32. Если х = 3,х 1= 2, х=4, то у = 36,Известен принцип разделения регистра на группы разрядов при представлении чисел в ЭВМ с плавающейзапятой, когда первая группа разрядов отводится для представленияпорядка, а вторая группа разрядовдля представления нормализованноймантиссы числа,При сравнении двух чисел, заключающемся в определении экстремального из них, операция сводится к выполнению операции вычитания чиселс последующим анализом результата.Результат операции сравнения формируется на основе анализа порядков имантисс чисел. При равных порядкахво внимание принимается результатсравнения мантисс. В ЭВМ выполнениеоперации вычитания производитсяс использованием двух сумматоров.В предлагаемом устройстве разделение регистров на группы разрядов преследует цель сокращенияоборудования при определении экст-ремального числа с использованиемдешифраторов групп разрядов и комбинационных схем для последовательного анализа одноименных выходовдешифратора последующих групп. Всоответствии с этим (фиг. 1) выходы дешифраторов одноименных группразрядов 2.,2.2 о .г 2 и ганализируются в блоке 6. перено-са. Каждый блок 6 16., перено 117177910 5 20 30 35 40 са обеспечивает определение группы одноименных разрядов распределитель ных коцов в соответствии с табл, 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 ре.зультата.Устройство работает следующим образом.Для определения наибольшего числа массив исходных чисел принимается во входные регистры й в обратных 45 кодах. Рассмотрим работу устройства при следующих условиях, Пусть каждый регистр 1 разделен на группы по два разряда в каждой. Предположим, что обратный код массива чис ла имеет следующий вид:. а 1 = 1100 а = 11 11 а. = 1111, ав 1010, а = 1011, где все разряды промежуточных чисел и разряды в промежуточных группах ука ванных чисел содержат единицы. Сгруппируем эти разряды так, чтобы привести их в соответствие.с табл.2,Тогда под третьим номером регистра подразумевается регистр 1 под четвертым - регистр 1, под второй группой дешифраторов - г-ая группа всех регистров 1, при этом число входов дешифратора Б = 2 =4.Выходные сигналы дешифраторов. 2 22 г2 Ог 1 2 и.поступают в блок бгпереноса. В соответствии с табл. 2 по выходным сигналам дешифраторов г-ой (второй) группы(фиг.4) единичные сигналы будут на входахэлементов ИЛИ 27), 27 1(М а нулевые - на выходах элементов ИЛИ 27 и 2. Единичные сигналы с выходов элементов НЕ 29, 2929открывают по управляющим входам элементы И 281,2828 ,28 . Так как единичным сигналом с выхода элемента ИЛИ 27. через элемент НЕ 2 закрывается элемент И 28., что на выходе 6 переноса формируется код 0,1.00,0. Это означает, что необходимо проводить дальнейший анализ только тех чисел, информация о местонахождении которых находится в выходных сигналах (Б)-ой группы выходов г-ых дешифраторов 2.Определение номеров регистров, где находятся эти числа, производится в блоке 3 управления. Так как в последнем единичный сигнал присутствует только на входе 13 (фиг.2) элементы И 20 группы 195открыты. Так как (табл, 2) единичные сигналы в (8-1)-ой группе имеются только на (и) -ом и и-ом выходах, то они через элементы И 201 20 О группы 19, поступают через элементы ИЛИ 1818 соответственно на выходы 14.,14блока управления. По этим сигналам в блок 6. переноса (фиг. 1) на анализ поступают только выходные сигналы дешифраторов 2,.1, и 2).ч 2т е анализируются коды чисел, сходящиеся в и-ом и (и)-ом входных регистрах 1. Так как по условию в промежуточных группах разрядов содержатся все единицы, то работа блоков 6. 6переноса и блоков 3,3 управления переносом аналогична работе блоков 6.1 м 3 1 . Отличие состоит лишь в том, что в них анализируются (табл, 2) Я-е группы выходов дешифраторов кодов чисел из регистров 1 О и 1 В конечном итоге на выходе блока 31171779 Таблица 1 Кодчисла Ре- гистр Номер выходов дешифраторов О 1 .2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1100 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 2 1111 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 3 1010 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 4 1011 0 0 0 0 00 0 0 0 0 1 0 0 0 0 0 Таблица 2 Номер выходов дешифраторов Кодчисла Регистр Первая группа Вторая группа 120 0 0 1 0 0 1 0 0 1 11 00 2 11 11 3 10 10 4 10 11 0 0 0 0 0 0 0 0 0 0 0 0 0 будут в единичные сигналы на выходах 14 и 14 в. , а в блок 5 анализа поступят выходные сигналы дешифраторов 2 и 2, (табл. 2). Так как в первой группе дешифраторов 2 первая единица находится в группе выходов 15 р., то в блоке 5 анализа (фиг. 3) единичный сигнал формируется на выходе элемента И 24 р, (ш)-го поразрядного узла анализа, так как он открыт единичными сигналами переноса элемента И 25 и элементов НЕ 23,р1,223 р- р-р-,1 2-. 2Единичный сигнал с выхода элемента И 23 щчерез элемент ИЛИ 26 р. поступает на выход 142 блока 5 анализа. По этому сигналу открывается группа элементов И 7 р 1, содержпмое регистра 1 через эти элементы и далее через группу элементов ИЛИ 8 передается в регистр 9 результата. Таким образом, в регист ре 9 результата находится наибольшее число в обратном коде. Например, из массива чисел а= 3, а = О, а 2 = 5, а = 4 (табл. 2) выбрано наибольшее число а 2 = 5, двоичный 10 обратный код которого имеет вид1010.Для выбора наименьшего числамассив Йсходных чисел принимается во входные регистры 2 в прямом коде.15 При этом устройство работает аналогично рассмотренному, но в регистре 9 результата будет наименьшее число в прямом коде.71 сное Заказ оскв илиал ППП "Патент", г. Ужгород, ул. Просктная, 4 40ВНИИПИпо13035,Тир Государ елам из