Устройство для сортировки информации

 

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

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

РЕСПУБЛИН (19) (11) (51)4 G 06 F 7 06

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

Ж

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К AB ГОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4037902/24-24 (22) 18.03.86 (46) .,15.07.87. Бюл. ¹ 26 (72) Е.Я.Ваврук, Л.Б.Заячкивская, P.Ñ.Ëàáÿê и В.M.Ðàâñêèé (53) 681.325(088.8) (56) Авторское свидетельство СССР № 1073770, кл . G 06 F 7/06, 1982.

Авторское свидетельство СССР

¹ 1183956, кл. G 06 F 7/06, 1983. (54) УСТРОЙСТВО ДПЯ СОРТИРОВКИ ИН40PMA1g5I (57) Изобретение относится к вычислительной технике и может быть ис пользовано в системах обработки информации. Цель изобретения — расширение области применения за счет воз.-. можности сортировки массивов информации. Устройство содержит k узлов сортировки 1, коммутатор 2, управляющий элемент И 3, многовходовый элемент И 4, k групп элементов И 5, элеI мент ИЛИ 6.Каждый узел сортировки содержит элементы И, элемент задержки, триггер, счетчик, блок памяти.

Устройство работает в трех режимах— очистки памяти, сортировки и считывания информации. После очистки блоков памяти всех узлов сортировки во все блоки памяти всех узлов сорти- ровки записываются единицы по адре:сам, соответствующим кодам сортируемых чисел. При считывании из блока памяти какого-либо узла сортировки единичной информации счетный вход счетчика этого узла сортировки блокируется.и адрес, формируемый íà его выходе, не изменяется. Нри считыва" нии единичной информации со всех узлов памяти на выходе многовходового элемента И формируется сигнал, разрешающий выдачу на выход устройства информации со всех узлов сортировки.

3 ил.

24024

1 13

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

Цель изобретения — расширение области применения устройства путем обеспечения возможности обработки массивов информации.

На фиг.1 приведена структурная схема устройства для сортировки информации; на фиг.2 — функциональная схема узла сортировки; на фиг.3— временные диаграммы работы устройства в режиме считывания.

Устройство для сортировки информа ции содержит 1< узлов 1,...,11, сортировки, коммутатор 2, управляющий элемент И 3, многовходовый элемент

И 4, k групп 5,,...,5 элементов И, элемент ИЛИ 6, информационные входы

7,...,7, вход 8 разрешения записи, вход 9 начальной установки, вход 10 тактовых импульсов, стробирующий вход 11 устройства, входы 12 и 13 задания режима, вход 14 управления режимом очистки, выходы 15,...,15„ Я ° ° ° ф устройства, выходы 16 блоков памяти, входы 17 установки триггеров в единичное состояние и входы 18 записи считывания блоков памяти.

Узел 1 сортировки образуют элементы И. 19 и 20, элемент 21 задержки триггер 22, счетчик 23 и блок 24 памяти.

Для записи информации на управляющий вход необходимо подать уровень логической единицы, для считывания — нулевой сигнал. При подаче сигнала единичного уровня коммутатор 2 открыт по вторым входам, при подаче сигнала нулевого уровня — по первым. Сигнал нулевого уровня разрешает работу счетчиков 23 в счетном режиме сигнал, единичного уровня — в режиме параллельного приема информации.

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

10 — 15

Режим очистки памяти.

На входе 8 устанавливается уровень логического нуля, на входах 12

В и 13 — уровни логической единицы. На входе 14 устанавливаетсч уровень логической единицы для установки и поддержки триггеров 22 в единичном состоянии. По сигналу начальной уста новки (вход 9) все счетчики 23 устанавливаются в нулевое состояние.

После этого по входу 10 подается 2 импульсов, где m — разрядность сортируемых массивов чисел, которые по своему заднему фронту увеличивают содержимое счетчиков 23. Так как сначала формируется сигнал записи в блоки 24, а потом переключения счетчиков 23, то после прохождения всех 2 импульсов, все блоки 24 памяти по всем адресам обнуляются.

Режим сортировки.

На входы 8, 13 и 14 подается уровень логической единицы, на вход 12— уровень логического нуля. На входы

7,...,7„ поступает информация сорти руемых массивов. Параллельно с информацией по входу 11 поступают ее стробирующие сигналы, являющиеся сигналами записи информации в блоки 24 памяти. После записи всей информации по всем блокам 24 памяти записываются единицы rro соответствующим адресамм °

Режим считывания информации.

На входах 8 и 13 устанавливается уровень логического нуля, на входе

12 — уровень логической единицы. По сигналу начальной установки (вход 9) все счетчики 23 устанавливаются в нулевое положение. На вход 14 подается строб, устанавливающий триггеры

22 в единичное состояние. ° По входу

10 поступают импульсы.

Дальнейшую работу устройства в этом режиме рассмотрим на конкретном примере (фиг.3, где q — сигналы на входе 10; б — выход счетчика 23; 6— выход блока 24 памяти, — выход элемента И 19; Э вЂ” выход триггера 22; е — выход элемента задержки; — выход элемента И 4).

Пусть по адресу А, одного из узлов 1 сортировки считывается нулевая информация, а по адресу А — единичная (Фиг.3 ь, с ); 7,„ „ - задержка на время считывания из блока 24 памяти. Минимум по одному из блоков 24 памяти других узлов 1 сортировки в это время считывается нулевая информация. Тогда на выходе элемента И 19 узла 1 сортировки, где считывается единичная информация, формируется сигнал (фиг.3 z, с„), сбрасывающий триггер 22 в нулевое положение (фиг.3д, с„). До тех пор, пока сигнал Hà входе 17 не опрокинет- этот триггер 22 в единичное состояние, на счетный вход соответствующего счетчика 23 не будут поступать им=

3 132402 пульсы с входа 10. Пусть в момент t со всех узлов 1 сортировки считывается единичная информация. Тогда на выходе элемента И 4 формируется сигнал (фиг.Зх, t ), который разрешает выдачу на выход устройства информа— ции со всех узлов 1 сортировки. При этом информация из разных узлов сортировки может быть разной или одинаковой. 10

Передний фронт сигнала с выхода элемента И 4 устанавливает в едичниное состояние триггера 22 (фиг.33, t ), разрешая тем самым прохождение импульсов с входа 10. Если при пере- 15 ключении адреса в одном из узлов 1 сортировки снова находится нулевая информация (например, по адресу А фиг.З 6, t ), выход элемента И 4 переключается (фиг.З, с ) и дальней- 20 шая работа устройства происходит аналогично описанному. Элемент 21 задержки предназначен для устранения возможности переключения счетчика 23 при считывании из блока 24 единичной информации.

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

Устройство для сортировки информации, содержащее группу элементов

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

"0" счетчика узла сортировки, вход разрешения записи счетчика соединен с ин- 45 формационным входом блока памяти и является входом разрешейия записи устройства, информационные входы счетчика являются входами первой группы сортируемых чисел устройства, а вы- 50 ходы разрядов подключены к соответствующим адресным входам блока памяти и информационным входам соответствующих элементов И первой группы, . управляющие входы которых объедине4 4 ны, а выходы являются выходами первой группы устройства, о т л и ч а— ю щ е е с я тем, что, с целью расширения области применения за счет возможности сортировки массивов информации, в первый узел сортировки введены первый и второй элементы И, триггер и элемент задержки, в устройство введены (k-1) узлов сортировки., где k — количество сортируемых массивов, (k-1) групп элементов

И, элемент ИЛИ, многовходовый элемент И и управляющий элемент И, пер-. вый вход которого соединен с вторым входом управления режимом устройства, второй вход подключен к выходу коммутатора, а выход соединен с входами записи считывания блоков памяти всех узлов сортировки, входы разрешения записи и установки в нулевое состояние счетчиков всех узлов сортировки соответственно объединены, счетные входы всех узлов сортировки объединены, причем счетный вход в каждом узле сортировки соединен с первым входом первого элемента И и через элемент задержки с первым входом второго элемента И, выход которого соединен со счетным входом счетчика, а второй вход — с прямым выходом триггера, информационный вход которого подключен к входу логического нуля устройства, а синхровход соединен с выходом первого элемента

И, второй вход которого соединен с выходом блока памяти, выходы блоков памяти всех узлов сортировки подключены к входам многовходового элемента И, выход которого соединен с первым входом элемента ИЛИ, второй вход которого соединен с входом управления режимом очистки устройства, а выход подключен к входам установки в единичное состояние триггеров всех узлов сортировки и управляющим входам элементов И всех групп, информа.— ционные входы счетчиков i-го узла сортировки являются входами i-й группы сортируемых чисел устройства, выходы разрядов счетчика i-ro узла сортировки, где i = 2, 3, °, k соединены с информационными входами соответствующих элементов И i-й группы, выходы которых являются выходами i-й группы устройства.

1324024

Фиа.2

Редактор А.Orap

Заказ 2966/52

Производственно-полиграфическое предприятие, г,Ужгород, ул.Проектная, 4

8

И

l аf1 г? ф Г,3

Составитель Е.Иванова

Техред И.Попович Корректор H. Король

Тираж 672 1 одписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5