Устройство для сортировки чисел
Изобретение относится к автоматике и вычислительной технике и может быть использовано при создании устройств обработки информации. Цель изобретения - повышение быстродействия устройства. Устройство содержит N регистров 1, N групп элементов И-ИЛИ 2, N-1 групп элементов И 3, N схем сравнения 4. Устройство осуществляет сортировку /упорядочение чисел/ по мере их поступления в порядке убывания, т.е.максимальное число размещается в первом регистре. Прием информации в регистр в зависимости от соотношения величины входного числа и чисел, записанных в регистр, осуществляется либо со стороны информационных входов устройства, либо со стороны предыдущего регистра. 1 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК
„„80„„161 4 (51) 5 С 06 F 7/06
ОПИСАНИЕ ИЗОБРЕТЕ
К .АВТОРСХОМУ СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
1 (21) 4608113/24 (22) 23.11.88 (46) .30.12.90. Бюл. 1п 48 (71) Таганрогский радиотехнический ,институт им. В.Д.Калмыкова (72) В.А.Авдеев, С.Ю. Фомин, С.А.Чиненов и С.В.Филиппович (53) 681.325.5(088.8) ,(56) Авторское свидетельство СССР
У 1037246, кл. С 06 F 7/06, 1982.
Авторское свидетельство СССР
Ф 1365076, кл. С 06 F 7/06, 1986.
2 (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано при создании устройства обработки информапии.
Цель изобретения — повьппение быстродействия устройства. Устройство содержит и регистров 1, и групп элементов
И-ИЛИ 2, п-1 групп элеметов И 3, п схем сравнения 4. Устройство осуществляет сортировку (упорядочение чисел) по мере их поступ1617432 писанных в регистр, осуществляется либо со стороны информационных входов устройства, либо со стороны пре5 дыдущего регистра. 1 ил.
Изобретение относится к автоматике и вычислительной технике и может быть использовано при создании устройств обработки информации.
Бель изобретения — повышение 15 бы тродействия устройства.
На чертеже представлена структурная схема устройства для сортировки чисел.
Устройство для сортировки чисел содержит и — регистров 1 — 1, . n групп элементов И-ИЛИ 2 — 2,(п-1) элементов И 3 - Зя, 1 и схем 4 — 4 сравнения.
Каждый регистр 1 устройства вы- 25
l полнен по двухступенчатой схеме, т.е ° каждый разряд можно представить, например, в виде двухступенчатого триггера, При наличии управляющего сигнала, поступающего на вход 6 устройства, происходит запоминание входной информации на элементах памяти (триггерах) первой ступени, а при отсутствии управляющего сигнала информация переписываетая на триггеры
35 второй ступени, схема 4 сравнения осуществляет сравнение двух чисел.
Если входное число меньше числа, хранимого в регистре 1, то на первом
1 (верхнем) выходе схемы 4 сравнения формируется сигнал единичного уровня, в противном случае сигнал вырабатывается на втором (нижнем) выходе.
Устройство работает следующим образом. 45
На выходе 5,— 5„последовательно по словам и параллельно по разрядам поступают m-разрядные коды чисел.
Устройство осуществляет сортировку (упорядочение чисел) по мере их поступления в порядке убывания, т.е ° максимальное число разме-. ается в первом регистре. После подачи очередного кода числа на выходе 5 < — 5 „ устрой-, ства через промежуток времени, в течение которого заканчиваются переходные процессы в устройстве, на вход 6 поступает управляющий сигнал, осуществляющий прием в регистр 1 информации ления в порядке убывания, т.е. максимальное число р,.змещается в первом регистре. Прием информации в ре" гистр в зависимости от соотношения величины входного числа и чисел, зачерез группу элементов И-ИЛИ либо со стороны регистра 1,,, либо со стороны входов 5 — 5
Управление приемом информации в регистр 1 со стороны входов 5 1 — 5, выполняется сигналом элемента И 3 ° (i=
1 -1
2, и-1) а управление вводом информации иэ регистра 1, — сигналом с второго входа схемы 4;,сравнения.
Элементы И 3< — 3 „, предназначены для определения соотношения, когда очередное число меньше предыцущего, но больше последующего.
Например, пусть четвертое входное число оказывается меньше второго, хранимого во второй ступени регистра
1, но больше третьего, записанного во второй ступени регистра 1, Тогда на выходе элемента И 3 формируется сигнал единичного уровня, который разрешает прием информации в первую ступень регистра 1 со стороны вхоЭ дов 5 — 5,1 по управляющему сигналу, поступающему на вход 6. Кроме того, в это же время происходит одровременный сдвиг содержимого второй ступени регистра 1 в первую ступень регистра 1, который осуществляется одновременно с приходом управляющего сигнала единичного уровня на вход 6.
Формула и э обретения
Устройство для сортировки чисел, содержащее и регистров, п групп элементоз И-ИЛИ, и-1 элементов И и и схем сравнения, причем информационные входы устройства соединены с входами первых групп схем сравнения и первыми входами элементов И-ИЛИ групп, входы второй группы i-й схемы сравнения, где i 1. ..n, соединены с выходами разрядов i-го регистра, выходы разрядов j-го регистра, где
1,...,n-1, соединены с вторыми входами элементов И-ИЛИ (j+1)-й группы,. выходы элементон И-ИЛИ i é группы соединены с входами соответствуюСоставитель Е.Иванова
Техред Л.Олийнык Корректор Т.Малец
Редактор Л.Пчолинская
Заказ 4119 Тираж 565 Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж-35, Раушская наб., д. 4/5
Производственно-издательский комбинат "Патент", г.Ужгород, ул. Гагарина,10
5 161 щих разрядов i-ro регистра, выход
j-ro элемента Й соединен с третьими входами элементов И-ИЛИ (j+1)-й группы, выход "Больше" первый схемы сравнения подключен к вторым входам элементов И-ИЛИ первой группы, выход
"Меньше" j-й схемы сравнения соединен с первым входом j-го элемента И, выход "Больше" (j+1)-й схемы сравнения соединен с вторым входом j-ro
7432 6 элемента И, тактовый вход устройства подключен к управляющим входам всех регистров, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия, выход Больше" j-й схемы сравнения подключен к четвертым входам элементов И (j+1)-й группы, выход "Меньше" j-A cxewa сравнения подключен к (j+2)-входу схем сравнения с (j+2)-й по (n-1)-ю.
