Устройство для упорядочения массива чисел

 

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

СО1.1ИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

„„SU„„1425652 А1 (51)4 G Об Р 7 06

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4063507/24-24 (22) 30,04,86. (46) 23,09.88. Вюл. 9 35 (72) li.È.Êðüëîâ, В.N,Ëîëèùóêu Н.Н.Шубина (53) 681.325.5 (088. 8) (56) Авторское свидетельство СССР

Р 981988, кл. G 06 F 7/06, 1980.

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

У 1234827, кл. G 06 Р 7/06, 1984. (54) УСТРОЙСТВО ДЛЯ УПОРЯДОЧЕНИЯ

МАССИВА ЧИСЕЛ (57) Изобретение может быть использовано s .области вычислительной техники. Цель изобретения — повышение быстродействия устройства. Устройство содержит регистры I-5, счетчики

6,7, схемы сравнения 8-10, триггеры

11-14, элемент запрета 15, группы элементов И переписи 16-20, группы выходных элементов И 21-25, группы элементов ИЛИ 26,27, элементы И 2838, элементы ИЛИ 39-42, формирователь импульсов 43, элементы задержки

44-48. Устройство выполняет упорядочение чисел, начиная с адреса начала зоны, записанного в регистре 1. Для сортировки массива из N чисел размещение чисел в заданной зоне предлагаемым устройством осуществляется толь.ко в конце каждого цикла сравнения.

1 ил.

1425652

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

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

Устройство содержит регистры 1 - 5, счетчики 6 и 7, схемы 8-10 сравнения, триггеры 11-14, элемент 15 запрета, группы 16-20 элементов И переписи, ! группы 21-25 выходных элементов И, группы элементов ИЛИ 26 и 27, элементы И 28-38, элементы ИЛИ 39-42, фор". иронатель 43 импульсов, элементы

4-48 задержки, информационные вхоы 49, вход 50 запуска, вход 51 таконых импульсов, информационные выхсы 52, выход 53 окончания работы, 20

ыходы 54 разрешения считывания, 1 аписи 55, адресные выходы 56.

В качестве формирователя 43 имульсов может использоваться известая. схема мультинибратора, которая

1тозволяет сформировать управляющий игнал при каждом изменении состояния хемы сравнения.

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

В исходном состоянии в регистре 1 аписан адрес начала зоны, а-в регистре 2 — адрес конца эоны массива чисел, записанного в запоминающем устройстве (ЗУ) общегО назначения, который требуется упорядочить, В рео гистрах 3 и 4 записано минимальное машинное число, счетчики 6 и 7, триггеры 11-14 находятся в нулевом самостоянии. Так как содержимое реги- 40 отров 3 и 4 равно, то на первом выХоде схемы 10 сравнения имеется едиНичный сигнал, который подтверждает установку триггера 11 в нулевое состояние, и, следовательно, открыты 45 элементы И группы 19. При поступлении сигнала запуска на вход 50 содержимое регистра 1 переписывается через элементы И группы 18 н счетчик 6, а затем через время задержки, опредее ляемое элементом 44 задержки, переписывается через элементы И группы 16 в счетчик 7. Содержимое счетчиков 6 и 7 сравнивается схемами 8 и 9 с содержимым регистра 2. Так как содержимое счетчиков 6 и 7 меньше, то на выходах схем 8 и 9 сравнения имеется нулевой сигнал и, следовательно, элемент 15 запрета открыт. Тактовый им" пульс с входа 51 через открытые элементы 15 запрета и И 29 поступает на выход 54 разрешения считывания (из

ЗУ) и через элемент И 30 на входы элементов И группы 23, в, результате чего на выходах 56 устройства сформирован адрес первого числа через элементы И группы 23 и элементы ИЛИ группы 27 и из ЗУ считано первое число, которое поступает, на входы 49 устройства и далее через элементы И группы 19 в регистр 3.

Схема 10 сравнения и триггер 11 меняют свое состояние, так как содержимое регистра 3 больше, чем содержимое регистра 4, а формирователь о

43 вырабатывает импульс, по которому из счетчика 7 через элементы И группы

i7 в регистр 5 записывается адрес первого числа. Затем .этим же такто" вым импульсом, задержанным на элементе 45 задержки на время переходных процессов, содержимое счетчика 7 оувеличивается на единицу. При поступлении нторого тактового импульса на вход 51 из ЗУ считывается второе число по адресу счетчика 7, описанным вьппе способом. Поступающее на входы

49 второе число записывается н регистр 4 через открытые элементы И групп 20, так как триггер 11 находится в единичном состоянии ° Если поступившее второе число, записанное в регистре 4, больше или равно первому числу, записанному в регистре

3, то схема 10 сравнения и триггер меняют свое состояние, подготавливая запись очередного числа в регистр 3, а формирователь 43 вырабатывает импульс, по которому адрес нторого {очередного) числа записывается в ре.чстр 5. При поступлении очередного тактового импульса очередное число считывается из ЗУ и записывается в тот из регистров 3 или 4, где записано меньшее число. Если при этом соотношение чисел, записанных в регистрах 3 и 4, меняется, то формирователь 43 вырабатывает сигнал, по которому в регистр 5 через элементы И группы 17 записывается содержимое счетчика 7. Таким образом, в одном из регистров 3 или 4 записано максимальное число, а в регистре 5 — его адрес ° Работа устройства продолжается аналогично до тех пор,, пока содержимое счетчика 7 не превышает значение адреса конца зоны, записанного в регистре 2. Как только н счетчике

1425652

7 будет значение, превышающее значение адреса конца зоны, схема 9 сравнения вырабатывает сигнал, который устанавливает триггер 12 в единичное состояние, и очередной тактовый импульс поступает на выход 54 и через элементы И 31 и ИЛИ 40 на входы элементов И группы 24, в результате че- . го по первому адресу считывается первое число в один из регистров 3 или 4. Таким образом, в одном из регистров 3 или 4 записано максимальное, а в другом — первое число. 3атем этим же тактовым импульсом, за" держанным в элементе 46 задержки на время переходных процессов триггер

13 устанавливается в единичное состояние.

При поступлении очередного тактового импульса максимальное число из регистра 3 или 4 соответственно через элементы И группы 21 или И группы 22 записывается в ЗУ по адресу счетчика

6, а при поступлении следующего тактового импульса первое число иэ регистра 4 или 3 соответственно через элементы И группы 22 или И группы 21 записывается в ЗУ по адресу максимального числа следующим образом.

Очередной тактовый импульс, пройдя открытые элементы И 32, И 33, И 35 или И 36, ИЛИ 41 или ИЛИ 42, открывает элементы И группы 21 или И группы 22 в зависимости от состояния триггера 11, который находится в единичном состоянии, если в регистре 3 записано большее,чем в регистре 4, число, и в нулевом — в противном случае, и максимальное число из регистра

3 или 4 через элементы И группы 21 или И группы 22 и элементы ИЛИ группы 26 поступает на выход 52 устройства.- Этим же тактовым импульсом открываются элементы И группы 24 и по адресу, находящемуся в счетчике 6, в

ЗУ записывается максимальное число.

Этот же импульс, задержанный элементом 47 задержки на время переходных процессов, устанавливает триггер 14 в единичное состояние. Следующий тактовый импульс, пройдя элементы И 32, И 34, И 38 или И 37, HJIH 42 или .4ЛИ

41, открывает элементы И группы 22 или И группы 21, и меньшее число, которое ранее записано в регистре 4 или 3 через элементы И группы 22 или

И группы 21 и элементы ИЛИ,группы 26, поступает на выход 52 устройства. По этому же тактовому импульсу на выходы

56 через элементы И группы 25 и ИЛИ группы 27 поступает адрес, по которому в ЗУ записано максимальное число, 5 и число из регистра 4 или 3 записывается по этому адресу, Этот же импульс, задержанный в элементе 48 задержки на время переходных процессов, устанавливает счетчик 6 в очередное состояние, а регистры 3 — 5, триггеры 12 — 14 — в исходное (нулевое) состояние, а далее по этому же импульсу, задержанному в элементе 44 задержки на время переходных процессов,содержимое счетчика 6 через элементы И группы 16 переписывается в счетчик 7.

Работа устройства продолжается описанным вьппе способом до тех пор, пока содержимое счетчика 6 не станет равным содержимому регистра 2. Как только они сравняются, схема 8 сравнения вырабатывает сигнал, который закрывает элемент 15 запрета и поступает на выход 53, сигнализируя об окончании сортировки.

П р и M е р. Пусть в ЗУ записан массив чисел, который необходимо

30 упорядочит|:

Адрес 1 2 3 4 5

Число 13 11 12 14 15

Из ЗУ в устройство последовательно считываются числа из упорядочиваемого

35 массива и устройство работает следующим образом, Первый цикл сравнения:

1-й такт — считывается (в регистр

3) первое число (13) и запоминается

40 (в регистре 5) его адрес (1), 2-й такт — считывается (в регистр

4) второе число (»), сравнивается (в схеме 10 сравнения) с первым числом (13) и запоминается максимальное из двух чисел (13 в регистре 3) и его адрес (1 в регистре 5), 3-й такт — считывается (в регистр 4) третье число (12), сравнивается (в схеме 10 сравнения) с максимальным

50 из двух чисел (13 в регистре 3) и запоминаеч ся максимальное иэ трех чисел (13 в регистре 3) и его адрес (1 в регистре 5), 4-й такт — считывается (в регистр

55 4) четвертое число (14), сравнивается (в схеме сравнения 10) с максимальным из трех чисел (13 в регистре 3) ц- запоминается максимальное из

1425652 четырех чисел (14 в регистре 4) и

;его адрес (4 в регистре 5), 5-й такт — считывается (в регистр

3) пятое число (15), сравнивается (в схеме 10 сравнения) с максималь ным из четырех чисел (14 в регистре

4) и запоминается максимальное из пяти чисел (15 в регистре 3) и его адрес (5 в регистре 5), 6-8"й такты — после сравнения всех чисел массива происходит перезапись в ЗУ: по адресу максимального числа (5) записывается первое число (13), а по адресу первого числа (1), аксимальное число (15), т.е. после

1 !

if-ro цикла сравнения в ЗУ имеется следующая последовательность чисел:

Адрес 1 2 3 4 5

Число 15 11 !2 14 13 торой цикл сравнения:

1-й такт — считывается (в регистр

) второе число (») и запоминается в регистре 5) его адрес (2), 2-й такт — считывается (в регистр

) третье число (12), сравнивается в схеме 10 сравнения) с вторым чис,ом (11) и запоминается максимальное з двух чисел (12 в регистре 4) и его дрес (3 в регистре 5), 3-й такт — считывается (в регистр

) четвертое число (14), сравнивается в схеме 10 сравнения) с максимальным из двух чисел (12 в регистре 4) и запоминается максимальное иэ трех чисел (14 в регистре 3) и его адрес (4 в регистре 5), 4-й такт — считывается (в регистр

4) пятое число (13), сравнивается (в схеме 10 сравнения) с максимальным из трех чисел (14 в регистре 3) и за- 40 поминается максимальное из четырех чисел (14 в регистре 3) и его адрес (4 в регистре 5), 5-7-й такт — после сравнения всех чисел массива происходит перезапись 45 чисел в ЗУ: по адресу максимального числа (4) записывается второе число (11), а по адресу второго числа (2) максимальное число (14), т.е. после второго цикла сравнения в ЗУ имеется 50 следующая последовательность чисел:

Адрес 1 2 3 4 5

Число 15 *14 12 11 13

20 далее аналогично выполняются тре тий и четвертый циклы сравнения, сравнение в которых начинается соот» в тственно с третьего и четвертого чИсел . После третьего цикла сравне6 ния (6 тактов) в ЗУ имеется следующая последовательность чисел:

Адрес 1 .2 3 4 5

Число 15 14 13 11 12

После четвертого цикла сравнения (пять тактов) в ЗУ имеется упорядоченный (в порядке убывания) массив чисел:

Адрес 1 2 3 4 5

Число 15 14 13 12 11

Таким образом, на упорядочение данного массива чисел в.предлагаемом устройстве требуется 26 тактов, а перезапись чисел в ЗУ осуществляется эа три такта работы устройства.

Для упорядочения данного массива чисел в известном устройстве требуется 30 тактов, а перезапись чисел в

ЗУ осуществляется за два такта работы устройства, так как известное устройство работает по следующему алгоритму:

Первый цикл сравнения:

1-й такт — из 3У считывается первое число (13), 2-й такт — из ЗУ считывается второе число (11), так как оно меньше первого (13), то перезапись чисел в

ЗУ не происходит, 3- и такт — из ЗУ считывается третье число (12), так как оно меньше первого (13), то перезапись чисел в ЗУ не происходит, 4-й такт — из ЗУ считывается четвертое число (14), так как оно больше первого числа (13), то происходит перезапись чисел в ЗУ;

5 и 6-й такты — в ЗУ на место первого числа (13) записывается четвертое число (!4), а на место четвертого числа (14) — первое число (13), большее число (14) запоминается в устройстве и последующие числа теперь сравниваются с этим чисЪом, 7-й такт — из ЗУ считывается пятое число (15), так как оно больше первого. числа (14), то происходит перезапись в ЗУ, 8 и 9-й такты — в ЗУ на место первого числа (14) записывается пятое число (15), а на место пятого числа (15) — первое число (14) .

Таким образом, после сравнения всех чисел массива (первого цикла сравнения) в ЗУ записана следующая последовательность чисел:

Адрес 1 2 3 4 5

Число !5 11 12 13 14

1425652

7

Второй цикл сравнения:

1-й такт — из ЗУ считывается второе число (11) и сравнение выполняется аналогично описанному 1-му циклу сравнения.

После второго цикла сравнения (десять тактов) в ЗУ имеется следующая последовательность чисел:

Адрес 1 2 3 4 5

Число 15 14 11 12 13

Далее аналогично выполняются третий и четвертый циклы сравнения, сравнение в которых начинается соответственно с третьего и четвертого чисел. После третьего цикла сравнения (семь тактов) в ЗУ имеется следующая последовательность чисел:

Адрес 1 2 3 4 5

Число 15 14 13 l1 12

После четвертого цикла сравнения (четыре такта) в ЗУ имеется упорядоченный (в порядке убывания) массив чисел:

Адрес

Число

1 2 3 4 5

15 14 13 12 11

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

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

И, вторые входы которых соединены соответственно с прямым и инверсным выходами первого триггера, выход первого элемента И является выходом pasрешения считывания устройства,.выход второго элемента И подключен к первым входам третьего и четвертого элементов И, вторые входы которых соединены .соответственно с прямым и инверсным выходами второго триггера, входы установки в "0" первого и второго триггеров соединены с выходом первого элемента задержки, выходы разрядов первого и второго регистров подключены к входам соответственно первой и второй групп первой схемы сравнения и первым входам соответствующих вы5

ЗО

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

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

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

1425652

9 °

Корректор С. Шекмар

Заказ 47?О/46 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 соединены со счетным входом первого счетчика, вторым входом первого элемента ИЛИ, выходом первого элемента задержки входами установки .в "0

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

1 подключен к первым входам пятого и

,шестого элементов И, вторые входы которых подключены соответственно к

1 инверсному и прямому выходам третье.

ro триггера, вход установки.в еди- 20 ичное состояние которого соединен

lc выходом третьей схемы сравнения, ыход пятого элемента И подключен вторым входам выходных элементов четвертой группы и через третий элемент задержки к счетному входу торого счетчика, выходы разрядов оторого подключены к первым входам оответствующих элементов И перепии третьей группы, вторые входы ко30 торых подключены к выходу седьмого флемента И, первый вход которого соединен с инверсным выходом третьего триггера, а второй вход подключен к выходу формирователя импульсов, первый вход которого соединен с инферсным выходом четвертого триггера, Первыми входами восьмого и девятого элементов И и вторыми входами элементов И переписи четвертой группы, Составитель E.Èâàíñ"а

Редактор Г.Гербер Техред М.Ходанич; второй вход формирователя импульсов соединен с первыми входами десятого и одиннадцатого элементов И, вторыми входами элементов И переписи пятой группы и прямым выходом четвертого триггера, вход установки в единичное состояние которого подключен к выходу

"Меньше" первой схемы сравнения, выход "Больше", равно" которой подключен к входу установки в "0" четвертого триггера, выход шестого элемента И соединен с первым входом второго элемента ИЛИ и через четвертый элемент задержки с входом установки в единичное состояние первого триггера, выход второго элемента ИЛИ подключен к вторым входам выходных элементов И третьей группы, а второй вход соединен с выходом четвертого элемента И и вторыми входами девятого и.десятого элементов И, выходы которых подключены к первым входам соответственно третьего и четвертого элементов ИЛИ, выходы которых подключены к вторым входам выходных элементов И соответственно второй и первой групп, а вторые входы соединены с выходами соответственно одиннадцатого и восьмого элементов И, вторые входы которых соединены с входом первого элемента задержки, вторыми входами выходных элементов И пятой группы и выходом третьего элемента И, выход второго элемента И является выходом разрешения записи устройства и через пятый элемент задержки подключен к входу установки в единичное состояние второго триггера.