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

 

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

СОЦИАЯИСТИЧЕСНИХ

РЕСПУБЛИН (19) (И)

1 11 G 06 F 7/06 (21) 3767701/24-24 (22) 13.07,84 (46) 15.02.86. Бюл„ ¹ 6 (72) В.Г.Попов (53) 681.325(088.8) (56) Авторское свидетельство СССР

¹ 928342, кл. G 06 Р 7/06, 1980.

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

¹ .1092494, кл. С 06 F 7/06, 1982. (54)(57) УСТРОЙСТВ() ДЛЯ СОРТИРОВКИ

ЧИСЕЛ, содержащее и регистров, и элементов И, где И число сортируемих чисел, и схем сравнения, (n-1) элементов запрета, регистр результата, две группы выходных элементов И, сумматор, первая группа входов которого соединена с входами задания начального адреса устройства, а выходы соединены с информационными входами выходных элементов И первой группы, выходы которых являются выходами адреса устройства, выходы регистра результата соединены с информационными входами выходных элементов И второй группы, выходы которых являются выходами отсортированного числа устройства, управляющие входы выходных элементов И первой и второй групп подключены к тактовому входу устройства, входы сортируемых чисел. устройства соединены с информационными входами соответствующих регистров, выходы которых соединены с первыми группами входов соответствующих схем сравнения, 1 .-е инверсные входы эле-: ментов запрета с 6 -го по (и-1)-й объединены { I =1,2,...,п-1), о т— л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены (tn- n) элементов запрета, и дешифраторов, tn элементов

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

-ro дешифратора, где =1,2,..., в ) =1,2,...,п, соединены с ) -м входом i --ro элемента ИЛИ, выход первого элемента ИЛИ соединен с первым входом шифратора и первыми инверсными входами элементов запрета, выход k --ro элемента ИЛИ, где

k =2,3,...,rn подключен к прямому входу (k-1)-ro элемента запрета и к 1 -му инверсному входу k --ro элемента запрета, выход р -ro элемента запрета, где р =1, 2,..., (ю-1), соединен с (p+1)-м входом шифратора, тактовый вход устройства через элемент задержки подключен к вторым входам всех элементов И.

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

Цель изобретения — повышение быстродействия.

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

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

1, и дешифраторов 2, m элементов

ИЛИ 3, (m-1) элементов запрета 4, шифратор 5, схем 6 сравнения, элементов И 7, регистр 8 резуль тата; сумматор 9, элемент 10 задержки, элемент И-HE 11, группы выходных элементов И 12 и 13, входы

14 сортируемых чисел устройства, входы 15 задания начального адреса устройства, выход 16 конца сортировки, выходы 17 отсортированного числа, тактовый вход 18 и выход 19 адреса устройства. Рассмотрим принципы построения н работу устройства.

Исходное состояние устройства характеризуется тем, что в .регист" ры 1 по входам 14 принимается массив исходных чисел, а в сумматор 9код адреса памяти, начиная с которого необходимо разместить отсортированный массив чисел.

Исходные числа преобразуются де.;чфраторами 2, выходные сигналы с одноименных выходов которых объединяются соответствующими элементами ИЛИ 3.

Пусть массив чисел имеет следующий вид: а, =4, ц =5, а =3, а =4, При этих чсходных данных работа дешифраторов 2 и элементов ИЛИ 3 поясняется таблицей 1.

Из таблицы видно, что номер выходов дешифраторов, а следовательно и номер элемента ИЛИ 3 одн6значно соответствуют значению числа, а выходные единичные сигналы элементов

ИЛИ 3 размещены в порядке возраста° ния значения чисел. Кроме того, при равных двоичных кодах в массиве чисел (а,,= а =100," а = с =101) единичные сигналы формируются. соответствующими элементами ИЛИ 34 и

3, Таким образом, упорядоченный

"массив должен иметь вид: Ъ, =1, 6 =3,1 4, Ь =5, причем эти числа необходимо разместить в выделенной

После установки в "0" регистра

1 на выходах элементов ИЛИ 3 формируется очередной позиционный код 00111, а на входе шифратора 5— код 00100-. При этом в регистр 8 результата принимается двоичный код 011, а в схеме б сравнения формируется единичный сигнал. По очередному тактовому импульсу с входа 18 значения числа 011 и код адреса А поступают в 3ВМ, а в устройстве регистр 1 устанавливается в "0" и в сумматоре 9 формируется очередной адрес А =А +i. При этом на выходах элементов ИЛИ 3 формируется позиционный код 00010, а на выходе шифратора 5 — двоичный код 100. В схемах 6, и 6 сравнения происходит совпадение кодов, 11718 2 области памятч, код начального адреса которого Ащ„ принят в сумматор 9.

Позиционный код выходных сигна5 лов элементов ИЛИ 3 10111 подается на элементы запрета 4, включенные по приоритетной схеме. Так, единичный сигнал с выхода элемента

ИЛИ 3,закрывает по инверсным входам ,все последующие элементы 4,-4 запрета. При этом на входе шифратора 5 формируется позиционный код

10000. Шифратором 5 этот код преобразуется в двоичный 001, принимаемый в регистр 8 результата. Кроме того, в схеме 6 сравнения происходит совпадение кодов, единичный. сигнал с выхода которой поступает на первый вход элемента И 7.. На выходе элемента И-HE 11 единичный сигнал отсутствует, поэтому из ЭВМ по входу 18 поступает тактовый импульс. По этому импульсу адрес

A A„ „èç сумматора 9 через группу элементов И 13 поступает на выходы 19, а двоичный код первого числа из регистра 8 результата через группу элементов И 12 выдается

30 на выходы 17. Через некоторое время, определяемое задержкой в элементе 10. задержки, в сумматоре 9 формируется очередной адрес А А „+1 и устанавливается s "0" регистр чем исключается из анализа число ot .

Бремя задержки выбирается исходя из необходимого времени приема в

ЭВМ адреса и значения чисел с выходов 17 и 19.

По очередному импульсу по входу

18 значение числа 100 и код адреса

A поступают в 3ВМ, регистры 11 и 1 устанавливаются в "0", а в сумматоре 9 формируется адрес очередного числа А =А +1. По следующему тактовому импульсу происходит запись числа 101 по адресу А+, а в устройстве — установка в "0" регистров

Номер выходов девврраеора 2,,...,2 (Двоичный код числа

2 3 4

0

Позиционный код элемента ИЛИ 3

a f mm100 а,=101

g,011 а„-100

a,=-=001 о =101

0 0

0 0

0 0

0 0

0 0

1211718. 4

1 и 1 . При этом все регистры 1 оказываются в нулевом состоянии, и

I на выходе элемента И-HE 11 Формируется единичный сигнал, поступающий в ЭВИ в качестве сигнала конца сортировки °

Таким образом, массив из жести чисел отсортирован на четыре тактовых сигнала.

1211718

Составитель E.Èâàíîâà

Редактор Н.Швыдкая Техред А.Бабинец Корректор Л.Патай

Заказ 640/52 . Тираж 673 . Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и откритий

113035, Москва, Ж-35, Раушская наб.,д, 4/5

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