Устройство для сортировки чисел

Устройство для сортировки чисел

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Севетскнм

Сециалнстнческмк

Республнк(61) Дополнительное к авт. сеид-ву(22) Заявлено 10.12. 80 (21) 3214008/18-24

РЦМК з

G Об F 7/06 сприсоединеннемзаявки ЖГосударственный комитет

СССР по делам изобретений и открытий (23) Приоритет "

Опублнковано151282. Ьоллетень йо 46 (53) УДК б81.325 .бб (088. 8) Дата опубликования описания 15 ° 12 .82 (72) Авторы изобретения

Э.П.Черваков, Б.С.Богумирский и В.М.Цы (71 ) Заявитель (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ

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

Известно устройство дяя сортировки п-разрядных чисел, содержащее m регистров, регистр . результата, m схем сравнения, элемент ИЛИ, переключатель; группы элементов И, триггер, узлы запрета и распределитель импульсов Щ .

Недостаток устройства .- низкое бы« стродействиб, так как сортировка всего исходного массива чисел требует а(п+1) тактов, где m - количество, 15 а n - разрядность сортируеввх чисел.

Наиболее близким по технической сущности и достигаемому результату к изобретению является устройство для. сортировки чисел, содержащее распре- 20 делитель импульсов, m регистров, m схем сравнения, группы элементов И, счетчик сумматор и регистр результата (2).

Недостатком его является низкое

25. быстродействие, так как запксь како«

ro-либо числа в регистр результата и сравнение его с остальными числа-: ми осуществляется постедовательно во времени.

Цель изобретения - повышение быст- . родействия устройства путем совмещения во времени операций записи числа в регистр результата и сравнения его с другими числами.

Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее распределитель им пульсов, ю регистров, m элементов сравнения, m групп элементов И, счетчик, сумматор,.и регистр результата, причем выходы i-го (i=1 m) регистра соединены с первой группой входов i-ого элемента сравнения л с ttepвыми входами элементов И i-ой груп. пы, выходы- которой соединены с i-ой .группой входов регистра результата,. а вторые входы - с i-выходом распределителя импульсов, вход которого является первым управляющим входом устройства, выход i-oro элемента сравнения соединен c i-и входом счет» чика, выходы которогЬ соединены с первой группой входов сумматора, вторая группа входов которого соединена с группой информационных входов устройства,,а выходи - с,первыми входами элементов И первой выходной группы, выходы которых являются первой группой выходов: устройства, первые входы

981988, элементов И второй выходной группы соединены с выходами регистра результата, а выходы являются второй группой выходов устройства, введены отличительные связи — выходы элементов

И i-ой группы соединены с (i- 1) -ыми группами входов элементов сравнения с первой no (i-1)-ую и к i-ым группам входов элементоз сравнения с (1+1)-ой по m-ую.

На чертеже приведена схема устрой10 ства.

Устройство содержит распределитель импульсов 1, m регистров 2,,m элементов сравнения 3, группы 4-б элементов

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

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

60, 1-ми группами входов элементов срав 5 нения с (i+1)-го по в-й.

В регистры 2 заносятся сортируеьые числа, в регистр 9 результатануль, а распределитель импульсов 1устанавливается в начальное состояние (на чертеже не показано). После этого устройство готово к сортировке чисел в порядке возрастания.На вход

10 устройства подаются первый тактовый сигнал, по которому появляется импульс на первом выходе,распределителя иьйульсов 1. При этом открывается первая группа элементов И 4, и число из первого регистра 2 переписывается в регистр.9 результата и одновременно с этим, подается на соответствующие группы входов (m-1)-го элемента сравнения 3, где оно сравнивается со всеми сортируеьими числами. Сигнал на выходах элементов сравнения 3 появляется лишь в том случае, если числа, находящиеся в соответствующем регистре 2, меньше числа, поступаемого на вторые входы элемента сравнения через группы элементов И. Счетчик 7 подсчит;вает количество поступающих сигналов с блоков элементов сравнения 3, т.е. подсчитывает количество чисел, которые меньше, чем выделенное распределителем импульсов 1 и записанного в регистр 9 результата. Это число поступает на первую группу входов сумматора 8, à íà его вторую группу входов — код адреса области памяти, начиная с которого необходимо разместить отсортированный массив чисел.

Тогда адрес областн памяти, по которому следует записать число, находящееся в регистре 9 результата, определяется, как А = Аноч+ N, где Анач.—, адрес области памяти, начиная с Которого необходимо разместить отсортированные числа; N — количество чисел, меньших числа, записанного в реги» стре 9 результата.

Сумматор 8 вычисляет сумму A»„+N.

По сигналу на управляющем входе 11 устройства, число, находящееся в регистре 9 результата, переписывается в запоминающее устройство по адресу, находящемуся в сумматоре 8. Следующий такт. работы устройства начинается с подачи следующего тактового сигнала на вход 10 устройства. При. этом появляется импульс на следующем выходе распределителя импульсов

1, который откр..вает следующую группу 4 элементов И, вследствие чего в регистр 9 результата переписывается число из следукщего регистра 2 группы и одновременно с этим осуществля-. ется сравнение этого числа с остальными числами. В дальнейшем устройство работает так, как описано выае.

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

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

Устройство для сортировки чисел, содержащее распределитель импульсов, m регистров,,m элементов сравнения, m групп элементов И, счетчик, сумМатор и регистр результата, причем выходы .i-го (i=1,...,m) регистра соединены с первой группой входов i-го элемента сравнения и с первыми входами элементов И 1-й группы, выходы которых соединены с i-.é т;руппой входов регистра результата, а вторые входы - c i-м выходом распределителя импульсов, вход которого является первым управляющим входом устройства, выход i-го элемента сравнения соединен с i-м входом счетчика, выходы которого соединены с первой группой входов сумматора, вторая группа входов которого соединена с группой информационных входов устройства,,à выходы — с первыми входами элементов И первой выходной группы, выходы которых являются первой группой выходов устройства, а первые входы элементов И второй выходной группы соединены с выходами регистра результата, а выходы являются второй группой выходов устройства, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, выходы элементов И i-й группы соединены с (i-1)-ми группами входов элементов сравнения с первого по (i-1)-й и с

981988

Составитель В. Горохов

Техред М.Гергель Корректор Н. Король

Редактор М. Товтин

Эаказ 9712/68 Тираж 731 Подписное

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

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

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4

Источники информации, принятые во внимание при .экспертизе

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

9 526888, кл. 6 06 F 7/00, 1974.

2 Авторское свидетельство СССР по заявке Ю 2893485/18-24, кл. С 06 F 7/06, 10.03 80;-(прото.тип .