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

(51)4 С; 06 Г 15/3 ЫЙ КОМИТЕТ СССРРЕТЕНИЙ И ОТНРЫТИИ ГОСУДАРСТВЕНПО ДЕЛАМ И ОПИСАНИЕ ИЗОБРЕТЕН К АВТОРСКОМУ С яется потройствоователейзрядныйразрядныхтный прего кода в ю изобретения явл ыстродействия. Ус ш прямых преобраэл ого кода в 2 -ра ш - количество и- чисел), один обрафлель 5 2 -разрядно цин. Цель ььцпение б содерхит 2 п-разряди код (где двоичных образова дный к(71) Институт технической кибернетики АН БССР(56) Авторское свидетельство СССР В 746501, кл. С 06 Р 7/02, 1978.Авторское свидетельство СССР 1 Ф 1211717, кл. С 06 Р 7/02, 1984. (54) УСТРОЙСТВО ДЛЯ ВЦЦЕЛЕНИЯ ВЫБОРОЧНОЙ МЕДИАНЫ ИЗ ш ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано при создании цифровых систем переработки информап-раэря од, в - групп узловш+1анализа по 3 4 - узлов анализа в2группе. Прямой преобразователь кодов преобразует и-разрядньй двоичный код А в 2 -разрядный код, содерваащий единицы. в первых А разрядах и нули в остальных 2"-А, разрядах. Схема устройства позволяет проводить одновременный анализ всех разрядов анализируемых чисел. 6 ил.132Изобретение относится к автоматике и вычислительной технике и можетбыть использовано при создании цифровых систем переработки информации.Целью изобретения является повышение быстродействия.На фиг, 1 представлена схема предлагаемого устройства в случае шт 7,где 1 п - количество и-разрядных двоичных чисел; на фиг. 2 и 3 - узлыанализа первого и второго типов; нафиг. 4 и 5 - частные случаи схемы, устройства при ш 3 и щ=5; на фиг.б -схема устройства для случая щ=7.Устройство для выделения выборочной медианы иэ ш чисел содержит входы 11, анализируемых чисел, щпрямйх преобразователей (ФП) 2 и-разьрядного двоичного кода в 2 -разрядщ ный код, -- групп узлов анализа, каждая из Которых состоит из первыхш- ,- узлов 3 и одного узла 4 обратноЬго преобразователя 2 -разрядного кода в п-разрядный двоичный код (ФП)5, подключенного выходами к выходам6 устройства,Узел 3 (фиг. 2) содержит 2" элементов ИЛИ 7 и 2" элементов И 8.Узел 4 (фиг. 3) содержит 2" элементов ИЛИ 7.ФП 2 и ФП 5 являются известными средствами вычислительной техники и могут быть выполнены по различным схемам известными методами, например с помощью программируемой логической матрицы, постоянного запоминающего устройства, запрограммированного таким образом, что двоичному и-разрядному коду А иа адресных входах соответствует ячейка, содержащая 2"-разрядный код, содержащий единицы в первых А разрядах и нули в остальных 2"-А разрядах, ФП может быть выполнен известными методами в виде комбинационной схемы.Устройство работает следующим образом.Двоичные коды анализируемых чисел поступают на входы 1 устройства, Код А поступает на вход 1-го (1= "1ш) ФП 2. При этом иа выходах ФП 2 формируется специальный двоичный код, содержащий логические единицы в первых А разрядах и нули в остальных 2 -А разрядах. Большему числу на входах 1 соответствует большее 122число единиц ка выходах связанногос ними фП 2,Коды с выходов фП 2 поступают вузлы 3 и 4 анализа. Иэ двух специальных кодов, поступающих в узел 3,больший код через схемы ИЛИ 7 узлапроходит капервые выходы, а меньшийкод через схемы И 8 - ка вторые выходы узла 3.10Из двух кодов, поступающих в узел4 анализа, на его первые выходы проходит большой код, а меньший код исключается иэ дальнейшего рассмотрения,По алгоритму работы устройства(фиг, 1) в первой группе узлов 3, 4пН 3сравниваются -- чисел, В этой груп 2пе из дальнейшего рассмотрения ис. ш+3ключается наименьшее из -- чисел.2Аналогично после каждой группы узлов анализа из дальнейшего рассмотрения будет исключаться каждый раэпо одному числу - наименьшему иэш+3чисел. Так как таких групп узлов2ш то после срабатывания послед 30ней группы узлов из рассмотрения исш ключится 2 наименьших чисел из щрассматриваемых.Но выборочная медиана из щ чисел35 является наименьшим числом изш+1- - чисел которые остались после2ш прохождения -2- групп узлов 3, 4.40 В силу поразрядного соединениявыходов последней группы узлов 3, 4происходит поразрядная логическаяоперация И (кМонтажное соединение И"),Поэтому специальный код, соответст 45 вующий выборочной медиане иэ ш чисел,останется на входах ФП 5.Наконец, обратным преобразованием в ФП 5 специального кода на выходах 6 устройства получим двоичный50 код выборочной медианы.П р и м е р, Пусть шф а на входах 1 устройства находятся двоичныекоды 1, 5, 6, 4, 7, 5, 6 (фиг. 6).Тогда в первой группе узлов аналиэи 55 руются числа 1, 5, 6, 4, 7, представленные в специальных кодах, и иэрассмотрения исключается число 1.Во вторую группу узлов на дальнейший анализ с первой группы прой1327 дут числа 5, 6, 4, 7, .а также добавится число 5, Наименьшее число 4 из чисел, сравниваемых во второй группе узлов, будет исключено из даль 5 нейшего рассмотрения, а в следующую (третью) группу узлов будут допущены на анализ числа 6, 5, 7 и 5, а также добавится число 6. Но число 5 - наименьшее из сравниваемых чисел, 1 О поэтому одно из чисел 5 будет исключено иэ рассмотрения, а на выходах последней группы узлов анализа останутся специальные коды чисел 6, 7, 5, 6.15В силу поразрядного соединения выходов последней группы узлов 3, 4 происходит поразрядная логическая операция И (" Монтажное соединение И"), В результате из набора чисел 6, 7, 5, 6, представленных в вышееуказанном специальном коде, выделится минимальный код, соответствующий числу 5.Специальный код числа 5, после преобразования в ФП 5 в двоичный код числа 5, поступает на выходы 6 устройства.Таким образом, на вьходах 6 устройства выделяется код выборочной медианы из 7 чисел. 25 Формула изобретенияУстройство для выделения выборочной медианы иэ ш чисел. (ш - нечетное число), содержащее и групп узлов анализа, и-разрядность анализируемыхш+1чисел по в , - узлов анализа2в группе, причем в каждой группе первг 1 40 вые -- узлов анализа содержат2три элемента И и три элемента ИЛИ, а ш+1в - -й узел анализа содержит один элемент ИЛИ,в каждой группе узлов анали за первый вход первого элемента И. вд-го узла анализа, где д=2,3.2соединен с выходом первого элемента И (д)"го узла анализа,50 о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия в устройство введены ш прямых преобразователей поразрядного двоичного кода в 2"-разрядный код и одного обратного преобразователя 2 -разрядного кода 55шв и"разрядный двоичный код, -- -и,шгрупп узлов анализа, в первые -"224узлов анализа каждой группы введены 2" -3 элементов И и 2 -3 элементовш+1ИЛИ в -- -й узел анализа2каждой группы введены 2"-1 элементов ИЛИ, причем входы анализируемых чисел устройства подключены к входам соответствующих прямых преОбраэователей и-разрядного двоичного кода в 2 -разрядный код, в каждой группе узлов анализа первые входы элементов И с второго по 2" д-го узла анализа соецинены с выходами элементов И соответственно с второго по 2 -1 (дь -1)-го узла анализа, первые входы в-х элементов И и ИЛИ первых ш-- -х узлов анализа каждой 2группы объединены, в-й выход 3-го прямого преобразователя п-разрядного двоичного кода в 2"-разрядный (гдеш+1 в=1, 2 2; 3=2 - -) соединенс вторыми входами в-х элементов ИЛИ И (1-1)-го узла анализа первой групш+1пы в-й выход ( -- +1)-го прямогоУ2преобразователя и-разрядного двоичЬного кода в 2 -разрядный код (Мш=1,2 ) соединен с первым вхош+1 дом в-го элемента ИЛИ ( в в .)-го узла2 анализа 1-й группы, в-й выход. перво-. го прямого преобразователя и-разрядлного двоичйого кода в 2 -разрядный подключен к первым входам в-х элементов И первого узла анализа первой группы, в 1-м узле анализа д-й группы вторые входы в-х элементов ИЛИ объединены с вторыми входами в-.х элементов И и подключены к выходам в-х элементов ИЛИ +1)-го узла анализа (д)-й;группы, первый вход 1-го элемента ИПИ первого узла анализа д-й группы подключен к выходу в-го элемента ИЛИ первого узла анализа (д)-й группы, выход в-го элементаш-И ( в -)-го узла анализа каждой груп 2пы соединен с вторым входом в-го элеш+1мента ИЛИ ( в -)-го узла анализа2этой группы, выходы в-х элементов ИЛИ всех узлов анализа -- -й груп 2 пы объединены и подключены к в-му входу обратного преобразователя 2"-разрядного кода в п-разрядный двоичный код, выходы которого являются выходами устройства, 1327122327 ги иа,б ставитель В.Журавле хред И.Попович орректор М.Пожо Редактор М.Бандура аказ 3391/4 Тираж 67ИИПИ Госуда делам из 5, Москва П рственного комитета СССРобретений и открытий