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

 

СОЮЗ COBETCkMX

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

РЕСПУБЛИК (я)з G 06 F 7/06

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ (,Б6

«/«

Фиг.1

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

1 (21) 4822863/24 (22) .07,05.90 . . (46) 23.12.92, Бюл. ¹ 47 (72) С.Н.Макареня, В.И.Бенкевич, М.М,Татур и B.Ì.Áóëîé÷èê (56) Авторское свидетельство СССР

N 1300459, кл. G 06 F 7/08, 1985.

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

N. 1441384, кл, G 06 F 7/06, 1986 (прототип). (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к вычислительной технике, в частности к устройствам an.!Ж 1783512 А1 паратурной поддержки вычислительного процесса, и может быть использовано в специализированных вычислительных устройствах для аппаратурной реализации функции сортировки чисел.. ЦельЮ изобретения является упрощение устройства, Уст,ройство содержит кольцевые регистры сдвига 1, регистры сдвига результата 2, и триггеров 3, счетчик 4,группы элементов И

5, 6, 7, 12, элемент ИЛИ 8. элемент И 9, элементы задержки 10, 11. Устройство выполняет упорядочение чисел по возрастанию. 2 ил.

1783512

Устройство относится к вычислительной рого соединен с первыми входами элементехнике, в частности кустройствам аппарат- тов И третьей группы и через второй эленой поддержки вычислительного процесса. мент задержки с входами установки в и может быть использовано в специализи- единичноесостояниетриггеров, Выход 1-го рованных вычислительных устройствах для 5 триггера соеДинен С инверсным входом 1-го аппаратн0й реализации функции сортйров- элемента И четвертой группы и вторым sxoки чисел:.- -: :;: . .:: . дом элемента И третьей группы, выход котоИзвестно устройство для сортировки рого подключен к входу обнуления l-го чисел (1), содержащее две груПпы иэ ri счет- m-разрядного кольцевого регистра сдвига. чиков (n - . количество сортируемых чисел), 10 Прямой вход Aep80ro элемента И четвертой группу.из и элементбв запрета, первый и группы соединен с третьим входом элеменвторой входные элементы И, элемент ИЛИ, та И третьей группы и входом логйческой сдвиговый регистр и елок аналива. содержа- единицы устройства. выход -го элемента тт щий птриггеров,,группу из n: элементов . четвертой группы O - 1...., n-1) соединен с

ИЛИ, групйу из (и-1) элементов И. элементы 15 прямым входом (J+1)-го элемента И четверИ, НЕ, - .:.::-:: -: той группы и с третьим входом элемента И . Наиболее близким к предполагаемому третьей группы. Выход старшего разряда по технической сущности и достигаемому J-го регистра сдвига результата соедгмнен с результату является устройство для сорти- входом младшего разряда Ц+1)-го регистра ровки чисел (2), выбранное в качестве про- 20 сдвига результата, выходы регистров сдвига тотипа,:, " ":. : . .результата являются выходами сортируеУстройство содержит и m-разрядных мых чисел устройства. кольцевых регистра сдвига, управляющий . Ha фиг. 1 представлена структурная схеэлемент И-ИЛИ, и элементов 2И-ИЛИ, два ма устройства, на фиг. 2 — диаграмма рабо-. элемента И, один элемент ИЛИ, блок управ- 25 ты. ления, три группы триггеров, (n-2) элемЕн- Устройство для сортировки n m-разрядтов И, (n-1) элементов ИЛИ. -. - ных чисел содержит группу входных кольце-

Недостаткомукаэанногоустройства яв- ."вых сдвиговых регистров 1, группу ляется большая сложность.: сдвиговых регистров результата 3; группу

Целью изобретения является упроще- 30 триггеров 3, счетчик 4, первую 5, вторую 6, ние устройства. .: третью 7 группы элементов И, элемент ИЛИ .

В состав устройства входят n m-разряд- 8, элемент И 9, первый 10, второй 11 элеменных кольцевых регистров сдвига, где и — ты задержки, четвертую группу элементов И число сортируемых чисел, и триггеров, пер- 12. вую группу элементов И, элемент ИЛИ, эле- 35 Устройство имеет группу входов 13, мент И, причем информационные входы 1-го синхровход 14, группу выходов 15, l-й вход

m- ðàçðÿäíîãî кольцевого регистра сдвига устройства 13 (i - 1, и) соединен с информа являются входами соответствующих сорти- ционными входами 1-ro регистра 1, выход руемыхчиселустройства.авыходстаршего старшего разряда которого соединен с разрядасоединен с первым входом 1-го зле- 40 первым входом 1-ão элемента И 5, выход мента И первой группы 1= 1..... и, второй которого соединен с i-м входом элемента . вход которого соединен с выходом l-го триг- . ИЛИ 8 и с йнверсным входом 1-го элемента гера, а выход подключен к 1-му входу эле- И 6, выход которого соединен с нулевым мента ИЛИ. Устройство дополнительно входом 1-ro триггера 3, выход которого сосодержит счетчик, вторую, третью и четвер- 45 единен со вторым входом 1-ro элемента И .тую группы элементов И, первый и второй 5, инверсным входом I-го элемента И T u элементы задержки, и регистров сдвига ре- . первым входом l-ro. элемента И 12, выход зультата,- причем выход элемента ИЛИ сое- которого соедйнен со входом обнуления динен с входом младшего разряда первого . 1-го регистра 1. Синхровход устройства 14 регистра сдвига результата и с первым вхо- соединен со вторым. входом элемента И 9

" .дом элемента И, выход которого соединен с и со входом элемента задержки 10, выход

50 прямыми входами элементов И второй груп- которого соединен с синхровходами peruhbl, выходы которых подключены к входам строе 1, 2 и с суммирующим входом счетустановки в ноль соответствующих тригге- чйка 4, выход переполнения которого

@os„синхровход устройства соединен с вто- соединен с третьими входами элементов И рым входом элемента И и через первый 12 и со входом элемента задержки 11, вы55

: элемент задержки с синхровходами m-раз- ход которого соединен с единичными вхо .::. рядныхкольцевыхрегистровсдвига,регист- дамиитриггеров 3. Выход 1-го элемента И 7 ров сдвига результата и с суммирующим O 1, и-1) соединен с прямым входом(1+1)-ro входом счетчика, выход переполнения кото- элемента И 7 и со вторым входом (1+1)-ro

1783512 элемента И 12, на прямой вход первого открытыеэлементы И 6обнуляетсоответстэлемента И 7 и на второй вход первого вующие триггеры 3. элемента И 12 подан потенциал логиче- . При переходе i го триггера 3 в нулевое ской единицы. Выход элемента ИЛ И 8 состояние соответствующий ему элемент И соединен со входом младшего разряда 5 5 закрывается, и соответствующее число из первого регистра 2 и с первым входом: регистра 1 исклЮчается из дальнейшего элемента И 9, выход которого соединен с" рассмотрения. прямыми входами элементов И 6, Выход;: Через время задержки 4о, определяестаршего разряда j-го регистра 2 соеди- . мое элементом 10, синхроимпульс поступанен со входом младшего разряда (j+ 1)-ro 10 ет" на синхровходы регистров 1, 2 (фиг. 2, регистра 2. Выходы разрядов j-ro регист- эпюра 2). При этом осуществляется сдвиг ра 2 соединены с t-м выходом устройства информации в регистрах 1, 2 на один разряд

15.: вправо. В младший разряд первого регистПринцип работы устройства заключает- pa 2 осуществляется запись информации с ся в следующем. В регистры 1 параллель- 15 выхода элемента ИЛИ 8, В кольцевом сдвиным кодом запйсываются исходные Числа, говом регистре 1 значение старшего разряна синхровход 14 подается последователь- да переписывается в младший разряд. ность из m.п импульсов, С приходом первых Импульс с выхода элемента задержки 10, m импульсов (m — разрядность чисел) выде- кроме того, увеличивает состояйие счетчика ляется максимальное из и чисел и последо- 20 4 на единицу. Аналогично устройство рабовательным кодом записывается в первый тает и при поступлении следующих импульрегистр 2. Выделенное максимальное число сов. исключается из дальнейшего рассмотрения С приходом fTl-го по счету импульса осу(соответствующий регистр 1 обнуляется). С ществляется анализ последнего (младшего) приходом следующих m импульсов выделя- 25 разряда исходных чисел и через время зается максимальное из оставшихся (A-1) чи- держки йв осуществляется сдвиг информа. сел,котороезаписываетсявпервыйрегистр ции в регистрах. Таким образам, после

2, а его содержимое переписывается после- поступления первых импульсов синхронидовательным кодом во второй регистр 2 и зации(. моментТона фиг. 2, эп. 2) в первом т.д. Выделение максимального из и чисел 30 регистре 2 находится выделенное максизаключается в последовательном анализе мальное число, в регистрах 1 — исходные содержимогоодноименных разрядов(начи- числа в их первоначальном представленая со старших) сравниваемых чисел.: нии.

Устройствр работает следующим обра- С приходом m импульсов на вход счетзом, В исходном состоянии в регистры 1 по 35 чика 4 на его выходе переполнения появлявходам 13 записаны исходные числа, счет- ется импульс, а счетчик обнуляется. чйк 4 обнулен, триггеры 3 — в единичном: Импульс с выхода переполнения счетчика 4 состоянии, элементы И 5 открыты, старшие (см:фиг, 2, эп. 3) поступает йа вход элеменразряды анализируемых чисел поступают тов И 12 и на вход элемента задержки 11. на входы элемента ИЛИ 8. На вход 14 уст- 40 Группа элементов И 12 и на вход элемента ройства поступает последовательность из задержки 11. Группа элементов И 7, И 12 в.п импульсов(фиг.2, эпюра1). С приходом представляют собой схему приоритета и первого импульса изменяется состояние : предназначено для обнуления регистра 1, триггеров 3 по следующему правилу: если-:: содержащего выделенное максимальное

" старшие разряды всех чисел равны нулю-, на 45- число, на что указывает единичнбе состоявыходе элемента ИЛИ 8 нуль, элемент И 9 ние соответствующего триггера 3, Если в закрыт, состояние триггеров 3 не изменяет- регистрах 1 содержится два и более одинася. Если старшие разряды всех чисел равны . ковых максимальных чисел, то несколько соединицы, на выходе элементы ИЛИ 8 — еди-. ответствующих триггеров 3 находится в ница. элемент И 9 открыт, а все элементы И единичном состоянии. С приходом импуль6 закрыты, состояние триггеров 3 не изме-: са переполнения с выхода счетчика 4 на няется. входы элементов И 12, на выходе одного из

Если старшие разряды некоторых чисел элементов И 12 формируется импульс обнуравны единице, а старшие разряды oc àëü- ления и при наличии двух и более одинаконыхчиселравнынулю,тона выходеэлемен-. 55 вых максимальных чисел обнуляется та ИЛИ 6 единица, элемент И 9 открыт и соответствующий регистр 1 с минимальным открыты элементы И. 6. на инверсный вход порядковым номером. Таким образом, выкоторых поступает сигнал логического нуля. деленное максимальное число исключается Импульс со входа 14 через элемент И 9 и из дальнейшего анализа.

1783512

Через время задержки т11, определяемое элементом 11 (см, фиг. 2. эп. 4) импульс переполнения устанавливает в единичное состояние триггеры 3 и с приходом (m+1)-ro импульса синхронизации начинается выделение максимального из оставшихся (и-1) чисел.

По окончании работы в регистрах 2 записана упорядоченная последовательность чисел, причем в первом регистре 2 — минимальное из чисел, в и-ом регистре 2 — макси.мальное иэ чисел. Регистры 1 обнулены.

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

Фи2, 2

Составитель С.Макареня

Техред М.Моргентал,. Корректор С.Лисина

Редактор Г.Мельникова

Заказ 4516 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

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

Устройство для сортировки чисел, содержащее n m-разрядных кольцевых регистров сдвига, где и — число сортируемых чисел, и триггеров, первую группу элементов И, элемент ИЛИ, элемент И, причем информационные входы i-ro m-разрядного кольцевого регистра сдвига являются входами соответствующих сортируемых чисел устройства. а выход старшего разряда соединен с первым входом i-ro элемента И первой группы, второй вход которого соединен с выходом i-го триггера, а-выход подключен к 1-му входу элемента ИЛИ, о т л и ч а ю щ ее с я тем, что, с целью упрощения, оно содержит счетчик, вторую, третью и четвертую группы элементов И. первый и второй элементы задержки, и регистров сдвига резульl тата, причем выход элемента ИЛИ соединен с входом младшего разряда первого регистра сдвига результата и с первым входом элемента И, выход которого соединен с пря5 мыми входами элементов И второй группы, выходы которых подключены к входам установки в "0" соответствующих триггеров, синхровход устройства соединен с вторым входом элемента И и через первый элемент

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

15 третьей группы и через второй элемент задержки с входами установки в единичное состояние триггеров, выход i-ro триггера соединен с инверсным входом I-ro элемента И четвертой группы и вторым входом элемен20 та И третьей группы, выход которого подключен к входу обнуления i-го m-разрядного кольцевого регистра сдвига, прямой вход первого элемента И четвертой группы соединен с третьим входом элемента И третьей группы и входом логической единицы устройства, выход j-го элемента И четвертой группы (j = 1, и-1) соединен с прямым входом (j+1)-ão элемента И четвертой группы и с третьим входом элемента И третьей группы, 30 выход старшего разряда j-ro регистра сдвига результата соединен с входом младшего разряда (j+1)-ro регистра сдвига результата,,выходы регистров сдвига результата являются выходами сортируемых чисел устрой35 ства.