Устройство для сортировки мк-разрядйопшс

Союз СоветскниСоцнапнстнческнкРеспубпнн ОП ИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ. СВИДЕТЕЛЬСТВУ826340до девам изобретений и еткрытиХДата опубликования описания 04.05.81. (72) Авторы изобретения В. И. Верченко, В, И. Дроздов и В; Г Калашников яв 1Изобретение относится к автоматике н вычислительной технике и может быть использовано в .системах обработки информации при реализации технических средств цифровых вычислительных машин и дискретной автоматики.Известно устройство для сортировки двоичных чисел, содержащее п регистров, выходы каждого из которых соединены со входами схем сравнения, другие входы которых подключены к выходам регистра результата, выходные шины схем сравнения соединены через переключатели со входами элемента ИЛИ элемента И, триггер и узлы запрета 11Однако это устройство сложно и требует для своей реализации больших аппаратурных затрат.Наиболее близким техническим решением к предлагаемому является устройство, содержащее о регистров, регистр результата, и схем сравнения, узлы запрета, элементы И, переключатели, коммутатор, триггер, элемент ИЛИ 12. Недостатком этого устройстваляется его сложность,Цель изобретения - упрощение устройства.Поставленная цель достигается тем,ф что в устройстве для сортировки епразрядных чисел, содержащем а регистров, элементы И, НЕ, элемент равнозначности, две группы элементов И,схему сравнения, группу элементов ИЛИ,10причем выходы регистра результата соединены со входами первой группы схе"мы сравнения, выход которой подключен к первому входу элемента равнозначности, выход которого соединен15с первым входом элемента И, выходкоторого соединен со входом управления регистра результата, выходы каждого 1-го регистра, где1,2,(щ-), подключены ко входам (1+1)-горегистра, выходы щ-го регистра соединены со входами регистра результата,выходы которого подключены к информационным входам элементов И первой3 82634 группы, выход каждого 1-го из которых подключен к первому входу 1-го элемента ИЛИ группы, где 1 = 1,2п выход каждого из которых соединен со входом 1-го разряда первого регистра5 выходы е-го регистра подключены ко входам второй группы схемы с 15 авнения и к информационным входам элементов И второй группы, выход каждого 1-го из которых соединен со вторым входом 10 1-го элемента ИЛИ группы, выход. элемента равнозначности подключен к управляющим входам элементов И первой группы и через элемент НЕ - к управляющим входам элементов И второй груп пы. На чертеже представлена функциональная схема устройства.Устройство содержит шп-разрядныхг 0 регистров 14 -1 ь регистр 2 результата, схему 3 сравнения, элемент 4 равнозначности,элемент НЕ 5, группы элементов И 61-61 и 74 -и, группу эле" ментов ИЛИ 84-8 элемент И 9, управляющую шину 10, шину 11 тактовых сигналов,Устройство работает следующим образом.1 30При сортировке чисел в порядке убывания в начале работы все разряды регистра 2 результата устанавливаются в единичное состояние (цепи начальной установки регистра 2 на чертеже35 не показаны) и на управляющую шину 10 подается .единичный потенциал, Затем в регистры 14 -111 заносится массив исходных чисел и после этого устройство готово к работе, Число, записанное в40 регистр 1, сравнивается с содержимым регистра 2 результата схемой 3 сравнения. В качестве схемы 3 сравнения может использоваться любая известная схема для сравнения двух и-разрядных чисел. Если в результате сравнения число, записанное в регистре 11 я, оказывается меньше числа, находящегося в регистре 2 результата,. то на выходе схемы 3 сравнения по"50 является единичный потенциал,. по,которому элемент 4 равнозначности разрешает прохождение тактового сигнала записи через элемент И 9 на вход записи регистра 2 результата, прохождение информации с выходов регистра 2 результата через вторую группу элементов И 71 -1, и запрещает через элемент НЕ 5 прохождение информации с 0 авыходов регистра 1 через первую группу элементов И 6-6,Тактовый сигнал, поступающий с шины 11, переписывая содержимое регистра 2 результата (единичный. вектор) через группы элементов И 7 -7, и ИЛИ 81-811 в регистр 14, а содержимое регистров 14 -1 последовательно переписывает из каждого предыдущего в .последующий регистр, причем содержимое последнего регистра 1 заносится в регистр 2 результата. Если при очередном сравнении содержимое регистра 11 вновь становится меньше содержимого регистра 2, то по следующему тактовому сигналу с шины 11 повторяется перезапись чисел из регистра в регистр, как было указано.Если при сравнении чисел оказывается, что содержимое регистра 11 больше или равно содержимому регистра 2 результата, то на выходе схемы 3 сравнения появляется нулевой потенциал иэлемент 4 равнозначности запрещает прохождение через элемент И 9 тактового сигнала записи на регистр 2 результата, прохождение информации с регистра 2 результата через вторую группу элементов И 74 -7 и разрешает через элемент НЕ 5 работу первой группе элементов И б -б4 ИПоступающий тактовый сигнал, воздействуя только на входы записи регистров 1, -1, переписывает содержимое регистра 1 через группы элементов И 61 -б, и ИЛИ 84-8 в регистр 11, а содержимое регистров 14 -1;последовательно переписывает из каждого предыдущего регистра в каждый последующий и в регистр 1, заносится новое число для сравнения с содержимым регистра 2 результата, которое за время действия такта остается неизменКак видно, в зависимости от результата сравнения содержимого регистра 2 результата и регистра 11, перезаписьчисел массива проводится через группу элементов И 6 -6 или группу И 7 -н и после каждого тактового сигнала в регистре 2 результата остается меньшее из сравниваемых чисел. Через а тактовых сигналов регистр 2 результата содержит минимальное число массива, а в регистре 11 находится единичный вектор, при этом на выходе схемы 3 сравнения присутствует нулевой потенциал.Формула изобретения 5 82634Для того, чтобы переписать минимальное число массива в регистр 11 и продолжить сортировку чисел, на управляющую шину 10 подается нулевой потенциал, соответствующий в данном случае записи в регистр 2 результата большего из двух сравниваемых чисел. Тогда схема равнозначности 4 разрешает прохождение тактового сигнала на регистр 2 результата, а его содержи О мому - через элементы И 71 -7 на элементы ИЛИ 8 -8 п, При поступлении очередного (щ+1) тактового сигнала минимальное число массива из регистра 2 результата переписывается в ре гистр 11, а единичный вектор из регистра 11 - в регистр результата. На шине 10 вновь устанавливается единичный потенциал и на этом заканчивается первый цикл сортировки чисел. По вы- щ полнению (щ)-го циклов исходные числа массива располагаются в регистрах 11-1в порядке убывания, начиная с регистра 1.При сортировке чисел в порядке 25 возрастания в начале работы все разряды регистра 2 результата устанавливаются в нулевое состояние, на управляющую шину 10 подается нулевой потенциал, а в регистры 11-11 заносится массив исходных чисел.Порядок сортировки чисел по возрастанию аналогичен сортировке чисел по убыванию, но за счет инвертирования по отношению к предыдущему случаю 5 сигнала, подаваемого на шину О управления, в данном случае больше из сравниваемых чисел, записанных в регистре 2 результата и регистре 11, после тактового сигнала остается в 40 регистре результата, а меньшее переписывается в регистр 1, через группуэлементов И 61 -6 или группу элементов И 71 -7.После поступления щ-го тактового 45 сигнала регистр 2 результата содержит максимальное число массива, а регистр 1- нулевой вектор. 50Для того, чтобы перезаписать максимальное число массива в регистри продолжить сортировку чисел, на управляющую шину 10 подается единичный потенциал, соответствующий в этом случае записи в регистр 2 результата меньшего из двух сравниваемых чисел. Схема равнозначности разрешает очередному (щ+)-му тактовому сигналу 0 6переписать содержимое регистра 2 результата в регистр 1, а нулевой век 1 тор из регистра 1- в регистр результата. На шине 1 О вновь устанавливается нулевой потенциал и на этом заканчивается первый цикл сортировки, По выполнению (щ)-го циклов исходные числа массива располагаются в регистрах1,-1в порядке возрастания, начинаяс регистра 11 . Таким образом предлагаемое устройство реализует те же функции, что и известное, но значительно проще его, так как в нем отсутствуют щ схем сравнения, щ узлов запрета, коммутатор, щ переключателей. Устройство для сортировки щп-разрядных чисел, содержащее регистров, элементы И, НЕ, элемент равнозначности, две группы элементов И, схему сравнения, группу элементов ИЛИ, причем выходы регистра результата соединены со входами первой группы схемы сравнения, выход которой подключен к первому входу элемента равнозначности, выход которого соединен с первым входом элемента И, выход которого соединен со входом управления регистра результата, о т л и ч а ю щ е " е с я тем, что, с целью упрощения устройства, в нем выходы каждого 1-го регистра, где= 1,2.,(щ) подключены ко входам (1+1)-го регистра, выходы щ-го регистра соединены со входами регистра результата, выходы которого подключены к информационным входам элементов И первой группы, выход каждого 1-го из которых подключен к первому входу 1-го элемента ИЛИ группы, где 3 - 1,2п, выход каждого из которых соединен со входом 1-го разряда первого регистра, выходи щ-го регистра подключены ко входам второй группы схемы сравнения и к информационным входам элементов И второй группы, выход каждого 1-го из которых соединен со вторым входом -го элемента ИЛИ группы, выход элемента равнозначности подключен к управляющим входам элементов И первой группы и через элемент НЕ - к управСоставитель Б. БелкинТехред М. Коштура Шевченко Корректор Г. Рещетн дакт каз 2516 7 ВНИИППодпис 7826.340 ляющим входам элементов И второй группы е, Авторское В 263277, кл. 6 2. Авторское Источники информации, В 637810, кл. 6 принятые во внимание при экспертизетотип).0 Тираж 745И Государственного комитета СССРпо делам изобретений и открытий3035, Москва, Ж, Раушская наб д. 4/5иал ППП "Патент", г. Ужгород, ул. Проектная,8свидетельство СССР06 Г 7/00, 1968,свидетельство СССР06 Р 7/00, 1976 (про