Устройство для определения квантилей распределения

 

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

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

СОЮЗ СОВЕТСНИХ.

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

РЕСПУБЛИК (д1) 4 G 06 F 15/36

ПРИ fNHT СССР

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

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

ЮЛЮ."Ц

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 4252450/24-24 (22) 28.05.87 (46) 23.05.89. Бюл. 9 19 (72) Л.В. Вариченко, В.В. Вишневский, М.Я. Дедишин, В.И. Корнейчук, А.П. Марковский, M.À. Раков, Ю.А. Томин и С.В. Широчин (53) 681,3 (088.8) (56) Авторское свидетельство СССР

N 1053100, кл. G 06 F 7/04, 1982.

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

У 607226, кл. С 06 F 15/36, 1978. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КВАНТИЛЕЙ РАСПРЕДЕЛЕНИЯ

ÄÄSUÄÄ 1481 97 А1

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

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

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

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

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

1797

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

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

20 е1

55.

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

Сигнал пуска, подаваемый по входу

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

Импульс с генератора 12 импульсов осуществляет сдвиг регистра 11 маски, при котором в старший его разряд поступает логическая единица, сдвиг сдвигового регистра 16 регист" ра 9 последовательного приближения, при котором на вход его поступает логическая единица с выхода триггера 15, установленного сигналом пуска, после чего триггер 15 сбрасывается в нуль, а первый триггер блока

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

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

5 1481797

i-й разряд блока 17 триггеров (i

2,3,...,m, где m — число разрядов ассоциативного накопителя 1) заносится единица, а в (i-1)-й разряд инвертированная элементом HE 18 информация с выхода компаратора 6.

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

НЕ 18 в младший разряд триггера блока 17 регистра 9 последовательного приближения.

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

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

11001

10101

00111

11111

10101

0001,1

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

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

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

10110.

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

11111

11001

10101

10101

10011

00111

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

75 выборки.

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

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

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

1О

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

"0" регистра последовательного приближения, регистра маски и блока триггеров объединены с входом запуска генератора импульсов и являются входом пуска устройства, выход ре1481797 ройстна, информационный вход регистра является входом задания квантиля. гистра последовательного приближения является информационным выходом уст-.

Такт

Лоступающая информация

Вход маски Вход признака

Выход сов- Выход Выход падения компара- блока 4 тора 6 триггеров опроса

Составитель Л. Григорьян-Чтенц

Техред М.Ходанич КорректорВ. Гирняк Редактор В. Данко

Заказ 2692/51 Тираж 669 Подписное

ВНИИПИ Государственного комитета па изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина, 101

1 10000

2 11000

3 11100

4 11110

5 11111

11 000

10111

00000000

1

0

01000100

Разряд результата +

1-й такт

0

1