Устройство для сортировки чисел Советский патент 1983 года по МПК G06F7/06 

() УСТРОЙСТВО для СОРТИРОВКИ ЧИСЕЛ

.1

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

Известно устройство для сравнения п-двоичных чисел, содержащее л кольцевых регистров сдвига, п схем равнозначности, элементы ИЛИ, эле- JQ мент И 1 |.

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

Наиболее близким к предлагаемо- , му по техническому решению является го устройство для сортировки чисел, содержащее п кольцевых регистров, управляющие элементы И-ИЛИ, входные элементы И-ИЛИ, дешифраторы, счетчики, элементы И, ИЛИ, регистр, узел ; синхронизации, первый выход которого соединен с установочными входами , кольцевых регистров, с управляющим ... входом схемы сравнения и с входом первого счетчика, выходы которого подключены к входам первого дешифратора и установочным входам второго счетчика, выходы которого соединены с входами второго дешифратора, каждый i-ый выход первого дешифратора ( ,.,..., п -1 ) соединен с i-ым ; входом первого управляющего элемента .И-ИЛИ и с первым входом i-ro входного элемента И-ИЛИ, выход каждого i- го входного элемента И-ИЛИ под-. ключен к входу f-го кольцевого регистра, выход каждого i-ro кольцевого регистра соединен с ()-ым входом первого управляющего элемента И-ИЛИ, выход которого подключе.н к первому информационному входу схе- мы сравнения и к первому входу первого элемента И, выход которого со- , единен с первым установочным входом регистра, первый выход которого под ключен к вторым входам 1,2,..., (n-l)-ro входных элементов И-ИЛИ, каждый 1-,ый выход второгодешифрато ра соединен с i-ым входом второго управляющего элемента И-ИЛИ, каждый J-ый выход второго дешифратора (,2,...,n-2) подключен к третьим входам (j+1)-ro входного элемента И-ИЛИ, (п-1)-ый выход второго де шифратора соединен с первым входом п-го входного элемента И-ИЛИ, выход которого соединен с входом п-го кольцевого регистра, выход которого подключен к п-му входу второго управ ляющего элемента И-ИЛИ, выход каждого К-го кольцевого регистра (,3,..., п-1) соединен с (K-tn-l)ым входом второго управляющего элемента И-ИЛИ, выход которого подключен к второму информационному входу схемы сравнения и к первому входу второго .элемента И, выход которого соединен с вторым установочным входом регистра, второй выход которого подключен к четвертым входам 2,3,.. (п-1)-го входных элементов И-ИЛИ и к второму входу п-го элемента И-ИЛИ первый выход схемы сравнения соединен с вторыми входами элементов И и с первым управляющим входом узла синхронизации, второй выход которого подключен к информационному входу pervicTpa и к вторым установочным вхо дам кольцевых регистров, второй выход схемы сравнения соединен с первым входом Элемента ИЛИ,второй вход которого подключен к третьему выход узла синхронизации а выход - к информационному входу второго счетчика, выход которого соединен с вторым управляющим,входом узла синхронизации 2 J, Недостаток устройства - низкое быстродействие. Цель изобретения - повышение быст родействия устройства. Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащееп входных регистров, регистры, узел выделения, узел обобщения, счетчики, дешифраторы, схему сравненияJ группы входных элементов И, группы элементов И перезаписи информации, узел синхронизации, группы элементов И, ИЛИ, элементы И, Или. причем выходы первого счетчика соединены с входами первого дешифратора, каждый i-й выход которого (1 1,.. ., л-1) подключен к уп:равляющим входам элементов И i-й группы узла выделения , первый выход первого дешифратора соединен с первыми управляющими входами первых входных элементов И групп, каждый j-й выход первого дешифратора {j 2,.,./1-1) подключен к первым управляющим входам J-X входных элементов И первой группы, выходы элементов И каждой 1тй группы узла выделения соединены с входами элементов ИЛИ группы узла выделения, выходы которых подключены к первой группе входов схемы сравнения и к информационным входам элементов И первой группы перезаписи информации, выходы которых соединены с информационными входами первого регистра, выходы которого подключены к информационным входам с второго по (п -1)-I входных элементов И второй группы и к информационным входам п-х входных элементов И первой группы, выходы каждого 1-го входного регистра (1 2,.,., п) соединены с информационными входами элементов И (Е-1)группы узЛа обобщений, выходы которых подключены к входам элементов ИЛИ группы узла обобщения, выходы , которых соединены с второй группой входов схемы сравнения и с информационными входами элементов И второй Сруппы перезаписи информации, выходы которых подключены к входам второго регистра, выходы которого соединены с информационными входами с второго по (п-1)-й входных элементов И первой группы и с информационными входами первых входных элементов И первой группы, выходы каждого i-го входного регистра подключены к информационным входам элементов И i-й группы узла выделения, выходы второго счетчика соединены с входами второго дешифратора, выход схемы сравнения подключен к управляющим входам элементов И первой и второй групп перезаписи информации и к входу перезапуска узла синхронизации, первый выход которого соединен с вторыми управляющими входами с второго по (п-1)-й входных элементов И первой и второй групп, вторыми управляющими входами первых входных элементов И группы и с первыми управляющими входами п-х входных 5элементов И группы, вшходы первых и п-X входных элементов И группы соеди нены с входамипервого и п- го входных регистров соответственно, выходы J-X входных элементов И первой и второй групп подключены к входам J-X входных элементов ИЛИ группы, выходы которых соединены с входами J-го входного регистра соответственно, введены элементы И, ИЛИ, триг геры, элементы задержки, выход каждо го К-го разряда каждого 1-го входног регистра (,.,.,т, т- количество разрядов сравниваемых чисел) соедине с первым входом К-го элемента И (-l)-t группы, выходы элементов И каждой -.й группы подключены к входа -го элемента ИЛИ группы, выход каждого i-го элемента ИЛИ группы соединен с i-M входом первого элемента ИЛИ и с входом установки в единичное состояние i-ro триггера первой групп выход первого элемента ИЛИ подключен к входу установки в единичное состоя (Ние триггера, прямой и инверсный выходы которого соединены с первымивходами первого и второго -элементов 14 соотбетственно выход первого элемента И подключен к входу первого счетчика, к вхсду установки в нулево состояние триггера и к. первому входу второго элемента ИЛИ, выход которого через элемент задержки соединен с первыми входами элементов И п-й группы, выход второго элемента И под ключен к второму входу второго элеме та ИЛИ и к входу второго счетчика, каждый К-ый выход второго дешифратора соединен с вторым входом эле мента И п-й группы, выход каждого К-го элемента И п-й группы подключен к вторым входам К-х элементов И с первой по (п+1)-ю группы, прямой и инверсный выходы каждого i-ro триггера второй группы соединены с первы ми входами i-X элементов И (п+1)-й и (п+2)-й групп, выход каждого J-го элемента И (п+2)-й группы подключен к вторым входам (J-1)-х элементов И (п+ 1)-й и (п+2)-й групп, выход первого элемента И (п+2 )-й группы соединен с вторыми входами первого и второго элементов И, выход каждого i-ГОэлемента И (п+1)-й груп пы подключен к управляющим входам элементов И -группы узла обобщения и через i-й элемент-задержки пер вой группы соединен с входом установ в нулевое состояние i-ro триггера пёр83вой группы и с входом i-ro элемента задержки второй группы,выход каждого р-го элемента задержки второй группы ( ,. . . /1 -2 ) подключен к вторым управляющим входам элементов И второй группы, выход (п-1)-го элемента задержки втррой группы соединен с вторыми управляющими входами п-входных элементов И группы, второй выход узла синхронизации подключен к вторым входам (n-l)-.x элементов И (гн-1)-й и (п+2)-й группы, вход установки в единичное состояние р-го триггера второй группы соединен с соответствующим J- м выходом первого дешифратора, инверсный выход каждого р-го триггера второй группы подключен к третьим входам элементом И р-й группы. На чертеже представлена схема устройства. Устройство содержит п входных регистров 1, регистр 2 числа А, регистр . 3 числа В, счетчики и 5, дешифраторы 6 и 7, группу первых входных элементов И 8, группу п-х входных элементов И 9, первые группы j-x входных элементов И 10 ( j 2,... ,п-1), вторые группы j-x входных элементов И 11, группы j-x входных элементов ИЛИ 12, группы из m элементов И 13 и Т (т -разрядность числа), группу из {п-1)-го элемента ИЛИ 15, группу из -1)-го триггера 16, группу из (п-2 )-го элемента ИЛИ 15, группу из (n-l)-ro триггера 16, группу из (п-2)-х триггеров 17, триггер 18, группы из (п-1)-го элемента И 19 и 20, узел 21 выделения, содержащий (п-1)-ую группу элементов И 22 и группу элементов ИЛИ 23, узел 2k обобщения, содержащий 1л-1)-ую группу элементов И 25 и группу элементов ИЛИ 26, схему 27 сравнения, группы элементов И 28 и 29 перезаписи информации, элементы И 30 и 31, элементы ИЛИ 32 и 33, элемент 3 задержки, группы из {п-1)-го элемента 35 и Зб задержки, узел 37 синхронизации , вход 38 тактовых импульсов. Группы элементов И 8-11, 22, 25, 28 и 29 и группы элементов ИЛИ 12, 23 и 26 содержат по m соответствующих элементов. Устройство работает следующим образом. В исходном состоянии в регистрах 1 записаны числа, которые необходимо упорядочивать. Счетчик 4 и триггеры 16-18 находятся в нулевом, а счетчик 5 в единичном состояниях. Код числа А из первого регистра 1 поступает на первую группу входов схе мы 27 сравнения через первую группу элементов И 22 и группу элементов ИЛИ 23 узла 21 выделения за счет разрешающего потенциального сигнала с первого выхода дешифратора 7, определяющего единичное состояние счетчика 5. По стартовому импульсу (вход 38) узел 37 синхронизации вырабатывает сигнал а,, который через открытые элементы И 20 и 3 поступает на вход счетчика k, устанавливая его в единичное состояние, и через элемент ИЛИ 33, элемент 3 задержки (на время, необходимое для -срабатывания счетчика Ц и дешифратора 6) на, первые входы группы элементов И 13. Пройдя через один из элементов И 13, на втором входе которого имеется потенциальный сигнал с первого BBIXOда дешифратора 6, определяющий единичное состояние счетчика k, сигнал а открывает элементы И в груп пах элементов И И, через которые значения т-ых (старших) разрядов чисел из регистров 1 (с второго по п-ый) поступают через элементы ИЛИ 15 на входы элемента ИЛИ 32 и од но ременно на единичные входы соответстующих триггеров 16, устанавливая их в нулевое состояние в зависимости от значения т-го разряда чис ла. Если хотя бы в одном из чисел, записанных в регистрах 1, в т-ом разряде - 1, то через элемент : ИЛИ 32 поступает сигнал на единичный вход триггера 18, устанавливая его в единичное состояние. Второй сигнал а от узла 37 синх ронизации через первый из открытых элементов И 19 проходит на управляющие входы соответствующей группы элементов И 25 и разрешает поступление числа В с соответствующего регис ра 1 через элементы И 25 и ИЛИ 26 уз ла 2k обобщения на вторую группу вхо дов схемы 27 сравнения, т.е. на вторую группу входов схемы 27 сравнения поступит первое из чисел, начиная с п-го, в т-ом ра-зряде которого 1. Одновременно сигнал а с выхода эле мента И 19, пройдя элемент 35 задерж ки (на время, необходимое для сравнения чисел А и В в схеме 27 и записи их в регистры 2 и 3), устанавливает в нулевое состояние соответствующий триггер 16 и далее через элемент задержки Зб (необходимый для временного совпадения импульса с выхода элемента 35 задержки и сигнала б от узла 37 синхронизации) поступает на управляющие входы соответствующих элементов И 9 или. П. После сравнения чисел А и В в схеме 27 возможны два варианта работы устройства: 1) если , то на выходе схемы 27 сравнения появляется сигнал, поступающий на управляющие входы элементов 28 и 29 И перезаписи информации и разрешает запись чисел А и В через эти элементы в регистры 2 и 3 соответственно. Одновременно сигнал с выхода схемы 27 сравнения поступает на вход 37 перезапуска узла синхронизации, который вместо сигнала а выработает сигнал б , разрешающий перепись числа В из регистра 3 р пербый регистр 1, а числа А из регистра 2 в тот регистр 1, где было записано число В. Следующим тактом узел 37 синхронизации вновь вырабатывает сигнал 2) если А7/В, то на выходе схемы 27 сравнения сигнала нет и узел ,37 синхронизации вырабатывает оче,редной сигнал а. По каждому очередному сигналу а устройство работает аналогично с вторым сигналом а. . После сравнения числа А со всеМИ числами В, в разрядах которых .1, -триггеры 16 будут в нулевом состоянии. Очередной сигнал а пот ступает через элементы И 20 и 30 на нулевой вход триггера 18, вход счетчика 5 и через элемент ИЛИ 33, элемент З задержки на первые входы группы, элементов И 13. Триггер 18 устанавливается в нулевое состояние. Счетчик 5 переключается в состояние 2. На втором выходе дешифратора 7 появляется потенциальный сигнал, устанавливающий первый триггер 17 в единичное состояние, закрывая тем самым элементы .И 1 первой группы, и подключает второй регистр 1 (число А) через вtopyю группу элементов И 22 и и группу элементов ИЛИ 23 узла 21 выделения к первой группе входов схемы 27 сравнения. Пройдя через один из элементов И 13, на втором входе которогоимеется потенциальный сигнал с первого выхода дешифратора 6, определяющий единичное состояние счетчика k, сигнал а открывает пгые элементы И в группах элементов И Н, через которые значения щ-ых разрядов чисел и регистров 1 (с третьего по п-ый) пос-гупают чере элементы ИЛИ 15 на. входы элемента ИЛИ 32 и одновременно на единичные входы соответствующих триггеров 16, устанавливая их в нулевое или единичное состояние в зависимости от значения m - го разряда чис ла. Далее устройство работает анало гично описанному выше до полного упорядочения чисел, в т-ых разрядах которых 1. При поступлении-очередного сигна а от узла 37 синхронизации после полногр упорядочения чисел, в т-ых разрядах котЬрых 1, на входЭлемента ИЛИ 32 при пе|эезаписи т-ых разрядов чисел из регистров 1 в соответствующие триггеры 16 сигналов не поступает и триггер 18 ост ется в нулевом состоянии . Следовательно, следующий сигнал а от узл 37 синхронизации проходит через эле менты И. 20 и 31, поступает в счет чик, устанавл14вая его в состояние 2, и через элемент ИЛИ 33, элемент задержки на первые входы группы

«С )( ) , где,;, количество чисел, в т-ых (старших) разрядах которых п- количество -чисел, в(т-1)-ых . разрядах которых 1, исклю чая числа группы ,| количество нисеп, в I-OM ра ряде которых .1, исключая числа групп Пу„/1, . . . .; п.-количество чисел, в первом разряде которых 1, исключая числа групп п. , п ,.. . ,.. . , п,; п -общее количество упорядочив емых чисел (п п + п t .. .+ .+-пн ); m -количество групп, соответст . вующее разрядности чисел. Вбазовом же объекта для полного упорядочения чисел т-ребуется Q та тов работы: Oi -1) элементов И 13. Пройдя через один из элементов И 13, на втором входе которого имеется потенциальный сигнал с второго выхода дешифратора 6, соответствующий состоянию 2 счетчика k сигнал а открывает (т-1)--ые элементы И в группах элементов И 1, через которые значения (т-1)-ых : . разрядов чисел из регистров 1с(q+1)-ro по п-ый (q - значение счьтчика 5) поступают через.элементы ИЛИ 15 на входы элемента ИЛИ 32 и/ одновременно на единичные входы соответствующих триггеров 16,устанавливая их в нулевое или единичное состояние в зависимости от значения (m-l)-ro разряда .Числа. Далее устройство работает аналогично описанному выше до полного упор-ядочеиия чисел. Об окончании работы устройства сигнализирует переключение cчetчикa в состЬяние 0. . Технико-экономический эффекч заключается в том, что предлагаемое устройство обладает большим быстродействием по сравнению с базовым объектом. .В предлагаемом устройстве упорядочение .чисел осуществляется по группам и для полного их упорядочения требуется Q,.,TaKTOBработы:Так, для 8-разрядных чисел быстрог действие предлагаемого устройства по сравнению с базовым объектом повышается в раз в зависимости от количества чисел, в группах. Кроме этого, предлагаемое уст- : ройство адаптируемо к изменению количества упорядочиваемых чисел. В . базовом объекте количество тактов (0,-) не зависит от количестваупорядочиваемых чисел и определяется их . максимально возможным числом 1п ), т.е. любое количество упорядочиваемых чисел {1 , где ) требует одинакового количества тактов работы. В предлагаемом устройстве количество, тактов {Цл) определяется числом упорядочиваемых чисел, чем меньше чисел, тем-меньше требуется тактов для их упорядочения, т.е. в формуле (1) . Формула изобретения Устройство для сортировки чисел, содержащее п входных регистров, регистры, узел выделения, узел обобщения, счетчики, дешифраторы, схему сравнения, группы входных элементов И, группы элементов И перезаписи и формации, узел синхронизации, групп элементов И, ИЛИ, элементы ИЛИ, при чем выходы первого счетчика .соедине ны с входами первого дешифратора, к дый i-й выход которого (1 1, ... ,п-1 подключен к управляющим входам элем тов И I-и грулпы узла.выделения, пе вый выход первого дешифратора соеди нен с первыми управляющими вхрдами первых входных элементов И групп, каждый j-й выход первого дешифратор (j 2,3,..., п-1) подключен к первы управляющим входам j-х входных элем тов И первой группы, выходы элемент И каждой i-и группы узла выделения соединены со входами элементов ИЛИ группы узла выделения, выходы которых подключены к первой группе схемы сравнения, и к информационным вх ; дам элементов И первой группы перезаписи информации, выходы которых с единены с информационными входами первого регистра, выходы которого подключены ,к информационным входам с второго по (п-1)-й входных элементов И второй группы и к инфйрмационным входам п-х входных элементов И первой группы, выходы каждого 1-го входного регистра (1 2,,..,п) соединены соответственно с информационными входами элементов И ОО группы узла обобщения, еыходы которых подключены к входам элементов ИЛИ группы узла обобщения, выходы которых соединены-с второй группой входов схемы сравнения и с информационными входами элементов И второй группы перезаписи информации, выходы которых подключены к входам второго регистра, выходы которого соединены с информационными входами с второго по (п-)-й входных элементов И первой группы и с информаI ционными входами первых входных элементов И первой группы, выходы каждого i-ro входного регистра подключены к информационным входам элементов И i-й группы узла выделения, выходы второго счетчика сое.динены с входаьи второго дешифратора, выход схемы сравнения подключен к управляющим входам элементов И первой и второй групп перезаписи информации и к входу перезапуска узла синхронизации, первый выход которого соединем с вторыми управляющими входами с второго по (п-1)-й входных элементов И первой и второй групп, вторыми управляющими входами первых входных элементов И группы и с первыми управляющими входами п-х входных элементов И группы, выходы первых и п- X входных элементов И группы соединены с входами первого и п-го входных регистров соответственно, выходы j-X входных элементов И первой и второй групп подключены к входам J-X входных элементов ИЛИ группы, выходы которых соединены с входами j-ro входного регистра соответственно., отличающ.е.еся тем, что, с целью повышения быстродействия , в него введены элементы И, ИЛИ, триггеры, элементы задержки, выход каждого К-по разряда каждого Е- го входного регистра ,..,,т, тколичество разрядов сравниваемых чисел) соединен с .первым входом К-го элемента И (1-1)-й группы, выходы элементов И каждой 1-:й группы подключены к входам i-ro элемента ИЛИ группы, выход каждого 1-го элемент.а ИЛИ группы соединен с i-м входом первого элемента ИЛИ и с входом установки в единичное состояние i-ro триггера первой группы, выход первого элемента ИЛИ подключен к входу установки в единичное состояние т|3иггера, прямой и инверсный выходы которого соединены с первыми входами первого и второго элементов И соответственно, выход первого элемента И подключен к входу первого счетчика, к входу установки в нулевое состояние триггера и к первому входу второго элемента ИЛИ, выход которого через элемент задержки соединен с первыми входами элементов Ип-й группы, выход второго элемента И подключен к второму входу второго элемента ИЛИ и к входу второго счетчика, каждый К-й выход второго дешифратора соединен с вторым входом К-го элемента Ип-й группы, выход каждого К-го элемента Ип-й группы подключен к вторым входам К-х элементов И с первой по (п+1)-ю группы, прямой и инверсный выходы каждого 1-го триггера второй группы соединены с первыми входами 1-х элементов И 1р+1)-й vf (п+2)--й групп, выход каждого j-ro элемента И i +2)- и группы подключен к вторым входам (j-l)-x элементов И (п+1)-й и (п+2)-й групп, выход первого элемента И +2}-Л группы соединен с вторыми входами первого второго элементов И, выход каждого i-го элемента И (п+1)-й группы подключен к управляющим входам элементов И i-й группы узла обобщения через 1-й элемент задержки первой . группы соединен с входом установки в нулевое состояние -.го триггера первой группы и с входом то элемента задержки второй группы, выход каждого р-го элемента задержки второй группы ,..., п-2 ) подключен к вторым управляющим входам элементов И второй группы, выход -1)-го элемента задержки второй группы соединен с вторыми управляю щими входами п-входных элементов И 3.1 группы, второй выход узла синхрони- зации подключен к вторым входам (л - 1)- X элементов И fri+l)- и и +2)- и групп, вход установки в единичное состояние р-го триггера второй группы соединен с соответствующим }-м выходом первого даиифратора, инверсный выход каждого р-го триггера второй группы подключен к третьим вхо дам элементов И р-й. группы. Источники- информации, принятые во внимание при экспертизе 1 . Авторское свидетельство СССР Н- W303, кл. G Об F 7/0, 1975. 2. Авторское свидетельство СССР М- 826339. кл. G Об F 7/06, 1979 (прототип).