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

Abstract

Изобретение относитс  к вычислительной технике и может быть использовано при статистической обработке данных, например дл  обработки изображений. Целью изобретени   вл етс  повышение быстродействи . Устройство содержит блок микропрограммного управлени , блоки обработки, блоки буферной пам ти, блоки задержки, регистр результата, регистр ранга выходного элемента, шифраторы, элементы НЕ. 7 ил., 2 табл.

Description

Ё

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

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

На фиг.1 и 2 представлена структурна  схема устройства; на фиг.З - схема блока обработки; на фиг.4 - схема блока задержки; на фиг.5 - схема блока буферной пам ти. на фиг.6 - схема блока микропрограммного управлени ; на фиг.7 - схема шифратора.

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

мультиплексор 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). При этом на информационные входы 37 устройства от внешнего устройства поступают последовательно на каждом такте числа, а на вход 64 блока 1 - тактирующий импульс, на вход 65 - нулевое значение, а на вход 66 - единичное значение. Ноль на входе 65 устанавливает выходы счетчика 76 в единичное состо ние. (При использовании в качестве счетчика, например, микросхемы типа К155ИЕ7 входом установки в единичное состо ние выходов счетчика  вл етс  вход разрешени  параллельной загрузки. При этом на все входы счетчика подаютс  единицы). Выход элемента 79 И устанавли- ваетс  в 1, так как на его второй вход также поступает единица с выхода 66 блока 1. В результате на адресном входе узла 75 имеетс  код 111. Состо ние выходов узла 75 определ етс  из табл.1, а управл ющие сиг- налы, вырабатываемые на выходах блока, - из табл.2. Сигналы с выходом 41-45 блока 1 поступают на входы первого блока 2. Этот код записываетс  в первый регистр 14 блока 4 по заднему фронту тактирующего импуль- са, поступающего на вход 31 блока 2 с выхода блока 1. После третьего такта содержимое первого регистра 14 перепишетс  в третий регистр 14, Теперь, на каждом такте можно подавать на информационные входы 37 числа, которые записываютс  в блок 3 по низкому уровню сигнала, поступающего с выхода 59 блока 1 на входы 61 записи блоков 3. С выхода первого блока 3 Q-й разр д числа записываетс  в регистр 11 данных по заднему фронту импульса , поступающего с выхода элемента 19 ИЛИ первого блока 2. На тактирующий вход блока 3 импульс не поступает, К адресному входу узла 10 подключаетс  выход регистра 11 данных, так как на его вход разрешени  вывода с выхода третьего регистра 14 поступает нуль.

С выходов третьего регистра 14 на входы выбора функций узла 9 поступает код 0011, соответствующий функции установки нул  на выходе узла 9. Нуль с выхода узла 9 запишетс  в узел 10 по низкому уровню следующего тактирующего импульса, с приходом которого также происходит перепись содержимого третьего регистра 14 первого блока 2 в первый регистр 14 второго блока 2. Работа всех блоков 2 в этом режиме аналогична работе первого блока 2.

На вход 63 синхронизации блока 4 по- ступает с выхода 62 блока 1 тактирующий импульс. Запись в узел 67 происходит по низкому уровню тактирующего импульса.

Адрес, по которому происходит запись, определ етс  содержимым счетчика 68. ко- торое мен етс  по заднему фронту тактирующего импульса.

Значение задержки (1,1)-го блока 4 (I -2 , М) устанавливаетс  равной (1-1),а значений задержки (к, J)-ro блока 4 (к - 1ТТЯ. j -7. 5) равно (М-1).

Следующим этапом работы устройства  вл етс  начальна  установка, которой соответствует режим начального формировани  гистограмм (НФГ).

На вход 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. Коэффициент делени  счетчика ра- вен N (где N - число столбцов окна фильтра). На вход 63 блока 4 поступает ТИ, который  вл етс  также сигналом разрешени  записи в узел 67 с выхода 62 блока 1. По заднему фронту ТИ происходит изменение содержимого счетчика 68. Устранение гонок возможно подбором RC-цепочек таким образом, чтобы ТИ поступали в следующей последовательности: (блок 3 и блок 4) - регистр 11 данных - регистр 12 суммы - регистр 13 адреса - регистр 14 команды.

После начальной установки устройство переводитс  в основной этап работы, алгоритм которого имеет вид

Ci,i - R;

PU- O;

& 1.1-1;

дл  j 170 выполнить параллельно, дл  I f7Rl выполнить параллельно.

Cij-Cij$i,Hi,(Pi,);(1)

Ни(Ац) Ни(Ац)-1;(2)

Н.|(Ви)-Н|,(Вц)+1:(3)

Сн-ij Cij;

(§ I-H.J 8. ij:

Рн-U - PIJ,(4)

конец дл  I: если CMJ 0, то

(Q - J + 1)-й разр д Pij-n равен 1;

(Q - )-й разр д равен 0: $ 1, н-i 1. иначе

(Q -1 + 1}-й разр д PI.J+I равен 0;

(Q - }-й разр д равен 1; § 1.J+1 0,(5)

конец дл  J:

S Рм.о,(6)

где AIJ- входные данные, удал емые из окна фильтра по 1-му входу 37, Ь(1,)-м блоке 2:

BIJ - входные данные, включаемые в окно фильтра, поступающие по 1-му входу в (I,J)-M блоке 2;

HIJ(X) - гистограмма, формируема  в (i.j)- м блоке 2 по j старшим разр дам числа х;

Cij - значение промежуточной суммы в (I,J)-M блоке 2;

PIJ - значение результата в (i.j) м блоке 2;

R - значение ранга выходного элемента ,

$ - переменна  кода операции в (i.j)-M блоке 2,

1. то выполн етс  вычитание, иначе суммирование, S - результат.

Цикл в основном этапе работы устройства состоит из 3 тактов.

В каждом цикле на входы 37 устройства поступают обрабатываемые данные. Последовательность работы блока 2 внутри цикла имеет следующий вид: суммирование (вычитание ) отсчета гистограмм - удаление элемента столбца - включение элемента столбца. В первом такте на вход 64 блока 1 поступает тактирующий импульс, на входы 65 и 66 - единица от внешнего источника. Так как на вход 65 поступает единица, то разрешаетс  работа счетчика 76 в счетном режиме. В предыдущем режиме счетчик 76 был установлен в единичное состо ние. Поэтому при переходе в основной этап работы счетчика сбрасываетс  в нуль сигналом 1 с выхода элемента 78 И, на вход которого поступает Тс входа 65 блока 1. а на другой вход - Т с выхода элемента 77 И. Таким образом на адресный вход узла 75 поступает код 000. Состо ние выхода узла 75 видно

из табл. 1, а состо ние выхода блока 1 из. табл.2. После первого такта первого цикла основного этапа работы устройства во втором и третьем регистрах 14 блока 2 будут 5 находитс  управл ющие данные, соответствующие режиму начального формировани  гистограмм, а в первый регистр 14 запишутс  управл ющие данные режима вычитание отсчета гистогоамм. Во втором такте сигна0 лы, поступающие на входы блока 1, не измен ютс , По заднему фронту импульса, поступающего на счетный вход счетчика 76, его содержимое увеличитс 1 ча единицу. В результате на адресный вход узла 75 посту5 пит код 001, в соответствии с которым установ тс  на выходе блока 1 управл ющие денные режима удалени  элементов столбца блока 2, Эти дакные запишутс  в первый регистр 14 по заднему фронту ТИ на входе

0 31 первого блока 2 Во е.тирой регистр 14 перепишетс  содержимое первого pei истра 14. С приходом третьего тактирующего импульса на вход 64 блока 1 содержимое счетчик .76 будет равно 2, сигналы

5 поступающие на входы 65 и 66 блока 1 от внешнего источника, не мен ютс . На адресный вход узла 75 поступит код 010. На выходе блока 1 формируютс  сигналы установки режима включени  элементов столб0 ца, которые запишутс  в первьм регистр 14 первого блока 2. На третий регистр 14 перепишетс  содержимое второго регистоа 14, а во второй регистр 14 - содержимое первого регистра 14. На этом цикл работы блока 1

5 заканчиваетс  и с приходом очередного импульса на вход 64 блок 1 счетчик 76 сбрасываетс  в нуль, так как на выходе счетчика 76 будет код 11, который активизирует сигнал Сброс через элементы 77, 78 И. затем на0 чинаетс  следующий цикл.

С началом второго цикла раЬоты блски 1 и 2 начинают выполн ть операцию вычитани  отсчета гистограмм. CHI налы установки этого режима содержатс  в третьем

5 регистре 14, С выхода третьего регистра 14 поступает код 0110, соответствующий функции (А - В). На вход А первого операнда узла

9поступает число с выхода третьего регистра 12, так как на вход выбора канала муль0 типлексора 15 поступает с выхода регистра 14 лог. 1, что соответствует подключению первого канала мультиплексора 15 (куда поступает число с выхода третьего регистра 12) на его выход. Содержимое регистра 12

5 первого блока 2 равно значению ранга, так как вход 21 первого блока 2 подсоединен к выходу регистра 6. На вход В второго операнда узла 9 поступает число с выхода узла

10пам ти. Адрес считывани  узла 10 определ етс  содержимым третьего регистра 13

адреса, так как выход этого регистра подключен к адресному входу узла 10 единицей с выхода третьего регистра 14, после элемента 16 НЕ. Выход регистра 11 данных отключаетс  от адресного входа единицей с выхода третьего регистра 14. Содержимое регистра 13 адреса первого блока 2 равно О, так как вход 22 адреса первого блока 2 соединен с входом лог, О. (Операци  (1) алгоритма). В первом такте цикла на тактовый вход 61 блока 3 с выхода 58 блока 1 поступит импульс. В результате содержимое счетчика 71 изменитс , указыва  на адрес удал емого элемента столбца.

Во втором такте по заднему фронту ТИ на входе 31 блока 2 происходит перепись содержимого третьего регистра 14, третьего рагистра 13 адреса и результата с выхода узла 9 первого блока 2 в первые регистры 14, 13 и 12 второго блока 2. (Операци  (4) алгоритма). Первый блок 2 во втором такте будет выполн ть операцию удалени  элемента столбца, так как в третьем регистре

14содержитс  код режима удалени  столбца . На входы выбора функций узла 9 поступаете выхода третьего регистра 14 код 1111, что соответствует функции (А-1).-(Операци  (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. В третьем такте в первый блок 3 по низкому уровню сигнала, поступающего на вход 61 записи блока 3 с выхода 58 блока 1, запишетс  значение элемента вход щего

столбца. Третий регистр 14 (1,1)-го блока 2 будет содержать код режима включени  элемента столбца. На вход выбора функций узла 9 поступает код 0000, соответствующий

функции (А+1). На вход А первого операнда поступает число с выхода узла 10, так как на вход выбора канала мультиплексора с выхода п того разр да третьего регистра 14 поступает #, соответствующий подключению

0 второго канала мультиплексора 15 к выходу мультиплексора. В регистр 11 данных с выхода первого блока 3 записываетс  значение элемента вход щего столбца по заднему фронту ТИ. Нуль на выходе п того

5 разр да третьего регистра 14 подключает вход регистра 11 данных к адресному входу узла 10. Результат с выхода узла 9 записываетс  в узел 10 пам ти по тому же адресу, с которого производилось считывание по

0 низкому уровню ТИ первого такта следующего цикла. Значение вход щего столбца с выхода первого блока 3 также запишетс  в (1,2)-ой блок 4 по низкому уровню ТИ, поступающего с выхода 62 блока 1 в третьем такте

5 текущего цикла. На вход 60 блока 3 импульс не поступает (Операци  (3) алгоритма).

В следующем цикле первый блок 2 начинает обрабатывать первый элемент следующего удал емого и вставл емого

0 столбца, (2,1)-ый блок 2 обрабатывает второй элемент предыдущего удал емого и вставл емого столбца с учетом значени  промежуточной суммы, полученной в первом блоке 2 (операци  (4) алгоритма).

5 Второй элемент столбца поступает с задержкой на один цикл по отношению к первому элементу этого же столбца. Задержка обеспечиваетс  (2,1)-ым блоком 4. Последовательность режима работы и работа (2,1)-го

0 блока 2 аналогична последовательности ре- жимгуэаботы первого блока 2. В l-ом цикле (I 3, М) обрабатываетс  1-ый элемент столбца в (I. 1)-ом блоке 2. Задержку 1-го элемента столбца осуществл ет (М)-ый блок 4 (I

5 2, М) на (1-1) циклов по отношению к первому элементу этого же столбца. После первого такта М-ro цикла сигналы с выходов 32-36 и выхода 30 признака результата (М, 1)-го блока 1 поступают на входы 46-51 первого

0 шифратора соответственно, а с выхода 29 промежуточной суммы и выхода 28 адреса - на вход 21 промежуточной суммы и на (Q - 2)- младших разр дов входа 22 адреса (1. 2)-го блока 2.

5 Единица на входе 50 шифратора 7 отключает выходы узла 86 от выходов 52-55 шифратора 7. Нуль с выхода элемента 88 поступает на входы разрешени  вывода узлов 84, 85. Подключение выходов узлов 64 и А к выходам шифратора 7 зависит от состс ни  сигнала на входе 51 шифратора 7, определ емого значением признака результата . Если значение сигнала на входе 51 равно 1, то подключаетс  выход узла 85, иначе выход узла 84. Сигнал с выхода элемента 87 НЕ поступает на выход 38, а с входа 51 - на выход 39 блока 7. При подключении выхода узла 1 на выходы 52-56 шифратора 7 пост у- пает код 0110. что соответствует функции (А - В) узла 9, а при подключении узла 85 - код 1001 функции (А + В) (операци  (5) алгоритма ). Выход 38 первого шифратора 7 соединен с Q-ым разр дом входа 22 адреса (1,2)-го блока 2, а выход 39 - с (Q 1)-ым разр дом. Во втором и третьем тактах цикла сигнал на входе 50 шифратора 7 равен И. что соответствует подключению выходов узла 86 к выходам 52-55 блока 7. Это означает, что код операции через шифратор 7 передаетс  без изменени .

Аналогично происходит формирование и передача команд от (М, J)-ro блока 2 к {1 J+ + 1)-му блоку 2 через j-ый шифрэт ор 7 (j - Т, Q - 1). При этом (Q - J + 2)-ый (j 27Q) разр д входа 22 адреса Q, 1)-го блока 2 соедин етс  с выходом 38, a (Q - j + 1)- ый разр д с. выходом 39 0 шифратора 7.

Другие (Q - 2) разр да входа 22 адресэ (1, J)-ro6flOKa2(J 2, Q)соединены с выходом 28 адреса (М, jjJJ-го блока 2 (I, )-ый блока 4 (I 1, М, J - 2, Q) обеспечивает задержку данных на (М 1) циклов.

Значени  (Q - 1) старших разр дов третьего регистра 13 адреса и инверсноэ значение признака результата (М, Q)-ro бло- ка 2 запишутс  в регистр 5 результата

Claims (1)

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

   регистра данных и третьего регистра адреса соединены с адресным входом узла пам ти и с адресным выходом блока обработки, выход первого регистра суммы соединен с информационным входом второго регистра суммы, выход которого соединен с информационным входом третьего регистра суммы , выход которого соединен с первым информационным входом мультиплексора. выход которого соединен с входом первого операнда арифметического узла, вход второго операнда которого подключен к выходу пам ти и к второму информационному входу мультиплексора, вьиод результата арифметического узла соединен с входом данных узла пам ти и с выходом промежуточной суммы блока обработки, выход о.ображе- ни  эквивалентности арифметического узла соединен через первый элемент НЕ с первым входом первого элемента ИЛИ, второй вход которого соединен с выходом старшего разр да результата агифметичесокго узла, входы резр дов второго регистра команды соединены с выходами разр дов первого регистра команды соответственно, входы разр дов третьего регистра команды соединены с выходами разр дов второго регистра команды соответственно, выходы разр дов с первого по четвертый третьего регистра команды соединены с входами выбора функций арифметического узла и с первого по четвертый управл ющими выходами блока обработки соответственно выход п того разр да регистра команды соединен с входом второго элемента НЕ, с входом выбора канала мультиплексора, с п тым управл ющим выходом блока обработки с входом разрешени  вывода регистра данных и с первым входом второго элемента ИЛИ, выход первого регистра адреса соединен с информационным входом второго регистра адреса, выход которого соединен с информационным входом третьего регистра адреса, вход разрешени  вывода которого соединен с выходом второго элемента НЕ, входы синхронизации каждого регистра команды , регистра суммы и регистра адреса, второй вход второго элемента ИЛИ соединены с входом синхронизации блока обработки , выход второго элемента ИЛИ соединен с входом записи узла пам ти и с входом синхронизации регистра данных, информационный вход 1-го блока буферной пам ти (I 1, М)  вл етс  i-м информационным входом устройства, Q-й разр д выхода первого блока буферной пам ти соединен с информационным входом (i, 1)-го блока задержки . Q-й разр д входа данных (i, 1)-го 11- 2, М) блока обработки соединен с Q-м .разр дом информационного входа (I, 1)-го

   блоке задержки, j старших разр дов входа данных (I, }-го блока обработки (I - 1, М, j - -2, U) соединены с j старшими разр дами выхода (I, J)-ro блока задержки, (Q - j) младших разр дов входа данных (I, j)ro блока обработки (I - 1. М, J 2TQ) соединены с входом логического нул  устройства, выход (I, 1)-го блока задержки (I - 2, М) соединен с информационным входом (I, 2)-го блока задержки , адресный вход первого блока обработки соединен с входом логического нул  устройства, адресный вход (1. J)-ro блока обработки (J - 2, Q) соединен с адресным выходом (М, J - 1)-го блока обработки, выход признака результата (М, Q)-ro блока обработки соединен с входом элемента НЕ, адресный выход (М, Q)-ro блока обработки и выход элемента НЕ соединены с входами регистра результата соответственно, выход регистра результата  вл етс  выходом устройства , вход промежуточной суммы первого блока обработки соединен с выходом регистра ранга выходного элемента, с первого по п тый управл ющие входы первого блока обработки соединены с первого по п тый управл ющими выходами блока микропрограммного управлени  соответственно , с первого по п тый управл ющие выходы, адресный выход и выход промежуточной суммы (I, j)-ro блока обработки (I Т,

   М -1. J 1, Q) соединены с первого по п тый управл ющими входами, адресным входом и входом промежуточной суммы (I + 1, J) блока обработки соответственно, выход

   промежуточной суммы (М, j)-ro блока обработки 0 1. Q -1) соединен с входом промежуточной суммы (1, J + 1)-го блока обработки, с первого по п тый управл ющие выходы и выход признака результата (М, j)-ro блока

   обработки соединены с первого по шестой входами j-ro шифратора, с первого по п тый выходы J-ro шифратора (« 1, Q -1) соединены с первого по п тый управл ющими входами (1, J + 1)-го блока обработки

   соответственно, шестой и седьмой выходы блока микропрограммного управлени  соединены с входом синхронизации и входом разрешени  записи каждого блока буферной пам ти, восьмой выход блока микропрограммного управлени  соединен с входом синхронизации каждого блока задержки , дев тый выход соединен с входом синхронизации каждого блока обработки, три входа блока микропрограммного управлени   вл ютс  входами команд устройства , (Q - j + 1)-й разр д 0 2, U) адресного входа (1, J)-ro блока обработки соединен с п тым выходом (J - 1)-го шифратора, a (Q - J+ + 2)-й разр д соединен с шестым выходом

   0 1) г° шифратора.

   Таблица 1

   57

   -э

   If

   Фиг.1

   Л

   69

   67

   63

   /73

   L...

   фигА

   .Г7П

   51

   72

   Ж

   60

   7

   И

   фиг. 5

   Фигб

   ..J

   фиг.7