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

ОП ИСАНИ ИЗОБРЕТЕН И Союз Советски кСоциалистическикРеспублик 083. ИДЕТЕЛ АВТОРСКОМ,ФгФ 1) 3335032/18 и исоединением заяв Г 4 сяйрственкын к 4СССР риорнт Опубликовано 28,02 Дата опубликования 81. делал кзебретенкк ллете н 4 ткрьп нсания 28. рылов и Н. Н, Шубина 1 ДОБА 1. 72) Авторы изобретения 71) Заявит) УСТРОЙСТВ СОРТИРО ИС ое и лиз о тис авнещее и схемтками устройства являются ые функциональные возможзволяющие определить тольальное число из и сравниел с потерей информации о остальных чисел.е близким к предлагаемоическому решению является 2 о для сортировки чисел, со- кольцевых регистров, упэлементы И-ИЛИ, входные -ИЛИ, дешифраторы, счетчие т гра ченнпо тремчис иях боле техн ост о.э аем нач На му по устро.1Изобретение относится к ав матике и вычислительной техни жет быть использовано при ре ции технических средств ЭВИ дании устройств обработки ста .ческой информации.Известно устройство для ср ния и-двоичных чисел, содержа кольцевых регистров сдвига, и равнозначности, элементы ИЛИ, мент И 1. 2ки, элементы И, ИЛИ, регистр, узел синхронизации, первый выход которого соединен с установочными входами кольцевых регистров, с управляющим входом схемы сравнения и с входом первого счетчика, выходы которого подключены к входам первого дешифратора и установочным входам второго счетчика, выходы которого соединены с входами второго дешифратора, каждый 1- ый выход первого дешифратора (1=1,; и -1) соединен с 1-ым входом первого управляющего элемента,И-ИЛИ.и с первым входом 1- го входного элемента И-ИЛИ, выход каждого 1- го входного элемента И-ИЛИ подключен к входу 1- го кольцевого регистра, выход каждого 1- го кольцевого регистра соединен с (+и - 1)-ым входом первого управляющего элемента И.-ИЛИ, выход которого подключен к первому информационному входу схемы сравнения и к первому вх;ду первого элемента И, выход которого со 3 10010единен с первым установочным входомрегистра, первый выход которого подключен к вторым входам 1,2(и - 1)-го входных элементов И-ИЛИ,каждый 1-.ый выход второго дешифрато- %ра соединен с 1-ым входом второгоуправляющего элемента И-ИЛИ, каждый у ый выход второго дешифратора(=1,2 п) подключен к третьим входам ( )+1)-го входного элемента И-ИЛИ, (и)-ый выход второго дешифратора соединен с первым входоми - го входного элемента И-ИЛИ, выход которого соединен с входом и -гокольцевого регистра, выход которогоподключен к и -му входу второго управляюцего элемента И-ИЛИ, выход каждого К-го кольцевого регистра(К=2,3 и -1) соединен с (Кп)ым входом второго управляющего эле- .20мента И-ИЛИ, выход которого подключен к второму информационному входусхемы сравнения и к первому входувторого .элемента И, выход которогосоединен с вторым установочным вхо- ЪЬдом регистра, второй выход которогоподключен к четвертым входам 2,3(и)- го входных элементов И-ИЛИ ик второму входу и -го элемента И-ИЛИ,первый выход схемы сравнения соеди- Зрнен с вторыми входами элементов И ис первым управляющим входом узласинхронизации, второй выход которого подключен к информационному входурегистра и к вторым установочным вхо 35дам кольцевых регистров, второй выход схемы сравнения соединен с первым входом элемента ИЛИ, второй входкоторого подключен к третьему выходуузла синхронизации а выход - к информационному входу второго счетчика, выход которого соединен с вторым управляющим, входом узла синхронизации 2 ,Недостаток устройства - низкое145быстродействие. Цель изобретения - повышение быст.родействия устройства,Поставленная цель достигаетсятем, что в устройство для сортировки чисел, содержащее и входных регистров,регистры, узел выделения,узел обобщения, счетчики, дешифраторы, схему сравнения 1 группы входныхэлементов И, группы элементов И перезаписи информации узел синхронизации, группы элементов И ИЛИ, элементы И, ИЛИ, прицем выходы первого счетчика соединены с входами первого дешифратора, каждый 1-й выход которого (1 1 и -1) подключен к уп:равляющим входам элементов И 1-й группы узла выделения, первый выход первого дешифратора соединен с первыми управляющими входами первых входных элементов И групп, каждый у й выход первого дешифратора ( 1= 2, ,и -1) подключен к первым управляющим входам )-х входных элементов И первой группы, выходы элементов И каждой 1-.й группы узла выделения соединены с входами элементов ИЛИ группы узла выделения, выходы которых подключены к первой группе входов схемы сравнения и к информационным входам элементов И первой группы перезаписи информации, выходы которых соединены с информационными входами первого регистра, выходы которого подключены к информационным входам с второго по (и -1)- 1 входных элементов И второй группы и к информационным входам и -х входных элементов И первой группы, выходы каждого 1- го входного регистра (1 = "=2 п) соединены с информационными входами элементов И (- 1)- 2 группы узла обобщений, выходы которых подключены к входам элементов ИЛИ группы узла обобщения, выходы которых соединены с второй группой входов схемы сравнения и с информационными входами элементов И второй группы перезаписи информации, выходы которых подключены к входам второго регистра, выходы которого соединены с информационными входами с второго по (и -1)- й входных элементов И первой группы и с информационными входами первых входных элементов И первой группы, выходы каждого 1- го входного регистра подключены к информационным входам элементов И 1-й группы узла выделения, выходы второго счетчика соединены с входами второго дешифратора, выход схемы сравнения подключен к управляющим входам элементов И первой и второй групп перезаписи информации и к входу перезапуска узла синхронизации, первый выход которого соединен с вторыми управляющими входами с второго по (и - 1)-й входных элементов И первой и второй групп, вторыми управляющими входами первых входных элементов И группы и с первыми управляющими входами ив х входных5 1001элементов И группы, выходы первых ии -х входных элементов И группы соединены с входами первого и п - го входных регистров соответственно, выходы ух входных элементов Й первой и 5второй групп подключены к входам.1-х входных элементов ИЛИ группы,выходы которых соединены с входамиу го входного регистра соответственно, введены элементы И, ИЛИ, триггеры, элементы задержки, выход каждого К-го разряда каждого 1- го входногорегистра (К=1в, е - количестворазрядов сравниваемых чисел) соединенс первым входом К-го элемента И 15(- 1)-группы, выходы элементов Икаждой 1-.й группы подключены к входам1- го элемента ИЛИ группы, выход каждого 1- го элемента ИЛИ группы соединен с. 1-м входом первого элемента 20ИЛИ и с входом установки в единичноесостояние -го триггера первой группы,выход первого элемента ИЛИ подключен .к входуустановки в единичное состояние триггера, прямой и инверсный выходы которого соединены с первымивходами первого и второго элементовИ соотйетственно выход первого элемента И подключен к входу первого,счетчика, к вх ду установки в нулевоеЗ 0состояние триггера и к. первому входу второго элемента ИЛИ, выход которого через элемент задержки соединенс первыми входами элементов И и-йгруппы, выход второго элемента И подключен к второму входу второго элемен 35та ИЛИ и к входу второго счетчика,каждый К-ый выход второго дешифратора соединен с вторым входом К-,го элемента И л -й группы, выход каждого40К-го элемента И и- й группы подключенк вторым входам К-х элементов И спервой по (и+ 1)- ю группы, прямой иинверсный выходы каждого - го триггера второй группы соединены с первыми входами 1- х элементов И (и +1)-й45и (и+2)-й групп, выход каждогоуго элемента И (и+2)-й группы подключен к вторым входам ( 1- 1)-х элементов И (п+ 1)- й и (и+2 )- й групп, выход первого элемента И (и+2 )-йгруппы соединен с вторыми входамипервого и второго элементов И, выходкаждого 1- го-элемента И (и+ 1)-й группы подключен к управляющим входамэлементов И 1-й группы узла обобще ния и через 1-й элемент задержки первой группы соединен с входом установки в нулевое состояние 1- го триггера пер 083 4вой группы и с входом 1 го элементазадержки второй группы, выход каждогор-го элемента задержки второй группы (р=1. и -2 ) подключен к вторымуправляющим входам элементов И второй группы, выход (и)- го элементазадержки втррой группы соединен с вторыми управляющими входами и -входныхэлементов И группы, второй выход узласинхронизации подключен к вторым входам (и)-х элементов И (и+ 1)-йи Ь +2)- й группы, вход установки вединичное состояние р-го триггера второй группы соединен с соответствующим у м выходом первого дещифратора, инверсный выход. каждого р-готриггера второй группы подключен ктретьим входам элементом И р-й группы.На чертеже представлена схемаустройства.Устройство содержит и входны;, регистров 1, регистр 2 числа А, регистр3 числа В, счетчики 4 и 5, дещифраторы 6 и 7, группу первых входных элементов И 8, группу и- х,входных элементов И 9, первые группы у х входных элементов И 10 (=2,;п),вторые группы 1-х входных элементовИ 11, группы 1-х входных элементов ИЛИ 12, группы из щ элементовИ 13 и 14 (в -разрядность числа),группу из (и -1)- го элемента ИЛИ 15,группу из (и - 1)- го триггера 16, груп.пу из (и -2 )- го элемента ИЛИ 15,группу из (и - 1)- го триггера 16, группу из Ь)-х триггеров 17, триггер .18, группы из (и)-го элемента И 19и 20, узел 21 выделения, содержащий(и)-ую группу элементов И 22 игруппу элементов ИЛИ 23, узел 24обобщения, содержащий (и)-ую группу элементов И 25 и группу элемен- .тов ИЛИ 26, схему 27 сравнения,группы элементов И 28 и 29 перезаписи информации, элементы И 30 и 31,элементы ИЛИ 32 и 33, элемент 34 задержки, группы из (и -1)- го элемента 35 и 36 задержки, узел 37 синхронизации вход 38 тактовых импульсов.Группь 1 элементов И 8-11, 22, 25, 28и 29 и группы элементов ИЛИ 12, 23и 26 содержат по в соответствующихэлементов,Устройство работает следующим образом. В исходном состоянии в регистрах1 записаны числа, которые необходимо7 1001 упорядочивать. Счетчик 4 и триггеры 16-18 находятся в нулевом, а счетчик 5 " в единичном состояниях. Код числа А из первого регистра 1 поступает на первую группу входов схе мы 27 сравнения через первую группу элементов И 22 игруппу элементов ИЛИ.23 узла 21 выделения за счет разрешающего потенциального сигнала с первого выхода дешифратора 7, ф определяющего единичное состояниесчетчика 5.По стартовому импульсу (вход 38) узел 37 синхронизации вырабатывает сигнал "а", который через открытые элементы И 20 и 31 поступает на вход счетчика 4, устанавливая его в единичное состояние, и через элемент ИЛИ 33, элемент 34 задержки (на время, необходимое для срабатывания 20 . счетчика 4 и дешифратора 6) на,первые входы группы элементов И 13. Пройдя через один из элементов И 13, на втором входе которого имеется потенциальный сигнал с первого выхо- И да дешифратора 6, определяющий единичное состояние счетчика 4, сигнал "а" открывает о-ые элементы И в группах элементов И 14, через которые значения щ-ых (старших) разрядов 36 чисел из регистров 1 (с второго по и -ый) поступают церез элементы ИЛИ 15 на входы элемента ИЛИ 32 и одновременно на единичные входы соответстующих триггеров 16, устанавливая их в нулевое состояние в зави- симости от значения в- го разряда числа. Если хотя бы в одном из чисел, записанных в регистрах 1, в в- ом разряде - "1", то через элемент . ИЛИ 32 поступает сигнал на единичный вход триггера 18, устанавливая его в единичное состояние. Второй сигнал "а" от узла 37 синх 45 ронизации через первый из открытых элементов И 19 .проходит на управляющие входы соответствующей .группы элементов И 25 и разрешает поступление числа В с соответствующего регист. ра 1 через элементы И 25 и ИЛИ 26 узЯ ла 24 обобщения на вторую группу входов схемы 27 сравнения, т.е. на вторую группу входов схемы 27 сравнения поступит первое из чисел, начиная с и- го, в в-ом разряде которого". Одновременно сигнал "а" с выхода элемента И 19, пройдя элемент 35 задержки (на время, необходимое для срав 0838 нения чисел К и 8 в схеме 27 и записи их в регистры 2 и 3), устанавливает в нулевое. состояние соответствующий триггер 16 и далее через элемент задержки 36 (необходимый для временного совпадения импульса с выхода элемента 35 задержки и сигнала "б" от узла 37 синхронизации) поступает на управляющие входы соответствующих элементов И 9 или. 11.После сравнения чисел К и В в схеме 27 возможны два варианта работы устройства: 1) если АВ, то на выходе схемы 27 сравнения появляется сигнал, поступающий на управляющие входы элементов 28 и 29 И перезаписи информации и разрешает запись чисел А и В через эти элементы в регистры 2 и 3 соответственно, Одновременно сигнал с выхода схемы 27 сравнения поступает на вход 37 перезапуска узла синхронизации, который вместо сигнала "а" выработает сигнал "б", разрешающий перепись числа В из регистра 3 в первый регистр 1, а числа А из регистра 2 в тот регистр 1, где было записано числа В. Следующим тактом узел 37 синхронизации вновь вырабатывает сигнал "а"; 2) если АЪВ, то на выходе схемы 27 сравнения сигнала нет и узел 37 синхронизации вырабатывает очередной сигнал "а", По каждому очередному сигналу "а" устройство работает аналогично с вторым сигналом "а".После сравнения числа К со всеми числами В, в в"ых разрядах которых ."1", триггеры 16 будут в нулевомсостоянии. Очередной сигнал "а" по-,ступает через элементы И 20 и 30 нанулевой вход триггера 18, входсчетчика 5 и через. элемент ИЛИ 33,элемент 34 задержки на первые входыгруппы элементов И 13. Триггер 18 устанавливается в нулевое состояние,Счетчик 5 переключается в состояние2. На втором выходе дешифратора 7 появляется потенциальный сигнал, устанавливающий первый триггер 17 в единичное состояние, закрывая тем самымэлементыИ 14 первой группы, и подключает второй регистр(число А)через вторую группу элементов И 22 ии группу элементов ИЛИ 23 узла 2 вы.деления к первой группе входов схемы 27 сравнения. Пройдя через одиниз элементов И 13, на втором входекоторого имеется потенциальный сиг9 10 нал с первого выхода дешмфратора 6, определяющий единичное состояние счетчика 4, сигнал "а" открывает пгые элементы И. в группах элементов И 11, через которые значения щ-ых разрядов чисел из регистров 1 (с третьего по и- ый) поступают через элементы ИЛИ 15 на. входы элемента ИЛИ 32 и одновременно на единичные входы соответствующих триггеров 16, устанавливая их в нулевое или единичное состояние в зависимости от значения в - го разряда числа. Далее устройство работает аналогично описанному выше до полного .упорядочения чисел, в в-ых разрядах которых "1".При поступлении очередного сигнала "а" от узла 37 синхронизации после полнОго упорядочения чисел, в щ-ых разрядах которых , на вяод"элемента ИЛИ 32 при перезаписи щ-ых разрядов чисел.из регистров 1 в соответствующие триггеры 16 сигналов не поступает.и триггер 18 оста ется в нулевом состоянии , Следовательно, следующий сигнал "а" от узла 37 синхронизации проходит через элементы И, 20 и 31, поступает в счетчик 4, устанавливая его в состояние 2, и через элемент ИЛИ 33, элемент 31 задержки на первые входы группы11 иР )+в- (Ъ +)+01083 10 элементов И 13. Пройдя через один из элементов И 13, на втором входе которого имеется потенциальный сигнал с второго выхода дешифратора 6, соответствующий состоянию 2 счетчика М; сигнал "а" открывает (в).-ые элементы И в группах элементов И 14,через которые значения (е)-ых разрядов чисел из регистров 1 с.(ц+1)- го по и -ый (ц - значение счетчика 5) поступают через. элементыИЛИ 15 на входы элемента ИЛИ 32 иодновременно на единичные входы соответствующих триггеров 16,устанавливая их в нулевое или единичноесостояние в зависимости от значе"ния (щ)- го разряда числа. Далееустройство работает аналогично описанному выше до полного упорядоче"ния чисел, Об окончании работы устройства сигнализирует переключениесчетчика 1 в состояние О.,10 15 20 ни(И+1)+. +И (,9+1)1+щ Технико-зкономический эффею заключается в том, что предлагаемое устройство обладает. большим быстродействием по сравнению с базо" вым .объектом,.В предлагаемом уст. ройстве. упорядочение,чисел осуществляется по группам и для полного1 их упорядочения требуется Я итактов работы:"1";ив : количество чисел; в(в)-ыхразрядах которых "1", исключая числа группы ищ,.и- количество цисел в -ом раз уряде которых ".1", исключаячисла групп и ,и , ии -количество .чисел, в первомразряде которых "1", исключая числа групп и , иМ фьфф ия.и -общее количество упорядочиваемых чисел (и =и + и + +иМ+ и+ + и. )в -количество групп, соответст вующее разрядности чисел. В базовом же объекта для полного упорядочения чисел требуетсятактов работы: Так, для 8-разрядных чисел быстро-, действие предлагаемого устройства по сравнению с базовым объектом повышается в 3,5-8 раз в зависимости от количества чисел. в группах.Кроме этого, предлагаемое устройство адаптируемо к изменению количества упорядочиваемых чисел. В базовом объекте количество тактов ,(Ц ) не зависит от количестваупорядочиваемых чисел и определяется их максимально возможным числом Ь ) т.е. любое количество упорядочиваемых чисел (1, где 1 и ) требует одинакового количества тактов работы. В предлагаемом устройстве количество. тактов (Ц) .определяется числом упоря. .-дочиваемых чисел, чем меньше чисел, тем. меньше требуется тактов для их упорядочения, т,е, в формуле (1) и =,Формула изобретенияустройство для сортировки чисел, содержащее и входных регистров, реги11 10010 стры, узел выделения, узел обобщения, счетчики, .дешифраторы, схему сравнения; группы входных элементов И, группы элементов И перезаписи информации, узел синхронизации, группы 5 элементов И, ИЛИ, элементы ИЛИ, причем выходы первого счетчика .соединены с входами первого дешифратора, каждый 1- й выход которого (1=1п - 1) подключен к управляющим входам элемен 40 тов И 1-й группы узла выделения, первый вцход первого дешифратора соединен с первыми управляющими вхддами первых входных элементов И групп, каждый )-й выход первого дешифратора 15 (3 =23,. и) подключен к первым управляющим входам )-х входных элементов И первой группы, выходы элементов И каждой 1-й группы узла выделения соединены со входами элементов ИЛИ 20 группы узла выделения, выходы которых подключены к первой группе схемы сравнения. и к информационным вхо: дам элементов И первой группы перезаписи информации, выходы которых со единены с информационными входами первого регистра, выходы которого подключены,к информационным входам с второго по (и - 1)-й входных элементов И второй группы и к информа- З 0 ционным входам и-х входных элементов И первой группы, выходы каждого 1-го входного регистра (1 =2и) соединены соответственно с информационными входами элементов И (1- 1)-й35 группы узла обобщения, выходы которых подключены к входам элементов ИЛИ группы узла обобщейия, выходы которых соединены с второй группой входов схемы сравнения и с информа 40 ционными входами элементов И второй группы перезаписи информации, выходы которых подключены к входам второго регистра, выходы которого соединены с информационными входами с второго по (и - 1)-й входных элемен 45 тов И первой группы и с информа, ционными входами первых входных элементов И первой группы, выходы каждого 1- го входного регистра подключены к информационным входам элементов И 1- й группы узла выделения, выходы второго счетчика соединены с входаьи второго дешифратора, выход схемы сравнения подключен к управляющим входам элементов И первой и второй групп перезаписи информации и к входу перезапуска узла синхронизации, первый выход которого соедиВ 3 12нен с вторыми управляющими входамис второго по (и)-й входных элементов И первой и второй групп, вторыми управляющими входами первых входных элементов И группы и с первымиуправляющими входами и- х входныхэлементов И группы, выходы первыхи и -х входных элементов И группысоединены с входами первого и и -говходных регистров соответственно, выходы 1-х входных элементов И первойи второй групп подключены к входам1"х входных элементов ИЛИ группы, выходы которых соединены с входамиуго входного регистра соответственно о т л и ч а ю щ,е.е.с я тем,что, с целью повышения быстродействия , в него введены элементы И, ИЛИ,триггеры, элементы задержки, выходкаждого К-по разряда каждого 0- говходного регистра (К=1 .в, щ -количество разрядов сравниваемых чисел) соединен с .первым входом К- гоэлемента И (1 в 1)-й группы,выходы элементов И каждой 1-.й группы подключены к входам 1-го элемента ИЛИ группы, выход каждОго 1-го элемента ИЛИгруппы соединен с 1-м входом первого элемента ИЛИ и с входом установки в единичное состояние 1- го триггера первой группы, выход первогоэлемента ИЛИ подключен к входу установки в единичное состояние триггера,прямой и инверсный выходы которогосоединены с первыми входами первогои второго элементов И соответственно, выход первого элемента И подключен к входу первого счетчика, к входу установки в нулевое состояние триггера и к первому входу второгоэлемента ИЛИ, выход которого через элемент задержки соединен с первымчвходами элементов И и -й группы, вы-. ход второго элемента И подключен к второму входу второго элемента ИЛИ и к входу второго счетчика, каждыйК-й выход второго дешифратора соединен с вторым входом К-го элемента ,И и -й группы, выход каждого К-го элемента И и -й группы подключен к вторым входам К-х элементов И с первой по (и+1)-ю группы, прямой и инверсный выходы каждого 1-го триггера второй группы соединены с первыми входами 1-х элементов И+1) - й и (и +2)- й групп, выход каждого 1-гоэлемента И (р +2)- й группы подключенк вторым входам ( у)-х элементовИ (и +1)-й и (и +2)- й групп, выход13 1001083 14 первого элемента И п+2)-й группы группы, второй выход узла синхронисоединен с вторыми входами. первого и зации подключен к вторым входам второго элементов И, выход каждого . Ь - 1)-х элементов И Ь +1)- й и+2)" й 1- го элемента й (п + 1)-й группыгрупп, вход установки в единичное подключен к управляющим входам эле- у состояние р-го триггера второй груп- ментов И -й группы узла обобщения и пы соединен с соответствующим 1-м через 1- й элемент задержки первой . выходом первого деширатора, инвер" группы соединен с входом установки сный выход каждого р-го триггера в нулевое состояние 1-,го триггера второй группы подключен к третьим вхо; первой группы и с входом "го эле дам элементов И р"й. группы. мента задержки второй группы, выход каждого р-го элемента задержки Источники информации, второй группы (р=1 и) под- принятые во внимание при экспертизе ключен к вторым управляЮщим входам 1. Авторское свидетельство СССР элементов И второй группы, выход и Ю 478303, кл. 6 06 Г 7704, 1975. Ь - 1)- го элемента задержки второй 2. Авторское свидетельство СССР группы соединен с вторыми управляю г 826339, кл. ь 06 Г 7/06:, 1979 Ьро" щими входами и-входных элементов И тотип).