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

 

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

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

РЕСПУБЛИН (19) (11) (5D 4 G 06 F 7 06

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

Н АВТРРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3739647/24-24 (22) 10.05 ° 84 (46) 15.12.85. Бюл. Ф 46 (72) В.А. Грешков (53) 681.325(088.8 ) (56) Патент США 1(3829664, кл. G 06 F 7/02, опублик. 1974.

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

М- 1109739, кл. G 06 F 7/06, 1983 (54)(57} УСТРОЙСТВО ДЛЯ РАНЖИРОВАНИЯ

ЧИСЕЛ, содержащее (N-l) последовательно соединенных m-разрядных регистров сдвига, где И - число сортируемых чисел, (И-l) схем сравнения двух ш-разрядных чисел и блок подсчета номера ранга входного числа, причем выкод i-го m-разрядного регистра сдвига, где i = 1,2,...,,(N-l) соединен с первым входом i-й схемы сравнения, вторые входы схем . сравнения подключены к шине входных чисел устройства и входу, первоrom-разрядного регистра сдвига, выходы схем сравнения подключены к вхо. дам блока подсчета номера ранга входного числа, шина сдвига устройства соединена с синхронизирующими входами всех m-раэряднык регистров сдвига, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей эа счет формирования ва" риационного ряда чисел в реальном масштабе времени, в него введены дешифратор управления сдвигом, (Я-1) элементов ИЛИ, Н элементов И управления сдвигом, N дополнительных последовательно соединеннык m-разрядных регистров сдвига, дополнительный

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

i-го элемента ИЛИ, выход которого соединен с первым входом i-ro элемента И управления сдвигом, первый вход

N-ro элемента И управления сдвигом соединен с Б-и выходом дешифратора управления сдвигом и вторым входом (N-1)-ro элемента ИЛИ, второй вход

J-го элемента ИЛИ, где j = 1,2,..., (N-2), подключен к выходу (j+1)-го элемента ИЛИ, вторые входы всех элементов И управления сдвигом соединены с шиной сдвига устройства, вы ход k-ro элемента И управления сдвигом соединен с входом управления сдвигом k -ro дополнительного tn-разрядного регистра сдвига, где

1,2,...,щ, вход управления записью которого подключен к выходу

%-ro элемента И управления записью, первый вход которого соединен с k-м выходом дешифратора управления записью, вторые входы всех элементов И управления записью соединены с шиной записи устройства, шина. входных чисел устройства дополнительно. подключена к входу дополнительного rn-разрядного регистра сдвига входного числа, выходы которого подключены к информационным входам всех дополнитель« ных(ъ-разрядных регистров сдвига, вьвходы которых являются выходами отсортированных чисел устройства.

1 1

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

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

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

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

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

В начале работы устройства перед поступлением значения первого число1 ваго элемента выборки все регистры 2 сдвига должны быть обнулены.. Перед поступление очередного числа производится сдвиг всех ранее поступив- ших чисел, находящихся в сдвиговых регистрах 2, в соседний регистр с выдачей данных на схемы сравнения 3.

По входной шине 1 в каждый такт посту-. пают числовые значения в виде параллельного 1п-РазРЯДного Двоичного коДа на вход первого регистра 2, первые входы всех схем сравнения 3 и вход дополнительного m-разрядного входного регистра 5.

Каждое вновь поступившее число сравнивается схемами сравнения 3 с ранее поступившими числами и нулевыми значениями, если ранее посту" пивших числовых элементов выборки меньше (11-1). Если входное число равно или больше числа, поступивmего с выхода одного из регистров 2, то на выходе соответствующей схемы сравнения 3 образуется сигнал ло198509 2

5

40 гической единицы. Если входное числоменьше числа с выхода регистра 2, то на выходе соответствующей схемы сравненля 3 образуется сигнал, логического нуля, Сигналы с выходов (N-1) схем сравнения 3 поступают на блок 4 подсчета номера ранга. На выходе блока 4 образуется число в виде параллельного п-разрядного двоичного кода, равное количеству единиц, поступивших на входы блока 4. В общем случае количество единиц может принимать любое значение от 0 до (N-1)

Значение ранга R поступает одновременно на вход дешифратора 6 управления сдвигом и дешифратора 11 управления записью. На выходе (R+1)ro дешифратора 6 управления сдвигом образуется сигнал логической единицы, который, .проходя через цепочку элементов ИЛИ 7, образует (R+1) сигналы, которые поступают на первые входы (1,..., В+1) элементов 8 Иуправления сдвигом и открывают их.

Синхроимпульсы сдвига поступают через элементы 8 И с первого по (В +1)-й на первые управляющие входы соответствующих регистров 9 и осуществляют сдвиг ранее записанных данных .в соседние регистры.

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

° запись в него числа с выхода ш-раэрядного входного регистра 5. Таким образом, за время одного такта работы устройства происходит размещение вновь поступившего числового элемента выборки в регистр, определяемый его рангом и . После М-ro такта работы схемы все К элементов выборки будут расположены в порядке . возрастания их величин.

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

ll98509

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

Редактор М. Дылын Техред О.Неце Корректор А. Тяско

Заказ 7722/48 Тираж 709 Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4 величин (формирование вариационного ряда). При поступлении всех элементов выборки объема (N), на который рассчитано предлагаемое устройство, номера регистров, в которых находятся элементы упорядоченной выборки, определяют ранги этих элементов.