УСТРОЙСТВО ДЛЯ СОРТИРОВКИ МК-РАЗРЯДЙоПшс! Советский патент 1981 года по МПК G06F7/08 

. Изобретение относится к автоматике и вычислительной технике и может быть использовано в система.х обработки информации при реализации технических средств цифровых вычислительных машин и дискретной автоматики. Известно устройство для сортировки двоичных чисел, содержащее п регистров, выходы каждого из которых соединены со входами схем сравнения, другие входы которых подключены к выходам регистра результата, выходные шины схем сравнения соединены через переключатели со входами элемента ИЛИ злемента И, триггер и узлы запрета ij Однако это устройство сложно и требует для своей реализации больших аппаратурных затрат. Наиболее близким техническим решением к предлагаемому является устройство, содержащее m регистров, регистр результата, п схем сравнения, узлы запрета, элементы И, переключатели, коммутатор, триггер, элемент ИЛИ 2. Недостатком зтого устройства является его сложность. Цель изобретения - упрощение устройства. Поставленная цель достигается тем, что в устройстве для сортировки mnразрядных чисел, содержащем m регистров, злементы И, НЕ, элемент равнозначности, Д1ве группы элементов И, схему сравненияу группу элементов ИЛИ, причем выходы регистра результата соединены со входами первой группы схемы сравнения, ыход которой подключен к первому входу злемента равнозначности, выход которого соединен с первым входом элемента И, выход которого соединен со входом управления регистра результата, выходы каждого i-ro регистра, где i 1,2,..., . (m-l), подклю.чены ко входам ()-ro регистра, выходы т-го р1егистра соединены со входами регистра результата, выходы которого подключены к информационным входам элементов И первой группы, выход каждого j-ro из которых подключен к первому входу j-ro эле- , мента ИЛИ группы, где j 1,2,...,п, выход каждого из которых соединен со входом J-го разряда первого регистра, выходы т-го регистра подключены ко входам второй группы схемы С15авнения и к информационным входам элементов И второй группы, выход каждого j-ro из которых соединен со вторым входом j-ro элемента ИЛИ группы, выход элемента равнозначности подклк чен к управляющим входам элементов И первой группы и через элемент НЕ - к управляющим входам элементов И второй групНа чертеже представлена функциональная схема устройства. Устройство содержит mn-разрядных регистров , регистр 2 результата, схему 3 сравнения, элемент 4 равнозначности, элемент НЕ 5, группы элементов И и , группу элементов ШШ , элемент И 9, управляющую шину 10, шину 11 тактовых сигналов. Устройство работает следующим образом. I При сортировке чисел в порядке убывания в начале работы все разряды регистра 2 результата устанавливаютс в единичное состояние (цепи началь„ ., ной установки регистра 2(на чертеже не показаны) и на управляющую шину 1 подается .единичный потенциал. Затем в регистры 1 -ly, заносится массив ис ходных чисел и после этого устройств готово к работе. Число, записанное в регистр 1)ц, сравнивается с содержиьв)1м регистра 2 результата схемой 3 сравнения. В качестве схемы 3 сравнения может использоваться любая известная схема для сравнения двух п-разрядных чисел. Если в результате сравнения число, записанное в регистре т оказывается меньше числа, находящегося в регистре 2 результата то На выходе схемы 3 сравнения появляется единичный потенциал, по/которому элемент 4 равнозначности разрешает прохождение тактового сигнала записи через элемент И 9 на вход записи регистра 2 результата, прохожденне информации с выходов регистра 2 результата через вторую группу элементов И 7 -7( и запрещает через элемент НЕ 5 прохождение информации с выходов регистра 1уу через первую группу элементов И . Тактовый сигнал, поступающий с шины 11, переписывая содержимое регистра 2 результата (единичный вектор) через группы элементов И 7 -7у и ИЛИ в регистр Ц, а содержимое регистров , последовательно переписывает из каждого предыдущего в последующий регистр, причем содержимое последнего регистра 1 заносится в регистр 2 результата. Если при очередном сравнении содержимое регистра 1уу, вновь становится меньше содержимого регистра 2, то по следующему тактовому сигналу с шины 11 повторяется перезапись чисел из регистра в регистр, как было указано. Если при сравнении чисел оказывается, что содержимое регистра 1 больше или равно содержимому регистра 2 результата, то на выходе схемы 3 сраврения появляется нулевой потенциал и I элемент 4 равнозначности запрещает прохождение через элемент К 9 такто сигнала записи на регистр 2 результата, прохождение информации с регистра 2 результата через вторую группу элементов И 7 -7 и разрешает через элемент НЕ 5 работу первой группе элементов И 6,-6и. Поступающий тактовый сигнал, воздействуя только на входы записи регистров переписывает содержимое регистра через группы элементов И , и ИЛИ j в регистр 1, а содержимое регистров последовательно переписывает из каждого предыдущего регистра в каждый после„,„„.. „ „ „ i дующий ив регистр 1 заносится новое число для сравнения с содержимым регистра 2 результата, которое за время действия такта остается неизменным. Как видно, в зависимости от результата сравнения содержимого регистра 2 результата и регистра 1, перезапись чисел массива проводится через группу элементов И 6 -6 или группу И 7/( -7ц и после каждого тактового сигнала в регистре 2 результата остается меньшее из сравниваемых чисел. Через m тактовых сигналов регистр 2 результата содержит минимальное число массива, а в регистре lyy, находится единичный вектор, при этом на выходе схемы 3 сравнения присутствует нулевой потенциал.

Для того, чтобы переписать минимальное число массива в регистр и продолжить сортировку чисел, на управляющую шину 10 подается нулевой потенциал, соответствующий в данном случае записи в регистр 2 результата большего из двух сраБНИваемь х чисел. Тогда схема равнозначности 4 разрешает прохождение тактового сигнала на регистр 2 результата, а его содержимому - через элементы И 7/( -7j на элементы ИЛИ 8 -8,, При поступлении очередного (m+l) тактового сигнала минимальное число массива из регистра 2 результата переписывается в регистр Ц , а единичный вектор из регистра 1 - в регистр результата. На шине 10 вновь устанавливается единичный потенциал и на этом заканчивается первый цикл сортировки чисел. По выполнению (m-l)-ro циклов исходные числа массива располагаются в регистрах в порядке убывания, начиная с регистра lyy,.

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

Порядок сортировки чисел по возрастанию аналогичен сортировке чисел по убьгоанию, но sai счет инвертирования по отношению к предыдущему случаю сигнала, подаваемого на шину 10 управления, в данном случае больше из сравниваемых чисел, записанных в регистре 2 результата и регистре ) после тактового сигнала остается в регистре результата, а меньшее переписывается в регистр 1( через группу элементов И 6( -бц или группу элементов И 7 -7,,.

После поступления т-го тактового сигнала регистр 2 результата содержи максимальное число массива, а регистр 1 yvi - нулевой вектор.

Для того, чтобы перезаписать мак-

симальное число массива в регистр 1 и продолжить сортировку чисел, на управляющую шину 10 подается единичный потенциал, соответствующий в этом случае записи в регистр 2 результата меньшего из двух сравниваемых чисел. Схема равнозначности разрешает очередному (пи-1 )-му тактовому сигнал

переписать содержимое регистра 2 результата в регистр 1, а нулевой век|тор из регистра 1 - в регистр результата.

На шине 10 вновь устанавливается нулевой потенциал и на этом заканчивается первый цикл сортировки. По выполнению (m-l)-ro циклов исходные числа массива располагаются в регистрах 1,-lyy, в порядке возрастания, начиная с регистра 1.

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

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

Устройство для сортировки mn-разрядньЬс чисел, содержащее регистров, элементы И, НЕ, элемент равнозначности, две группы элементов И, схему сравнения, группу элементов ИЛИ, причем выходы регистра результата соединены со входами первой группы схемы сравнения, выход которой подключен к первому входу элемента равнозначности, выход которого соединен с первым входом элемента И, выход которого соединен со входом управления регистра результата, отлич азощее с я тем, что, с целью упрощения устройства, в нем выходы каждого i-ro регистра, где 1,2,...,(m-J) подключены ко входам (i+l)-ro регистра, выхода т-го регистра соединены со входами регистра результата, выходы которого подключены к информационным входам элементов И первой группы, выход каждого j-ro из которых подключен к первому входу j-ro элемента ИЛИ групгал, где j },2,...,п, выход каждого из которых соединен со входом J-ro разряда первого регистра, выходы т-го регистра подключены ко входам второй группы сравнения и к информационным входам элементов И второй группы, выход каждого J-ro из которых соединен со вторым входом J-ro элемента ИЛИ группы, выход элемента равнозначности подключен к управлякщим входам элементов И первой группы и через элемент НЕ - к управ78263408

ляющим входам элементов И второй труп- 1 . Авторское свидетельство СССР .- № 263277, кл. G 06 F 7/00. 1968.

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

Источники информации,№ 637810, кл. G 06 Р7/00, 1976 (пропринятые во внимание при экспертизе j тотип).