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

 

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ти -РАЗРЯДНЫХ ЧИСЕЛ, содержашее 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.

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19У (l12

3(51) G 06F 7/08

1

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

К АВТОРСКОМ .Ф СВИДЕТЕЛЬСТВУ (21) 3394376/18-24 (22) 1 7.02.82 (46) 23.07.83 Бюл. ¹ 27 (72) В. И. Мхатришвили и В. А. Носачев (53) 681 .32 5 (088. 8) (56) 1. Авторское свидетельство СССР

N 263277, кл. GO6 F 7/00, 1972

2. Авторское свидетельство СССР, № 637810, кл. G06 F 7/08, 1976 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ Фи РАЗРЯДНЫХ ЧИСЕЛ, содержашее pnрегистров, (rn -1) схем сравнения, (ь| -1) переключателей,причем выходы каждого y -ro регистра, кроме последнего, соединены с первой группой входов 1 -й схемы сравнения

1 1,..., щ, rn — число сравниваемых чисел, выходы 1-й схемы сравнения соединены с входами 1 -го переключателя, о т л и ч а ю ш е е с я тем, что с целью повышения быстродействия путем сокрашения времени сортировки информации, устройство содержит группы элемен

roB ИЛИ, группы элементов И, причем выходы каждого j -ro регистра, кроме первого, соединены с второй группой, входов (1 -1)-ой схемы сравнения, первая группа входов элементов ИЛИ первой группы соединена с шиной ввода информации, выходы q -й группы элементов

ИЛИ соединены с информационными . вхо дами j -го регистра, тактовые входы регистров .соединены с первым управляюшим входом устройства, первая, вторая и гретья группы входов -х элементов ИЛИ

Р групгы соединены соответственно с выхода. ми (1 -1)-х элементов И первой и второй групп и 1 -х элементов И третьей группы, вто. рая группа входов первой группы элементов

ИЛИ соединена с выходами первых элементов И третьей группы, j =2,..., ь -1, первая и вторая группы входов

И -х элементов ИЛИ группы соединены соответственно с выходами (И -1)-х элементов И первой и второй группы, вы ходы g -го регистра соединены с информационными входами 1 -х элементов И первой и второй групп и (-1)-ми элементами И третьей группы, 1 =1...,pre, второй управляюший вход устройства соединены с управлякшими входами элемен= тов И первой группы, третий управляю- ший вход устройства — с первыми управляюшими входами нечетных элементов И второй и третьей групп, а четвертый / управляюший вход устройства — с первыми управляюшими входами четных элементов И второй и третьей групп, выход

g -го переключателя соединен с вторым управляюшим входом q -х элементов И второй и третьей групп.

1 10307

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

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

И, триггер, узлы запрета $1)

t5, Недостатком этого устройства является низкое быстродействие, так как для анализа информации во всем каталоге необходимо сформировать и сравнить с хранящимися числами 2 чисел, -где И вЂ” 1 О и разрядность чисел.

Наиболее близким к изобретению является устройство для сортировки Юи -разрядных чисел, содержащее М регистров, выходы каждого из которых соединены с входами схем сравнения, другие входы которых подключены к выходам регистра резульrara, выходные шины схем сравнения соединены через переключатели с входами элемента ИЛИ, элементы И„триг- ЗО гер, узлы запрета.

Причем выход ревенства каждой схемы сравнения соединен с управляющим входом соответствующего узла запрета, другие входы которого соединены с управляющими входами устройства, а выходы подключены к одному из входов первого элемента Vi, другой вход которого соединен с входной шиной устройства, а выход с управляющим иродом схемы сравнения, выход элемента ИЛИ соединен с входом триггера, другой вход которого соединен с шиной тактовых сигналов, а выходы— через переключатель — с входом второго элемента И, другой вход которого соединен с управляющей шиной устройства, а выход — с входом установки в нулевое состояние регистра результата, входы поразрядного управления которого подключены к выходам коммутатора, вход которо-:-о соединен с шиной тактовых сигналов, а входы установки в единичное состояние разрядов регистра результата соединены с с управляющей шиной устройства $2) .

Однако известное устройство, затрачи55 вая для упорядоченного перебора сортируемых чисел M (И +1) тактов работы, обладает сравнительно низким быстро де йс тви ем.

8 у

Белью изобретения является повышение быстродействия устроЖтва, Указанная цель досжигается тем, что устрой:.твв для сортировки NH-разрядных чисел содержашее и регистров, (w «1 ) схем сравнения, (ь -1) переключателей, причем выходы каждого 1-го регистра, кроме последнего, соединены с первой

rруппой входoa -й схемы сравнения, =.1,. „ vl,,1 -число сравниваемых чисел,. выходы;. -й схемы сравнения соединены с входами -го переключателя, устрой=тво содержит группы элементов ИЛИ, группы элементов И, причем выходы каждого (элементов И, причем выходы каждого

-го регистра., кроме первого, соединены с BropoA гру.. пой входов (1 -1)-ой схемы сравнения, первая группа входов элементов ИЛИ первой группы соединена с шиной вв-.да информации, выходы 1 -й группь;:. элементов ИЛИ соединены с информационными входами „ -го регистра, тактовые входы регистров соединены с

a8pBbIM упрВВГиюшим входом ус тро йства, первая, вторая и третья группы входов

-z элементов ИЛИ группы соединены соответственно с выходами (-))-х элементов И первой и второй Fp и -х элементов И третьей группы, BropBR групта входов первой грчп ы элементов

ИЛИ соединена с выходами первых элементов И третьей группы,. j =2,... И -l. первая и вторая группы входов щ-хэлементов ИЛИ группы соединены соответ ственно с выходами (yn -1)-х элементов

И первой и второй групп, выходы 1 -го регистра соединены с информационными входами i -x элементов И первой и второй групп и (-1)-ми элементами И третьей группы 1 = 1,... р, второй уп» равляюший вход устройства соединен с управляющими входами элементов И первой группы, третий управляющий вход устройства — с первыми управляющими входами нечетных элементов И второй и третьей группы, а четвертый управляющий вход

";-=тройства — с первыми управляющими входами четных элементов И второй и третьей групп, выход 1-го переключателя соединен = вторым управляющим входом

-х элементов И второй и третьей групп, I

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

Устройство содержит и регистров

3„„.,„1» (й1-1) схем сравнения 2,...., 2, (И1 -1) групп элементов

И 3,..., 3 „ „, 4,..., 4

5,, 5, „ групп элементов л-1

3 10307

ИЛИ 6,..., 6„, (тн-1) переключателей

7,...,7„„1, информационную шину устройства, 8, выходную шину 9, управляквцие входы устройства 10-13.

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

В начале работы переключатели 7 переводятся в положение, соответсвукецее перебору, чисел в порядке их убывания или возрастания (на чертеже положение 10 переключателя соответствуег расположению чисел в порядке их возрастания после перебора or регистра 1 к регистру 1„„).

В регистры 1 заносягся исходные числа по информационной шине 8 через группы 15 элементов 6, и далее в регистры 1

1 п через первую группу элементов

И 3,..., 3 „и элементы ИЛИ 6

6 „подачей сигналов по управляющему входу 11, открывающей первую группу 20 элементов И 3,...3 и импульса ввода информации в регистр по управлякацему входу 10.

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

97 4

2„, 2, а затем по входу 13 на группы элементов И, связанные со схемами ми сравнения 2, 2,..., а по управля|ошему входу 10 подаегся импульс ввода информации в регистр. При этом в первом такте производится обмен между парами регистров 1 н 1, 1 и 1ч причем большее число оказывается в, регистре с большим индексом. Во втором такте производится аналогичный обмен между царами регистров 1 и 1>, 1 и

1я,.... Таким образом, максимум через . (и -1.) тактов все сортируемые числа окажутся расположенными в порядке возрастания ог регистра 1 к регистру 1„

После этого может быть произведен сьем отсортированных чисел открывающего сигнала по второму управляющему входу 11 и сигналов по первому управляющему входу 10 с выходной шины 9.

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

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

Q (л +1) такт.

1930797

РНИИПИ Заказ 5214/49 Тираж 706 Поанисиое

Филиал ППП Патент", r. Ужгород, ул. Проектная,