Устройство для выделения медианы последовательности из пяти чисел
Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных системахобработкиинформации , предназначенных для сортировки данных в реальном масштабе времени. Целью изобретения является упрощение устройства при выделении медианы из последовательности чисел. Устройство содержит регистры 1-4, 9-11, схемы 5-8 сравнения, блок 12 постоянной памяти, группы элементов И 13..17. Последовательность чисел в параллельном коде поступает на информационный вход 18 устройства, причем каждое число стробируется импульсом по тактовому зходу 19. После прихода каждого тактового импульса в устройстве накапливается информация о результатах попарного сравнения последних пяти чисел, поступивших на устройство, а хранятся эти числа в регистрах 1-4. На выходах компараторов 5-8 и регистров 9-11 формируется управляющее слово, в котором содержится информация о том, какое число является медианой последовательности . С помощью блока 12, где хранится таблица преобразования, управляющее слово преобразуется в сигнал на одном из выходов данных блока 12, который поступает на разрешающий вход одной из групп элементов И 13-17. по которому медиана поступает на выход 20 устройства. I ил, 1 табл.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (я)з 6 06 F 7/06
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4644983/24 (22) 01.02.89 (46) 07.10.91. Бюл. hh 37 (71) Московский институт электронной техники (72) А. В. Смирнов, Б. И. Полянин и В. А.
Григорович (53) 681.325(088. 8) (56) Авторское свидетельство СССР
ЬЬ 1348820, кл. 0 06 F 7/06, 1987.
Авторское свидетельство СССР
М 1586580, кл. 6 Об F 7/06, 26.03.89. г (54) УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ МЕДИАНЫ ПОСЛЕДОВАТЕЛЬНОСТИ ИЗ ПЯТИ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных системах обработки информации, предназначенных для сортировки данных в реальном масштабе времени. Целью изобретения является упрощение устройства при выделении медианы из последовательSU 1683005 А1 ности чисел. Устройство содержит регистры
1 — 4, 9 — 11, схемы 5-8 сравнения, блок 12 постоянной памяти, группы элементов И
13,.17. Последовательность чисел в параллельном коде поступает на информационный вход 18 устройства, причем каждое число стробируется импульсом по тактовому входу 19. После прихода каждого тактового импульса в устройстве накапливается информация о результатах попарного срав-: нения последних пяти чисел, поступивших на устройство, а хранятся эти числа в регистрах 1 — 4. На выходах компараторов 5-8 и регистров 9-11 формируется управляющее слово, в котором содержится информация о том, какое число является медианой последовательности. С помощью блока 12, где хранится таблица преобразования, управляющее слово преобразуется в сигнал на одном из выходов данных блока 12, который поступает на разрешающий вход одной из групп элементов И 13-17. по которому медиана поступает на выход 20 устройства. 1 ил, 1 табл.
1683005
Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных системах обработки информации, предназначенных для сортировки массивов 5 данных в реальном масштабе времени.
Целью изобретения является упрощение устройства.при выделении медианы из последовательности чисел, На чертеже показана схема устройства. 10
Устройство для выделения медианы последовательности из пяти чисел содержит регистры 1 — 4, схемы 5 — 8 сравнения, регистры 9-11, блок 12 постоянной памяти, группы элементов И 13 — 17, информационный вход 15
18 устройства, тактовый вход 19 устройства, выход 20, Устройство работает следующим obpaзам, Последовательность чисел в параллель- 20 ном коде поступает на информационный вход 18 устройства и тактируются импульсами, поступающими на тактовый вход 19 устройства. При каждом тактовом импульсе число с информационного входа 18 записы- 25 вается в первый регистр 1, число из которого переписывается во второй регистр 2, содержимое которого переписывается в третий регистр 3, содержимое последнего переписывается в четвертый регистр 4. В 30 момент поступления числа на информационный вход устройства, на выходах схем 5-8 ,сравнения сформированы сигналы, уровни которых зависят от результатов сравнения числа на информационном входе устрайст- 35 ва с числами, записанными в регистрах 1 — 4.
С приходом тактового импульса эта информация записывается в пятый регистр 9, а с приходом двух последующих тактовых им- пульсов переписывается в шестой 10 и седь- 40 мой 11 регистры с уменьшением числа передающихся разрядов на единицу, После прихода четырех тактовых импульсов первое число находится в четвер- 45 том регистре, второе, третье и четвертое числа находятся в третьем, втором и первом регистрах соответственно, пятое число находится на информационном входе устройства, в седьмом регистре находится 50 результат сравнения первого и второго чисел, в шестом регистре находятся результаты сравнения первого с третьим и второго с третьим чисел, в пятом регистре находятся результаты сравнения четвертого числа с 55 первым, вторым и третьим числами, HG вы" ходах схем 5-8 сравнения сформированы результаты сравнения пятого числа с первым, вторым, третьим и четвертыми числами.
Таким образом, в устрой тве сформирована вся информации для определения соотношения между пятью числами, которая н виде управляющего слова поступает на адресные входы блока 12 постоянной памяти, где хранится таблица преобразования, с помощью которой управляющее слово преоб разуется в активный сигнал на одном Из пяти выходов данных, который поступает на разрешающий вход соответствующей группы элементов И13 — 17, па которому медиана пяти чисел поступает на выход устройства
20, При поступлении пятого тактового импульса в устройстве пропадет. информация, связанная с первым числом, на информационном входе устройства находится шестое число, на выходах схем 5 — 8 сравнения и регистров 9 — 11 формируется информация о попарных сравнениях чисел с второго по шестое, а на выход устройства поступает медиана набора из этих чисел и т. д.
Алгоритм работы блока 12 постоянной памяти заключается в анализе ста двадцати различных ситуаций, возникающих при сравнении пяти произвольных чисел. Число перестановок и чисел равно п!. Следовательно, имеют 51=120 различных векторов, поступающих на адресные входы блока 12 постоянной памяти, Для каждого из этих вполне определено место медианы входного набора чисел. Поэтому на выходе блока
12 постоянной памяти формируется позиционнь.: код, который определяет местонахождение числа, являющегося медианой.
Таблица представляет собой таблицу программирования блока 11 постоянной памяти, выполненного на одной микросхеме ПЗУ
556РТ7. При этом используются десять разрядов адреса и пять разрядов данных. Всего программируется 120 ячеек памяти, адреса которых приведены в таблице. Остальные ячейки программируются произвольно или не программируются совсем.
Рассмотрим в качестве примера случай, когда на информационный вход 18 устройства поступила последовательность чисел
"1", "2 ", "4", "3, "5", причем первые четыре числа cTpGGvlpoBGllNcb TBKTQBbiMw импульсами по тактовому входу 19 устроиства, Тогда на выходах схем 5 — 8 сравнения формируются логические уровни "О", "О", "О", "0", на выходах первого, второго и третьего разрядов пятого регистра 9 формируются сигналы
1", "О", "О", на выходах первого и второго разрядов регистра 10 имеются сигналы "О", "0", на выходе седьмого регистра 11 — сигнал "О". Таким образом, на адресные входы блока 12 постоянной памяти поступает нек"ор G000000100. Из таблицы видно, что при этом активизируется второй выход блока 12, 1683005 поэтому открывается вторая группа элементов И 14, и на выход поступает число "3", находящееся в данный момент в первом регистре 1 и являющееся медианой„поступившей на устройство последовательности.
Формула и зоб рете н и я.
Устройство для выделения медианы последовательности из пяти чисел, содержащее четыг:е схемы сравнения, блок постоянной памяти, причем выходы больше первой — четвертой схем сравнения соединены соответственно с входами первого— четвертого разрядов адреса блока постоянной памяти, о т л и ч а ю щ е е с я тем, что. с целью упрощения устройства при выделении медианы из последовательности чисел, оно содержит семь регистров, пять групп элементов И, причем информационные входы устройства подключены к информационным входам первого регистра, первым входам элементов И первой группы и входам первых групп всех схем сравнения, входы вторых групп которых подключены соответственно к выходам разрядов первого — четвертого регистров, тактовые входы которых являются тактовым входом устройства и соединены с тактовыми входами пятого, шестого и седьмого регистров, выходы разрядов первого регистра соединены с информационными входами второго регистра и первыми входами элементов И второй группы, выходы разрядов второго регистра соединены с информационными входами третьего регистра и первыми входами элементов И третьей группы, выходы разрядов
5 третьего регистра соединены с информационными входами четвертого регистра и первыми входами элементов И четвертой группы, выходы разрядов четвертого регистра соединены с первыми входами элемен10 тов И пятой группы, выходы первой, второй и третьей схем сравнения соединены соответственно с входами первого, второго и третьего разрядов пятого регистра, выходы первого и второго разрядов которого соеди15 нены с входами первого и второго разрядов . шестого регистра, выход первого разряда которого соединен с входом первого разряда седьмого регистра, выходы первого, второго и третьего разрядов пятого регистра
20 соединены с входами соответственно пятого, шестого и седьмого разрядов адреса блока постоянной памяти, входы восьмого, .девятого и десятого разрядов адреса которого подключены соответственно к выходам
25 первого и второго разрядов шестого регистра и первого.разряда седьмого регистра, выходы разрядов данных блока постоянной памяти соединены с вторыми входами элементов И соответственно первой — пятой
30 групп, выходы элементов И которых обьединены по ИВИ и являются информационным выходом устройства, 1683005
Продолжение таблицы
Выход ПЗУ
Лдре с
00100
00001
000tg
00010
00001
01000
01000
00001
01000
00001
00010
00100
СОС10
00001
ОС1О0
00100
00001
oooto
00010 01000
0000!
00100
00001
01000
00001
00001
00001
00001
0000000000
0000000001
0000000011
0000000100
0000000110
0000000111
0000001011
0000001111
О000010100
0000010110. 0000011110 000001111t
0000100000
000010000!
0000101001
00001010!1
0000110000
0000110100
0000111000
0000111001
0000111011
0000111100
0000111110 0000111! 1!
0001001011 0001001111
0001011111
,,0001101011
0001111011
0001111111
0010010100
00100101!Î
00100!1110
00101!0100
0010111)00
0010111110
001101111д
001011111
00111 11110
0011i1i1t1
0100100000
01001 00001
0100101001
0100!!оооо
0100111000
0100111001
0101101001
0!O11О1О11
01011tlool
010111t011
0110110000
0110110100
0110111000
0110111100
0111111000
0111!1100!
01!1111011
0111111100
0111111110
1О
01111!!111
1000000001
1000000011
1000000110 !
000000111
1001000011
1001000111
1001001011
1001001111
1011000111
101100111!
10110! 1111
1100000000 !
100000001
t1ОО1ОООО1
1101000001
1101000011
1101001011
1i01100001
1101101001
1101101011
111000000»
11i0010100
11i0100000
1!10110000
1 10110100
1111000001
i111000011
l111000111 ! 111001011
111i001111
11110111 1
1i11100001
1111101001
1t11101011
1t11110000
1i 11 1 10100
1111111-000
1111111001
1111111011
1111111!00
1i1l111110
1il1111111
00!00
00001
00001
10000 !
oooo
i0000
00001
000.1 О
00001
1.0000
00001
00001
О!000
00001
00001
ОС010
00001
00001
00001
00001
00100
