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

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

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

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

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

Недостатком известного устройства является узкая область применения, так как оно не позволяет осуществлять сортировку чисел последующего массива до полного вывода чисел предыдущего массива, а также затрачивает на сортировку большое число тактов - по два такта на каждое число массива (с учетом требуемого вывода чисел предыдущего массива до ввода и сортировки чисел последующего массива).

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

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

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

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

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

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

На чертеже представлена структурная схема устройства для сортировки чисел. Устройство для сортировки чисел содер0 жит ячейки 11-1к, анализа j каждая из которых содержит регистр 2, элемент И 3, блок 4 сравнения и коммутатор 5, а также выходной регистр б, регистр 7 сдвига на К-1 выходов, первый 8 и второй 9 элементы

5 задержки, элемент И 10, элемент ИЛИ 11 и элемент НЕ 12, информационный вход 13, вход 14 начала массива, тактовый вход 15, информационный вход 16 регистра сдвига, выходы 171-17к-1 регистра сдвига, инфор0 мационный выход 18.

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

Массивы сортируемых чисел состоят из К чисел каждый, которые поступают на вход

5 13 устройства последовательно, одно за другим, в произвольном порядке. Каждое число сопровождается импульсом на тактовом входе 15 устройства. Первое число каждого массива сопровождается также сигналом логической Г на входе 14 начала

массива устройства. Исходное состояние всех блоков устройства произвольное. Блоки 4 сравнения формируют единичный сигнал на выходах в том случае, когда код числа, содержащийся в регистре одноименной ячейки анализа, меньше кода числа, поступающего на вход 13 устройства. Коммутатор 5 любой ячейки анализа при наличии на его управляющем выходе положительного сигнала коммутирует на выход сигнал с входа 13 устройства; при нулевом управляющем сигнале - сигнал с регистра 2 одноименной ячейки анализа.

При поступлении первого числа массива сигнал начала массива, поступая на вход сброса регистра 7, удерживает его в течение первого такта работы устройства в нулевом состоянии, вследствие чего на все элементы И 3 по входам 17 поступают нулевые сигналы, и коммутаторы 5 коммутируют на выходы коды одноименных регистров 2. Таким образом обеспечивается последовательный сдвиг рассортированных чисел предыдущего массива (в случае их наличия). Сдвиг осуществляется импульсом, сформированным по тактовому и задержанным на элементе 8 задержки. Максимальное число из регистра 2(К-1)-й ячейки анализа (при наличии результата по предыдущему массиву) записывается в выходной регистр, по тактам производится вывод рассортированных чисел предыдущего массива через выходной регистр.

Сигнал начала массива поступает также через второй элемент 9 задержки и элемент ИЛИ 11 на синхровход регистра 2 первой ячейки анализа и в него записывается первое число данного массива (независимо от величины этого числа). Так как все элементы И закрыты, первое число не может записаться больше ни в один из регистров 2.

Во втором такте работы устройства на вход 13 поступает второе число массива/ При этом (во всех последующих тактах ввода данного массива) сигнал на входе 14 отсутствует, тактовым импульсом в регистр 7 сдвига по информационному входу (подклю ченному постоянно к положительной шине питания устройства) в первый разряд регистра 7 записывается единица, открывая элемент И 3i. Работа устройства во втором и последующих тактах работы определяется взаимным расположением и величинами чисел массива.

Пусть второе число массива больше первого. При этом с выхода блока 41 сравнения формируется положительный сигнал, который, проходя через открытый элемент И 3i, обеспечивает формирование на выходе коммутатора 51 сигнала с выходов 13

устройства. По задержанному тактовому импульсу, поступающему на регистры 2 и 6 в данном случае сигнал на синхровход регистра 2i не поступает), все числа предыдущего массива вновь сдвигаются по последовательной цепочке регистров 2, в которых они находятся, а в регистр 2а записывается число - второе число массива, Первое число при этом остается в регистре 2i.

0 Пусть третье число больше первого, по меньше второго. В третьем такте работы устройства открыты элементы И 3i и 32 (по единичным значениям сигналов на выходах 17i и регистра 7), Из соотношения чисел

5 следует, что срабатывает элемент И 3i, a элемент 32 не срабатывает. Следовательно, второе число записывается в регистр 2з. третье - в регистр 22, а первое число вновь остается в регистре 2i. Функционирование

0 устройства при вводе остальных чисел массива аналогично. По мере ввода чисел массива регистр 7 заполняется единицами, обеспечивая со ртировку заданного количества чисел, введенного в данном массиве в

5 устройство.

В том случае, когда вводимое число меньше минимального (на текущий момент)1 числа, содержащегося в регистре 21, блок 4г:% г сравнения не формирует единичного сигна-

0 ла, что вызывает появление единичного сигнала на выходе элемента НЕ 12, который по тактовому импульсу проходит через элементы И 10, ИЛИ 11 на синхровход регистра 2i. обеспечивая запись данного числа (наи5 меньшего) в регистр 21. При этом остальные числа массива продвигаются по цепочке регистров 2.

В К-м такте единица достигает старшего разряда регистра 7, фиксируя окончание

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

5 обнуления регистра 7 числа данного массива защищены от участия в сортировке совместно с числами последующего массива. В К-м такте старшее (наибольшее по величине) число данного массива записывается в

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

Таким образом, предлагаемое устройство позволяет осуществлять сортировку мас5 сивов без ожидания полного вывода всех чисел предыдущего массива до начала ввода чисел следующего, при этом на каждое число для его Сортировки затрачивается лишь один такт работы устройства, в то время как известные устройства требуют либо

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

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

Изобретениёгетносится к автоматике и вычислительной технике и может быть ис/5 Я Пг1 пользовано для сортировки массивов двоичных чисел. Целью изобретения является повышение быстродействиия при сортировке по убыванию. Устройство для сортировки чисел содержит выходной регистр 6, регистр 7 сдвига, элементы 8, 9 задержки, элементы И 10, ИЛИ 11, НЕ 12, К-1 ячеек 1 анализа - где К - число чисел в массиве. Каждая ячейка анализа содержит регистр 2, элемент И 3, блок 4 сравнения и коммутатор 5. Быстродействие устройства повышается за счет возможности ввода нового массива до окончания сортировки предыдущего массива. 1 ил. 21213 ,7,, Ё vj ел CJ 4 О Ю