Вычислительное устройство для ранговой фильтрации

), 1,(1 1 г ." ОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКН", СССР ТОРСКОМУ СВИДЕТЕЛЬСТВУ(71) Ленинградский институт точной механики и оптики, Авторское свидетельство СССРМ 1196898, кл. 6 06 Р 11/00, 1984. Изобретение относится к вычислительной технике и может быть использовано при статистической обработке данных, например, для обработки изображений.Цель изобретения - повышение быстродействия.На фиг.1 и 2 представлена структурная схема устройства; на фиг.3 - схема блока обработки; на фиг,4 - схема блока задержки; на фиг.5- схема блока буферной памяти. на фиг.6 - схема блока микропрограммного управления; на фиг.7 - схема шифратора.Устройство содержит блок 1 микропрограммного управления, блоки 2 обработки, блоки 3 буферной памяти, блоки 4 задержки. регистр 5 результата, регистр 6 ранга выходного элемента, шифраторы 7, элемент 8 НЕ арифметический узел 9, узел 10 памяти, регистр 11 данных, регистры 12 суммы, регистры 13 адреса, регистры 14 команды,54) ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСДЛЯ РАНГОВОЙ ФИЛЬТРАЦИИ(57) Изобретение относится к вычислительной технике и можетбыть использовано при статистической обработке данных, например для обработки изображений. Целью изобретения является повышение быстродействия. Устройство содержит блок микропрограммного управления, блоки обработки, блоки буферной памяти, блоки задержки, регистр результата, регистр ранга выходного элемента, шифраторы, элементы НЕ, 7 ил., 2 табл. мультиплексор 15, элементы 16, 17 НЕ, элементы,18, 19 ИЛИ, связи 20-66, узел 67 памяти, счетчик 68, связи 69, 70, счетчик 71, узел 72 памяти, связи 73, 74, узел 75 постоянной памяти, счетчик 76, элементы 77 - 80 И, элемент 81 НЕ, элементы 82, 83 ИЛИ, узлы 84, 85 и 86 шифрации, элементы 87, 88 НЕ.В начале работы устройства производится очистка ячеек узлов памяти всех блоков 2, что соответствует режиму обнуления табл,2). При этом на информационные входы 7 устройства от внешнего устройства поступают последовательно на каждом такте числа, а на вход 64 блока 1 - тактирующий импульс, на вход 65 - нулевое значение, а на вход 66 - единичное значение. Ноль на входе 65 устанавливает выходы счетчика 76 в единичное состояние, (При использовании в качестве счетчика, например, микросхе 16565541656554Составитель И. Жеренов Редактор А, Долинич Техред М.Моргентал Корректор Т. Колб аказ 2054 Тираж 424 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., 4/5роизводственно-издательский комбинат "Патент", г. Ужгород. ул,Гагарина, 10На вход 64 устройства поступает тактиующий импульс, а на входы 65 и 66 - нуль.отличие от предыдущего режима на адресый вход узла 75 поступает нуль, так как на торой вход элемента 79 И с входа 66 блока 1 поступает нуль. Таким образом на адресный вход узла 75 поступает код 110, На выходе блока 1 установятся сигналы, соответствующие режиму начального формирования гистограмм. После третьего тактирующего импульса, поступающего на вход 64 блока 1, на информационные входы 37 устройства начинают поступать входные данные, а содержимое третьего регистра 14 будет соответствовать режиму НФГ. На входы выбора функций узла 9 поступает с выхода третьего, регистра 14 код 0000, соответствующий функции (А+1), При этом на вход первого операнда (А) узла 9 поступает число с выхода узла 10, так как на вход выбора канала мультиплексора 15 с выхода третьего регистра 14 поступает нуль, что соответствует выбору второго канала мультиплексора 15, который подключен к выходу узла 10,С приходом следующего тактирующего импульса (ТИ) результат с выхода узла 9 запишется по низкому уровню ТИ в узел 10 по тому же адресу, с которого производилось считывание, так как содержимое регистра 11 данных изменяется по заднему фронту ТИ. Также при приходе следующего ТИ содержимое третьего регистра 14 первого блока 2 перепишется в первый регистр 14 второго блока 2, Работа второго блока 2 и других блоков аналогична.Данные, поступающие с информационного входа 37 устройства на вход блока 3, записываются в узел 72 по низкому уровню сигнала, поступающего на вход 61 блока 3 с выхода 59 блока 1. Адрес, по которому производится запись, определяется содержимым счетчика 71, которое меняется по переднему фронту ТИ, поступающего с выхода 58 блока 1 на тактирующий вход 60 блока 3. Коэффициент деления счетчика равен й (где й - число столбцов окна фильтра). На вход 63 блока 4 поступает ТИ, который является также сигналом разрешения записи вузел 67 с выхода 62 блока 1. Поэаднему фронту ТИ происходит изменение содержимого счетчика 68, Устранение гонок возможно подбором ВС-цепочек таким образом, чтобы ТИ поступали в следующей последовательности:(блок 3 и блок 4) - регистр 11 данных - регистр 12 суммы - регистр 13 адреса - регистр 14 команды.Чосле начальной установки устройство переводится в основной этап работы, алгоритм которого имеет вид мы типа К 155 ИЕ 7 входом установки,в единичное состояние выходов счетчика являет- рся вход разрешения параллельной загрузки, ВПри этом на все входы счетчика подаются нединицы). Выход элемента 79 И устанавли ввается в "1", так как на его второй входтакже поступает единица с выхода 66 блока1. В результате на адресном входе узла 75имеется код 111. Состояние выходов узла 75определяется иэ табл,1, а управляющие сигналы, вырабатываемые на выходах блока, -из табл.2, Сигналы с выходом 41-45 блока 1поступают на входы первого блока 2. Этоткод записывается в первый регистр 14 блока4 по заднему фронту тактирующего импульса, поступающего на вход 31 блока 2 с выхода блока 1. После третьего тактасодержимое первого регистра 14 перепишется в третий регистр 14. Теперь; на каждом такте можно подавать на 20информационные входы 37 числа, которыезаписываются в блок 3 по низкому уровнюсигнала, поступающего с выхода 59 блока 1на входы 61 записи блоков 3. С выхода первого блока 3 0-й разряд числа записывается 25в регистр 11 данных по заднему фронту импульса, поступающего с выхода элемента 19ИЛИ первого блока 2. На тактирующий входблока 3 импульс не поступает. К адресномувходу узла 10 подключается выход регистра 3011 данных, так как на его вход разрешениявывода с выхода третьего регистра 14 поступает нуль.С выходов третьего регистра 1.4 на входы выбора функций узла 9 поступает код 350011, соответствующий функции установкинуля на выходе узла 9, Нуль с выхода узла 9запишется в узел 10 по низкому уровнюследующего тактирующего импульса, с приходом которого также происходит перепись 40содержимого третьего регистра 14 первого блока 2 в первый регистр 14 второго блока 2. Работа всех блоков 2 вэтом режимеаналогична работе первого блока 2,На вход 63 синхронизации блока 4 поступает с выхода 62 блока 1 тактирующийимпульс. Запись в узел 67 происходит понизкому уровню тактирующего импульса.Адрес, по которому происходит запись,определяется содержимым счетчика 68, которое меняется по заднему фронту тактирующего импульса.Значение задержки(1, 1)-го блока 4("-2, М) устанавливается равной (И а значений задержки(К-го блока 4(М, У,1-2, 55О) равно (М).Следующим этапом работы устройстваявляется начальная установка, которой соответствует режим начального формирования гистограмм (НФГ).(О - Д-й разряд равен 1;Ц+1= О, (5)конец для ):Я= Рм,0, (6)где Аи - входные данные, удаляемые из окнафильтра по 1-му входу 37, Ь(Ц)-м блоке 2;Ви - входные данные, включаемые в окно фильтра, поступающие по 1-му входу а(Ц)-м блоке 2;Н 1(х) - гистограмма, формируемая в (Ц)м блоке 2 по) старшим разрядам числа х;С 11 - значение промежуточной суммы в(Ц)-м блоке 2;Рц - значение результата в (Ц)-мблоке 2;й - значение ранга выходного элемента;- переменная кода операции в (Ц)-мблоке 2,еслиф = 1, то выполняется вычитание, иначесуммирование, Я - результат,Цикл в основном этапе работы устройства состоит из 3 тактов,В каждом цикле на входы 37 устройствапоступают обрабатываемые данные. Последовательность работы блока 2 внутри циклаимеет следующий вид: суммирование (вычитание) отсчета гистограмм - удаление элемента столбца - включение элементастолбца. В первом такте на вход 64 блока 1поступает тактирующий импульс, на входы65 и 66 - единица от внешнего источника.Так как на вход 65 поступает единица, торазрешается работа счетчика 76 в счетномрежиме. В предыдущем режиме счетчик 76бцл установлен в единичное состояние. Поэтому при переходе в основной этап работысчетчика сбрасывается в нуль сигналом "1"с выхода элемента 78 И, на вход которогопоступает "1" с входа 65 блока 1, а на другойвход - "1" с выхода элемента 77 И, Такимобразом на адресный вход узла 75 поступает код 000, Состояние выхода узла 75 видноиз табл. 1, а состояние выхода блока 1 из. табл,2, После первого такта первого цикла основногс этапа работы устройства вс втором и третьем регистрах 14 блока 2 будут находится управляющие данные, соответствующие режиму начального формирования гистограмм, а в первый регистр 14 запишутся управляющие данные режима вычитание отсчета гистограмм. Во втором такте сигналы, поступающие на входы блока 1, не изменяются, По заднему фронту импульса, поступающего на счетный вход счетчика 76, ега содержимое увеличится на единицу, В результате на адресный вход узла 75 поступит код 001, в соответствии с которым установятся на выходе блока 1 управляющие данные режима удаления элементов столбца блока 2. Эти данные запишутся в первый регистр 14 по заднему фронту ТИ на входе 31 первого блока 2, Вс второй регистр 14 20 перепишется содержимое первого ре истра 14, С приходом третьего тактиоующего импульса на вход 64 блока 1 содержимое счетчика,76 будет равно 2, сигналы поступающие на входы 65 и 66 блока 1 от 25 внешнего источника, не меняются. На адресный вход узла 75 поступит код 010. На выходе блока 1 формируются сигналы установки режима включения злсментсв стслбпишется содержимое второго регистса 14, а во второй регистр 14 - содержимое первого регистра 14. На этом цикл работы блока 1 заканчивается и с приходом очередного импульса на ехсд 64 блок 1 счетчик 76 сбрасывается в нуль, так как на выходе счетчика 76 будет код 11, который активизирует сигнал "Сброс" через элементы 77, 78 И, затем начинается следующий цикл.С началом второго цикла расоты блоки 1 и 2 начинают выполнять операцию вычитания отсчета гистограмм; Сигналы установ 40 ки зтогс режима содержатся в третьем регистре 14. С выхода третьего регистра 14 поступает код 0110, соответствующий функ 45 ции (А - В). На вход А первого операнда узла 9 поступает число свыхода третьего регистра 12, так как на вход выбора канала мультиплексора 15 поступает с выхода регистра 14 лог. "1". что соответствует подключению первого канала мультиплексора 15(куда поступает число с выхода третьего регистра 12) на егс выход, Содержимое регистра 12 первого блока 2 равно значению ранга, так как вход 21 первого блока 2 подсоединен к выходу регистра 6. На вход В второго опе 55 ранда узла 9 поступает число с вцхода узла 10 памяти. Адрес считывания узла 10 апределяется содержимым третьего регистра 13 30 ца, которые запишутся в первый регистп 4 первого блока 2, На третий регистр 14 пере165 адреса, так как выход этого регистра подключен к адресному входу узла 10 единицей с выхода третьего регистра 14, после элемента 16 НЕ. Выход регистра 11 данных отключается от адресного входа единицей с выхода третьего регистра 14, Содержимое регистра 13 адреса первого блока 2 равно О, так кзк вход 22 адреса первого блока 2 соединен с входом пог. "0". (Операция (1) алгоритма), В первом такте цикла на тактовый вход 61 блока 3 с выхода 58 блока 1 поступит импульс. В результате содержимое счетчика 71 изменится, указывая на адрес удаляемого элемента столбца,Во втором такте по заднему фронту ТИ на входе 31 блока 2 происходит перепись . содержимого третьего регистра 14, третьего регистра 13 адреса и результата с выхода узла 9 первого блока 2 в первые регистры 14, 13 и 12 второго блока 2, (Операция (4) алгоритма). Первый блок 2 во втором такте будет выполнять операцию удаления элемента столбца, так как в третьем регистре 14 содержится код режима удаления столбца. На входы выбора функций узла 9 поступает с выхода третьего регистра 14 код 1111, что соответствует функции (А):(Операция (2) алгоритма), На вход А первого операнда узла 9 поступает число с выхода узла 10, так как на вход выбора канала мультиплексора 15 с выхода регистра 14 поступает Ж что соответствует подключению второго канала мультиплексора 15 на выход. Адрес считывания определяется содержимым регистра 11 данных, так как выход регистра 13 отключается, а выход регистра 11 данных подключается к адресному входу узла 10 нулем, поступающим с выхода пятого разряда регистра 14. В регистр 11 по заднему фронту ТИ записывается значение удаляемого элемента с выхода блока 3, выставленное в предыдущем такте. На тактирующий вход блока 3 импульс не поступает. Значение удаляемого элемента с выхода первого блока 3 также записывается в (1,2)-ый блок 4 по низкому уровню ТИ, поступающего с выхода 62 блока 1. По заднему Фронту ТИ содержимое счетчика 68 (1,2)-го блока 4 изменится, указывая адрес следующего элемента столбца, обрабатываемого в (1,2)-ом блоке 2,Результат с выхода узла 9 запишется вузел 10 по тому же адресу, с которого производилось считывание с приходом ТИ третьего такта цикла. Также происходит перепись содержимого третьего регистра 14 (1, 1).го блока 2 в первый регистр 14 (2 1)-го блока 2. 8 третьем такте в первый блок 3 по низкому уровню сигнала, поступающего на вход 61 записи блока 3 с выхода 58 блока 1, запишется значение элемента входящего 6554 8столбца, Третий регистр 14 (1,1)-го блока 2 будет содержать код режима включения элемента столбца. На вход выбора Функций узла 9 поступает код 0000, соответствующий 5 функции (А+1), На вход А первого операндапоступает число с выхода узла 10, так как на вход выбора канала мультиплексора с выхода пятого разряда третьего регистра 14 поступает Ю соответствующий подключению 10 второго канала мультиплексора 15 к выходумультиплексора. В регистр 11 данных с выхода первого блока 3 записывается значение элемента входящего столбца по заднему фронту ТИ. Нуль на выходе пятого 15 разряда третьего регистра 14 подключзетвход регистра 11 данных к адресному входу узла 10. Результат с выхода узла 9 записывается в узел 10 памяти по тому же адресу, с которого производилось считывание по 20 низкому уровню ТИ первого такта следующего цикла. Значение входящего столбца с выхода первого блока 3 также запишется в (1,2)-ой блок 4 по низкому уровню ТИ, поступающего с выхода 62 блока 1 в третьем такте 25 текущего цикла, На вход 60 блока 3 импульске поступает (Операция (3) алгоритма).В следующем цикле первый блок 2 начинает обрабатывать первый элемент следующего удаляемого и вставляемого 30 столбца, (2,1)-ый блок 2 обрабатывает второй элемент предыдущего удаляемого и вставляемого столбца с учетом значения промежуточной суммы, полученной в первом блоке 2 (операция (4) алгоритма).35 Второй элемент столбца поступает с задержкой на один цикл по отношению к первому элементу этого же столбца, Задержка обеспечивается (2,1)-ым блоком 4. Последовательность режима работы и работа (2,1)-го 40 блока 2 аналогична последовательности режима, работы первого блока 2. В 1-ом цикле ( = 3, М) обрабатывается 1-ый элемент столбца в (1, 1)-ом блоке 2, Задержку 1-го элемента столбца осуществляет (И)-ый блок 4 ( =.45 =2, М) на (1-1) циклов по отношению к первому элементу этого же столбца, После первого такта М-го цикла сигналы с выходов 32-36 и выхода 30 признака результата (М, 1)-го блока 1 поступают на входы 46-51 первого 50 шифратора соответственно, а с выхода 29промежуточной суммы и выхода 28 адреса - на вход 21 промежуточной суммы и на (О - 2)- младших разрядов входа 22 адреса (1, 2)-го блока 2.55 Единица на входе 50 шифратора 7 отключает выходы узла 86 от выходов 52-55 шифратора 7. Нуль с выхода элемента 88 поступает на входы раэредения вывода узлов 84, 85. Подключение выходов узлов 84 и1, то подключается выход узла 85, иначе выход узла 84, Сигнал с выхода элемента 87 5 НЕ поступает на выход 38, а с входа 51 - на выход 39 блока 7. При подключении выхода узла ,1 на выходы 52-56 шифратора 7 поступает код 0110, что соответствует функции (А 40 45 50 55 яния сигнала на входе 51 шифратора 7, определяемого значением признака результата. Если значение сигнала на входе 51 равно- В) узла 9, а при подключении узла 85 - код 1001 функции (А + В) (операция (5) алгоритма). Выход 38 первого шифратора 7 соединен с О-цм разрядом входа 22 адреса (1,2)-го блока 2, а выход 39 - с (О - 1)-ым разрядом, Во втором и третьем тактах цикла сигнал на входе 50 шифратора 7 равенн, что соответствует подключению выходов узла 86 к выходам 52 - 55 блока 7, Это означает, что код операции через шифратор 7 передается без изменения.Аналогично происходит формирование и передача команд от (М, -го блока 2 к (1, )+ +Я.му блоку 2 через )-ый шифратор 7 ( = 1;0 - 1). При этом (О - ) + 2)-ый= 2, О) разряд входа 22 адреса О, 1)-го блока 2 соединяется с выходом 38, а (О - ) + 1)- ый разряд с выходом 39 О - 1)1-го шифратора 7.Другие (О - 2) разряда входа 22 адреса (1,Д-гоблока 2 О =2,0) соединены с выходом 28 адреса (М, ) - 11-го блока 2 (1, Д-ый блока 4 ( = 1, М, ) = 2, О) обеспечивает задержку данных на (М - 1) циклов,Значения (О - 1) старших разрядов третьего регистра 13 адреса и инверсное значение признака результата (М, О)-го блока 2 запишутся в регистр 5 результата. Формула изобретения Вычислительное устройство для ранговой фильтрации, содержащее блоки обработки, блок микропрограммного управления и регистр результата, о т л и ч аю щ е е с я тем, что, с целью повышения быстродействия, в него введены блоки буферной памяти, блоки задержки, регистр ранга выходного элемента и элемент НЕ, причем блок обработки содержит арифметический узел, узел памяти, регистр данных, три регистра суммы, три регистра адреса, три регистра команды, мультиплексор, два элемента НЕ, два элемента ИЛИ, выход первого из которых является выходом признака результата блока обработки, информационные входы регистра данных, первого регистра суммы и первого регистра адреса соединены с входом данных, входом промежуточной суммы и адресным входом блока обработки соответственно, входы резрядов первого регистра команд являются управляющими входами блока обработки, выходы 15 20 25 30 35 регистра данных и третьегр регистра адреса соединены с адресным входом узла памяти и с адресным выходом блока обработки, выход первого регистра суммы соединен с информационным входом второго регистра суммы, выход которого соединен с информационным входом третьего регистра суммы, выход которого соединен с первым информационным входом мультиплексора.выход которого соединен с входом первого операнда арифметического узла, вход второго операнда которого подключен к выходу памяти и к второму информационному входу мультиплексора, выход результата арифметического узла соединен с входом данных узла памяти и с выходом промежуточной суммы блока обработки, выход о-ображения эквивалентности арифметического узла соединен через первый элемент НЕ с первым входом первого элемента ИЛИ, второй вход которого соединен с выходом старшего разряда результата арифметичесокго узла, входы резрядов второго регистра команды соединены с выходами разрядов первого регистра команды соответственно, входы разрядов третьего регистра командь соединены с выходами разрядов второго регистра команды соответственно, выходы разрядов с первого по четвертый третьего регистра команды соединены с входами выбооа фун кций арифметического узла и с первого па четвертый управляющими выходами блока обработки соответственно, выход пятого разряда региСтра команды соединен с входом второго элемента НЕ, с входом выбора канала мультиплексора, с пятым управляющим выходом блока обработки, с входом разрешения вывода регистоа данных и с первым входом второго элемента ИЛИ. выход первого регистра адреса соединен с информационным входом второго регистра адреса, выход которого соединен с информационным входом третьего регистра адреса, вход разрешения вывода которого соединен с выходом второго элемента НЕ, входы синхронизации каждого регистра команды, регистра суммы и регистра адреса, второй вход второго элемента ИЛИ соединены с входом синхронизации блока обработки, выход второго элемента ИЛИ соединен с входом записи узла памяти и с входом синхронизации регистра данных, информационный вход -го блока буферной памяти ( = 1; М) является 1-м информационным входом устройства, 0-й разряд выхода первого блока буферной памяти соединен с информационным входом (1, 1)-го блока задержки, 0-й разряд входа данных (, 1)-го (1" = 2, М) блока обработки соединен с О-м .оазрядом информационного входа (1, 1)-гоблока задержки, ) старших разрядов входа данных (, -го блока обработки ( -1; М, ) = Гб) соединены сстаршими разрядами выхода (, Д-го блока задержки, (О - ) младших разрядов входа данных (, го блока обработки ( - Г 9, ) = Гб) соединены с входом логического нуля устройства, выход (, 1)-го блока задержки ( - 2 М) соединен с информационным входом (, 2)-го блока задержки, адресный вход первого блока обработки соединен с входом логического нуля устройства, йщ)есный вход(1, 1)-го блока обработки ( = 2, О) соединен с адресным выходом (М, 1- 1)-го блока обработки, выход признака результата (М, О)-го блока обработки соединен с входом элемента НЕ, адресный выход (М, О)-го блока обработки и выход элемента НЕ соединены с входами регистра результата соответственно, выход регистра результата является выходом устройства, вход промежуточной суммы первого блока обработки соединен с выходом регистра ранга выходного элемента, с первого по пятый управляющие входы первого блока обработки соединены с первого по пятый управляющими выходами блока микропрограммного управления соответственно, с первого по пятый управляющие выходы, адресный выход и выход промежуточной суммы (, Д-го блока обработки ( = 1,М - 1, ) = 1, О) соединены с первого по пятый управляющими входами, адресным входом и входом промежуточной суммы ( + 1,блока обработки соответственно, выход 5 промежуточной суммы (М, Д-го блока обреботки ( = Гб) соединен с входом промежуточной суммы (1,1+ 1)-го блока обработки, с первого по пятый управляющие выходы и выход признака результата (М, Д-го блока 10 обработки соединены с первого по шестойвходами 1-го шифратора, с первого по пятый выходы )-го шифратора ( = 1, О -. 1) соединены с первого по пятый управляющими входами (1, ) + 1)-го блока обработки 15 соответственно, шестой и седьмой выходыблока микропрограммного управления соединены с входом синхронизации и входом разрешения записи каждоо блока буферной памяти, восьмой выход блока микро программного управления соединен свходом синхронизации каждого блока задержки, девятый выход соединен с входом синхронизации каждого блока обработки, три входа блока микропрограммного управ ления являются входами команд устройства, (О - ) + 1)-й разряд ( - Гб) адресного входа (1, -го блока обработки соединен с пятым выходом 0 - 1)-го шифратора, а (О -)+ + 2)-й разряд соединен с шестым выходом 30 0 -1)-го шифратора.Таблица 1