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

СОКИ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 3(59 С 06 Г 7/02 Н У 4 тво ССС979.о СССР976 (пр ете /04 2. А65855 тотип). ское свидетельс л. С 06 Р 7/02,ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ПИСАНИЕ ИЗ К АВТОРСКОМУ С(54)(57) УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯЭКСТРЕМАЛЬНОГО ЧИСЛА ИЗ пщ-РАЗРЯДНЫХДВОИЧНЫХ ЧИСЕЛ, содержащее первый одноразрядный модуль анализа, имеющийи входов и и+1 выходов, щдвухразрядных модулей анализа последующих разрядов, имеющих и входов анализа старших разрядов, и входов анализа младших разрядов и и+1 выходовкаждый, причем входы старшего (щ)-го разряда и чисел устройства подключены к соответствующим входампервого одноразрядного модуля анализа, выходы которого подключены ксоответствующим входам анализа старших разрядов первого двухразрядногомодуля анализа последующих разрядов,входы младших разрядов которого подключены к соответствующим входам .(щ"2)-го разряда и чисел устройства,одноразрядный модуль анализа содержит элемент ИЛИ-НЕ и и элементов ИЛИ,первый вход 1-го элемента ИЛИ, где1=1,2 и, соединен с входом старшего разряда 1-го числа и 1-м входом элементаИЛИ-НЕ, а выход - с1-м выходом одноразрядного. модуляанализа, (и+1)-й выход которого под-ключен к выходу элемента ИЛИ-НЕ ивторым входам всех элементов ИЛИ,каждый двухразрядный модуль анализапоследующих разрядов содержит элемент ИЛИ-НЕ и п групп элементов И,ИЛИ, включающих первый и второй элементы И и элемент ИЛИ, причем в каждой 1-й группе элементов выход.пер,БО 107054 вого элемента И соединен с первым входом элемента ИЛИ, выход которого подключен к первому входу второго элеменТа И, при этом первый вход первого элемента И 1-й группы, где 1 = =1,2 и, подключен к 1-му входу анализа старших разрядов двухразрядного модуля анализа последующих разрядов и второму входу второго элемента И 1 -й группы, второй вход первого элемента И д-й группы подключен к гму входу младших разрядов первого двухразрядного модуля анализа последующих разрядов, а выход - к соответствующему входу элемента ИЛИ-НЕ первого двухразрядного модуля анализа последующих разрядов, выход второго.Ф элемента И подключен к 1-му выходу первого двухразрядного модуля анализа последующих разрядов, (и+1)-й выход которого соединен с выходом элемента ИЛИ-НЕ первого двухразрядного модуля анализа последующих разрядов иЯ вторыми входами элементов ИЛИ всех групп элементов И, ИЛИ, .т л и ч а - ю щ е е с я тем, что,с цельюповыше. ния быстродействия, в него введены - -1 одноразрядных модулей анаг 3 лиза, два элемента НЕ и коммутатор, где символ х )есть целая часть числа .х, причем одноразрядные модули анализа объединены в нулевую ступень анализа, двухразрядные модулианализа последующих разрядов образуют Я=1 од щ) ступеней анализа помодулей в каждой ступени анали а где с 1 ф 2 ,1 ощ . где символ (х 3 есть такое наименьшее целое Б, что Б 3 х . входы 3-го модуля нулевой ступени анализа, где 3=2,3,. Гподключены кр Ф/ 2 одноименным входам щ+1)-го разряда и чисел, входы анализа старших разрядов 3-го двухразрядного модуля анализа последующих разрядов первой ступени соединены с соответствующими выходами-го модуля нуле1070543 вой ступени, а входы младших разрядов - с одноименными входами(щ)-го разряда и чисел, входы анализа старших разрядов и входы младших разрядов 1-го двухразрядного модуля анализа последующих разрядов 1-й ступени анализа, где 1=1,21=23 . , Б, подключены к соответствующим выходам (1- 1)-го и 1-годвухразрядных модулей анализа последующих разрядов (%-1)-й ступени входы младшего разряда и чисел при нечетном числе разрядов или выходы двухразрядного модуля анализа последующих разрядов р-й ступени анализа при нечетном Я- , р=1,2Р5-1, не вошедшие в пару для подключения к модулю анализа (р+1)-ой ступени, подключены к входам младших разрядов двухразрядного модуля анализа 1Изобретение относится к вычислительной технике и связи и может использоваться, например, в специалиэированных устройствах декодирования двоичных комбинаций по минимуму их 5 расстояния от эталонов или по максимуму их корреляции с эталонами.Известно устройство для сравнения чисел, содержащее и циклических регистров сдвига, п элементов И, 10 элемент ИЛИ, при этом каждый циклический регистр сдвига прямым выходом подключен к соответствующему входу элемента ИЛИ, инверсным выходом - к первому входу соответствующего эле мента И, управляющим входом - к входу импульсов сдвига, входом установки "0" - к выходу соответствующего элемента И, а выход элемента ИЛИ подключен к вторым входам всех элементов И Ь)20Недостаток данного устройства состоит в том, что для его работы необходимы тактирование регистров, запись чисел в регистры и выделение регистра с экстремальным числом.Наиболее близким по технической сущности к предлагаемому является устройство для выделения экстремального числа, содержащее щ выходных элементов ИЛИ-НЕ и щ поразрядных уз- ЗО лов переноса, где щ - число разрядов в сравниваемых числах, а каждый поразрядный узел переноса состоит из и групп элементов И и ИЛИ, каждая ,у .я группа элементов З.-го поразряд ного: узла переноса, где 1=1,2п,=2,3. . . щ, состоит из одного элемента УЛИ,щ - 1 + 1-го элеменпоследующих разрядов (р+ц)-й ступе-ни, 1-е выходы двухразрядного модуля анализа последующих разрядов последней ступени анализа, соединены с1-ми выходными шинами номера экстремального числа устройства и с 1-миуправляющими входами коммутатора,(и + 1)-евыходы.первого одноразрядного и первого .двухразрядного модулейанализа последующих разрядов, черезпервый и второй элементы НБ подключены к выхоцам соответственно щ-го и(щ). - го разрядов экстремальногочисла, выходы остальных разрядов экстремального числа соединены с соответствующими выходами коммутатора, информационные входы которогоподключены к соответствующимвходам остальных разрядов чисел. 2та И, а каждая -я группа элементов первого поразрядного узла переноса состоит из одного элемента ИЛИ и (щ)-го элемента И, причем во всех группах элементов всех поразрядных узлов переноса первый вход элемента ИЛИ соединен с выходом выходного элемента ИЛИ-НЕ соответствующего разряда, а выход элемента ИЛИ подключен к первым входам элементов И той же группы элементов, выход каждого 1-го элемента И 1-й группы элементов 1-го поразрядного узла переноса, где 1=2, 3 щ-(1+1), 1=2,3 и, 1= 2,3. щ, соединен с вторым входом (1+1)-го элемента И 1-й группы элементов (1+1)-го поразрядного узла переноса, а выход первого. элемента И каждой 1-ой группы элементов 1-го поразрядного узла переноса, где =1,2, ,и, 1=1,2 щ, подключены к одному из входов выходного элемента ИЛИ-НЕ соответствующего разряда и к второму входу элемента ИЛИ 1-й группы элементов (1+1)-го поразрядного узла, второй вход элемента ИЛИ каждой -й группы элементов первого поразрядного узла переносов и входы первого выходного элемента ИЛИ-НЕ соединены с шиной первого разряда -го сравниваемого числа, вторые входы каждого р-го элемента И 1-й группы элементов первого поразрядного узла переноса, где р=1,2щ, ,1"1,2 и, подключены к шине (р+ +1)-го разряда 1-го сравниваемого числа, выходы 1-го элемента И каждой 1-й группы элементов первого поразрядного узла переноса, где 1=2,31070543 3= ф 2 э ,и, соединены с нторы входами элементов И (1-1)-й группы элементов подключен к второму входу элемента ИЛИ )-й группы элементов второго поразрядного узла переноса, второй вход каждого (щ)-го элемен та И -й группы элементов второго поразрядного узла переноса соединен с выходом элемента ИЛИ 1-й группы элементов первого поразрядного узла переноса, а выходы элементов И всех 10 групп элементов щ-го поразрядного узла переноса служат выходами устройства. В известном устройстве присутствуют одноразрядный и двухраэрядный модули анализа и чисел. 15 Одноразрядный модуль анализа образован элементом ИЛИ-НЕ 1 и элемен- тами ИЛИ 4 первого поразрядного узла переноса.Двухразрядный модуль анализа образует, например, элемент ИЛИ-НЕ 1 г и и групп элементов из последо- вательно соединенных элемента И 5 первого узла переноса, элемента ИЛИ 4, элемента И 5 второго узлапереноса каждая 2).Однако известное устройство имеет недостаточное быстродействие, так как выделение экстремального числа осуществляется последовательным поразрядным анализом чисел, поскольку модули анализа (поразрядные узлы переноса) включены последовательно,Цель изобретения - повышение быстродействия устройства для выделения экстремального числа из ищ-разрядных З 5 двоичных чисел.Поставленная цель достигается тем, что в устройство для выделения экстремального числа иэ ищ-разрядных двоичных чисел, содержащее первый одно разрядный модуль анализа, имеющий и входов и и+1 выходов, щдвухразрядных модулей анализа последующих разрядов, имеющих и входов анализа старших Разрядов, и входон анализа млад ших разрядов и и+1 выходов каждый, причем входы старшего (щ)-го разряда и чИсел устройства подключены к соответствующим входам первого одноразрядного модуля анализа, выходы которого подключены к соответствующим входам анализа старших разрядов первого двухраэрядного модуля анализа последующих разрядов, входы младших разрядов которого подключены к соответствующим входам (щ)-го разряда и чисел устройства, одноразрядный модуль анализа содержит элемент ИЛИ-НЕ и и элементов ИЛИ, первый вход 1-го элемента ИЛИ, где 1=1,2,и, соединен с входом старшего разряда 1-го. .40 числа и 1-м входом элемента ИЛИ-НЕ, а выход - с 1-м выходом одноразрядного модуля анализа, (и+1)-й выход которо" го подключен к выходу элемента ИЛИ-НЕ и вторым входам нсех элементов ИЛИ, 65 каждый двухразрядный модуль анализа последующих разрядов содержит элемент ИЛИ-НЕ и и групп элементон И, ИЛИ, включающих первый и.нторой эле-: менты И и элемент ИЛИ, причем в каждой 1-й группе элементов выход первого элемента И соединен с первым входом элемента ИЛИ, выход которого подключен к первому входу второго элемента И, при этом первый вход первого элемента И 1-й группы, где 1=1,2,и, подключен к 1-мувходу анализа старших разрядов двухразрядного модуля анализа последукв 1 их разрядов и второму входу второго элемента. И 1-й группы, второй вход первого элемента И 1-й группы подключен к .1-му входу младших разрядов первого двухразрядного модуля анализа послеЬующих разрядов, а выход - к соответствующему входу элемента ИЛИ-НЕ первого двухразрядного модуля анализа последующих разрядов, выход второго элемента И подключен к 1-му выходу первого днухразрядного модуля анализа последующих разрядов, (и+1)-й.выход которого соединен с выхоДом элемента ИЛИ-НЕ первого двухразрядного модуля анализа последующих разрядов и вторы- ми входами элементов ИЛИ всех групп элементов И, ИЛИ, введены (ш-)-1 одноразрядных модулей анализа, днаг элемента НЕ и коммутатор, где символ х) есть целая часть числа х, причем одноразрядные модули анализа двухразрядные модули анализа последующих разрядов образуют Б= 1 од щ ) сту 2 пеней анализа помодулей в каждойгступени анализа, где с=1,2 1 одг в, где символ (х) есть такое наименьшее целое Я, что Ях, входы -го модуля нулевой ступени анализа, где З=2,3 -. подключены к одноименным входам (щ)+1)-го разряда и чисел, входы анализа старших разрядов -го двухразрядного модуля анализа последующих разрядов первой ступени соединены с соответствующими выходами 1-го модуля нулевой ступени, а входы младших разрядов - с одноменными входами (в)-го разряда и чисел, входы анализа старших разрядов и входы младших разрядов 1-го двухраэрядного модуля анализа последующих разрядов 1-й ступени анализа, где 1=1,2, 1=2,3, Б, подключены к соответствующим выходам (Р)-го и Р-го днухразрядных модулей анализа последующих разрядов ф)-.й ступени, входы младшего разряда и чисел при нечетном числе разрядов или выходы двухразрядного мо дуля анализа последующих разрядов р-й ступени анализа при нечетномр=1,25-1 не вошедшие вщ 1г 2ттвГгр/пару для подключения к модулю анализа (р+1)-й ступени, подключены квходам младших разрядов двухразрядного модуля анализа последующих разрядов (р+ц)-й ступени, 1-е выходыдвухразрядного модуля анализа последующих разрядов последней ступенианализа соединены с 1-ми выходнымишинами номера экстремального числаустройства и с 1-ми управляющими входами коммутатора, (и+1)-е выходы первого одноразрядного и первого двухразрядного модулей анализа последующих разрядов через первый и второйэлементы НЕ подключены к выходам соответственно щ-го и (щ)-го разрядов экстремального числа, выходы остальных разрядов экстремального числа соединены с соответствующими выходаси коммутатора, информационные вхо ды которогоподключены к соответствующим входам остальных разрядов и чисел.На фиг 1 приведена схема устройства для выделения экстремального числа 25из и 8-разрядных двоичных чисел, нафиг.2 - схема первого одноразрядного модуля анализа, на фиг.Зсхема первого двухразрядного модуля анализа последующих разрядов. 30Устройство для выделения экстремального числа (фиг.1) содержитодноразрядные модули анализа 1 О12,о 1 Эо 14 нулевой Ступени анализа, двухразрядные модули анализапоследующих разрядов 2 2 2,2,2 4 1 Первой ступени анализа21,2,22 - второй ступени анализа,2 - третьей ступени анализа, дваэлемента НЕ 3 и 4, коммутатор 5, информационные входы 6 1,1 й62, - бпдустройства, где 1=01.е.7 выходы7 7 + одноразрядного модля анализз а вйходы 8, .., 8 8двухразрядного модуля анализа последующих разрядов выходы 9. 9, 45экстремального числа устройства, вйходы 1010 номера экстремального числа устройства.Первый одноразрядный модуль анализа 1 ,р (фиг.2) содержит элемент 50ИЛИ-НЕ 11 и и элементов ИЛИ 12.Первый двухразрядный модуль анализа 2 ,1 (фиг.З) содержит элемент ИЛИ-НЕ 13 и и групп элементов из последовательно соединенных первого 55 элемента,И 14, элемента ИЛИ 15, второго элемента И 16 каждая. В общем случае нулевая ступень анализа содержитмодулей 1, где символ гх 1 есть целая часть числа х, двухразрядные модули анализа 2 распределены по 5= 1 о 8 щ ) ступеням анализа, где символ (х 1 есть такое наименьшее цед лое Б что 5 Ъ х. Входы нулевого разряда и чиселпри нечетном щ или выходы модуля3-й СтуПЕНИ ПрИ НЕЧЕТНОМ 2, (3 т 1 г5-1) не вошедшие в пару дляподключения к модулю (3+1)-й ступени,подключаются к младшим входам модуля соответствующей старшей ступени.Устройство для выделения экстремального числа работает следующим образом.На входы б (фиг.1) поступают кодыпщ-разрядных двоичных чисел в прямомвиде при выделении максимальнЬгочисла и в инверсном виде при выделении минимальногочисла (в устройствена фиг.1 щ=8). Первый одноразрядныймодуль 1 т анализа нулевой ступенисравнения анализирует (щ)-е (старшие) разряды чисел, поступающие навходы б 62,76-, и формируетлогическую "1" (признак экстремального числа по одному разряду на выходе7 ,(% =1,2, й) если старший разряд 1-го числа равен 1 или если старшие разряды п чисел равны О,Аналогичным образом 1 д-й модуль 1;в ( 1=2,3,1 нулевой ступени анализа вы 2 лявляет экстремальное число по разряду-2 +1,Первый двухразрядный модуль анализа последующих разрядов 21 первойступени анализа анализирует признакиэкстремального числа, поступающие наего старшие входы с выходов 7727 модуля 1 0 и (е) -е разряды чисел, поступающие на его младшие входы с входов бб62,б,.6,6 иформирует логическую 1 (признак экстремального числа по двум разрядам)на выходе 8 к ( =1,2 л ), если на %-мстаршем и Ф -м младшем входах присутст,вует логическая "1" или если на Ф-мстаршем входе присутствует логическая "1, а на всех младших входахлогической "0". Аналогичным образом1-й модуль 2. (1=2,3 ищ 1- ) первой ступени анализа формиругет признак экстремального числа поразрядам щ+ и щ.Точно также 1-й модуль 2 Ц,3-йступени анализа (1=1,2 23==2,3 Я анализирует призйаки поступающиена его старшие входы свыходов (21-1)-го модуля, на младщие входи - с выходов 21-го модуля-)-й ступени анализа и формирует признак экстремального числа поразрядам с, (щ1) -го по щ(1- 1)- 11 йе Входы нулевого разряда при нечетном щ или выходы модуля 3-й ступени Прн НЕЧЕТНОМ -т (3=1,2 5-1) остаются без пары для подключения к модулю Я+1)-й ступени. Й этом случае они подключаются к младшим входам модуля соответствующей старшей ступени.Модуль 2 , последней ступени4анализа выделяет экстремальное число по всем щ разрядам и чисел и формирует логическую "1" на соответству ющем выходе 10 10 10 номера экстремального числа. Сигналы с этих выходов поступают на управляющие входы коммутатора 5, который коммутирует на выходы 9, 9, 9 нулевой, первый, , (щ)-й разряды экстремального числа, выделенные согласно номеру экстремального числа из указанных разрядов всех чисел поступающих на информационные входы 15 . коммутатора 5 с соответствующих входов б., Старший (щ)-й разряд экстремального числа выделяется на выходе 7, модуля 1 О и через элемент НЕ 3 выдается на выход 9, а (щ)-й 20 разряд экстремального числа выделяет. ся на выходе 8 + модуля 2и через элемент НЕ 4 выдается на выход 96.В одноразрядном модуле анализа 1 О (фиг.2) ИЛИ-НЕ 11 выявляет состояние старших разрядов чисел, поступающих на входы б,б б., и формирует на выходе 7 + (инверсный выход старшего разряда экстремального числа) логическую ф 1", если старшие разряды чисел равны О, и логический фО", если старший разряд хотя бы одного числа равен 1. В результате на выходах 77 . , 7 элементов ИЛИ 12 присутствует логическая "1", если старшие разряды чисел равны О,в З 5 противном случае коды старших чисел с входов б через элементы ИЛИ 12 передаются на выходы 7 без изменений, т.е. модуль 1формирует признаки,оэкстремального числа по старшему разряду. Остальные модули 1 работают аналогично, с тем лишь отличием,что их выход 7в схеме устройства не используется.В двухразрядном модуле анализа 45 2(фиг.З) первый элемент И 14 (1=1,2 п) образует конъюнкцию а Ь где а. - сигнал на старшем в;соде 7;, Ь; - сигнал на младшем входа б; б, а элемент ИЛИ-НЕ 13 Формирует логическую "1" на выходе 8(инверсный выход (щ)-,го разрядам+ экстремального числа), если все конь юнкции равны логическому "Оф, и логический "0", если хотя бы одна из конъюнкций равна логической "1".55 В результате на выходах элементов. ИЛИ 15, 15 15 присутствует ло,гическая 1 ф, если на выходах всех элементов И 14 присутствует логический "О", в противном случае сигналы с выходов элементов И 14 проходят на выходы элементов ИЛИ 15 без изменений. Элемент И 16 (1=1,2 и) объясняет по И сигнал на старшем входе 7 с выходным сигналом эле 1мента ИЛИ 15; и образует на выходе 8; логическую "1", если а=Ь=1 или а;=0 при 13, т.е. модуль 2 , формйрует признаки экстремального числа по сигналам на его старших и младших входахОстальные модули 2 работают аналогично, с тем лишь отличием, что их выход 7 и+ в схеме устройства не используется.Повыщение быстродействия в предлагаемом устройстве достигается сочетанием параллельного сравнения чисел в каждой ступени с последовательным включением ступеней анализа, при этом используется одна ступень одноразрядного анализа и 5= 1 оц щ 3г ступеней двухразрядного анализа. В одноразрядном модуле анализа (фиг.2) .сигнал проходит две ступени задержки, в двухразрядном модуле анализа (фиг.З) - четыре ступени задержки, в результате задержка выделения номера экстремального числа на выходах 10 устройства (фиг.1) .равна йз=(2+ :+45) Т, где 7 - задержка распространенйя сигнала в одном элементе И, или ИЛИ, или ИЛИ-НЕ.Коммутатор 5 может быть выполнен на элементах И, ИЛИ, при этом элементы И коммутируют разряды чисел, а элементы ИЛИ объединяют выходы тех элементов И, которые коммутируют одноименные разряды чисел. В результате код экстремального числа Формируется с дополнительной задержкой .2 .В прототипе в каждом узле переноса сигнал проходит три ступени задержки, поэтому номер экстремального числа выделяется с задержкой Зщт, так.как узлы переноса включены последовательно, а код экстремального числа - с задержкой (Зщ);Выигрыш в быстродействии предлагаемого устройства по сравнению с прототипом в случае 8-разрядных чисел равен 1,7 по выделению номера экстремального числа и 1,4 по выделению кода экстремального числа. С ростом количества разрядов существенно растут и выигрыши по быстродействию, причем без дополнительных затрат .оборудования, так как введенные коммутатор, элементы НЕ, щодноразрядные модули сравнения .реалпэуются на меньшем числе элементов схемы по сравнению с элементами И в прототипе, через которые на следующий узел переноса проходят не участвунищие в анализе разряды чисел. Испытания макетов базового образца.,за которйй принято устройство 2 3, и предлагаемого устройства показывают работоспособность и эффективность предлагаемого устройства.Тираж 699 Подписиударственйого комитета СССРизобретений и открытийва, Ж, Раушская наб., д.4/5 каз 11683/46ВНИИПИ Гопо делам113035, Мос лиал ППП фПатентф, г.Укгород, ул.Проектная