Устройство для сортировки чисел
Патент 1730618
Авторы
Классы МПК
Устройство для сортировки чисел
Иллюстрации
Реферат
Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки информации, предназначенных для сортировки массива данного в скользящей выборке . Цель изобретения - повышение быстродействия. Устройство содержит N ячеек анализа (ЯА) 1.1.-1.N - апертура скользящей выборки, N буферных регистров 2, элемент 3 задержки, информационный вход 4, тактовый вход 5, выходы отсортированных чисел 6.1-6.N ЯА. 1 содержит блоки сравнения , регистры, преобразователь кода, коммутатор . К k-му такту в регистрах расположены в порядке возрастания N последних поступивших по входу 4 чисел. На k-ом такте происходит удаление числа z, поступившего на (k-N+1)-oM такте, и упорядочение по возрастанию оставшихся чисел и нового, только что поступившего числа у. 2 ил. (Л С
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (51)5 G 06 F 7/08
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ 4 (лЭ
О
0 с
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (2:1) 4740379/24 (22) 25.09.89 (46) 30.04;92. Бюл. 1Ф 16 (71) Научно-исследовательский институт телевизионной техники "Электрон" (72) С.А.Елманов (53) 681.325.5(088.8) (56) Авторское свидетельство СССР
N -1112362,,кл. 6 06 F 7/08, 1983.
Авторское свидетельство СССР
М 1654811, кл. G 06 F 7/08, 1988. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработ. Ж» 1730618 Al ки информации, предназначенных для сортировки массива данного в скользящей выборке. Цель изобретения — повышение быстродействия. Устройство содержит N ячеек анализа (ЯА) 1.1.-1.N — апертура скользящей -выборки, N буферных регистров 2, элемент 3 задержки, информационный вход
4, тактовый вход 5, выходы отсортированных чисел 6.1 — 6.N ЯА. 1 содержит блоки сравнения, регистры, преобразователь кода, коммутатор, К k-му такту в регистрах расположены в порядке возрастания N последних поступивших по входу 4 чисел. На k-ом такте происходит удаление числа z, поступившего на (&+1)-ом такте, и упорядочение rio возрастанию оставшихся чисел и нового, только что поступившего числа у. 2 ил.
1730618
Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки информации, предназначенных для сортировки массива данных в скользящей выборке, Цель изобретения — повышение быстродействия, На фиг. 1 приведена схема устройства; на фиг, 2 — схема ячейки анализа.
Устройство содержит N ячеек анализа
1,1 — 1.N, где N — апертура скользящей выборки, N буферных регистров 2, элемент 3 задержки, информационный вход 4, тактовый вход 5, выходы отсортированных чисел
6,1-6.N. Ячейка анализа 1 содержит блоки 7 и 8 сравнения, регистры 9 и 10, преобразователь 11 кода, коммутатор 12.
К k-му такту в регистрах 10 расположены в порядке возрастания N последних поступивших по входу 4 чисел. На k-ом такте и роисходит удаление числа z, поступившего на (k-N+1)-ом такте, и упорядочение по возрастанию оставшихся чисел и нового, только что поступившего числа у.
Устройство работает следующим образом, Текущая апертура Л длины N и предшествующая апертура Л 1 отличаются друг от друга двумя элемента z и у, Предположим, что в (k-1)-ом такте работы мы имеем упорядоченную в порядке возрастания последовательность (ai), i = 1, N значений элементов апертуры Л вЂ” 1. Очевидно, для того, чтобы получить в k-ом такте работы упорядоченную в порядке возрастания последовательность (а ) значений элементов апертуры Л к, необходимо удалить значения элемента z из последовательности (ai) и скорректировать ее и ввести в скорректированную последовательность соответствующим образом значение элемента у.
Для того, чтобы удалить значение z из последовательности (ai), необходимо найти крайний правый элемент а ц, равный z, его удалить, а все элементы, расположенные слева, сдвинуть на одну позицию вправо, а в первый элемент записать О, т.е. реализовать следующую операцию: а-1, если а z, а = а;; если а >z; а =O,i= I,N, В результате выполнения операции (1) получаем упорядоченную в порядке возрастания последовательность (а ) значений .! апертуры Л 1 без значения элемента z.
Затем необходимо ввести соответству1 ющим образом в последовательность (а ) значение элемента у. Для этого необходимо
I найти крайний правый элемент аP последовательности(а;), который небольше значения у, и этот элемент и все элементы, расположенные от него слева, сдвинуть влево на одну позицию, а на место элемента
I аР записать значение у, т,е, реализовать выполнение операции
И
aI =
1 I а, если а; > ;
ai+1 если ai+1 у;
I ( у — в противном случае (2); ам+1 = М, где М вЂ” максимально возможное значение отсчетов сигнала.
B результате последовательного выполнения операций (1) и (2) получим значения элементов упорядоченной в порядке возрастания последовательности (а ) значений, II элементов текущей апертуры Л .
Применив суперпозицию выражений (2) и (1) и учитывая, что à-1 а;, получаем
30 а -1, если ai Sz аИ > у; а,еслиа; >г а >у;
aIИ = аь если ai+1 z а+1 у „у, в противном случае; (3) 35
ao=0, aN+1= М.
Таким образом, выражение (3) описывает закон рекуррентного формирования эле40 ментов упорядоченной последовательности значений элементов текущей апертуры
Л на основе полученной на предыдущем этапе упорядоченной последовательности значений элементов предшествующей
45 апертуры h, — 1 °
Число у поступает в ячейки анализа с входа 4, число z — с выхода N-го буферного регистра. Блоки 7 и 8 сравнения i-й ячейки анализа 1л сравнивают число ai u z u ai и у, 50 результаты сравнения z и у с аь1 и с а+1 поступают от смежных ячеек 1л — 1 и 1,i+1.
Преобразователь 11 кода вырабатывает управляющие сигналы для коммутатора 12, который обеспечивает запись в регистр 9
55 одного из значений аь1, à, ai+1, у в соответствии с выражением (3).
Для повышения надежности и исключения сбоев при переходных процессах тактовым сигналом, задержанным элементом 3 задержки, происходит перезапись инфор1730618
55 мации из регистров 9 в регистры 0. Тем же сигналом происходит сдвиг чисел, храня- . щихся в буферных регистрах 2.
Формула изобретения 5
Устройство для сортировки чисел, содержащее N последовательно соединенных буферных регистров и N ячеек анализа, где
N — апертура скользящей выборки, каждая ячейка анализа содержит два регистра, пер- 10 вый блок сравнения и коммутатор, причем в каждой ячейке анализа первые информационные входы и выходы первого регистра соединены с входами соответственно первой и второй групп первого блока сравнения 15 и с информационными входами соответственно первой и второй групп коммутатора, выход первого регистра j-й ячейки анализа, где ) = 2, 3, „., N, соединены с информационными входами третьей группы коммутато- 20 ра (j-1)-й ячейки анализа, выходы первого регистра i-й ячейки анализа (i = 1, 2, ..., N) являются выходами i-го отсортировочного числа скользящей выборки устройства, выходы N-ro буферного регистра соединены с 25 информационными входами второй группы первой ячейки анализа, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия, в него введен. элемент задержки, а в каждую ячейку анализа — преобразователь 30 кода и второй блок сравнения, причем в каждой ячейке анализа выходы первого и второго блоков сравнения соединены соответственно с первым и вторым входами и реобразователя кода, выходы которого 35 соединены с управляющими входами коммутатора, выходы которого соединены с информационными входами второго регистра, выходы которого соединены с информаци40 онными входами первого регистра, выходы которого соединены с входами первой группы второго блока сравнения, входы второй группы которого являются информационными входами второй группы данной ячейки анализа, выходы первого регистра (j-1)-й ячейки анализа соединены с информационными входами четвертой группы коммутатора j-й ячейки анализа, информационные входы устройства соединены с первыми информационными входами всех ячеек анализа и с информационными входами первого буферного регистра, выходы N-го буферного регистра соединены с вторыми информационными входами j-й ячейки анализа, выходы первого и второго блоков сравнения
j-й ячейки анализа соединены соответственно с третьим и четвертым входами преобразователя кода (j-1)-й ячейки анализа, выход первого блока сравнения (j-1)-й ячейки анализа соединен с пятым входом преобразователя кода j-й ячейки анализа, информационные входы четвертой группы коммутатора первой ячейки анализа и информационные входы третьей группы коммутатора N-й ячейки анализа соединены с входами соответственно минимального и максимального чисел устройства, пятый вход преобразователя кода первой ячейки анализа подключен к входу логического нуля устройства, третий и четвертый входы преобразователя кода N-й ячейки анализа подключены к входу логической единицы устройства, тактовый вход устройства соединен с тактовыми входами вторых регистров всех ячеек анализа и через элемент задержки — с тактовыми входами первых регистров всех ячеек анализа и с тактовыми входами всех буферных регистров, 1730618
ÔÃ/8. 2
Составитель 8.Горохов
Редактор Н.Швыдкая Техред M,Ìoðãåíòàë Корректор Н.Ревская
Заказ 1512 Тираж Подписное
BHNVlPVI Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж-35, Раушская наб., 4/5
Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101