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

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

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

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

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

Устройство содержит N регистров 1 -1 границ интервалов, выходами соединенных с входами соответствующих N М-разрядных блоков сравнения, каждый из которых содержит L элементов 2 сравнения, первый, и второй вы- ходы каждого элемента 2. (,N; j 1 ,Ь-1 ) сравнения подключ ены через соответственно первый и второй 4| триггеры из (L-1 ) групп к управля юищм входам последующих элементов сравнения, выходы Больше и Меньше каждого элемента 2- блока сравнения подключены соответственно к входам элементов И 5 и 5-,, группы (N+1) элементов И, выход каждого из элементов И 5, группы подключены к счетному входу соответст- вукицего счетчика 6,-6„. группы (N+1) счетчиков, информационный вход 7 устройства соединен с входами приемного регистра 8, M/L выходов старших разрядов которого подключены к

2 -2 п сравневхода м всех элементов ния (М - разрядность поступающих на вход 7 чисел), остальные разряды регистра 8 соединены с входами первого из (L-1) промежуточных регистров 9. - 9. , выходы каждого из которых соединены с входами соответствующих полнительных регистров ,., , каждый регистр 9. и lOj (j l,L-1 ) имеет (L-j ) M/L разрядов, причем M/L выходов старших разрядов каждого дополнительного регистра 10j подключены к входам элементов 2 сравнения, а остальные разряды каждого регистра Юр (, L-2) соединены с входами установки промежуточного регистра 9

t + i

Тактовый

вход 11 соединен с входами управления приемом кода регистров 8 и 10, счетным входом счетчика 12 числа формирований гистограмм и входом первого элемента 13 задержки, выход которого связан с входами управления приемом кода регистров 9 и входом второго элемента 14 задержки, выход которого подключен к управляющим входам всех (L-1 ) групп триггеров 3

и 4, счетчиков 6 и входам (N+1 ) элементов И 5 группы.

Элемент сравнения (фиг.2) содержит элементы И-НЕ 15, элементы ИЛИ- НЕ 16, элементы ИЛИ 17, элементы НЕ 18.

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

В исходном состоянии на регистрах

1 -1 хранятся упорядоченные коды

1

границ интервалов гистограммы,счетчики 6 и 12, как и регистры 8-10, обнулены. С поступлением тактового

импульса на вход 11 осуществляется прием поступившего М-разрядного кода числа по входу 7 на регистр 8 и прибавление единицы к содержимому счет- чика . В промежутке времени, определяемом первым элементом 13 задержки, производится сравнение M/L старших разрядов поступившего числа с соответствующими разрядами регистров 1. Указанное сравнение выполняется

на соответствующих первых элементах 2-2 сравнения всех блоков сравнения. Если код указанных разрядов регистра 8 больше кода соответствующих разрядов регистра 1, то единичный

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

соответствующего элемента сравнения, на его обоих выходах формируются нулевые потенциалы. Сигналом с выхода элемента 14 задержки потенциалы с выходов элементов сравнения

переписываются на соответствующие

триггеры 3-3, 4,,-4 групп. Сигналом с выхода элемента 13 задержки производится перепись (М -(L-1 ) M/L)нпад- ших разрядов регистра В на регистр 9,.

С поступлением очередного тактового импульса на вход 11 на регистр 8 по входу 7 записывается новое (второе) число, а содержимое регистра 9 переписывается на регистр 10 , к содержимому счетчика 12 прибавляется единица. За период, определяемый элементом 13 задержки, производится сравнение M/L старших разрядов второго из поступивших чисел с соответствующими разрядами регистров 1 на элементах и сравнение M/L разрядов (с M(L-2)/L-ro по М(Ь-1)/Ь-й) первого из поступивших чисел, хранящегося на регистре 10, с соответствующими разрядами регистров 1 на элементах 2-2 сравнения, при этом на управляющий входы последних поступаз:-з;,и4;-

ют сигналы с триггеров

групп так, что каждый из элементов производит сравнение поступа2 1 П

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

при этом на элементах 2-2 сравниваются M/L старших разрядов числа, поступившего последним (хранящимся на регистре 8), с соответствующими разрядами регистров 1, на каждом из элементов (, L) производится сравнение разрядов с (M(L-k )/L)-ro по (M(L-k+1 )/L}-H k-го из поступивших чисел (считая первым последнее

fO из поступивших чисел) с соответствующими разрядами регистров 1. Сигналом с выхода элемента 13 задержки содержимое разрядов, не участвовавших в сравнении, всех чисел, кроме L-ro

15 (все разряды которого приняли участие в сравнении), переписывается с регистров 8,10 -10L-J на регистры 9,- 9|. соответственно. Сигналом с выхода элемента 14 задержки результаты

20 сравнения (L-1 ) чисел (кроме L-ro) фиксируются с выходов элементов 2 сравнения на соответствуюш 1х триггерах 3 и 4 групп и, кроме того, открываются элементы И 5 группы, еди(т.е. если сравнение старших M/L раз- - ничный сигнал, сформированный на выходе одного из элементов И 5 (г 2, п ), соответствует нахождению L-ro числа между пороговыми значениями гистограммы, зафиксированными на регистрах 1., и если единичный сигнал зафиксирован на выходе элемента И 5. тому, ного порога, записанного на регистре

рядов кода поступившего первым числа с соответствующими разрядами соответствующего регистра 1 не выявило большего из них), в противном случае на выходах упомянутых элементов сравнения формируются потенциалы, идентичные поступающим на управляющие входы. По сигналу с выхода элемейта 13 задержки несравнившиеся разряды первого и второго чисел с регистров соответственно 8 и 10 записываются на регистры 9 и 9 соответственно. По сигналу с выхода элемента 14 задержки результаты сравнения фиксируются на соответствующих триггерах 3 и 4 групп.

30

, группы, то это соответствует что L-e число меньше минималь35 1 ., если единичный сигнал появляется на выходе элемента И группы, то это соответствует тому, что L-e число больше наибольшего порога, зафиксированного на регистре 1,.

40 Единичным сигналом с выхода элемента И 5 группы производится увеличение на единицу содержимого соот- - ветствующего счетчика 6.

В дальнейшем работа устройства

повторяется по описанному принципу так, что одновременно обрабатывается L поступивших последовательно на вход 7 чисел. По тактовому импульсу, подаваемому на вход 11, производится прибавление единицы к содержимому счет- чика 12 и запись вновь поступившего числа на регистр 8, а также перепись не обработанных на предшествукмцих тактах работы разрядов (L-1 ) чисел, поступивших ранее с регистров .,

соответственно.

о о

1 и-(

на регистры 10 -10j., За период, определяемый элементом 13 задержки, производится сравнение частей L словлС пороговыми значениями.

при этом на элементах 2-2 сравниваются M/L старших разрядов числа, поступившего последним (хранящимся на регистре 8), с соответствующими разрядами регистров 1, на каждом из элементов (, L) производится сравнение разрядов с (M(L-k )/L)-ro по (M(L-k+1 )/L}-H k-го из поступивших чисел (считая первым последнее

O из поступивших чисел) с соответствующими разрядами регистров 1. Сигналом с выхода элемента 13 задержки содержимое разрядов, не участвовавших в сравнении, всех чисел, кроме L-ro

5 (все разряды которого приняли участие в сравнении), переписывается с регистров 8,10 -10L-J на регистры 9,- 9|. соответственно. Сигналом с выхода элемента 14 задержки результаты

0 сравнения (L-1 ) чисел (кроме L-ro) фиксируются с выходов элементов 2 сравнения на соответствуюш 1х триггерах 3 и 4 групп и, кроме того, открываются элементы И 5 группы, еди- ничный сигнал, сформированный на выходе одного из элементов И 5 (г 2, п ), соответствует нахождению L-ro числа между пороговыми значениями гистограммы, зафиксированными на регистрах 1., и если единичный сигнал зафиксирован на выходе элемента И 5. тому, ного порога, записанного на регистре

30

сигнал, сформированный на выдного из элементов И 5 (г ), соответствует нахождению исла между пороговыми значениятограммы, зафиксированными на рах 1., и если единичный зафиксирован на выходе элемен. орога, записанного на регистре

, группы, то это соответствует что L-e число меньше минималь

1 ., если единичный сигнал появляется на выходе элемента И группы, то это соответствует тому, что L-e число больше наибольшего порога, зафиксированного на регистре 1,.

Единичным сигналом с выхода элемента И 5 группы производится увеличение на единицу содержимого соот- ветствующего счетчика 6.

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

|

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

|

Устройство для формирования гистограммы, содержащее N регистров границ интервалов, группу из N+1 элементов И, счетчик числа формирований, гистограмм, группу из N+1 счетчиков, N М- разрядных блоков сравнения, приемный

регистр, информационный вход которого является информационным входом устройства, M/L выходов старших разрядов приемного регистра подключены к первым информационным N входам М-разряд- ных блоков сравнения, вторые информационные входы которых соединены соответственно с разрядными выходами N регистров границ интервалов, выходы

тельного регистра подключены к первым информационным входам ( )-х элементов сравнения всех блоков сравнения, а выходы остальных разрядов каждого t-ro дополни- тельного регистра (, L-2 ) соединены с разрядными входами (t+1)-ro промежуточного регистра, 11нформационные входы первого промежуточного Больше и Меньше каждого i-ro бло- fO регистра подключены к выходам М -M/L младших разрядов приемного регистра, выходы Больше и Меньше

ка сравнения (, N) соединены соответственно с входами i-ro и (i+l)-ro элементов И группы, выходы элементов И группы подключены к счетным входам

всех L-1 элементов сравнения соединены с информационными входами соот

соответствунщих счетчиков группы,вход 15 ветствующих триггеров групп, выходы

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

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

действия, каждый из N М-разрядных блоков сравнения содержит L элементов сравнения, а в устройство введены L-1 групп триггеров по 2 N в каждой группе, два элемента задержки, L-1 дополнительньк и L-1 промежуточ-у 25 та задержки соединен с входом управ- ных регистров, число разрядов каждого ления приемом кода промежуточных j-ro (, L-1) из которых равно регистров непосредственно, а че- (L-J )«M/L, при этом выходы каждого рез второй элемент задержки - с промежуточного регистра подключены управляющими входами триггеров к входам соответствующего дополни- 30 групп, с соответствующими входа- тельного регистра, M/L выходов стар- ми элементов И группы и счетчи ших разрядов каждого j-ro дополни- ков- группы.

тельного регистра подключены к первым информационным входам ( )-х элементов сравнения всех блоков сравнения, а выходы остальных разрядов каждого t-ro дополни- тельного регистра (, L-2 ) соединены с разрядными входами (t+1)-ro промежуточного регистра, 11нформацивсех L-1 элементов сравнения соединены с информационными входами соот20

триггеров каждой группы соединены соответственно попарно с первым и вторым управляющими входами последующих элементов сравнения, при этом входы управления приемом кода приемного и дополнительных регистров, а также вход nepBOl o элемента задержки объединены и являются тактовым входом устройства, выход первого элемен25 та задержки соединен с входом управ- ления приемом кода промежуточных регистров непосредственно, а че- рез второй элемент задержки - с управляющими входами триггеров 30 групп, с соответствующими входа- ми элементов И группы и счетчи ков- группы.

Изобретение относится к рычисли- тельной и измерительной технике и может быть использовано для анализа распределения случайных величин и процессов. Целью изобретения является повышение быстродействия. В схеме устройства каждый из N блоков сравнения состоит из L элементов сравнения. При этом каждый элемент сравнения, кроме последнего, соединение информационными входами соответствующей пары триггеров. Введено (L-1) дополнительных и (L-1) промежуточных регистров. Устройство также содержит регистр, элементы задержки, группы (N+1 ) элементов И, счетчиков, счетчик числа формирований, N регистров границ интервалов. Предлагаемое устройство позволяет повысить скорость обработки данных за счет использования конвейерных принципов обработки поступаюпщх чисел при построении гистограммы. 2 ил. 9 сл ю со 00 о: оо

Составитель Э.Сечина Редактор Е.Папп Техред Л.Сердюкона. Корректор О.Луговая

Заказ 891/52 Тираж 673Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д.4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная,4