Однородная вычислительная структура для обработки трехмерных бинарных матриц

 

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

СООЗ СОБЕТСКИХ сОцидлистических

РЕСПУБДИК (51)5 G 06 F 7/00

ГОсудАМстВенный кОмитет

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ е

/ (21) 4745505/24 (22) 03,10.89 (46) 30.12.91. Бюл. М 48 (71) Днепропетровский государственный университет им, 300-летия воссоединения

Украины с Россией (72) А,Л. Белоус и П.B. Крот (53) 681.3 (088,8) (56) Авторское свидетельство СССР

N . 610105, кл, G 06 F 7/00, 1975.

Авторское свидетельство СССР

N 851398, кл. G 06 F 7/00, 1979. (54) ОДНОРОДНАЯ ВЫЧИСЛИТЕЛЬНАЯ

СТРУКТУРА ДЛЯ ОБРАБОТКИ ТРЕХМЕРНЫХ БИНАРНЫХ МАТРИЦ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах поточной обработки информации. Целью изобретения

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

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

На фиг.1 приведена структурная схема однородной вычислительной структуры для обработки трехмерных бинарных матриц, на фиг.2 — функциональная схема ячейки однородной вычислительной структуры; на фиг,3 — схема размещения трехмерных би. Ж,, 1702359 А1 является расширение функциональных возможностей за счет выполнения за одну команду вариантов операции поиска элементов массива по заданному интервалу в трехмерной бинарной матрице. Однородная вычислительная структура содержит / » хЪ k — ячеек (где ) — количество слоев; i— строк; k — столбцов), каждая из которых содержит три триггера, шесть элементов И и три элемента ИЛИ. Однородная вычислительная структура позволяет выполнять за одну команду операцию поиска по интервалу в трехмерной бинарной матрице, которая представляет собой двоичные отсчеты двумерной функции, при этом границы интервала могут задаваться в виде произвольных поверхностей двумерной функции. 1 табл, 3 ил, нарных матриц в ячейках однородной вычислительной структуры.

Однородная вычислительная структура для обработки трехмерных бинарных матриц (фиг.1) содержит j» i «k ячеек 1 (где J— количество слоев, i — количество строк, k— количество столбцов), три группы тактовых входов 2 — 4, группу входов признака верхней границы 5, группу входов значения числа 6, группу входов признака нижней границы 7, две группы настроечных входов

8-9, группу входов признака значения интервала 10, три группы тактовых выходов

11 — 13, группу выходов значения интервала

14, две группы управляющих выходов 15 и

16, группу выходов признака нижней границы 17, группу выходов значения числа 18, группу выходов признака верхней границы

19.

Ячейка однородной вычислительной структуры (фиг.2) содержит три триггера 2О—

22, шесть элементов И 23 — 28, и три элемен- 5 та ИЛИ 29 — 31.

Ячейка однородной структуры реализует следующие функции: (1) C01 = Cu; (2) Са1 = C,. (ЗФ = Cd. (4}0 =UCU; (5} =ас,; (6)d1 =dcd, 10 (7) б = Z1(а ч0 ) (8)Zj = Z2(a vd1); (9)V = V Z1A1UqvZ2a3d1 где u, qi, d — состояния триггеров

20-22 соответственно.

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

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

Перед началом вычислений трехмерные двоичные массивы, соответствующие верхней и нижней границе и массив, подлежащий обработке, ориентируют и вводят в однородную GTpgKTgpg таким образом, что разряды отсчетов двумерной функции рас- - 5 полагаются вдоль строк, младшими разрядами в направлении увеличения индекса К.

Направления координатных осей X,Y,Z сеответствуют направлениям в сторону увеличения индексов Ц,К (фиг.З).

4О

Отсчеты 0ц, Оц и Ац массивов верхней и нижней границы и массива, подлежащего обработке, поразрядно подаются на соответствующие входы признака верхней гра45 ницы 5 группы, признака нижней границы 7 группы и значения члена 6 группы ячеек левой грани однородной структуры, начиная с младших разрядов. Тактовые сигналы,. поступающие на тактовые входы 2-4 (Cu, Cd, Са), осуществляют запись разрядов GT- О счетов в триггеры 20 — 22 ячеек. Поскольку выходы признака нижней границы 17, значения числа 18 и признака верхней границы

19 ячейки 5-го столбца в и-й строке ln-re ( слоя (S=1, к-1, п=1, l; m=l„j) соединены с входами признака нижней границы 7, зна.чения числа 6 и признака верхней границы

5 ячейки (S+1)-го столбца и-й строки m-rG слоя, то по истечении К-тактов разряды отсчетов продвинутся по строкам на K-ячеек и заполнят всю однородную структуру. Тактирование ввода каждого из трех массивов осуществляется независимо друг от друга, по трем различным шинам Cu, Cd, Ca. Ha настроечные входы первой 8 и второй 9 групп (Z1 и Z2) и входы признака значения интервала 10 группы ячеек левой грани однородной структуры подаются константы 21

= 1, Z2= 1, V = О соответственно.

После ввода информации в каждой строке однородной структуры с помощью

Сигнала Z1 производится поразрядное сравнение(начиная со старших разрядов) хранимого В триггерах 21 ячеек данной строки числа Ail = aij1, ац2,... с верхним граничным признаком Ц)=0Ц1, Ulj2"" хранимом В TpPlr

repax 2О ячеек этой же строки. Одновременно с помощью сигнала Z2 производится сравнение АЦ с нижним граничным признаком Dlj = б, бр, „хранимом в триггерах 22 ячеек этой строки. По завершении переходных процессов при сравнении Ап с Ull сигнал

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

All>Ull, т.е. находится вне заданного интервала. Аналогично при сравнении Ап с Оп в соответствии с выражениями (8) и (9) сигнал

V на выходе значения интервала 14 группы правой грани однородной структуры принимает значение V = 1 только в том случае, когда AijgDlj, г,е. находится вне заданного ийтервала. Следовательно, тольf ко ситуация V =О свидетельствует о том, что число, записанное в данной строке, удовлетворяет критерию поиска (Dii А 1 0щ. Характер неравенства на границах заданного интервала может быть при этом определен по сигналам Z и Zz ячеек на правой грани в соответствии с таблицей значений интервэЛ ОВ.

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

Из таблицы значений интервалов видно, что комбинируя сигналы V, Z,l и Z ìîæíî г с помощью предлагаемой однородной структуры за одну команду выполнить различные варианты поиска в заданном интервале. Например, комбинация V Z, = 1

i г соответствует поиску О А

Если в качестве нижних граничных признаков О испольэовать числа меньшие, чем минимальные возможные значения отсчетов All, то за одну команду можно выделить все А 1<О, Если в качестве верхних гранич1702359

10

50

55 ных признаков использовать числа большие, чем максимальные возможные значения отсчетов Aii, то можно выделить все

AiI>DII. Если задать 0 = D = R, то выполнится поиск по совпадению Aii=RiI.

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

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

Однородная вычислительная структура для обработки трехмерных бинарных матриц, содержащая t

j — количество слоев), причем m-й настроечный вход первой группы (где m=1,j) соединен с первым настроечным входом ячейки первого столбца m-ro слоя, второй настроечный вход которой соединен с m-м настроечным входом второй группы, m-й вход признака значения интервала группы соединен с входом признака значения интервала ячейки первого столбца m-го слоя, первый управляющий выход ячейки S-го столбца (где 5=1,k-1) m-ro слоя соединен с первым настроечным входом ячейки (S+1)го столбца m-ro слоя, второй настроечный вход которой соеднинен с вторым управляющим выходом ячейки S-го столбца m-rq слоя, выход значения интервала которой соединен с входом призннака значения интервала ячейки ($+1)-ro столбца m-го слоя, выход значения интервала ячейки k-ro столбца m-го слоя соединен с выходом значения интервала группы, m-й управляющий выход первой группы соединен с первым управляющим выходом ячейки k-ro столбца (m-го слоя, второй управляющий выход которой является управляющим выходом второй группы, причем каждая ячейка содержит первый триггер, шесть элементов И и три элемента ИЛИ, первый вход первого из которых соединен с выходом первого элемента И и первым входом второго элемента И, второй вход которого соединен с первым входом третьего элемента И, второй вход которого и первый вход первого элемента И соединен с первым настроечным входом ячейки, второй настроечный вход которой соединен с первыми входами четвертого и пятого элементов И, выходы которых соединены соответственно с первым и вторым входами второго элемента ИЛИ, второй вход пятого элемента И соединен с первым входом шестого элемента И, второй вход которого соединен с первым входом второго элемента ИЛИ, выход третьего элемента И соединен с вторым входом первого элемента ИЛИ, выход которого является первым управляющим выходом ячейки, второй управляющий выход которой соединен с выходом второго элемента ИЛИ, выход значения интервала ячейки соединен с выходом третьего элемента ИЛИ, первый вход которого соединен с входом признака значения интервала, выход второго элемента И соединен с вторым входом третьего элемента

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

j-го слоя соединен с тактовым выходом I-й группы, вход признака верхней границы группы соединен с входом признака верхней границы ячейки t-го столбца п-й строки

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

17Î2359 п-й строки m-ro слоя соединен с входом значения числа ячейки (S+1$ro столбца и-й строки m-ГО слОя, ВыхОд признака I .Mæí6É границы и выход признака верхней границы ячейки S-го столбца и-й строки m-ro слоя соединены соответственно с входом признака нижней границы и входом признака верхней границы ячейки (3+1 -Го столбца ий строки m-й слоя, выход признака нижней границы и выход признака верхней границы ,ячейки k-ro столбца и-й строки m-го слоя ,соединены соответственно с выходом признака нижней границы группы и выходом признака верхней границы группы, выход значения чисйа ячейки k-го столбца и-Й строки m-ro слоя соединен с выходом значения числа группы, настроечный Вход первой группы и настроечный вход Второй группы соединены соответственно с первым на строечным входом и вторым настроечным входом ячейки t-го столбца V-й строки в-го слоя, вход прйзнака значения интервала которой сОединен с Входом признака значения интервала группы, первый управляющий выход, второй управлящий

ВыхОд и Выход значения интерВала ячейки

S-го столбца, V-й строки m-го слоя соединеНЫ СООТ86ТСТВЕННО С ПврВЫМ НВСТРОЕЧНЫМ входом, Вторым настроечным входом и входом признака значения интервала ячейки (S+1)-ro столбца, Ч-й строки m-го слоя, перВый упраВляющий выход, Второй управляющий выход и выход признака значения интервала k-го столбца Ч-й строки m-го слоя

6 соединены соответственно с управляющим

Выходом первой Группы. суправляющим выходом Второй Группы и выхОдом признака значения интервала группы, причем ячейка содержит второй и третий триггеры, такто1(вые входы которых и тактовый вход первого триггера соединены соответственно с вторым, третьим и первым тактовыми входами ячейки, прямОЙ Выход rI6pBoro триГГера соеДинен с ВЫХОДОМ rIPM3H8KB 86PxHGA ГPBHM16 цы ячейки, выход значения числа которой соединен с вторым входом первого элемента

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

2О Второго элемента И соединен с инверсным

Выходом rlepIIoro т риггера, информационный вход которого и информационные входы второго и третьего триггеров соединены соответственно с входом признака верхней границы, 25 входом значения числа и входом признака нижней границы ячейки, выход третьего триггера соединен с вторым входом пятого элемента И M выходом признака нижней границы ячейки, 1-й тактовый выход которой соединен

ЗО о тактовым входом I-го триггера.

1702359

1702359

1702359

Составитель В.Сорокин

Техред М.Моргентал Корректор B. Гирняк

Редактор А.Долинич

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 4543 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4!5