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

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

5

лении второго тактового импульса на вход 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. Как только в .счетчике

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

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

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

8

10

15

20

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

25

30

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

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

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

8

5

0

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

5

0

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

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

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

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

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

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

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