Устройство для ранжирования чисел

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (51) 4 С 06 F 7/06

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

t

& !

ГОСУДАРСТ8ЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К А8ТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3853677/24-24 (22) 05.02.85 (46) 30.01.87. Бюл. Ф 4 (72) В.А.Грешнов (53) 681.325.5(088.8) (56) Авторское свидетельство СССР

Р 1109739, кл. G 06 F 7/06, 1983.

Авторское свидетельство СССР

Р 1198509, кл. G 06 F .7/06, 1984. (54) УСТРОЙСТВО ДЛЯ РАНЖИРОВАНИЯ ЧИСЕЛ (57) Изобретение относится к области вычислительной техники и может быть использовано в специальных устройствах автоматической обработки данных.

Целью изобретения является расшире-.i ние абласти применения за счет непрерывного формирования в реальном масштабе времени вариационного ряда

N чисел, поступающих в "скользящем окне". Устройство содержит N последовательно соединенных m-разрядных регистров сдвига, блок управления, SU 1287143 А 1

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

1287143

5С

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

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

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

Устройство содержит шину 1 входных чисел, выраженных тп-разрядным параллельным кодом, N последовательно соединенных m ðàçðÿäíûõ регистров 2 сдвига, блок 3 управления, m разрядный регистр 4 входного числа, (N-1) схем 5 сравнения, блок 6 подсчета ранга входного числа, N элементов И 7 управления сдвигом, N последовательно соединенных вспомогательных m-разрядных регистров 8 сдви— га, N элементов И 9 управления записью и дешифратор 10 управления записью, вырабатывающий сигнал логической единицы на (R+1) ì выходе, где

R-ранг входного числа.

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

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

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

Очередное m-разрядное число, поступающее по входной шине 1, записывается в ш-разрядный регистр 4-входного числа, а также сравнивается схемами 5 сравнения с (N-1)-м упорядоченным в порядке возрастания величин числом поступившим Г BE !õодов ITI раз рядных регистров 2 сгп.ига, с второт о по 11-й. Оттновременно число с выхода каждого m-разрядного регистра 2 сдвига поступает в соответствующий вспомогательный тп †разрядн регистр 8 сдвига.

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

Таким образом, входное число имеет более высокий ранг, чем равные ему ранее поступившие числа. С выходов схем 5 сравнения сигналы поступают на блок 6 подсчета ранга входного числа и элементы И 7 управле— ния сдвигом. Так как числа, поступившие на схему 5 сравнения с регистров

2, упорядочены в порядке возрастания величин, то сигналы логической единицы поступают на элементы И 7, с первого по {R+I) é, где R — ранг входного числа относительно сравниваемых

8 и осуществляют сдвиг ранее записанньтх данных в соседние регистры.

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

Значение ранга R поступает одновременно на входы блока 3 и дешифратора

10 управления записью. На (2+1)-м выходе дешифратора 10 образуется сигнал логической единицы, который поступает на первый вход соответствующего (R+1)-ro элемента И 9 управления записью и открывает его. Через (R+1) — и элемент И 9 синхроимпульсы записи поступают на (R+1)-й m-разрядный регистр 8 и осуществляют запись в него числа с выхода m-разрядного регистра

4 входного числа. Затем числа из каждого m-разрядного регистра 8 сдвига переписываются в соответстующий mразрядный регистр 2 сдвига.

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

)287)43 п-ðàçðÿäHûé регистр ll поступает на вторые входы всех схем 13 сравнения.

Одновременно величина S ранга числа, поступившего N тактов ранее, с выхода (И+1)-ro n-разрядного регистра 11 поступает на вторые входы всех схем

14 сравнения и на вход дешифратора

15. Из и-разрядных регистров сдвига, с второго по N-й, на вторые входы соответствующих схем 13 и !4 срав- 10 нения выдаются числа, поступившие в (N-1)-м предыдущем такте.

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

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

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

При наличии на выходах схем 13 и

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

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

В соответствии с величиной ранга

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

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

На каждый такт работы устройства N имеющихся чисел расположены в порядке возрастания их величин, а порядковый номер регистра, в котором расположено число, определяет ранг этого числа.

На временной диаграмме работы устройства в течение одного временного такта (фиг.3) обозначены время работы схем 5 сравнения и блока подсчета ранга входного числа; время на сдвиг данных в соседний m-раз82 рядный регистр 8 и запись вновь пос" тупившего числа из ш-разрядного регистра 4 входного числа в соответствующий m ðàçðÿäíûé регистр 8 и передачу упорядоченных чисел в соответствующие m-разрядные регистры 2 сдвига; время t> работы блока 3 по коррекции рангов чисел и на выдачу синхроимпульсов сдвига данных в соседний m-разрядный регистр 2 сдвига и

Время t253 на сдВИГ данных В сосед

Ч ий ш-разрядный регистр сдвига 2 и выдачу данных на схемы 5 сравнения и соответствующие m-разрядные регистры 8 сдвига.

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

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

Устройство для ранжирования чисел, содержащее N-l последовательно соединенных m-ðàçðÿäíûõ регистров сдвига, где N — число сортируемых чисел, N-1 схем сравнения двух m-ðàýðÿäíbõ чисел, блок подсчета номера ранга входного числа, N элементов И управления сдвигом, N вспомогательных последовательно соединенных m-разрядных регистров сдвига, m-разрядный регистр сдвига входного числа, Х элементов

1287143

И управления записью, дешифратор управления записью, блок управления, включающий дешифратор управления сдвигом, N-1 элементов ИЛИ, причем первые входы всех схем сравнения соединены.с шиной входных чисел устройства и входом m-разрядного регистра сдвига входного числа, второй вход каждой схемь« сравнения соединен с информационным выходом соответствующего m-разрядного регистра сдвига, выход каждой схемы сравнения соединен с соответствующим входом блока подсчета ранга входного числа, выходы которого соединены с входами дешифратора управления записью, выходы которого соединены с первыми входами. соответствующих элементов И управле— ния записью, вторые входы которых соединены с шиной управления записью устройства, выходы элементов И управления записью соединены с входами управления записью соответствующих вспомогательных m ðàçðÿäíûõ регистров сдвига, информационные входы которых соединены с выходом m-разрядного регистра сдвига входного числа, входы управления сдвигом вспомогательных регистров сдвига соединены с выходами соответствующих элементов

И управления сдвигом, первые входы которых соединены с шиной сдвига устройства, i-й выход дешифратора управления сдвигом, где (i=1 2,..., (Ы-l), соединен с первым входом i-го элемента ИЛИ, второй вход j-ro элемента ИЛИ, где j=l, 2,...,(N — 2), подключен к выходу (j+1)-го элемента

ИЛИ, N-й выход дешифратора управления сдвигом соединен с вторым входом (N-l)-го элемента ИЛИ, информационные выходы вспомогательных m-разрядных регистров сдвига являются информационными выходами, о т л и ч аю щ е е с я тем, что, с целью расширения области применения за счет непрерывного формирования в реальном масштабе времени вариационного ряда

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

N дополнительных элементов И управления сдвигом и (N+l) и-разрядных регистров сдвига, где и — количество разрядов ранга входного числа,,Б-1 сумматоров параллельного действия, N-1 схем сравнения ранга входного числа, N-l схем сравнения ранга исключаемого числа, причем выход до40

55!

О

ЗО полнительного m-разряд««ого регистра сдвига соединен с информационным входом первого ш-разрядного регистра сдвига и с входом первого вспомога— тельного m-разрядного регистра сдвига, выход которого соединен с входом до««олнительного ш--разрядного регистра сдвига, инфор. 1апионный вход и выход 1.-го m — разрядного регистра сдвига соединены соответственно с выходом и информационным входом (i+1)-го вспомогательного m-разрядного регист— ра сдвига, выход i-й схемы сравнения соединен с вторым входом (i+1)-го элемента И управления сдвигом, второй вход первого элемента И управления сдвигом соединен с выходом первой схемы сравнения, выходы блока подсчета номера ранга соединены с информационными в«1 одами первого п-разрядного регистра сдвига блока управления, в блоке управления выход первого иразрядного регистра сдвига соединен с входом второго и-разрядного регистра сдвига и первыми входами всех схем сравнения ранга входного числа, выходы (i+I)-ro п-разрядного регистра сдвига соединены с первой группой входов i — ro сумматора параллельного действия, выход которого соединен с входом (i+2)-го и-разрядного регистра o ««Hr, ««b««ro (N+1)-ro n -разряд-1 ного регистра сдвига. соединен с первыми входами всех схем сравнения ранга исключаемого числа, вторые входы

i-х схем сравнения ранга входного числа и ранга исключаемого числа соединень« с выходом (+1)-го n разрядного регистра сдвига, выход i-й схемы сравнения ранга входного числа подключен к объединенным входам второй группы i ãî сумматора параллельного действия, вход переноса которого соединен с выходом -й схемы сравнения ранга исключаемого числа, выходы (N+!)-го и-разрядного регистра сдвига соединены с входами дешифратора сдвига, выход i-го элемента ИЛИ соединен с первым входом 1-го дополнительного элемента И управления сдвигом, первый вход N-го дополнительного элемента И управления сдвигом подключен к N-му выходу дешифратора управления сдвигом, вторые входы дополнительных элементов И управления сдвигом подключены к шине сдвига устройства, выход первого дополнительного элемента И управления сдвигом соединен с входом управления сдвигом ло1287143 полнительного m-разрядного регистра сдвига, выход (i+1) — го дополнительного элемента И управления сдвигом соединен с входом управления сдвигом

i — го m-разрядного регистра сдвига.

1287143

Д д . / Зыд. 2

Редактор А.Лежнина

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

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д.4/5

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

0

У

0 Такт.

4Ьа 5

Составитель Е.Иванова

Техред Л.Олейник Корректор E.Ñèðîõìàí