Устройство для сортировки разрядных чисел Советский патент 1978 года по МПК G06F7/08 

(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ m П-РАЗРЯДНЫХ

ЧИСЕЛ

Благодаря указанкьй.1 конструктивным свгэям повьааается быстродействие, так как для упорядоченного перебора этих Чисел требуется (й4-1).гй тактов ра боты.

Это позволяет значительно (на 2-4 порядка) повысить быстродействие устройства для сортировки ш п -разрядных чисел.

Функциональная схема устройства приведена на чертеже.

Устройство содержит m регистров 1, S которые записываются исходные чис. ла, и регистр результата 2, в котором формируется очередное максимальное {минимальное) число. Единичные и нулевые выходы регистров 1 и 2 соединены с информационными входами схем сравнения 3, управляющие.входы которых подключены к входной шине 4 через первые элементы И 5, Первые и вторые выходы неравенства схем 3, в зазнсимости от положения переключателя 6, связаны с соответствующими входами элемента ИЛИ 7, выход которого соеди нен со входом установки в нулевое состояние триггера 8, Выходы равенства схем сравнения 3 подключены к управляющему входу соответствующих узлов запрета 9, вторые и третьи входы которых связаны соответственно с управляющими шинами 10 и 11с Выходы узлов 9 соединены со вторыми входами соответствующих элементов И 5. Вход установки в- единичное состояние триггера 8 подключен к шине тактовых сигналов 12, а его прямой и инверсный выходы связаны через переключатель 6 с первым входом второго элемента И 13, второй вход которого подключен к управлящей щине 14. Выход элемента И 13 соединен с входом установки в нулевое состояние регистра результата 2.Вхогда поразрядного управления регистра результата 2 подключены к соответствующим выходам коммутатора 15, вход которого связан с шкной тактов ых сигналов 12, Входы установки разрядов регистра результата 2 в единичное состоние соединены с управляющей шиной 16.

Устройство работает следующим образом.

В начале работы переключатель б ne револится в положение, соответствующее сортировке чисел в порядке их убывания или возрастания (полох ение переключателя 6 на чертеже соответствует сортировке чисел в порядке их убывания) . Затег в регистры 1 заносятся исходные числа, а регистр результата 2 и KONtMyTaTop 15 сбрасываются в исходное состояние ( цепи занесения информации в регистры 1 и установки в нуль регистра 2 и коммутатора 15 на чертеже не показаны) . Па. шину 11 подается сигнал, устанавливающий все узлы запрета 9 в такое положение, что элементы И 5 оказываются открытыми. После этоЬо устройство готово- к работ

Теперь на шину 12 подается первый тактовый сигнал,.который переводит ко даутатор 15 в первое положение. При этом подготавливается к работе ( по первому входу поразрядного управления) первый (старший) разряд регистра ре«зультата 2, Кроме того, триггер 8

1 и подготавустанавливается в

ливает элемент И 13 к работе. Затем на тину 16 подается сигнал, который заносит в первый (старший) разряд регистра результата 2 единицу ( по цепи, подготовленной первым выходом коммутатора 15). После этого на шину 4 подается сигнал,который проходит через открытые элементы И 5 на управляющие входы всех схем сравнения 3 (в качестве их могут быть использованы любые известные для сравнения двух п -разрядных чисел, имеющие выходы неравенства , 4 и выход равенства), Схемы сравнения 3 осуществляют сравнение чисел (N1), находящихся в принадлежащих им регистрах 1 с числом, находящимся в регистре результата 2 (100,.,0). В результате этого сравнения сигнал на выходе неравенства больше или равно в ,;какой-либо схеме сравнения 3 появится в том случае,, если число в соответствующем регистре iMJSlOO.,,0 (сигналы, появляющиеся на выходах равенства схем 3 не оказывают воздействия на узлы запрета 9, так как сигнал на управляющую шину 10 не подан),

Таким образом, если хотя бы Б одно из регистров 1 найдется число К; i Я00,..0, то сигнал появится на выходе соответствующей схемы сравнения . 3 пройдет через переключатель б, элемент ИЛИ 7 и поступит на вход установки в нулевое состояние триггера 8. Триггер 8 установится в нуль и подаст на вход элемента И 13 запрещающи и с и г и ал.

После окончания сигнала на шине 4 подается сигнал на шину 14, так как элемент И 13 закрыт, то этот сигнал дальше в устройство не поступит а в регистре результата 2 сохранится записанная в старшем разряде . Итак, к концу первого такта работы в первом разряде регистра результата 2 будет записана , если, хотя бы в одном из регистров 1 найдется число, большее или равное iOO..,0.

Если же во всех регистрах 1 окажутся числа меньш}5е, чем 100...О, то на выходах неравенства больше али равно схем сравнения 3 сигналов не будет, следовательно, триггер 8 останется в положении . Тогда сигнал с шины 14 пройдет через открытый элемент и 13 на входы установки в нулевое состояние регистра результата 2. Через подготовленную цепь (по первому входу поразрядного управления) первый разряд регистра результата 2 вернется в положение О. 5 Таким образом, если во всех регистрах 1 окажутся числа меньшие, чем 100...О, то к концу первого так та работы в первом (старшем) разряде регистра результата 2 будет записан О . Затем на шину 12 подается второй тактовый сигнал, и работа устройства повторяется. К концу второго такта работы во втором разряде регистра 2 будет записана , если хотя бы в одном из регистров 1 найдется число большее или равное числу, сформирова ному в регистре результата 2 за два такта работы. В противном случае во втором разряде регистра результата будет записано . После окончания п тактов в регист ре результата 2 будет сформировано число, равное максимсшьному значению числа, хранящемуся в одном из регист ров 1. В (п+1) такте коммутатор 15 сигна лом по шине 12 переводится в (rt+l) положение, чтобы не изменить содержи мое регистра 2. Затеи на шину 10 подается управляющий сигнал, подгота ливаюищй к работе узлы запрета 9, Сигналы по другим шинам (4,14,16) поступают также, как и в предьщувщх тактах. Сигнал по шине 16 никаких изменений в регистре результата 2 не вызовет, так как коммутатор 15 переведен в (t7+l положение. Сигнал, поступающий по шине 4, пройдет на управляющие входы всех схем сравнения 3, но появится на выходе равенст ва только той схемы сравнения 3, где в принадлежащем ей регистре 1 записано максимальное число, равное сфор мированнсму в регистре результата 2 Сигнал с выхода равенства соответствующей схемы сравнения 3 поступит на управляквдий вход узла запрета 9, принадлежащего данной схеме сравнения 3. Узел запрета 9 переведете в закрытое состояние и элемент И 5 ока жется закЕ«тым по второму входу. Таким образом в дальнейшем сигнал с ши ны 4 уже не будет проходить на данну схему сравнения 3, а значит регистр 1, где находится уже найденное максимальное число, в дальнейшей работе участия принимать не будет. После этого содержимое регистра результата 2 выбирается (максимальное число), а он сбрасывается в исходное (нулевое) состояние. Затем на щину 12 подается очередной тактовый сигнал, и устройство начинает поиск максимального числа из оставшихся чисел (без учета уже выбранных). Работа устройства циклически повторяется до тех пор, пока не будет осуществлена сортировка всех чисел, находящихся в регистрах 1, в порядке их убывания. Для сортировки чисел в порядке их возрастания переключатель 6 пере0водится в другое положение. Работа устройства происходит аналогично ранее описанному, только теперь каждый раз будет осуществляться выбор минимгшьного из оставшихся чисел. При этом в очередном разрядке регистра 2 будет сохраняться Ч, если в данном такте работы числа во всех неисключенных из работ регистров 1будут больше или равны числу, сформированному а регистре 2 за прошедшие такты работы (включая и данный). В противнее случае в данном разряде регистра 2 будет сформирован О, На (п+1) такте очередное минимальное число будет выбрано из регистра 2, а соответствующий регистр 1 будет исключен из дальнейшей работы с помошью узла запрета 9, принадлежащех-о данному регистру 1. Устройство обладает высоким быстродействием, так как для сортировки № rj -разрядных чисел требуется «1{г1-И) тактов работы, в то время как для известных устройств необходимо 2тактов. Формула изобретения Устройство для сортировкн п п -разрядных чисел, содержацдее п регистров , выходы каждого нз которых соединены со входами схем сравнения, другие входы которых подключены к выходам регистра результата, выходные шины схем сравнения соединены через переключатели со входагли элемента ИЛИ, элементы И, триггер, узлы запрета, отличаю щеес я тем, что, с целью повьацення бкстродействип, в нем выход равенства саждоя схемы сравнения соединен с управляющим входом соответстну ощего узла запрета, другие входы которого подключены к управляющим шинам устройства, а выход - к одному из входов первого элемента И, другой вход которого соединен с входной шиной устройства, а выход - с управляющим входом схемы сравнения, выход элемента ИЛИ соединен со входом триггера, другой вход которого соедкнек с uiHHOft тактовых сигналов, а выходы - через переключатель - со входом второго элемента И, другой вход которого соединен с управляющей тиной устройства, а выход - со входом установки Е нулевое состояние регистра результата, входы поразрядного управления которого подключены к выходам коад 1угатора, вход которого соединен с шино.ч тактовых сигналов, а входы установки в единичное состояние разрядов регистра результата подключены к управляющей шине устройства. Источники информации, принятые во внимание при экспертизе: 1. Авторско свидетельство ССС& « 463968, кл. Q 06 Р 7/00, 1954. 2.Авторское свидетельство СССР 263277, кл.СчОб Р 7/00, 1956.

;