Устройство для сортировки чисел

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (si)s G 06 F 7/06

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ!

Ю

I (21) 4807309/24 (22) 28.03.90 (46) 30,01.93. Бюл, М 4 (71) Московский институт инженеров гражданской авиации (72) С.Ж.Кишенский, Н.С.Вдовиченко, В.Э.Игнатьев и О.Ю.Христенко (56) Авторское свидетельство СССР

М 1397900, кл. G 06 F 7/08, 1988.

Авторское свидетельство СССР

М 1112362, кл. G 06 F 7/08, 1983. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для сортировки массивов двоичных чисел. Целью изобретения является,, Ы,„, 1791812 Al расширение области применения за счет обеспечения сортировки массивов чисел произвольного объема, Устройство roäåðжит К ячеек анализа, где К вЂ” количество чисел в массиве, каждая ячейка анализа содержит регистр 2, регистр 3 результата. блок 4 сравнения, коммутатор 5, триггеры

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

1791812

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

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

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

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

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

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

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

50 узле сравнения прямой выход первого триггера соединен с информационным входом второго триггера и с первым входом элемента ИЛИ, второй и третий входы которого соединены с выходами первого и второго элементов И, выход схемы сравнения через элемент НЕ соединен с первым входом второго элемента И, вторые входы первого и второго элементов И соединены соответственно с прямым и инверсным выходами третьего триггера, прямой выход которого соединен с информационным входом четвертого триггера, выходы разрядов первого регистра соединены с информационными входами второго регистра, выходы разрядов которого подключены к вторым группам информационных входов коммутатора и схемы сравнения,. выход элемента ИЛИ соединен с управляющим входом коммутатора и входом разрешения записи второго регистра, прямые выходы второго и четвертого триггеров j-ro узла сравнения соединены соответственно с информационными входами первого и третьего триггеров (j+1)-го узла сравнения, J=1, К-1, выходы коммутатора (К-1)-го узла сравнения соединены с информационными входами первого регистра К-го узла сравнения, информационные входы первого регистра первого узла сравнения являются информационными входами устройства, прямые выходы второго и четвертого триггеров К-го узла сравнения являются соответственно выходом окончания сортировки массива и выходом сортировки массива устройства, выходы коммутатора К-го узла сравнения являются информационными выходами устройства, выходы первого и второго элементов И устройства соединены соответственно с входами установки в "0" и в "1" триггера, прямой выход которого соединен с информационным входом третьего триггера первого узла сравнения.

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

Устройство для сортировки чисел содержит узлы сравнения 1>-1к, каждый узел сравнения содержит первый и второй регистры 2 и 3, схему 4 сравнения и коммутатор

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

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

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

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

25 в единичное состояние, которое поддерживается в течение всего текущего ввода массива чисел. С- приходом первого тактового импульса, задержанного на время установки триггера 25, триггер 8 первого узла сравнения устанавливается в единичное состояние; впоследствии по мере поступле ния тактовых импульсов триггеры 8 и 9 блоков 1 последовательно заполняются

"единицами", определяя режим работы устройства "большими числами вперед".

В данном режиме по первомутактовому импульсу первое число массива записывается в регистр 2, а триггер 6> устанавливается в единичное состояние. Единичный сигнал с его выхода предопределяет перезапись в следующем (втором) такте числа из регистра 2 в регистр 3., а числа из регистра

3 (если оно там имеется — это может быть последнее число предыдущего массива) — в регистр 2z независимо от соотношения чисел в регистрах 2> и 3>, На втором такте. работы "единица" из триггера 6 переписывается в триггер 7 ; в этот же момент времени в регистр 21 записывается второе число массива, а первое переписывается в регистр 3 . В третьем такте работы устройства происходит сравнение чисел, содержащихся в регистрах 2 и 3>. Если число в регистре

3 больше, схема сравнения 4 формирует положительный сигнал, подключая через коммутатор 5> выходы регистра 3> к входам регистра 22, и этот же сигнал, по которому формируется разрешающий сигнал на регистр 3>, организует перепись числа из регистра 2> в регистр Зь В регистр 2 в этом

35

40. ном индивидуальном для каждого массива режиме массивы размерностью до К чисел включительно, При этом возможен выбор

50

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

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

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

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

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

"меньшими числами вперед" ).

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

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

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

Составитель С.Кишенский

Техред M.Ìoðãåíòàë Корректор О.Кравцова

Редактор

Заказ 152 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб„4/5

Производственно-издательский комбинат "Патент", г, Ужгород, ул,Гагарина, 101 мент И, схему сравнения, коммутатор и первый регистр, выходы разрядов которого соединены с первыми группами информационных входов схемы сравнения и коммутатора, выход схемы сравнения соединен с первым входом первого элемента И. выходы коммутатора i-го узла сравнения (1=1,К-2) соединены с ин! ормационными входами первого регистра

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

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

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

20 первого узла сравнения являются информационными входами устройства, прямые выходы третьего и четвертого триггеров К-го узла сравнения являются соответственно выходом окончания сортировки массива и

25 выходом режима сортировки массива устройства, выходы коммутатора К-го узла сравнения являются информационными выходамиустройства, выходы первого и второго элементов И устройства соединены

30 соответственно с входами установки в "Он и в "1" триггера, прямой выход которого соединен с информационным входом второго триггера первого узла сравнения.