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

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

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

Недостатком этого устройства является mi3KDe быстродействие, Т9к как для анализа информации во всем каталоге необходимо сформировать и сравнить С хранящимися числами 2 чисел, - где И разрядность чисел.

, Наиболее близким к изобретению является устройство для сортировки И1 и-разрядных чисел, содержащее Vvi регистров, выходы каждого из которых соединены с входами схем сравнения, другие входы которых подключены к выходам регистра результата, выходные иганы схем сравнения соединены через переключатели с входами элемента ИЛИ, элементы И, триг гер, .узлы запрета. Причем выход ревенства каждой схемы Сравнения соединен с управляющим входом соответствующего узла запрета, другие входы которого соединены с управляющил-га входами устройства, а выходы подключены к одному из входов первого элемента И, другой вход которого соединен с входной шиной устройства, а выход с управляющим входом схемы сравнения, выход элемента ИЛИ соединен с ксодом триггера, другой ЕКОД которого соединен с шиной тактовых сигналов, а вьгхода через переключатель - с входом второго элемента И, другой вход которого соединен с управлякхцей шиной устройства, а выход - с Клодом установки в нулевое состояние регистра результата, входы поразрядного управления которого подключены к выходам коммутатора, вход котор го соединен с шиной тактовых сигналов, а входы установки в единишое состояние разрядов регистра результата соединены с с управляющей шиной устройства 2 Однако известное устройство, затрачивая для упорядоченного перебора сортируемых чисел VM ( И -fl) тактов работы, обладает сравнительно низкт1м быстро действием.

Цеяью изобретения является Повышение бь5С1гродёйствия устройства,

Укезанная цель достигается тем, что ycrpofcTBo для сортировки 17|И-разрядт ЫХ - ч51сеЛе содержащее И регистров, ( Ц1-1) схем сравнеиия, ( (ц -1) переключателей, причем выходы каждого 1-го регистра, кроме последнего, соединены с первой группой вхрдов 1 и схемы сравнешш, -i 1,,.,, п, il -число сравниваемых чисеП; выходы ( -и схемы сравнения соединены с входами -го переключателя, устройство содержит группы элементов ИЛИ, rpynribj элементов И, причем вьжоды каждого |злеменгов И, причем вькоды каждого

-го репкггра. кроме первого, соединены с второй грулпой входов ( -1 -1)-ой схемы сравнения, первая группа входов элементов ИЛИ первой группы соединена С шиной ввода информации, выходы -) -И группы элементов ИЛИ соединены с информагдаонными входами -го регистра, тактовые входы регистров соединены с первым управляющим входом устройства, первая, вторая и третья группы входов j -X элеменгов ИЛИ группы соединены соответственно с выхода.™ ( /-))-х элементов И первой и второй групп и j -х элементов И третьей группы, вторая группа входов первой гру1шы элементов ИЛИ соединена с выходами первых элеменгов И третьей , j 2,,, W-1. первая и вторая группы входов vn-x элементов ИЛИ группы соединены соответственно с выходами ( w-l)-x элеменгов И первой и второй групп, выходы i -го регистра соединены с информационными входами 1 х элементов И первой и второй групп и ( ,1)-ми элементами И третьей группы 1 1,.., yvj, второй управляющий вход устройства соединен с управляющими входами элементов И первой группы, третий управл.яюший вход устройства с первыми управляющими входами нечетных элементов И второй и третьей группы, а четвертый управляклций вход cтройства - с первьй-ш управляющими входами четных элементов И второй и третьей групп, выход i -го переключателя соединен с вторым управляющим входом i -X элементов И второй и третьей групп. На чертеже представлена функциона}1ьная ся:ема jcrpoficTBa. Устройство содержит Vr регистров З,),...) , (w-l) схем сравнения Я,...«, . ( Ж -1) групп элементов ЦП -л J yyj групп элементов

ИЛИ 6 ,.,., ) переключагелей 7v информационную шину jcrpoftcTBa, 8, выходную шину 9, управляющие входы устройства 1О-13.

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

В начале работы переключатели 7 переводятся в положение, соответсвукшее перебору; ., чисел в порядке их убывания или возрастания (на чертеже положение переключателя соответствует расположению чисел в порядке их возрастания после перебора от регистра 1 к регистру 1). В регистры 1 заносятся исходные числа по информационной шине 8 через группы элементов 6 и далее в регистры l,j ,.., 1 через первую группу элементов И 3 ,..., 3j и элементы ИЛИ б,,..., 6 подачей сигналов по управляющему входу 11, открывающей первую группу элементов И 3 3 и импульса ввода информации в регистр по управляющему входу 10.

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

2 , 2 ,...., а затем по входу 13 на

группы элементов И, связанные со схемйк ми сравнения 2 , 2ц. ,..., а по управляющему ВХОДУ 16 подается импульс ввода информации в регистр. При этом в первом такте производится обмен между парами регистров 1| и 1 , 1- и 1ф ,..., причем большее число оказывается в . регистре с большим индексом. Во втором такте производигся аналогичный обмен между парами репютров 1, 1 , Ijj. и 1с ...... Таким образом, маюсимум через .

( 171-1) тактов все сортируемые числа окажутся расположенными в порядке возрастания от регистра 1 к регистру 1. . После этого может быть произведен 1съем отсортированных чисел открывакяцего сигнала по второму управлякадему входу 11 и сигналов по первому управляющему входу Юс выходной шины 9.

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

Предлагаемое сгройство обладает по сравнению с известным более высоким быстродействием, так как для сортировки требуется только (hi -1) такт работы, в то время как в известном требовалось (о ) такт.

ц

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ти -РАЗРЯДНЫХ ЧИСЕЛ, содержашее m регистров, ( (гт-1) схем сравнения, ( ки-1) пepeключaтeлefi пpичем выходы каждого 1-го регистра, . кроме последнего, соединены с первой группой входов 1 -и схемы сравнения ,..., И1, W- число сравниваемых чисел, выходы 1-й схемы сравнения соединены, с входами 1-го переключателя, о гли чающееся гем, что с целью покышеггая &1стродействия путем сокращения времени сортировки информации, устройство содержит группы элемен гов ИЛИ, группы элементов И, причем выходы каждого i -го регистра, кроме первого, соединены с второй группой .входов ( 1 -1)-ой схемы сравнения, первая группа входов элементов ИЛИ первой группы соединена с шиной ввода информации, выходы i -и группы элементов ИЛИ соединены с информационными вхо дахш i -го регистра, тактовые входы регистров .соединены с первым управляющим входом устройства, первая, вторая и третья группы входов j -X элементов ИЛИ группы соединены соответственно с выходами ( у -1)-х элементов И первой и второй групп и j -X элементов И третьей группы, вторая группа входов первой группы элементов ИЛИ соединена с выходами первьпс элементов И третьей группы, j 2,..., hl-l, первая и вторая грзппы входов И1-Х элементов ИЛИ группы соединены соответственно с выходами ( )-x элементов И первой и второй группы, выi ходы -(-го регистра соединены с информационными входами 1 -X элементов И W С первой и второй групп- и ( i -1)-ми элементами И третьей группы, t l,..,w второй управляющий вход зстройства соединены с управляющими входами элементов И первой группы, третий управляюший вход jCTpoftcTBS - с первыми управляюшими входами нечетных элементов И 00 второй и третьей групп, а четвертый о со управляющий вход стройства - с первыми управляющими входами четных элементов И второй и третьей групп, выход -го переключателя Соединен с вторым , управляющим входом -х элементов И второй и третьей rpjitn.

-

#г

... ii.-3 .ГЛЧ

1

-4-

MKIMHUr.

с

«с«Г

W

.г

I s..«i i

zL.

.I

ZT