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

СООЗ СОВЕТСКИХсОциАлистическиРЕСПУБДИК 7023 51)5 0 06 Г 7/00 ОПИСАНИЕ И ЗОБ РЕТ ЕЛЬСТ ВТОРСКОМУ Св ородной выГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР(71) Днепропетровский государственный университет им, 300-летия воссоединения Украины с Россией(56) Авторское свидетельство СССР М 610105, кл, 6 06 Г 7/00, 1975.Авторское свидетельство СССР й. 851398, кл. 6 06 Е 7/00, 1979.(54) ОДНОРОДНАЯ ЦЫЧИСЛИТЕЛЬНАЯ СТРУКТУРА ДЛЯ ОБРАБОТКИ ТРЕХМЕРНЫХ БИНАРНЫХ МАТРИЦ(57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах поточной обработки информации. Целью изобретения Изобретение относится к области автоматики и цифровой вычислительной техники и может быть использовано в устройствах поточной обработки информации,Целью изобретения является расшире-,ние функциональных воэможностей за счетвыполнения за одну команду вариантов операции поиска элементов массива по заданному интервалу в трехмерной бинарнойматрице,На фиг.1 приведена структурная схемаоднородной вычислительной структуры дляобработки трехмерных бинарных матриц,на фиг.2 - функциональная схема ячейкиоднородной вычислительной структуры; нафиг,3 - схема размещения трехмерных биявляется расширение функциональных возможностей за счет выполнения за одну команду вариантов операции поиска элементов массива по заданному интервалу в трехмерной бинарной матрице. Однородная вычислительная структура содержит / х Ь 1 - ячеек (где ) - количество слоев;- строк; К - столбцов), каждая из которых содержит три триггера, шесть элементов И и три элемента ИЛИ, Однородная вычислительная структура позволяет выполнять за одну команду операцию поиска по интервалу в трехмерной бинарной матрице, которая представляет собой двоичные отсчеты двумерной функции, при этом границы интервала могут задаваться в виде произвольных поверхностей двумерной функции, 1 табл, 3 ил,Ю нарных матриц в ячеиках однчислительной структуры,Однородная вычислительная структура для обработки трехмерных бинарных матриц (фиг.1) содержит ) фс 3 зс 3 с ячеек 1 (где ) - количество слоев, 1 - количество строк, 1 - количество столбцов), три группы тактовых входов 2-4, группу входов признака верхней границы 5, группу входов значения числа 6, группу входов признака нижней границы 7, две группы настроечных входов 8-9, группу входов признака значения интервала 10, три группы тактовых выходов 11 - 13, группу выходов значения интервала 14, две группы управляющих выходов 15 и 16, группу выходов признака нижней границы 17, группу выходов значения числа 18, группу выходов признака верхней границы19.Ячейка однородной вычислительнойструктуры (фиг.2) содержит три триггера 2 О -22, шесть элементов И 23 - 28, и три эпемента ИЛИ 29 - 31,Ячейка однородной структуры реализует следующие функции:(9) = Ч г 1 АО "чааагде о, а 1, д - состояния триггеров20-22 соответственно.Функции "4" - "б" позволяют осущестВить запись информации в триГГеры 2 О - 22ячейки 1. Функции "7" - "9" используютсядля выполнения операции поиска всех элементов, расположеннцх в заданном интер Овале значений, С помощью функций "1" - 3"осуществляют тактирование ввода трехмерных бинарнцх матриц в однородную вычислительную структуру,Выполнение операции поиска по интервалу в трехмерной бинарной матрице с по-,мОщью ОднороднОй вычислительнойструктуры Осуществляют следующим образом,Перед началом вычислений трехмерныедвоичные массивы, соответствующие верхней и нижней границе и массив, подлежащий обработке, ориентируют и вводят вОднородную структуру таким Образом, чтОразряды отсчетов двумерной функции рас- "5полагаются вдоль строк, младшими разрядами в направлении увеличения индекса К.Направления координатнцх осей Х,У,Е соответствуют направлениям в сторону увеличения индексов Ц,К (фиг,З).4 ООтсчеты О, О и А массивов верхней инижней границы и массива, подлежащегообработке, поразрядно подаются на соответствующие входы признака верхней гра 45ницы 5 группц, признака нижней границы 7группы и значения члена 6 группц ячееклевой грани однородной структуры, начиная с младших разрядов. Тактовые сигналы,.поступающие на тактовые входы 2-4 (Со,Со, Са), осуществляют запись разрядов от- Осчетов в триггеры 20 - 22 ячеек. Посколькувыходы признака нижней границы 17, значения числа 18 и признака верхней границы19 ячейки 5-го столбца в п-й строке гп-гослоя (3=1, к, п=1, 1; а=Ц) соединены свходами признака нижней границы 7, зна.чения числа 6 и признака верхней границы5 ячейки (3+1)-го столбца и-й строки щ-го слов, то по истечении К-тактов разряды отсчетов продвинутся по строкам на К-ячеек и заполнят Всю однородную структуру. Тактирование ввода каждого из трех массивов Осуществляется независимо друг от друга, по трем различным шинам Сц, Со, Са. На настроечные входы первой 8 и второй 9 групп (г 1 и 2.2) и входы признака значения интервала 10 группы ячеек левой грани однородной струкгуры подаются константы 21 = 1, 72 = 1, Ч = О соответственно.После ввода информации в каждой строке однородной структуры с помощью сигнала Ь производится поразрядное сравнение(начиная со старших разрядов) хранимого В триггерах 21 ячеек данной строки числа А = а 1, а 2,. с верхним Граничным признаком О=О 11 О 2 хранимом В триГ- герах 2 О ячеек этой же строки. Одновременно с помощью сигнала 72 производится сравнение А) с нижним граничным признаком О = Ф, б 2, хранимом в триггерах 22 ячеек этой строки. По завершении переходнцх процессов при сравнении Ас Осигнал Чна выходе значения интервала 14 группы правой грани однородной структуры в соответствии с выражениями (7) и (9) принимает значение Ч = 1 только в том случае, когда АО, т.е. находится вне заданного интервала. Аналогично при сравнении А с О в соответствии с выражениями (8) и (9) сигнал Ч на выходе значения интервала 14 группы правой грани однородной структуры принимает значение Ч = 1 только в том случае, когда А,О,г,е. находится вне заданного ийтервала, Следовательно, только ситуация Ч =О свидетельствует о том, что число, записанное в данной строке, удовлетворяет критерию поиска (О А О). Характер неравенства на границах заданного интервала может врыть при этом определен по сигналам Е, и Е ячеек на правой грани в соответствии с таблицей значений интерва- ЛОВ.Под О, А и О подразумеваются поверхности двумерных функций, представленные совокупностью отсчетов О, А и О.Из таблицы значений интервалов видно, что комбинируя сигналы Ч, Л и Е можно с помощью предлагаемой однородной структуры за одну команду выполнить различные варианты поиска в заданном интервале. Например, комбинация Ч У, = 1 соответствует поиску О А О, а комбинация Ч.7= 1 поиску ОАО.Если в качестве нижних граничных признаков О испольэовать числа меньшие, чем минимальные возможные значения отсчетов А, то за одну команду можно выделить все АО, Если в качестве верхних гранич 17023595 10 15 20 25 30 35 40 45 50 55 ных признаков использовать числа большие, чем.максимальные возможные значения отсчетов Ац, то можно выделить все А 101, Если задать О = 0 = В, то выполнится поиск по совпадению А=В,Однородная вычислительная структура для обработки трехмерных бинарных матриц позволяет выполнять за одну команду различные варианты операции поиска по интервалу элементов в трехмерных бинарных матрицах; в каждой строке задавать отличные от других строк значения границ интервала поиска, что позволяет осуществлять обработку трехмерных массивов, представляющих собой изображения двумерных функций от координат плоскости, при этом на обрабатываемом изображении выделяются области, в которых отсчеты двумерной функции находятся между ограничивающими поверхностями О и О; за счет независимого тактирования триггеров 20 - 22 в ячейках однородной структуры видоизменять границы интервала и обрабатываемый массив путем сдвига разрядов отсчетов параллельно по строкам однородной структуры,Дополнительным эффектом изобретения является повышение производительности однородной вычислительной структуры при выполнении операции поиска.Формула изобретения Однородная вычислительная структура для обработки трехмерных бинарных матриц, содержащая Ис) ячеек (где 1 = 1 - количество строк; Е - количество столбцов; ) - количество слоев), причем п-й настроечный вход первой группы (где п=1, соединен с первым настроечным входом ячейки первого столбца в-го слоя, второй настроечный вход которой соединен с в-м настроечным входом второй группы, щ-й вход признака значения интервала группы соединен с входом признака значения интервала ячейки первого столбца щ-го слоя, первый управляющий выход ячейки Я-го столбца (где 5=1,К) щ-го слоя соединен с первым настроечным входом ячейки (3+1)- го столбца в-го слоя, второй настроечный вход которой соеднинен с вторым управляющим выходом ячейки 5-го столбца т-го слоя, выход значения интервала которой соединен с входом призннака значения интервала ячейки (5+1)-го столбца п-го слоя, выход значения интервала ячейки К-го столбца ю-го слоя соединен с выходом значения интервала группы, е-й управляющий выход первой группы соединен с первым управляющим выходом ячейки 1-го столбца (п-го слоя, второй управляющий выход которой является управляющим выходом второй группы, причем каждая ячейка содержит первый триггер, шесть элементов И и три элемента ИЛИ, первый вход первого из которых соединен с выходом первого элемента И и первым входом второго элемента И, второй вход которого соединен с первым входом третьего элемента И, второй вход которого и первый вход первого элемента И соединен с первым настроечным входом ячейки, второй настроечный вход которой соединен с первыми входами четвертого и пятого элементов И, выходы которых соединены соответственно с первым и вторым входами второго элемента ИЛИ, второй вход пятого элемента И соединен с первым входом шестого элемента И, второй вход которого соединен с первым входом второго элемента ИЛИ, выход третьего элемента И соединен с вторым входом первого элемента ИЛИ, выход которого является первым управляющим выходом ячейки, второй управляющий выход которой соединен с выходом второго элемента ИЛИ, выход значения интервала ячейки соединен с выходом третьего элемента ИЛИ, первый вход которого соединен с входом признака значения интервала, выход второго элемента И соединен с вторым входом третьего элемента ИЛИ, третий вход которого соединен с выходом шестого элемента И, о т л и ч а ю щ ая с я тем, что, с целью расширения функциональных возможностей за счет выполнения за одну команду вариантов операции поиска элементов массива по заданному интервалу в трехмерной бинарной матрице,она содержит ч 1) ячеек (где ч = 2,), причем тактовый вход первой группы соединен с первым тактовым входом ячейки б-го столбца (где б=13) и-й строки (где п=1,1 с-го слоя, второй тактовый вход которой соединен с тактовым входом второй группы, тактовый вход третьей группы соединен с третьим тактовым входом ячейки б-го столбца и-й строки т-гослоя, первый, второй и третий тактовые выходы ячейки б-го столбца и-й строки а-го слоя (где в=1, )-1) соединены соответственно с первым, вторым и третьим тактовыми входами ячейки б-го столбца и-й строки (а+1)-го слоя, 1-й выход (где 1=1,2,3) ячейки б-го столбца и-й строки)-го слоя соединен с тактовым выходом 1-й группы, вход признака верхней границы группы соединен с входом признака верхней границы ячейки 1-го столбца п-й строки в-го слоя, вход признака нижней границы которой соединен с входом признака нижней границы группы, вход значения числа группы соединен с входом значения числа ячейки с-го столбца и-й строки гл-го слоя, выход значения числа ячейки 5-го столбца17 О 2359 О О 1 п-й строки в-го слоя соединен с входом значения числа ячейки (+1-го столбца и-й строки в-го слоя, выход признака нижней границы и выход признака верхней границы ячейки Я-го столбца и-й строки в-го слоя соединены соответственно с входом признака нижней границц и входом признака верхней границы ячейки (3+1-го столбца ий строки в-й слоя, выход признака нижней границы и выход признака верхней границы ,ячейки к-го столбца и-й строки в-го слоя ,соединены соответственно с выходом признака нижней границы группы и выходом признака верхней границы группы, вцход значения чистка ячейки к-го столбца и-й строки в-го слоя соединен с выходом значения числа группы, настроечный вход первой группы и настроечнцй вход второй группы соединены соответственно с первым настроечным входом и вторым настроечным входом ячейки -го столбца Ч-й строки в-гослоя, вход прйзнака значения интервала коорой соединен с водо признака Значения интервала группы, первый управляющий вцход, второй управлящий выход и ВыхОд значения интервала ячейки Б-го столбца, Ч-й строки в-го слоя соедине-. ны сООтветственнО с первым настроечным входом, вторым настроечным входом и входом признака значения интервала ячейки 3+1)-го столбца, Ч-й строки в-го слоя, первый управляющий выход, второй управляющий вцход и выход признака значения интервала к-го столбца Ч-й строки в-го слоя 6 соединень соответственно с управляющимвыходом первой группы. суправляющим выходом второй группы и Выходом признака значения интервала группы, причем ячейка содержит второй и третий триггеры, такто О вые входы которых и тактовый вход первоготриггера соединены соответственно с вторым, третьим и первцм тактовыми входами ячейки, прямой выход первого триггера соединен с выходом признака верхней грани цц ячейки, Выход значения числа которойсоединен с вторым входом первого элемента И и прямым выходом второго триггера, инверсный выход которого соединен с вторым входом четвертого элемента И, второй вход 2 О второго элемента И соединен с инверснымвыходом первого т риггера, информационный вход которого и информационные входы второго и третьего триггеров соединены соответственно с входом признака верхней границы, 25 входом значения числа и входом признаканижней границы ячейки, выход третьего триггера соединен с вторым входом пятого элемента И и выходом признака нижней границь 1 ячейки, 1-й тактовый выход которой соединен ЭО с тактовым Входом 1-го триггера.1702359 Составитель В.СорокиРедактор А.Долинич Техред М.Моргентал ор 8, Гирняк К Производственно-издательский комбинат "Патент", г, Уж л. Гагарина аказ 4543 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 45