Устройство для определения квантилей распределения Советский патент 1989 года по МПК G06F17/18 

JL

(Л

Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах цифрового автоматического управления. Цель изобретения - повышение быстродействия и расширение области применения. Устройство содержит ассоциативный накопитель 1, блок элементов ИЛИ 2, блок элементов И 3, блок триггеров 4, комбинированный сумматор 5, компаратор 6, регистр 7, элемент И 8, регистр последовательного приближения 9, регистр маски 11, генератор импульсов 12 и элемент задержки 13

10 - вход пуска устройства. 2 ил., 1 табл.

И

5№ S

JO

I Г

С

4

00

PU8.1

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

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

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

Устройство для определения квантилей распределения содержит ассоциативный накопитель 1, информационные выходы которого соединены с первой группой входов блока 2 элементов ИЛИ и информационными входами блока 3 элментов И, выходы которых подключены к единичным входам блока 4 триггеров, выходы которых соединены с вторми входами блока 2 элементов ИЛИ,выходы которых подключены к входам комбинационного сумматора 5, выход которого подключен к второму входу компаратора 6, с первым входом кото- iporo соединен выход регистра 7, выход компаратора 6 соединен с первым входом элемента И 8 и информационным входом регистра 9 последовательного приближения, выход которого подключен к входу признака опроса ассоциативного накопителя 1 и является выходом всего устройства, вход 10 пуска устройства соединен с входами установки в нуль регистра 9 последовательного приближения, регистра 11 маски, входами установки в нуль блока 4 триггеров, входом пуска генератора 12 импульсов, выход которого подсоединен к второму входу элемента И 8, тактирующим входам регистра 9 последовательного приближения и регистра 11 маски, входу элемента 13 задержки, выход которого подключен к входу разрешения поиска ассоциативного накопителя 1, вход 14 задания квантилей является информационным входом регистра 7.

Регистр последовательного приближения содержит триггер 15, регистр 16 сдвига, блок 17 триггеров, элемент НЕ 18.

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

Перед началом работы устройства в регистр 7 по входу заносится число (1-q) N, где q - требуемая квантиль, N - количество чисел ассоциативного накопителя 1 (величина выборки).

Сигнал пуска, подаваемый по входу 10, устанавливает в нуль регистр 11 маски, регистр 9 последовательного

приближения, блок 4 триггеров и запускает генератор 12 импульсов.

Импульс с генератора 12 импульсов осуществляет сдвиг регистра 11 маски, при котором в старший его раз5 РЯД поступает логическая единица, сдвиг сдвигового регистра 16 регистра 9 последовательного приближения, при котором на вход его поступает логическая единица с выхода тригге0 ра 15, установленного сигналом пуска, после чего триггер 15 сбрасывается в нуль, а первый триггер блока 17 устанавливается в единичное состояние. Кроме того, через элемент 13

5 задержки по окончании сдвигов импульс осуществляет обращение поиска в ассоциативном накопителе 1. На ши-1 - нах совпадения ассоциативного накопителя 1 в случае совпадения фор0 мируются единичные сигналы. Триггеры 4 сброшены в нуль, поэто му через блок 2 элементов ИЛИ эти сигналы поступают на комбинационный сумматор 5, где превращаются в код числа совпадений. Этот код сравнивается с кодом, записанным в регистре 7,причем если он больше кода, записанного в регистре 7, то на выходе компаратора 6 формируется нулевой сигнал, если меньше или равен - то единичный.

В случае появления единичного сигнала на выходе компаратора 6 следующий импульс генератора 12 импульсов проходит через элемент И 8 и те элементы И блока 3, на информационных входах которых присутствует единичный сигнал, и устанавливает в единицу соответствующие триггеры блока 4. В случае нулевого сигнала

0 этого не происходит. В обоих случаях импульс генератора 12 импульсов вызывает сдвиг регистра 11 маски и регистра 16 регистра 9 последовательного приближения, при котором на ин5 формационный вход регистра 16 подается нулевой сигнал с триггера 15, сброшенного предыдущим импульсом генератора 12 импульсов. При этом в

5

0

5

51

i-й разряд блока 17 триггеров (i 2,3,...,m, где m - число разрядов ассоциативного накопителя 1) заносится единица, а в (Ј-1)-й разряд инвертированная элементом НЕ 18 информация с выхода компаратора 6. После этого через элемент 13 задержки импульс осуществляет обращение поиска в ассоциативном накопителе 1

Так продолжается до тех пор,пока после (т+1)-го импульса на выход переполнения регистра 11 маски не сформируется логическая единица,блокирующая генератор 12 импульсов; (га+1)-й импульс вызывает появление логической единицы на выходе переполнения сдвигового регистра 16 регистра 9 последовательного приближения, что вызывает запись информации с выхода компаратора 6 через элемен НЕ 18 в младший разряд триггера блока 17 регистра 9 последовательного приближения.

Работа устройства иллюстрируется следующим примером.

Пусть вычисляется 75%-ная квантиль выборки из восьми пятиразрядных чиселj записанных в ячейках ассоциативного накопителя 1 в виде

10011

11001

10101

00111

10110

11111

10101

При этом в регистр 7 заносится число два.

Работа устройства при этом иллюстрируется таблицей.

В результате сформирован код 10110.

Действительно, если расположить числа в порядке возрастания, т.е. в виде

11111

11001

10110

10101

10101

10011

00111

00011

то в интервал от 00000 до 10110 включительно попадают 6 чисел, т.е. 75% выборки.

7976

Устройство позволяет определять квантиль за число тактов т+1 независимое от количества чисел N.

5 Л

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

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

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

5 элементов И и подключена к информационным выходам ассоциативного накопителя, выходы блока элементов И соединены соответственно с входами установки в 1 блока триггеров,пряQ мые выходы которого подключены соответственно к второй группе входов блока элементов ИЛИ, выходы которых соединены с входами комбинационного сумматора, выход которого подключен к второму входу компаратора, тактовые входы регистра последовательного приближения и регистра маски и вход элемента задержки объединены с вторым входом элемента И и подклю.. чены к выходу генератора импульсов, вход блокировки которого соединен с выходом старшего разряда регистра маски, информационный выход которого подключен к входу маски ассоциативного накопителя, вход признака опроса которого соединен с выходом регистра последовательного приближения, информационный вход которого подключен к выходу компаратора,выход элемента задержки соединен с

5

0

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

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

гистра последовательного приближения является информационным выходом уст-.

10000 11000 11100 11110

11111

10000 11000 10100 10110 10111

11101110 01000100 00101010 00001000 00000000

#

76

OR RG

ff

7

г

8

ройства, информационный вход регистра является входом задания квантиля.

00000000 01000100 01000100 01000100 01000100

1

о 1 1 о

D

С

я

MBMI

о

С

и