Устройство для сортировки информации Советский патент 1987 года по МПК G06F7/06 

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

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

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

Устройство для сортировки информа ции содержит k узлов 1 ,...,1j сортировки, коммутатор 2, управляющий элемент ИЗ, многовходовый элемент И 4, k групп 5;,,.,.,5, элементов И, элемент ИЛИ 6, Информационные входы 7 f,,,,7., вход 8 разрешения записи вход 9 начальной установки, вход 10 тактовых импульсов, стробирующий вход, 11 устройства, входы 12 и 13 задания режима, вход 14 управления режимом очистки, выходы 1 5, ..., 1 5. устройства, выходы 16 блоков памяти входы 17 установки триггеров в единичное состояние и вхады 18 записи считывания блоков памяти,

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

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

татор 2 открыт по вторым входам, при 40 выход элемента задержки; - вы- подаче сигнала нулевого уровня - по .ход. элемента И 4).

первым. Сигнал нулевого уровня раз- Пусть по адресу Ад одного из уз- решает работу счетчиков 23 в счетном лов 1 сортировки считывается нулевая режиме сигнал, единичного уровня - в информация, а по адресу А - единич45

режиме параллельного приема информации.

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

ная (фиг.З 6, с ); Т i задержка на время считывания из блока 24 памяти. Минимум по одному из блоков 24 памяти других узлов 1 сортировки в это время считывается нулевая инфор мация. Тогда на выходе элемента И 19 узла 1 сортировки,, где считывается единичная информация, формируется сигнал (фиг.Зг, с), сбрасывающий триггер 22 в нулевое положение

50

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

На входе 8 устанавливается уро- вень логического нуля, на входах 12 и 13.- уровни логической единицы. На входе 14 устанавливаетсч уровень логической единицы для установки и под-55 (фиг.3с), t). До тех пор, пока сиг- держки триггеров 22 в единичном со- нал на входе 17 не опрокинет- этот стоянии. По сигналу начальной уста- новки (вход .9) все счетчики 23 устанавливаются в нулевое состояние.

ная (фиг.З 6, с ); Т i задержка на время считывания из блока 24 памяти. Минимум по одному из блоков 24 памяти других узлов 1 сортировки в это время считывается нулевая информация. Тогда на выходе элемента И 1 узла 1 сортировки,, где считывается единичная информация, формируется сигнал (фиг.Зг, с), сбрасывающий триггер 22 в нулевое положение

триггер 22 в единичное состояние, на счетный вход соответствующего счетчика 23 не будут поступать им

5

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

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

На входы 8, 13 и 14 подается уровень логической единицы, на вход 12- уровень логического нуля. На входы 7,...,7, поступает информация сортируемых массивов. Параллельно с информацией по входу 11 поступают ее стро- бирующие сигналы, являюр иеся сигналами записи информации в блоки 24 Q памяти. После записи всей информации по всем блокам 24 памяти записывают- - ся единицы по соответствующим адресам .

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

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

Дальнейшую работу устройства в г этом режиме рассмотрим на конкретном примере (фиг.З, где q-. сигналы на входе 10; 5- выход счетчика 23; В - . выход блока 24 памяти; г - выход элемента И 19; Э - выход триггера 22;

5

0

Пусть по адресу Ад одного из уз- лов 1 сортировки считывается нулевая информация, а по адресу А - единич

(фиг.3с), t). До тех пор, пока сиг- нал на входе 17 не опрокинет- этот

ная (фиг.З 6, с ); Т i задержка на время считывания из блока 24 памяти. Минимум по одному из блоков 24 памяти других узлов 1 сортировки в это время считывается нулевая инфор мация. Тогда на выходе элемента И 19 узла 1 сортировки,, где считывается единичная информация, формируется сигнал (фиг.Зг, с), сбрасывающий триггер 22 в нулевое положение

(фиг.3с), t). До тех пор, пока сиг- нал на входе 17 не опрокинет- этот

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

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

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

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

возможности сортировки массивов информации, в первьй узел сортировки введены первый и второй элементы И, триггер и элемент задержки,- в устройство введены (k-1) узлов сортировки., где k - количество сортируемых массивов, (k-1) групп элементов И, элемент ИЛИ, многовходовый элемент И и управляющий элемент И, первый вход которого соединен с вторым

входом управления режимом устройства, второй вход подключен к выходу коммутатора, а выход соединен с входами записи считывания блоков памяти всех узлов сортировки, входы разрешения записи и установки в нулевое состояние счетчиков всех узлов сортировки соответственно объединены, счетные входы всех узлов сортировки объединены, причем счетный вход в

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

И, вторбй вход которого соединен с выходом блока памяти, выходы блоков памяти всех узлов сортировки подключены к входам многовходового элемента И, выход которого соединен с первым входом элемента ИЛИ, второй вход которогосоединен с входом управления режимом очистки устройства, а выход подключен к входам установки в единичное состояние триггеров всех

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

группы устройства.

1

J4

ffffff

г

д

ff

А.Огар

to t. t

Составит( Техред И.Попович

o - фие.З

Составитель Е.ИвановаЗаказ 2966/52 Тираж 672Подписное

ВНИИГШ .Государственного комитета СССР

. . по делам изобретений и открытий

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

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

Корректор Н. Король