Устройство для построения гистограммы

 

союз совЕтских

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

РЕСПУБЛИК

Р1) G 06 F f5/36

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

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

1 (21) 4615400/24 (22) 02.12.88 (46) 30. 10.91. Бюл. ¹ 40 (71) Киевский политехнический инсти- . тут им. 50-летия Великой Октябрьской социалистической революции (72) С.В.Широчин, Е.А.Маслянчук, А.П.Марковский и В,И.Корнейчук (53) 681.3 (088.8) (56) Авторское свидетельство СССР

¹ 1020836, кл. G 06 F 15/36, 1983, Авторское свидетельство СССР

¹ 1388901, кл. G 06 F 15/36, 1988. (54) УСТРОЙСТВО ДЛЯ,ПОСТРОЕНИЯ ГИСТОГРАММЫ (57) Изобретение относится к вычислительной технике, в частности к специализированным устройствам статистиИзобретение относится к вычислительной технике и может быть использовано в устройствах статистической обработки информации.

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

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

Устройство для построения гистограммы содержит регистр 1 маски, первый блок 2 ассоциативной памяти, первый выход 3 блока управления, второй блок 4 ассоциативной памяти, мультиплексор 5, m групп по и элементов

РАВНОЗНАЧНОСТЬ 6 (m — коды граничных значений гистограммы, и — количество

„,80„„1688261. A 1

2 ческой обработки информации, и может быть использовано для построения высокопроизводительных систем автоматизированной обработки результатов измерений, выполненных на узлах с высокой степенью интеграции. Цель изобретения — повьппение быстродействия устройства. Устройство для построения гистограммы содержит регистр маски, два блока ассоциативной памяти, первый мультиплексор, m групп по и элементов РАВНОЗНАЧНОСТЬ (m — количество пределов построения гистограммы), m групп по и D-триггеров, RSтриггеров, комбинационный сумматор, .m-2 групп по п элементов НЕРАВНОЗНАЧНОСТЬ, группу элементов НЕ, К ре-. гистров. 1 з.п.h-лы, 3 ил. анализируемых выборок), m групп по и

D-триггеров 7, m групп по и КЯ-триггеров 8, m+1 комбинационных сумматоров 9, m-1 групп по п элементов НЕ- СЬ

РАВНОЗНАЧНОСТЬ 10, группу из и эле- QO ментов HF. 11, m+1 регистров 12, вход . Q()

13 сброса устройства, вход 14 пуска ;) ,.блока управления, блок 15 управления, (.1 вход 16 сброса блока управления, второй 17, третий 18 и четвертый 19 выходы блока управления, причем блок 15 управления содержит триггер 20, элементы 21 — 23 задержки, генератор 24,, элемент И 25. Регистр 1 маски подключен к входам маскирования первого . блока 2 ассоциативной памяти, и выходов совпадения второго блока 4 ассоциативной памяти связаны с первыми входами мультиплексора 5, каждый i-й

1688261 (j, = 1,n), выход которсго подключен к пеовомч входу i-ro элемента 6, РАВНОЗНАЧНОСТЬ каждой j-й группы (где — 1„m, m — количество .ячеек перво5 го блока 2 ассоциативной памяти) и ииформационному входу i-го 0-триггера 7; 1-й группы, каждый 1-й выход совпадения первого блока 2 ассоциативной памяти подсоединен к вторым входам всех элементов РАВНОЗНАЧНОСТЬ

1 1-и группы1 Выход кажпого 1-Го элемента РАВНОЗНАЧНОСТЬ 6, 1-й

I группы связан с первым входом установки i-ro КБ-триггера 8, 1-й груп- 15

nba, выход каждого |.-го RS òðèããåðà

8 . j-й группы подключен к входу 1,) синхронизации i-го 1)-триггера 7

1,1

j-й группы, выходы группы Ю-триггеров

71 подсоединены к входам комбинапионного сумматора 9 и первым входам элементов НЕРАВНОЗНАЧНОСТЬ 10, ) группы, выходы элементов р-й группы (р = 2, m-1) D — триггеров /, связа,ны с первыми входами элементов НЕРАВ- 2S

НОЗНАЧНОСТЬ 10 р-х групп и вторы1

Ми входами элементов НЕРАВНОЗНАЧНОСТЬ

10, р < (р-1)-х групп,, выходы m-й

1 группы П-триггеров 7 ° подключены к

< Hh вторым входам элементов НЕРАВНОЗНАЧНОСТЬ 10; n, (m- 1)-й группы и входам группы элементов НЕ 11, выходы которых связаны с входами (m+1)-ro комбинационного сумматора 91, выходы элементов НЕРАВНОЗНАЧНОСТЬ 10, б (= 1 m 1) ен) к 35

Входам (а+1)-х комбинационных суммаа oðoâ 9 < <, выходы К-х к омбинационIlbIx сумматоров 9((подсоединены к информационным входам К.-х регистров

12К, выходы которых являются выходами . 40 устройства, вход 13 управления началом работы устройства связан с входами сброса всех RS-òðèrråðoí 8 всех

1,)

rðóïï, входом установки в исходное состояние регистра 1 маски и первым

45 входом 14 блока 15 управления, выход переполнения при сдвиге регистра 1 маски подключен к управляющему входу мультиплексора 5 и второму входу 16 блока 15 управления, первый выход 3 которого подсоединен к входу управле-. ния сдвигом регистра 1 маски, второй выход 17 блока 15 управления связан вхоцом управления опросом блока 2 ассоциативной памяти, третий выход 55

18 блока 15 управления подсоединен к вторым входам установки всех КБ-триггеров 8 всех групп четвертый выl() " > ход 19 блока 15 управ. пения связан с входами синхронизации регистров 12, вторые входы первого мультиплексора

5 связаны с источником потенциала

"1", кроме того, блок 15 содержит триггер 20, входом подсоединенный к первому входу 14 блока 15 управления, выход которого подключен к первому входу элемента И 25, выход которого является вторым выходом 17 блока 15 управления и подсоединен к входу первого элемента 2 1 задержки, выход которого является третьим выходом 18 блока 15 управления, второй вход 16 блока 15 управления является входом сброса триггера 20 и входом второго элемента 22 задержки, выход которого является выходом блока 15 управления и связан с входом элемента 21 задержки, выход которого является четвертым выходом 19 блока 15 управления, выход генератора импульсов 24 подключен к второму входу элемента И 25.

Устройство для построения гистограммы работает следующим образом.

Перед началом работы устройства в первый блок 2 ассоциативной памяти заносятся коды граничных значений гистограммы в порядке убывания, причем первый выход совпадения соответствует старшему пределу, à m-й— младшему. В блоке 4 ассоциативной памяти хранятся коды выборки, по которым строится гистограмма.

Сигнал по входу "Начало работы" 13 поступает на вход установки в исход-, ное состояние регистра 1 маски, где устанавливается число с единицей в старшем разряде и нулями в остальных, поступают на входы сброса всех RSтриггеров 8; всех групп, устанавливая их в нулевое состояние, и через вход 14 блока 15 управления устанавливает в единичное состояние триггер 20. После установки триггера 20 импульсы с генератора 24 импульсов начинают проходить через элемент И

25 и вызывают через выход 18 блока

15 управления обращение к блоку 2 ассоциативной памяти и на вход опроса блока 4 ассоциативной памяти. На выходах совпадения блоков 2 и 4 ассоциативной памяти формируются сигналы совпадения в выделенном (старшем) разряде с содержимым регистра 1 маски, и эти сигналы выдаются на выходы совпадения. Информация с выхода блока 4 ассоциативной памяти передается

88261

25

55

5 16 на выходы первого мультиплексора 5.

Элементы РАВНОЗНАЧНОСТЬ 6, групп элементов РАВНОЗНАЧНОСТЬ реализуют следующую функцию: на вход i-го (i — 1,n) элемента РАВНОЗНАЧНОСТЬ 6;, j-й (j = 1,m) группы поступают сйгналы совпадения i-ro слова второго блока 4 ассоциативной памяти и j-го слова блока 2 ассоциативной памяти.

Если значения анализируемых разрядов этих слон не совпадают, то на выходе

i-го элемента РАВНОЗНАЧНОСТЬ 6 j-й

1,) группы сформировано нулевое значение, которое устанавливает в единичное состояние i-й RS-триггер 8, j -й группы, к оторый, в свою очередь, пер едним фронтом выходного сигнала о сущес твляет запись состояния i-го выхода совпадения блока 4 ас соци атийной памяти в 1-й D-триггер 7 ) -и группы . Единичное значение этого тригг ера означает, что i-e число блока 4 ассоциативной памяти больше j -ro числа (предела ) блока 2 ассоциативной памяти . Если же разряды i-го числа блока 4 ассоциативной памяти и j -ro числа блока 2 ассоциативной памяти совпадают, то на выходе i- ro элемента

РАВНОЗНАЧНОСТЬ 6 1 j -й группы сформиров ано единичн ое значение и j -й

RS"òðèã ãåð 8 ; j -й группы остается в нулевом состоянии . Сигнал с выхода элемента И 2 5, вызывающий сигнал onроса блоков 2 и 4 ассоциативной памяти, после окончания опроса через первый элемент 2 1 задержки осуществляет сдвиг содержимого регистра 1 маски в сторону младших разрядов, который теперь вызывает опрос . следующего р аэряда, при котором схема работает аналогично, за исключением того, что появление единичных сигналов на выходе элементов РАВНОЗНАЧНОСТЬ 6, j -й групп вызывает установку соот ветствующего RS-триггера 8 j -й группы

1„1 только в том случае, если он не был установлен ранее, т.е. фиксируется различие в наиболее старшем разряде.

Устройство работает таким образом до тех пор, пока после 1-го (где 1— разрядность числа блоков 2 и 4 ассоциативной памяти) импульса с выхода элемента И 25 не проанализированы младшие разряды блоков 2 и 4 ассоциативной памяти и через первый элемент

2 1 задержки не осуществился сдвиг содержимого регистра 1 маски, при котором на выходе переполнения сформируется единичное значение, которое подает на выходы первого мультиплексора 5 единичные значения с его второго входа, сбрасывает триггер 20 и через второй элемент 22 задержки осуществляет установку в единичное состояние RS-триггеров 8, )-х групп, при которой из нулевого в единичное состояние переходят только те RSтриггеры, которые не были установлены ранее, т.е. соответствующие совпадению i-го числа блока 4 ассоциативной памяти и j-го числа блока 2 ассоциатив- ной памяти, эти RS-триггеры устанавливаются в единичное состояние и передним фронтом выходного сигнала осуществляют запись в соответствующие

D-триггеры 7, j-x групп единичных состояний с выхода первого мультиплексора 5. Таким образом, единичное состояние i-ro D-триггера 7; j-й группы обозначает, что i-е число блока 4 ассоциативной памяти больше или равно j-му числу (пределу) блока 2 ассоциативной памяти. После установки через второй элемент 22 задержки все RS-триггеры всех групп RS-триггеров 8 установки в единичное состояние во все D-триггеры всех групп D-триггеров 7 заносится. информация о соотношении чисел и пределов.

Единичное состояние D-триггеров

7. 1 первой группы свидетельствует о превьппении числами верхнего предела, количество превысивших чисел определяется первым комбинационным сумматором 9. 1.

Если i-й D-триггер 7; s-й группы установлен в единичное состояние,. а i-й D-триггер 7; +.» (s-1)-й груп1 пы установлен в нулевое состояние, то на выходе i-го элемента НЕРАВНОЗНАЧНОСТЬ 10, < (s-1)-й группы присут45 ствует единичный сигнал, свидетельст,вующий о нахождении i-го числа блока

2 ассоциативной памяти между з-ми и (s-1)-м пределами, хранящимися в блоке 4 ассоциативной памяти, включая

50 (s-1)-й предел количество чисел пеЭ редающих в указанный интервал, подсчитывается s-м комбинационным сумматором 9 .

Числа, для которых соответствующие

D-триггеры 7 m-й группы содержат

i. Vn нулевые значения потенциалов, имеют значения ниже нижнего предела, их количество с использованием группы

16882б! элементов НЕ 11 подсчитывается комбинационным сумматором 9<1+,1.

Коды количества чисел, определенные по описанному способу, фиксируются в регистрах 12 сигналом с выхода переполнения при сдвиге регистра 1 маски, задержанным элементами 22, 23 задержки.

Последовательность выдачи сигналов 10

Иллюстрируется временными диаграммами (фиг.3) .

Формула изобретения устройство для построения гис- 15 тограммы, содержащее первый блок ассоциативной памяти, регистр маски и блок управления, причем выходы регистра маски подключены к входам маскирования первого блока ассоциативной 20 памяти, первый выход блока управления, связан с входом управления сдвигом регистра маски, второй выход блока управления подключен к входу управления опросом блока ассоциативной памяти, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены второй блок ассоциативной памяти, мультиплексор, m групп по п элементов РАВНОЗНАЧНОСТЬ 30 (ттт — коды граничных значений гистограммы, n — количество анализируемых выборок), m групп по n RS-триггеров, m групп по n D-триггеров, тп-1 групп по и элементов НЕРАВНОЗНАЧНОСТЬ, группа из и элементов НЕ, m+1 комби-национных сумматоров на и входов, m+1 регистров, причем второй выход блока управления подключен к входу управления опросом второго блока ас- 40 социативной памяти, выходы которoro соединены с первой группой информаци,онных входов мультиплексора, информационные выходы регистра маски подключены к входам маскирования второго 45 блока ассоциативной памяти, выход старшего разряда регистра маски соединен с управляющим входом мультиплексора и входом пуска блока управления, третий выход блока управления подключен к первым входам установки

RS-триггеров групп, четвертый вьтхоц блока управления соецинен с входами синхронизации регистров, каждый >-Й выход (i = 1 n) мультиплексора соедиЭ

55 нен с первыми входами i-х элементов

РАВНОЗНАЧНОСТЬ групп и информационными входами i D-триггеров групп соответственно, выходы каждого элемента РАВНОЗНАЧНОСТЬ групп подключены к вторым входам установки RS-триггеров групп соответственно, выходы которых подсоединены к входам синхронизации П-триггеров групп соответственно, каждый j-й выход (где

1,n) первого блока ассоциативной памяти соединен с вторыми входами элементов РАВНОЗНАЧНОСТЬ j-й группы, выходы D-триггеров первой группы подключены к входам первого комбинационного сумматора и первым входам элементов НЕРАВНОЗНАЧНОСТЬ первой группы, выходы D-триггеров р-й группы (р = 2, m-1) соединены с первыми входами элементов НЕРАВНОЗНАЧНОСТЬ р-х групп и вторыми входами элементов

НЕРАВНОЗНАЧНОСТЬ (р- 1)-х групп, выходы D-триггеров m-й группы подключены к вторым входам соответствующих элементов НЕРАВНОЗНАЧНОСТЬ (m-1)-й группы и входам элементов НЕ группы, вы! ходы которых соединены с входами (m+1)-ro комбинационного сумматора, выходы элементов НЕРАВНОЗНАЧНОСТЬ

q-й группы (q = 1, тп-1) соединены с входами (ц+1)-го комбинационного сумматора, выходы комбинационных сумматоров группы подключены к информационным входам регистров соответственно, выходы которьгх являются выходами устройства, вход сброса устройства соединен с входом сброса регистра маски, входами сброса RS-триггеров групп и входом сброса блока управления, вторая группа информационных входов мультиплексора подключена к источнику потенциала 1

2. Устройство по п. 1, о т л и— ч а ю щ е е с я тем, что блок управления содержит генератор импульсов, триггер, три элемента задержки, элемент И, причем вход пуска блока является входом установки в "1" триггера, выход которого подсоединен к первому входу элемента И, выход кото рого является вторым выходом блока и подключен к входу первого элемента задержки, выход которого является первым выходом блока, выход генератора импульсов подключен к второму входу элемента И, второй вход блока подключен к входу сброса триггера и входу второго элемента задержки, выход которого является третьим выходом блока и соединен с входом третьего элемента задержки, выход которого является четвертым выходом блока.! 6882h !

Фиг.1

1688261

uzo

Редактор М.Келемеш

Заказ 3710 Тираж Подписное

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

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

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

Ug

Оу

Составитель Д.ухтверон

Техред М.Дидык Корректор С Некмар