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

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

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

Недостатками известного устройства являются низкое быстродействие и узкие функциональные возможности.

Наиболее близким к заявленному является устройство для сортировки чисел, содержащее группу узлов сравнения,входной регистр, выходной регистр, элемент НЕ и два элемента И, причем каждый узел сравнения содержит элемент И, регистр, схему сравнения и коммутатор.

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

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

Цель достигается тем, что в устройство для сортировки чисел, содержащее К-1 узлов сравнения, где К - количество чисел сортируемого массива, элемент НЕ, два эле- мента И, причем вход задания режима устройства соединен с первым входом первого элемента И и через элемент НЕ - с первым входом второго элемента И, вторые входы первого и второго элементоз И объединены и подключенц к входу начальной установки устройства, каждый узел сравнения содержит первый элемент И, схему сравнения, коммутатор и первый регистр, выходы разрядов которого соединены с первыми группами информационных входов схемы сравнения и .коммутатора, выход схемы сравнения соединен с первым входом первого элемента И, выходы коммутатора 1-го узла сравнения, , К-2, соединены с информационными входами первого регистра (1+1)-го узла сравнения, введены элемент задержки, триггер, К-й узел сравнения, а в каждый узел сравнения - элемент НЕ, второй элемент И, элемент ИЛИ, второй регистр и триггеры с первого по четвертый, причем вход тактовых импульсов устройства соединен через элемент задержки с син- хровходами всех триггеров, а также первого и второго регистров всех узлов сравнения, вход начальной установки устройства соединен с информационным входом первого триггера первого узла сравнения, в каждом

узле сравнения прямой выход первого триггера соединен с информационным входом второго триггера и с первым входом элемента ,

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

0 второ.го элементов И соединены соответственно с прямым и инверсным выходами третьего триггера, прямой выход которого. соединен с информационным входом четвертого триггера, выходы разрядов первого

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

0 с управляющим входом коммутатора и входом разрешения записи второго регистра, прямые выходы второго и четвертого триггеров j-ro узла сравнения соединены соответственно с информационными входами

5 первого и третьего триггеров (j+1)-ro узла сравнения, , K-1, выходы коммутатора (К-1)-го узла сравнения соединены с информационными входами первого регистра К-го узла сравнения, информационные

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

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

Устройство для сортировки чисел содержит узлы сравнения 11-1к, каждый узел сравнения содержит первый и второй реги0 стры 2 и 3, схему А сравнения и коммутатор 5, триггеры 6-9 с первого по четвертый соответственно, элемент НЕ 10, первый и второй элементы И 11 и 12, элемент ИЛИ 13, информационный вход 14, вход 15 начальной уста5 новк и, тактовый вход 16, вход 17 задания режима работы устройства, информационный выход 18. выходы 19 и 20 соответственно триггеров и 9 каждого узла 1 сравнения, вход21 выбора режима узла сравнения, элемент НЕ 22, второй и первый элементы И

соответственно 23 и 24, триггер 26 и элемент задержки 26.

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

На вход 14 устройства последовательно параллельным кодом поступают числа сортируемых массивов. Одновременно с ними поступают тактовые импульсы на вход 16 устройства. Первое число массива сопровождается сигналом логической 1 на входе 15. Перед началом ввода очередного массива чисел на входе режима 17 должен быть установлен потенциал, соответствующий режиму сортировки чисел данного массива. Если необходимо выдавать на выход числа массива, начиная с наибольшего, на входе 17 должен быть установлен (и поддерживаться в течение ввода всех чисел данного массива) нулевой потенциал. При выводе младшими числами вперед - единичный потенциал на входе 17. При нулевом потенциале на входе 17 появление сигнала начала массива на входе 15 вызывает срабатывание элемента И 23 и устанавливает триггер 25 в единичное состояние, которое поддерживается в течение всего текущего ввода массива чисел. С- приходом первого тактового импульса, задержанного на время установки триггера 25, триггер 8 первого узла сравнения устанавливается в единичное состояние; впоследствии по мере поступления тактовых импульсов триггеры 8 и 9 блоков 1 последовательно заполняются единицами, определяя режим работы устройства большими числами вперед.

В данном режиме по первомутактовому импульсу первое число массива записывается в регистр 2i, а триггер 6i устанавливается в единичное состояние. Единичный сигнал с его выхода предопределяет перезапись в следующем (втором) такте числа из регистра 2i в регистр 3-1, а числа из регистра 3i (если оно там имеется - это может быть последнее число предыдущего массива)- в регистр 22 независимо от соотношения чисел в регистрах 21 и 3i. На втором такте, работы единица из триггера 6i переписывается в триггер 7-|; в этот же момент времени в регистр 2i записывается второе число массива, а первое переписывается в регистр 3i. В третьем такте работы устройства происходит сравнение чисел, содержащихся в регистрах 2i и 3i. Если число в регистре 3i больше, схема сравнения 4i формирует положительный сигнал, подключая через коммутатор 5i выходы регистра 3i к входам регистра 22, и этот же сигнал, по которому формируется разрешающий сигнал на регистр 3i, организует перепись числа из регистра 2i в регистр 3i. В регистр 2i в этом

же такте записывается третье число массива. При условии, что число в регистре 2i больше, отсутствие сигнала со схемы сравнения 4i подключает через коммутатор 5

5 выходы регистра 2i к входам регистра 22; в регистре 3i при этом остается то же число, что и раньше. Таким образом, в данном режиме большие числа переписываются из узла в узел, не записываясь в регистры 3, чем

10 организуется обгон ими меньших чисел.

При режиме меньшими числами вперед триггеры 8 и 9 узлов сравнения последовательно устанавливаются в нулевое состояние, при этом задействуется элемент

5 И 12 (вместо И 11), то есть режим подключения коммутатора определяется инверсным сигналом с блока сравнения 4, что обеспечивает обратный (меньшими числами вперед) режим работы.

0 Сразу за загрузкой последнего числа . данного массива может в следующем такте . начаться загрузка чисел следующего массива. При этом для каждого массива можно задать индивидуальный режим сортировки.

5 Единичное значение сигнала в триггерах 6 и 7 запрещает сравнение первого числа последующего массива и последнего числа предыдущего массива, чем исключается перемешивание чисел смежных массивов,

0 Окончание сортировки очередного массива фиксируется по наличию единичного значения сигнала на выходе 19 последнего узла сравнения. Режим сортировки текущего массива определяется потенциалом на вы5 ходе 20 последней ячейки 1, на информационном выходе 18 которой формируется очередное число отсортированного массива чисел. При наличии К узлов сравнения устройство позволяет сортировать в выбран- 0. ном индивидуальном для каждого массива режиме массивы размерностью до К чисел включительно. При этом возможен выбор режима (большими числами вперед или меньшими числами вперед).

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

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

0 Устройство для сортировки чисел, содержащее (К-1) узлов сравнения, где К - количество чисел сортируемого массива, элемент НЕ, два элемента И, причем вход задания режима устройства соединен с пер5 вым входом первого элемента И и через элемент НЕ -с первым входом второго элемента И, вторые входы первого и второго элементов И объединены и подключены к входу начальной установки устройства, каж- дый узел сравнения содержит первый эле

Изобретение относится к автоматике и вычислительной технике и может быть использовано для сортировки массивов двоичных чисел. Целью изобретения является г расширение области применения за счет обеспечения сортировки массивов чисел произвольного объема, Устройство содержит К ячеек анализа, где К - количество чисел в массиве, каждая ячейка анализа содержит регистр 2, регистр 3 результата, блок 4 сравнения, коммутатор 5, триггеры 6-9, элемент НЕ 10, элементы И 11, 12, элемент ИЛ И 13. Кроме того, устройство содержит элемент НЕ 22, элементы И 23, 24, триггер 25, элемент 26 задержки. Устройство позволяет осуществлять сортировку массивов чисел в режимах возрастания и убывания. Сразу за загрузкой последнего числа предыдущего массива может начаться загрузка первого числа следующего массива. Для каждого массива можно задать индивидуально режим сортировки. 1 ил.