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

4:

00

со

aiit.f

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

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

На фиг. 1 представлена ф Ункциональ ная схема устройства; на фиг. 2 - временная диаграмма работы блока синхрО - низации; на фиг. 3 - временная диаг- рамма работы блоков синхронизации группы.

Устройство содержит блок 1 синхро- низа1щи, счетчик 2, первую группу из М блоков 3 памяти, где М - количество чисел в строке массива, вторую группу из М блоков 4 памяти, группу из М ключей 5, группу из М блоков 6 элементов И, группу из М блоков 7 синхронизации, первую группу из М эле- ментов И 8, вторую группу из М эле- |ментов И 9, блок 10 выбора максимального кода, блок 11 приоритета, блок 12 элементов ИЛИ и с первого по третий элементы ИЛИ 13-15.

Кроме того, на фиг,1 показаны вход 16 начальной установки устройства, вход 17 пуска устройства, информацион ньй выход 18 счетчика 2 (подключен к адресным входам всех блоков 3,4 памяти), первый выход 19 блока 1 синхронизации, второй выход 20 блока 1 синхронизации, выходы 21 группы блока 1 синхронизации, с первого по четвертый выходы 22 - 25 блока 7 синхронизации.

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

Пусть необходимо упорядочить по невозрастанию чисел в строках массив

50

Перед началом работы указанньй мае- сив чисел записьгоают в блоки 3 памяти. При этом в первый блок 3 памяти группы по адресам 1-3 записывают соответственно числа 1,5,7 (т.е. числа первого столбца массива), во второй блок 3 памяти группы по адресам 1, 2, 3 записьшают числа 2, 3, 2 и в третий блок 3 памяти группы по адресам 1, 2,

Q

0 5 0

5

0

5

0

3 - числа 4, 1, 1. На вход 16 начальной установки подают импульсный сигнал единичного уровня. При этом счетчик 18 обнуляется, блок 1 синхронизации устанавливается в исходное состояние. На вход 17 пуска устройства подают импульсный сигнал единичного уровня. При этом блок 1 синхронизации начинает вырабатывать сигналы, предусмотренные временной диаграммой его работы. Сигнал единичного уровня появляется на выходе 20 блока 1, при

этом все ключи 5 группы устанавлива

ются в исходное состояние, при котором их информационные входы соединены с информационными выходами, в счетчике 2 фиксируется код числа 1, блоки 3 памяти вьщают на свои выходы числа первой строки массива. Одновременно появляется сигнал на первом выходе 21 группы блока 1. Через время Т1, достаточное для выбора Максимального из кодов чисел 1, 2, 4 (т.е. максимального из чисел первой строки массива), обладающего наивысшим приоритетом (в данном случае - числа 4), на выходе 19 блока 1 появляется им- пусный сигнал единичного уровня, ко- торьй запускает третий блок 7 синхронизации группы (так как число 4 нахо дится в третьем блоке 5 памяти), Тре-; тий блок 7 синхронизации начинает вырабатывать импульсные сигналы в соответствии с временной диаграммой работы. Сигнал появл:яется на выходе 21 третьего блока 7, при этом открывается третий блок 6 элементов И, и одновременно - на вькоде 24 третьего блока 7, при этом третий ключ 5 размыкает свою информационную цепь (выключается) о Через время Т1, достаточное для выдачи максимального числа на ин формационные входы блоков 4 памяти третий блок 7 формирует сигнал на выходе 23. При этом максимальное число первой строки (число 4) заносится по адресу О в первый блок 4 памяти группы. Сразу после завершения процесса записи третий блок 7 синхронизации формирует сигнал на выходе 25. При этом блок 1 синхронизации снимает потенциал единичного уровня с первого выхода 21 группы и формирует его на втором выходе 21 группы. Далее работа устройства повторяется г выбирается максимальное из оставшихся чисел первой строки (1 к 2), записьюается во второй блок 4 памяти группы и т,д.

После того как будут упорядочены все числа первой строки массива, по очередному импульсу пуска появится сигнал на выходе 20 блока 1 синхронизации. При этом счетчик 2 зафиксирует код числа 2, на выходах блоков 3 памяти группы появятся числа второй строки массива и т.д. После того как будут упорядочены числа всех строк массива, при очередном пуске блока 1 синхронизации сигнал с выхода 20 переполнит счетчик 2, что будет служить признаком окончания работы устройства.

.

Кроме того, сигнал с выхода признака переполнения остановит блок 1 синхронизации и работа устройства прекратится. При этом числа исходного массива будут упорядочены по строкам следующим образом:

4 5 7

2 3 2

В том случае, если числа массива вводятся в блоки 3 памяти группы по строкам, устройство упорядочивает числа массива по невозрастанию в столбцах.

Следует отметить, что группы блоков 3, 4 памяти могут быть вьтолнены в виде матриц регистров.

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

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

ции и к выходу установки а О счетчика, информационный выход которого подключен к адресным входам всех бло- g ков памяти первой и второй групп, выход К-го блока памяти первой группы (,.о.,М) подключен к информационному входу К-го ключа группы и к инфор- мационнму входу К-го блока элементов И группы, выход которого подключен к К-му информационному входу блока элементов ИШ-1, выход которого подключен . к информационным входам всех блоков памяти второй группы, вход пуска уст- 5 ройства подключен к первому входу первого элемента ИЛИ, выход которого подключен к входу пуска блока синхронизации, первый выход которого под-, ключей к первым входам всех элементов 0 И первой группы, выход К-го ключа группы подключен к К-му входу блока выбора максимального кода, К-й выход позиции максимального кода которого подключен к К-му входу блока приори- . 5 тетов К-й выход позиции сигнала с наибольшим приоритетом которого подключен к второму входу К-го элемента И первой группы, выход которого подключен к входу пуска К-го блока син- 0 хронизации группы, первый выход которого подключен к управляющему входу К-го блока элементов И группы, второй выход К-го блока синхронизации группы подключен к К-му входу второго элемен- с та ИЛИ, выход которого подключен к первым входам всех элементов И второй группы, третий выход К-го блока синхронизации группы подключен к управляющему входу К-го ключа группы, чет- 0 вертый выход К-го блока синхронизации подключен к К-му входу третьего элемента И, выход которого подключен к второму входу первого элемента ИЛИ, второй выход блока синхронизации под- 5 ключен к входам начальной установки всех ключей группы и к суммирующему входу счетчика, выход признака переполнения которого подключен к входу останова блока синхронизации, К-й выход группы которого подключен к второму входу К-го элемента И второй груп-, пы, выход которого подключен к входу признака записи К-го блока памяти второй группы.

. Z

Изобретение относится к области вьгаислительной техники и может быть использовано для упорядочения двумерных массивов чисел по строкам (столбцам) массива. Целью изобретения является повьшение быстродействия устройства при упорядочении двумерного массива чисел по признаку невозрастания чисел йо строке. Устройство содержит блок 1 синхронизации, счетчик 2, первзгю и вторую группы блоков 3 и 4 памяти, группу ключей 5, группу блоков 6 злементов И, группу блоков 7 синхронизации, две группы элементов И 8 и 9, блок 10 выбора максимального кода, блок 11 приоритета, блок 12 элементов ИЛИ и с первого по третий элементы ИЛИ 13, 14 и 15. Перед началом работы числа исходного массива вводят в блоки 3 памяти (в каждый блок - один столбец массива)о Далее последовательно выбираются строки чисел массива и упорядочиваются при помощи блока 10 выбора максимального кода. 3 ил. сл

вход пуска

jr

27

23

2

гг

Фие. S

-& €

t

-анЛ