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

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

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

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

Устройство содержит управляющий регистр 1, элементы 2 и 3 запрета и m узлов 4 анализа (т - количество сортируемых чисел).

Каждый узел анализа образуют шинный формирователь 5, блок 6 сравнения, коммутаторы 7 и 0, регистр 9, элемент И 10, элементы ИЛИ 11 и 12, шину 13,J ввода-вывода 1-го сортируемого числа (i 1, 2, ..., m). Устройство содержит также вход 14 записи, тактовый вход 15, информационный выход 16, выход 17 окончания работы, входы, и выходы наращивания устройства .

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

На шины 13 -1Зщодновременно поступает m сортируемых чисел и сигналом по входу 14 через соответствующие шинные формирователи 5 и комутаторы 8 записываются в регистры 9 узлов 44-4т анализа, регистр 1 обнуляется (не показано). Затем сигнал с входа 14 снимается, а на входе 18 устанавливается код минимального возможного числа. В каждом из узлов анализа 4J коммутатор 7 выбирает болшее из двух чисел: поступившее с выходов коммутатора 7 предыдущего узла анализа 4j и хранящееся в регистре 9,. В результате на выходе 16 устройства формируется код максимального из чисел, записанных в регистры 9

0

5

0

5

0

5

0

5

устройства. Это число пЪд воздействием тактового импульса по входу 15 записывается в регистр 9 узла 4{. Одновременно число, хранящееся в регистре 9 этого узла, переписывается в регистр 9 узла 4г и т.д. вплоть до того узла анализа 4, в регистре 9 которого находилось выделенное максимальное число. В этом узле 4 на выходе блока 6 сравнения имеется О, который поступает на вход цепочки элементов И 10, что предопределяет нулевой сигнал на входах разрешения записи Увсех регистров 9 узлов анализа 4р для (5 #. В узт лах 4р,р К, на входах разрешения записи V регистров 9 присутствует потенциал 1. Тем же тактовым сигналом с входа 15 содержимое регистра 1 сдвигается в сторону старших разрядов, а в младший разряд записывается единица.

После i тактов в i младших разрядах регистра 1 записаны единичные значения, которые поступают на входы элементов ИЛИ 12 соответствующих узлов 4jj-4j. Это приводит к тому, что уже выделенные и записанные в регистры 9 узлов j i максимальных чисел не принимаются во внимание при поиске очередного (i-M)-ro по величине числа. На выходах элементов ИЛИ 11 этих узлов анализа присутствует сигнал , который вызывает перезапись чисел, находящихся в регистрах 9.

После m тактов на выходе ш-го разряда регистра 1 и на выходе 17 окончания работы устройства формируется сигнал 1, а в регистрах 9 узлов 4,-4m находится исходный массив чисел, отсортированный в порядке возрастания. Формула изобретения

Устройство для сортировки чисел, со держащее регистр управления и m

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

9533. 6

ввода-вывода второй группы шинного формирователя соединены с информационными входами первых групп первого и второго коммутаторов и выходами соответствующих разрядов регистра, выход блока сравнения и выход 1-го разряда регистра управления соединены соответственно с первым и вторым

JQ входами второго элемента ИЛИ того же узла анализа, выход этого элемента ИЛИ соединен с управляющим входом первого коммутатора и первым входом элемента И, выход первого элемента

J5 ИЛИ и выходы второго коммутатора соединены соответственно с входом разрешения записи и информационными входами регистра того же узла анализа, выходы первого коммутатора первого

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - расширение области применения за счет обеспечения параллельного ввода сортируемых чисел. Устройство содержит управляющий регистр 1, элементы запрета 2, 3 и m узлов анализа (УА) 4 - 4m(m - количество сортируемых чисел). Каждый узел анализа содержит шинный формирователь 5, блок сравнения 6, комму з I8i ML

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

5

0

5

0

ми выходами устройства и соединены с информационными входами второй грУп- пы второго коммутатора первого узла анализа, вход логической единицы устройства соединен с вторыми входами элемента И и первого элемента ИЛИ первого узла анализа, информационные входы первой и второй групп первого коммутатора j-ro узла анализа, где j 1 2, ..., (m-1), подключены соответственно к входам второй группы второго коммутатора и выходам первого коммутатора (j+1)-ro узла анализа, выход элемента И j-ro узла анализа соединен с вторыми входами элемента И и первого элемента ИЛИ (j+1)-ro узла анализа, первый и второй входы первого коммутатора и выход элемента И т-го узла анализа являются соответственно входами и выходом наращивания устройства.