Устройство для сортировки разрядных чисел

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 230276 (23) 2327153/18-24 с присоединением заявки 3@в (23) Приоритет— (43) Опубликовано 151228.Бюллетень №46 (45) Дата опубликования описания 5.1273

Союз Советскмх

Сфцкаакстическкх

Респубпкк о1>6378 0 (5l) M. Кл.

G 06 Р 7/08

Государственный комитет

Совета Министров СССР по делам изобретений н открытий (53) УДК681. 325. 5 (088.8) (72) Автор изобретения

В.P.Ïoòàéoâ (71) Заявитель (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ 1т1 и -РАВРЯДННХ

ЧИСЕЛ

2" чисел, Изобретение относится к области автоматики и вычислительной техники и может быть использовано в системах обработки информации при реализации технических средств цифровых вычислительных машин и дискретной автоматики.

Известно устройство для сортировки двоичных чисел (11, в котором использованы программные методы сортировки. Оно не имеет схемы для переключения мажоритарного элемента, поэтому не может быть использовано для упорядоченного выбора чисел. Это устройство обладает низким быстродействием. 15

Наиболее близким к данному изобретению техническим решением является устройство для сортировки N A -разрядных чисел, содержащее П регистров, выходы каждого из которых соединены со входами схем сравнения, другие входы которых подключены к выходам регистра результата, выходные шины схем сравнения соединены через переключатели со входами элемента ИЛИ, элемента И, триггер, узлы запрета (2) °

Недостатком этого устройства является низкое быстродействие, так как для анализа информации во всем каталоге необходимо сформировать и сравнить с хранящимися числами где и — Разрядность чисел.

Целью изобретения является повышение быстродействия устройства.

Это достигается тем, что в предлагаемом устройстве ьыход равенства каждой схемы сравнения соединен с управляющим входом соответствующего узла запрета, другие входы которого подключены к управляющим шинам устройства, а выход — к одному из входов первого элемента И, другой вход которо î соединен с входной шиной устройства, а выход — с управляющим входом схемы сравнения, выход элемента ИЛИ соединен со входом триггера, другой вход которого соединен с шиной тактовых сигналов, а выходы — через переключатель — со входом второго элемента И, другой вход которого соединен с управляющей шиной устройства, а выход со входом установки в нулевое состояние регистра резульiата входы псраз рядного управления которого подключены к выходам коммутатора, вход которого соединен с шинсй тактовых сигналов, а входы установки в единич йое состояние разрядов регистра результата подключены к управляющей шине устройства.

637810

Благодаря указанным конструктивным связям повышается быстродействие, так

Как для упорядоченного перебора этих чисел Требуется (((+1). Ф тактов ра бОты

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

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

Устройство содержит 3П регистров 1, 3О

В кОтОрые записываются исхОдные чис ла, и регистр результата 2, в котором формируется ОчереднОе максимальнОе (минимальное) BHOJIG единичHble H нулеВые Выходы регистров 1 и 2 соединены )5 с информационными вхОдами схем срав нениЯ Зр упраВлЯющие, Входы которых подключены к входной шине 4 через перВые элементы И 5. Первые и втОрые выходы неравенства схем Зу в зависи- а мости от положения переклю ателя 6, связаны с соответству3ощимн входами элемента ИЛИ 7, выход которого соединен со входом установки В нулевое состояние триггера 8. Выходы равенства схем cpBBнения 3 подкл3очены к управ

5 ляющему входу соответствующих узлов запрета 9, вторые и третьи входы которых связаны сОответстненнО с управляющими шинами 10 H 11. Выходы узлов

9 соединены со вторыми входами соответствующих элементОВ И 5. ВХОД уста ковки в. единичное состояние триггера

8 подключен к шине тактовых сигналов

12, " его прямой и инверсный Выходы связаны через переключатель 6 с пер- 85 вым входом второго элемента И 13, ВToрой вход которого подключен к управляющей шине 14. Выход элемента И 13 соединен с входом установки В нулевое состояние регистра результата 2.Входы 40 поразрядного управления регистра результата 2 подк e-leHII к соответствующим выходам коммутатора 15, вход которого связан с шиной тактовых сигналов 12. Входы установки разрядов регистра результата 2 В единичное состояние соединены с управля3ощЕй шнной 16. устройство работает следующим образом.

В начале работы переключатель 6 пе-@ реводится в положение, соответствующее сортировке чисел в порядке их убывания илн возрастания (положение переключателя 6 на чертеже соответствует сортировке чисел в порядке их убывания). Затем в регистры 1 заносятся исходные числа, а регистр результата

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

После это(.о устройство го-ово к работеВ5

Теперь на шину 12 подается первый тактовый сигнал,.который переводит коммутатор 15 в первое положение. При этом подготавливается к работе (по первому входу поразрядного управления) первый (старший) разряд регистра результата 2. Кроме того, триггер 8 устанавливается В 1 и подготавливает элемент И 13 к работе. Затем иа шину 16 подается сигнал, который заносит в первый (старший) разряд регистра результата 2 единицу (по цепи, подготовленной первым Выходом коммутатора 15). После этого на шиHу 4 подается сигнал, который проходит через Открытые элементы И 5 на управляющие входы всех схем сравнения 3 (a качестве их могут быть использованы любые известные схемы для сравнения двух П -разрядных чисел, имеющие выходы неравенства >, (и выход равенства), Схемы сравнения 3 осуществляют сравнение чисел (Н3}, находящихся в принадлежащих им регистрах 1, с числом, находящимся в регистре результата 2 (100...0). В результате этого сравнения сигнал на Выходе

° неравенства больше или равно в какой-либо схеме сравнения 3 появится в том случае, если число в соответствующем регистре 1М Ь 100...0 (сигналы, появляющиеся на выходах равенства схем 3 не оказывают Воздействия на узлы запрета 9, так как сигнал на управляющую шину 10 не подан).

Таким образом, если хотя бы в одном из регистров 1 найдется число К;

100...0, то сигнал появится на выходе соответствующей схемы сравнения 3, пройдет через переключатель 6, элемент ИЛИ 7 и поступит иа вход установки В нулевое состояние триггера

8. Триггер 8 установится в нуль и подаст на вход элемента И 13 запрещающий сигнал.

ПОС33е окончания сигнала на шине

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

Итак, к концу первого такта работы в первом разряде регистра результата

2 будет записана 1, если, хотя бы в одном из регистров 1, найдется число, большее или равное 100...0.

Если же во всех регистрах 1 окажутся числа меньшие, чем 100...0, то на выходах неравенства больше или равно схем сравнения 3 сигналов, не будет, следовательно, триггер 8 останется в положении 1 . Тогда сигнал с шины 14 пройдет через открытый элемент И 13 на входы установки в нулевое состояние регистра результата 2. Через подготовленную цепь (IIo первому входу поразрядного управления) первый разряд регистра результата 2 вернется в положение 0 .

637В10

Таким образом, если во всех регистрах 1 окажутся числа меньшие, чем 100...0, то к концу первого такта работы в первом (старшем) разряде регистра результата 2 будет записан 0 .

Затем на шину 12 подается второй тактовый сигнал, и работа устройства 5 повторяется. К концу второго такта работы во втором разряде регистра 2 будет записана 1, если хотя бы в одном из регистров 1 найдется число, большее или равное числу, сформирован-)0 ному в регистре результата 2 за два такта работы. В противном случае во втором разряде регистра результата 2 будет записано 0 .

После окончания и тактов в регист- 15 ре результата 2 будет сформировано число, равное максимальному значению числа, хранящемуся .в одном из регистров 1.

В (ll+1) такте коммутатор 15 сигналом по шине 12 переводится в (П+1) положение, чтобы не изменить содержимое регистра 2. Затеи на шину 10 подается управляющий сигнал, подготавливающий к работе узлы запрета 9.

Сигналы по другим шинам (4, 14,16) поступают также, как и в предыдущих тактах. Сигнал по шине 16 никаких изменений в регистре результата 2 не вызовет, так как коммутатор 15 переведен в (я+1) положение. Сигнал, поступающий по шине 4, пройдет ка управляющие входы всех схем сравнения 3, но появится на выходе равенства только той схемы сравнения 3, где в принадлежащем ей регистре 1 эапи- 35 сано максимальное число, равное сформированному в регистре результата 2.

Сигнал с выхода равенства соответствующей схемы сравнения 3 поступит на управляющий вход узла запрета 9, 40 принадлежащего данной схеме сравнения 3. Узел запрета 9 переведется, в закрытое состояние и элемент И 5 Окажется закрытым по второму входу. Таким образом в дальнейшем сигнал с шины 4 уже ие будет проходить ка данную схему сравнения 3, а значит регистр 45

1, где находится уже найденное максимальное число, в дальнейшей работе участия принимать ке будет.

После этого содержимое регистра результата 2 выбирается (максималь- 50 кое число), а он сбрасывается в исходное (нулевое) состояние.

Затем ка шику 12 подается очередной тактовый сигнал, и устройство начинает поиск максимального чиспа иэ оставшихся чисел (без учета уже выбранных). Работа устройства циклически повторяется до тех пор, пока ке будет осуществлена сортировка всех чисел, находящихся в регистрах

1, в порядке их убывания.

Для сортировки чисел в порядке их возрастания переключатель 6 переводится в другое положение. Работа устройства происходит аналогично ранее описанному, только теперь каждый раз будет Осуществляться выбор минимального из оставшихся чисел.

При этом в очередном разрядке регистра 2 будет сохраняться 1, если в данном такте работы числа во всех кеисключенных иэ работ регистров

1 будут больше или равны числу, сформированному в регистре 2 зв прошецшие такты работы (включая и данный). В противном случае в данном разряде регистра 2 будет сформирован 0 е

На (tl+1) такте очередное минимальное число будет выбрано из регистра

2, а соответствующий регистр 1 будет исключен из дальнейшей работы с помок ю узла запрета 9, принадлежащего данному регистру 1. устройство Обладает =-ысоккм быст" оДЕйСТВИЕМе Так Хак ДЛЯ COPT PCS ã(Á

М к -разрядных чисел требуетса

Al ° (0+1) тактов работы, в то время как для известных устройств неОбходкмо

2 тактов.

Формула кзобре еккя

УстройствО для сортировки % к разрядных чисел, содержащее и регистров, выходы каждого из которых соецккекы со входамк схем сравнения, другие входы которых подключены к выходам регистра результата, выходные шккы схем сравнения соединены через переключатели со входами элемента ИЛИ, элементы И, триггер, у" ë.û запрета, О т л и ч а ю щ е е с я тем, То, с целью повыаекия быстродействия, в кем выход равенства каждой схемы сравнения соединен с управляющим входом соответствующего узла запрета, другие входы которого подключены к управляющим шикам устройства, а выХОД вЂ” К ОДКОМУ ИЗ ВХОДОВ ПЕРВОГО ЭЛЕмента И, другой нход которОго соецикек с БХОцнОЙ мккОЙ устройства, а выход — с управляющим входом схемы сравнения, выход элемента ИЛИ соеДИКЕК СО ВХОДОМ ТРКГГЕРа, ДРУГой вход которого соединен с шиной тактовых сигналов, а выходы — через

ПЕРЕКЛЮЧаТЕЛЬ вЂ” CO ВХОДОМ КТОРОГО элемента И, другой вхОД кОТОРагО Соединен с управляющей 1ккой устройства, а выход — со входом устаковкк в нулевое состоякке регистра результата, входы поразрядкого управлекия которого подключены к выходам ком1утатора, ВХОД КОТОРОГО СОЕДИКЕК С Шиной таКтовых сигналов, а входы устаковки в едкккчное состояние разрядов регистра результа — à подключекы к управляющей шине устройства.

Источники информации, принятые во внимание прк экспертизе:

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

463968 кл. 5 06 Г 7/00, 1954.

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

Р 263277, кл. 5 06 Р 7/00, 1956.

Составитель В.Белкин

Редактор H.Kàìåíñêàÿ Техред М.Борисова Корректор Д.Мельниченко

Заказ 7107/39 Тираж 784 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д.4/5 филиал ППП Патент, г.ужгород, ул. Проектная, 4