SU1425652A1

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

Info

Publication number: SU1425652A1
Application number: SU864063507A
Authority: SU
Inventors: Николай Иванович Крылов; Виктор Михайлович Полищук; Наталья Николаевна Шубина
Original assignee: Войсковая Часть 25840
Priority date: 1986-04-30
Filing date: 1986-04-30
Publication date: 1988-09-23

Description

W

(Л

to ел

О5

ел

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

Целью изобретени вл етс повы- |шение быстродействи устройства. I На чертеже представлена схема уст- |ройства,

Устройство содержит регистры 1 3, ;счетчики 6 и 7, схемы 8-10 сравнени , |триггеры 11-14, элемент 15 запрета, группы 16-20 элементов И переписи, группы 21-25 выходных элементов И, группы элементов ИЛИ 26 и 27, элементы И 28-38, элементы ИЛИ 39-42, формирователь 43 импульсов, элементы 44-48 задержки, информационные вхо- чы 49, вход 50 запуска, вход 51 так™ говых импульсов, ин формационные выходы 52, выход 53 окончани работы, зыходы 54 разрешени считывани , записи 55, адресные выходы 56,

В качестве формировател 43 им

5

0

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

Схема 10 сравнени и триггер 11 мен ют свое состо ние, так как содержимое регистра 3 больше, чем содержимое регистра 4, а формирователь 43 вырабатывает импульс, по которому из счетчика 7 через элементы И группы 17 в регистр 5 записываетс адрес первого числа. Затем .этим же тактовым импульсом, задержанным на элементе 45 задержки на врем переходных процессов, содержимое счетчика 7

пульсов может использоватьс извест- «увеличиваетс на единицу. При поступна . схема мультивибратора, котора Дозвол ет сформировать управл ющий Сигнал при каждом изменении состо ни хемы сравнени .

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

I В исходном состо нии в регистре 1 фаписан адрес начала зоны, реги- 4тре 2 - адрес конца зоны массива Ысел, записанного в запоминающем Устройстве (ЗУ) общего назначени , Который требуетс упор дочить. В ре- ifHCTpax 3 и 4 записано минимальное ашинное число, счетчики 6 и 7, Триггеры 11-14 наход тс в нулевом (Досто нии. Так как содержимое реги- cjTpoB 3 и 4 равно, то на первом вы- 5|оде схемь 10 сравнени имеетс единичный сигнал, который подтверждает установку триггера 11 в нулевое состо ние , и, следовательно, открыты элементы И группы 19. При поступлении сигнала запуска на вход 50 содержимое регистра 1 переписываетс через элементы И группы 18 в счетчик 6, а затем через врем задержки, определ емое элементом 44 задержки, переписываетс через элементы И группы 16 в счетчик 7. Содержимое счетчиков 6 и 7 сравниваетс схемами 8 и 9 с со- держимьм регистра 2. Так как содержимое счетчиков 6 и 7 меньше, то на выходах схем 8 и 9 сравнени имеетс нулевой сигнал и, следовательно, элемент 13 запрета открыт. Тактовый им30

35

40

45

55

лении второго тактового импульса на вход 51 из ЗУ считываетс второе число по адресу счетчика 7, описанным выше способом. Поступающее на входы 49 второе число записываетс в регистр 4 через открытые элементы И групп 20j так как триггер 11 находитс в единичном состо нии. Если поступившее второе число, записанное в регистре 4, больше или равно первому числу, записанному в регистре 3, то схема 10 сравнени и триггер И мен ют свое состо ние, подготавлива запись очередного числа в регистр 3, а формирователь 43 вырабатывает импульс, по которому адрес второго (очередного) числа записываетс в регистр 5. При поступлении очередного тактового импульса очередное число считываетс из ЗУ и записываетс в тот из регистров 3 или 4, где записано меньшее число. Если при этом соотношение чисел, записанных в регистрах 3 и 4, мен етс , то формирователь 43 вырабатывает сигнал, по которому в регистр 5 через элементы И группы 17 записываетс содержимое счетчика 7. Таким образом, в одном из регистров 3 или 4 записано максимальное число, а в регистре 5 - его адрес, Работа устройства продолжаетс аналогично до тех пор, пока содержимое счетчика 7 не преБьш1ает значение адреса конца зоны, записанного в регистре 2. Как только в .счетчике

0

5

0

5

7 будет значение, превьшаю1цее значеие адреса конца зоны, схема 9 сравнени вырабатывает сигнал, который станавливает триггер 12 в единичное состо ние, и очередной тактовый импульс поступает на выход 54 и через элементы И 31 и ИЛИ 40 на входы элеентов И группы 24, в результате че- го по первому адресу считываетс первое число в один из регистров 3 или 4. Таким образом, в одном из регистров 3 или 4 записано максимальное , а в другом - первое число. Затем этим же тактовым импульсом, заержанным в элементе 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 и элементы I-fflH группы 26 поступает на выход 52 устройства .-Этим же тактовым импульсом открываютс элементы И группы 24 и по адресу , наход щемус в счетчике 6, в

ЗУ записываетс максимальное число. Этот же импульс, задержанный элементом 47 задержки на врем переходных процессов, устанавливает триггер 14 в единичное состо ние. Следующий i-aK- тоБЫй импульс, пройд элементы И 32, И 34, И 38 или И 37, ИЛИ 42 или ИЛИ 41, открывает элементы И группы 22 или И группы 21, и меньшее число, которое ранее записано в регистре 4 или 3 через элементы И группы 22 или группы 21 и элементы ИЛИ.группы 26, поступает на выход 52 устройства. По

0

5

0

5

0

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

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

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

Адрес 1234 5

Число 13 11 12 14 15

5

0

5

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

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

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

3)первое число (13) и запоминаетс (в регистре 5) его адрес (1),

2-й такт - считываетс (в регистр

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

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

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

0

четьфех чисел (14 в регистре 4) и iero адрес (4 в регистре 5),

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

6-8-й такты - после сравнени всех чисел массива происходит перезапись в ЗУ: по адресу максимального числа (5) записываетс первое число (13), а по адресу первого числа (1) - максимальное число (15), т.е. после |1-го цикла сравнени в ЗУ имеетс Следующа последовательность чисел: I Адрес 12345

Число 15 11 -12 14 13 $торой цикл сравнени :

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

2-й такт - считываетс (в регистр I t) третье число (12), сравниваетс в схеме 10 сравнени ) с вторьм чис- jjioM (11) и запоминаетс максимальное из двух чисел (12 в регистре 4) и его лдрес (3 в регистре 5), I 3-й такт - считываетс (в регистр i) четвертое число (14), сравниваетс IB схеме 10 сравнени ) с максимальным 3 двух чисел (12 в регистре 4) и запоминаетс максимальное из трех чи- 4ел (14 в регистре 3) и его адрес (4 в регистре 5),

4-й такт - считываетс (в регистр 4:) п тое число (13), сравниваетс (IB схеме 10 сравнени ) с максимальным HJ3 трех чисел (14 в регистре 3) и за- п1оминаетс максимальное из четырех чисел (14 в регистре 3) и его адрес (4 в регистре 5),

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

Адрес 1 2345

Число 15 14 12 11 13

Далее аналогично выполн ютс третий и четвертый циклы сравнени , сравнение в которых начинаетс соот- в0тственно с третьего и четвертого чисел. После третьего цикла сравне0

ни (6 тактов) в ЗУ имеетс следующа последовательность чисел:

Адрес 1 .2 34 5 Число 15 14 13 11 12 После четвертого цикла сравнени (п ть тактов) в ЗУ имеетс упор доченный (в пор дке убывани ) массив чисел:

Адрес 12 3 4 5 Число 15 14 13 12 11 Таким образом, на упор дочение данного массива чисел в.предлагаемом устройстве требуетс 26 тактов, а 5 перезапись чисел в ЗУ оС5тцествл етс за три такта работы устройства.

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

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

с

1-й такт - из ЗУ считываетс первое число (13),

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

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

5 такт - из ЗУ считываетс четвертое число (14), так как оно больше первого числа (13), то происходит перезапись чисел в ЗУ;

5 и 6-й такты - в ЗУ на место пер- 0 вого числа (13) записываетс четвертое число (14), а на место четвертого числа (14) - первое число (13), большее число (14) запоминаетс в устройстве и последующие числа теперь 5 Сравниваютс с этим чис Ьом,

7-й такт - из ЗУ считываетс п тое число (15), так как оно больше первого числа (14), то происходит перезапись в ЗУ,

0 8 и 9-й такты - в ЗУ на место первого числа (14) записываетс п тое число (15), а на место п того числа (15) - первое число (14).

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

Адрес 12345

Число 15 11 12 1314

0

7 Второй цикл сравнени ;

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

После второго цикла сравнени (дес ть тактов) в ЗУ имеетс следующа последовательность чисел: Адрес 12345 Число 15 14 11 12 13 Далее аналогично выполн ютс третий и четвертый циклы сравнени , сравнение в которых начинаетс соответственно с третьего и четвертого чисел. После третьего цикла сравнени (семь тактов) в ЗУ имеетс следующа последовательность чисел: Адрес 12345 Число 15 14 13 11 12 После четвертого цикла сравнени (четыре такта) в ЗУ имеетс пор - доченный (в пор дке убывани ) массив чисел:

Адрес 12345 Число 15 14 13 12 11

Claims

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

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

8

10

15

20

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

25

30

чей к пр мому входу элемента запрета, и вторыми входами выходных элементов

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

выходами первого триггера, выход пер- 45 ви , в устройство введены п тый ревого элемента И вл етс выходом разрешени считывани устройства,«выход второго элемента И подключен к первым входам третьего и четвертого элементов И, вторые входы которых соединены .соответственно с пр мым и инверсным выходами второго триггера, входы установки в О первого и второго триггеров соединены с выходом первого элемента задержки, выходы разр дов первого и второго регистров подключены к входам соответственно первой и второй групп первой схемы сравнени и первым входам соответствующих вы-

8

5

0

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

5

0

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

50 тый и одиннадцатый элементы И,

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

55 переписи четвертой и п той групп., выходы которых соединены с соответст- вую|дими информационными входами соответственно первого и второго регистров , входы установки в О которых

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

стого элементов И, вторые входы оторых подключены соответственно к версному и пр мому выходам третье |го триггера, вход установки.в еди- ричное состо ние которого соединен с выходом третьей схемы сравнени , выход п того элемента И подключен к вторым входам выходных элементов Л четвертой группы и через третий 5лемент задержки к счетному входу jToporo счетчика, выходы разр дов .соторого подключены к первым входам Соответствующих элементов И переписи третьей группы, вторые входы которых подключены к выходу седьмого флемента И, первый вход которого фоединен с инверсным выходом третье- iho триггера, а второй вход подклю- ен к выходу формировател импульсов 1 ервый вход которого соединен с ин- ерсным выходом четвертого триггера, йервьми входами восьмого и дев того Элементов И и вторыми входами элементов И переписи четвертой группы.

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