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

СОЮЗ СОВЕТСКИХ СОЦИАЛИСТИЧЕСКИ ЕСПУБЛИК 9)5 О 06 Р 7/О ОБРЕ АНИ ЛЬСТВУ ОМУ СВИ лектронной тех И. Полянин ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(54) УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ МЕДИАНЫ ПОСЛЕДОВАТЕЛЬНОСТИ ИЗ ПЯТИ ЧИСЕЛ(57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных системах обработки информации, предназначенных для сортировки данных в реальном масштабе времени. Целью изобретения является упрощение устройства при выделении медианы из последовательности чисел. Устройство содержит регистры 1 - 4, 9 - 11, схемы 5-8 сравнения, блок 12 постоянной памяти, группы элементов И 13,.17. Последовательность чисел в параллельном коде поступает на информационный вход 18 устройства, причем каждое число стробируется импульсом по тактовому входу 19. После прихода каждого тактового импульса в устройстве накапливается информация о результатах попарного сравнения последних пяти чисел, поступивших на устройство, а хранятся эти числа в регистрах 1 - 4. На выходах компараторов 5-8 и регистров 9-11 формируется управляющее слово, в котором содержится информация о том, какое число является медианой последовательности. С помощью блока 12, где хранится таблица преобразования, управляющее слово преобразуется в сигнал на одном из выходов данных блока 12, который поступает на разрешающий вход одной из групп элементов И 13-17, по которому медиана поступает на выход 20 устройства. 1 ил, 1 табл.Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных системах обработки информации, предназначенных для сортировки массивов данных в реальном масштабе времени.Целью изобретения является упрощение устройства при выделении медианы из последовательности чисел,На чертеже показана схема устройства.Устройство для выделения медианы последовательности из пяти чисел содержит регистоы 1 - 4, схемы 5 - 8 сравнения, регистры 9-11, блок 12 постоянной памяти, группы элементов И 13 - 17, информационный вход 18 устройства, тактовый вход 19 устройства, вь 1 ход 20,Устройство работает следующим образом,Последовательность чисел в параллельном коде поступает на информационный вход 18 устройства и тактируются импульсами, поступающими на тактовый вход 19 устройства. При каждом тактовом импульсе число с информационного входа 18 записывается в первый регистр 1, число из которого переписывается во второй регистр 2, содержимое которого переписывается в третий регистр 3, содержимое последнего переписывается в четвертый регистр 4. В момент поступления числа на информационный вход устройства, на выходах схем 5-8 ,сравнения сформированы сигналы, уровни которых зависят от результатов сравнения числа на информационном входе устройства с числами, записанными в регистрах 1 - 4. С приходом тактового импульса эта информация записывается в пятый регистр 9, а с приходом двух последующих тактовых импульсов переписывается в шестой 10 и седьмой 11 регистры с уменьшением числа передающихся разрядов на единицу,После прихода четырех тактовых импульсов первое число находится в четвертом регистре, второе, ретье и четвертое числа находятся в третьем, втором и первом регистрах соответственно, пятое число находится на информационном входе устройства, в седьмом регистре находится результат сравнения первого и второго чисел, в шестом регистре находятся результаты сравнения первого с третьим и второго с третьим чисел, в пятом регистре находятся результаты сравнения четвертого числа с первым, вторым и третьим числами, на выходах схем 5-8 сравнения сформированы результаты сравнения пятого числа с первым, вторым, третьим и четвертыми числами,5 10 15 20 25 30 35 40 45 50 55 Таким образом, в устройстве сформирована вся информации для определения соотношения между пятью числами, которая ввиде управляющего слова поступает на адресные входы блока 12 постоянной памяти, где хранится таблица преобразования, с помощью которой управляющее слово преоб разуется в активный сигнал на одном из пяти выходов данных, который поступает на разрешающий вход соответствующей группы элементов И 13 - 17, по которому медиана пяти чисел поступает на выход устройства 20, При поступлении пятого тактового импульса в устройстве пропадет. информация, связанная с первым числом, на информационном входе устройства находится шестое число, на выходах схем 5 - 8 сравнения и регистров 9 - 11 формируется информация о попарных сравнениях чисел с второго по шестое, а на выход устройства поступает медиана набора из этих чисел и т. д.Алгоритм работы блока 12 постоянной памяти заключается в анализе ста двадцати различных ситуаций, возникающих при сравнении пяти произвольных чисел. Число перестановок и чисел равно и 1, Следовательно, имеют 51=120 различных векторов, поступающих на адресные входы блока 12 постоянной памяти, Для каждого из этих вполне определено место медианы входного набора чисел. Поэтому на выходе блока 12 постоянной памяти формируется позиционнь код, который определяет местонахождение числа, являющегося медианой. Таблица представляет собой таблицу программирования блока 11 постоянной памяти, выполненного на одной микросхеме ПЗУ 556 РТ 7. При этом используются десять разрядов адреса и пять разрядов данных. Всего программируется 120 ячеек памяти, адреса которых приведены в таблице. Остальные ячейки программируются произвольно или не программируются совсем.Рассмотрим в качестве примера случай когда на информационный вход 18 устройства поступила последовательность чисел "1", "2", "4", "3, "5", причем первые четыре числа стробировались тактовыми импульсами по тактовому входу 19 устроиства, Тогда на выходах схем 5 - 8 сравнения формируются логические уровни "О", "0, "0", "О", на выходах первого, второго и третьего разрядов пятого регистра 9 формируются сигналы 1", "О", "О", на выходах первого и второго разрядов регистра 10 имеются сигналы "0", "О", на выходе седьмого регистра 11 - сигнал "О". Таким образом, на адресные входы блока 12 постоянной памяти поступает вектор 0000000100. Из таблицы видно, что при этом активизируется второй выход блока 12, 1683005поэтому открывается вторая группа элементов И 14, и на выход поступает число "3", находящееся в данный момент в первом регистре 1 и являющееся медианойпоступившей на устройство последовательности,Формула изобретения.Устройство для выделения медианы последовательности из пяти чисел, содержащее четцг:е схемы сравнения, блок постоянной памяти, причем выходы больше первой - четвертой схем сравнения соединены соответственно с входами первого - четверого разрядов адреса блока постоянной памяти,отлича ющеесятем,что,с целью упрощения устройства при выделении медианц из последовательности чисел, оно содержит семь регистров, пять групп элементов И, причем информационные входц устройства подключены к информационным входам первого регистра, первым входам элементов И первой группы и входам первых групп всех схем сравнения, входы вторых групп которых подключены соответственно к выходам разрядов первого - четвертого регистров, тактовые входы которых являются тактовым входом устройства и соединены с тактовыми входами пятого, шестого и седьмого регистров, выходы разрядов первого регистра соединены с информационными входами второго регистра и первыми входами элементов И второй группы, выходы разрядов второго регистра соединены с информационными входами третьего регистра и первыми входами элементов И третьей группы, выходы разрядов 5 третьего регистра соединены с информационными входами четвертого регистра и первыми входами элементов И четвертой группы, выходы разрядов четвертого регистра соединены с первыми входами элемен тов И пятой группы, выходы первой, второйи третьей схем сравнения соединены соответственно с входами первого, второго и третьего разрядов пятого регистра, выходы первого и второго разрядов которого соеди нены с входами первого и второго разрядов. шестого регистра, выход первого разрядакоторого соединен с входом первого разряда седьмого регистра, выходы первого, второго и третьего разрядов пятого регистра 20 соединены с входами соответственно пятого, шестого и седьмого разрядов адреса блока постоянной памяти, входы восьмого, .девятого и десятого разрядов адреса которого подключены соответственно к выходам 25 первого и второго разрядов шестого регистра и первого.разряда седьмого регистра, выходы разрядов данных блока постоянной памяти соединены с вторыми входами элементов И соответственно первой - пятой 30 групп, выходы элементов И которых обьединены по ИВИ и являются информационным выходом устройства,1683005 Адрес 1 ЗУ Выход ПЗУ 00100 00100 00001 00010 00010 00001 01000 01000 01000 01000 00001 00010 01000 01000 00001 00100 00010 00100 СОС 10 00001 00100 00100 00001 00010 01000 01000 000 О 00100 00100 00010 01000 01000 0000 00100 00100 00001 10000 10000 10000 10000 01000 01000 00001 000 1.0 00010 00001 10000 10000 10000 10000 10000 1000010000 10000 00001 00010 000 О 00001 001000000000000 0000000001 0000000011 0000000100 0000000110 0000000111 0000001011 0000001111 0000010100 0000010110