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

1I

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

Целью изобретения является расширение области применения устройства ранжирования чисел за счет непрерывного формирования в реальном масштабе времени вариационного ряда N чисел, поступающих в скользящем окне , т.е. при поступлении (N+l)-ro числа первое число исключается, а из оставшихся N чисел формируется вариационный ряд.

На фиг.1 представлена схема устройства для ранжирования чисел; на фиг.2 - схема блока управления; на фиг.3 - временная диаграмма работы устройства.

Устройство содержит шину 1 входных чисел, выраженных т-разрядным параллельным кодом, N последовательно соединенных т-разряДных регистров 2 сдвига, блок 3 управления, го- разрядный регистр 4 входного числа, (N-1) схем 5 сравнения, блок 6 подсчета ранга входного числа, N элементов И 7 управления сдвигом, N последовательно соединенных вспомогательных т-разрядных регистров 8 сдвига, N элементов И 9 управления записью и дешифратор 10 управления записью, вырабатывающий сигнал логической единицы на (К+1)-м выходе, где R-ранг входного числа.

Блок 3 управления содержит (N+1) п-разрядных регистров 1 сдвига, (N-1) сумматоров 12 параллельного действия, (N-1) схем 13 сравнения ранга входного числа, () схем 14 сравнения ранга исключаемого числа, дешифратор 15 сдвига, вырабатывающий сигнал логической единицы на ( выходе, где S - ранг исключаемого числа, (N-1) элементов ИЛИ 16 и N дополнительных элементов И 17 управления сдвигом.

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

В начале работы устройства, перед поступлением первого числа, все регистры 2, 8 и II сдвига обнулены.

Очередное т-разрядное число, поступающее по входной шине 1, записывается в т-разрядный регистр 4- входного числа, а также сравнивается схе нами 5 сравнения с (N-l)-M упорядоченным в порядке возрастания величин

to

15

20

25

871432

числом, поступивгаим с. выходов т-разрядных регистров 2 сднига, с втор(5го по N-й. Одновременно число с выхода каждого т-разрядного регистра 2 сдви- 5 га поступает в соответствующий вспомогательный т-разрядный регистр 8 сдвига.

Если входное число больше или равно числу, поступившему с выхода регистра 2, то на выходе схемы 5 срав- нения формируется сигнал логической единицы,в противном случае - сигнал логического нуля.

Таким образом, входное число имеет более высокий ранг, чем равные ему ранее поступивише числа. С выходов схем 5 сравнения сигналы поступают на блок 6 подсчета ранга входного числа и элементы И 7 управления сдвигом. Так как числа, поступившие на схему 5 сравнения с регистров 2, упорядочены в порядке возрастания величин, то сигналы логической единицу поступают на элементы И 7, с первого по (Е+1)-й, где R - ранг входного числа относительно сравниваемых (N-1) чисел. Синхроимпульсы сдвига поступают через элементы И 7, с первого по (К-1-1)-й, на первые управляющие входы соответствующих регистров 8 и осуществляют сдвиг ранее записанных данных в соседние регистры.

На выходе блока 6 образуется чис- 35 ло R в виде параллельного п-разрядно- го двоичного кода, равное количеству единиц, поступивших на входы блока 6. Количество единиц может принимать любое значение от О до (N-1). Значение ранга R поступает одновременно на входы блока 3 и дешифратора 10 управления записью. На (R-bl)-M выходе дешифратора 10 образуется сигнал логической единицы, который поступает на первый вход соответствующего (R+l)-ro элемента И 9 управления записью и открывает его. Через (R+l)-й элемент И 9 синхроимпульсы записи поступают на (R+l)-й tn-разрядный регистр 8 и осуществляют запись в него числа с выхода го-разрядного регистра 4 входного числа. Затем числа из каждого т-разрядного регистра 8 сдвига переписываются в соответстуюп1ий го- разрядный регистр 2 сдвига.

Величина R, поступившая на вход блока 3 в виде параллельного п-раз- рядного двоичного кода, через первый

30

40

45

5С

31

n-разрядный регистр 11 поступает на вторые входы всех схем 13 сравнения. Одновременно величина S ранга числа, поступившего N тактов ранее, с выхода (N+l)-ro п-разрядного регистра II поступает на вторые входы всех схем 14 сравнения и на вход дешифратора 15. Из п-разрядных регистров сдвига, с второго по N-Й, на вторые входы соответствующих схем 13 и 14 срав- нения выдаются числа, поступившие в (N-l)-M предыдущем такте.

Схемы 13 и 14 сравнения формируют сигналы логической единицы, если число на первом входе больше или рав но числу на втором входе.

При наличии логической единицы на выходе схемы 14 сравнения с выхода соответствующего сумматора 12 снимается число, большее на единицу числа поступившего на его вход.

При наличии логической единицы на выходе схемы 13 сравнения значение числа, поступившего на вход соответствующего сумматора 12, увеличивает- ся на 1+2+...+2 2 -, что для п-разрядного числа эквивалентно уменьшению его значения на единицу.

При наличии на выходах схем 13 и 14 сравнения одновременно нулей или единиц значение числа на выходе сумматора 12 совпадает со значением числа, поданного на его выход.

Таким образом, в п-разрядные регистры 11, с второго по (К+)-й за- несены значения, скорректированные в соответствии -с рангом R вновь поступившего числа и рангом S исключаемого числа.

В соответствии с величиной ранга S исключаемого числа на (5+1)-м выходе дешифратора 15 образуется сигна логической единицы, который, проходя через цепочку элементов ИЛИ 16, образует (S+I) сигналов, которые поступают на первые входы (1,...,S+1) элементов И 17 и открывают их. Синхроимпульсы сдвига поступают через открытые элементы И 17 на первые уп- равляющие входы соответствующих го- разрядных регистров 2 и осуществляют сдвиг ранее записанных данных в соседние регистры. Таким образом, число, поступившее ранее N тактов, не- ключено и в т-разрядные регистры 2, с второго по N-й, занесены упорядо- ченные в порядке возрастания величин оставшиеся (N-1) чисел.

1434

За время одного такта работы устройства происходит исключение числа, поступившего N тактов ранее, и размещение вновь поступившего числа в регистр, определяемый его рангом R относительно оставшихся (N-1) чисел. На каждый такт работы устройства N имеющихся чисел расположены в порядк возрастания их величин, а порядковый номер регистра, в котором расположено число, определяет ранг этого числа.

На временной диаграмме работы устройства в течение одного временного

такта (фиг.З) обозначены время t,

ь ь

работы схем 5 сравнения и блока 6 подсчета ранга входного числа; время

to- на сдвиг данных в соседний ш-раз- о

рядный регистр о и запись вновь поступившего числа из т-разрядного регистра 4 входного числа в соответствующий т-разрядный регистр 8 и передачу упорядоченных чисел в соответствующие т-разрядные регистры 2 сдвига; Время t. работы блока 3 по коррекции рангов чисел и на вьщачу синхроимпульсов сдвига данных в соседний т-разрядный регистр 2 сдвига и время tj5 на сдвиг данных в сосед- 91ИЙ т-разрядный регистр сдвига 2 и выдачу данных на схемы 5 сравнения и соответствующие т-разрядные регистры 8 сдвига.

Предлагаемое устройство обеспечивает непрерывное в реальном масштабе времени упорядочение N чисел в порядке возрастания их величин (формирование вариационного ряда), поступающих в скользящем окне, т.е. при поступлении (N+)-ro числа первое число исключается, а из оставшихся N чисел формируется вариационный ряд, причем номера регистров, в которых находятся числа вариационного ряда, определяют ранги этих чисел.

Формула изобретения

Устройство для ранжирования чисел, содержащее N-1 последовательно соединенных т-разрядньгх регистров сдвига, где N - число сортируемых чисел, N-1 схем сравнения двух т-разрядньгх чисел, блок подсчета номера ранга входного числа, N элементов И управления сдвигом, N вспомогательных последовательно соединенных га-разрядных регистров сдвига, т-разрядный регистр сдвига входного числа, N элементов

И управления записью, дешифратор управления записью, блок управления, включающий дешифратор управления сдвигом, N-1 элементов ИЛИ, причем первые входы всех схем сравнения сое динены.с шиной входных чисел устройства и входом т-разрядного регистра сдвига входного числа, второй вход каждой схемы сравнения соединен с информационным выходом соответствующе- го т-разрядного регистра сдвига, выход каждой схемы сравнения соединен с соответствующим входом блока подсчета ранга входного числа, выходь которого соединены с входами дещифра тора управления записью, выходы которого соединены с первыми входами. соответств::,тощих элементов И управления записью, вторые входы которых соединены с шиной управления записью устройства, выходы элементов И управления записью соединены с входами управления записью соответствующих вспомогательных т-разрядных регистров сдвига, информационные входы которых соединены с выходом т-разрядного регистра сдвига входного числа, входы управления сдвигом вспомогательных, регистров сдвига соединены с выходами соответствующих элементов И управления сдвигом, первые входы которых соединены с шиной сдвига устройства, i-й выход дешифратора управления сдвигом, где (,2,..., (N-I), соединен с первым входом i-ro элемента ИЛИ, второй вход j-ro- элемента ИЛИ, где , 2,...,(N-2), подключен к выходу .(j + l)ro элемента ИЛИ, N-Й выход депшфратора управления сдвигом соединен с вторым входом (N-)-ro элемента ИЛИ, информационные выходы вспомогательных т-разрядных регистров сдвига являются информационными выходами, отличающееся тем, что, с целью рас- ширения области применения за счет непрерывного формирования в реальном масштабе времени вариационного ряда N чисел, поступающих в скользящем окне, в него введены т-разрядный ре- гистр сдвига, в блок управления - N дополнительных элементов И управления сдвигом и (N+1) п-разрядных регистров сдвига, где п - количество разрядов ранга входного числа, .N-1 сумматоров параллельного действия, N-1 схем сравнения ранга входного числа, N-1 схем сравнения ранга исключаемого числа, причем выход до

5

0 5 0 35 40 45 50 55

30

полнительного ш-разрядиого регистра сдвига соединен с информационным входом первого т-разрядного регистра сдвига и с входом первого вспомогательного т-разрядного регистра сдвига, выход которого соединен с входом дополнительного т-разрядного регистра сдвига, информационный вход и выход i-ro ш-разрлдного регистра сдвига соединены соответственно с выходом и информационным входом (i+)-ro вспомогательного т-разрядного регистра сдвига, выход i-й схемы сравнения соединен с вторым входом (i+l)-ro элемента И управления сдвигом, второй вход первого элемента И управления сдвигом соединен с выходом первой схемы сравнения, выходы блока подсчета номера ранга соединены с информационными родами первого п-разрядно- го регистр а сдвига блока управления, в блоке управления выход первого п- разрядного регистра сдвига соединен с входом второго п-разрядного регистра сдвига и первыми входами всех схем сравнения ранга входного числа, выходы ()-ro п-разрядного регистра сдвига соединены с первой группой входов 1-го сумматора параллельного действия, выход которого соединен с входом (i+2)-ro п-разрядного регистра сдвига, выход (N+l)-ro п-разряд-i ного регистра сдвига.соединен с первыми входами всех схем сравнения ранга исключаемого числа, вторые входы i-x схем сравнения ранга входного числа и ранга исключаемого числа соединены с выходом (i-(-l)-ro п-разрядного регистра сдвига, выход i-й схемы сравнения ранга входного числа подключен к объединенным входам второй группы i-ro сумматора параллельного действия, вход переноса которого соединен с выходом i-й схемы сравнения ранга исключаемого числа, выходы (N- -)-ro п-разрядного регистра сдвига соединены с входами дешифратора сдвига, выход i-ro элемента ИЛИ соединен с первым входом i-ro дополнительного элемента И управления сдвигом, первый вход N-ro дополнительного элемента И управления сдвигом подключен к N-му выходу дешифратора управления сдвигом, вторые входы дополнительных элементов И управления сдвигом подключены к шине сдвига устройства, выход первого дополнительного элемента И управления сдвигом соединен с входом управления сдвигом до 1287 из8

полнительного m-разряяного регистра динен с входом управления сдвигом сдвига, выход (i+l)-ro дополнительно- i-ro m-разрядного регистра сдви- го элемента И управления сдвигом сое- га.

ZV./

Заказ 7718/52 Тираж 69ДПодписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб,, д.4/5

Производственно-полиграфическое предприятие,г.Ужгород,ул.Проектная,4

Изобретение относится к области вычислительной техники и может быть использовано в специальных устройствах автоматической обработки данных. Целью изобретения является расшире- i ние области применения за счет непрерывного формирования в реальном масштабе времени вариационного ряда N чисел, поступающих в скользящем окне. Устройство содержит N последовательно соединенных т-разрядных регистров сдвига, блок управленияj m-разрядный регистр входного числа, N последовательно соединенных вспомогательных т-разрядных регистров сдвига, элементы И управления записью и сдвигом, дешифратор управления записью. Блок управления содержит п-разрядные регистры сдвига,сумматоры параллельного действия, схемы сравнения ранга входного числа и ранга исключаемого числа, дешифратор сдвига, элементы ИЛИ, дополнительные элементы И управления сдвигом. Устройство обеспечивает непрерывное в реальном масштабе времени упорядочение N чисел в порядке возрастания их величин, поступающих в скользящем окне, т.е. при поступлении (N+l)-ro числа первое число исключается, а из оставшихся N чисел формируется вариационный ряд, причем номера регистров, в которых находятся числа вариационного ряда, определяют ранги этих чисел. 3 ил. (Л to с СА9