Вычислительное устройство для ранговой фильтрации Советский патент 1991 года по МПК G06F15/36 G06F15/66 

Ё

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

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

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

На фиг.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,

Цикл в основном этапе работы устройства состоит из 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 результата

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

регистра данных и третьего регистра адреса соединены с адресным входом узла памяти и с адресным выходом блока обработки, выход первого регистра суммы соединен с информационным входом второго регистра суммы, выход которого соединен с информационным входом третьего регистра суммы, выход которого соединен с первым информационным входом мультиплексора. выход которого соединен с входом первого операнда арифметического узла, вход второго операнда которого подключен к выходу памяти и к второму информационному входу мультиплексора, вьиод результата арифметического узла соединен с входом данных узла памяти и с выходом промежуточной суммы блока обработки, выход о.ображе- ния эквивалентности арифметического узла соединен через первый элемент НЕ с первым входом первого элемента ИЛИ, второй вход которого соединен с выходом старшего разряда результата агифметичесокго узла, входы резрядов второго регистра команды соединены с выходами разрядов первого регистра команды соответственно, входы разрядов третьего регистра команды соединены с выходами разрядов второго регистра команды соответственно, выходы разрядов с первого по четвертый третьего регистра команды соединены с входами выбора функций арифметического узла и с первого по четвертый управляющими выходами блока обработки соответственно выход пятого разряда регистра команды соединен с входом второго элемента НЕ, с входом выбора канала мультиплексора, с пятым управляющим выходом блока обработки с входом разрешения вывода регистра данных и с первым входом второго элемента ИЛИ, выход первого регистра адреса соединен с информационным входом второго регистра адреса, выход которого соединен с информационным входом третьего регистра адреса, вход разрешения вывода которого соединен с выходом второго элемента НЕ, входы синхронизации каждого регистра команды, регистра суммы и регистра адреса, второй вход второго элемента ИЛИ соединены с входом синхронизации блока обработки, выход второго элемента ИЛИ соединен с входом записи узла памяти и с входом синхронизации регистра данных, информационный вход 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