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

 

Изобретение относится к вычислительной технике и может быть использовано в системах обработки информации . Цель изобретения - повышение быстродействия. Устройство для сортировки информации содержит генератор 1 импульсов, коммутатор 2, счетчики 3 и 4, блоки 5 и 6 памяти, группу 7 элементов И , первый 8 и второй 9 элементы И, элемент ИЛИ 10, триггер 11, входы 12-17, выходы 18. Выход генератора 1 импульсов соединен с синхровходом триггера 1I, работающим по заднему фронту. Инверсный выход триггера 1I соединен с вторым входом элемента И 9. Блоки 5 и 6 памяти - одноразрядные. Максимальное количество сортируемой информации 2 -т разрядных слов. При этом счетчик 3 считает до 2, счетчик 4 - до 2f(). На входы 12 и 13 поступают соответственно младшие k и старшие 1 разрядов т-разрядного числа (). Сущность изобретения заключается в формировании во втором блоке памяти признака записи в массив информации. Во время считьшания информации при отсутствии этого признака осуществляется переключение адресов первого блока памяти, минуя незаполненный сортируемой информацией массив. Изобретение позволяет повысить быстродействие сортировки информации . 2 ил. (Л

СОЮЗ CORETCHHX

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

РЕСПУБЛИК

А1

„„SU, 1322256 (51) 4 G 06 F 7/06

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

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

12

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4023216/24-24 (22) 17.02.86 (46) 07.07.87. Бюл. М 25 (72) Е.Я. Ваврук (53) 681.325.5(088.8) (56) Авторское свидетельство СССР

11е 1073770, кл. С 06 Р 7/06,1982.

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

1е 1183956, кл. G 06 F 7/06, 1984. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ИНФОРМАЦИИ (57) Изобретение относится к вычислительной технике и может быть использовано в системах обработки информации. Цель изобретения — повышение быстродействия. Устройство для сортировки информации содержит генератор 1 импульсов, коммутатор 2, счетчики 3 и 4, блоки 5 и 6 памяти, группу 7 элементов И, первый 8 и второй 9 элементы И, элемент ИЛИ 10, триггер 11, входы 1"-17, выходы 18.

Выход генератора I импульсов соединен с синхровходом триггера 11, работающим по заднему фронту. Инверсный выход триггера 11 соединен с вторым входом элемента И 9. Блоки 5 и 6 памяти — одноразрядные. Максимальное количество сортируемой информации

2 m разрядных слов. При этом счет-. чик 3 считает до 2, счетчик 4 — до

2 (2 =2 ). Ha входы 12 и 13 посту(гп gi p пают соответственно младшие k и старшие 1 разрядов m-разрядного числа (m=k+1). Сущность изобретения заключается в формировании во втором блоке памяти признака записи в массив информации. Во время считывания информации при отсутствии этого признака осуществляется переключение адресов первого блока памяти, минуя незаполненный сортируемой информацией массив. Изобретение позволяет повысить быстродействие сортировки информации. 2 ил.

1 13

Изобретение относится к »з11ч»»спительной технике и може-, быть использовано в системах обрлботки информа22256 2 логического нуля, разрешающий работу счетчиков 3 и 4 в счетном режиме. На входах 15 и 16 устанавливается уровень логической единицы, определяющий режим записи блоков 5 и 6 памяти по сигналам с выхода генератора 1 импульсов. С выхода генератора 1 импульсов поступлет 2 импульсов, которые проходят через коммутатор 4, записына»от нули, находящиеся в информационном ции.

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

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

Устройство для сортировки информации содержит генератор 1 импульсов, коммутатор 2, счетчики 3 и 4, блоки

5 и 6 памяти, группу 7 элементов И, первьп» 8 и второй 9 элементы И, элемент ИЛИ 10, триггер 11, входы младших 12 и стлрших 13 рлзрядон сортируемого числя, вход 1 1 рлзрешения записи, входы 15 и !б злдлния режима, тактоньгй» вхоц 17, вы:;оды 18.

Коммутатор 2 открыт по первым входам при поступлении на управляющий вход 15 уровня логического нуля и по вторым входам при 1»оступлении уровня логической единицы. Управление блок»ми 5 и 6 памяти поступает с н»,»хздл коммутатора 2 и элемент» И 8 и организонлно для БИС плмяти статического типа (например, серий 13?, 5 11 и т.п.).

Для записи информлции подают сигнлль1 на входы записи II выборки, л дпя считывания информации — только нл вход»зь»борк»» кристлп л, Нл»дресные

Bõ»)ä»:1 блока 5 памяти 1»oeTó»»»10m сигна.лы с выходов счетч»п»он 3 и 4. Сонме— стиля рлботл счетчикон 3 и 4 (11 счетном режиме ) орган»»зона»»л 1»осредством связи выход;1 переноса счетчикл 3 и счетного входа счетчика 4 (через элемент ИЛП 1О). fl» выходы элементов И группы элементов И ноступ11ет содержимое счетчиков 3 и 4 голько при н»пи;ни единичного урс»зня нл выход»х бло— кон 5 и 6 памяти.

10

По входам 12 и 13 поступает сортируемая информация, k младших разрядов — по входам 12, а старших ио входам 13. С каждой сортируемой

V информацией поступает сигнал по тактовому входу 17, формирующий сигналы записи и выборки блоков 5 и 6 памяти.

После поступления всей сортируемой информации по всем соответствующим адресам блока 5 памяти записаны единичные потенциалы, а в блоке 6 памяти записаны единичные потенциалы по30

35 адресам, определяющимся старшими разрядами сортируемой информации.

Режим считывания информации. На входах 14 и 16 устанавливается уровень пог»»ческого нуля, определяющий режим рлботы счетчиков 3 и 4 в счетном режиме и режим счить»нания блоков 5 и 6 памяти. На входе 15 устанавливается уровень логической единицы, на выходе триггера ll устанавливается уровень логического нуля.

С выхода генератора I импульсов поступают импульсы, начиная с единичного уровня (фиг..2а, t ), с блоков

5 и 6 плмяти происходит считывание и прав»»ль»»ля иыформация появляется через время . „ (фиг. 2б). При считын 111111» нулевой информации с блока 6 памяти (фиг. 2б) н момент времени происходит ее злпись в триггер ll нл его 1»нверсном выходе присутствует уровень »огической единицы (фиг.2в, 40

Максимальное количество сортируеь»о1» и»»формлци1» 2 1»1 разряди»»х слон. и

При этом счетчик 3 считлет до 2

Е г )1 ° Р счетчик 4 — до 2 (2 =2 ) . Il» входы

12 и 13 поступ»;от соответстне»и»о мп»вшие !». и старшие рлзр>»цов и-разрядного числ,s (m=k+1).

Устройство рлботлет в трех режимах.

Режим очистки плм>»ти. По сигналу нлчлпьной установки 11»е пр»п»сцен) счетчики 3 и 4 устлнлнпгп»лю»c>» в нулевое состоя1гие, н» нь»ходе триггера

"11 устлнлвп»1н;1» тся нулевое состояние.

Н,"1 н х оде 1 -1 v с т» i I: 111>11»11 » е т с я у р о н е н ь входе блокон 5 и 6 по всем адресам блоков 5 и 6 памяти.

Режим сортировки информации. На входе 14 устанавливается уровень ло15 гической единицы, разрешающий работу счетчикон 3 и 4 в режиме параллельного приема 1»нформации. На входе 16 устанавливается уровень логической един»»ц»1, определяющий режим записи в

20 блоки 5 и 6 памяти. На входе 15 устанавливается уровень логического нуля, разрешающий прохождение через коммутатор 2 сигналов по тактовому входу 17.

3 132225

), который разрешает формирование (фиг. 2г, t„ ) сигнала, который с увеличивает содержимое счетчика 4 «а

+11 - и сбрасывает в нулевое состояние счетчик 3. Аналогично происходит ра5 бота устройства в моменты времени (фиг. 2).

Таким образом, при считывании нулевой информации с блока 6 памяти происходит увеличение адреса считыва- 1О ния блока 5 не íà 1, а на 2 . При

1 считывании единичной информации с блока 6 памяти на выходе триггера ll устанавливается сигнал логического нуля (фиг. 2в, t„) на выходе элемен- 15 та И 9 — нулевой уровень, счетчик

3 работает в счетном режиме. После перебора 2 адресов с блока 5 памя1 ти счетчик 3 формирует сигнал переноса (фиг. 2д, t„,), который увеличива- 21) ет содержимое счетчика 4 на +1, и работа устройства продолжается. Выдача информации на выход происходит при наличии единичной информации на выходах блоков 5 и 6 памяти. 25 формула изобретения устройство для сортировки информации, содержащее генератор импульсов, 30 первый счетчик, первый блок памяти, группу элементов И, причем выход генератора импульсов соединен со счетным входом первого счетчика и первым информационным входом коммута- З5 тора, второй информационный и управляющий входы которого являются соответственно тактовым входом и первым входом задания режима устройства, входы младших разряцов соргируемого 4Q числа устройства соединнеы с информационными входами первого счетчика, вход управления записью которого подключен к входу разрешения записи устройства и информационному входу пер- 45 вого блока памяти, входы младших разрядов адреса которого соединены с выходами разрядов первого счетчика и первыми входамн элементов И младших разрядов группы, вторые входы элемен— тов И группы соединены с выходом первого блока памяти, а выходы являются выходами младших разрядов отсортированного числа устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены второй счетчик, второй блок памя( ти, элемент ИЛИ, два элемента И и триггер, инверсный выход которого соединен с первым входом первого элемента И, второй вход которого подключен к синхровходу триггера и выходу генератора импульсов, а выход соединен с входом установки в ноль первого счетчика и первым входом элемента

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

1322256

Фиг 2

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

Редактор П. Гереши Техред А.Кравчук

Корректор С. Шекмар

Заказ 2864/44 Тираж 672 Подписное

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

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

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