Устройство для сортировки чисел

 

ОП ИСАНИ

ИЗОБРЕТЕН И

К АВТОРСКОМУ СВИДЕТЕЛЬСТВ

Союз Советски к

Социалистическик

Республик

083. (6l ) Дополнительное к авт. свнд-ву (22)Заявлено 08.09.81 (2t) 3335032/18

Ь с присоединением заявки М (23) Приоритет.

Опубликовано 28. 02 . 83 . Бюллетень

7/06

Г4с7мрстееяный квмктют

СССР

681

) ве делен кзебретенкк н еткрытнк

Дата опубликования описания 28 .О

И. Крылов и Н. Н. Шубина Ы,, й". "„,,:,. й,, °, l / (72) Авторы изобретения (71) Заявитель (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ мент И (1).

Изобретение относится к автоматике и вычислительной технике и может быть использовано при реализации технических средств 3ВМ и создании устройств обработки статисти5 . чес кой и нформации .

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

Наиболее близким к предлагаемому по техническому решению является ро устройство для сортировки чисел, со- держащее и кольцевых регистров,,управляющие элементы И-ИЛИ, входные элементы И-ИЛИ, дешифраторы, счетчики, элементы И, ИЛИ, регистр, узел синхронизации, первый выход которого соединен с установочными входами кольцевых регистров, с управляющим входом схемы сравнения и с входом первого счетчика, выходы которого подключены к входам первого дешифратора и установочным входам второго счетчика, выходы которого соединены с входами второго дешифратора, каждый i- ый выход первого дешифратора (i=1,2,..., n -1) соединен с i-ым входом первого управляющего элемента,И-ИЛИ.и с первым входом i- го входного элемента И-ИЛИ, выход каждого 1- го входного элемента И-ИЛИ подключен к входу 1- го кольцевого регистра, выход каждого i- ro кольцевого регистра соединен с (i+n - 1)-ым входом первого управляющего элемента И.-ИЛИ, выход которого подключен к первому информационному входу схемы сравнения и к первому вх, ду первого элемента И, выход которого соЦель изобретения - повышение быстродействия устройства.

Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее и входных регистров, регистры, узел выделения, узел обобщения, счетчики, дешифраторы, схему сравнения1 группы входных элементов И, группы элементов И перезаписи информации узел синхрони} зации, группы элементов И ИЛИ, элементы И, ИЛИ. причем выходы первого

3 10010 единен с первым установочным входом регистра, первый выход которого подключен к вторым входам 1,2...,, (n - 1)-го входных элементов И-ИЛИ, каждый i-,ûé выход второго дешифратора соединен с i-ым входом второго управляющего элемента И-ИЛИ, каждый 1- ый выход второго дешифратора (j=-1,2,..., п-2 ) подключен к третьим входам (j+1)-го входного элемента И-ИЛИ, (и- 1)-ый выход второго дешифратора соединен с первым входом и - го входного элемента И-ИЛИ, выход которого соединен с входом и --го кольцевого регистра, выход которого подключен к и -му входу второго управляюцего элемента И-ИЛИ, выход каждого К-го кольцевого регистра (K=2,3,..., n-1) соединен с (К+и- 1)ым входом второго управляющего эле- .20 мента И-ИЛИ, выход которого подключен к второму информационному входу схемы сравнения и к первому входу второго .элемента И, выход которого соединен с вторым установочным вхо- 2$ дом регистра, второй выход которого подключен к четвертым входам 2,3,..., (и- 1)- ro входных элементов И-ИЛИ и к второму входу и -го элемента И-ИЛИ, первый выход схемы сравнения соеди- $р нен с вторыми входами элементов И и с первым управляющим входом узла синхронизации, второй выход которого подключен к информационному входу регистра и к вторым установочным вхо3$ дам кольцевых регистров, второй выход схемы сравнения соединен с первым входом элемента ИЛИ, второй вход которого подключен к третьему выходу узла синхронизации, а выход - к информационному входу второго счетчика, выход которого соединен с вторым управляющим. входом узла синхронизации(2 ).

Недостаток устройства - низкое

1 45 быстродейст вие.

83 счетчика соединены с входами первого дешифратора, каждый 1-й выход которого (i l,..., и »1) подключен к уп:равляющим входам элементов И 1-й группы узла выделения, первый выход первого дешифратора соединен с первыми управляющими входами первых входных элементов И rpynn, каждый

1-й выход первого дешифратора (j=

2,,и -1) подключен к первым управляющим входам j-x входных элементов

И первой группы, выходы элементов И каждой i-.é группы узла выделения соединены с входами элементов ИЛИ группы узла выделения, выходы которых подключены к первой группе входов схемы сравнения и к информационным входам элементов И первой группы перезаписи информации, выходы которых соединены с информационными входами первого регистра, выходы которого подключены к информационным входам с второго по (n -1)- 1 входных элементов И второй группы и к информационным входам и -х входных элементов И первой группы, выходы каждого 1- ro входного регистра (1 =

"=2,..., n) соединены с информационными входами элементов И ((- 1)- 2 группы узла обобщений, выходы которых подключены к входам элементов

ИЛИ группы узла обобщения, выходы которых соединены с второй группой входов схемы сравнения и с информационными входами элементов И второй группы перезаписи информации, выходы которых подключены к входам второго регистра, выходы которого соединены с информационными входами с второго no (n -1)- и входных элементов И первой группы и с информационными входами первых входных элементов И первой группы, выходы каждого i- го входного регистра подключены к информационным входам элементов И i-й группы узла выделения, выходы второго счетчика соединены с входами второго дешифратора, выход схемы сравнения подключен к управляющим входам элементов И первой и второй групп перезаписи информации и к входу перезапуска узла синхронизации, первый выход которого соединен с вторыми управляющими входами с второго по (и - 1)-й входных элементов И первой и второй групп, вторыми управляющими входами первых входных элементов И группы и с первыми управляющими входами и†х входных

5 1001 элементов И группы, выходы первых и и -х входных элементов И группы соединены с входами первого и п - го входных регистров соответственно, выходы j x входных элементов Й первой и второй групп подключены к входам

J-х входных элементов ИЛИ группы, выходы которых соединены с входами у го входного регистра соответственно, введены элементы И, ИЛИ, триггеры, элементы задержки, выход каждого К-го разряда каждого 1- го входного регистра (К=I,...,m, m - -количество разрядов сравниваемых чисел) соединен с первым входом К-го элемента И (f- 1)- 1I- гrр у пnпnы, выходы элементов И каждой i-.é группы подключены к входам

i- го элемента ИЛИ группы, выход каждого 1- го элемента ИЛИ группы соединен с. 1-м входом первого элемента 20

ИЛИ и с входом установки в единичное состояние i-го триггера первой группы, выход первого элемента ИЛИ подключенк входу установки в единичное состоя ние триггера, прямой и инверсный вы- 25 ходы которого соединены с первымивходами первого и второго элементов

И соотйетственно выход первого элемента И подключен к входу первого, счетчика, к вх< ду установки в нулевоеЗ0 состояние триггера и к. первому входу второго элемента ИЛИ, выход которого через элемент задержки соединен с первыми входами элементов И и — и группы, выход второго элемента И под. ключен к второму входу второго элемен35 та ИЛИ и к входу второго счетчика, каждый К-ый выход второго дешифратора соединен с вторым входом К-.го элемента И л -й группы, выход каждого

К-го элемента И и-й группы подключен к вторым входам К-х элементов И с первой по (и+ 1)- ю группы, прямой и инверсный выходы каждого - го триггера второй группы соединены с первыми входами i- x элементов И (и +1)-й

45 и (n+ 2 )- и групп, выход каждого уго элемента И (п+2)-й группы подключен к вторым входам (j-1)-х элементов И (n+ 1)-й и (и+2 )- и групп, выход первого элемента И (и+2 )-й группы соединен с вторыми входами первого и второго элементов И, выход каждого i- ro-элемента И (n+ 1)-й группы подключен к управляющим входам элементов И i-й группы узла обобще- 55 ния и через i-й элемент- задержки первой группы соединен с входом установки в нулевое состояние i- го триггера пер083 4 ,ВОЙ группы и с входом 1 го элемента задержки второй группы, выход каждого р-го элемента задержки второй группы (р=1,...,п -2 ) подключен к вторым управляющим входам элементов И второй группы, выход (n- 1)- го элемента задержки втррой группы соединен с вторыми управляющими входами и -входных элементов И группы, второй выход узла синхронизации подключен к вторым входам (n- 1)-х элементов И (и+ 1)-й и (n +2)- и группы, вход установки в единичное состояние р-го триггера второй группы соединен с соответствующим у м выходом первого дешифратора, инверсный выход. каждого р-го триггера второй группы подключен к третьим входам элементом И р-й группы.

На чертеже представлена схема устройства.

Устройство содержит и вхцдны;, регистров 1, регистр 2 числа А, регистр

3 числа В, счетчики 4 и 5, дешифраторы 6 и 7, группу первых входных элементов И 8, группу и- х,входных элементов И 9, первые группы у х входных элементов И 10 (j =2,...;n-1), вторые группы j-x входных элементов

И 11, группы g-x входных элементов ИЛИ 12, группы из m элементов

И 13 и 14 (m -разрядность числа), группу из (n -i)- го элемента ИЛИ 15, группу из (и - 1)- го триггера 16, группу из (n -2 )- ro элемента ИЛИ 15, группу из (n - 1)- ro триггера 16, группу из (и-2)-х триггеров 17, триггер

18, группы из (n -1)- го элемента И 19 и 20, узел 21 выделения, содержащий (n- 1)-ую группу элементов И 22 и группу элементов ИЛИ 23, узел 24 обобщения, содержащий (и- 1)-ye rpynпу элементов И 25 и группу элемен- . тов ИЛИ 26, схему 27 сравнения, группы элементов И 28 и 29 перезаписи информации, элементы И 30 и 31, элементы ИЛИ 32 и 33, элемент 34 задержки, группы из -(и -1)- го элемента 35 и 36 задержки, узел 37 синхронизации вход 38 тактовых импульсов.

Группы элементов И 8-11, 22, 25, 28 и 29 и группы элементов ИЛИ 12, 23 и 26 содержат по m соответствующих элементов.

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

В исходном состоянии в регистрах

1 записаны числа, которые необходимо

7 10010 упорядочивать. Счетчик 4 и триггеры

16-18 находятся в нулевом, а счетчик 5 " в единичном состояниях. Код числа А из первого регистра 1 поступает на первую группу входов схе- S мы 27 сравнения через первую группу элементов И 22 и группу элементов .

ИЛИ.23 узла 21 выделения за счет разрешающего потенциального сигнала с первого выхода дешифратора 7, определяющего единичное состояние счетчика 5, По стартовому импульсу (вход 38) узел 37 синхронизации вырабатывает сигнал "а", который через открытые элементы И 20 и 31 поступает на вход счетчика 4, устанавливая его в единичное состояние, и через элемент

ИЛИ 33, элемент 34 задержки (на время, необходимое для.срабатывания 2О . счетчика 4 и дешифратора 6) на,первые входы группы элементов И 13.

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

"а" открывает в-ые элементы И в группах элементов И 14, через которые значения m-ых (старших) разрядов 30 чисел из регистров 1 (с второго по и -ый) поступают через элементы

ИЛИ 15 на входы элемента ИЛИ 32 и одновременно на единичные входы соответстующих триггеров 16, устанавливая их в нулевое состояние в зави- симости от значения m- го разряда числа. Если хотя бы в одном из чисел, записанных в регистрах 1, в m- ou разряде — "1", то через элемент .

ИЛИ 32 поступает сигнал на единичный вход триггера 18, устанавливая его в единичное состояние.

Второй сигнал "а" от узла 37 синх45 ронизации через первый из открытых элементов И 19 .проходит на управляющие входы соответствующей .группы элементов И 25 и разрешает поступление числа В с соответствующего регистра 1 через элементы И 25 и ИЛИ 26 уз„Я1 ла 24 обобщения на вторую группу входов схемы 27 сравнения, т.е. на вторую группу входов схемы 27 сравнения поступит первое из чисел, начиная с п- го, в в-ом разряде которого "1".

Одновременно сигнал "а" с выхода элемента И 19, пройдя элемент 35 задержки (на время, необходимое для сравнения чисел А и 8 в схеме 27 и записи их в регистры 2 и 3), устанавливает в нулевое состояние соответствующий триггер 16 и далее через элемент задержки 36 (необходимый для временного совпадения импульса с выхода элемента 35 задержки и сигнала

"б" от узла 37..синхронизации) поступает на-управляющие входы соответствующих элементов И 9 или. 11.

После сравнения чисел А и В в схеме 27 возможны два варианта работы устройства: 1) если АсВ то на выходе схемы 27 сравнения появляется сигнал, поступающий на управляющие входы элементов 28 и 29 И перезаписи информации и разрешает запись чисел А и В через эти элементы в регистры 2 и 3 соответственно. Одновременно сигнал с выхода схемы 27 сравнения поступает на вход 37 перезапуска узла синхронизации, который вместо си гнала "а" выработает сигнал "б", разрешающий перепись числа В из регистра 3 в первый регистр 1, а числа А из регистра 2 в тот регистр 1, где было записано числа В. Следующим тактом узел 37 синхронизации вновь вырабатывает сигнал "а"; 2) если АЪ В, то на выходе схемы 27 сравнения сигнала нет и узел 37 синхронизации вырабатывает очередной сигнал "а". По каждому очередному сигналу "а" устройство работает аналогично с вторым сигналом "а".

После сравнения числа А со всеми числами В, в m"ûõ разрядах которых ."1"",,триггеры 16 будут в нулевом состоянии. Очередной сигнал "а" по-, ступает через элементы И 20 и 30 на нулевой вход триггера 18, вход счетчика 5 и через элемент ИЛИ 33, элемент 34 задержки на первые входы группы элементов И 13. Триггер 18 устанавливается в нулевое состояние.

Счетчик 5 переключается в состояние

2. На втором выходе дешифратора 7 появляется потенциальный сигнал, устанавливающий первый триггер 17 в единичное состояние, закрывая тем самым элементы..И 14 первой группы, и подключает второй регистр 1 (число А) через вторую группу элементов И 22 и и группу элементов ИЛИ 23 узла 2! выделения к первой группе входов схемы 27 сравнения. Пройдя через один из элементов И 13, на втором входе которого имеется потенциальный сиг9 10 нал с первого выхода дешмфратора 6, определяющий единичное состояние счетчика 4, сигнал "а" открывает пгые элементы И. в группах элементов И 14, через которые значения

m-ых разрядов чисел из регистров 1 (с третьего по и- ый) поступают через элементы ИЛИ 15 на. входы элемента ИЛИ 32 и одновременно на единичные входы соответствующих триггеров 16, устанавливая их в нулевое или единичное состояние в зависимости от значения m - -го разряда числа. Далее устройство работает аналогично описанному выше до полного .упорядочения чисел, в m-ых разрядах которых "1".

При поступлении" очередного сигнала "а" от узла 37 синхронизации после полнОго упорядочения чисел, в m-ых разрядах которых "!", на вяод"элемента ИЛИ 32 при перезаписи

m-ых разрядов чисел.из регистров 1 в соответствующие триггеры l6 сигналов не поступает -и триггер 18 оста ется в нулевом состоянии . Следовательно, следующий сигнал "а" от узла

37 синхронизации проходит через элементы И, 20 и 31, поступает в счетчик 4, устанавливая его в состояние

2, и через элемент ИЛИ 33, элемент

34 задержки на первые входы группы

1Щ(и в1)+И „(И,, )+.

- где n — коли чест во. чисел, в m-ых (старших) разрядах которых

I II1 1 111;

n-: количество .чисел; a(m-1}-ых разрядах которых "1", исключая числа группы nù, :и- количество чисел в i-ом раз1, t ряде которых ".1", исключая числа групп п„пр,,...,и и -количество .чисел, в первом разряде которых "1", исключая числа групп и>, п

М М ь ° ° ° в п ь и -общее количество упорядочиваемых чисел (n= и + и + ...+

- vn пм

+n„+ ...+п1);

in -количество групп, соответст вующее разрядности чисел.

В базовом же объекта для полного упорядочения чисел требуется Q тактов работы: и (n -1)Q = ----б 2

01083 10

20

Фи„-(и„ +4>+.. +и„(и„+1 ) . +n+e;

4S

$0

$$ элементов И 13. Пройдя через один из элементов И 13, на втором входе которого имеется потенциальный сигнал с второго выхода дешифратора 6, соответствующий состоянию 2 счетчика 4; сигнал "а" открывает (в- 1)=ые элементы И в группах элементов И 14, через которые значения (а-1)-ых разрядов чисел из регистров 1 с (q+1)- го по и -ый (q - значение счетчика 5) поступают через. элементы

ИЛИ 15 на входы элемента ИЛИ 32 и одновременно на единичные входы соответствующих триггеров 16,устанавливая их в нулевое или единичное состояние в зависимости от значения (m- 1)- го разряда . числа. Далее устройство работает аналогично описанному выше до полного упорядоче" ния чисел. Об окончании работы уст ройства сигнализирует переключение счетчика 4 в состояние О..

Технико-экономический эффею заключается в том, что предлагаемое устройство обладает большим быстродействием по сравнению с базовым .объектом..8 предлагаемом уст. ройстве. упорядочение,чисел осуществляется по группам и для полного

1 их упорядочения требуется Q тактов. работы:

Так, для Ы-разрядных чисел быстро-, действие предлагаемого устройства по сравнению с базовым объектом повышается в 3, 5-8 раз в зависимости от количества чисел. в группах.

Кроме этого, предлагаемое устройство адаптируемо к изменению количества упорядочиваемых чисел. В базовом объекте количество тактов ,(Ц ) не зависит от количества упорядочиваемых чисел и определяется их максимально возможным числом (П ), т.е. любое количество упорядочиваемых чисел (1, где 1 yn ) требует одинакового количества тактов работы.

В предлагаемом устройстве количество. тактов (Ц„) .определяется числом упоря.-дочиваемых чисел, чем меньше чисел, тем. меньше требуется тактов для их упорядочения, т.е. в формуле (1) n =g, Формула изобретения

Устройство для сортировки чисел, содержащее и входных регистров, региIl 10010 стры, узел выделения, узел обобщения, счетчики, .дешифраторы, схему сравнения; группы входных элементов

И, группы элементов И перезаписи информации, узел синхронизации, группы элементов И, ИЛИ, элементы ИЛИ, причем выходы первого счетчика,соединены с входами первого дешифратора, каждый i- и выход которого (i=1,...,п — 1) подключен к управляющим входам элемен40 тов И i-й группы узла выделения, первый выход первого дешифратора соединен с первыми управляющими вхддами первых входных элементов И групп, каждый j-й выход первого дешифратора (j =2 3,, и- 1) подключен к первым управляющим входам 1-х входных элементов И первой группы, выходы элементов

И каждой i-й группы узла выделения соединены со входами элементов ИЛИ 20 группы узла выделения, выходы которых подключены к первой группе схе-. мы сравнения. и к информационным вхо: дам элементов И первой группы перезаписи информации, выходы которых со- 2З единены с информационными входами первого регистра, выходы которого подключены .к информационным входам с второго по (n - l)-й входных элементов И второй группы и к информа- зо ционным входам и-х входных элементов И первой группы, выходы каждого

l -ro входного регистра (2 =2,...,и ) соединены соответственно с информационными входами элементов И (1- 1)-й

35 группы узла обобщения, выходы которых подключены к входам элементов

ИЛИ группы узла обобщения, выходы которых соединены. с второй группой входов схемы сравнения и с информа40 ционными входами элементов И второй группы перезаписи информации, выходы которых подключены к входам второго регистра, выходы которого соединены с информационными входами с второго по (и - 1)-й входных элемен45 тов И первой группы и с информа, ционными входами первых входных элементов И первой группы, выходы каждого i- ro входного регистра подключены к информационным входам элементов И 1- и группы узла выделения, выходы второго счетчика соединены с входами второго дешифратора, выход схемы сравнения подключен к управляющим входам элементов И первой и второй групп перезаписи информации и к входу перезапуска узла синхронизации, первый выход которого соеди83 12 нен с вторыми управляющими входами с второго по (n-1)-й входных элементов И первой и второй групп, вторыми управляющими входами первых входных элементов И группы и с первыми управляющими входами и- х входных элементов И группы, выходы первых и и -х входных элементов И группы соединены с входами первого и и --го входных регистров соответственно, выходы j --х входных элементов И первой и второй групп подключены к входам

j-x входных элементов ИЛИ группы, выходы которых соединены с входами

j--го входного регистра соответственно о тл и ч а ющ.е.е.с я тем, что, с целью повышения быстродействия, в него введены элементы И, ИЛИ, триггеры, элементы задержки, выход каждого К-по разряда каждого 0- го входного регистра (К=l,...,m, m— количество разрядов сравниваемых чисел) соединен с первым входом К- го элемента И (1- 1)-й группы, выходы элементов И каждой i- и группы подключены к входам i-ro weve x ИЛИ группы, выход каждого i-го элемента ИЛИ группы соединен с i-м входом первого элемента ИЛИ и с входом установки в единичное состояние i- го триггера первой группы, выход первого элемента ИЛИ подключен к входу установки в единичное состояние триггера, прямой и инверсный выходы которого соединены с первыми входами первого и второго элементов И соответственно, выход первого элемента И подключен к входу первого счетчика, к входу установки в нулевое состояние триггера и к первому входу второго элемента ИЛИ, выход которого через элемент задержки соединен с первымц входами элементов И n --й "группы, вы-. ход второго элемента И подключен к второму входу второго элемента ИЛИ и к входу второго счетчика, каждый

К-й выход второго дешифратора соединен с вторым входом К-ro элемента ,И n --й " группы,,выход каждого К-го элемента И n --й "группы подключен к вторым входам К-х элементов И с первой по (n+1)-ю группы, прямой и инверсный выходы каждого l l o триггера второй группы соединены с первыми входами i-х элементов И (p +1)-й и (n +2)- и групп, выход каждого j-го элемента И (р +2)- и группы подключен к вторым входам (у- 1)-х элементов

И (n +1)-й и (n +2)- и групп, выход

13 1001083 14 первого элемента И п+2)-й группы группы, второй выход узла синхронисоединен с вторыми входами. первого и зации подключен к вторым входам второго элементов И, выход каждого, Ip-l)-x элементов И (p+1)-й и (+2)-й

i- го элемента и (п + 1)-й группы групп, вход установки в единичное

- подключен к управляющим входам эле- у состояние р-ro триггера второй групментов И i-й группы узла обобщения и пы соединен с соответствующим 1-м через i- и элемент задержки первой . выходом первого дешифратора, инвергруппы соединен с входом установки сный выход каждого р-ro триггера в нулевое состояние 1-.го триггера второй группы подключен к третьим вхо; первой группы и с входом i-го эле- М дам элементов И р-й. группы. мента задержки второй группы, выход каждого р-ro элемента задержки Источники. инФормации, второй группы (р=1,..., n-2) под- принятые во внимание при экспертизе ключен к вторым управляЮщим входам 1. Авторское свидетельство СССР элементов И второй группы, выход 1s 11 478303, кл. G 06 F 7/04, 1975.

Ь - 1)- ro элемента задержки второй 2. Авторское свидетельство СССР группы соединен с вторыми управляю- Ф 826339, кл. 6 06 F 7/06:, 1979 (прощими входами и-входных элементов И тотип).

1001083

ВНИИПИ Заказ 1396/55 Тираж ?04 . Подписное филиал ППП "Патент, г. Ужгород, ул. Проектная, 4