Устройство для выделения выборочной медианы из @ чисел

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) ((1) (S1)4 (; 06 F 15/36

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

4иг

3 @+3

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4026297/24-24 (22) 21.02.86 (46) 30.07.87. Бюл. У 28 (71) Институт технической кибернетики АН БССР (72) М.М.Маханек, В .E.×åðíÿâñêèé, А.Г.Ярусов и П.Н.Бибнло (53) 681.3(088.8) (56) Авторское свидетельство СССР

В 746501, кл. С 06 Р 7/02, 1978.

Авторское свидетельство СССР

У 1211717, кл. G 06 F 7/02, 1984. (54) УСТРОЙСТВО gJIK ВЦЦЕЛЕНИЯ ВЫБОРОЧНОЙ МЕДИАНЫ ИЗ m ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике и мо кет быть использовано при создании цифровых систем переработки информацин. Целью изобретения является повышение быстродействия. Устройство содерхит m прямых преобразователей л

2п-разрядного кода в 2 -разрядный код (где m — - количество и-разрядных двоичных чисел), один обратный преобразователь 5 2 -разрядного кода в

m-l п-разрядный код †- групп узлов

2 ш+1 анализа по 3 4 — узлов анализа в

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

Схема устройства позволяет проводить 1а одновременный анализ всех разрядов анализируемых чисел. 6 ил.

С:

1 132

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

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

На фиг, 1 представлена схема предлагаемого устройства в случае m >i 7, где m - количество и-разрядных двоичных чисел; на фиг. 2 и 3 — узлы анализа первого и второго типов; на фиг. 4 и 5 — частные случаи схемы . устройства при ш 3 и m=5; на фиг.6— схема устройства для случая m=7.

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

m-1 —.- узлов 3 и одного узла 4„обратноЬ го преобразователя 2 -разрядного кода в п-разрядный двоичный код (ФП)

5, подключенного выходами к выходам

6 устройства. узел 3 (фиг. 2) содержит 2" элементов ИЛИ 7-и 2" элементов И 8.

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

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

2"-А разрядах, ФП может быть выполнен известными методами в виде комбинационной схемы.

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

Двоичные коды анализируемых чисел поступают на входы 1 устройства, Код А поступает на вход 1-ro (1=

1,...,m) ФП 2. При этом иа выходах

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

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

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

Из двух кодов, поступающих в узел

4 анализа, на его первые выходы проходит большой код, а меньший код исключается иэ дальнейшего рассмотре15 ниЯ

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

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

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

m+3 чисел. Так как таких групп узлов

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

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

35 является наименьшим числом из ш+1 †-- чисел которые остались после

2 ш-1 прохождения -«2- групп узлов 3, 4.

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

Поэтому специальный код, соответст45 вующий выборочной медиане иэ ш чисел, останется на входах ФП 5.

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

50 код выборочной медианы.

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

Тогда в первой группе узлов аналиэи55 руются числа il 5, 6, 4, 7, представленные в специальных кодах, и иэ рассмотрения исключается число 1.

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

5 — наименьшее из сравниваемых чисел, 1О поэтому одно из чисел 5 будет исключено иэ рассмотрения, а на выходах последней группы узлов анализа останутся специальные коды чисел 6, 7, 5, 6.

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

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

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

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

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

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

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

m+1 чисел по вЂ, — узлов анализа

2 в группе, причем в каждой группе nepm-1 40 вые — — - узлов анализа содержат

Z три элемента И и три элемента ИЛИ, а ш+! †- -й узел анализа содержит один эле 2 мент ИЛИ,.в каждой группе узлов анали- 45 за первый вход первого элемента И . ш-1 х-го узла анализа, где д=2,3,..., 2 соединен с выходом первого элемента И (i-1)-ro узла анализа, 5Î о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия в устройство введены ш прямых преобразователей поразрядного двоичного кода в 2"-разрядный код и одного обратного преобразователя 2 -разрядного кода 55

m-1 в и-разрядный двоичный код, — — -и, m-l групп узлов анализа, в первые ——

22

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

2"-3 элементов И и 2 -3 элементов ш+1

ИЛИ в — — -й узел анализа

У 2 каждой группы введенъ 2"-1 элементов

ИЛИ, причем входы анализируемых чисел устройства подключены к входам соответствующих прямых прейбраэователей и-разрядного двоичного кода в

2 -разрядный код, в каждой группе узлов анализа первые входы элементов

И с второго по 2" i-ro узла анализа соецинены с выходами элементов И соответственно с второго по 2 -1 (iu»

-I )-го узла анализа, первые входы

s-x элементов И и ИЛИ первых ш-1 — — -х узлов анализа каждой

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

s=l 2,...,2; j =2,...,— -) соединенс вторыми входами s-x элементов ИЛИ

И (j-1)-ro узла анализа первой rpynm+1 пы s-й выход (— — +k)-ro прямого

У

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

m-1

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

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

i-й группы подключен к выходу s-го элемента ИЛИ первого узла анализа (i-1)-й группы, выход s-ro элемента ш-!

И (†-)-ro узла анализа каждой груп2 пы соединен с вторым входом s-го элеm+1 мента ИЛИ (†-)-го узла анализа

2 этой группы, выходы з-х элементов

ИЛИ всех узлов анализа — — -й груп2 пы объединены и подключены к s-му входу обратного преобразователя

2"-разрядного кода в и-разрядный двоичный код, выходы которого являются выходами устройства.

1327122

1327?22 фие, Ф фиа. 5

Фиа.б

Составитель В.Журавлев

Редактор М.Бандура Техред И.Попович

Корректор М.Пожо

Тираж 672 Подписное

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

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

Заказ 3391/46

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