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

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

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву(22) Заявлено 250480 (21) 2916946/18-24 (3Ц М. Кп.з

G 06 F 7/06 с присоединением заявки ¹(23) Приоритет—

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

СССР но делам изобретений и открытий (ЯЯ) УДК 681. 325. .5 (088.8) Опубликовано 150582, Бюллетень ¹ 18

Дата опубликования описания 150182 (72) Авторы изобретения

Э.П. Чернаков и Б.С. Богумирский

Военный инженерный Краснознаменный институт им. А.Ф. Можайского (71) Заявитель (54 ) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ

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

Известно устройство для сортировки mn-разрядных чисел, содержащее

m регистров, выходы каждого из Которых соединены со входами схем сравнения, другие входы которых подКлючены .к выходам регистра результата, выходы схем сравнения соединены через переключатели со входами элемента ИЛИ, клапаны и триггер, узлы запрета (1) .

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

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

Для достижения цели в устройстве для сортировкИ чисел, содержащем регистры, схемы сравнения, элементы

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

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

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

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

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

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

11 1т ...,1, схемы сравнения

2 2,...,2, регистр результата 3, распределитель импульсов 4, элементы.запрета 5i,5p,...,5q элементы И

6i,6,...,6q, элемент И 7, вход записи устройства 8, вход тактовых сигналов 9, входы управления устройства 10 и 11, вход опроса устрайства 12, вход записи результатов 13.

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

В регистры 1 заносятся числа, подлежащие сортировке, регистр результата 3 устанавливается в нулевое состояние, а временной-распределитель 4 — в исходное состояние (цепи занесения информации в регистры 1, установки в нулевое состояние регистра результата 8, а также установки в исходное состояние распреде- 35 лителя 4 (не показаны). На вход управления устройства 11 подается сигнал переводящий все элементы запрета 5 в такое состряние, что элементы б оказываются открытыми. 40

После проведения этих операций устройство готово к работе. На вход тактовых сигналов устройства 9 пода- ется первый тактовый сигнал, по которому на первом выходе распреде- 45 лителя 4 появляется сигнал. Он проходит на управляющий вход старшего разряда регистра результата 3, разрешая запись в него информации. Затем на вход записи устройства 8 подается сигнал, по которому в старший разряд регистра результата 3 заносится единица. После этого сигнал подается на вход опроса устройства

12. Он проходит на управляющие входы схем сравнения 2 через открытые элементы б. Схемы сравнения 2 осуществляют сравнение чисел, находящихся в соответствующих регистрах 1, с числом, находящимся в регистре результата 3. Если число в каком-либо регистре 1 меньше числа, находящегося в регистре результата 3, то на выходе меньше соответствующей схемы сравнения 2 появляется сигнал„ если числа равны, то сигнал появля- . 65 ется на выходе равно. . Сигналы, появляющиеся на выходах равно схем сравнения 2,не оказывают воздействие на элементы запрета 5, так как сигнал на запрещающие входы не

:подан. Затем подается сигнал на вход устройства 13. Если на выходах меньше всех схем сравнения 2 при. сутствует сигнал, то он появляется на выходе элемента И 7 и проходит на нулевой вход старшего разряда регистра 3. Таким образом, если, все сортируемые числа меньше числа, записанного в регистре результата.,то в его старший разряд записывается нуль. После этого на вход устройства 9 подается второй тактовый сигнал и устройство работает так же,.как в первом такте. К концу в.торого такта работы устройства во втором разряде регистра результата записывается нуль, если все сортируемые числа меньше числа, сформированнрго в начале второго такта, в противном случае — единица. После окончания п тактов в регистре результата 3 сформируется максимальное из хранящихся в регистрах 1 чисел. В (и+1) такте распределитель 4 по сигналу на входе тактовых сигналов устройства 9 переводится в исходное состояние, при котором сигналы на его выходах отсутствуют. На вход устройства 10 по"дается сигнал, который проходит на управляющйе входы узлов запрета 5, Затем подается сигнал на вход опроса устройства 12, который поступает

Ыа управляющие входы всех схем срав нения 2, но появляется на выходах равно только тех схем сравнения

3, где в принадлежащих им регистрах

1 записаны числа, равные числу, сформированному в регистре результата 3. Соответствующие этим схемам сравнения элементы запрета 5 переводятся в такое состояние, что соединенные с ним клапаны закрываются.

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

После этого содержимое регистра ре.зультата 3 выбирается и он переводится в нулевое состояние.

Затем на вход тактовых сигналов устройс тв а 9 подаетс я очередной так товый сигнаЛ и устройство начинает формировать максимальное число из оставшихся ° Работа устройства циклически повторяется до тех пор, пока .не отсортируются все числа, находя åñR в регистрах 1, в порядке их убывания. Для сортировки чисел в порядке их возрастания необходимо

s регистры 1 записать инверсные коды сортируемых чисел и инвертировать. коды, считываемые с регистра результата 3..

928342

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

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

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

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

ВНИИПИ Заказ 3241/61 .Тираж 732 Подписное

Филиал ППП "Патент"

r, Ужгород, ул. Проектная, 4 управления установкой разрядов регистра результата, выходы которых соединены со входом второй группы схем сравнения, первый и второй входы управления устройства подключены к первым и вторым информационным входам соответственно элементов запрета, вход записи устройства соединен со входами установки в единичное состояние разрядов регистра результата, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, в нем второй выход каждой i-ой схемы сравнения соединен с i-ым входом (i+1) -го элемента И, выход которого подключен ко входам установки в нулевое состояние разрядов регистра результата, вход записи результата устройства соединен с (i+1)-ым входом (i+I)-ro элемента И.

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

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

9 263277, кл. G 06 F 7/00, 1956.

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

9 687810, кл. G 06 F 7/08, 1976 (прототип).