Устройство для сортировки чисел Советский патент 1992 года по МПК G06F7/08 

VI CJ О

о

00

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

Цель изобретения - повышение быстродействия.

На фиг. 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)-OM такте, и упорядочение по возрастанию оставшихся чисел и нового, только что поступившего числа у.

Устройство работает следующим образом.

Текущая апертура Л длины N и предшествующая апертура Д k - 1 отличаются

друг от друга двумя элемента z и у. Предположим, что в (k-1)-OM такте работы мы имеем упорядоченную в порядке возрастания последовательность {ai}, i 1 ,N значений элементов апертуры Дk- 1- Очевидно, для того, чтобы получить в k-ом такте работы упорядоченную в порядке возрастания последовательность {а } значений элементов апертуры Д , необходимо удалить значения элемента z из последовательности {ai} и скорректировать ее и ввести в скорректированную последовательность соответствующим образом значение элемента у.

Для того, чтобы удалить значение z из последовательности {ai}, необходимо найти крайний правый элемент асе, равный z, его удалить, а все элементы, расположенные слева, сдвинуть на одну позицию вправо, а в первый элемент записать 0, т.е. реализо- вать следующую операцию:

а

аи, если ai z; а если а: z; а0 0, i 1,N.

В результате выполнения операции (1) получаем упорядоченную в порядке возрастания последовательность {ai} значений апертуры Д | 1 без значения элемента z.

Затем необходимо ввести соответствующим образом в последовательность {ai1} значение элемента у. Для этого необходимо

найти крайний правый элемент а К последовательности {ai}, который небблыие значения у, и этот элемент и все элементы, расположенные от него слева, сдвинуть влево на одну позицию, а на место элемента

aft записать значение у, т.е. реализовать выполнение операции

aj1, если ai у;

ан-ч1, если ан-1 у;

у - в противном случае

(2);

3N+1 М,

где М - максимально возможное значение отсчетов сигнала.

В результате последовательного выполнения операций (1) и (2) получим значения элементов упорядоченной в порядке возрастания последовательности {ai } значений элементов текущей апертуры А.

Применив суперпозицию выражений (2) и (1) и учитывая, что аи а, получаем

I

аи, если а гл аи у; ai, если а z л а; у;

ai ai, если ai-м z as у; (3) I ан-1, если ai+1 z л ai+i у y, в противном случае;

а0 0, аы+1 М.

Таким образом, выражение (3) описывает закон рекуррентного формирования элементов упорядоченной последовательности значений элементов текущей апертуры Ak на основе полученной на предыдущем этапе упорядоченной последовательности значений элементов предшествующей апертуры А 1.

Число у поступает в ячейки анализа с входа 4, число z - с выхода N-ro буферного регистра. Блоки 7 и 8 сравнения i-й ячейки анализа 1.1 сравнивают число ai и z и ai и у, результаты сравнения z и у с аи и с ai+i поступают от смежных ячеек 1.1-1 и 1,1+1, Преобразователь 11 кода вырабатывает управляющие сигналы для коммутатора 12, который обеспечивав запись в регистр 9 одного из значений аи, ai, ai+1, у в соответствии с выражением (3).

Для повышения надежности и исключения сбоев при переходных процессах тактовым сигналом, задержанным элементом 3 задержки, происходит перезапись информации из регистров 9 в регистры 10. Тем же сигналом происходит сдвиг чисел, хранящихся в буферных регистрах 2.

Формула изобретения Устройство для сортировки чисел, содержащее N последовательно соединенных буферных регистров и N ячеек анализа, где N - апертура скользящей выборки, каждая ячейка анализа содержит два регистра, первый блок сравнения и коммутатор, причем в каждой ячейке анализа первые информационные входы и выходы первого регистра соединены с входами соответственно первой и второй групп первого блока сравнения и с информационными входами соответственно первой и второй групп коммутатора, выход первого регистра j-й ячейки анализа, где j 2, 3 N, соединены с информационными входами третьей группы коммутатора 0-1)-й ячейки анализа, выходы первого регистра i-й ячейки анализа (1 1,2, ..., N) являются выходами i-ro отсортировочного числа скользящей выборки устройства, выходы N-ro буферного регистра соединены с информационными входами второй группы первой ячейки анализа, отличающее- с я тем, что, с целью повышения быстродействия, в него введен элемент задержки, а в каждую ячейку анализа - преобразователь кода и второй блок сравнения, причем в каждой ячейке анализа выходы первого и второго блоков сравнения соединены соответственно с первым и вторым входами преобразователя кода, выходы которого соединены с управляющими входами коммутатора, выходы которого соединены с информационными входами второго регистра, выходы которого соединены с информаци0

5

0

5

0

5

0

онными входами первого регистра, выходы которого соединены с входами первой группы второго блока сравнения, входы второй группы которого являются информационными входами второй группы данной ячейки анализа, выходы первого регистра 0-1)-й ячейки анализа соединены с информационными входами четвертой группы коммутатора j-й ячейки анализа, информационные входы устройства соединены с первыми информационными входами всех ячеек анализа и с информационными входами первого буферного регистра, выходы N-ro буферного регистра соединены с вторыми информационными входами j-й ячейки анализа, выходы первого и второго блоков сравнения j-й ячейки анализа соединены соответственно с третьим и четвертым входами преобразователя кода 0-1)-й ячейки анализа, выход первого блока сравнения (-1)-й ячейки анализа соединен с пятым входом преобразователя кода j-й ячейки анализа, информационные входы четвертой группы коммутатора первой ячейки анализа и информационные входы третьей группы коммутатора N-й ячейки анализа соединены с входами соответственно минимального и максимального чисел устройства, пятый вход преобразователя кода первой ячейки анализа подключен к входу логического нуля устройства, третий и четвертый входы преобразователя кода N-й ячейки анализа подключены к входу логической единицы устройства, тактовый вход устройства соединен с тактовыми входами вторых регистров всех ячеек анализа и через элемент задержки - с тактовыми входами первых регистров всех ячеек анализа и с тактовыми входами всех буферных регистров,

Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки информации, предназначенных для сортировки массива данного в скользящей выборке. Цель изобретения - повышение быстродействия. Устройство содержит 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 ил. (Л С