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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 17 9) 05 6 06 Г 7/08 Т в граж 1 ченко, ИСЕЛ ике и ть исГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРК А ВТОР С КОМУ С В ИДЕТЕЛ ЬСТВУ(71) Московский институт инженероданской авиации(56) Авторское свидетельство СССРМ 1397900, кл. С 06 Г 7/08, 1988,Авторское свидетельство СССРМ 1112362, кл. 0 06 Г 7/08, 1984.(57) Изобретениеетйосится к автомвычислительной технике и может б пользовано для сортировки массивов двоичных чисел. Целью изобретения является повьциение быстродействиия при сортировке по убыванию. Устройство для сортировки чисел содержит выходной регистр 6, регистр 7 сдвига, элементы 8, 9 задержки, эле-менты И 10, ИЛИ 11, НЕ 12, Кячеек 1 анализагде К - число чисел в массиве.Каждая ячейка анализа содержит регистр 2, элемент И 3, блок 4 сравнения и коммутатор 5. Быстродействие устройства повышается за счет возможности ввода нового массива до окончания сортировки предыдущего массива, 1 ил.ФИзобретение относится к автоматике и вычислительной технике и может быть использовано при сортировке массивов двоичных чисел,Известно устройство для сортировки чисел, содержащее К ячеек анализа,"каждая из которых содержит приемный регистр, блок сравнения, коммутатор и регистр результата, тактовые входы всех ячеек анали 10 эа обьединены, выход регистра результата предыдущей ячейки анализа соединен с входом коммутатора последующей ячейки анализаНедостатками этого устройства являются низкое быстродейс вие, узкая область применения и высокая .ложность конструкции.Наиболее близким по технической сущности к предлагаемому является устройство 15 20 для сортировки чисел содержащее К ячеек анализа, где К- количество чисел в массиве, каждая ячейка анализа содержит приемный регистр, блок сравнения, регистр результата и коммутатор, выход коммутатора предприемного регистра последующей ячейкианализа, тактовый вход устройства соединен с синхровходами всех приемных регистров ячеек анализа. Недостатком известного устройства является узкая область применения, так как оно не позволяет осуществлять сортировку чисел последующего массива до полного вывода чисел предыдущего массива, а так 30 же затрачивает на сортировку большое чис 35 ло тактов " по два такта на каждое число массива (с учетом требуемого вывода чиселпредыдущего массива до ввода и сортировки чисел последующего массива),Целью изобретения является расширение области применения устройства за счет обеспечения сортировки следующего массива чисел до окончания вывода предыдущего массива.Поставленная цель достигается тем, что 45 в устройство для сортировки чисел, содержащее Кячеек анализа, где К- количество чисел в массиве, каждая ячейка анализа содержит регистр, блок сравнения и коммутатор, причем информационный вход устройства соединен с информационным входом регистра первой ячейки анализа, выход регистра каждой ячейки анализа соединен с первыми информационными входами блока сравнения и коммутатора одноименной ячейки анализа, выход коммутатора 1-й ячейки анализа,= 1,К, соединен с информационным входом регистра ( + 1)-й ячейки анализа, введены выходной регистр, регистр сдвига, два элемента заыдущей ячейки анализа соединен с входом 25 держки, элемент НЕ, элемент И и элемент ИЛИ, а в каждую ячейку анализа - элемент И, причем тактовый вход устройства соединен с синхровходом регистра сдвига и через первый элемент задержки с синхровходами регистров всех ячеек анализа, кроме первой, и с синхровходом выходного регистра, вход начала массива соединен с входом сброса регистра сдвига и через второй эле. мент задержки с первым входом элемента ИЛИ, выход которого соединен с синхровходом регистра первой ячейки анализа, выход блока сравнения первой ячейки анализа через элемент НЕ соединен с первым входом элемента И, к второму входу которого подключен выход первого элемента задержки, выход элемента И соединен е вторым входом элемента ИЛИ, информационный вход устройства соединен с вторыми информационными входами блоков сравнения и коммутаторов всех ячеек анализа, вйход коммутатора (К)-й ячейки анализа соединен с информационным входом выходного регистра, выход которого является выходом устройства, информационный вход регистра сдвига подключен к положительной шине устройства, выходы (К)-разрядного регистра сдвигасоедийены с первыми входами элементов И одноименных ячеек анализа, (К)-й выход регистра сдвига является выходом окончания сортировки массива устройства, в каждой ячейке анализа выход блока сравнения соединен с вторым входом элемента И, выход которого подключен к управляющему входу коммутатора одноименной ячейки анализа.На чертеже представлена структурная схема устройства для сортировки чисел.Устройстводля сортировки чисел содержит ячейки 11-1, анализа каждая из которых содержит регистр 2, элемент И 3, блок 4 сравнения и коммутатор 5, а также выходной регистр 6, регистр 7 сдвига на Квыходов, первый 8 и второй 9 элементы задержки, элемент И 10, элемент ИЛИ 11 и элемент НЕ 12, информационный вход 13, вход 14 начала массива, тактовый вход 15, информационный вход 16 регистра сдвига, выходы 171-17 крегистра сдвига, инфор мационный выход 18,Устройство работает следующим образом,Массивы сортируемых чисел состоят из К чисел каждый, которые поступают на вход 13 устройства последовательно, одно за другим, в произвольном порядке. Каждое число сопровождается импульсом на тактовом входе 15 устройства, Первое число каждого массива сопровождается также сигналом логической "1" на входе 14 начала17534695 6массива устройства. Исходное состояние устройства. По задержанному тактовомувсех блоков устройства произвольное. Бло- импульсупоступающему на регистры 2 и 6ки 4 сравнения формируют единичный сиг- в данном случае сигнал на синхравход регинал на выходах в том случае, когда код стра 21 не поступает), все числа предыдущечисла, содержащийся в.регистре одноимен го массива вновь сдвигаются понойячейкианализа,меньше кодачисла,.по- последовательной цепочке регистров 2, вступающего на вход 13 устройства. которых они находятся, а в регистр 22 запиКоммутатор 5 любой ячейки анализа при сывается число-второечисломассива, Перналичии на его управляющем выходе поло- вое число при этом остается в регистре 21.жительного сигнала коммутирует на выход 10 Пусть третье число больше первого, посигнал с входа 13 устройства; при нулевом . меньше второго, В третьем такте работыуправляющем сигнале - сигнал с регистра 2 устройства открыты элементы И 31 и 32 (поодноименной ячейки анализа, . единичным значениям сигналов на выходахПри поступлении первого числа масси и 172 регистра 7). Из соотношения чиселва сигнал начала массива, поступая на вход 15 следует, что срабатывает элемент И 31, асброса регистра 7, удерживает его в течение элемент 32 не срабатывает, Следовательно,первого такта работы устройства в нулевом второе число записывается в регистр 2 з,состоянии, вследствие чего на все элементы третье - в регистр 22, а первое число вновьИ 3 по входам 17 поступают нулевые сигна- остается в регистре 21. Функционированиелы, и коммутаторы 5 коммутируют на выхо устройства при вводеостальных чисел масды коды одноименных регистров 2, Таким сива аналогичноПо мере ввода чисел масобразом обеспечивается последовательный сива регистр 7 заполняется единицами,сдвиг рассортированных чисел предыдуще- обеспечивая сортировку заданного количего массива (в случае их наличия), Сдвиг осу- ства чисел, введенного в.данном массиве вществляется импульсом; сформированным 25 устройство.по тактовому и задержанным на элементе 8; В том случае, когда вводимое числозадержки, Максимальное число иэ регистра меньше минимального(на текущий момент) "2(К)-й ячейки анализа (при наличии ре- числа, содержащегося в регистре 21, блок 41,.эультата по предыдущему массиву) записы- сравнения не формирует единичного сигна-вается в выходной регистр, по тактам 30 ла,чтовызываетпоявлениеединичногосигпроизводится вывод рассортированных чи- нала на выходе элемента НЕ 12, который посел предыдущего массива через выходной тактовому импульсу проходит через элеменрегистр. ты И 10, ИЛИ 11 на синхровход регистра 21.Сигнал начала массива поступаеттакже обеспечивая запись данного числа (наичерез второй элемент 9 задержки и элемент 35 меньшего) в регистр 21. При этом остальныеИЛИ 11 на синхровход регистра 2 первой числа массива продвигаются по цепочке реячейки анализа и в него записывается пер- гистров 2,вое число данного массива (независимо от В К-м такте единица достигает старшеговеличиныэтогочисла),Таккаквсеэлементы разряда регистра 7, фиксируя окончаниеИ закрыты, первое число не может эапи сортировкиданногомассива; в этом такте всаться больше ни в один из регистров 2. устройство вводится последнее число и заВо втором такте работы устройства на канчивается сортировка. В следующем таквход 13 поступает второе число массива, те в устройство может поступить первоеПри этом (во всех последующих тактах вво- число следующего массива, и посредствомда данного массива) сигнал на входе 14 от обнуления регистра 7 числа данного массисутствует, тактовым импульсом в регистр 7 ва защищены от участия в сортировке сосдвига по информационному входу(подклю вместно с числами последующего массива,.ченному постоянно к положительной шине В К-м такте старшее(наибольшее по величипитания устройства) в первый разряд реги- " не) число данного массива записывается встра 7 записывается единица, открывая эле регистр 6, через который рассортированныемейт И 31. Работа устройства во втором и числа вдальнейшемгпоследовательно вывопоследующих тактах работы определяется дятся на выход устройства.взаимным расположением и величинами чи-Таким образом, предлагаемое устройстсел массива., во позволяет осуществлять сортировку масПусть второе число массива больше 55 сивов без ожидания полного вывода всехпервого. При этом с выхода блока 41 срав- чисел предыдущего массива до начала ввонения формируется положительный сигнал, да чисел следующего, при этом на каждоекоторый, проходя через открытый элемент число для его сортирровки затрачиваетсяИ 31, обеспечивает формирование на выхо- лишь один такт работы устройства, а то вреде коммутатора бг сигнала с аыходоа тб ма как нелестные устродстаа требуют либо1753469 ФСоставитель С.КишенскийРедактор И.Шмакова Техред М.Моргентал Корректор М.Максимишинец Заказ 2768 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5 Прслзводственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина 101 не менее двух тактов на каждое число массива, либо не позволяют вводить и сортировать числа последующего массива до полного вывода рассортированных чисел предыдущего массива. Указанные свойства 5 предлагаемого устройства позволяют расширить область его применения, включая в нее системы с непрерывным следованием массивов сортируемых чисел и высокими требованиями по оперативности сортиров ки.Формула изобретенияУстройство для сортировки чисел, содержащее элемент И, элемент НЕ, выходной регистр и Кузлов сравнения, где К - 15 количество чисел сортируемого массива, причем каждый узел сравнения содержит схему сравнения, коммутатор, элемент И и регистр, выходы разрядов которого соединены с информационными входами первой 20 группы схемы сравнения и коммутатора, вы-, ход схемы сравнения соединен с первым . входом элемента И, выходы коммутатора 1-го узла сравнения, где= 1, К, соединены с информационными входами регистра ( + 25 1)-го узла сравнения, информационные входы второй группы схем сравнения и коммутаторов всех узлов сравнения обьединены и соединены с соответствующими входами регистра первого узла сравнения, выходы 30 коммутатора (К)-го узла сравнения соединены с информационными входами выходного регистра, выходы которого являются информационными выходами устройства, выход Элемента НЕ соединен с первым входом элемента И, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия при сортировке чисел по убыванию, в него введены регистр сдвига, элемент ИЛИ и два элемента задержки, причем вход тактовых импульсов устройства соединен с синхровходом регистра сдвига и через первый элемент задержки с вторым входом элемента И, а также с входами управления записью выходного регистра и регистров всех узлов сравнения, кроме первого, вход начала массива устройства соединен с входом сброса регистра сдвига и через второй элемент задержки с первым входом элемента ИЛИ, второй вход и выход которого подключены соответственно к выходу элемента И и входу управления записью регйстра первого узла сравнения, выход схемы сравнения первого узла сравнения соединен с входом элемента НЕ, информационныевходы устройства соединены с информационными входами регистра первого узла сравнения, выходы регистра сдвига соединены с вторыми входамй элементов И одноименных узлов сравнения, информационный вход регистра сдвига соединен с входом логической единицы устройства, в каждом узле сравнения выход элемента И соединен с управляющим входом коммутатора,