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

вход устройства соединен с- синхронизиpye ыми входами операционного блока каждого сумматора, каждого регистра результата, регистра логических условий и блока микропрограммного управления, второй синхронизирующий вход устройства соединен с синхронизируящими входа1 01 блоков памяти, причем операционный блок содержит два мультиплексора условий, два регистра данных, мультиплексор данных, элемент НЕ, два деши(}ч атора, две группы элементов НЕ, узел задания адреса, группу элементов ИЛИ и регистр адреса, выходы разрядов которого являются адресньм выходом операционного блока, информа1щонный вход первого мультиплексора условий является первым информационньм входом операционного блока, второй информационный вход которого соединен с информационнюш входами первого и второго регистров данных, выходы разрядов первого регистра данных является информационным выходом операционного блока, выход логических условий которого соединен с выходом второго мультиплексора условий, а вход кода операции соединен с разрешающими входами первого и второго мультиплексоров условий, мультиплек сора данных, первого и второго дешифраторов первого регистра данных

96898 ,

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

УСТРОЙСТВО ДЛЯ ОБРАБОТКИ ДАННЫХ ГИСТОГРАММ, содержащее первый блок памяти, первый сумматор, блок микропрограммного управления, выход микрокоманд ifOToporo Соединен с информационным входом первого блока памяти, отличающееся тем, что, с целью повьшения быстродействия, в него введены («V-1) блоков памяти, () сумматоров , ( формирователей прямоугольных импульсов, регистров результата, регистр логических условий и операционный блок, причем первый информационный вход каждого jcyMMaTopa соединен с выходом соответствующего формирователя прямоугольных импульсов, второй информационный вход первого сумматора соединен с информационным выходом операционного блока, второй информационный вход (i-fl)-ro сумматора соединен с выходами разрядов 1-го регистра результата, где t « 1, (-1, информационный выход калсдого сумматора соединен с информационным входом соответствующего регистра результата, знаковый выход - с входом соответствующего разряда регистра логических условий, ин формационный выход каждого блока памяти - с входом соответствующего формирователя прямоугольных импульсов, а информационный вход подключен к выходам разрядов соответствуюп1его регистра результата, выходы разрядов регистра логических условий соединены с перв1 1м информационным входом операционного.блока, второй информационный вход которого является информационным входом устройства, адресный выход i операционного блока соединен с адресным входом каждого блока памя(Л ти, выход логических условий. с первым входом логических условий блока микропрограммного управления, второй и третий входы логических условий которого являются соответственно первЕЯм и вторым входами задания режима работы устройства, ;о а выход микрокоманд блока микропрограммного управления соединен с вхо00 дами Кода операций операционного :& блока, входами управления записью00 чтением каждого введенного блока памяти, входами разрешения каждого формирователя прямоугольных импульсов, входами управления каждого сумматора, входами стробирования каждого регистра результата, с первым и вторым выходами состояний устройства, вход команд блока микропрограммного управления является входом номера режима обработки устройства, установочный вход - входом установки исходного состояния уст.ройства, первый синхронизирующий

1

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

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

На фигЛ-З представлена схема предлагаемого устройства; на гЛ пример работы устройства.

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

мультиплексор 16 условий, мультиплексор 17 условий, элемент НЕ 18, дешифраторы 19 и 20, группы 21 и 22 элементов НЕ, узел 23 задания адреса, группа 24 элементов ИЛИ, регистр 25 адреса, входы и выходы 26-38 устройства, блок 39 микропрограммного управления, операционный блок 40.

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

Предварительно с входа 32 установки устройства в исходное состояние на установочный вход узла 9 поступает сигнал отрицательной полярности. На выходе узла 9 устанавливается нулевой адрес узла 10 памяти. . Извлеченная микрокоманда из узла 10 записывается в первый 11 н второй

3

12 регистры микрокоманд. В регистре 11 содержится управляющее поле микрокоманд, в регистре 12 - адрес перехода к подпрограмме. Узел 7 па основе информационного сигнала, поступающего с мультиплексора 6, и управляющих сигналов, поступающих с регистра 11, формирует тип выполняемой инструкции. В исходном состоянии с помощью мультиплексора 6 опр шивается вход 33 логических условий по состоянию которого проверяется наличие записанной команды в регистре 8 команд. При нулевом сигнале на входе 33 логических условий узел 7 формирует инструкцию перехода по адресу, записанному в регистре 8, а при единичном сигнале - инструкцию перехода по счетчику микрокоманд, входящего в состав узла 9. Причем счетчик микрокоманд узла 9 может работать как в режиме инкрементирования (т.е. увеличения содержимого на единицу), так и в режиме повторения предыдущего адреса (режим задается управляющим полем микрокоманды) . В исходном состоянии счетчик узла 9 работает в режиме повторения предыдущего адреса.

Основные команды, выполняемые устройством, задаваемые с помощью внешнего устройства, следующие: суммирование элементов гистограммыj вычитание элементов гистограммы; тип выполняемой операции, например, медианная фильтрация, эквализация гистограммы, определение минимального или максимального значений гистограммы.

При выполнении команд суммирования или вычитания элементов гистограммы с помощью мультиплексора 6 проверяется состояние входа 34 логических условий, по состоянию которого определяется наличие записанных данных в первый 13 и второй 14 регистры данных. При нулевом сигнале на входе 34 логических условий узел 7 формирует инструкцию перехода узла 9 по адресу регистра 12, т. обработка данных, записанных в первом 13 и втором 14 регистрах данных разрешена. Иначе узел 7 формирует инструкцию перехода по содержимому счетчика микрокоманд узла 9, т.е. реализуется режим ожидания (повторная проверка состбяния входа 24 логических условий). С помощью управлянидих сигналов на выходах 36 и 37

96898 4 .

состояния устройство оповещает внешние устройства .соответственно о режиме функционирования устройства (ожидание команды/работа) и о готрв5 ности (или неготовности) устройства принять для обработки входные данные. Гистограмма статическрго распределения строится с помощью простого алгоритма: на каждом шаге выборки отсчета измеряемого сигнала Б содержимое ячейки памяти с адресом изменяется на единицу.

При построении гистограммы посредством соответствующего управляющего поля микрокоманды, записанной в регистре 11, осуществляется запрет работы дешифраторов 19 и 20, адрес блоков 1 памяти определяется узлом

20 23 задания адреса в соответствии с записанной информацией в регистре 14. Сформированный адрес записывается в регистр 25 адреса. В блоках 1 памяти параллельно формируется

25 гистограмм, причем в с, -блоке 1 памяти формируется 2 точньк отсчетов гистограммы, в то время как в остальных блоках 1 памяти строятся грубые отсчеты гистограммы статистического

2Q распределения. Число отсчетов гистограммы, формируемое в 1 -памяти, определяется как 2, где

1 1 и с, , соответственно емкость блока 1 памяти равна 2. Адрес i- блока 1 памяти.АJ определяется следующим образом: ()

где i :},-; при 1 i ; с . В соответствии с адресами А. блоков 1 памяти осуществляется считывание содержи мого соответствуюпр х 1 ячеек памяти

40 и изменение содержимого ячеек на единицу в сумматорах 3. Преобразованная в сумматорах 3 информация записывается в регистры 4, а в следующем машинном цикле осуществля45ется запись содержимого регистров 4 в соответствующие .блоки 1 па1-1яти. Режимы Чтение и Запись блоков 1 памяти, операции инкрементирования на единицу и декрементирования на единицу в сумматорах 3, а также сигналы разрешения вьщачи информации регистрами 4 и формирователями

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

5

Рассмотрим функционирование уст

ройства для обработки гистограмм в режиме поиска медианы гистограммы статического распределения.

Медианой статического распределения , j-m ,-М т H,-Ni п N является элемент Dij , для которого существует (L-1)/2 элементов, меньших или равных ему по величине, и (L-1)/2 элементов, больших или равных ему по величине, где L(2M+l)

(2N+1). Поиск медианы в устройстве осуществляется следующим образом. В соответствии с управляющим полем микрокоманды, записанной в регистре 11, в уэле 23 формируется нулевой адрес обращения к блокам 2 памяти. Из регистра 13 данньсх в первый сумматор 3 заносится величина (L-l)/2, в то время как в остальных сумматорах 3 устанавливаются нулевые величины. Далее выполняется операция вычитания из содержимого нулевой ячейки i-го блока 1 памяти содержимого -го сумматора 3; при этом формирователи 2 открыты для передачи информации. Результаты операции вычитания заносятся в соответствующие регистры 4, а содержимое знака вых разрядов сумматоров 3 заносится в регистр 5 логических условий. С помощью мультиплексора 16 условий опрашивается значение знакового разряда первого сумматора 3. Выходное значение мультиплексора 16 подается через элемент НЕ 18 на информационный вход дешифратора 19 и на информационный вход мультиплексора 17. Если знаковый разряд первого сумматора 3 равен единице, т.е. результат операции вычитания отрицательньй, то с помощью депшфратора 19 и соответствующего элемента из группы 21 элементов НЕ осуществляется маскирование по ИЛИ cj.-ro разряда адреса узла 23, означающее, что медиана содержится во второй половине гистограммы, а ,-й разряд адреса равен единице. При нулевом знаковом разряде первого сумматора 3 адрес узла 23 не изменяется, т.е. медиана расположена в первой половине гистограммы статистического распределения. Последующие (ц,-1) циклов разрядного определения адреса в узле 23 для определения медианы имеют следующий вид.В { -и сумматор 3 заносится содержимое t -1 регистра 4.

968986

При единичном значении разряда адреса dj.,, id iq-1, определенного в предьщущем цикЛе в «у суммато pax 3, выполняется операция суммиJ рования содержимого i-го сумматора 3 с содержимым выбранной ячейки -го блока 1 памяти по адресу, определенному в предьадзгщем цикле, где i 1, { . При нулевом значении разto ряда адреса , определенного в предыдущем цикле, с помощью мультиплексора 17, дешифратора 20, соответствуиицего элемента из группы 22 элементов НЕ и соответствующего эле(5 мента из группы 24 элементов ИЛИ в регистре 25 адреса устанавливается значение разряда адреса «, равное единице. В сумматорах 3 выполняется операция вычитания содержимого -го

20 сумматора 3 и соответствующей ячейки

1-го блока 1 памяти. По величине знакового разряда (q-d+1)сумматора 3 определяется истинное значение с разряда блока 1 памяти. Таким образом,

25 по построенным грубым и точным отсчетам гистограмм в блоках 1 памяти поиск медианы осуществляется всего за циклов сравнения. Код управления мультиплексора 16, мультигшек30 сора 17, дешифраторов 19 и 20, узла 23 задается соответствующими полями микрокоманд, записанных в узле 10. Результат поиска медианы считывается с регистра 25.

Рассмотрим пример поиска медианы

для четырехразрядных входных данных. Устройство содержит четьчре восьмиразрядных сумматоров 3 и четыре блока 1 памяти. На фиг.4 приведены грубые и точные отсчеты гистограммы

для произвольного статистического распределения для окрестности 9«9 элементов. В исходном состоянии узлом 23 в регистре 25 устанавливается нулевой адрес . В первый сумматор 3 заносится величина (9-9+1). Результат операции вычитания в первом сумматоре 3 содержимого ячейки памяти блока 1 памяти по адресу 0000 и содержимого сумматора равен Е, 60-41 19. Результаты операции вычитания в осталь ных сумматорах 3 не приводятся, так как данные операции являются избыточными для данного цикла сравнения. Так как результат О, то знаковый разряд первого сумматора 3 р11век нулю и результирующее значение , Ъо втором цикле сравнения определя7

ется а. Поскольку , то предварительно устанавливается а 1 и во втором сумматоре 3 вьтолня1тся операция вычитания F, и содержимого ячейки памяти по адресу 0100 F -19-39 -20. Если , то истинное значение а,1. В третьем цикле сравнения выполняется операция суммирования в третьем сумматоре 3 значения F2 с содержимым ячейки третьего блока 1 памяти по адресу 0100 Р. -20+ . Так как Рэ70, то а 0. В четвертом цикле сравнения Аосле предварительной установки значения в четвертом сумматоре 3 выполняется операция вычитания из F, содержимого четвертого блока 1 памяти . так как „ ,0, то . Результирующий адрес, сформи968988

Рованный в регистре 25 равен 0100 и соответственно величина медианы iJ,. с помощью данного устройства для обработки гиcтoгpa lы за о, 5 поразрядных сравнений по построенным грубым и точным отсчетам гистограмм вьтолняются и другие вычислительные операции статистической обработки информации, например. 10 зквализация гистограммы, Ъпредедение минимального и максимального значений статистического распределения. При выполнении операции эквализации гистограммы осуществляется 5 поразрядное тестирование входного числа, записанного в регистре 14 данных, мультиплексором 15 с целью определения адресов блоков 1 памяти в процессе поиска результата.

Фиг. 1

фиг. 2

itB

J tff - /S

16

В

13

21

23

i

fS

№

гг

20

I