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

вой ступени, а входы младших разрядЬв - с одноименными входами (m-2j)-ro разряда п чисел, входы анализа старших разрядов и входы младших разрядов 1-го двухразрядного модуля анализа последукхцих разрядов k-й ступени анализа, где ,2,..., , ,3,..., S, подключены к соответствующим выходам (1-1)-го и 1-Г0 двухразрядных модулей анализа последующих разрядов (1с-1)-й ступени входы младшего разряда п чисел при нечетном числе разрядов или выходы двухразряднрго модуля анализа последующих разрядов р-й ступени анализа при нечетном , ,2,..., S-1, не вошедшие в пару для подключения к модулю ансшиза (р+1)-ой ступени, подключены к входам младших разрядов двухразрядного модуля анализа

последующих разрядов (p+q)-n ступени, i-e выходы двухразрядного модуля анализа последующих разрядов последней ступени анализа -соединены с i-ми выходными шинами номера экстремального числа устройства и с i-ми управляющими входа1ми коммутатора, (п - 1 )-е выходы-первого одноразрядного и первого двухразрядного модулей анализа последующих разрядов, через первый и второй элементы-НЕ подключены к выходам соответственно т-го и (т-1) - го разрядов экстремального числа, выходы остсшьных разрядов экстремального числа соединены с соответствующими выходами коммутатора, информационные входил которого подключены к соответствукяцим входам остальных разрядов чисел.

УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ ЭКСТРЕМАЛЬНОГО .ЧИСЛА ИЗ пт-РАЗРЯДНЫХ ДВОИЧНЫХ ЧИСЕЛ, содержащее первый одноразрядный модуль анализа, имеющий п входов и п+1 выходов, т-1 двухразрядных модулей анализа последующих разрядов, имеющих п входов анализа старших разрядов, п входов анализа младших разрядов и п+1 выходов каждый, причем входы старшего (т-1)-го разряда п чисел устройства подключены к соответствующим входам первого одноразрядного модуля анализа, выходы которого подключены к соответствующим входам анализа старших разрядов первого двухразрядного модуля анализа последующих разрядов, входы м)1адших разрядов которого подключены к соответствующим входам . (т-2)-го разряда п чисел устройства, одноразрядный модуль анализа содержит элемент ИЛИ-НЕ и п элементов ИЛИ, первый вход i-ro элемента ИЛИ, где ,2,.. ., п, соединен с входом старшего разряда i-ro числа и i-м входом элемента ИЛИ-НЕ, а выход - с i-M выходом одноразрядного.модуля анализа, (п+1)-й выход которого под- ключен к выходу элемента ИЛИ-НЕ и вторым входам всех элементов ИЛИ, каждый двухразрядный модуль анализа последующих разрядов содержит элемент ИЛИ-НЕ и п групп элементов И, ИЛИ, включающих первый и второй элементы И и элемент ИЛИ, причем в каждой i-й группе элементов выход.первого элемента И соединен с первым входом элемента ИЛИ, выход которого подключен к первому входу второго элемента И, при этом первый вход первого элемента И i-й группы, где i 1,2,..., п, подключен к i-му входу анализа старших разрядов двухразрядного модуля анализа последующих разрядов и второму входу второго элемента И i -и группы, второй вход первого элемента И i-й группы подключен к i-му входу младших разрядов первого двухразрядного модуля анализа последующих разрядов, а выход - к соответствующему входу элемента ИЛИ-НЕ первого двухразрядного модуля анализа последующих разрядов, выход второго « элемента И подключен к i-му выходу первого двухразрядного модуля анализа последующих разрядов, (п+1)-и выход которого соединен с выходом элемента ИЛИ-НЕ первого двухразрядного модуля анализа последукхдих разрядов иЗ (вторыми входами элементов ИЛИ всех групп элементов И, ИЛИ, . т л и ч а ю щ е е с я тем, что, с целью повыше-. .ния быстродействия, в него введены -1 одноразрядных модулей анализа, два элемента НЕ и коглмутатор, где символ х есть целая часть чисСП ла .X, причем одноразрядные модули анализа объединены в нулевую ступень анализа, двухразрядные модули СО анализа последующих разрядов образуют т ступеней анализа по -j- модулей в каждой ступени-анализа, где ,2,...,, . где символ х есть такое наименьшее целое S, что S х, . входы j-го модуля нулевой ступени анализа, где j 2, 3,..., Г-у- подключены к одноименным входам (jn-2j«-1) -го разряда п чисел, входа анализа старших разрядов j-ro двухразрядного модуля анализа последукндих разрядов первой ступени соединены с сор тветствующими выходами j-ro модуля нуле

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

Известно устройство для сравнения чисел, содержащее п циклических регистров сдвига,- п элементов И, 10 элемент ИЛИ, при этом каждый циклический регистр сдвига прямым выходом подключен к соответствующему входу элемента ИЛИ, инверсным выходом - к первому входу соответствующего эле- 5 мента И, управляющим входом - к входу импульсов сдвига, входом установки О - к выходу -соответствующего элемента И, а выход элемента ИЛИ подключен к вторым входам всех элементов И Г1.. .

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

Наиболее близким по технической сущности к предлагаемому является устройство для выделения экстремального числа, содержащее m выходных элементов ИЛИ-НЕ и m поразрядных уз- 30 лов переноса, где m - число раэря- : дов в сравниваегых числах, а каждый поразрядный узел переноса состоит из п групп элементов И и ИЛИ, каждая группа элементов i-ro поразряд- 35 нога узла переноса, где ,2,...,n, i 2,3,.., m, состоит из одного элемента 1лПИ,т - i + 1 -го элемента И, а каждая j-я группа элементов первого поразрядного узла переноса состоит из одного элемента ИЛИ и (т-1)-го элемента И, причем во всех rpyrtnax элементов всех поразрядных узлов переноса первый вход элемента ИЛИ соединен с выходом выходного элемента ИЛИ-НЕ соответствуккдего разряда, а выход элемента ИЛИ подключен к первым входам элементов И той же группы элементов, выход каждого k-ro элемента И 1-й группы элементов i-r поразрядного узла переноса, где , 3,..,, m-Ci + l) , 1-2,3,..., п, 2,3,. .. ,m-1, соединен с вторым входом (i-«-1)-ro элемента И 1-й группы элементов ()-ro поразрядного узла переноса, а выход первого элемента И каждой j-ой группы элементов i-ro поразрядного узла переноса, где ,2, ...,п, i 1,2 ,..., m, подключены к одному из входов выходного элемента ИЛИ-НЕ соответствующего-разряда и к второму входу элемента ИЛИ j-й группы элементов (i+1)-ro поразрядного узла, второй вход элегданта ИЛИ каждой j-й группы элементов первого поразрядного узла переносов и входы первого выходного элемента ИЛИ-НЕ соединены с шиной первого разряда j-ro сравниваемого числа, вторые входы каждого р-го элемента И j-й группы элементов первого поразрядного узла переноса, где ,2,...,т, ,2,..., п, подключены к шине (р+ +1)-го разряда j-го сравниваемого числа, выходы i-ro элемента И каждой i-й группы элементов первого пораздэядного узла переноса, где i 2,3,....

m,j 1-,2,...,n, соединены с вторыми входами элементов и (1-1)-й группы элементов подключен к второму входу элемента ИЛИ j-й группы элементов второго поразрядного узла переноса, второй вход каждого (m-l)-ro элемента И j-й труппы элементов второго поразрядного узла переноса соединен с выходом элемента ИЛИ j-й группы элементов первого поразрядного узла переноса, а выходы элементов И всех Irpynn элементов т-го поразрядного узла переноса служат выходами устройства. В известном устройстве присутствуют одноразрядный и двухразрядный модули анализа п чисел. Одноразрядный модуль анализа образован элементом ИЛИ-НЕ 1 и элементами ИЛИ 4 первого поразрядного узла переноса.

Двухразрядный модуль анализа образует, например, элемент ИЛИ-НЕ 1 и п групп элементов из последовательно соединенных элемента И 5 первого узла переноса, элемента ИЛИ 4 элемента И 5 второго узла переноса каждая 2. .

Однако известное устройство имеет недостаточное быстродействие, так как выделение экстремального числа осуществляется последовательным поразрядным анализом чисел, поскольку модули анализа (поразрядные узлы переноса) включены последовательно.

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

Поставленная цель достигается тем что в устройство для выделения экстремального числа из nm-разрядных двоичных чисел, содержащее первый одноразрядный модуль анализа, имеющий п входов и п+1 выходов, т-1 двухразрядных модулей анализа последующих разрядов, имеющих п входов анализа старших разрядов, 11 входов анализа младших разрядов и выходов каждый, причем входы старшего (m-l)-ro разряда п чисел устройства подключены к соответствующим входам первого одноразрядного модуля анализа, выходы которого подключены к соответствующим входам анализа старших разрядов первого двухразрядного модуля анализа последующих разрядов, входы младших разрядов которого подключены к соответствующим входам (т-2)-го разряда п чисел устройства, одноразрядный модуль анализа содержит элемент ИЛИ-Н и п элементов ИЛИ, первый вход i-ro элемента ИЛИ, где 1 1 ,2 ,. . . ,п, соединен с входом старшего разряда i-ro числа и i-M входом элемента ИЛИ-НЕ, а выход - с 1-м выходом одноразрядного модуля анализа, ()-й выход которого подключен к выходу элемента ИЛИ-НЕ и вторым входам всех элементов ИЛИ,

каждый двухразрядный модуль анализа последующих разрядов содержит элемент ИЛИ-НЕ и п групп элементов И, ИЛИ, включающих первый и. второй эле-, менты и и элемент ИЛИ, причем в каждой i-й группе элементов выход первого элемента И соединен с первым входом элемента ИЛИ, выход которого подключен к первому входу второго элемента и, при этом первый вход первого элемента И i-й группы, где ,2, ..., п, подключен к i-му входу анализа старших раэрядов двухразрядного модуля анализа последующих разрядов и второму входу второго элемента. И i-й группы, второй вход первого элемента И i-й группы подключен к i-му входу- младших разрядов перво1чэ двухразрядного модуля анализа послеЬУКВДИХ разрядов, а выход - к соответствугацему входу элемента ИЛИ-НЕ первого двухразрядного модуля анализа последующих разрядов, выход второго элемента И подключен к i-му выходу первого двухразрядно- го модуля анализа последующих разрядов , (п+1)-и выход которого соединен с выходом элемента ИЛИ-НЕ первого двухразрядного модуля анализа последующих разрядов и вторыми входами элементов ИЛИ всех групп элементов И, ИЛИ, введены J3-J-1 одноразрядных модулей анализа, два элемента НЕ и коммутатор, где символ х} есть целая часть числа х, причем одноразрядные модули анализа двухразрядные модули анализа последующих разрядов образуют 5 1ой„т ступеней анализа по я- модулей в каждой

ступени анализа, где ,2,..., logjin, где символ такое наименьшее целое S, что входы j-ro модуля нулевой ступени анализа,

где ,3,..., Г подключены к одноименным входам (т-2j+l)-го разряда п чисел, входы нализа старших разрядов j-ro двухразрядного модуля анализа последующих разрядов первой ступени соединены с соответствующими выходами j-ro модуля нулевой ступени, а входы младших разря.чов - с одноменными вxoдa 4и (m-2j)-ro разряда п чисел, входы aHajmsa старших разрядов и входы младших разрядов 1-го двухраэрядного модуля анализа последующих разрядов k-й ступени анализа,

где ,2,..., ,3,..., S,

подключены к соответствующим выходам (I-l)-ro и 1-го двухразрядных модулей анализа последующих разрядов (k-1)-й ступени, входы младшего разряда п чисел при нечетном числе разрядов или выходы двухразрядного мо дуля анализа последующих разрядов р-й ступени анализа при нечетном Гя-1, ,2,...,S-l, не вошедшие в пару для подключения к модулю анализа (р--1)-й ступени, подключены к входам младших разрядов двухразрядного модуля анализа последующих разрядов (p-t-q)-ft. ступени, i-e выходы двухразрядного модуля анализа последующих разрядов последней ступени анализа соединены с i-ми выходными шинами номера экстремального числа устройства и с i-ми управляющими вхо дами коммутатора, (п+1)-е выходы пер вого одноразрядного и первого двухразрядного модулей анализа последующих разрядов через первый и второй элементы НЕ подключены к выходам соответственно п-го и (m-l)-ro разрядов экстремального числа, выходы остальных разрядов экстремального числа соединены с соответствующими выхо коммутатора, информационные вхо ды которого подключены к соответствующим входам остальных разрядов п чисел. На фиг.1 приведена схема устройст ва для вьаделения экстремального числ из п 8-разрядных двоичных чисел; на фиг.2 - схема первого.одноразрядного модуля анализа} на фиг.З схема первого двухразрядного модуля анализа последующих разрядов. Устройство для выделения э.кстремсшьного числа (фиг.1) содержит одноразрядные модули анализа 1 д , 12.0 Дэ,о.4,о нулевой ступени анализа, двухразрядные модули анализа последующих разрядов 2 ,2 2, 31 первой ступени анализа 2V,2 2 2 2 второй ступени анализа. - третьей ступени анализа, два элемента НЕ 3 и 4, коммутатор 5, информационные входы 6-| , г, n,if устройства, где , l,. .., l, выходы 7 ,... ,7,7 одноразрядного модуля анализа, выходы 8., ..., 8,8 двухразрядного модуля аналнза последующих разрядов выходы 9,... ,9 экстремального числа устройства, выходы 1о,...,10 номера экстремально го числа устройства. Первый одноразрядный модуль анализа 1 1,0 (фиг.2) содержит элемент ИЛИ-НЕ 11 и п элементов ИЛИ 12. Первый двухразрядный модуль анализа 2 -t,-i (фиг.З) содержит элемент ИЛИ-НЕ 13 и и групп элементов из последовательно соединенных первого элемента-И 14, элемента ИЛИ 15, второго элемента И 16 каждал.в общем случае нулевая ступень анализа содержит j модулей 1, где символ CX есть целая часть числа х, двухраз рядные модули анализа 2 распределены по S log2in ступеням анализа, где символ fx есть такое наименьшее целое S, что S / X. Входы нулевого разряда п чисел при нечетном m или выходы модуля j-й ступени при нечетном ут- (j 1,2, ... , S-1) , не вошедшие в пару для подключения к модулю ()-и ступени, подключаются к младшим входам модуля соответствующей старшей ступени. Устройство для выделения экстремального числа работает-следующим образом. На входы 6 (фиг.1) поступают коды nm-разрядных двоичных чисел в прямом виде при выделении максимального числа и в инверсном виде при выделении минимального числа (в устройстве на фиг.1 ). Первый одноразрядный модуль 1 о анализа нулевой ступени сравнения анализирует (m-l)-e (старшие) разряды чисел, поступающие на входы 6 j ,62,7 г-Г 6 п.т и формирует лргическую 1 (признак экстремально го числа по одному разряду на выходе 7-,(( 1,2 ,;;., пг, если старший разряд )с-го числа равен 1 или если старшие разряды п чисел равны б.Аналогичным образом i-й модуль 1 ,-д (,3, -..f -у- нулевой ступени анализа выявляет экстремальное число по разряду m -2 +1. Первый двухразрядный модуль анализа последующих разрядов 2 первой ступени анализа анализирует признаки экстремального числа, поступакядие на его старшие входы с выходов 1,1,,. 7„ модуля и (т-2;-е разряды чисел, поступа;ощие на его младшие входы с входов 6 , б2,б , ,.., 6 , и формирует логическую 1 (признак экстремального числа по двум разрядам J на выходе ,2,... ,п ,если на tt-м старшем и i -м младшем входах присутствует логическая 1 или если на старшем входе присутствует логичес - кая 1 а на всех входах логической О. Аналогичным образом 1-й модуль 2|. (1 2,3,..., п ГтК первой ступени анализа формирует признак экстремального числа по разрядам т-21+1 и т-21. Точно также 1-й модуль 2ij ,j-fi ступени анализа (1 1,2-j , j 2,3,..., S анализирует признаки, поступающие на его старшие входы с выходов (21-1)-го модуля, на младще входы - с выходов 21-го модуля ()-1)-й ступени анализа и формирует признак экстремального числа по разрядам с. (m-2ji)-ro по fm-2j(i-1). Входы нулевого разряда при нечетом m или выходы модуля j-й ступени ри нечетном Л (,2,..., S-1) стаются без пары для подключения к одулю (;--1)-й ступени. В этом слуае они подключаются к младшим входам модуля соответствующей старшей ступени. Модуль 2 последней ступени анализа выделяет экстремальное число по всем m разрядам п чисел и формирует логическую 1 на соответству ющем выходе Ю, 10 ,. .., 10, номера экстремального числа. Сигналы с этих выходов поступают на управляющие входы коммутатора 5, который ком мутирует на выходы 9д, 9,..., 95 нулевой, первый, ..., {т-3)-й разряды экстремального числа, выделенные согласно номеру экстремального числа из указанных разрядов всех чисел, . поступающих на информационные входы коммутатора 5 с соответствуквдих входов 6 . Старший (т-1)-й разряд экстре мального числа выделяется на выходе 7,. модуля1 дИ через элемент НЕ 3 выдаетсяна выход 9т , (т-2)-й разряд экстремального числа выделяет ся на выходе 8n+-i модуля 2 -( и через элемент НЕ 4 выдается на выход 9 В одноразрядном модуле анализа (фиг.2) ИЛИ-НЕ 11 выявляет состо яние старших разрядов чисел, поступа ющих на входы , ,62, t,-1 И формирует на выходе 7 ), (инверсный выход старшего разряда экстремального числа) логическую 1, если старшие разряды чисел равны О, и логичес кий О, если старший разряд хотя бы одного числа равен 1. В результате на выходах 7 ,7 ,..., 7 элементов ИЛИ 12 присутствует логическая 1, если старшие разряды чисел равны О,в противном случае коды старших чисеТГ с входов 6 через элементы ИЛИ 12 передаются на выходы 7 без изменений. т.е. модуль 1 формирует признаки экстремсшьного числа по старшему раз ряду. Остальные модули 1 работают аналогично, с тем лишь отличием,что их выход 7р в схеме устройства не используется, i В двухразрядном модуле анализа 2 (фиг.З) первый элемент И 14 (,2,..,,n) образует конъюнкцию а-, bj, где сигнал на старшем входе 7,-, Ь - сигнал на младшем входе 6g , а элемент ИЛИ-НЕ 13 формирует логическую 1 на выходе 8 (инверсный выход (т-2)-,го разряда экстремального числа), если все конъ юнкции равны логическому О, и логический О, если хотя бы одна из конъюнкций равна логической 1. В результате на выходах элементов . ИЛИ 15, 15v ,.. ., 15 присутствует Jibf .гическая 1, если на выходах всех элементов И 14 присутствует логический О, в противном случае сигналы с выходов элементов И 14 проходят на выходы элементов ИЛИ 15 без изменений. Элемент И 16. {1 },2,..,, п) объясняет по И сигнал на старшем входе 7; с ВЕЛХодным сигналом элемента ИЛИ 15 и образует на Bbixojqe если а. или логическую , ,j, . . . ,, или и при , т.е. модуль 2. формирует признаки экстремального числа по сигналам на его старших и младших входах. Остальные модули 2 работают аналогично, с тем лишь отличием, что их выход 7 „ц. в схеме устройства не используется. Повышение быстродействия в предлагаемом устройстве достигается сочетанием параиплельного сравнения чисел в каждой ступени с последовательным включением ступеней анализа, при этом используется одна ступень одноразрядного анализа и S log2m3 ступеней двухразрядного анализа. В одноразрядном модуле анализа (фиг.2) сигнал проходит две ступени задержки , в двухраэрядном модуле анализа (фиг.З) ,- четыре ступени задержки, в результате задержка выделения номера экстремального числа на выходах 10 устройства (фиг.1) равна t(Z+ 4S)r, , где Т - задержка распространения сигнала в одном элементе И, или ИЛИ, или ИЛИ-НЕ. Коммутатор 5 может быть выполнен на элементах И, ИЛИ, при этом элементы И коммутируют разряды чисел, а элементы ИЛИ объединяют выходы тех элементов И, которые коммутируют одноименные разряды чисел. В результате код -экстремального числа формируется с дополнительной задержкой .2Т. В прототипе в каждом узле переноса сигнал проходит три ступени задержки, поэтому номер экстремального числа выделяется с задержкой , так как узлы переноса включены последовательно, а код экстремального числа - с задержкой (3m-2)f . Выигрыш в быстродействии предла- гаемого устройства по сравнению с прототипом в случае 8-разрядных чисел равен 1,7 по выделению номера экстремального числа и 1,4 по выделению кода экстремального числа, С ростом количества разрядов существенно растут и выигрыши по быстродействию, причем без дополнительных затрат оборудования, так как введенные коммутатор, элементы НЕ, т-1 одноразрядные модули сравнения реализуются на меньшем числе элементов схемы по сравнению с элементами и в прототипе, через которые на следующий узел переноса проходят не участвующие в анализе разряды чисел. Испытания макетов базового образца , за который принято устройство С2, и предлагаемого устройства показывают работоспособность и эффективность предлагаемого устройства.