Однородная вычислительная структура для обработки трехмерных бинарных матриц Советский патент 1991 года по МПК G06F7/00 

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

Целью изобретения является расширение функциональных возможностей за счет выполнения за одну команду вариантов операции поиска элементов массива по заданному интервалу в трехмерной бинарной матрице.

На фиг.1 приведена структурная схема однородной вычислительной структуры для обработки трехмерных бинарных матриц, на фиг.2 - функциональная схема ячейки однородной вычислительной структуры; на фиг 3 - схема размещения трехмерных бинарных матриц в ячейках однородной вычислительной структуры.

Однородная вычислительная структура для обработки трехмерных бинарных матриц (фиг.1) содержит j i k ячеек 1 (где j - количество слоев, - количество строк, k - количество столбцов), три группы тактовых входов 2-4, группу входов признака верхней границы 5, группу входов значения числа 6, группу входов признака нижней границы 7, две группы настроечных входов 8-9, группу входов признака значения интервала 10, три группы тактовых выходов 11-13, группу выходов значения интервала 14, две группы управляющих выходов 15 и 16, группу выходов признака нижней границы 17, группу выходов значения числа 18,

XI

О

N3 ОС

О1 3

группу выходов признака верхней границы 19.

Ячейка однородной вычислительной структуры (фмг.2) содержит три триггера 20- 22, шесть элементов И 23-28, и три элемента ИЛ И 29-31.

Ячейка однородной структуры реализует следующие функции:

(1) CU1 Си ; (2) Cl Са; (3)d С (4) U1 UCu ; ( аСа; (6)d1 dCd; (7)Zl Zi (a1vU1 (80 Z2(a1vd1);

(9)

M ZiAVvZzaV

где и ., a,, dr - состояния триггеров 20-22 соответственно.

Функции позволяют осуществить запись информации в триггеры 20-22 ячейки 1. Функции 7 - 9 используются для выполнения операции поиска всех элементов, расположенных в заданном интервале значений. С помощью функций 1 - 3 осуществляют тактирование ввода трехмерных бинарных матриц в однородную вычислительную структуру.

Выполнение операции поиска по интервалу в трехмерной бинарной матрице с помощью однородной вычислительной структуры осуществляют следующим образом.

Перед началом вычислений трехмерные двоичные массивы, соответствующие верхней и нижней границе и массив, подлежащий обработке, ориентируют и вводят в однородную структуру таким образом, что разряды отсчетов двумерной функции располагаются вдоль строк, младшими разрядами в направлении увеличения индекса К. Направления координатных осей X,Y,Z соответствуют направлениям в сторону увеличения индексов I.J.K (фиг.З).

Отсчеты Uij, t5ij и AIJ массивов верхней и нижней границы и массива, подлежащего обработке, поразрядно подаются на соответствующие входы признака верхней границы 5 группы, признака нижней границы 7 группы и значения члена б группы ячеек левой грани однородной структуры, начиная с младших разрядов. Тактовые сигналы, поступающие на тактовые входы 2-4 (Си, Cd, Са), осуществляют запись разрядов отсчетов в триггеры 20-22 ячеек. Поскольку выходы признака нижней границы 17, значения числа 18 и признака верхней границы 19 ячейки S-ro столбца в n-й строке m-ro слоя (, k-1, , i; ,j) соединены с входами признака нижней границы 7, зна- .чения числа б и признака верхней границы 5 ячейки (5+1)-го столбца n-й строки m-ro слоя, то по истечении К-тактов разряды отсчетов продвинутся по строкам на К-ячеек и заполнят всю однородную структуру. Тактирование ввода каждого из трех массивов осуществляется независимо друг от друга,

по трем различным шинам Си. Са, Са. На настроечные входы первой 8 и второй 9 групп (Zi и Z2) и входы признака значения интервала 10 группы ячеек левой грани однеродной структуры подаются константы Zi

1, 2.2 1, V 0 соответственно.

После ввода информации в каждой строке однородной структуры с помощью Сигнала Zi производится поразрядное сравнение (начиная со старших разрядов)хранимого з триггерах 21 ячеек данной строки числа AIJ aiji, asp,... с верхним граничным признаком , Uij2хранимом в триггерах 20 ячеек этой же строки. Одновременно с помощью сигнала 7.2 производится

сравнение Aij с нижним граничным пр изна- ком DIJ dij, dij2,..., хранимом в триггерах 22 ячеек этой строки. По завершении переходных процессов при сравнении Ац с Uij сигнал У на выходе значения интервала 14 группы

правой грани однородной структуры в соответствии с выражениями (7) и (9) принимает значение V 1 только в том случае, когда , т.е. находится вне заданного интервала. Аналогично при сравнении AIJ с DIJ в

соответствии с выражениями (8) и (9) сигнал V на выходе значения интервала 14 группы правой грани однородной структуры принимает значение V 1 только в том случае, когда т.е. находитсявне

заданного интервала. Следовательно, только ситуация свидетельствует о том, что число, записанное в данной строке, удовлетворяет критерию поиска (Dij Aij Uij). Характер неравенства на границах заданного

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

Под D, А и U подразумеваются поверхиости двумерных функций, представленные совокупностью отсчетов DIJ. AIJ и Uij

Из таблицы значений интервалов видно, что комбинируя сигналы V, Z, и Z мoжнo с помощью предлагаемой однородной

структуры за одну команду выполнить различные варианты поиска в заданном интер- вале. Например, комбинация v z 1 соответствует поиску D A U, а комбинация VfZ Z2 1 поиску .

Если в качестве нижних граничных признаков Dij использовать числа меньшие, чем минимальные возможные значения отсчетов Aij, то за одну команду можно выделить все . Если в качестве верхних граничных признаков использовать числа большие, чем максимальные возможные значения отсчетов AIJ, то можно выделить все Если задать U D R, то выполнится поиск по совпадению .

Однородная вычислительная структура для обработки трехмерных бинарных матриц позволяет выполнять за одну команду различные варианты операции поиска по интервалу элементов в трехмерных бинарных матрицах; в каждой строке задавать отличные от других строк значения границ интервала поиска, что позволяет осуществлять обработку трехмерных массивов, представляющих собой изображения двумерных функций от координат плоскости, при этом на обрабатываемом изображении выделяются области, в которых отсчеты двумерной функции находятся между ограничивающими поверхностями U и D; за счет независимого тактирования триггеров 20-22 в ячейках однородной структуры видоизменять границы интервала и обрабатываемый массив путем сдвига разрядов отсчетов параллельно по строкам однородной структуры.

Дополнительным эффектом изобретения является повышение производительности однородной вычислительной структуры при выполнении операции поиска.

Формула изобретения

Однородная вычислительная структура для обработки трехмерных бинарных матриц, содержащая ячеек (где t 1 - количество строк; k - количество столбцов; -J - количество слоев), причем m-й настроечный вход первой группы (где ,j) соединен с первым настроечным входом ячейки первого столбца m-ro слоя, второй настроечный вход которой соединен с m-м настроечным входом второй группы, m-й вход признака значения интервала группы сое- дине н с входом признака значения интервала ячейки первого столбца т-го слоя, первый управляющий выход ячейки S-ro столбца (где ,k-1) m-ro слоя соединен с первым настроечным входом ячейки (S+1)- го столбца т-го слоя, второй настроечный вход которой соеднинен с вторым управляющим выходом ячейки S-ro столбца т-гр слоя, выход значения интервала которой соединен с входом признака значения интервала ячейки (S+1)-ro столбца m-го слоя, выход значения интервала ячейки k-ro столбца пп-го слоя соединен с выходом значения интервала группы, m-й управляющий выход первой группы соединен с первым управляющим выходом ячейки k-ro столбца (т-го слоя, второй управляющий выход которой является управляющим выходом второй

группы, причем каждая ячейка содержит первый триггер, шесть элементов И и три элемента ИЛИ, первый вход первого из которых соединен с выходом первого элемента И и первым входом второго элемента И, второй вход которого соединен с первым входом третьего элемента И, второй вход которого и первый вход первого элемента И соединен с первым настроечным входом

0 ячейки, второй настроечный вход которой соединен с первыми входами четвертого и пятого элементов И, выходы которых соединены соответственно с первым и вторым входами второго элемента ИЛИ, второй

5 вход пятого элемента И соединен с первым входом шестого элемента И, второй вход которого соединен с первым входом второго элемента ИЛИ, выход третьего элемента И соединен с вторым входом первого элемен0 та ИЛИ, выход которого является первым управляющим выходом ячейки, второй управляющий выход которой соединен с выходом второго элемента ИЛИ. выход значения интервала ячейки соединен с выходом

5 третьего элемента ИЛИ, первый вход которого соединен с входом признака значения интервала, выход второго элемента И соединен с вторым входом третьего элемента ИЛИ, третий вход которого соединен с вы0 ходом шестого элемента И,отличающа- я с я тем, что, с целью расширения функциональных возможностей за счет выполнения за одну команду вариантов операции поиска элементов массива по заданному ин5 тервалу в трехмерной бинарной матрице, она содержит v k j ячеек (где v 2,i), причем тактовый вход первой группы соединен с первым тактовым входом ячейки d-ro столбца (где ,k) n-й строки (где ,1) t-ro

0 слоя, второй тактовый вход которой соединен с тактовым входом второй группы, тактовый вход третьей группы соединен с третьим тактовым входом ячейки d-ro столбца п-й строки t-ro слоя, первый, второй

5 и третий тактовые выходы ячейки d-ro столбца n-й строки w-ro слоя (где , j-1) соединены соответственно с первым, вторым и третьим тактовыми входами ячейки d-ro столбца n-й строки (w+1)-ro слоя, 1-й выход

0 (где ,2,3) ячейки d-ro столбца n-й строки j-го слоя соединен с тактовым выходом 1-й группы, вход признака верхней границы группы соединен с входом признака верхней границы ячейки t-ro столбца n-й строки

5 m-ro слоя, вход признака нижней границы которой соединен с входом признака нижней границы группы, вход значения числа группы соединен с входом значения числа ячейки t-ro столбца n-й строки m-го слоя, выход значения числа ячейки S-го столбца

n-й строки m-ro слоя соединен с входом значения числа ячейки (S-Mj-ro столбца п-й строки m-ro слоя, выход признака гижней границы и выход признака верхней границы ячейки S-ro столбца n-й строки m-ro слоя соединены соответственно с входом признака нижней границы и входом признака верхней границы ячейки (S+1)-ro столбца п- й строки гл-й слоя, выход признака нижней границы и выход признака верхней границы ячейки k-ro столбца n-й строки m-ro слоя соединены соответственно с выходом признака нижней границы группы м выходов признака верхней границы группы, выход значения чисЛа ячейки k-ro столбца n-й строки rn-го слоя соединен с выходов значения числа группы, настроечный вход первой группы и настроечный вход второй группы соединены соответственно с первым на- строечным входом м вторым настроечным входом ячейки t-ro столбца V-й строки rn-ro слоя, вход признака значения интервала которой соединен с входом признака значения интервала группы, первый управляющий выход, второй упрээлящий выход и выход значения интервала ячейки S-ro столбца, V-й строки m-ro слоя соединены соответственно с первым настроечным входом, вторым настроечным входом м входом признака значения интерзала ячейки

и

(S+IJ-ro столбца, V-й строки m-ro слоя, первый управляющий выход, второй управляющий выход м выход признака значения интервала k-ro столбца V-й строки m-ro слоя 5 соединены соответственно с управляющим выходом первой группы, с управляющим выходом второй группы и выходом признака значения интервала группы, причем ячейка . содержит второй и третий триггеры, такто- 10 вые входы которых и тактовый вход первого триггера соединены соответственно с вто- рым, третьим и первым тактовыми входами ячейки, прямой выход первого триггера соединен с выходом признака верхней грани- IB 8ды ячейш, выход значения числа которой соединен с вторым входом первого элемента Л к прямым выходом второго триггера , ин- версиый выход которого соединен с вторым входом четвертого элемента И, второй вход 20 второго элемента И соединен с инверсным выходом первого триггера, информационный вход которого и информационные входы второго и третьего триггеров соединены соответственно с входом признака верхнзй границы, 2В входом значения числа и входом признака мшкией границы ячейки, выход третьего триггера соединен с вторым входом пятого элемента 1Л и выходом признака нижней границы ячейки, 1-й тактовый выход которой соединен 30 с тактовым входом 1-го триггера.

01 J

Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах поточной обработки информации. Целью изобретения является расширение функциональных возможностей за счет выполнения за одну команду вариантов операции поиска элементов массива по заданному интервалу в трехмерной бинарной матрице. Однородная вычислительная структура содержит j x xi k - ячеек (где j - количество слоев; i - строк; k - столбцов), каждая из которых содержит три триггера, шесть элементов И и три элемента ИЛИ. Однородная вычислительная структура позволяет выполнять за одну команду операцию поиска по интервалу в трехмерной бинарной матрице, которая представляет собой двоичные отсчеты двумерной функции, при этом границы интервала могут задаваться в виде произвольных поверхностей двумерной функции. 1 табл, Зил, С/1 С

-у-

-o

N. i

v x

n° и

/

/

я

/X

Ј

6SC20Z.I

234

м

Фиг.з