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

(21) 4615400/24

С22) 02.12.88

(46) 30.10.91. Бюл. N° 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 быть использовано для построения высокопроизводительных систем автоматизированной обработки результатов измерений, выполненных на узлах с высокой степенью интеграции. Цель изобретения - повышение быстродействия устройства. Устройство для построения гистограммы содержит регистр маски, два блока ассоциативной памяти, первый мультиплексор, m групп по п элементов РАВНОЗНАЧНОСТЬ (т - количество пределов построения гистограммы) , га групп по п D-триггеров, RS- триггеров, комбинационный сумматор, ,т-2 групп по п элементов НЕРАВНОЗНАЧНОСТЬ, группу элементов НЕ, К регистров. 1 з.п.ф-лы, 3 ил.

(Л

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

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

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

Устройство для построения гистограммы содержит регистр 1 маски, первый блок 2 ассоциативной памяти, первый выход 3 блока управления, второй блок 4 ассоциативной памяти, мультиплексор 5, m групп по п элементов РАВНОЗНАЧНОСТЬ 6 (т - коды граничных значений гистограммы, п - количество

анализируемых выборок), m групп по п D-триггеров 7, m групп по п RS-триг- геров 8, т+1 комбинационных сумматоров 9, т-1 групп по п элементов НЕРАВНОЗНАЧНОСТЬ 10, группу из п элементов НЕ 11, т+1 регистров 12, вход 13 сброса устройства, вход 14 пуска блока управления, блок 15 управления, вход 16 сброса блока управления, второй 17, третий 18 и четвертый 19 выходы блока управления, причем блок 15 управления содержит триггер 20, эле менты 21-23 задержки, генератор 24, элемент И 25. Регистр 1 маски подключен к входам маскирования первого , блока 2 ассоциативной памяти, п выходов совпадения второго блока 4 ассоциативной памяти связаны с первыми входами мультиплексора 5, каждый 1-й

О 00 00

го

0

(I 1,n)}выход которого подключен к первому входу 1-го элемента 6; РАВНОЗНАЧНОСТЬ каждой j-й группы (где j 1,n, m - количество ячеек перво- го блока 2 ассоциативной памяти) и информационному входу 1-го D-тригге- ра 7;: j-й группы, каждый j-й выход совпадения первого блока 2 ассоциативной памяти подсоединен к вторым входам всех элементов РАВНОЗНАЧНОСТЬ 6j : j-й группы, выход каждого 1-го элемента РАВНОЗНАЧНОСТЬ 6;j j-й группы связан с первым входом уста- , новки 1-го RS-триггера 8j : j-й груп- пы, выход каждого i-ro RS-триггера 8 j-й группы подключен- к входу синхронизации 1-го D-триггера 7 j1 j-й группы, выходы группы D-триггеров

7 , подсоединены к входам комбинационного сумматора 9 и первым входам элементов НЕРАВНОЗНАЧНОСТЬ 10 группы, выходы элементов р-й группы (р 2, га-1) D-триггеров /, связа- ,ны с первыми входами элементов НЕРЛВНОЗНАЧНОСТЬ Ю ;„ р-х групп и вторы- Ми входами элементов НЕРАВНОЗНАЧНОСТЬ Ю, р (р-1)-х rpyniij выходы т-й группы П-триггеров 7; ж подключены к вторым входам элементов НЕРАВНОЗНАЧНОСТЬ 10 , n, (m-l)-n группы и входам группы элементов НЕ 11, выходы которых связаны с входами (т+1)-го комбинационного сумматора 9nvH, выхо- ДЪ1 элементов НЕРАВНОЗНАЧНОСТЬ 10j|0 (q 1, m-1) групп подключены к уходам (о+1)-х комбинационных сумма-торов 9л-и , выходы К-х комбинационных сумматоров 9 | подсоединены к информационным входам К-х регистров 12|, выходы которых являются выходам устройства, вход 13 управления началом работы устройства связан г входами сброса всех RS-триггеров 8 j j все Групп, входом установки в исходное состояние регистра 1 маски и первым Мходом 14 блока 15 управления, выход Йереполнения при сдвиге регистра 1 маски подключен к управляющему входу мультиплексора 5 и втэрому входу 16 блока 15 управления, первый выход 3 которого подсоединен к входу управления сдвигом регистра 1 маски, второй Выход 17 блока 15 управления связан : входом управления опросом блока 2 ассоциативной памяти, третий выход 18 блока 15 управления подсоединен к вторым входам установки всех RS-триггеров 8| всех групп, четвертый вы

5

0

0

5

5

0

5

0

5

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

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

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

Сигнал по входу Начало работы 13 поступает на вход установки в исходное состояние регистра 1 маски, где устанавливается число с единицей в старшем разряде и нулями в остальных, поступают на входы сброса всех RS- триггеров Я всех групп, устанавливая их в нулевое состояние, и через вход 14 блока 15 управления устанавливает в единичное состояние триггер 20. После установки триггера 20 импульсы с генератора 24 импульсов начинают проходить через элемент И 25 и вызывают через выход 18 блока 15 управления обращение к блоку 2 ассоциативной памяти и на вход опроса блока 4 ассоциативной памяти. На выходах совпадения блоков 2 и 4 ассоциативной памяти формируются сигналы совпадения в выделенном (старшем) разряде с содержимым регистра 1 маски, и эти сигналы выдаются на выходы совпадения. Информация с выхода блока 4 ассоциативной памяти передаётся

5

на выходы первого мультиплексора 5. Элементы РАВНОЗНАЧНОСТЬ 6; групп элементов РАВНОЗНАЧНОСТЬ реализуют следующую функцию: на вход 1-го (з Т7п) элемента РАВНОЗНАЧНОСТЬ б;,: j-й (j 1,т), группы поступают сигналы совпадения 1-го слова второго блока 4 ассоциативной памяти и j-ro слова блока 2 ассоциативной памяти. Если значения анализируемых разрядой этих слов не совпадают, то на выходе 1-го элемента РАВНОЗНАЧНОСТЬ 6jJ j-й группы сформировано нулевое значение, которое устанавливает в единичное состояние 1-й RS-триггер 8 ji j-й группы, который,в свою очередь, передним фронтом выходного сигнала осуществляет запись состояния 1-го выхода совпадения блока 4 ассоциативной памяти в 1-й D-триггер 7jJ j-й группы. Единичное значение этого триггера означает, что 1-е число блока 4 ассоциативной памяти больше j-ro числа (предела) блока 2 ассоциативной памяти. Если же разряды 1-го числа блока 4 ассоциативной памяти и j-ro числа блока 2 ассоциативной памяти совпадают, то на выходе 1-го элемента РАВНОЗНАЧНОСТЬ 6{j j-й группы сформировано единичное значение и j-й RS-триггер 8 { | j-й группы остается в нулевом состоянии. Сигнал с выхода элемента И 25, вызывающий сигнал опроса блоков 2 и 4 ассоциативной памяти, после окончания опроса через первый элемент 21 задержки осуществляет сдвиг содержимого регистра 1 маски в сторону младших разрядов, который теперь вызывает опрос следующего разряда, при котором схема работает аналогично, за исключением того, что появление единичных сигналов на выходе элементов РАВНОЗНАЧНОСТЬ 6 Jj j-й групп вызывает установку соответствующего RS-триггера 8j j j-й группы только в том случае, если он не был установлен ранее, т.е. фиксируется различие в наиболее старшем разряде. Устройство работает таким образом до тех пор, пока после 1-го (где 1 - разрядность числа блоков 2 и 4 ассоциативной памяти) импульса с выхода элемента И 25 не проанализированы младшие разряды блоков 2 и 4 ассоциативной памяти и через первый элемент 21 задержки не осуществился сдвиг содержимого регистра 1 маски, при котором на выходе переполнения сформиру1

882616

ется единичное значение, которое подает на выходы первого мультиплексора 5 единичные значения с его второ- с го входа, сбрасывает триггер 20 и через второй элемент 22 задержки осуществляет установку в единичное состояние RS-триггеров 8 j-x групп, при которой из нулевого в единичное

JQ состояние переходят только те RS- триггеры, которые не были установлены ранее, т.е. соответствующие совпадению 1-го числа блока 4 ассоциативной памяти и j-ro числа блока 2 ассоциативJ5 ной памяти, эти RS-триггеры устанавливаются в единичное состояние и передним фронтом выходного сигнала осуществляют запись в соответствующие D-триггеры j-x групп единичных

20 состояний с выхода первого мультиплексора 5. Таким образом, единичное состояние 1-го D-триггера 7{1 j-й группы обозначает, что 1-е число блока 4 ассоциативной памяти больше или

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

Единичное состояние D-триггеров 7.1 первой группы свидетельствует о превышении числами верхнего предела, количество превысивших чисел определяется первым комбинационным сумматором 9.1.

30

35

Если 1-й D-триггер 7- s-й груп

V 5 пы установлен в единичное состояние,.

а 1-й D-триггер 75- (з-1)-й группы установлен в нулевое состояние, то на выходе 1-го элемента НЕРАВНОЗНАЧНОСТЬ (з-1)-й группы присут- ствует единичный сигнал, свидетельствующий о нахождении 1-го числа блока 2 ассоциативной памяти между s-ми и (s-l)-M пределами, хранящимися в блоке 4 ассоциативной памяти, включая (з-1)-й предел; количество чисел, передающих в указанный интервал, подсчитывается s-м комбинационным сумматором 9с .

Числа, для которых соответствующие D-триггеры 7« m-й группы содержат нулевые значения потенциалов, имеют значения ниже нижнего предела} их количество с использованием группы

элементов НЕ 11 подсчитывается комбинационным сумматором 9(т4.

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

Последовательность выдачи сигналов иллюстрируется временными диаграмма- Ми (фиг.З).

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

выход (i 1,n) мультиплексора соединен с первыми входами 1-х элементов РАВНОЗНАЧНОСТЬ групп и информационными входами 1-х D-триггеров групп соответственно, выходы каждого эле

5 0 5

5

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

ъ

Я

г±

Т

1

6

в

№ И Htvi ЩЩ

JL

Я

I

п

д

п - п

д

д

t

д

t

д

Фиг.З

t