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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 783512 А 5 0 06 Г 7/06 ЗОБРЕТЕН ЬСТВУ АНИЕ И РСКОМУ СВИД К(56) Авторское свидетельство СССРМ 1300459, кл. 6 06 Г 7/08, 1985,Авторское свидетельство СССРМ 1441384, кл, 0 06 Г 7/06, 1986 (прототИп),(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ(57) Изобретение относится к вычислительной технике, в частности к устройствам апГОСУДАРСТВЕННОЕ ПАТЕНТНОЕВЕДОМСТВО СССР(ГОСПАТЕНТ СССР) 2рной поддержки вычислительного са, и может быть использовано в спеированных вычислительных устройдля аппаратурной реализации и сортировки чисел ЦельЮ изобре-, вляется упрощение устройства, Уст,- о содержит кольцевые регистры 1, регистры сдвига результата 2, и ов 3, счетчик 4,группы элементов И , 12, элемент ИЛИ 8, элемент И 9, ты задержки 10, 11. Устройство выт упорядочение чисел по возрастаил. парату процес циализ ствах функци тения я ройств сдвига триггер 5, 6, 7 эемен полняеУстройство относится к вычислительной рого соединен с первыми входами элементехнике, е частности кустройствам аппарат- тов И третьей группы и через второй эленой поддержки вычислительного процесса. мент задержки с входами установки в и может быть использовано вспециализи-единичноесостояниетриггеров, Выход 1-го рованных вычислительных устройствах для 5,триггера соединен С инверсным входом 1-го аппаратнОй реализации функции сортйров- элемента И четвертой группы и вторым вхоки чисел:.-:;: ..: .:дом элемента И третьей группы, выход котоИзвестно устройство для сортировки рого подключенк входу обнуления 1-гочисел (1), содержащее две груПпы иэ и счет- в-разрядного кольцевого регистра сдвига.чиков (и -. количество сортируемых чисел), 10 Прямой вход первого элемента И четвертой группу .из и элементбв запрета, первый и группы соединен с третьим входом элеменвторой входныеэлементы И, элемент ИЛИ, та И третьейгруппы и входом логйческой сдвиговый регистр и блок аналива, содержа- единицы устройства, выход-го элемента тт щий и триггеров, группу из й элементов . четвертой группы О -1, , и) соединен с ИЛИ, групйу из (и) элементов И. элементы 15 прямым входом (3+1)-го элемента И четвер- И, НЕ, :. -: той группы и с третьим входом элемента И,Наиболее близким к предполагаемому третьей группы, Выход старшего разрядапо технической сущности и достигаемому )-го регистра сдвига результата соедгмнен с результату является устройство длясорти- входом младшего разряда О+1)-го регистра ровки чисел (2), выбранное е качестве про сдвига результата; выходы регистров сдвига тотипа, : ".: ..результата являются выходами сортируеУстройство содержит и в-разрягдных мых чисел устройства.кольцевых регистра сдвига, управляющий . На фиг. 1 представлена структурная схеэлемент И-ИЛИ, и элементов 2 И-ИЛИ, два ма устройства, на фиг, 2 - диаграмма работ элемента И, один элемент ИЛИ, блок управ ты.ления, три группы триггеров, (и) элемЕн- Устройство для сортировки и а-разрядтов И, (и) элементов ИЛИ..ных чисел содержит группу входных кольце-Недостаткомукаэанногоустройства яв- . вых сдвиговых регистров 1, группуляется большая сложность:сдвиговых регистров результата 3, группуЦелью изобретения является упроще триггеров 3, счетчик 4, первую 5, вторую 6,ние устройства.. третью 7 группы элементов И, элемент ИЛИ .В состав устройства входят и е-разряд, элемент И 9, первый 10, второй 11 элеменных кольцевых регистров сдвига, где и - ты задержки, четвертую группу элементов И число сортируемых чисел, п триггеров, пер.вую группу элементов И, элемент ИЛИ, эле Устройство имеет группу входов 13, мент И, причем информационные входы 1-го синхровход 14, группу выходов 15, 1-й вход в-разрядхного кольцевого регистра сдвига устройства 13 (1 - 1, и) соединен с информа являются входами соответствующих сорти- ционными входами 1-го регистра 1, выходруемыхчиселустройства.авыходстаршего старшего разряда которого соединен с разрядасоединен с первым входом 1-го зле первым входом 1-го элемента И 5, выход мента И первой группы 1= 1,и, второйо которого соединен с 1-м входом элемента вход которого соединен с выходом 1-го триг- ИЛИ 8 и с инверсным входом 1-го элемента гера, а выход подключен к 1-му входу эле- И 6, выход которого соединен с нулевым .мента ИЛИ. Устройство дополнительно входом 1-го триггера 3, выход которого сосодержит счетчик, вторую, третью и четвер единен со вторым входом 1-го элемента И .тую группы элементов И, первый и второй 5, инверсным входом 1-го элемента И 7 и элементызадержки, й регистров сдвига ре- первым входом 1-го. элемента И 12, выход зультвта,- причем выход элемента ИЛИ сое- которого соедйнен со входом обнуления динен с входом младшего разряда первого . 1-го регистра 1. Синхровход устройства 14 регистра сдвига результата и с первым вхо- соединен со вторым, входом элемента И 9.дом элемента И, выход которого соединен с и со входом элемента задержки 10, выход50прямыми входами элементов И второй груп- которого соединен с синхровходами регипы, выходы которых подключены к входам строе 1, 2 и с суммирующим входом счет- установки в ноль соответствующих тригге- чика 4, выход переполнения которого ров, синхровход устройства соединен с вто- соединен с третьими входами элементов И рым входом элемента И и через первый 12 и со входом элемента задержки 11, вы 55элемент задержки с синхровходами в-раз- ход которого соединен с единичными ехо.;:. рядныхкольцевыхрегистровсдвиге,регист- дами триггеров 3, Выход)-го элемента И 7ров сдвига результата и с суммирующим11, и) соединен с прямым входом Д+1)-го входом счетчика, выход переполнения кото- элемента И 7 и со вторым входом +1)-гоэлемента И 12, на прямой вход первого открытыеэлементы И 6 обнуляетсоответстэлемента И 7 и на второй вход первого вующиетриггеры 3.элемента И 12 подан потенциал логиче- . При переходе 1-го триггера 3 в нулевое ской единицы, Выход элемента ИЛ И 8 состояние соответствующий ему элемент И соединен со входом младшего разряда 5 5 закрывается, и соответствующее число из первого регистра 2 и с первым входомрегистра 1 исклЮчается из дальнейшего элемента И 9, выход которого соединен с" рассмотрения.прямыми входами элементов И 6, Выход;: Через время задержки т 1 о, определяестаршего разряда 1-го регистра 2 соеди- мое элементом 10, синхроимпульс поступанен со входом младшего разряда(3+1)-го 10 ет" на синхровходы регистров 1, 2 (фиг. 2, регистра 2. Выходы разрядов)-го регист- эпюра 2). При этом осуществляется сдвиг ра 2 соединены с-м выходом устройства информации в регистрах 1, 2 на один разряд 15: . вправо, В младший разряд первого регистПринцип работыустройства заключает-ра 2 осуществляется запись информации с ся в следующем. В регистры 1 параллель выхода элемента ИЛИ 8, В кольцевом сдвиным кодомзапйсываются исходные Числа, говом регистре 1 значение старшего разряна синхровход 14 подается последователь- да переписывается в младший разряд.ность из а.п импульсов, С приходом первых Импульс с выхода элемента задержки 10, а импульсов (в - разрядность чисел) выде- кроме того, увеличивает состояйие счетчика ляется максимальное из и чисел и последо 4 на единицу. Аналогично устройство рабовательным кодом записывается в первый тает и при поступлении следующих импульрегистр 2. Выделенное максимальное число сов.исключается из дальнейшего рассмотрения С приходом п-го по счету импульса осу(соответствующий регистр 1 обнуляется), С ществляется анализ последнего (младшего) приходом следующих е импульсов выделя разряда исходных чисел и через время зается максимальное из оставшихся (и) чи- держки йо осуществляется сдвиг информа. сел,котороезаписываетсявпервыйрегистр ции в регистрах. Таким образом, после 2, а его содержимое переписывается после- поступления первых импульсовсинхронидовательным кодом во второй регистр 2 и зации(. моментТона фиг.2, эп. 2) в первом т,д. Выделение максимального из и чисел 30 регистре 2 находится выделенное макси- заключается в последовательном анализе мальное число, в регистрах 1 - исходные содержимогоодноименныхразрядов(начи-числа в их первоначальном представленая со старццих) сравниваемых чисел.нии.Устройствр работает следующим обра- С приходом в импульсов на вход счетзом, В исходном состоянии в регистры 1 по 35 чика 4 на его выходе переполнения появлявходам 13 записаны исходные числа, счет- ется импульс, а счетчик обнуляется.чйк 4 обнулен, триггеры 3 - в единичном Импульс с выхода переполнениясчетчика 4 состоянии, элементы И 5 открыты, старшие (см:фиг, 2, эп, 3) поступает йа вход элемен- разряды анализируемых чисел поступают тов И 12 и на вход элемента задержки 11.на входы элемента ИЛИ 8. На вход 14 уст Группа элементов И 12 и на вход элемента ройства поступает последовательность из задержки 11, Группа элементов И 7, И 12 в.п импульсов(фиг.2, зпюра 1), С приходом представляют собой схему приоритета и первого импульса изменяется состояние : предназначено для обнуления регистра 1, триггеров 3 по следующему правилу: если-: . содержащего выделенное максимальное " старшие разряды всех чисел равны нулю., на 45 число, на что указывает единичнбе состоя- выходе элемента ИЛИ 8 нуль, элемент И 9 ние соответствующего триггера 3, Если в закрыт, состояние триггеров 3 не изменяет- регистрах 1 содержится.два и более одинася. Если старшие разряды всех чисел равны . ковых максимальных чисел, то несколько соединицы, на выходе элементы ИЛИ 8 - еди-. ответствующих триггеров 3 находится в ница, элемент И 9 открыт, а все элементы И единичном состоянии, С приходом импуль закрыты, состояние триггеров 3 не изме-са переполнения с выхода счетчика 4 на няется. входы элементов И 12, на выходе одного изЕсли старшие разряды некоторых чисел элементов И 12 формируется импульс обнуравны единице, а старшие разряды осталь- ления и при наличии двух и более одинаконыхчиселравнынулю,тона выходеэлемен-. 55 вых максимальных чисел обнуляется та ИЛИ 6 единица, элемент И 9 открыт и соответствующий регистр 1 сминимальным открыты элементы И. 6. на инверсный вход порядковым номером. Таким образом, выкоторых поступает сигнал логического нуля. деленное максимальное число исключаетсяИмпульс со входа 14 через элемент И 9 и издальнейшего анализа.рректор С.Лис Заказ 4516 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС 113035, Москва, Ж, Раушская наб., 4/5 Производственно. издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 10 Через время задержки т 11, определяемое элементом 11 (см, фиг. 2, эп. 4) импульс переполнения устанавливает в единичное состояние триггеры 3 и с приходом (в+1)-го импульса синхронизации начинается выделение максимального из оставшихся (и) чисел,По окончании работы в регистрах 2 записана упорядоченная последовательность чисел, причем в первом регистре 2 - минимальное из чисел, в п-ом регистре 2 - макси.мальное иэ чисел. Регистры 1 обнулены.Таким образом, предлагаемое устройство осуществляет сортировку в-разрядных чисел и имеет меньшую сложность, чем известное устройство. Ф о р мул э изобретенияУстройство для сортировки чисел, содержащее и в-разрядных кольцевых регистров сдвига, где и - число сортируемых чисел, и триггеров, первую группу элементов И, элемент ИЛИ, элемент И, причем информационные входы 1-го ги-разрядного кольцевого регистра сдвига являются входами соответствующих сортируемых чисел устройства, а выход старшего разряда соединен с первым входом 1-го элемента И первой группы, второй вход которого соединен с выходом 1-го триггера, а.выход подключен к 1-му входу элемента ИЛИ, о т л и ч а ю щ ее с я тем, что, с целью упрощения, оно содержит счетчик, вторую, третью и четвертую группы элементов И. первый и второй элементы задержки, и регистров сдвига резуль( тата, причем выход элемента ИЛИ соединен с входом младшего разряда первого регистра сдвига результата и с первым входом элемента И, выход которого соединен с пря мыми входами элементов И второй группы,выходы которых подключены к входам установки в "0" соответствующих триггеров, синхровход устройства соединен с вторым входом элемента И и через первый элемент 10 задержки с синхровходами а-разрядныхкольцевых регистров сдвига, регистров . сдвига результата и с суммирующим входом счетчика, выход переполнения которого со. единен с первыми входами элементов И 15 третьей группы и через второй элемент задержки с входами установки в единичное состояние триггеров, выход 1-го триггера соединен с инверсным входом 1-го элемента И четвертой группы и вторым входом элемен та И третьей группы, выход которого подключен к входу обнуления 1-го в-разрядного кольцевого регистра сдвига, прямой вход первого элемента И четвертой группы соединен с третьим входом элемента И третьей группы и входом логической единицы устройства, выход )-го элемента И четвертой группы = 1, и) соединен с прямым входом О+1)-го элемента И четвертой группы и с третьим входом элемента И третьей группы, 30 выход старшего разряда )-го регистра сдвига результата соединен с входом младшего разряда 0+1)-го регистра сдвига результата, ,выходы регистров сдвига результата являются выходами сортируемых чисел устрой ства.