Устройство для сравнения к @ -разрядных чисел

 

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - расширение функциональных возможностей за счет обеспечения выделения выборочного квантиля для любого количества чисел. Устройство содержит ячейки анализа 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 табл.

союз соВетсних

СОЦИАЛИСТИЧЕСНИ1(° РЕСПУБЛИН (19) (И) (51)5 С 06 F 7/04

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А BTQPCHQMY СВИДЕТЕЛЬСТВУ

Фис. 1

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ пРи Гннт сссР (21) 4606640/24-24 (22) 1 7,,11 ° 88 (46) 23.08. 90. Бюл. М 31 (72) О.П. Орлов, А.В. Тихомиров, Г.В. Волков и Т.Н. Чернейкина (53) 681.325.5 (088.8) (56) Авторское свидетельство СССР

Р 851401, кл. G 06 F 7/04, )979, Авторское свидетельство СССР

М - 1282115, кл. G 06 F 7/04, 1985.

2 (54) УСТРОЙСТВО ДЛЯ СРАВНЕНИЯ К и-РАЗРЯДНЪ|Х ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике. Цель изобретения — расширение функциональ-. ных возможностей за счет обеспечения выделения выборочного квантиля для любого колнчества чисел. Устройство содержит ячейки анализа 1 -1„,каждая ячейка анализа содержит группу эле1587492

10 ментов И-HE 2»-2<», группу элементов равнозначности 3<-3, группы элементов И 4»-4<,, 5<-5<, блоки уплотнения 6,7, коммутатор 8, элемент HF. 9, выходы разрядов выделенного числа

10 -10»,, информационные входы 11

ll, входы переноса 12»-12„, входы маски 13 »-13, выходы переноса 14<—

14,, выходы маски 15<-15 . На входы 11 подаются двоичные коды аналиИзобретение относится к автоматике и вычислительной технике и может быть использовано при создании цифровых систем переработки информации. 20

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

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

Устройство содержит ячейки 1» -1, анализа, каждая ячейка анализа содер-. жит группу элементов И-НЕ 2» -2<„ груп-30 пу элементов 3» Зк равнозначности, группы элементов И 4»-4 < и 5» -5<, блоки б и 7 уплотнения, коммутатор 8,элемент НЕ 9, выходы 10» -10», разрядов выделенного числа, информационные 35 входы 11» - 11п, входы 12,-12 „ переноса, входы 13,-13<» маски, выходы 14»вЂ”

14»< переноса, выходы 15» -15» маски.

Блок уплотнения содержит матрицу из К ° (К-1)/2 ячеек 16, состоящих из 40 элементов И 17 и ИЛИ 18. Блок 6 уплотнения преобразует К-разрядный двоичный код, содержащий q единиц и (К вЂ” q) нулей в код, в котором в разрядах с первого по q-й содержатся

45 единицы, а в разрядах с (q+! )-го по

К-й нули. Блок 7 преобразует такой же код таким образом, что в разрядах с первого по (К-q)-й находятся нули, а в разрядах с.(K-q+1)-ro по К-й еди- 50 ницы.

Если на К-м выходе блока 7 уплотнения — единичный сигнал, то на выходе коммутатора 8 формируется код, поступающий с выхода блока 7, а если нулевой сигнал — то код . поступающйй с входа 12 переноса. зируемых чисел (первый разряд является старшим), на входы 13» — единичные сигналы, на входы 12 — код "m,из К" уплотненный в сторону старших разрядов, где m — параметр квантиля, т.е. номер числа по величине. Например, для выделения третьего по величине числа на входы 12< подается код

11100...0, m можно задавать в пределах 1 < ш « К, 2 ил., 1 табл.

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

Запуск устройства осуществляется установкой на входах 13» уровней логической единицы, подачей на входы 12» потенциалов кода выделяемого квантиля в коде "m из К", уплотненном в сторону старших разрядов, где

m — параметр квантиля, т.е. номер числа по величине. Например, если требуется выделить третье по величине число из массива на входы 12 » подается код 11100...0. На входы

11 i-й ячейки I, анализа поступают

i-е разряды анализируемых чисел. На выходах элементов И-НЕ 2 группы устанавливается инверсный код поразрядной конъюнкции соответствующего разрядного столбца анализируемых чисел с соответствующей входной разрядной маской. Количество нулей в этом коде соответствует количеству подлежащих анализу в данной ячейке (с учетом информации разрядного столб" ца) чисел. Единицы этого кода подвергаются уплотнению в сторону младших разрядов в блоке 6 уплотнения. В элементах И 5 производится поразрядная конъюнкция уплотненного таким образом кода с кодом соответствующего разрядного квантиля, поступающего с входов

12. С выходов элементов И 5 группы на вход блока 7 уплотнения поступает код, количество единиц в котором равно разности количества единиц входного разрядного квантиля 12 и количества нулей в блоке уплотнения, если эта разность положительна. В этом случае на выходе старшего разряда блока 7 уплотнения устанавливается уровень логической единицы и коммутатор 8 пропускает. на входы 12 следующей ячейки

1 анализа код с выходов блока 7 уп5 15 лотнения. В противном случае на входы 12 следующей ячейки проходит .значение входного квантиля данной ячейки. Управляющий уровень с выхода старшего разряда блока 7 уплотнения проходит также на вторые входы элементов 3 равнозначности группы и через элемент НЕ на разрядный выход 10 ячейки анализа. Посредством элементов 3 равнозначности группы и элементов И 4 группы с учетом значения сигналов на выходе старшего разряда блока уплотнения производится последующая корректировка входной разрядной маски. Новая разрядная маска с выходов элементов И 4 первой группы проходит на входы 13 разрядной маски следующей ячейки 1 или, если данная ячейка — это ячейка анализа младшего разряда, — на выходы

15 устройства, на которых устанавливается позиционный адрес чисел, равных числу, найденному в процессе анализа и код которого устанавливается на выходах 10 ус-;рой".òBà., Пример. Рассматривают совокупность чисел: 5, 3, 7, 1, 5, 2 и 4.

В этом случае устройство для выделения выборочного квантиля из семи чисел содержит три ячейки 1 анализа.

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

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

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

i-го разряда маски j-ячейки анализа (где j = l 2,...,(п-l)) соединены соответственно с первым входом переноса (3+1)-й ячейки анализа и входом

i-го разряда маски (j + 1)-й ячейки анализа, первый выход переноса п-й

-ячейки анализа является первым выхо87492

5 !

0 !

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

i-го элемента И-HE группы, выход которого соединен с -м входом первого блока уплотнения и с первым входом

i-го элемента равнозначности, выход которого соединен с вторым входом

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

Р = 2,3,...,К) соединен с первым входом P-ro элемента И первой группы, i-й выход первого блока уплотнения соединен с вторым входом i-го элемента И первой группы, выход котоI рого соединен с i-м входом второго блока уплотнения, -й выход которо-. го соединен с (К + 1 — i)-м информационным входом первой группы коммутатора, управляющий вход которого соединен с К-м выходом второго бло-. ка уплотнения, вторыми входами элементов равнозначности и входом элемента HE, i-й вход переноса ячейки

I анализа соединен с х-м информационным входом второй группы коммутатора, i-й выход которого является

i-м выходом переноса этой ячейки анализа, P-й вход переноса первой ячейки анализа является P-м входом переноса устройства, P-й выход переносa j-й ячейки анализа соединен с

P-м входом переноса (j + 1)-й ячейки анализа, P-й выход переноса п-й ячейки анализа является P-м выходом переноса устройства, вход 1-ro разряда i-го числа устройства, где 1 1,. ...,n, соединен с вторым входом i-го

1587492

Значение результата в блоке анализа разряда

Элемент младшего

)з старшего

1 второго

I ?

Ill)Ill . 1010)0I l000101

0110010 1111100

))10000 1100000

0101010 1101111 011101) 0000111 Oil)Ill 00)l)ll

0110000 0000000

1100000 0000000

1100000 1100000

Разрядный информационный вы0 ход

Выходы элементов 3 равнозначности

Выходы первой группы элементов И 4

10)0101 1101)11 1000100

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

Входы 13 разрядной маски.

Разрядные входы 11 1010101

Входы 12 1110000

Выходы группы элементов ИНЕ 2

Выходы блока G уплотнения

Выходы элементов И 5 0000000

Выходы бло— ка 7 уплотнения 0000000

Выходы коммутатора 8 1110000 является выходом 1-го разряда выделенного числа устройства °

1587492.

Фиг,2

Составитель В. Горохов

Редактор Н, Бобкова Техред М.Дидык

Корректор О. Кравцова

Заказ 2420 Тираж 565 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СЧСР

113035, Москва, iK-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101