Устройство для выделения выборочной медианы из @ чисел Советский патент 1987 года по МПК G06F7/06 G06F17/18 

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

Целью изобретения является повы- . шение быстродействия.

На фиг. 1 представлена схема предлагаемого устройства в случае m7/7j где in - количество п-разрядных двоичных чисел; на фиг. 2 и 3 - узлы анализа первого и второго типов; на фиг. 4 и 5 - частные случаи схемы устройства при и на фиг.6 - схема устройства для случая .

Устройство для выделения выборочной медианы из jn чисел содержит входы 1.,..., анализируемых чисел, m прямых преобразователей (ФП) 2 п-раз- рядного двоичного кода в 2 -разряд m-l ный код -т- групп узлов анализа, кажv

дая из koTopbix состоит из первьпс

т-1 ,

--- узлов 3 и одного узла 4, обратного преобразователя 2 -разрядного кода в п-разрядный двоичный код (ФП) 5, подключенного выходами к выходам 6 устройства.

Узел 3 (фиг, 2) содержит ментов ИЛИ 7-и 2 элементов

2 эле- И 8.

Узел 4 (фиг. 3) содержит 2 элементов ИЛИ 7.

ФП 2 и ФП 5 являются известными средствами вычислительной техники и могут быть вьшолнены по различным схемам известными методами, например с помощью программируемой логической матрицы, постоянного запоминающего устройства, запрограммированного таким образом, что двоичному п-разряд- ному коду А на адресных входах соответствует ячейка содержащая 2 -раз- рядный код, содержащий единигцз в первых А разрядах и нули в остальных разрядах, ФП может быть выполнен известными методами в- виде ком™ бинациоиной схемы.

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

Двоичные коды анализируемых чисел поступают на входы 1 устройства. Код А, поступает на вход l-ro (1 l,.,,,m) ФП 2. При этом на выходах

40

т-1 ключится -г- наименьших чисел из m

рассматриваемых.

Но выборочная медиана из m чисел 35 является наименьшим числом из

ш+1

которые остались после

--- чисел.

ш-1

прохождения групп узлов 3, 4.

В силу поразрядного соединения вызсодов последней группы узлов 3, 4 происходит поразрядная логическая операция И (Монтажное соединение И) Поэтому специальный код, соответст- 45 вующий выборочной медиане из тп чисел, останется на входах ФП 5.

Наконец, обратным преобразованием в ФП 5 специального кода на выходах 6 устройства получим двоичный 50 код выборочной медианы.

Пример. Пусть , а на входах 1 устройства находятся двоичные коды 1, 5, 6, 4, 7, 5, 6 (фиг. 6),

Тогда в первой группе узлов анализи- ФП 2 формируется специальный двоичный 55 РУются числа 1, 5, 6, 4, 7, предста- код, содержащий логические единицы вленные в специальных кодах, и из

в первых А разрядах и нули в остальных 2 -А разрядах. Большему числу на входах 1 соответствует большее

рассмотрения исключается число 1.

Во вторую группу узлов на дальнейший анализ с первой группы прой

число единиц на выходах связанного с ними ФП 2.

Коды с выходов ФП 2 поступают в узлы 3 и 4 анализа. Из двух специальных кодов, поступающих в узел 3, больший код через схемы ИЛИ 7 узла проходит на первые выходы, а меньший код через схемы И 8 - на вторые выходы узла 3.

Из двух кодов, поступающих в узел 4 анализа, на его первые выходы проходит большой код, а меньший код исключается из дальнейшего рассмотрения .

По алгоритму работы устройства (фиг. 1) в первой группе узлов 3, 4

пИ-3

сравниваются чисел. В этой группе из дальнейшего рассмотрения ис. m-t-3 ключается наименьшее из -г- чисел.

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

тп-ьЗ

Так как таких групп узлов

. чисел.

0

т-1 2

0

ТО после срабатывания последней группы узлов из рассмотрения ист-1ключится -г- наименьших чисел из m

рассматриваемых.

Но выборочная медиана из m чисел 5 является наименьшим числом из

ш+1

которые остались после

--- чисел.

ш-1

прохождения групп узлов 3, 4.

В силу поразрядного соединения вызсодов последней группы узлов 3, 4 происходит поразрядная логическая операция И (Монтажное соединение И), Поэтому специальный код, соответст- 5 вующий выборочной медиане из тп чисел, останется на входах ФП 5.

Наконец, обратным преобразованием в ФП 5 специального кода на выходах 6 устройства получим двоичный 0 код выборочной медианы.

Пример. Пусть , а на входах 1 устройства находятся двоичные коды 1, 5, 6, 4, 7, 5, 6 (фиг. 6),

рассмотрения исключается число 1.

Во вторую группу узлов на дальнейший анализ с первой группы прой3

дут числа 5, 6, 4, 75-3 также добавится число 5. Наименьшее число 4 из чисел, сравниваемых во второй группе узлов, будет исключено из дальнейшего рассмотрения, а в следующую (третью) группу узлов будут допущены на анализ числа 6, 5, 7 и 5, а taKKe добавится число 6. Но число 5 - наименьшее из сравниваемых чисел поэтому одно из чисел 5 будет исклн - чено из рассмотрения, а на выходах последней группы узлов анализа останутся специальные коды чисел 6, 7,

5,6. В силу поразрядного соединения выходов последней группы узлов 3, 4 происходит поразрядная логическая операция И (Монтажное соединение

и). В результате из набора чисел

6,7, 5, 6, представленных в вьте- указанном специальном коде, вьщелит- ся минимальный код, соответствующий числу 5,

Специальный код числа 5, после преобразования в ФП 5 в двоичный код числа 5, поступает на выходы 6 устройства.

Таким образом, на выходах 6 устройства выделяется код выборочной медианы из 7 чисел.

Формула изобретения Устройство для выделения выборочной медианы из ш чисел, (т - нечетное число),содержащее п групп узлов анализа, п-разрядность анализируемых

т+1 чисел по -т- узлов анализа

в группе, причем в каждой группе перт-1

вые у- -: узлов анализа содержат

три элемента И и три элемента ИЛИ, а

m+l

-j- -и узел анализа содержит один элемент ИЛИ, в каждой группе узлов анали- за первый вход первого .элемента И . i-ro узла анализа, где ,3,...,- соединен с выходом первого элемента И (i-l)-ro узла анализа, отличающееся тем, что, с целью повышения быстродействия в устройство введены m прямых преобразователей п- -разрядного двоичного кода в 2 -разрядный код и одного обратного преобразователя 2 -разрядного кода

. т-1

в п-разрядньи двоичный код, --- -п,

Vl групп узлов анализа, в первые -г

22

узлов анализа каждой группы введены

2-3 элементов И и элементов

Q

5

т+1 „ -2- -и

анализа

0

5

О

5

0

.ИЛИ, в --- -и узел

каждой группы введены элементов ИЛИ, причем входы анализируемых чисел устройства подключены к входам соответствующих прямых преобразователей п-разрядного двоичного кода в 2 -разрядный код, в каждой группе узлов анализа первые входы элементов И с второго по 2 i-ro узла анализа соединены с выходами элементов И соответственно с второго по (i- -1)-го узла анализа, первые входы S-X элементов И и ИЛИ первых

1ТГ-1

-г- -X узлов анализа каждой группы объединены, s-й выход j-ro прямого преобразователя п-разрядного двоичного кода в 2 -разрядный (где

„-I о о -о т+1,

s-l, ; ,...,---) соединенс вторыми входами s-x злементов ИЛИ И (j-l)-ro узла анализа первой груп„ /m+l ,. пы, s-й выход (--- +k)-ro прямого

преобразователя п-разрНдного двоичного кода в 2 -разрядный код (k

10 m-K

1,/,...,---; соединен с первым входом s-ro элемента ИЛИ (--т)-го узла

анализа k-й группы, б-й выход, перво-. го прямого преобразователя п-разрядного двоичйого кода в 2 -разрядный подключен к первым входам s-x элементов И первого узла анализа первой группы, в k-M узле анализа i-й группы вторые входы S-X элементов ИЛИ объединены с вторыми входами s-x элементов И и подключены к выходам s-x элементов ИЛИ (k+l)-ro узла анализа (i-1)-и,Труппы, первый вход j-ro элемента ИЛИ первого узла анализа 1-й группы подключен к выходу s-ro элемента ИЛИ первого узла анализа (i-1)-й группы, выход s-ro элемента

И (-2-)-го узла анализа каждой группы соединен с вторым входом s-ro элемента ИЛИ (---)-го узла анализа этой группы, выходы S-X 3JieMeHTOB ИЛИ всех узлов анализа --- -и группы объединены и подключены к s-му входу обратного преобразователя 2 -разрядного кода в п-разрядный двоичный код, выходы которого являются выходами устройства.

Фив, 2

фиг.З

1:

-П1Н

(put. f

tj-j -Ц}

Изобретение относится к автоматике и вычислительной технике и может быть использовано при создании цифровых систем переработки информации. Целью изобретения является повышение быстродействия. Устройство содержит m прямых преобразователей 2п-разрядного кода в 2 -разрядный код (где m - количество п-разрядных двоичных чисел), один обратный преобразователь 5 2 -разрядного кода в т-1 п-разрядный код, -т- групп узлов анализа по 3,4-2 анализа в группе. Прямой преобразователь кодов преобразует п-разрядный двоичный код А в 2 -разрядный код, содержащий единицы в первых А разрядах и нули в остальных . разрядах. Схема устройства позволяет проводить одновременный анализ всех разрядов анализируемых чисел. 6 ил. (Л Гт

OHIKO

s f

1

г УСоставитель В.Журавлев Редактор М.Бандура Техред И.Подович Корректор М.Пожо

Заказ 3391/46 Тираж 672Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий П3035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

D- CFIF4IF