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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано для сортировки массивов двоичных чисел и является усовершенствованием устройства по авт.св. № 1397900. Целью изобретения является увеличение быстродействия при сортировке массивов определенной размерности. Устройство для сортировки чисел содержит ячейки 1 анализа , элементы ИЛИ-НЕ 2, элементы И 3, триггеры 4, группы элементов И 5, группу элементов ИЛИ 6 и блок 7 управления. Устройство позволяет повысить быстродействие при сортировке чисел за счет обеспечения вывода массивов чисел через всю совокупность ячеек анализа. 3 ил.

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

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

РЕСПУБЛИК

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) 1397900 (21) 4807361/24 (22) 28,03.90 (46) 15,06.92, Бюл. М 22 (71) Московский институт инженеров гражданской авиации (72) С.Ж.Кишенский, Н.С.Вдовиченко, А.Я,Крекер и О.Ю.Христенко (53) 681.325 (088.8) (56) Авторское свидетельство СССР

N 1007099, кл. G 06 F 7/08, 1981.

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

% 1397900, кл. G 06 F 7/08, 1988. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ

Ы2,, 1741127 А2 (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для сортировки массивов двоичных чисел и является усовершенствованием устройства по авт.св. М 1397900, Целью изобретения является увеличение быстродействия при сортировке массивов определенной размерности. Устройство для сортировки чисел содержит ячейки 1 анализа, элементы ИЛИ-НЕ 2, элементы И 3, триггеры 4, группы элементов И 5, группу элементов ИЛИ 6 и блок 7 управления.

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

1741127

25

40

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

По основному авт.св. t4 1397900 известно основное изобретения — устройство для сортировки чисел, содержащее m ячеек анализа (где m — количество чисел в массиве), причем каждая ячейка содержит приемный регистр, блок сравнения, регистр результата и коммутатор, информационный вход устройства соединен с информационным входом регистра первой ячейки анализа, выход приемного регистра каждой ячейки анализа соединен с информационным входом регистра результата и первыми информационными входами коммутатора и блока сравнения одноименной ячейки анализа, выход регистра результата соединен с вторым одноименным информационным входом блока сравнения, выход которого соединен с управляющим входом коммутатора и первым входом разрешения записи регистра результата той же ячейки анализа, выход коммутатора соединен с информационным входом приемного регистра следующей ячейки анализа, выход коммутатора последней ячейки анализа является выходом устройства.

Недостатком прототипа является низкое быстродействие.

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

Поставленная цель достигается тем, что в устройство для сортировки чисел введены (k+1) элементов ИЛИ-HE (где k — размерность массива чисел). (k+1) элементов И, (k+1) триггеров, (1+1)групп элементов И, группа элементов ИЛИ и блок управления, причем для четного m значение k = m/2, для нечетного m значение k =(m-1)/2, входы 1-го элемента ИЛИ-НЕ (i=1,...k) соединены соответственно с выходами блоков сравнения ячеек анализа с (m-2k+i)-й no (m-k-1+i)-ю, выход i-го элемента ИЛИ-НЕ соединен с первым входом i-го элемента И, второй вход которого подключен к прямому выходу второго триггера (m-k-1+i)-й ячейки анализа, выход j-го элемента И (j = 1„„k+1) соединен с входом установки в единичное состояние

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

На фиг,1 приведена структурная схема устройства для сортировки чисел; на фиг.2— структурная схема блока управления; на фиг,3 — структурная схема ячейки анализа.

Устройство для сортировки чисел содержит ячейки 1 — 1 анализа, элементы ИЛИНЕ 21 — 2 +, элементы И 31 — 3 +1, триггеры

4> — 4к+ группы элементов И 5 — 5 +, группу элементов ИЛИ 6, блок 7 управления, тактовый вход 8, информационный вход 9, вход

10 начала массива, выходы 11 и 12, причем выход 12 информации каждой ячейки анализа соединен с информационным входом 9 следующей ячейки анализа. Управляющие выходы I 3 ячеек анализа,с (m-2k+ i)-й по (m-k1+i)-ю соединены с входами i-ro элемента

ИЛИ-НЕ. Элементы 3 имеют выходы 14, элементы ИЛИ группы 6 — выходы 15, являющиеся выходами устройства. Первый 16 и второй 17 выходы блока управления соединены соответственно с входами сброса триггеров и с третьими входами элементов И, Блок 7 управления состоит из триггера

18, элемента И 19, счетчика 20, дешифратора 21 и элемента ИЛ И 22, Каждая ячейка 1 анализа содержит первый 23 и второй 24 триггеры, коммутатор 25, приемный регистр 26, регистр 27 результата и блок 28 сравнения, Устройство работает следующим образом, На вход 9 устройства последовательно поступают числа сортиру ." ого массива, содержащего m чисел, подлежащих сортировке. B результате сортировки числа выдаются на выход устройства начиная с максимального. Числа поступают одновременно с тактовыми импульсами на вход 8, а первое число сопровождается сигналом "1" на входе 10, Первое число массива записывается в регистр 26>, а триггер 23> устанавливается в единичное состояние. Единичный сигнал, поступающий на управляющий вход блока

281 сравнения безусловно предопределяет перезапись в следующем такте числа из регистра 271 через коммутатор 251 в регистр

26, а из регистра 26> — в регистр 271 независимо от соотношения чисел регистрах

26> и 271. На этом (втором) такте единица из триггера 23> переписывается в триггер 24

1741127

55 и в регистр 261 поступает второе число массива, В третьем такте происходит сравнение чисел, находящихся в регистрах 261 и 271 (соответственно второго и первого числа массива), Большее из этих чисел переписывается в регистр 26г через коммутатор 251, при этом число из регистра 262 переписывается безусловно в регистр 272, так как в третьем такте единица переписывается из триггера 241 в триггер 232, а меньшее число остается в регистре 27> (или переписывается в него из регистра 26 ), При этом в третьем такте в регистр 261 записывается третье число массива.

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

После загрузки последнего числа данного массива на следующем такте может быть загружено первое число следующего массива, не дожидаясь окончания сортировки чисел предыдущего массива; единицы, сопровождающие начала массивов предотвращает перемешивание чисел между массивами, В самом неблагоприятном случае сортировка заканчивается после прохождения числами массива всех ячеек анализа. Однако во многих случаях сортировка может за кончиться ран ьш е. П ри этом в и редлагаемом устройстве выдача информации (рассортированных чисел) может осуществляться сразу после окончания сортировки, не дожидаясь вывода чисел из последней ячейки анализа.

Пусть m — четное число, В этом случае, при загрузке в устройство последнего числа массива, все m чисел содержатся в k=m/2 ячейках анализа — по два в каждой ячейке.

Крометого, единица, сопровождающая первый элемент массива, находится в триггере

24 k-й ячейки анализа, В наилучшем случае уже в этот момент числа рассортированы.

Совокупность блоков 2 — 7 позволяет вывести числа массива из устройства сразу же после окончания их сортировки.

Начальное состояние триггера 18 — нулевое, счетчика 20 — также нулевое (соответствующие цепи начальной установки на чертежах не показаны).

Окончание сортировки основано на следующем принципе; наличие положительного сигнала на выходе блока сравнения некоторой ячейки анализа означает, что в данной ячейке анализа происходит пересортировка (смена места) двух соответствующих чисел массива, Если в некотором такте на выходах всех блоков анализа — ну5

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

Для обеспечения анализа лишь ячеек, в которых содержатся элементы данного массива, используются сигналы 12 — выходные сигналы триггеров 24 ячеек анализа 1. Соответствующий триггер 24 обеспечивает срабатывание (при окончании сортировки) того элемента И 3, который соответствует началу отсортированного массива чисел. Так как k = m/2, в устройстве могут размещаться лишь два массива чисел. Использование выходных сигналов от триггеров с {m-k)-ro no

m-й обеспечивает анализ полностью взеденного массива чисел.

B момент окончания сортировки сигнал с соответствующего элемента ИЛИ-НЕ ", совпадая с сигналом с триггера 24, в котором содержится единица, сопровождающего первое число массива, и с сигналом триггера 18 блока управления устанавливают соответствующий триггер 4 в единичное состояние. Кроме того, этим же сигналом устанавливается в единичное состояние триггер 18 блока 7 управления. Сигнал с триггера 4 разрешает прохождение первого числа массива через соответствующую групry элементов И 5 и элементы ИЛИ 6 на выход устройства.

Триггер 18, устанавливаясь в единичное состояние, запрещает срабатывание элементов И 3 до окончания вывода чисел данного массива, По положительному сигналу с прямого выхода триггера 18 открывается элемент И 19, на счетчик 20 через него начинают поступать тактовые импульсы.

Счетчик 20 совместно с дешифратором 21 настроены на число m — количество чисел в каждом массиве, После вывода последнего, m-го числа массива, сигнал с выхода дешифратора 21 сбрасывает триггер 18 и счетчик

20 в исходное, нулевое, состояние, а также устанавливает в нулевое состояние тот триггер 4, который разрешил вывод массива из некоторой ячейки анализа, 1741127

55

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

При нечетном m и k=-(m-1)/2, устройство работает аналогично описанному, Таким образом, предлагаемое устройство позволяет повысить быстродействие при сортировке чисел за счет обеспечения вывода массивов чисел сразу же после окончания их сортировки, не дожидаясь прохождения массива через всю совокупность ячеек анализа.

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

Устройство для сортировки чисел по авт.св. М 1397900, о т л и ч а ю щ е е с я тем, что, с целью увеличения быстродействия при сортировке массивов определенной размерности, в него введены (k+1) элементов ИЛИ-НЕ, (k — размерность массива чисел), (k+1) элементов И, (k+1) триггеров, (k+1) групп элементов И, группу элементов ИЛИ и блок управления, причем для четного

m значение k = m/2, для нечетного m значение k =(m-1)/2, входы i-ro элемента ИЛИ-НЕ (i=1,...,k) соединены соответственно с выходами блоков сравнения ячеек анализа c (m5 2k+1)-й по (m-k-1+ i)-ю, выход i-ro элемента

ИЛИ-НЕ соединен с первым входом 1-го элемента И, второй вход которого подключен к прямому выходу второго триггера (m-k-1+ ij-й ячейки анализа, выход j-го эле10 мента И (j=1,...,k+1) соединен с входом установки в единичное состояние J-го триггера, прямой выход которого соединен с первыми входами элементов И j-й группы, вторые входы элементов И которой соединены с

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

1741127

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

Редактор Л. Пчолинская Техред M.Ìîðãåíòàë Корректор А. Осауленко

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

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101