Устройство для обработки данных гистограмм

 

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

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

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

ЕЕСГ1УЬЛИН (19) (И) (50 4 С 06 F 15/36 (21) 3763226/24-24 (22) 28.06.84 (46) 07.12.85. Бюл. и 45 (71) Ленинградский ордена Трудового

Красного Знамени институт точной механики и оптики (72) К,И.Кучеренко, Ю.Н.Матвеев и Е.Ф,Очин (53) 681.3:519.2(088,8) (56) Авторское свидетельство СССР и 995097, кл. С 06 F 15/36, 1981.

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

Ф 830399, кл. G 06 F 15/36, 1979. (54) (57) УСТРОЙСТВО ДЛЯ ОБРАБОТКИ

ДАННЫХ ГИСТОГРАИИ, содержащее первый блок памяти, первый сумматор, блок микропрограммного управления, выход микрокоманд которого coåäèнен с информационным входом первого блока памяти, о т л и ч а ю щ ее с я тем, что, с целью повышения быстродействия, в него введены (q-1) блоков памяти, (q,-1) сумматоров, q формирователей прямоугольных импульсов, < регистров результата, регистр логических условий и операционный блок, причем первый информационный вход каждого,сумматора соединен с выходом соответствующего формирователя прямоугольных импульсов, второй информационный вход первого сумматора соединен с информационным выходом операционного блока, второй информационный вход (1+1)-го сумматора соединен с выходами разрядов I --ro регистра результата, где i1, q,-1, информационный выход каждого сумматора соединен с информационным входом соответствующего регистра результата, знаковый выход — с входом соответствующего раз- ряда регистралогических условий, ин формационный выход каждого блока памяти — с входом соответствующего формирователя прямоугольных импульсов, а информационный вход подключен к выходам разрядов соответствующего регистра результата, выходы разрядов регистра логических условий соединены с первым информационным входом операционного блока, второй информационный вход которого является информационным входом устройства, адресный выход операционного блока соединен с адресным входом каждого блока памяти, выход логических условий с первым входом логических условий блока микропрограммного управления, второй и третий входы логических . условий которого являются соответственно первым и вторым входами задания режима работы устройства, выход микрокоманд блока микропрограммного управления соединен с входами кода операций операционного блока, входами управления записьючтением каждого введенного блока памяти, входами разрешения каждого формирователя прямоугольных импульсов, входами управления каждого сумматора, входами стробирования каждого регистра результата, с первым и вторым выходами состояний устройства, вход команд блока микропрограммного управления является входом номера режима обработки устройства, установочный вход — входом установки исходного состояния уст,ройства, первый синхронизирующий

1196898 вход устройства соединен с синхро- и узла задания адреса, выход которонизируемыми входами операционного ro подключен к первым входам элеблока каждого сумматора, каждого ре- ментов ИЛИ группы, вторые входы гистра результата регистра логичес- которых соединены соответственно с ких условий и блока микропрограммно- выходами элементов НЕ первой группы»

ro управления, второй синхронизи- выходы элементов ИЛИ группы соедирующий вход устройства соепинен с нены с информационным входом ресинхрониэирующими входами блоков гнстра адреса, выход первого мультипричем .операциоНный блок со- плексора Услов и соединен с первым держит два мультиплексора Условий» информационным входом второго мульдва регистра данных, мультиплексор типлексора условий и через элемент данных, элемент НЕ, два дешифрато- . НŠ— с информационным входом первора, две группы элементов,НЕ, Узел го дешифратора, выходы которого чезадания адреса, группу элементов ИЛИ рез элементы НЕ второй группы соедин регистр адреса, выходы разрядов нены с первым информационным входом которого являются адресным выходом узла задания адреса, второй инфороперационного блока, информационный мационный вход которого соединен с вход первого мультиплексора усло- выходами Разрядов второго регистра вий является первым информационным данных, выход мультиплексора данных входом операционного блока, второй соединен с вторым информационным информационный вход которого соеди- вхоДом втоРого мультиплексоРа Усло- нен с информационньачи входами перво- вий» и формационный вход - с выходами разрядов второго регистра данходы разрядов первого регистра. дан- ных, выход второго мультиплексора ных является информационным выходом условий — с информационным входом второго дешифратора, выходы котороких условий которого соединен с виго соединены соответственно с входаС ходом второго мультиплексора усло- ми элементов НЕ первой группы, синхронизирующие входы первого и втос разреша пя входами ша пя входами первого и вто- Рого регистров данных» узла задания типлексоров условий муль- - адреса и регистра адреса соединены типлексора данньас» первого и второго с синхронизирующим входом операциондешифраторов первого регистра данных, ного блока.

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

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

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

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

8 команд, узел 9 формирования микрокоманд, узел 10 памяти, регистры 11 и 12 микрокоманд, регистры 13 и 14 данных, мультиплексор 15 данных, мультиплексор 16 условий, мультиплексор !7 условий, элемент НЕ 18, дешифраторы 19 и 20, группы 21 и 22 элементов НЕ, узел 23 задания адреf са, группа 24 элементов ИЛИ, регистр 25 адреса, входы и выходы

26-38 устройства, блок 39 микропрограммного управления, операционный блок 40.

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

Предварительно с входа 32 установки устройства в исходное состояние на установочный вход узла 9 по-!

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

3 11

12 регистры микрокоманд. В регистре

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

7 формирует инструкцию перехода по адресу, записанному в регистре 8, а при единичном сигнале — инструкцию перехода по счетчику микрокомаид, входящего в состав узла 9. Причем счетчик микрокоманд узла 9 может работать как в режиме инкрементирования (т.е. увеличения содержимого на единицу), tBK и в режиме повторения предыдущего адреса (режим задается управляющим полем микрокоманды). В исходном состоянии счетчик узла 9 работает в режиме повторения предыдущего адреса.

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

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

96898 4 состояния устройство оповещает внешние устройства .соответственно о режиме функционирования устройства (ожидание команды/работа) и о готовности (или неготовности) устройства принять для обработки входные данные.

Гистограмма статического распределения строится с помощью простого алгоритма: на каждом шаге выборки отсчета измеряемого сигнала 13; содержимое ячейки памяти с адресом А= Э " I ) изменяется на единицу.

10

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

23 задания адреса в соответствии с записанной информацией в регистре

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

25 гистограмм, причем в с -блоке 1 памяти формируется 21 точных отсчетов гистограммы, в то время как в остальных блоках 1 памяти строятся грубые отсчеты гистограммы статистического распределения. Число отсчетов гистограммы, формируемое в i-áëoêå 1 памяти, определяется как 2, где

1 4 1, соответственно емкость блока 1 памяти равна 2 . Адрес блока 1 памяти. А определяется сле- .

1 дующим образом: А;=А ((g-1): t), где = - при 1 i < g . В соответствии с адресами А. блоков 1 памяти

1 осуществляется считывание содержи = мого соответствующих 1 ячеек памяти

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

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

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

11. По окончании формирования гистограммы в блоках 1 памяти выполняется команда в соответствии с записью в регистре 8.

5 1

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

Медианой статического распределения Di, j-m,-М «< m М,-И4 и 4N явI ляется элемент D i>, для которого существует (Ь-1)/2 элементов, меньших или равных ему по величине, и (L-1)/2 элементов, больших или равных ему по величине, где Ь (2М+1) (2N+1). Поиск медианы в устройстве осуществляется следующим образом.

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

11, в узле 23 формируется нулевой адрес обращения к блокам 2 памяти.

Из регистра 13 данных в первый сумматор 3 заносится величина (L-1)/2, в то время как в остальных сумматорах 3 устанавливаются нулевые величины, Далее выполняется операция вычитания иэ содержимого нулевой ячейки ;-го блока 1 памяти содержимого «-го сумматора 3 при этом формирователи 2 открыты для передачи информации. Результаты операции вычитания заносятся в соответствующие регистры 4, а содержимое знако вых разрядов сумматоров 3 заносится в регистр 5 логических условий. С помощью мультиплексора 16 условий опрашивается значение знакового разряда первого сумматора 3. Выходное значение мультиплексора 16 подается через элемент НЕ 18 на информационный вход дешифратора 19 и на информационный вход мультиплексора

17. Если знаковый разряд первого сумматора 3 равен единице, т.е. результат операции вычитания отрицательный, то с помощью дешифратора

19 и соответствующего элемента из группы 21 элементов НЕ осуществляется маскирование по ИЛИ q-го разряда адреса узла 23, означающее, что медиана содержится во второй половине гистограммы, а q,-й разряд адреса равен единице. При нулевом знаковом разряде первого сумматора

3 адрес узла 23 не изменяется, т.е. медиана расположена в первой половине гистограммы статистического распределения. Последующие (g-1) циклов разрядного определения адреса в узле 23 для определения медианы имеют следующий вид. В, -й сумматор 3 заносится содержимое i --1 регистра 4.

196898 6

При единичном значении разряда адРеса ч,, 1 4с1 < «1-1, определенного в предыдущем цикле в q суммата рах 3, выполняется операция суммирования содержимого « -го сумматора 3 с содержимым выбранной ячейки

«-го блока 1 памяти по адресу, определенному в предыдущем цикле, где

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

20 -го блока 1 памяти. По величине знакового разряда (q-6+1)сумматора 3 определяется истинное значение ы,1 разряда блока 1 памяти. Таким образом, Z5 по построенным грубым и точным отсчетам гистограмм в блоках 1 памяти поиск медианы осуществляется всего за g циклов сравнения. Код управления мультиплексора 16, мультиплек»

3п сора 17, дешифраторов 19 и 20, узла

23 задается соответствующими полями микрокоманд, записанных в узле 10.

Результат поиска медианы считывается с регистра 25.

Рассмотрим пример поиска медианы для четырехразрядных входных данных. устройство содержит четыре восьмиразрядных сумматоров 3 и четыре блока 1 памяти. На фиг.4 приведены грубые и точные отсчеты гистограммы для произвольного статистического распределения для окрестности 9 9 элементов. В исходном состоянии узлом 23 в регистре 25 устанавлива45 ется нулевой адрес аЗ а2 а1 а =0, В первый сумматор 3 заносится величина (9-9+1)/2=41 Результат операции вычитания в первом сумматоре 3 содержимого ячейки памяти блока 1

50 памяти по адресу 0000 и содержимого сумматора равен Е, =60-41 19. Результаты операции вычитания в осталь ных сумматорах 3 не приводятся, так как данные операции являются избыточными для данного цикла сравнения.

Так как результат F > О, то знаковый разряд первого сумматора 3 равен нулю и результирующее значение а> 0, Во втором цикле сравнения определя7 1 а ° Поскольку а> =О то предва рительно устанавливается а 1 и во втором сумматоре 3 выполняется операция вычитания F н содержимого ячейки памяти по адресу 0100 F„ =

19-39 -20. Если F с О, то истинное значение а 1. В третьем цикле сравнения выполняется операция суммирования в третьем сумматоре 3 значения

Fg с содержимым ячейки третьего блока 1 памяти по адресу 0100 F -20+

+30 10. Так как F 7 О, то а =О. В

1 четвертом цикле сравнения после предварительной установки значения а 1 в четвертом сумматоре 3 выпол-. няется операция вычитания из F co3 держимого четвертого блока 1 памяти F4 =10-8=2, так как F о > О, то ао О. Результирующий адрес, сформи196898 8 рованный в регистре 25 равен..0100 и соответственно величина медианы

В . =О О

D;1= 100. С помощью данного устройст. ва для обработки гистограммы за поразрядных сравнений по построенным грубым и точным отсчетам гистограмм выполняются и другие вычисли.тельные операции статистической обработки информации, например, 1р зквализация гистограммы, определение минимального и максимального значений статистического распределе" ния. При выполнении операции эквализации гистограммы осуществляется !

5 поразрядное тестирование входного числа, записанного в регистре 14 данных, мультиплексором 15 с целью определения адресов блоков 1 .памяти в процессе поиска результата.

1196898

1196898

Составитель А.Жеренов

Редактор Н.Данкулич Техред Л.Мартяшова КорректорГ.Решетник

Заказ 7566/49 Тираж 709 Подписное

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

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

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4