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

(72)и Е.Ф Трудовоготочной 56) 995 Ав 763226/24-248.06.847. 12. 85. Бюл. У 45енинградский орденаго Знамени институтки и оптики(54) (57) УСТРОЙСТВО ДЛЯ ОБРАБОТКИДАННЫХ ГИСТОГРАИИ, содержащее первый блок памяти, первый сумматор,блок микропрограммного управления,выход микрокоманд которого соединен с информационным входом первого блока памяти, о т л и ч а ю щ ее с я тем, что, с целью повышения быстродействия, в него введены (-1) блоков памяти, (-1) сумматоров, 4, формирователей прямоугольных импульсов,регистроврезультата, регистр логическихусловий и операционный блок, причем первый информационный вход каждого,сумматора соединен с выходомсоответствующего формирователяпрямоугольных импульсов, второйинформационный вход первого сумматора соединен с информационным выходом операционного блока, второйинформационный вход (1+1)-го сумматора соединен с выходами разрядов 1-го регистра результата,где 11, я,-1, информационный выходкаждого сумматора соединен с информационным входом соответствующего регистра результата, знаковый выход - с входом соответствующего раз-ряда регистралогических условий, информационный выход каждого блокапамяти - с входом соответствующегоформирователя прямоугольных импульсов, а информационный вход подключен к выходам разрядов соответствующего регистра результата, выходы разрядов регистра логическихусловий соединены с первым информационным входом операционного блока, второй информационный вход которого является информационнымвходом устройства, адресный выходоперационного блока соединен садресным входом каждого блока памяти, выход логических условийс первым входом логических условийблока микропрограммного управлениявторой и третий входы логических условий которого являются соответственно первым и вторым входамизадания режима работы устройства,выход микрокоманд блока микропрограммного управления соединен с входами кода операций операционногоблока, входами управления записьючтением каждого введенного блока памяти, входами разрешения каждогоформирователя прямоугольных импульсов, входами управления каждогосумматора, входами стробированиякаждого регистра результата, с первым и вторым выходами состоянийустройства, вход команд блока микропрограммного управления являетсявходом номера режима обработки устройства, установочный вход - входомустановки исходного состояния уст,ройства, первый синхронизирующий1196898вход устройства соединен с синхро- и узла задания адреса, выход которонизируемыми входами операционного го подключен к первым входам элеблока каждого сумматора, каждого ре" ментов ИЛИ группы, вторые входы гистра результата, регистра логичес- которых соединены соответственно с ких условий и блока микропрограммно- выходами элементов НЕ первой группы го управления, второй синхронизи- выходы элементов ИЛИ группы соедирующий вход устройства соединен с нены с информационным входом ресинхрониэирующими входами блоков гнстра адреса, выход первогомультипамяти, причем .операционный блок со- плексора условий соединен с первым держит два мультиплексора условий, информационным входом второго мульдва регистра данных, мультиплексор типлексора условий и через элемент данных, элемент НЕ, два дешифрато- НЕ - с информационным входом первора, две группы элементов.НЕ, узел го дешифратора, выходы которого чезадания адреса, группу элементов ИЛИ рез элементы НЕ второй группы соедин регистр адреса, выходы разрядов нены с первым информационным входом которого являются адресным выходом узла задания адреса, второй инфороперационного блока, информационный мационный вход которого соединен с вход первого мультиплексора усло- выходами разрядов второго регистраданных, выход мультиплексора данных входом операционного блока, второй соединен с вторым информационным информационнфо нный вход которого соеди- входом второго мультиплексора усло- нен с информационньачи входами перво- вий, информационный вход - с выходарегистров данных вы- ми разрядов второго регистра данходы разрядов первого регистра дан- ных, выход второго мультиплексора ных является информационным выходом условий - с информационным входом операционного лока, выход второго дешифратора, выходы котороких условий которого соединен с ви- го соединены соответственно с входаСми элементов НЕ первой группы, синходом второго мультиплексора условий, а вход кода операции соедк да операции соединен хронизирующие входы первого и втос разрешающими входами первого и вто- рого регистров данных, узла заданияпл соров условий муль- адреса и регистра адреса соединены типлексора данных, первого и второго с синхронизирующим входом операциондешифраторов первого регистра данных, ного блока.Изобретение относится к вычисли"тельной технике и может быть использовано для обработки статистическойинформации.Цель изобретения - повышениебыстродействия устройства,На фиг, 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 задания адреэ са, группа 24 элементов ИЛИ, регистр 25 адреса, входы и выходы26-38 устройства, блок 39 микропрограммного управления, операционныйблок 40.О Устройство работает следующим образом,Предварительно с входа 32 установки устройства в исходное состояние на установочный вход узла 9 по 5 ступает сигнал отрицательной полярности. На выходе узла 9 устанавливается нулевой адрес узла 10 памяти., Извлеченная микрокоманда иэ узла 10записывается в первый 11 и второй3 11 12 регистры микрокоманд, В регистре 11 содержится управляющее поле микрокоманд, в регистре 12 - адрес перехода к подпрограмме. Узел 7 па основе информационного сигнала, поступающего с мультиплексора 6, и управляющих сигналов, поступающих с регистра 11, формирует тип выполняемой инструкции, В исходном состоянии с помощью мультиплексора 6 опра шивается вход 33 логических условий, по состоянию которого проверяется наличие записанной команды в регистре 8 команд. При нулевом сигнале на входе 33 логических условий узел 7 формирует инструкцию перехода по адресу, записанному в регистре 8, а при единичном сигнале - инструкцию перехода по счетчику микрокомаид, входящего в состав узла 9. Причем счетчик микрокоманд узла 9 может работать как в режиме инкрементирования (т,е, увеличения содержимого на единицу), так и в режиме повторения предыдущего адреса (режим задается управляющим полем микрокоманды). В исходном состоянии счетчик узла 9 работает в режиме повторения предыдущего адреса.Основные команды, выполняемые устройством, задаваемые с помощью внешнего устройства, следующие: суммирование элементов гистограммы, вычитание элементов гистограммы; тип выполняемой операции, например, медианная фильтрация, эквализация гистограммы, определение минимального или максимального значенийгистограммы,При выполнении команд суммирования или вычитания элементов гистограммы с помощью мультиплексора 6проверяется состояние входа 34 логических условий, по состоянию которого определяется наличие записанных данных в первый 13 и второй14 регистры данных, При нулевом сигнале на входе 34 логических условийузел 7 формирует инструкцию перехода узла 9 по адресу регистра 12, т,е,обработка данных, записанных в первом 13 и втором 14 регистрах данных,разрешена. Иначе узел 7 формируетинструкцию перехода по содержимомусчетчика микрокоманд узла 9, т,е,реализуется режим ожидания (повторная проверка состояния входа 24 логических условий), С помощью управляющих сигналов на выходах 36 и 3796898 4 состояния устройство оповещает внешние устройства, соответственно о режиме функционирования устройства (ожидание команды/работа) и о готовности (или неготовности) устройства принять для обработки входные данные. Гистограмма статического распределения строится с помощью простого алгоритма: на каждом шаге выборки отсчета измеряемого сигнала 13; содержимое ячейки памяти с адресом А= Э11 изменяется на единицу,510 При построении гистограммы посредством соответствующего управляющего поля микрокоманды, записанной В ре 15 гистре 11, осуществляется запрет работы дешифраторов 19 и 20, адресблоков 1 памятопределяется узлом 23 задания адреса в соответствии сзаписанной информацией в регистре 20 14. Сформированный адрес записывается в регистр 25 адреса, В блоках 1памяти параллельно формируется 25 гистограмм, причем в с -блоке 1 памяти формируется 21 точных отсчетовгистограммы, в то время как в остальных блоках 1 памяти строятся грубыеотсчеты гистограммы статистическогораспределения. Число отсчетов гистограммы, формируемое в 1-блоке 1 памяти, определяется как 2 , где1 ( 1, соответственно емкостьблока 1 памяти равна 2, Адресблока 1 памяти. А определяется сле- .35дующим образом: А;=А (-1):1,где=-при 1 ((. В соответствии с адресами А, блоков 1 памятиосуществляется считывание содержи =мого соответствующих 1 ячеек памяти 40и изменение содержимого ячеек наединицу в сумматорах 3, Преобразованная в сумматорах 3 информациязаписывается в регистры 4, а в следующем машинном цикле осуществля 45ется запись содержимого регистров 4в соответствующие блоки 1 памяти,Режимы "Чтение" и "Запись" блоков 1памяти, операции инкрементированияна единицу и декрементирования наединицу в сумматорах 3, а такжесигналы разрешения выдачи информации регистрами 4 и формирователями2 задаются соответствующими полямимикрокоманды, записанной в регистре11. По окончании формирования гистограммы в блоках 1 памяти выполняется команда в соответствии с записью в регистре 8.5 1Рассмотрим функционирование устройства для обработки гистограмм в режиме поиска медианы гистограммы статического распределения.Медианой статического распределения Р; , 1-в,-М с т с М,-И 4 и С Я яв 1ляется элемент 0 11 , для которого существует (Ь)/2 элементов, меньших или равных ему по величине, и (Ь)/2 элементов, больших или равных ему по величине, где Ь (2 М+1)(2 Н+1), Поиск медианы в устройстве осуществляется следующим образом. В соответствии с управляющим полем микрокоманды, записанной в регистре 11, в узле 23 формируется нулевой адрес обращения к блокам 2 памяти. Из регистра 13 данных в первый сумматор 3 заносится величина (Ь)/2, в то время как в остальных сумматорах 3 устанавливаются нулевые величины, Далее выполняется операция вычитания иэ содержимого нулевой ячейки 1-го блока 1 памяти содержимого 1-го сумматора 3 при этом формирователи 2 открыты для передачи информации. Результаты операции вычитания заносятся в соответствующие регистры 4, а содержимое знакб вых разрядов сумматоров 3 заносится в регистр 5 логических Условий. С помощью мультиплексора 16 условий опрашивается значение знакового разряда первого сумматора 3. Выходное значение мультиплексора 16 подается через элемент НЕ 18 на информационный вход дешифратора 19 и на информационный вход мультиплексора 17. Если знаковый разряд первого сумматора 3 равен единице, т.е. результат операции вычитания отрицательный, то с помощью дешифратора 19 и соответствующего элемента из группы 21 элементов НЕ осуществляется маскирование по ИЛИ ч.-го разряда адреса узла 23, означающее, что медиана содержится во второй половине гистограммы, а ч-й разряд адреса равен единице, При нулевом знаковом разряде первого сумматора 3 адрес узла 23 не изменяется, т.е. медиана расположена в первой половине гистограммы статистического распределения. Последующие (-1) циклов разрядного определения адреса в узле 23 для определения медианы имеют следующий вид. В , -й сумматор 3 заносится содержимое 1 -1 регистра 4.196898 6 При единичном значении разряда адреса с 1 4 с 1с 1-1, определенного в предыдущем цикле в ч, суммата рах 3, выполняется операция суммирования содержимого 1 -го сумматора 3 с содержимым выбранной ячейки 1-го блока 1 памяти по адресу, определенному в предыдущем цикле, где 1 1, ч При нулевом значении разряда адреса ас 1, определенного в пре 5 10 дыдущем цикле, с помощью мультиплексора 17, дешифратора 20, соответствующего элемента из группы 22 элементов НЕ и соответствующего элемента из группы 24 элементов ИЛИв регистре 25 адреса устанавливаетсязначение разряда адреса.ю,1, равноеединице, В сумматорах 3 выполняетсяоперация вычитания содержимого-госумматора 3 и соответствующей ячейки 1520 1-го блока 1 памяти, По величинезнакового разряда (1-6+1)сумматора 3определяется истинное значение ы,1разряда блока 1 памяти. Таким образом,25 по построенным грубым и точным отсчетам гистограмм в блоках 1 памятипоиск медианы осуществляется всегозациклов сравнения, Код управления мультиплексора 16, мультиплек" ЗО сора 17, дешифраторов 19 и 20, узла23 задается соответствующими полямимикрокоманд, записанных в узле 10.Результат поиска медианы считываетсяс регистра 25.35Рассмотрим пример поиска медианыдля четырехразрядных входных данных.устройство содержит четыре восьмиразрядных сумматоров 3 и четыреблока 1 памяти. На фиг,4 приведеныгрубые и точные отсчеты гистограммыдля произвольного статистическогораспределения для окрестности 9 9элементов. В исходном состоянииузлом 23 в регистре 25 устанавлива ется нулевой адрес а 3 а 2 а 1 а=ОВ первый сумматор 3 заносится величина (9 9+1)/2=41, Результат операции вычитания в первом сумматоре 3содержимого ячейки памяти блока 1 50памяти по адресу 0000 и содержимогосумматора равен Е, =60-4119, Результаты операции вычитания в остальных сумматорах 3 не приводятся, таккак данные операции являются избыточными для данного цикла сравнения,Так как результат Г 7 О, то знаковыйразряд первого сумматора 3 равеннулю и результирующее значение азО,Во втором цикле сравнения определя7 1 ется а. Поскольку а 5=0, то предварительно устанавливается а 1 и втором сумматоре 3 выполняется операция вычитания Г, н содержимого ячейки памяти по адресу 0100 Г = 19-39 -20. Если Г ( О, то истинное значение а 1. В третьем цикле сравнения выполняется операция суммирования в третьем сумматоре 3 значения Г с содержимым ячейки третьего блока 1 памяти по адресу 0100 Е 5 -20+ +3010. Так как Г 5 О, то а =О, В четвертом цикле сравнения после предварительной установки значения а 1 в четвертом сумматоре 3 выполняется операция вычитания из Р со 5 держимого четвертого блока 1 памяти ГАВ=10-8=2, так как Ро 0, то а О. Результирующий адрес, сформи 196898 8рованный в регистре 25 равен 0100 йсоответственно величина медианыЭ=00Э, = 100. С помощью данного устройст.ва для обработки гистограммы за ф5 поразрядных сравнений по построенным грубым и точным отсчетам гистограмм выполняются и другие вычисли.тельные операции статистическойобработки информации, например,10 эквализация гистограммы, определение минимального и максимальногозначений статистического распределе"ния. При выполнении операции эквализации гистограммы осуществляется15 поразрядное тестирование входногочисла, записанного в регистре 14данных, мультиплексором 15 с цельюопределения адресов блоков 1 памятив процессе поиска результата.0 Патент", г. Ужгород, ул. Проектная, 4 и Тираж 709Подписно ИИПИ Государственного комитета СССР о делам изобретений и .открытий Москва, Ж, Раушская наб., д. 4/5