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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных системахобработкиинформации , предназначенных для сортировки данных в реальном масштабе времени. Целью изобретения является упрощение устройства при выделении медианы из последовательности чисел. Устройство содержит регистры 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