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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН ОПИСАНИЕ ИЗОБРЕТЕ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ.У 46В.А.Миль ство СССР 22 1979во СССР 122, 1986,ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ(54) УСТРОЙСТВО ДЛЯ УПОРЯДОЧЕНИЯ МАС,СИВА ЧИСЕЛ(57) Изобретение относится к областивычислительной техники и может бытьиспользовано для упорядочения двумерных массивов чисел по строкам (столбцам) массива. Целью изобретения является повьппение быстродействия уст 801444830(504 С 06 С 7/122 С 06 Р 3 36 ройства при упорядочении двумерного массива чисел по признаку невозрастания чисел по строке. Устройство содержит блок 1 синхронизации, счетчик 2, первую и вторую группы блоков 3 и 4 памяти, группу ключей 5, группу блоков б элементов И, группу блоков 7 синхронизации, две группы элементов И 8 и 9, блок 10 выбора максимального кода, блок 11 приоритета, блок 12 элементов ИЛИ и с первого по третий элементы ИЛИ 13, 14 и 15. Перед началом работы числа исходного массива вводят в блоки 3 памяти (в каждый блок- один столбец массива). Далее последовательно выбираются строки чисел массива и упорядочиваются .при помощи ф блока 10 выбора максимального кода. 3 ил.С."Изобретение относится к вычислительной технике и может быть использовано для упорядочения двумерных массивов чисел по строкам (столбцам)массива.Целью изобретения является повышение быстродействия устройства приупорядочении двумерного массива чиселпо признаку невозрастания чисел построке,На Фиг. 1 представлена функциональ.ная схема устройства; на фиг. 2 - временная диаграмма работы блока синхронизации; на фиг, 3 - временная диаграмма работы блоков синхронизациигруппы.Устройство содержит блок 1 синхронизации, счетчик 2, первую группу изМ блоков 3 памяти, где М - количество 20чисел в строке массива, вторую группуиз М блоков 4 памяти, группу из Мключей 5, группу из М блоков 6 элементов И, группу из М блоков 7 синхронизации, первую группу из М элементов И 8, вторую группу из М эле 1 ментов И 9, блок 10 выбора максимального кода, блок 11 приоритета, блок12 элементов ИЛИ и с первого по третий элементы ИЛИ 13-15. 30Кроме того, на фиг.1 показаны вход16 начальной установки устройства,вход 17 пуска устройства, информацион.ный выход 18 счетчика 2 (подключен кадресным входам всех блоков 3,4 памяти), первый выход 19 блока 1 синхронизации, второй выход 20 блока 1 синхронизации, выходы 21 группы блока 1синхронизации, с первого по четвертыйвыходы 22 - 25 блока 7 синхронизации. 4 ОУстройство работает следующим образом.Пусть необходимо упорядочить поневозрастанию чисел в строках массив453 1Перед началом работы указанный мас 50 сив чисел записывают в блоки 3 памяти. При этом в первый блок 3 памяти группы по адресам 1-3 записывают соответ" ственно числа 1,5,7 (т.е. числа первого столбца массива), во второй блок55 3 памяти группы по адресам 1, 2, 3 записывают числа 2, 3, 2 и в третий блок 3 памяти группы по адресам 1, 2,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) заносится поадресу 0 в первый блок 4 памяти группы. Сразу после завершения процессазаписи третий блок 7 синхронизацииФормирует сигнал на выходе 25, Приэтом блок 1 синхронизации снимает потенциал единичного уровня с первоговыхода 21 группы и формирует его навтором выходе 21 группы. Далее работаустройства повторяется: выбираетсямаксимальное из оставшихся чиселпервой строки (1 и 2), записываетсяво второй, блок 4 памяти группы и т,д,3 14448 После того как будут упорядочены все числа первой строки массива, по очередному импульсу пуска появится сигнал на выходе 20 блока 1 синхрониза" ции, При этом счетчик 2 зафиксирует код числа 2, на выходах блоков 3 памяти группы появятся числа второй строки массива и т,д. После того как будут упорядочены числа всех строк1 О массива, при очередном пуске блока 1 синхронизации сигнал с выхода 20 переполнит счетчик 2, что будет служить признаком окончания работы устройства. Кроме того, сигнал с выхода признака 15 переполнения остановит блок 1 синхронизации и работа устройства прекратится. При этом числа исходного массива будут упорядочены по строкам следующим. образом: 20 4 2 1 5 3 1 7 2 1 25 Устройство для упорядочения массива чисел, содержащее две группы из М блоков памяти, где М - количество чисел в строке массива, группу из М 4 О ключей, блок выбора максимального кода, три элемента ИЛИ, блок синхрониЬации и счетчик, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия устройства при упорядочении двумерного массива чисел по признаку невозрастания чисел по строке, в него введены две группы из М элементов И, группа из М блоков синхронизации, группа из М блоков элемен. тов И, блок элементов ИЛИ и блок приоритета, причем вход начальной установки устройства подключен к входу начальной установки блока синхронизаВ том случае, если числа массива вводятся в блоки 3 памяти группы по строкам, устройство упорядочивает числа массива по невозрастанию в столбцах. ЗОСледует отметить, что группы блоков 3, 4 памяти могут быть выполнены в виде матриц регистров. Формула изобретения 30 411 1 ции и к выходу установки а 0 счетчика, информационный выход которого подключен к адресным входам всех бло" ков памяти первой и второй групп, выход К-го блока памяти первой группы (К=1, ,М) подключен к информационному входу К-го ключа группы и к информационнму входу К-го блока элементов И группы, выход которого подключен к К-му информационному входу блока элементов ИЛИ, выход которого подключен. к информационным входам всех блоков памяти второй группы, вход пуска устройства подключен к первому входу первого элемента ИЛИ, выход которого подключен к входу пуска блока синхронизации, первый выход которого под-, ключен к первым входам всех элементов И первой группы, выход К-го ключа группы подключен к К-му входу блока выбора максимального кода, К-й выход позиции максимального кода которого подключен к К-му входу блока приоритетов К-й выход позиции сигнала с наибольшим приоритетом которого подключен к второму входу К-го элемента И первой группы, выход которого подключен к входу пуска К-го блока синхронизации группы, первый выход которого подключен к управляющему входу К-го блока элементов И группы, второй выход К-го блока синхронизации группы подключен к К-му входу второго элемента ИЛИ, выход которого подключен к первым входам всех элементов И второй группы, третий выход К-го блока син" хронизации группы подключен к управляющему входу К-го ключа группы, четвертый выход К-го блока синхронизации подключен к К-му входу третьего элемента И, выход которого подключен к второму входу первого элемента ИЛИ, второй выход блока синхронизации подключен к входам начальной установки всех ключей группы и к суммирующему входу счетчика, выход признака переполнения которого подключен к входу останова блока синхронизации, К-й выход группы которого подключен к второ. му входу К-го элемента И второй груп", пы, выход которого подключен к входу признака записи К-го блока памяти второй группы.1444830 Коррек Редак ина а аж 70 9 51, Зак о НИИ 35, Мос ское предприятие рои дхО ЛС твенно-поли Составитель А Техред И,Дид арственног изобретени Ж, Раув комитета С и открытий кая наб.,ул. Проектная