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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК (я)5 G 06 F 7/08

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

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

ПРИ ГКНТ СССР Й »

ОП ИСАН И Е И 3ОБРЕТЕ Н И 4

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

1 (21) 4807362/24 (22) 28.03.90 (46) 07.08.92. Бюл, N 29 (71) Московский институт инженеров гражданской авиации (72) С.Ж.Кишенский, Н.С.Вдовиченко, С.В.Каменский и О.IO,Õðwcòåíêo (56) Авторское свидетельство СССР

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

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

N 1112362, кл. G 06 F 7/08, 1984. (54)УСТРОЙСТВОДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение етйосится к автоматике и вычислительной технике и может быть ис„, Ж„„1753469 А1

2 пользовано для сортировки массивов двоичных чисел. Целью изобретения является повьциение быстродействиия при сортировке по убыванию. Устройство для сортировки чисел содержит выходной регистр 6, регистр 7 сдвига. элементы 8, 9 задержки, эле- менты И 10, ИЛИ 11, НЕ 12, К-1 ячеек

1 анализа где К вЂ” число чисел в массиве.

Каждая ячейка анализа содержит регистр 2, элемент И 3, блок 4 сравнения и коммутатор

5. Быстродействие устройства повышается за счет возможности ввода нового массива до окончания сортировки предыдущего массива, 1 ил.

1753469

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

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

Наиболее близким по технической сущности к предлагаемому является устройство

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

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

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

Поставленная цель достигается тем, что

45 в устройство для сортировки чисел, содержащее К-1 ячеек анализа, где К- количество чисел в массиве, каждая ячейка анализа содержит регистр, блок сравнения и коммутатор, причем информационный вход устройства соединен с информационным входом регистра первой ячейки анализа, выход регистра каждой ячейки анализа соединен с первыми информационными входами блока сравнения и коммутатора одноименной ячейки анализа, выход коммутатора t-й ячейки анализа, i = 1,К-2, соединен с информационным входом регистра (! + 1)-й ячейки анализа, введены выходной регистр, регистр сдвига, два элемейта заыдущей ячейки анализа соединен с входом 25 держки, элемент НЕ, элемент И и элемент

ИЛИ, а в каждую ячейку анализа — элемент .

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

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

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

Устройстводля сортировки чисел содержит ячейки 11-1к,,,анализа каждая из которых содержит регистр 2, элемент И 3, блок

4 сравнения и коммутатор 5, а также выходной регистр 6, регистр 7 сдвига на К-1 выходов, первый 8 и второй 9 элементы задержки, элемент И 10, элемент ИЛИ 11 и элемент HE 12, информационный вход 13, вход 14 начала массива, тактовый вход 15, информационный вход 16 регистра сдвига, выходы 171-17к-1 регистра сдвига, информационный выход 18, Устройство работает следующим образом.

Массивы сортируемых чисел состоят из

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

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

1753469

5 6 массива устройства. Исходное состояние устройства. По задержанному тактовому всех блоков устройства произвольное. Gno- импульсу, поступающему на регистры 2 и 6 ки 4 сравнения формируют единичный сиг- в данном случае сигнал на синхравход регинал на выходах в том случае, когда код стра2 не поступает), всечислапредыдущечисла, содержащийся в.регистре одноимен- 5 го массива вновь сдвигаются по нойячейкианализа,меньше кодачисла,.по- последовательной цепочке регистров 2, в ступающего на вход 13 устройства. которых они находятся, а в регистр 2 запиКоммутатор 5 любой ячейки анализа при сывается число-второечисломассива, Перналичии на его управляющем выходе поло- вое число при этом остается в регистре 21. жительного сигнала коммутирует на выход 10 Пусть третье число больше первого, по сигнал с входа 13 устройства; при нулевом . меньше второго. В третьем такте работы управляющем сигнале — сигнал с регистра 2 устройства открыты элементы И 31 и 32 (no одноименной ячейки анализа,:. единичным значениям сигналов на выходах

При поступлении первого числа масси- 171 и 172 регистра 7). Из соотношения чисел ва сигнал начала массива, поступая на вход 15 следует, что срабатывает элемент И 31, а сброса регистра 7, удерживает его в течение элемент 32 не срабатывает, Следовательно, первого такта работы устройства в нулевом второе число записывается в регистр 2з, состоянии, вследствие чего на все элементы третье — в регистр 2z, à первое число вновь

И 3 по входам 17 поступают нулевые сигна- остается в регистре 21. Функционирование лы, и коммутаторы 5 коммутируют на выхо- 20 устройства при вводе остальных чисел масды коды одноименных регистров 2. Таким сива аналогично..По мере ввода чисел масобразом обеспечивается последовательный сива регистр 7 заполняется единицами, сдвиг рассортированных чисел предыдуще- обеспечивая сортировку заданного количего массива (в случае их наличия), Сдвиг осу- ства чисел, введенного в.данном массиве в ществляется импульсом; сформированным 25 устройство. по тактовому и задержанным на элементе 8; В том случае, когда вводимое число задержки. Максимальное число иэ регистра меньше минимального(на текущий момент) "2(К-1)-й ячейки анализа (при наличии ре- числа, содержащегося в регистре 2>, блок 4> ." - -. эультата по предыдущему массиву) записы- сравнения не формирует единичного сигна- вается в выходной регистр, по тактам 30 ла, что вызываетпоявлениеединичногосигпроизводится вывод рассортированных чи- нала на выходе элемента НЕ 12, который по сел предыдущего массива через выходной тактовому импульсу проходит через элеменрегистр. ты И 10, ИЛИ 11 на синхровход регистра 2i, Сигнал начала массива поступаеттакже обеспечивая запись данного числа (наичерез второй элемент 9 задержки и элемент 35 меньшего) в регистр 21. При этом остальные

ИЛИ 11 на синхровход регистра 2 nepsoA числа массива продвигаются по цепочке реячейки анализа и в него записывается пер- гистров 2. вое число данного массива (независимо от - В К-м такте единица достигает старшего величиныэтогочисла).Таккак все элементы разряда регистра 7, фиксируя окончание

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

При этом (во всех последующих тактах вво- число следующего массива, и посредством да данного массива) сигнал на входе 14 от- 45 обнуления регистра 7 числа данного массисутствует, тактовым импульсом в регистр 7 ва защищены от участия в сортировке сосдвига по информационному входу(подклю вместно с числами последующего массива. .ченному постоянно к положительной шине В К-м такте старшее(наибольшее по величипитания устройства) в первый разряд реги- " не) число данного массива записывается в стра 7 записывается единица, открывая эле- 50 регистр 6, через который рассортированные мейт И 31. Работа устройства во втором и числа вдальнейшемпоследовательно вывопоследующих тактах работы определяется дятся на выход устройства. взаимным расположением и величинами чи- Таким образом, предлагаемое устройстсел массива.. во позволяет осуществлять сортировку масПусть второе число массива больше 55 сивов без ожидания полного вывода всех первого. При этом с выхода блока 41 срав- чисел предыдущего массива до начала ввонения формируется положительный сигнал, да чисел следующего. при этом на каждое который. проходя через открытый элемент число для его сортирровки затрачивается

И 31, обеспечивает формирование на выхо- лишь один такт работы устройства, а то вреде коммутатора 51 сигнала с аыходоа 13 ма как нелестные устродстаа требуют либо

1753469 I

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

Редактор И.Шмакова Техред М.Моргентал Корректор М.Максимишинец

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

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

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

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

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

Устройство для сортировки чисел, содержащее элемент И, элемент НЕ, выходной регистр и К-1 узлов сравнения, где К вЂ” 15 количество чисел сортируемого массива, причем каждый узел сравнения содержит схему сравнения,-коммутатор, элемент И и регистр, выходы разрядов которого соединены с информационными входами первой 20 группы схемы сравнения и коммутатора, вы-, ход схемы сравнения соединен с первым входом элемента И, выходы коммутатора

I-ão узла сравнения. где l = 1, К-2, соединены с информационными входами регистра (i + 25

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

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