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

(51)5 0 06 Г 7/08 Я ПИСАНИЕ ИЗОБРЕ К АВТО ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИПРИ ГКНТ СССР МУ СВИДЕТЕЛЬСТВУ 1(71) Московский институт инженеров гражданской авиации(56) Авторское свидетельство СССР М 1007099, кл. О 06 Г 7/08, 1981.Авторское свидетельство СССРВ 1397900, кл. 6 06 Р 7/08, 1988. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИ- СЕЛ(57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для сортировки массивов двоичных чисел и является усовершенствованием устройства по авт.св. М 1397900, Целью изобретения является увеличение быстродействия при сортировке массивов определенной размерности, Устройство для сортировки чисел содержит ячейки 1 анализа, элементы ИЛИ-НЕ 2, элементы И 3, триггеры 4, группы элементов И 5, группу элементов ИЛИ 6 и блок 7 управления. Устройство позволяет повысить быстродействие при сортировке чисел за счет обеспечения вывода массивов чисел. через всю совокупность ячеек анализа. 3 ил.Изобретение относится к автоматике и вычислительной технике и может быть использовано для сортировки массивов двоичных чисел.По основному авт.св. В 1397900 известно основное изобретения - устройство для сортировки чисел, содержащее а ячеек анализа (где гп - количество чисел в массиве), причем каждая ячейка содержит приемный регистр, блок сравнения, регистр результата и коммутатор, информационный вход устройства соединен с информационным входом регистра первой ячейки анализа, выход приемного регистра каждой ячейки анализа соединен с информационным входом регистра результата и первыми информационными входами коммутатора и блока сравнения одноименной ячейки анализа, выход регистра результата соединен с вторым одноименным информационным входом блока сравнения, выход которого соединен с управляющим входом коммутатора и первым входом разрешения записи регистра результата той же ячейки анализа, выход коммутатора соединен с информационным входом приемного регистра следующей ячейки анализа, выход коммутатора последней ячейки анализа является выходом устройства,Недостатком прототипа является низкое быстродействие.Цель изобретения - увеличение быстродействия при сортировке массивов определенной размерности.Поставленная цель достигается тем, что в устройство для сортировки чисел введены (1+1) элементов ИЛИ-НЕ (где 1 - размерность массива чисел). (1+1) элементов И, (1+1) триггеров, (1+1)групп элементов И, группа элементов ИЛИ и блок управления, причем для четного гп значение К = гп/2, для нечетного а значение К =(щ)/2, входы 1-го элемента ИЛИ-НЕ (1=1,К) соединены соответственно с выходами блоков сравнения ячеек анализа с (аК+)-й по (п-К+1)-ю, выход -го элемента ИЛИ-НЕ соединен с первым входом -го элемента И, второй вход которого подключен к прямому выходу второго триггера (т-К+1)-й ячейки анализа, выход )-го элемента И= 11+1) соединен с входом установки в единичное состояние )-го триггера, прямой выход которого соединен с первыми входами элементов И )-й группы, вторые входы элементов И которой соединены с выходами коммутаторов (а-)-й ячейки анализа, выходы одноименных элементов И группы соединены с входами соответствующих элементов ИЛИ группы, выходы которых являются информационными выходами устройства, выходы1015 20304045 50 55 Первое число массива записывается в регистр 261, а триггер 231 устанавливается в единичное состояние, Единичный сигнал, поступающий на управляющий вход блока 281 сравнения безусловно предопределяет перезапись в следующем такте числа из регистра 271 через коммутатор 251 в регистр 262, а из регистра 26 - в регистр 271 независимо от соотношения чисел регистрах 261 и 271. На этом (втором) такте единица из триггера 231 переписывается в триггер 241 элементов И соединены с информационными входами блока управления, тактовыйвход блока управления соединен с тактовым входом устройства, первый выход блока управления соединен с входами установки в нулевое состояние триггеров, второй выход блока управления соединен с третьими входами элементов И.На фиг,1 приведена структурная схемаустройства для сортировки чисел; на фиг.2 -структурная схема блока управления; на фиг,3 - структурная схема ячейки анализа.Устройство для сортировки чисел содержит ячейки 11 - 1 анализа, элементы ИЛИНЕ 21 - 2+, элементы И 3 - 3+, триггеры 41-4 к+1 группы элементов И 51-5+1, группу элементов ИЛИ 6, блок 7 управления, тактовый вход 8, информационный вход 9, вход 10 начала массива, выходы 11 и 12, причем выход 12 информации каждой ячейки анализа соединен с информационным входом 9 следующей ячейки анализа. Управляющие выходы 3 ячеек анализа,с(гпК+ )-й по (т-К 1+)-ю соединены с входами -го элемента ИЛИ-НЕ. Элементы 3 имеют выходы 14, элементы ИЛИ группы 6 - выходы 15, являющиеся выходами устройства. Первый 16 ивторой 17 выходы блока управления соединены соответственно с входами сброса триггеров и с третьими входами элементов И,Блок 7 управления состоит из триггера 18, элемента И 19, счетчика 20, дешифратора 21 и элемента ИЛИ 22,Каждая ячейка 1 анализа содержит первый 23 и второй 24 триггеры, коммутатор 25, приемный регистр 26, регистр 27 результатаи блок 28 сравненияУстройство работает следующим образом,На вход 9 устройства последовательнопоступают числа сортиру."ого массива, содержащего т чисел, подлежащих сортировке. В результате сортировки числа выдаются на выход устройства начиная с максимального. Числа поступают одновременно с тактовыми импульсами на вход 8, а первое число сопровождается сигналом "1" на входе 10,и в регистр 261 поступает второе число массива,В третьем такте происходит сравнение чисел, находящихся в регистрах 261 и 271 (соответственно второго и первого числа массива), Большее из этих чисел переписывается в регистр 262 через коммутатор 251, при этом число из регистра 262 переписывается безусловно в регистр 272, так как в третьем такте единица переписывается из триггера 241 в триггер 232, а меньшее число остается в регистре 27 (или переписывается в него из регистра 261), При этом в третьем такте в регистр 261 записывается третье число массива.Таким образом, большие по значению числа продвигаются по ячейкам анализа, не перезаписываясь в регистры 27, поэтому они опережают меньшие числа.После загрузки последнего числа данного массива на следующем такте может быть загружено первое число следующего массива, не дожидаясь окончания сортировки чисел предыдущего массива; единицы, сопровождающие начала массивов предотвращает перемешивание чисел между массивами,В самом неблагоприятном случае сортировка заканчивается после прохождения числами массива всех ячеек анализа. Однако во многих случаях сортировка может за кончиться ран ьш е. П ри этом в и редлагаемом устройстве выдача информации (рассортированных чисел) может осуществляться сразу после окончания сортировки, не дожидаясь вывода чисел из последней ячейки анализа.Пусть в - четное число, В этом случае,при загрузке в устройство последнего числамассива, все т чисел содержатся в к=в/2ячейках анализа - по два в каждой ячейке. Крометого, единица, сопровождающая первый элемент массива, находится в триггере 24 К-й ячейки анализа, В наилучшем случае уже в этот момент числа рассортированы. Совокупность блоков 2 - 7 позволяет вывести числа массива из устройства сразу же после окончания их сортировки.Начальное состояние триггера 18 - нулевое, счетчика 20 - также нулевое (соответствующие цепи начальной установки на чертежах не показаны).Окончание сортировки основано на следующем принципе; наличие положительного сигнала на выходе блока сравнениянекоторой ячейки анализа означает, что в данной ячейке анализа происходит пересортировка (смена места) двух соответствующих чисел массива, Если в некотором такте на выходах всех блоков анализа - ну левые сигналы, это означает что, сортировка чисел в массиве закончена,В элементах ИЛИ-НЕ 2 анализируются сигналы с блоков сравнения ячеек анализа, причем на соответствующем элементе 2 - совокупность значений сигналов с блоков сравнения к смежных ячеек анализа. Учитывая, что анализируются все совокупности со сдвигом на одну ячейку анализа, таких совокупностей (и соответственно элементов 2) должно быть (1+1). Если все сигналы некоторой совокупности имеют нулевое значение, с выхода соответствующего элемента 2 формируется положительный сигнал, свидетельствующий об окончании сортировки данного массива. 5 10 15 20 25 30 35 50 Для обеспечения анализа лишь ячеек, в которых содержатся элементы данного массива, используются сигналы 12 - выходные сигналы триггеров 24 ячеек анализа 1. Соответствующий триггер 24 обеспечивает срабатывание (при окончании сортировки) того элемента И 3, который соответствует началу отсортированного массива чисел. Так как к = гп/2, в устройстве могут размещаться лишь два массива чисел. Использование выходных сигналовоттриггеровс(а-к)-го по гп-й обеспечивает анализ полностью взеденного массива чисел,В момент окончания сортировки сигнал с соответствующего элемента ИЛИ-НЕ 2, совпадая с сигналом с триггера 24, в котором содержится единица, сопровождающего первое число массива, и с сигналом триггера 18 блока управления устанавливают соответствующий триггер 4 в единичное состояние. Кроме того, этим же сигналом устанавливается в единичное состояние триггер 18 блока 7 управления. Сигнал с триггера 4 разрешает прохождение первого числа массива через соответствующую группу элементов И 5 и элементы ИЛИ 6 на выход устройства,Триггер 18, устанавливаясь в единичное состояние, запрещает срабатывание элементов И 3 до окончания вывода чисел данного массива, Поположительному сигналу с прямого выхода триггера 18 открывается элемент И 19, на счетчик 20 через него начинают поступать тактовые импульсы, Счетчик 20 совместно с дешифратором 21 настроены на число пт - количество чисел в каждом массиве, После вывода последнего, гп-го числа массива, сигнал с выхода дешифратора 21 сбрасывает триггер 18 и счетчик 20 в исходное, нулевое, состояние, а также устанавливает в нулевое состояние тот триггер 4, который разрешил вывод массива из некоторой ячейки анализа,1741127 30 Если к данному моменту времени числа следующего массива уже отсортированы, то сразу срабатывает соответствующий элемент И и начинается вывод из соответствующей ячейки чисел следующего массива. В противном случае вывод следующего массива начинается после его окончательной сортировки.При нечетном в и 1=-(в)/2, устройство работает аналогично описанному,Таким образом, предлагаемое устройство позволяет повысить быстродействие при сортировке чисел за счет обеспечения вывода массивов чисел сразу же после окончания их сортировки, не дожидаясь прохождения массива через всю совокупность ячеек анализа,Формула изобретения Устройство для сортировки чисел по авт.св, М 1397900, о т л и ч а ю щ е е с я тем, что, с целью увеличения быстродействия при сортировке массивов определенной размерности, в него введены (1+1) элементов ИЛИ-НЕ, (К - размерность массива чисел), (1+1) элементов И, (к+1) триггеров, (1+1) групп элементов И, группу элементов ИЛИ и блок управления, причем для четного гп значение к = в/2, для нечетного пз значение К =(в)/2, входы 1-го элемента ИЛИ-НЕ (1=1к) соединены соответственно с выходами блоков сравнения ячеек анализа с (гп 21+1)-й по (а-М+ )-ю, выход 1-го элементаИЛИ-НЕ соединен с первым входом 1-го элемента И, второй вход которого подключен к прямому выходу второго триггера (а-М+ )-й ячейки анализа, выход )-го эле мента И =11+1) соединен с входом установки в единичное состояние )-го триггера, прямой выход которого соединен с первыми входами элементов И )-й группы, вторые входы элементов И которой соединены с 15 выходами коммутаторов (щ)-й ячейкианализа, выходы одноименных элементов И групп соединены с выходами соответствующих элементов ИЛИ группы, выходы которых являются информационными вы ходами устройства, выходы элементов Исоединены с информационными входами блока управления, тактовый вход блока управления соединен с тактовым входом устройства, первый выход блока управ ления соединен с входами установки внулевое состояние триггеров, второй выход блока управления соединен с третьими входами элементов И.1741127 Редактор орректор А, Осауленко оизводственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 1 Составитель С, Кишенскийолинская Техред М.Моргентал аказ 2085 Тираж ПВНИИПИ Государственного комитета по изобретениям113035, Москва, Ж, Раушская на исноеоткрытиям при ГКНТ ССС4/5