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

7«

Л

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

.йиф.роспр.

HHfn.fXfC/tfl.

(Л

1

5, регистр опроса 3, блок памяти 6, сумматоры 14 и 15, регистры суммы 16 и 17, вычитатель 18 и элементы управления. Очередной пакет данных через входной регистр 5 поступает на адресный вход блока памяти 6, из которого читается число, и поступает на входы сумматора 14. Это число суммируется с единицей, постоянно находящейся на втором входе этого сумматора. Результат запомнится на регистре суммы 16 и далее запишется в блок памяти 6 по этому адресу. Таким образом, в блоке памяти 6 подсчитьгеается количество чисел, пришедших по каждому из значений адресов из очередного пакета данных. Опрос информации происходит через регистр опроса 3 по порядку, начиная со значения нуля. По адресу текущего числа опроса из блока памяти 6 читается текущее значение дифференциальной функции. Одновременно это же значение поступает на входы первой группы сумматора 15, где склаИзобретение отнрсится к вычислительной технике и может быть использовано в информационно-поисковых системах и системах статистической обработки данньк.

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

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

На фиг. 3-6 временные диаграммы работы устройства.

Устройство содержит генератор 1 тактовых импульсов, счетчик 2 опроса, регистр 3 опроса, счетчик 4 цикла, входной регистр 5, блок 6 памяти. Триггер 7 начальной установки, .элементы ИЛИ 8-10, элемент И 11, формирователь 12 имрульсов, триггер 13 выбора регистра, сумматоры 14 и 15, регистры 16 и 17 суммы, вычитатель 18. 385

дывается с преда1дуп(им значением, которое находится на его входах второй группы. Результат суммы заломи- нается на регистре 17 и далее поступает на входы вычитаемого вычитате- ля 18. Данная сумма вычитается из числа, равного кол гчеству чисел, находящихся в пакете данных. Это текущее значение интегральной функции. После каждого опроса текущих значений дифференциальной и интегральной функций в ячейку памяти блока 6, откуда проводился опрос, записырается нуль. Таким образом, функция дифференциального распределения показывает, какая доля из о&дего количества зафиксированных величин приходится на один из выбранных уровней (функция повторяемости). Функция интегрального распределения показывает, какая доля из общего количества чисел приходится на величины вьше заданного уровня (функция обеспеченности) . 6 ил.

Формирователь 12 импульсов содержит элемент ИЛИ 19, элемент 20 задержки, элемент И-НЕ 21.

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

Начальная установка (см. фиг, 3).

При первоначальном включении или при подаче отрицательного сигнала начальной установки НУ срабатывает триггер 7 начальной установки. Сиг- н-алом НУ через второй элемент ИЛИ 9 обнуляется счетчик 2 опроса и через третий элемент ИЛИ 10 устанавливается Триггер 13 выбора регистра в положение разрешающего работу регистра 3 опроса, так как на первом выходе триггера 13 устанавливается лог. 1. Потенищал второго выхода триггера 13 выбора регистра лог. О,

запрещающий работу входного регистра 5 (регистр находится в высокоим- педансном состоянии, что соответствует состоянию оборванной цепи) и «г держит в обнуленном состоянии первый

регистр 16 суммы, выход которого связан с информационным входом блок 6 памяти.

На первом выходе триггера 7 начальной установки устанавливается лог, 1, которая разрешает работу генератора 1 тактовых импульсов. Лог второго выхода триггера 7 начальной установки через элемент И 11 уста- навливает блок 6 памяти в режим записи.

Сигналы с генератора 1 тактовых импульсов через первый элемент ИЛИ поступают на счетные входы счетчика

2опроса и регистра 3 опроса. По фронту синхросигнала записывается информация с информационного выхода счетчика 2 опроса в регистр 3 опроса, а по спаду этого же импульса информационный выход счетчика 2 опроса увеличивается на единицу. Таки образом, информация с информационного выхода счетчика 2 опроса через регистр 3 опроса поступает на адресный вход блока 6 памяти, в котором по следующим синхросигналам, одущим от генератора 1 тактовых импульсов, перебираются адреса ячеек, начиная с нулевого, и тем самым в массив памяти записываются нули. Бл 6 памяти обнуляется. По окончании цикла обнуления памяти на втором выходе счетчика 2 опроса формируется отрицательный импульс, кото1М.1й чере второй элемент ИЛИ 9 устанавливает этот же счетчик в начальное состояние. Этим же сигналом Сбрасывается триггер 7 начальной установки, который запрещает работу генератора 1 тактовых импульсов. Также сбрасывается счетчик 4 циклов и триггер 13 выбора регистра, при котором разрешена работа входного регистра 5 и первого регистра суммы 16. Регистр

3опроса устанавливается в высокоим педансное состояние. В обнуленном состоянии удерживается второй регис 17 сумьы. Блок памяти 6 устанавливается в режим чтениетзапись информации. На этом подготовка устройства

к работе заканчивается.

В схеме первый элемент ИЛИ 8 уп- равляется высокими уровнями входных сигналов, второй элемент ИЛИ 9 и третий элемент ИЖ 10 управляются низкими уровнями входных сигналов (ИЛИ по-нулю).

Цикл приема информации (см.фиг.4).

Входная информация ИНФ в двоичном представлении одновременно с синхроимпульсами СИ фиксируется по фронту си во входном регистре 5 и далее поступает на адресный вход блока 6 памяти. Количество поступающих чисел (пакет данных) определяет счетчик 4 цикла, и эта величина равна N. Текущее -е число может принимать значение от О до М, т.е.

О А М,.- .

где А 1, 2, 3, N,

М - максимальное А;-е число (определяет объем памяти), N М.

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

вход (первое текущее слагаемое) первого сумматора 14 текущего числа. Это число суммируется с единицей, постоянно находящейся на втором входе этого же сзтФ1атора (второе слагае- мое). Далее по спаду сигнала СИ результат запоминается на первом регистре 16 и затем по отрицательному потенциалу, поступающему на управляющий вход блока 6 памяти,. записьшается в ячейку памяти по этому же адресу и в этом же такте синхроимпульса СИ. Такой режим чтение-запись по данному адресу в данном такте СИ формируется на формирователе 12 импульсов через элемент И 11. Таким образом в блоке 6 памяти запоминается количество чисел, пришедших к каждс 1у из значений адресов, т.е. в блоке 6 памяти подсчитывается, сколько чисел одной градации состоит в ряду данного цикла.

По окончании цикла приема и обработки входной информации счетчик 4 цикла, подсчитав количество принятых значений в пакете (N-значений),.формирует отрицаЕтельный импульс, который через третий элемент ИЛИ 10 устанавливает первый выход триггера

13 выбора регистра в состояние лог.1, а второй выход - в состояние лог.О. Разрешена работа регистра 3 опроса и второго регистра 17 суммы. Входной регистр 5 устанавливается в высокоимпедансное состояние. В обнуленном состоянии удерживается первый регистр 16 суммы, который непосредственно соединен с информационным входом блока 6 памяти. Последний остается в режиме чтение-запись.

Цикл опроса информахщи (см.фиг.5).

По сигналу опроса ОПР через

первый элемент ИЛИ 8 включается в ра- ю Роса устанавливается значение единиботу счетчик 2 опроса. Через регистр 3 опроса производится чтение информации из блока 6 памяти, которое осуществляется следующим образом.

При поступлении первого сигнала ОПР через первый элемент ИЛИ 8 по фронту сигнала в регистр 3 опроса записьтается значение нуля, так как счетчик 2 опроса был обнулен в

цикле приема информации и на его перч 20 числа с первым значением дифференциBcw информационном выходе в данный момент находится нуль. По этому адресу из блока 6 памяти читается значение, соответствующее количеству чисел нулевой градации. Это первое значение дифференциальной функции. Одновременно это же значение из блока 6 памяти поступает на первый вход второго сумматора 15 текущего числа (первое текущее слагаемое). Оно складывается с числом, которое находится на втором входе этого же сумматора (второе текущее слагаемое) На вторам входе сумматора 15 текущего числа в данный момент находится число нуль, так как второй регистр 17 суммы был обнулен в цикле приема информации. Результат суммы по спаду сигнала ОПР запоминается

на втором регистре 17 суммы и посту- 40 дифференциальной и интегральной

пает на первый вход вычитателя 18. На вычитателе 18 поступившее значение суммы вычитается из числа N, которое .постоянно находится на его втором входе (число N по значению равно количеству чисел в пакете данных). Это первое значение интегральной функции. В ячейку блока 6 памяти, из которой производился опрос дифференциального и интегрального значения, по спаду сигнала ОПР с некоторой задержкой отрицательньм потенциалом записывается нуль, так как в данном цикле (в цикле опроса) в обнуленном состоянии удерживается первый регистр 16 суммы, выход которого непосредственно соединен с информационным входом блока 6 памятки. Таким образом, обнуление данной ячейки

функций по каждому сигналу ОПР тупает на вход устройства с пос щим выводом на печать. По оконч цикла опроса (цикл опроса по зн

с нию равен ) на управляющем в счетчика 2 опроса формируется о тельный сигнал, который через в рой элемент ИЛИ 9 обнуляет сам Счетчик 4 цикла также обнуляетс

gQ устанавливается в режиме приема формации. Триггер 13 выбора рег устанавливается в положение, пр тором работает входной регистр Регистр 3 опроса информации пере дит в высокоимпедансное состоян Устройство готово к приему очер го пакета данных.

Таким образом, если обозначи количество чисел, которое прини

55

блока 6 памяти происходит сразу rtoc- ле того, как были получены дифференциальная и интегральная функции. Ре- дим чтение-запись по данному адресу в данном такте сигнала ОПР формирует формирователь 12 импульсов. Одновременно по спаду сигнала ОПР в данном такте на выходе счетчика 2 опцы. При поступлении второго сигнала ОПР по его фронту на регистре 3 опроса запоминается значение единицы. Из блока 6 памяти читается зна- чение, соответствующее количеству чисел первой градации. Это второе значение дифференциальной функции. Одновременно это же значение суммируется на втором сумматоре 15 текущего

альной функции, которое в данный момент находится на втором входе этого сумматора, и по спаду сигнала ОПР запоминается на втором регистре 17 суммы. Искомая сумма вычитается из числа вычитателя 18. Это второе значение интегральной функции. Ячейка памяти, как и в предьщущем случае, по данному адресу в данном

такте сигнала ОПР обнуляется при помощи режима чтение-запись, сформированного формирователем 12 режима. По спаду второго сигнала ОПР на выходе счетчика 2 опроса устанавливается число два. Аналогично получаются последующие значения дифференциальной и интегральной функций и аналогично происходит обнуление ячеек блока 6 памяти. Кал|дое значение

дифференциальной и интегральной

функций по каждому сигналу ОПР поступает на вход устройства с последую-f щим выводом на печать. По окончании цикла опроса (цикл опроса по значению равен ) на управляющем выходе счетчика 2 опроса формируется отрицательный сигнал, который через второй элемент ИЛИ 9 обнуляет сам себя. Счетчик 4 цикла также обнуляется и

устанавливается в режиме приема информации. Триггер 13 выбора регистра устанавливается в положение, при котором работает входной регистр 5. Регистр 3 опроса информации переходит в высокоимпедансное состояние, Устройство готово к приему очередного пакета данных.

Таким образом, если обозначить количество чисел, которое принимает

А;-я градация через D, то функция D(A}) соответствует закону дифференциального распределения

О (А,) D(A,)

и показывает, какая доля из общего количества зафиксированных величин приходится на один из выбранных уров ней (функция повторяемости). Значени N 5-D(A|) являются функцией, которая соответствует закону интегрального распределения

F(A;) N - XlD(A;)j,

e-i

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

(функция обеспеченности).

Формирователь 12 импульсов представлен на фиг. 2. Формирователь 12 импульсов работает следующим образом (см. фиг. 6).

На первый или второй вход элемента 19 поступают импульсы. С инвертирующего выхода этого элемента сигнал поступает на первый вход элемента И-НЕ 21. С неинвертирующего вьрсода элемента 19 сигнал через элемент 20 задержки поступает на второй вход элемента И-НЕ 21. На выходе элемента И-НЕ 21 формируется импульс лог. О, который несколько задержан по отношению к спаду входного сигнала. Формируется сигнал Чтение-запись, который поступает на управляющий вход блока 6 памяти.

Таким образом, по фронту сигнала си или ОПР по положительному потенциалу на управляющем входе блока 6 памяти информация читается, по спаду сигнала СИ или ОПР по потенциалу лог. О информация записывается в память, т.е. за один такт входного сигнала происходит переключение сигнала Чтение-запись блока 6 памяти.

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

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

ю

,5

20

25

ЗО

40

45

50

gg

383«

дифференциального распределения чисел, оно содеру:ит триггер начальной установки, два элемента Ш1И, триггер выбора регистра, два регистра суммы, вычитатель, счетчик цикла, входной регистр, регистр опроса, формирователь импульсов, причем вход установки в единичное состояние триггера начальной установки является входом начальной установки устройства и соединен с первыми входами первого и второго элементов ИЛИ,а прямой выход соединен с входом запуска генератора тактовых импульсов, выход которого соединен с первым входом третьего элемента ИЛИ, второй вход которого является входом опроса устройства, а выход соединен с первым входом формирователя импульсов, с синхровходами счетчика опроса,регистра опроса и первого регистра суммы, выходы разрядов которого соединены с входами вычитаемого вычитате- ля и входами первой группы первого сумматора, выходы суммы которого соединены с информационными входами первого регистра сум№, а входы второй группы соединены с информационными выходами блока памяти, выходами дифференциального распределения чисел устройства и с входами первой грунты второго сумматора,входы второй группы которого являются входами заданного числа устройства, а выходы суммы соединены с информаци- онными входами второго регистра суммы, выходы разрядов которого соединены с информационными входами блока памяти, управляющий вход кото- # рого соединен с выходом элемента И, первый вход которого соединен с выходом формирователя импульсов, а второй вход с инверсным выходом триггера начальной установки, вход установки в О которого соединен с вторым входом первого элемента ИЛИ, с выходом переполнения счетчика опроса с входа1 ш установки в нулевое состояние счетчика цикла и триггера выбора регистра, вход установки в единичное состояние которого соединен с выходом второго элемента ИЛИ, второй вход которого ,соединен с выходом переполнения счетчика цикла, счетный вход которого является входом синхронизации устройства и соединен с вторым входом формирователя импульсов, с входом синхронизации

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

Фие.г

т

т

Ht ипеет значения

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

21

/ LJ 2

f(Sx. ogp 1 W y 6(6x. упр.) RJNJ

6 (8х.дон. }Скз ZXS2

13{Вых.1} ;

13 (бых.2)

« (Sux.) 1 Не If mem значения

Фиг Л

Фиг.6

P

s SI g

1 II

| .4

1