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

г,

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - расширение функциональных возможностей за счет обеспечения выделения выборочного квантиля для любого количества чисел. Устройство содержит ячейки анализа 1 1 - 1 N, каждая ячейка анализа содержит группу элементов И-НЕ 2 1 - 2 K, группу элементов равнозначности 3 1 - 3 K, группы элементов И 4 1 - 4 K, 5 1 - 5 K, блоки уплотнения 6, 7, коммутатор 8, элемент НЕ 9, выходы разрядов выделенного числа 10 1 - 10 N, информационные входы 11 1 - 11 N, входы переноса 12 1 - 12 K, входы маски 13 1 - 13 K, выходы переноса 14 1 - 14 K, выходы переноса 15 1 - 15 K. На входы 11 подаются двоичные коды анализируемых чисел (первый разряд является старшим), на входы 13 1 - единичные сигналы, на входы 12 1 - код "M из K", уплотненный в сторону старших разрядов, где M - параметр квантиля, т.е. номер числа по величине. Например, для выделения третьего по величине числа на входы 12 1 подается код 11100...0, M можно задавать в пределах 1 ≤ M ≤ K. 2 ил. 1 табл.

А. ю,

п„

JOn

5ут

(Л

ел

00

3

я

Фиг.}

т;

ментов И-НЕ , группу элементов равнозначности 3,-3j;, группы элементов И ,, , блоки уплотне Ш1Я 6,7, коммутатор 8, элемент НЕ 9, выходы разрядов выделенного числа 10,-10, информационные входы 11.- 11 j, входы переноса ,, входы маски ц , выходы переноса 14,- 14, выходы маски- 15,-15. На вх ды 11 подаются двоичные коды аналиИзобретение относится к автоматике и вычислительной технике и может быть использовано при создании цифровых систем переработки информации.

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

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

Устройство содержит ячейки анализа, каждая ячейка .анализа содержит группу элементов И-НЕ ,, груп пу элементов равнозначности, группы элементов И | и 5.,-5к, блоки 6 и 7 уплотнения, коммутатор 8 элемент НЕ 9, выходы , разрядов выделенного числа, информационные входы 1 1 (- 1 Ц , входы 1 2,-1 2 ( переноса, входы 1 3,-1 3 ( маски, выходы 14)4 переноса, выходы 15(-15 маски.

Блок уплотнения содержит матрицу из К«(К-1)/2 ячеек 16, состоящих из элементов И 17 и ИЛИ 18. Блок б уплотнения преобразует К-разрядный двоичный код, содержащий q единиц и (К - q) нулей,в код, в котором в разрядах с первого по q-й содержатся едиьшцы, а в разрядах с (q+l)-ro по К-й нули. Блок 7 преобразует такой же код таким образом, что в разрядах с первого по (K-q)-й находятся нули, а в разрядах c.(K-q+l)-ro по К-й еди ницы.

Если на К-м выходе блока 7 уплотнения - единичный сигнал, то на вы- ходе коммутатора 8 формируется код, поступающий с выхода блока 7, а если нулевой сигнал - то код, поступающий с входа 12 переноса.

874924

I зируемых чисел (первый разряд является старшим), на входы 13 - единичные сигналы, на входы 12 - код т .из К с уплотненный в сторону старших разрядов, где m - параметр квантиля, т.е. номер числа по величине. Например, для выделения третьего по величине числа на входы 12 подается код jQ 11100,..0. m можно задавать в пределах . 2 ил,, 1 табл.

5

0 0

5

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

Запуск устройства осуществляется установкой на входах 13 уровней логической единицы, подачей на входы 12 потенциалов кода выделяемого квантиля в коде т из К, уплотненном в сторону старших разрядов, где m - параметр квантиля, т.е. номер числа по величине. Например, если требуется выделить третье по величине число из массива, на входы 12 подается код 1100.,.0. На входы 11 j i-й ячейки Ij анализа поступают i-e разряды анализируемых чисел. На выходах элементов И-НЕ 2 группы устанавливается инверсный код поразрядной конъюнкции соответствующего разрядного столбца анализируемых чисел с соответствующей входной разрядной маской. Количество нулей в . этом коде соответствует количеству подлежащих анализу в данной ячейке (с учетом информации разрядного столбца) чисел. Единицы этого кода подвергаются уплотнению в сторону младших разрядов в блоке 6 уплотнения. В элементах И 5 производится поразрядная конъюнкция уплотненного таким образом кода с кодом соответствующего разрядного квантиля, поступающего с входов 12. С выходов элементов И 5 группы на вход блока 7 уплотнения поступает код, количество единиц в котором равно разности количества единиц входного разрядного квантиля 12 и количества нулей в блоке уплотнения, если эта разность положительна, В этом случае на выходе старшего разряда блока 7 уплотнения устанавливается уровень логической единицы и коммутатор 8 пропускает, на входы 12 следующей ячейки 1 анализа код с выходов блока 7 уплотнения. В противном случае на входы 12 следующей ячейки 1 проходит значение входного квантиля данной ячейки. Управляющий уровень с выхода старшего разряда блока 7 уплотнения проходит также на вторые входы элементов 3 равнозначности группы и через элемент НЕ на разрядный выход 10 ячейки анализа. Посредством элементов 3 равнозначности группы и элементов И U группы с учетом значения сигналов на выходе старшего разряда блока уплотнения производится последующая корректировка входной разрядной маски. Новая разрядная маска с выходов элементов И 4 пер- вой группы проходит На входы 13 разрядной маски следующей ячейки I или если данная ячейка - это ячейка анализа младшего разряда, - на выходы 15 устройства, на которых устанавливается позиционньш адрес чисел, равных числу, найденному в процессе анализа и код которого устанавливается на выходах 10 устройства.,

Пример. Рассматривают совокупность чисел: 5, 3, 7, 1, 5, 2 и 4 В этом случае устройство для выделения выборочного квантиля из семи чисел содержит три ячейки 1 анализа.

Результаты обработки данной последовательности чисел при m 3, т.е. при выделении третьего по величине числа, приведены в таблице.

Формула изобретения

Устройство для сравнения К п-раз- рядных чисел, содержащее п ячеек анализа , каждая из которых содержит первую и вторую группы из К элементов И каждая, группу из К элементов И-НЕ и элемент НЕ, причем первый вход переноса устройства и вход i-ro разряда маски устройства, где i .1 2 К, соединены соответственно с первьм входом переноса первой ячейки анализа и входом i-ro разряда маски первой ячейки анализа, первый выход переноса j-й ячейки анализа и выход i-ro разряда маски j-ячейки анализа (где j 1,2, ...,(п-1)) соединены соответственно с первым входом переноса (j+l)-й ячейки анализа и входом 1-го разряда маски (j + 1)-й ячейки анализа, первый выход переноса п-й -ячейки анализа является первым выхо874926

дом переноса устройства, выход i-ro разряда маски п-й ячейки анализа является выходом i-ro разряда маски уст- роиства, в каждой ячейке анализа ее первый вход переноса соединен с первым входом первого элемента И пер- вой группы, вход i-ro разряда маски этой ячейки анализа соединен с пер- 10 вым входом i-ro элемента И второй группы, выход которого является выходом 1-го разряда маски этой ячейки анализа, отличающееся тем, что, с целью расширения функцио15

20

5

нальных возможностей за счет обеспечения выделения выборочного квантиля для любого количества чисел, в каждую ячейку анализа введены первый и второй блоки уплотнения, группа из К элементов равнозначности и коммутатор причем вход i-ro разряда маски ячейки анализа соединен с первым входом 1-го элемента И-НЕ группы, выход которого соединен с i-м. входом первого

блока уплотнения и с первым входом i-ro элемента равнозначности, выход которого соединен с вторым входом i-ro элемента И второй группы, Р-й 30 вход переноса ячейки анализа (где

) соединен с первым

входом Р-го элемента И первой группы, 1-й выход первого блока уплотнения соединен с вторым входом i-ro 35 элемента И первой группы, выход которого соединен с i-м входом второго блока уплотнения, i-й выход которого соединен с (К -f 1 - )-„ . мационным входом первой группы коммутатора, управляющий вход которого соединен с К-м выходом второго бло-, ка уплотнения, вторыми входами элементов равнозначности и входом эле- мента НЕ, i-й вход переноса ячейки анализа соединен с i-м информацион- ным входом второй группы коммутатора, 1-й выход которого является 1-м выходом переноса этой ячейки Q анализа, Р-й вход переноса первой ячейки анализа является Р-м входом переноса устройства, Р-й вькод переноса j-й ячейки анализа соединен с Р-м входом переноса (j + 1)-й ячей- 5 ки анализа, Р-й выход переноса п-й ячейки анализа является Р-м выходом переноса устройства, вход 1-го разряда 1-го числа устройства, где 1--1

..,,п.

соединен с вторым входом i-ro

элемента И-НЕ группы 1-й ячейки анализа , выход элемента НЕ 1-й ячейки анализа

Входы 13 разрядной

маски 1111111 Разрядные

входы 11 101010 Входы 12 1110000 Выходы группы элементов ИНЕ 2 0101010 Выходы блока б уплотнения 0000111 Выходы элементов И 5 0000000 Выходы блока 7 уплотнения 0000000 Выходы коммутатора 8 1110000

Разрядньп информационный выход 1 Выходы элементов 3 равнозначности 1010101 Выходы первой группы элементов И 4 1010101

является выходом 1-го разряда выделенного числа устройства.

1010101 1000101

ОПООЮ lllilOO 1110000 1100000

1 101111 oil 1011

01 nil 001 1 1 11 0110000 0000000

1 100000 0000000 и 00000 1100000

llOnil 1000100

1000101 1000100

фиг.2