Устройство для сортировки чисел Советский патент 1982 года по МПК G06F7/06 

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

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

Недостаток этого устройства низкое быстродействие.

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

Недостатками этого устройства являются значительные аппаратурные затраты. .

Цель изобретения - упрощение устройств..

Для достижения цели в устройстве для сортировки чисел, содержащем регистрал, схемы сравнения, элементы И, элементы запрета, регистр резуль10тата, распределитель импульсов, причем выходы каждого i-ro регистра, где i - 1,2,...,п, соединены со входами первой группы входов 1-ой схемы сравнения, первыйвыход кото15рой соединен со входом управления i-ro элемента запрета, выход каждого из которых подключен к первому входу i-ro элемента И, выход которого соединен со входом управления

20 i-ой схемы сравнения, вход опроса устройства подк.пючён ко вторым вхо.,дам элементов И, вход тактовых .сиг;лалов устройства соединен со входом распределителя импульсов, выхо.ды

25 которого подк.пючены ко входам управления установкой разрядов регистра результата, выхо.С1ы которых соединены со входом второй группы схем сравнения, первый и второй входы управления устройства подключены к первым и вторым информационным входам соответственно элементов запрета, вхо записи устройства соединен со входами установки в единичное состояние разрядов регистра результата, второй выход каждой i-ой схемы срав нения соединен с 1-ым входом (1+1)элемента И, выход которого подключен ко входам .установки в нулевое состояние разрядов регистра результата, вход записи результата ус.троД ства соединен с ( входом (i+1)-го элемента И. На чертеже приведена функциональ ная схема предлагаемого устройства. Устройство содержит регистры li,l2./...rlnf схемы сравнения 2,,,.,2r,, регистр результата 3, распределитель импульсов 4, элементы запрета 5i ,5г, .,.,5h элементы И б,б2,.../бп элемент И 7, вход записи устройства 8, вход тактовых сигналов 9, входы управления устрой ства 10 и 11, вход опроса устройства 12, вход записи результатов 13. Устройство работает следующим образом. В регистры 1 заносятся числа, подлежащие сортировке, регистр результата 3 устанавливается в нулево состояние, а временной распределитель 4 - в исходное состояние (цепи занесения информации в регистры 1, установки в нулевое состояние регистра результата 8, а также установки в исходное состояние распреде лителя 4 (не показаны) . на вход управления устройства 11 подается сигнал переводящий все элементы запрета 5 в такое состояние, что элементы 6 оказываются открытыми. После проведения этих операций устройство готово к работе. На вход тактовых сигналов устройства 9 пода ется первый тактовый сигнал, по которому на первом выходе распределителя 4 появляется сигнал. Он проходит на управляющий «вход старшего разрядарегистра результата 3, разрешая запись в него информации. Затем на вход записи устройства 8 подается сигнал, по которому в старши разряд регистра результата 3 заносится единица. После этого сигнал подается на вход опроса устройства 12. Онпроходит на управляющие вход схем сравнения 2 через открытые эле менты 6. Схемы сравнения 2 осуществляют сравнение чисел, находящихся в соответствующих регистрах 1, с числом, находящимся в регистре результата 3. Если число в каком-либо регистре 1 меньше числа, находящегося в регистре результата 3, то на выходе меньше соответствующей схемы сравнения 2 появляется сигнал если числа равны, то сигнеш появляется на выходе равно. Сигналы, появляющиеся на выходах равно схем сравнения 2, не оказывают воздействие на элементы запрета 5, так как сигнал на запрещгиощие входы не подан. Затем подается сигнал на вход устройства 13. Если на выходах меньше всех схем сравнения 2 присутствует сигнал, то он появляется на выходе элемента И 7 и проводит на нулевой вход старшего разряда регистра 3. Таким образом, если, все сортируемые числа меньше числа, записанного в регистре результата,то в его старший разряд записывается нуль. После этого на вход устройства 9 подается второй тактовый сигнал и устройство работает так же, как в первом такте. К концу в.торого такта работы устройства во втором разряде регистра результата записывается нуль, если все сортируемые числа меньше числа, сф.ормированнрго в начале второго такта, в противном случае - единица. После окончания п тактов в регистре результата 3 сформируется максимальное из хранящихся в регистрах 1 чисел. В (п+1) такте распределитель 4 по сигналу на входе тактовых сигналов устройства 9 переводится в исходное состояние, при котором сигналы на его выходах отсутствуют. На вход устройства 10 по-дается сигнал, которий проходит на управляющие входы узлов запрета 5, затем подается сигнал на вход опроса устройства 12, который поступает ца управляющие входы всех схем срав нения 2, но появляется на выходах равно только тех схем сравнения 3, где в принадлежащих им регистрах 1 записаны числа, равные числу, сформированному в регистре результата 3. Соответствующие этим схемам сравнения элементы запрета 5 переводятся в такое состояние, что соединенные с ним клапаны закрываются. Таким образом регистры 1, в которых записано максимальное число, в дальнейшей работе участия не принимают. После этого содержимое регистра ре-зультата 3 выбирается и он переводится в нулевое состояние. Затем на вход тактовых сигналов устройства 9 подается очередной так товый сигнал и устройство начинает формировать максимальное число из оставшихся. Работа устройства циклически повторяется до тех пор, пока не-отсортир потся все числа, находяi ecя в регистрах 1, в порядке их убывания. Для сортировки чисел в порядке их возрастания необходимо в регистры 1 записать инверсные коды сортируемых чисел и инвертировать коды, считываемые с регистра результата 3.

Использование предлагаемого устройства позволяет сократить аппаратурные затраты на один триггер и элемент И.

Формула изобретения

Устройство для сортировки чисел, содержащее регистры, схемы сравнения, элементы И, элементы запрета, регистр результата, распределитель импул ьс ов, причем выходы к аждого i-го регистра где i - 1,2,...,п соединены со входами первой группы входов 1-ой .схемы сравнения, первый выход которой соединен со входом управления i-ro элемента запрета, выход каждого из которых подключен к первому входу i-ro элемента И, выход которого соединен со входом управления 1-ой схемы сравнения, вход опроса устройства подключен ко вторым входам элементов И, вход тактовых. сигна пов устройства соединен со входом распределителя импульсов, выходы которого подключены ко Ьхода

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

0 что, с целью упрощения устройства, в нем второй выход каждой 1-ой схемы сравнения соединен с 1-ым входом (i+l)-ro элемента И, выход которого подключен ко входам установки в ну15левое состояние разрядов регистра ° результата, вход записи результата устройства соединен с (1+1)-ым входом (i+l)-ro элемента И.

Источники информации,

0 принятые во внимание при экспертизе

1.Авторское свидетельство СССР № 263277, кл. G 06 F 7/00, 1956.

2.Авторское свидетельство СССР 687810, кл. G 06 F 7/08, (прототип).

25