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

(19) И 1) ц С Об Р 7/О ПИСАНИЕ ИЗОБРЕТЕНИЯд ВТОРСНОМУ СВИДЕТЕЛЬСТВУе сти электрон В.10. ДуВ.И. Пол8.8) ровин,нин о СССР 1986,СССР 1987,идетельс 06 Р 7/О етельств 06 Р 7/О ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ГКНТ СССР(71) Московский иной техники(54) УСТРОЙСТВО ДЛЯ ВСЕЛЕНИЯ 10:ДИАНЫ ПЯТИ ЧИСЕЛ(57) Изобретение относится к автоматике и внчислительной технике и может бить испольэовано в специализированных системах обработки информации, предназначенных для сортировки массивов данных в реальном масштабе времени. Предлагаемое устройство для выделения медианы пяти чисел содержит десять компараторов 1-10, блок 11 постоянной памяти, коммутатор 12.,Входные числа в параллель1594520 51015 ном коде поступают на компараторы 110, где происходит их попарное сравнение, ятакже на входы каналов ком-.мутатора 12. На выходах компараторов1-10 Формируется управляющее слово,в котором содержится инФормяция отом, ня какой из входов 13-1 устройства поступило число, являющеесямедианой входного набора чисел. С помощью блока 11 постоянной памяти,где хранится таблица преобразования,управляющее слово преобразуется втрехразрядный код адреса, который,поступает на входы. разрядов адреса Изобретение относится к автоматикеи вычислительной технике и может бытьиспользовано в специализированныхсистемах обработки инФормации, предназначенных для сортировки массивовданных в реальном масштабе времени.Целью изобретения является повышение быстродействия устройства засчет параллельной обработки входных чисел.На чертеже представлена структурная электрическая схема устройства.Устройство для выделения медианыпяти чисел содержит первый 1, второй 352, третий 3, четвертый 4, пятый 5шестой 6, седьмой 7, восьмой 8, девятый 9 и десятый 10 компараторы,блок 11 постоянной памяти, коммутатор 12, входы первого 13, второго 4014, третьего 15, четвертого 16 и пятого 17 чисел устройства и выход 18,Устройство работает следующим образом.,45Входные числа в параллельном коде поступают на первый 1 - десятый 10компараторы, где происходит их попарное сравнение, а также на входы каналов коь 1 мутатора 12. На выходахкомпараторов 1-10 Формируется управляющее слово, в котором содержится инФормяция о том, ня какой из входов устройства,13-17 поступило числоявляющееся медианой входного набора55чисел. С помощью блока 11 постояннойпамяти, где хранится таблица преобра-.зования, управляющее слово преобразу;,ется в трехрязрядный код адреса, кокоммутатора 12 и определяет номер канала, по которому медиана пяти чиселпоступит ня выход устройства 18. Выполнение устройства для выделения медианы пяти чисел в соответствии с .предлагаемым техническим решением позволяет повысить быстродействие устройства за счет параллельной обработки всего входного набора чисел и немедленной передачи на выход медианынабора путем переключения многоканального коммутатора в соответствии срезультатом параллельной обработки.1 ил,торый поступает ня входы разрядов адреса коммутатора 12 и определяет номер канала, по которому медиана.пя" ти чисел поступает ня выход устройства 18.Предлагаемое устройство для выделения медианы пяти чисел в отличие от известного, где выделение медианы происходит в результате последо-. вательных попарных сравнений и пересылки входных чисел, позволяет повысить его быстродействие за счет па-. раллельной обработки всего входного набора чисел и немедленной передачи на выход медианы набора путем переключения многоканального коммутатора в соответствии с результатом параллельной обработки.Алгоритм работы блока 11 постоянной памяти заключается в анализе ста двадцати различных ситуаций,. возникающих при сравнении пяти произвольных чисел. Число перестановок и чисел равно и, следовательно получают 120 различных векторов, Формирующихся на схемах 1-10 сравнения и поступающих на адресные входы блока 11 постоянной памяти. Для каждого из этих случаев вполне определено место медианы входного набора чисел. Поэтому на,вьгходе блока 11 постоянной памяти Формируется номер входного канала, по которому поступило число, яв-, ляющееся медианой.В таблице приведены данные программирования блока 11 постоянной памяти, выполненного на одной микросхеме ПЗУ 556 РТ 7. При этом исноль4520 десятого компаратора и четвертомувходу данных коммутатора, вторыми .входами седьмого, девятого и десятого компараторов и с пятым входом данных комму атора, выходы компараторовс первого по десятый соответственноподключены к входам с первого по десятый блока постоянной памяти, выходы которого соединены с управляющими входами коммутатора, выходы которого я-ляются выходами устройства. 510 Номер информационноговхода мультиплексора Адрес ПЗУ ыход ПЗУ 0000000000 0000000001 0000000011 0000000100 0000000110 0000000111 0000001011 0000001111 0000010100 0000010110 0000011110 0000011111 0000100000 0000100001 0000101001 0000101011, 00001100000000110100 ОООО 1000 40 50 5 159 зуются десять рдзрлдов адреса и три разряда данных. Нсего программируется 120 ячеек памяти, адреса которых приведены в таблице. Остальные ячейки программируются произвольно или не программируются совсем.П р и и е р . На входы .13-17 устройства поступают соответственно числа "1" "2" "4" "3" "5" При эт мУ Э Эна выходах компараторов 1-10 ФормиИЛН 11 Ю1 Ю И 4 , Ил 1 Игй ветственно. На адресные входы ПЗУ поступает вектор 0000000100, По таблице находят в четвертой строке, что на выходе ПЗУ в этом случае Формируется управляющее слово 011, что приводит к переключению коммутатора на четвертый канал, где находится число 1 13 , которое и является медианой входного массива,Формула изобретения Устройство для выделения медианы пяти чисел, содержащее компараторы с первого по девятый, причем входы первого и второго чисел устройства соответственносоединены с первым и вторым входами первого компаратора, вход третьего числа устройства соединен с первым входом второго компаратора, вход четвертого числа устройства соединен с первым входом третьего компаратора, о т л и ч а ю щ е- . е с я тем, что, с целью повышения быстродействия, в него дополнительно введены десятый компаратор, коммутатор и блок постоянной памяти, причем вход пятого числа устройства соединен с первым входом четвертого компаратора, первый вход первого компаратора подкл 1 очен соответственно к вторым входам второго, третьего и четвертого компараторов и к первому входу данных коммутатора, второй вход первого компаратора соответственно подключен к первым входам пятого, шестого и седьмого компараторов и второму входу данных коммутатора, первый вход второго компаратора соответственно, подключен к второму входу пятого ком-, паратора, первым входам восьмого и девятого компараторов, третьему входу данных коммутатора, первый вход третьего компаратора соответственно подключен к вторым входам шестого и восьмого компараторов,.первому входу 0000111001000011101100001111000000111110000011111100010010110001001111000101111100011010110001111011.000111111100100101000010010110001001111000,10110100.00101111000010111110001101111000110111110011111110 010 010 100 011 011 100 001001 001 00 1 100 011 001 001 100 010 011 010 011 100 010 010 100 011 001 001 011 010 010 011 001001 100 010 010 100 000 000 000 3 3 5 4 5 2 2 2 2 5 4 2 2 5, 3 4 3 4 5 3 5 4 2 2 4 3 3 4 2 2 5 3 3 5 1 1 1.1594520 Продолжение таблицы Продолжение таблицы 5 000 000 000 000 000 100 011 011 100 001 001 Составитель В. ЖуравлевТехред МХоданич Корректор М. Шароши Редактор И. Дербак Заказ 2829 Тираж 565 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., д. 4/5 комбинат "Патент", г.ужгород, ул. Гагарина,101 Производственно-издательский 001111111 0100,100000 0100100001 0100101001 0100110000 0100111000 0100111001 ,0101101001 0101101011 0101111001 О 101111011 0110110000 0110110100 0110111000 0110111100 0111111000 0111111001 0111111011 0111111100 0111111110 0111111111 1000000000 1000000001 1000000011 ;1000000100 1000000110 1000000111 1001000011 100100011.1 1001001011 1001001111 1010000100 1010000110 .1010010100 1010010110 1 О 11 ООО 11 О 1011000111 1011001111 1011010110, 1011011110 1011011111 001 001 100 011 011 100 000 000 000 000 000 000 000 000 100 011 011 100 010 010 010 010 100 011 011 100 000 000 000 000 1 2 .2 5 4 4 5 1 1 1 1 1 1 1 1 5 4 4 5 3 3 3 3 4 4 5 1 1 1 1 1 1 1 1 5 4 4 5 2 2 1 О 15 го 25 30 35 40 45 110000000011000000011100100000.11001000011101000001110100001111010010111101100001110110100111011010111110000000111000010011100101001110100000,111011000011101101001111000000111100000111110000111111000100111100011011110001111111001011111001111111.101010011110101101111011110111101111111111000001111100001111110100111111010111111110000111111010011111110001111111001111111101111111110011111111101111111111 000 000 000 000 100 010 010 100 001 001 011 010 010 011 001 001 011 100 010 010 100 011 010 011 010 100 001 001 011 100 001 001 001 001 100 011 011 100 010 010. 1 1 1 1 5 3 3 5 2 2 3 .3 4 2 2 4 5 3 3 4 3 4 3 5 2 2 4 5 2 2 2 2 4 4 5 Э Э