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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 730618 А 19) (1 7 0 51)5 ИТЕТКРЫТИЯМ ГОСУДАР СТВЕ ННЫ И КПО ИЗОБРЕТЕНИЯМ ИПРИ ГКНТ СССР П ИСАН И Е И ЗС) БР ЕТЕ Н ИАВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) Авторское свидетельство СССРМ 1112362, кл. 6 06 Р 7/08, 1983.Авторское свидетельство СССРМ 1654811, кл. 6 06 Е 7/08, 1988.(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ(57) Изобретение относится к вычислительной технике и может быть использовано вспециализированных устройствах обработки информации, предназначенных для сортировки массива данного в скользящей выборке, Цель изобретения - повышение быстродействия. Устройство содержит М ячеек анализа (ЯА) 1,1.-1.Й - апертура скользящей выборки, М буферных регистров 2, элемент 3 задержки, информационный вход 4, тактовый вход 5, выходы отсортированных чисел 6,1 - 6.И ЯА. 1 содержит блоки сравнения, регистры, преобразователь кода, коммутатор, К К-му такту в регистрах расположены в порядке возрастания М последних поступивших по входу 4 чисел. На Е-ом такте происходит удаление числа к, поступившего на (М+1)-ом такте, и упорядочение по возрастанию оставшихся чисел и нового,только что поступившего числа у. 2 ил.Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки информации, предназначенных для сортировки массива данных в скользящей выборке,Цель изобретения - повышение быстродействия,На фиг, 1 приведена схема устройства; на фиг, 2 - схема ячейки анализа.Устройство содержит К ячеек анализа 1,1 - 1.М, где М - апертура скользящей выборки, М буферных регистров 2, элемент 3 задержки, информационный вход 4, тактовый вход 5, выходы отсортированных чисел 6,1-6.М. Ячейка анализа 1 содержит блоки 7 и 8 сравнения, регистры 9 и 10, преобразователь 11 кода, коммутатор 12.К Е-му такту в регистрах 10 расположены в порядке возрастания й последних поступивших по входу 4 чисел. На К-ом такте происходит удаление числа г, поступившего на (К-И+1)-ом такте, и упорядочение по возрастанию оставшихся чисел и нового, только что поступившего числа у.Устройство работает следующим образом,Текущая апертура Л, длины М и предшествующая апертура Л ,отличаются друг от друга двумя элемента г и у, Предположим, что в(К)-ом такте работы мы имеем упорядоченную в порядке возрастания последовательность (а),= 1, М значений элементов апертуры Л , - 1. Очевидно, для того, чтобы получить в К-ом такте работы упорядоченную в пооядке возрастания последовательность (а ) значений элементов апертуры Ь к, необходимо удалить значения элементаиз последовательности (а) и скорректировать ее и ввести в скорректированную последовательность соответствующим образом значение элемента у.Для того, чтобы удалить значение г из последовательности (а), необходимо найти крайний правый элемент а ц, равный г, его удалить, а все элементы, расположенные слева, сдвинуть на одну позицию вправо, а в первый элемент записать О, т.е, реализовать следующую операцию:аь 1, если а ;а =а;еслиа; ;га,=0,= 1,й,В результате выполнения операции (1)получаем упорядоченную в порядке возра стания последовательность (а) значений,апертуры Ь , 1 без значения элемента л.Затем необходимо ввести соответству ющим образом в последовательность (а) значение элемента у. Для этого необходимо(найти крайний правый элемент а Р последовательности(а;), который небольше значения у, и этот элемент и все элементы, расположенные от него слева, сдвинуть влево на одну позицию, а на место элемента /ар записать значение у, т,е, реализовать выполнение операции 15а =а, если ау;а+1, если а;+1 у;у - в противном случаеъ,(2); ам+1 = М,где М - максимально возможное значениеотсчетов сигнала.В результате последовательного выполнения операций (1) и (2) получим значенияэлементов упорядоченной в порядке возрастания последовательности (а ) значений,элементов текущей апертуры ЛПрименив суперпозицию выражений (2)и ,1) и учитывая, что аь 1а;, получаем 30аь 1, если аау; а;,еслиа; г а у; а = а, если а+1 г а; у; а+1, если а+1г а+1у у, в противном случае;(3) 35 а 0 = О, а +1 = М.Таким образом, выражение (3) описывает закон рекуррентного формирования элементов упорядоченной последовательности значений элементов текущей апертуры Ь, на основе полученной на предыдущем этапе упорядоченной последовательности значений элементов предшествующей 45 апертурь1Число у поступает в ячейки анализа свхода 4, число г - с выхода К-го буферного регистра. Блоки 7 и 8 сравнения -й ячейки анализа 1сравнивают число а и г и а и у, 50 результаты сравненияи у с аи с а+1поступают от смежных ячеек 1- 1 и 1,+1, Преобразователь 11 кода вырабатывает управляющие сигналы для коммутатора 12, который обеспечивает запись в регистр 9 55 одного из значений а, аь а+1, у в соответствии с выражением (3).Для повышения надежности и исключения сбоев при переходных процессах тактовым сигналом, задержанным элементом 3 задержки, происходит перезапись инфор1730618 50 55 мации из регистров 9 в регистры 10, Тем жесигналом происходит сдвиг чисел, храня- .щихся в буферных регистрах 2. Формула изобретения 5 Устройство для сортировки чисел, содержащее Й последовательно соединенных буферных регистров и М ячеек анализа, где К - апертура скользящей выборки, каждая ячейка анализа содержит два регистра, пер вый блок сравнения и коммутатор, причем в каждой ячейке анализа первые информационные входы и выходы первого регистра соединены с входами соответственно первой и второй групп первого блока сравнения 15 и с информационными входами соответственно первой и второй групп коммутатора, выход первого регистра )-й ячейки анализа, где ) = 2, 3, М, соединены с информационными входами третьей группы коммутато ра 0-1)-й ячейки анализа, выходы первого регистра -й ячейки анализа ( = 1, 2, .й) являются выходами -го отсортировочного числа скользящей выборки устройства, выходы й-го буферного регистра соединены с 25 информационными входами второй группы первой ячейки анализа, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия, в него введен. элемент задержки, а в каждую ячейку анализа - преобразователь 30 кода и второй блок сравнения, причем в каждой ячейке анализа выходы первого и второго блоков сравнения соединены соответственно с первым и вторым входами и реобразователя кода, выходы которого 35 соединены с управляющими входами коммутатора, выходы которого соединены с информационными входами второго регистра, выходы которого соединены с информаци 40 онными входами первого регистра, выходы которого соединены с входами первой группы второго блока сравнения, входы второй группы которого являются информационными входами второй группы данной ячейки анализа, выходы первого регистра Д)-й ячейки анализа соединены с информационными входами четвертой группы коммутатора )-й ячейки анализа, информационные входы устройства соединены с первыми информационными входами всех ячеек анализа и с информационными входами первого буферного регистра, выходы й-го буферного регистра соединены с вторыми информационными входами )-й ячейки анализа, выходы первого и второго блоков сравнения )-й ячейки анализа соединены соответственно с третьим и четвертым входами преобразователя кода 0-1)-й ячейки анализа, выход первого блока сравнения Ц)-й ячейки анализа соединен с пятым входом преобразователя кода )-й ячейки анализа, информационные входы четвертой группы коммутатора первой ячейки анализа и информационные входы третьей группы коммутатора Й-й ячейки анализа соединены с входами соответственно минимального и максимального чисел устройства, пятый вход преобразователя кода первой ячейки анализа подключен к входу логического нуля устройства, третий и четвертый входы преобразователя кода М-й ячейки анализа подключены к входу логической единицы устройства, тактовый вход устройства соединен с тактовыми входами вторых регистров всех ячеек анализа и через элемент задержки - с тактовыми входами первых регистров всех ячеек анализа и с тактовыми входами всех буферных регистров,1730618Составитель В.Горохов Редактор Н,Швыдкая Техред М,Моргентал Корректор Н.Ревск Заказ 1512 Тираж Подписное ВНИИХИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., 4/5Производственно-издательский комбинат "Патент", г, Ужгород, ул,Гагарина, 1