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

(51) 4 С 06 Р 7/06 ОПИСАНИЕ ИЗОБРЕТЕ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(21) (22) (46) (72) (53) 8. 8)идетельство СССР06 Р 7/06, 1983.етельство СССР06 Р 7/06, 1984.ДЛЯ РАНЖИРОВАНИЯ ЧИ я к областиможет быть еальном масшта е времени упоряд рядке возрастани ющих в "скользящ естроис ки данных расшире-. счет не и(И+1)-гося, ауется ваа регистпоступле ло исключаечисел формирпричем номеаходятся чиопределяют ьном нного ря кользяще а варит И посл г зрядных вления,аай ГОСУДАРСТ 8 ЕННЫИ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ 3853677/2405.02.8530.0187. БюВ.А.Грешнов681.325.5(056) Авторское с1109739, кл. САвторское сви1198509, кл. С54) УСТРОЙСТВО(57) Изобретение относи вычислительной техники использовано в специальньвах автоматической обрабЦелью изобретения являетние абласти применения зпрерывного формированиямасштабе времени вариациМ чисел, поступающих вокне". Устройство содерждовательно соединенных шрегистров сдвига, блок уп ш-разрядный регистр входного числа,И последовательно соединенных вспомогательных ш-разрядных регистровсдвига, элементы И управления записью и сдвигом, дешифратор управления записью. Блок управления содержит и-разрядные регистры сдвига,сумматоры параллельного действия, схемы сравнения ранга входного числа иранга исключаемого числа, дешифраторсдвига, элементы ИЛИ, дополнительныеэлементы И управления сдвигом. Устройство обеспечивает непрерывное в ние В чисел в повеличин, поступаокне", т.е. причисла первое чисиз оставшихся Н риационный ряд,ров, в которых национного ряда,этих чисел. 3 илИзобретение относится к вычисли - тельной технике и может быть использовано н специальных устройствах автоматической обработки данных,Целью изобретения является расширение области применения устройства ранжирования чисел за счет непрерывного формирования в реальном масштабе времени вариационного ряда И чисел, поступающих в скользящем окне", т,е, при поступлении (11+1)-го числа первое число исключается, а из оставшихся 11 чисел формируется вариационный РядНа фиг.1 представлена схема устройства для ранжирования чисел; на фиг,2 - схема блока управления; на фиг.3 - временная диаграмма работы устрОйства.Устройство содержит шину 1 входных чисел, выраженных тп-разрядным параллельным кодом, И последовательно соединенных п 1-разрядных регистров 2 сдвига, блок 3 управления, шразрядный регистр ч входного числа, (Б) схем 5 сравнения, блок 6 подсчета ранга входного числа, 11 элементов И 7 управления сдвигом, И последовательно соединенных вспомогательных п 1-разрядных регистров 8 сдви - га, Б элементов И 9 управления записью и дешифратор 10 управления записью, вырабатывающий сигнал логической единицы на (К+1)-м выходе, где К-ранг входного числа.Блок 3 управления содержит (К+1) тт-разрядных регистров 11 сдвига, (И - 1) сумматоров 12 параллельного действия, (Б) схем 13 сравнения ранга входного числа, (Б) схем 14 сравнения ранга исключаемого числа, дешифратор 15 сдвига, вырабатывающий сигнал логической единицы на (8+1)-м выходе, где Б - ранг исключаемого числа, (Ы) элементов ИЛИ 16 и Н до - полнительных элементов И 17 управления сдвигом.Устройство работает следующим образом.В начале работы устройства, перед поступлением первого числа, все регистры 2, 8 и 11 сдвига обнулены.Очередное ш-разрядное число, поступающее по входной шине 1, записывается в тп-разрядный регистр 4-входного числа, а также сравнивается схемами 5 сравнения с (11-1)-м упорядоченным в порядке возрастания величин1 О 15 20 25 ЗО 35 40 45 5 С 55 числом, поступившим с выходов ш в разрядных регистров 2 сдвига, с второо по 11-й. Одновременно число с выхода каждого ш-разрядного регистра 2 сдвига поступает в соответствующий вспомогательный тп в разрядн регистр 8сдвига.Если входное -и ло больше или равно числу, поступившему с выхода регистра 2, то на выходе схемы 5 сравнения формируется сигнал логическойединицы,в противном случае - сигнал логического нуля.Таким образом, входное число имеет более высокий ранг, чем равные ему ранее поступившие числа, С выходов схем 5 сравнения сигналы поступают на блок 6 подсчета ранга входного числа и элементы И 7 управления сдвигом. Так как числа, поступившие на схему 5 сравнения с регистров 2, упорядочены в порядке возрастания величин, то сигналы логической единицы поступают на элементы И 7, с первого по (К+1)-й, где К - ранг входного числа относительно сравниваемых (11-1) чисел. Синхроимпульсы сдвига поступают через элементы И 7, с первого по (К+1)-й, на первые управляющие входы соответствующих регистров 8 и осуществляют сдвиг ранее записанных данных в соседние регистры. На выходе блока б образуется число К в виде параллельного и-разрядного двоичного кода, равное количеству единиц, поступивших на входы блока 6. Количество единиц может принимать любое значение от О до (И). Значение ранга К поступает одновременно на входы блока 3 и дешифратора 10 управления записью, На (К+1)-м выходе дешифратора 10 образуется сигнал логической единицы, который поступает на первый вход соответствующего (К+1)-го элемента И 9 управления записью и открывает его. Через +1)-й элемент И 9 синхроимпульсы записи поступают на (К+1)-й тп-разрядный регистр 8 и осуществляют запись в него числа с выхода тп-разрядного регистра 4 входного числа. Затем числа из каждого пт-разрядного регистра 8 сдвига переписываются в соответстующий п 1- разрядный регистр 2 сдвига.Величина К, поступившая на вход блока 3 в виде параллельного и-разрядного двоичного кода, через первыйи-разрядный регистр 1 поступает на вторые входы всех схем 13 сравнения. Одновременно величина Б ранга числа, поступившего И тактов ранее, с выхода (И+1)-го и-разрядного регистра 11 поступает на вторые входы всех схем 14 сравнения и на вход дешифратора 15. Из и-разрядных регистров сдвига, с второго по И-й, на вторые входы соответствующих схем 13 и 4 срав нения выдаются числа, поступившие в (М)-м предыдущем такте.Схемы 13 и 14 сравнения формируют сигналы логической единицы, если число на первом входе больше или рав но числу на втором входе.При наличии логической единицы на выходе схемы 14 сравнения с выхода соответствующего сумматора 12 снимается число, большее на единицу числа, 20 поступившего на его вход.При наличии логической единицы на выходе схемы 13 сравнения значение числа, поступившего на вход соответствующего сумматора 12, увеличивается на 1+22 =2 - 1, что для и-разрядного числа эквивалентно уменьшению его значения на единицу.При наличии на выходах схем 13 и 14 сравнения одновременно нулей или 30 единиц значение числа на выходе сумматора 12 совпадает со значением числа, поданного на его выход.Таким образом, в п-разрядные регистры 11, с второго по (И+1)-й за несены значения, скорректированные в соответствии с рангом К вновь поступившего числа и рангом Б исключаемого числа.40В соответствии с величиной ранга Б исключаемого числа на (Б+1)-м выходе дешифратора 15 образуется сигнал логической единицы, который, проходя через цепочку элементов ИЛИ 1 б, 5 образует (Б+1) сигналов, которые поступают на первые входы (1Б+1) элементов И 17 и открывают их. Синхроимпульсы сдвига поступают через открытые элементы И 17 на первые уп равляющие входы соответствующих шразрядных регистров 2 и осуществляют сдвиг ранее записанных данных в соседние регистры. Таким образом, число, поступившее ранее Ю тактов, ис ключено и в ш-разрядные регистры 2, с второго по И-й, занесены упорядоченные в порядке возрастания величин оставшиеся (М) чисел . За время одного такта работы устройства происходит исключение числа, поступившего И тактов ранее, и размещение вновь поступившего числа в регистр, определяемый его рангом К относительно оставшихся (И) чисел . На каждый такт работы устройства И имеющихся чисел расположены в порядке возрастания их величин, а порядковый номер регистра, в котором расположено число, определяет ранг этого числа.На временной диаграмме работы устройства в течение одного временного такта (фиг,3) обозначены время работы схем 5 сравнения и блока подсчета ранга входного числа; времяна сдвиг данных всоседний ш-раз 82рядный регистр 8 и запись вновь пос" тупившего числа из ш-разрядного регистра 4 входного числа в соответствующий ш-разрядный регистр 8 и передачу упорядоченных чисел в соответствующие ш-разрядные регистры 2 сдвига; время Т работы блока 3 по коррекции рангов чисел и на выдачу синхроимпульсов сдвига данных в соседний ш-разрядный регистр 2 сдвига и рем С на сдвиг данных в соседний ш-разрядный регистр сдвига 2 и выдачу данных на схемы 5 сравнения и соответствующие ш-разрядные регистры 8 сдвига.Предлагаемое устройство обеспечивает непрерывное в реальном масштабе времени упорядочение М чисел в порядке возрастания их величин (формирование вариационного ряда), поступающих в "скользящем окне", т.е. при поступлении (И+1)-го числа первое число исключается, а из оставшихся И чисел формируется вариационный ряд, причем номера регистров, в которых находятся числа вариационного ряда, определяют ранги этих чисел.Формула изобретенияУстройство для ранжирования чисел, содержащее 1-1 последовательно соединенных ш-разрядных регистров сдвига, где И - число сортируемых чисел, Мсхем сравнения двух ш-разрядных чисел, блок подсчета номера ранга входного числа, М элементов И управления сдвигом, И вспомогательных последовательно соединенных ш-разрядных регистров сдвига, ш-разрядный регистр сдвига входного числа, Х элементовИ управления записью, дешифратор управления записью, блок управления, включающий дешифратор управления сдвигом, Иэлементов ИЛИ, причем первые входы всех схем сравнения соединены,с шиной входных чисел устройства и входом ш-разрядного регистра сдвига входного числа, второй вход каждой схемы сравнения соединен с информационным выходом соответствующего ш-разрядного регистра сдвига, выход каждой схемы сравнения соединен с соответствующим входом блока подсчета ранга входного числа, выходы которого соединены с входами дешифратора управления записью, выходы которого соединены с первыми входами. соответствующих элементов И управле - ния записью,вторые входы которых соединены с шиной управления записью устройства, выходы элементов И управления записью соединены с входами управления записью соответствующих вспомогательных т-разрядных регистров сдвига, информационные входы которых соединены с выходом ш-разрядного регистра сдвига входного числа, входы управления сдвигом вспомогательных регистров сдвига соединены с выходами соответствующих элементов И управления сдвигом, первые входы которых соединены с шиной сдвига устройства, 1-й выход дешифратора управления сдвигом, где (1=1,2 (Ы), соединен с первым входом -го элемента ИЛИ, второй вход 1-го элемента ИЛИ, где 1=1, 2(И - 2), подключен к выходу (1+1)-го элемента ИЛИ, 11-й выход дешифратора управления сдвигом соединен с вторым входом (Б)-го элемента ИЛИ, информационные выходы вспомогательных ш-разрядных регистров сдвига являются информационными выходами, о т л и ч аю щ е е с я тем, что, с целью расширения области применения за счет непрерывного формирования в реальном масштабе времени вариационного ряда Н чисел, поступающих в скользящем окне", в него введены т-разрядный регистр сдвига, в блок управления Ы дополнительных элементов И управления сдвигом и (И+1) и-разрядных регистров сдвига, где и - количество разрядов ранга входного числаБсумматоров параллельного действия, Бсхем сравнения ранга входного числа, Мсхем сравнения ранга исключаемого числа, причем выход до 40 45 50 55 Г 10 15 20 25 ЗО полнительного а-разрядного регистра сдвига соединен с информационным входом первого ш-разрядного регистрасдвига и с входом первого вспомогательного ш-разрядного регистра сдвига, выход которого соединен с входом дополнительного ш-.разрядного регистра сдвига, информационный вход и выход 1.-го гп-разрядного регистра сдвига соединены соответственно с выходом и информационным входом (1+1)-го вспомогательного ш-разрядного регистра сдвига, выход 1-й схемы сравнения соединен с вторым входом (1+1)-го элемента И управления сдвигом, второй вход первого элемента И управления сдвигом соединен с выходом первой схемы сравнения, выходы блока подсчета номера ранга соединены с информационными входами первого п-разрядного регистра сдвига блока управления, в блоке управления выход первого и- разрядного регистра сдвига соединен с входом второго и-разрядного регистра сдвига и первыми входами всех схем сравнения ранга входного числа, выходы (1+1)-го п-разрядного регистра сдвига соединены с первой группой входов х-го сумматора параллельного действия, выход которого соединен с входом (х+2)-го п-разрядного регистра сдвига, выход (11+1)-го и -разрядного регистра сдвига. соединен с первыми входами всех схем сравнения ранга исключаемого числа, вторые входы х-х схем сравнения ранга входного числа и ранга исключаемого числа соединены с выходом (+1)-го и-разрядного регистра сдвига, выход 1.-й схемысравнения ранга входного числа подключен к объединенным входам второйгруппы 1-го сумматора параллельногодействия, вход переноса которого соединен с выходом -й схемы сравненияранга исключаемого числа, выходы(И+1)-го и-разрядного регистра сдвига соединены с входами дешифраторасдвига, выход -го элемента ИЛИ соединен с первым входом 1-го дополнительного элемента И управления сдвигом, первый вход И-го дополнительного элемента И управления сдвигомподключен к И-му выходу дешифратора управления сдвигом, вторые входы дополнительных элементов И управлениясдвигом подключены к шине сдвига устройства, выход первого дополнительного элемента И управления сдвигом соединен с входом управления сдвигом ло 1287143полнительного п-разрядного регистрасдвига, выход (д+1)-го дополнительного элемента И управления сдвигом соединен с входом управления сдвигом д - го щ-разрядного регистра сдвига,