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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных системах обработки информации, предназначенных для сортировки массивов данных в реальном масштабе времени. Предлагаемое устройство для выделения медианы пяти чисел содержит десять компараторов 1-10, блок 11 постоянной памяти, коммутатор 12. Входные числа в параллельном коде поступают на компараторы 1-10, где происходит их попарное сравнение, а также на входы каналов коммутатора 12. На выходах компараторов 1-10 формируется управляющее слово, в котором содержится информация о том, на какой из входов 13-17 устройства поступило число, являющееся медианой входного набора чисел. С помощью блока постоянной памяти 11, где хранится таблица преобразования, управляющее слово преобразуется в трехразрядный код адреса, который поступает на входы разрядов адреса коммутатора 12 и определяет номер канала, по которому медиана пяти чисел поступит на выход устройства 18. Выполнение устройства для выделения медианы пяти чисел в соответствии с предлагаемым техническим решением позволяет повысить быстродействие устройства за счет параллельной обработки всего входного набора чисел и немедленной передачи на выход медианы набора путем переключения многоканального коммутатора в соответствии с результатом параллельной обработки. 1 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (И) А1 (Si)S С 06 Р 7/06

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР.(21) 4447037/24-24 (22) 24,06.88 (46) 23.09.90. Бюл. Р 35 (71) Московский институт электронной техники (72) А.В. Смирнов, В.fo. Дубровин, В.А. Григорович и В.И. Полянки (53) 681.325.5 (088.8) ! (56) Авторское свидетельство СССР

Р 1211717, кл. G 06 F 7/02, 1986, Авторское свидетельство СССР

Р 1348820, кл. G 06 Р 7/06, 1987.

2 (54) УСТРОЙСТВО ДЛЯ ВСЕЛЕНИЯ 1ПДИАНЫ ПЯТИ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике и может бить испольэовано в специализированных системах обработки информации, предназначенных для сортировки массивов данных в реальном масштабе времени. Предлагаемое устройство для выделения медианы пяти чисел содержит десять компараторов 1-10, блок 11 постоянной памяти, коммутатор 12..Входные числа в параллель1594520

15 ном коде поступают на компараторы 1—

10, где происходит их попарное сравнение, я также на входы каналов ком-. мутатора 12. На выходах компараторов

1-10 формируется управляющее слово, в котором содержится информация о том, ня какой из входов 13-17 устройства поступило число, являющееся медианой входного набора чисел. С помощью блока 11 постоянной памяти, где хранится таблица преобразования, управляющее слово преобразуется в трехразрядный код адреса, который .

1 поступает на входы. разрядов адреса

Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных системах обработки информации, предназначенных для сортировки массивов данных в реальном масштабе времени.

Целью изобретения является повышение быстродействия устройства за счет параллельной обработки входных чисел.

На чертеже представлена структурная электрическая схема устройства.

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

2, третий 3, четвертый 4, пятый 5„ шестой 6, седьмой 7, восьмой 8, девятый 9 и десятый 10 компараторы, блок 11 постоянной памяти, коммутатор 12, входы первого 13, второго 40

14, третьего 15, четвертого 16 и пя того 17 чисел устройства и выход 18.

Устройство работает следующим образом..

I 45

Входные числа в параллельном коде поступают на первый 1 — десятый 10 компараторы, где происходит их попарное сравнение, а также на входы каналов коммутатора 12. На выходах компараторов 1-10 формируется уп"" равляющее слово, в котором содержится информация о том, ня какой из входов устройства,13-17 поступило число, 4 являющееся медианой входного набора

55 чисел. С помощью блока 11 постоянной памяти, где хранится таблица преобра-. зования, управляющее слово преобразу.—. ется в трехрязрядный код адреса, ко коммутатора 12 и определяет номер канала, по которому медиана пяти чисел поступит ня выход устройства 18. Выполнение устройства для выделения медианы пяти чисел в соответствии с . предлагаемым техническим решением позволяет повысить быстродействие устройства за счет параллельной обработки всего входного набора чисел и немедленной передачи на выход медианы набора путем переключения многоканального коммутатора в соответствии с

1 результатом параллельной обработки.

1 ил. торый поступает ня входы разрядов адреса коммутатора 12 и определяет номер канала, по которому медиана.пяти чисел поступает ня выход устройства l8.

Предлагаемое устройство для выделения медианы пяти чисел в отличие от известного, где выделение медианы происходит в результате последо-. вательных попарных сравнений и пересылки входных чисел, позволяет повысить его быстродействие за счет па-. раллельной обработки всего входного набора чисел и немедленной передачи на выход медианы набора путем переключения многоканального коммутатора в соответствии с результатом параллельной обработки.

Алгоритм работы блока 11 постоянной памяти заключается в анализе ста двадцати различных ситуаций,. возникающих при сравнении пяти произвольных чисел. Число перестановок и чисел равно и! следовательно получают

120 различных векторов, формирующихся на схемах 1-10 сравнения.и поступающих на адресные входы блока 11 постоянной памяти. Для каждого из этих случаев вполне определено место медианы входного набора чисел. Поэтому на.вьгходе блока 11 постоянной памяти формируется номер входного канала, по которому поступило число, яв-, ляющееся медианой.

В таблице приведены данные программирования блока 11 постоянной памяти, выполненного на одной микросхеме ПЗУ 556РТ7. При этом исноль4520 десятого компаратора и четвертому входу данных коммутатора, вторыми . входами седьмого, девятого и десятого компараторов и с пятым входом дапнкх комму:атора, выходы компараторов с гервого по десятый соответственно подключены к входам с первого по десятый блока постоянной памяти, выходы которого соединены с управляющими входами коммутатора, выходы которого я-..ляются выходами устройства.

10

Номер информационного входа мультиплексора

Адрес ПЗУ

ыход ПЗУ

0000000001

0000000011

0000000111

0000001011

0000001111

0000010100

0000010110

00000 i 11 1 0

000001111!

0000!00001

0000101001

0000101011, 0000110000

0000! 10100

0000111000

55

5 159 зуются десять разрядов адреса и три разряда данных. Hcего программируется 120 ячеек памяти, адреса которых приведены в таблице. Остальные ячейки программируются произвольно или не программируются совсем.

П р и и е р . Ha входы 13-17 устройства поступают соответственно числа "1" "2" "4" "3" "5" При эт м

У Э t на выходах компараторов 1-10 формиItnll 11М), ttnti И II, Ил1 ttwtt ветственно. На адресные входы ПЗУ поступает вектор 0000000100. По таблице находят в четвертой строке, что на выходе ПЗУ в этом случае Формируется управляющее слово 011, что приводит к переключению коммутатора на четвертый канал, где находится число

tI It

3, которое и является медианой входного массива.

Формула изобретения

Устройство для выделения медианы пяти чисел, содержащее компараторы с первого по девятый, причем входы первого и второго чисел устройства соответственно соединены с первым и вторым входами первого компаратора, вход третьего числа устройства соединен с первым входом второго компаратора, вход четвертого числа устройства соединен с первым входом третьего компаратора, о т л и ч а ю щ е- . е с я тем, что, с целью повышения быстродействия, в него дополнительно введены десятый компаратор, коммутатор и блок постоянной памяти, причем вход пятого числа устройства соединен с первым входом четвертого компаратора, первый вход первого компаратора подключен соответственно к вторым входам второго, третьего и четвертого компараторов и к первому входу данных коммутатора, второй вход первого компаратора соответственно подключен к первым входам пятого, шестого и седьмого компараторов и второму входу данных коммутатора, первый вход второго компаратора соответственно, подключен к второму входу пятого ком-, паратора, первым входам восьмого и девятого компараторов, третьему входу данных коммутатора, первый вход третьего компаратора соответственно подключен к вторым входам шестого и восьмого компараторов, первому входу

0000111001

0000111011

0000111111

0001001011

0001001111

00010 11111

0001101011

0001111011

0001111111

00100 10100

001 001 11 10

00101101ÎÎ .

001 1011 11 1

0011111110

011

011

001

001

001

00 1

011

001

001

0i 1

011

011

001

001

011

011

001

001

000

3

4

5

2

2

4

2

5, 3

3

5

5

2

4

3

2

5

3

1

1.

1594520

Продогжение таблицы

Продолжение таблицы

000

000

000

01 1.

011

001

001

Составитель В. Журавлев

Техред H..Ходанин Корректор М. Шароши

Редактор

И. Дербак

Заказ 2829 Тираж 565 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5 комбинат "Патент", r.Óæãoðoä, ул. Гагарина,101

Производственно-издательский

0011111111

0100100001

0100101001

6100111001 ,0101101601

6101101011

6101111001

6101111011

Î110110000

6111111001

0111111011

0111111111

1000000001

1000000011

;1000000100

1000000111

1001000011

1001000111

1001001011

1001001111

1010000110 .

10«000110

1011000111

1011001111

1011010110 .

1011011111

001

001

011

011

011

011

011

011

000

2 .2

4

5

1

1

1

1

4

5

3

3

4

1

1

1

1

5

4

2

1100000001

1 100100000.

1100100001

1101000001

1101000011

1101001011

1101100001

1101101001

1101101011

1110100000.

1111000001

1111000011

1111000111

1111001011

1111001111

111.1010100

1111011111

1111100001

1111101001

1111101011

1111111001.

1111111011

1111111111

001

001

011

011

001

001

011

011

011

001

001

011

001

001

001

001

011

011

010.

1

1

3

5

2

3 .3

2

4

3

4

4

5

2

5

2

2

4

4.

Э