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

I

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

Известно устройство для поиска экстремальных значений, решающее задачу определения ранга числа, содержащее регистры, группу элементов И, генератор, триггеры, счетчик, дешифратор, группу элементов .НЕ,. блок регистрации экстремального значения, блок регистрации рашкированного ряда параметров, блоки определения ранга параметраJ разрядные коммутаторы pj

Недостатком известного устройства являются больиме- аппаратные- затраты.

Наиболее близким к предлагаемому по технической сущности является устройство для ранжирования чисел, содержащее регистр сдвига для хранения чисел буферный регистр для хранения эталонного числа из з.аданной последовательности чисел, схему сравнения устройства подсчета, номера ран га, элементы Р, ИЛИ, блок управления блок синхронизации, с.четчик .циклов сравнения, числа величин, блок определения конда цикла -сравне шя и блок индика1щи результата, при чем шина ввода данных соединена с первым входом первого элемента {ШИ, выход которого соединен с входом регистра сдвига, выход которого соединен с первым входом схемы сравнения, с вторым входом первой схемы IUM и с Первым входом первого элемента И, выход которой подключен к первому входу второго элемента или, соединенной выходом с входом, буферного регистра выход которого подключен к первым входам схемы сравнения и второго элемента ИЛИ, первый выход схемы сравнения подключен к первому входу второго элемента И, выход-которого соединен с входом устройства подсчета нойера ранга и с первым БХодом третьего элемента ЩН, выход Которого подключен к устройству подсчр.та номера коллективног-о ранга, першый выход блока управле шя соединей с управляющим входом регистра сдвига и первыми входами третьего я четвертого элементов И, вторые вхо дь которых подключены соотзетственно к первому и второму выходам блока синхронизации, выход третьего элемен.га Н подключен к второму входу перво.гр.элемента И и управляющим входам

32I

устройств подсчета номера ранга, выход четвертого элемента И соединен с вторыми входами второго и пятого элементов И, второй вход которого соединен с вторым выходом схемы сравнения ; а выход с вторым входом третьего элемента ИЛИ, второй выход блока упразле:ш-1я подключен к первым входам шестого, седьмого, восьмого и девятого элемен-тов И, вторые входы которых соединен. соответственно с выходами буферного регистра,, счетчика числа циклов сравнения и устройств подсчета номера ранга, а выходы - с входами блока ин щкации, третий выход блока управления соединен с управляющем входом счетчика циклов сравне1дая, четвертый выход блока управтгения подключен к входу бло.ка синхронизации, первый вход блока управления соединен с шиной начала работы и счет1а1Я входом с.четчика 111ИКЛОВ сравнения J информационный выход которого соединен с первым входом блока определения конца цикла сравнения, второй- вход котороТо под,ключен к информационному выходу счетчика числа величин, вход которого соединен с загшси номера ч;исла,5 выход блока определения конца цикла соединен с вторым входом блока управления 2j

У-стройство служит ,цля определения раигг; числа, - принятого за зтэлоннь.й из последовательности -.нсел за N ци:клов, Для определения рангов, всех чисел последовательности потребуется N - тактов

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

Поставленная цель достигается тем, что в устройстве для ранжирования 41-J с ел, содержащее регистр сдвига, схему, сравнения ,, блок , подсчета номера ранга, причем выход регистра сдви га соединен с первым входом схемы сравнения, регистр сдвига выполнен т-разрядным5 где m - количество разрядов сортируемых чисел, в устройство введены () регистров сдвига, где N - число сортируемых чисел:, (N-2) схем сравнения, (ыр блоков

подсчета, номера ранга,

одноразрядных регистров и-л--

:элементов НЕ, причем выход i-ro ре гистра где i 2, 3,.,s () соединен с первым входом -й схемы сраанени;Я5 вторые входь схем сравнения соеданены с анной входных чисел и с входом первого регистра сдвига, вход i-го регистра сдвига соединен с выходом (i-l)-ro регистра сдвига, выход j-и схемы сравнения, где J 1, 2,..., (N-1), подключен к входу первого одноразрядного регистра из цепочки последовательно соединенных (N-1-j) одноразрядных регистров, к одному из входов первого блока под счета номера ранга и через соответствующий элемент,НЕ к одному из входов (j+l)-ro блока подсчета номера ранга, выход k-ro одноразрядного регистра в j-й цеопчке одноразрядных регистров, где k 1 2,,.,, (N-1-j), подключен к одному из входов (k+l)-го блока подсчета номера ранга и через соответствукяцкй злемент НЕ к одному из входов (k-i-j-«-1)-г блока подсчета номера ранга, синхрокизирующие входы всех регистров соединены с шиной сигналов сдвига устройства. . Кроме того, блок подсчета номера ранга содержит сумматор с (N-1) входами, соединенными с входами блока подсчета номера ранга, выход суммато ра соединен с выходом блока подсчета номера ранга. На чертеже представлена структурная схема устройства для . Устройство для ранжирования чисел содержит входную шину 1 устройства, по которой подается последовательность чисел, выраженных т-разрядным параллельным кодом, т-разрядный вход ной регистр 2, схему 3 сравнения двух т-разрядных чисел, одноразрядный, регистр А, элемент НЕ 5, блок 6 подсчета номера ранга шину 7 сигналов сдвига,. Устройство работает следующим образом. На входную шину 1 при каждом такте -поступает число, выраженное пт-раз рядным параллельным кодом. Через (N-I) тактов с выходов последователь но-соединенных т-разряднь Х регистров 2 на входы схем 3 сравнения будут подан ы числа,, поступившие соответственно на вход 1 в (N-t) предыдущих тактах. Эти числа на схемах 3 сравнения сравниваются с входным числом, пршпед шим на входную шину 1 в N-м такте. Ксли входное число в N-M такте равно или больше числа, снимаемого с выходов одного из регистров 2 то ,на выходе соответствующей схемы 3 сравнения образуется сигнал, равный логической единице. Если же число на входной шине 1 меньше, чем число с выхода регистра 2, то на выходе соответствующей 3 сравнения образуется сигнал, равный логическому нулю. Сигнал с выхода j-й схемы сравнения ,..., N-I), общее количество схем сравнения равно (N-1), подается на вход цепочки из последовательно соединенных (N-1-j) одноразрядных регистров 4, а также к одному из входов первого блока 6 подсчета номера ранга и через элемент НЕ 5 к одному из входов (j+l)-ro блока 6 подсчета номера ранга. Отметим, что .общее количество одноразрядных регистров - M-i в составе устройства равно .1 (N-i-j . . общее кoличecfrio элементов НЕ 5 равно N-t+ i: (N-1-j) « Н -NJ --2 - общее количество блоков подсчета номера ранга 2 равно N. Сигнал с выхода k-ro регистра 4 j-й цепочки одноразрядных регистров подается на один из входов (k+O-ro блока 6 подсчета номера ранга и че|рез соответствующий элемент НЕ 5 на один из входов (j-bl+k)-ro блока : подсчета номера рангов 6. На выходе R-roблока подсчета номера ранга. 6 (R },..., N) образуется число (выраженное, например, двоичным кодом) , которое равно количеству пришедших на входы этого блока подсчета номера ранга, единиц и которое характеризует номер ранга R-ro числа входной последовательности в данном такте. Таким образом, на выходе первого блока подсчета номера ранга через N тактов будет присутствовать число, характеризующее номер ранга входного чксла, пришедшего по шине I в Ы-м такте, а на выходе; N-ro блока подсчета номера ранга будет присутствовать число, характеризующее номер ранга входного числа, пришедшего на входную шину в 1-м такте. Число на выходе блока подсчета номера ранга, характеризующее минималькм ранг входного числа, будет равно нулю; число, на выходе блока подсчета номера ранга, характеризующее максимальный ранг входного чис- . ла, будет равно N-1. Из рассмотрения работы устройства видно, что на выходе R-ro блока подсчета номера ранга в каждом такте

присутствует число, равное рангу R-ro числа числовой последовательности .(понимается, что is N-M такте на входную шину 1 приходит число с индексом R 1, а число с индексом R - снимается с выхода j-ro входного регистра 2 ( ,...,.N-1).

Таким образом, по сравнению с прототипом предлагаемое техническое решение обладает более высоким быстродействием и решает принципиально новую задачу определения в течение одного такта рангов всех членов числовой последовательности,

li УСТРОЙСТВО ДЛЯ РАНЖИРОВАНИЯ ЧИСЕЛ, содержащее регистр сдвига, схему сравнения, блок подсчета номера ранга, причем выход регистра сдвига соединен с первым входом схемы сравнения, отличающеес я тем, что, с целью повышения быстродействия устройства, регистр сдвига выполнен пг-разрядным, ще m - количество разрядов сортируемых чисел, в устройство введешь (N-2) регистров сдвига, где N - число сортируемых чисел, (N-2) схем сравнения, (N-lL блоков подсчета ранга, одноразрядных регистров и элементов НЕ, причем выход 1-го регистра, где i « « 2,3,. ., (N-1), соединен, с первым входом i-й схемы сравнения, вторые входы схем сравнения соединены с пкной входных чисел и с входом первого регистра сдвига, вход f-ro регистра сдвига соединен с выходом (J-l)-ro регистра сдвига, выход j-й схемы сравнения, где j - I, 2,...,(N-1), подключен к входу первого одноразрадного регистра из цепочки последовательно соединенных (N-1-J) одноразрядных регистров, к одному из входов первого блока подсчета номера ранга и через соответствующий злемент НЕ к одному из входов (j+l)-ro блока подсчета номера ранга, выход k-ro одноразрядного регистра J-й цепочке одноразрядных регистров, где ,2,,,,, (N-1-j), подключен к (Л одному из входов (k+l)-ro блока подсчета номера ранга и через соот-вет- . ствукщий злемент НЕ к одному из входов (k+j+l)-ro блока подсчета номера ранга, (шихронизирукицие входы всех регистров соединены с шиной сигналов сдвига устройства. 2. Устройство по п. 1, о т л и.чающееся- тем, что блок подел ел :счета номера ранга содержит сумматор 1с (N-I) входами, соединенными с вхо|дани блока подсчета номера ранга, Ш11ХОД сумматора соединен с выходом бпока подсчета номера ранга.

мял