Комірка однорідної структури

Изобретение относится к вычислительной технике и может быть использовано дли построения однородных структур, например, матричных и систолических процессоров. Известна ячейка однородной среды [Авт. св. СССР №1397899, кл. G 06 F 7/00, 1986], содержащая два регистра команд, три дешифратора, три арифметико-логических элемента, четыре элемента задержки, пять мультиплексоров, причем информационные входы первого, второго и третьего мультиплексоров соединены с информационными входами ячейки, настроечные входы первой группы которой соединены с настроечными входами первого регистра команд, настроечный выход которого соединен с первым настроечным выходом ячейки, информационные выходы которой соединены с выходами первого, второго, третьего и четвертого демультиплексоров, первый выход первого регистра команд соединен с входом первого дешифратора, выход которого соединен с настроечным входом первого арифметико-логического элемента, информационные входы которого соединены с выходами первого и второго мультиплексоров, управляющие входы которых соединены с вторым выходом первого регистра команд, третий выход которого соединен с управляющим входом первого элемента задержки, информационный вход которого соединен с выходом первого арифметико-логического элемента, выход первого элемента задержки соединен с информационным входом демультиплексора, управляющий вход которого соединен с четвертым выходом первого регистра команд, пятый выход которого соединен с управляющими входами второго, третьего и четвертого демультиплексоров, информационный вход второго демультиплексора соединен с выходом второго элемента задержки, вход которого соединен с выходом третьего мультиплексора, управляющий вход которого соединен с шестым выходом первого регистра команд, выход второго элемента задержки соединен с входом третьего элемента задержки, выход которого соединен с информационным входом третьего демультиплексора, кроме того, информационные входы ячейки соединены с информационными входами четвертого и пятого мультиплексоров, выходы которых соединены с информационными входами второго арифметико-логического элемента, настроечные входы которого соединены с выходом второго дешифратора, вход которого соединен с первым выходом второго регистра команд, второй выход которого соединен с управляющим входом четвертого элемента задержки, информационный вход которого соединен с выходом второго арифметикологического элемента и первым информационным входом третьего арифметико-логического элемента, выход которого соединен с информационным входом четвертого демультиплексора, а второй информационный и настроечный входы третьего арифметико-логического элемента соединены соответственно с выходом первого арифметико-логического элемента и выходом третьего дешифратора, входы которого соединены с седьмым выходом первого регистра команд и третьим выходом второго регистра команд, четвертый выход которого соединен с управляющими входами четвертого и пятого мультиплексоров, пятый, шестой и седьмой выходы второго регистра команд соединены соответственно с управляющими входами второго демультиплексора, третьего мультиплексора и пятого демультиплексора, информационный вход которого соединен с выходом четвертого элемента задержки, выходы пятого демультиплексора соединены с информационными выходами ячейки, настроечные входы второй группы которой соединены с настроечными входами второго регистра команд, настроечный выход которого соединен с вторым настроечным выходом ячейки. Функциональные возможности известной ячейки однородной среды позволяют выполнять операции над четырьмя переменными, функции условных переходов и функции самодиагностирования, что вместе с тем, не дает возможности использовать ее для создания матричных структур с перспективной областью применения, в частности, для корреляционной обработки двумерных изображений. Известна ячейка однородной структуры [Авт. св. СССР №1363180, кл. G 06 F 7/00, 1985], содержащая мультиплексор, три демультиплексора, арифметико-логический блок и блок настройки, содержащий счетчик, D-триггер, элемент И, два элемента НЕ, RS-триггер и четыре элемента И-НЕ, причем информационные входы первой группы ячеек соединены с информационными входами мультиплексора, выход которого соединен с первым входом арифметико-логического блока, первый выход которого соединен с информационным входом первого демультиплексора, управляющие входы которого соединены с одноименными входами мультиплексора, первым и вторым выходами счетчика, выходы которого являются первым и вторым выходами блока настройки, третий выход которого соединен с выходом триггера, выходы первого демультипексора соединены с информационными выходами первой группы ячейки, первый вход блока настройки соединен с первыми входами элемента И, первого элемента И-НЕ и входом первого элемента НЕ, выход которого соединен с информационным входом D-триггера, инверсный выход которого соединен с вторым входом элемента И, выход которого соединен со счетным входом счетчика, вход сброса которого соединен с одноименными входами D-триггера и RS-триггера и входом начальной установки блока настройки, второй вход которого соединен с входом второго элемента НЕ и вторым входом первого элемента И-НЕ, выход которого соединен с единичным входом RS-триггера, прямой выход которого соединен с первыми входами второго, третьего и четвертого элементов И-НЕ, вторые входы которых соединены соответственно с первым и вторым входами счетчика и прямым выходом D-триггера, установочные входы которых соединены соответственно с выходами второго, третьего и четвертого элементов И-НЕ, первый и второй выходы блока настройки соединены с управляющими входами второго и третьего демультиплексоров, входы синхронизации которых соединены с одноименными входами мультиплексора и первого демультиплексора и с третьим выходом блока настройки, первый и второй входы которого соединены с настроечными входами первой и, второй групп ячейки и информационными входами второго и третьего демультиплексоров, выходы которых соединены с настроечными выходами первой и второй групп ячейки, информационные входы второй группы которой соединены с вторым входом арифметико-логического элемента, второй выход которого соединен с информационными выходами второй группы ячейки. Известная ячейка однородной структуры при определенном виде настройки способна выполнять обратимую и необратимую коммутацию связей в однородной структуре, что является недостаточным функциональным базисом при создании, например, матричных структур, выполняющих корреляционную обработку двумерной информации. Наиболее близкой к предлагаемой по технической сущности является ячейка однородной структуры [Авт. св. СССР № 1778757, кл. G 06 F 7/00, 1992], содержащая мультиплексор и блок настройки, содержащий два триггера, счетчик, два элемента НЕ, с первого по четвертый элементы И, причем первый вход первого элемента И соединен с первым информационным входом ячейки, второй информационный вход которой соединен с входом первого элемента НЕ блока настройки, инверсный выход первого триггера которого соединен со вторым входом первого элемента И блока настройки, информационные входы группы ячейки соединены с информационными входами мультиплексора, выход второго элемента И блока настройки соединен с входом установки в единицу первого триггера блока настройки, выход которого является выходом ячейки, настроечные входы которой соединены с управляющими входами мультиплексора, выход которого соединен с информационным входом первого триггера блока настройки, тактовый вход которого соединен с тактовым входом счетчика блока настройки и тактовым входом ячейки, вход сброса которой соединен с входом установки в нуль первого триггера блока настройки, выходы третьего и четвертого элементов И которого соединены соответственно с вычитающим и суммирующим входами счетчика блока настройки, выход признака "меньше нуля" счетчика соединен с входом установки в нуль второго триггера блока настройки, вход начальной установки ячейки соединен с входом обнуления счетчика и входом установки в единицу второго триггера блока настройки, выход первого элемента И которого соединен с входом второго элемента НЕ и первым входом третьего элемента И блока настройки, второй вход третьего элемента И которого соединен с выходом первого элемента НЕ блока настройки, первый и второй входы четвертого элемента И которого соединены соответственно с входом первого элемента НЕ и выходом второго элемента НЕ блока настройки, первый и второй входы второго элемента И которого соединены соответственно с выходом второго триггера блока настройки и входом разрешения записи ячейки. Однородная структура, выполненная на известных ячейках, обладает функциональными возможностями, позволяющими использовать ее для корреляционной обработки двумерных изображений, в процессе которой определяется область множества ячеек однородной структуры, в которых взаимно-корреляционная функция (ВКФ) текущего изображения F и эталонного изображения G не превышает заданный порог D. Вместе с тем, в известной однородной структуре невозможно считывание результатов корреляционной обработки по битовым срезам. Задача изобретения заключается в вычислении взаимно-корреляционной функции (ВКФ) текущего изображения F и эталонного изображения G с учетом заданного порога D и считывании результатов корреляционной обработки по битовым срезам. Сущность изобретения заключается в том, что в ячейке однородной структуры, содержащей мультиплексор и блок настройки, содержащий триггер, счетчик, два элемента НЕ и с первого по четвертый элементы И, причем первый вход первого элемента И соединен с первым информационным входом ячейки, второй информационный вход которой соединен с входом первого элемента НЕ блока настройки, инверсный выход триггера которого соединен с вторым входом первого элемента И блока настройки, информационные входы группы ячейки соединены с информационными входами мультиплексора, выход второго элемента И блока настройки соединен с входом установки в единицу триггера блока настройки, выход которого является выходом ячейки, настроечные входы которого соединены с управляющими входами мультиплексора, выход которого соединен с информационным входом триггера блока настройки, тактовый вход которого соединен с тактовым входом счетчика блока настройки и тактовым входом ячейки, вход сброса которой соединен с входом установки в нуль триггера блока настройки, выходы третьего и четвертого элементов И которого соединены соответственно с вычитающим и суммирующим входами счетчика блока настройки, вход начальной установки ячейки соединен с входом обнуления счетчика блока настройки, выход первого элемента И которого соединен с входом второго элемента НЕ и первым входом третьего элемента И блока настройки, второй вход третьего элемента И которого соединен с выходом первого элементе НЕ блока настройки, первый и второй входы четвертого элемента И которого соединены соответственно с входом первого элемента НЕ и выходом второго элемента НЕ блока настройки, первый вход второго элемента И которого соединен соответственно с входом разрешения записи ячейки, введен в блок настройки компаратор, входы первой группы которого соединены с информационными выходами счетчика блока настройки, входы второй группы подключены к входам выборки битового среза ячейки, а выход соединен с вторым входом второго элемента И блока настройки, третий вход которого подключен к инверсному выходу признака "меньше нуля" счетчика блока настройки. Анализ научно-технической и патентной литературы показал, что известны устройства, обладающие конструктивными признаками в отдельности. Однако, устройств, обладающих совокупностью признаков, авторами не обнаружено. Функции известных ячеек однородных структур являются либо недостаточными для выполнения основных операционных функций однородных матричных структур, в частности, для корреляционной обработки двумерных изображений, либо ограничиваются определением области множества ячеек однородной структуры, в которых взаимно-корреляционная функция двух изображений не превышает заданный порог D. Введение в блок настройки ячейки однородной структуры компаратора с соответствующими связями позволяет расширить функциональные возможности однородных структур за счет считывания результата корреляционной обработки по битовым срезам. Т.о., заявляемое устройство соответствует критерию "изобретательский уровень". На фиг. 1 представлена функциональная схема ячейки однородной структуры; на фиг. 2 - фрагмент вычислительной структуры на основе предлагаемой ячейки; на фиг. 3 - пример выполнения корреляционной обработки информации. Ячейка однородной структуры (фиг. 1) содержит мультиплексор 1 и блок 2 настройки, который содержит счетчик 3, триггер 4, компаратор 5, элементы И 6,7,8,9 и элементы НЕ 10, 11, а также информационные входы 12.1-12.4 группы, информационные выходы 13.1-13.4 группы, причем информационные входы 12.1-12.4 группы соединены с входами мультиплексора 1, а информационные выходы 13.1-13.4 группы подключены к прямому выходу триггера 4 блока 2 настройки. Информационный вход 14 и вход разрешения записи 15 ячейки соединены соответственно с первыми входами элементов И 6 и 7, информационный вход 16 ячейки соединен с первым входом элемента И 9 и через элемент НЕ 11 с первым входом элемента И 8, а выход элемента И 6 подключен к второму входу элемента И 8 и через элемент НЕ 10 к второму входу элемента И 9 блока 2 настройки. Выходы элементов И 8 и 9 соединены соответственно с вычитающим и суммирующим входами счетчика 3 блока 2 настройки, тактовый вход которого подключен к тактовому входу триггера 4 и тактовому входу 17 ячейки, вход установки в нуль триггера 4 соединен с входом сброса 18 ячейки, инверсный выход признака "меньше нуля" - счетчика 3 блока 2 настройки соединен с третьим входом элемента И 7 блока 2 настройки, а вход обнуления счетчика 3 подключен к входу начальной установки 19 ячейки. Выход компаратора 5 блока 2 настройки соединен с вторым входом элемента И 7, выход которого подключен к входу установки в единицу триггера 4 блока 2 настройки, информационный вход которого подключен к выходу мультиплексора 1, управляющие входы которого соединены с настроечными входами 20.1, 20.2 ячейки. Входы первой группы компаратора 5 блока 2 настройки соединены с соответствующими выходами счетчика 3 блока 2 настройки, а входы второй группы - с входами 21.1-21.k выборки битового среза ячейки (k = Іоg2 D). Однородная структура (фиг. 2) содержит матрицу ячеек 22.i.j, где і - номер строки, j - номер столбца матрицы. Информационный вход 16 каждой ячейки 22 подключен к информационной шине 23 матрицы соответственно, управляющие входы 15, 17, 18, 19 - к управляющим шинам 24, 25, 26, 27 матрицы соответственно, настроечные входы 20.1, 20.2 - к шинам 28 настройки матрицы, а информационный вход 14 к шине 29. Информационные выходы 13.1-13.4 каждой ячейки 22 соединены с информационными входами 12.1-12.4 ячеек 22, являющихся соседними справа, сверху, слева, снизу, а настроечные входы 21.1-21.k - с шинами 30. Ячейка однородной структуры работает следующим образом. Перед началом решения задачи производится установка в нулевое состояние триггера 4 по сигналу на входе 18 сброса ячейки, а затем запись в триггер 4 информации, поступающей по информационному входу 12.1 в мультиплексор 1 при наличии на управляющих входах 20.1-20.2 мультиплексора 1 соответствующих настроечных сигналов. Через вход 2.1 ячейки последовательно разряд за разрядом заносится входная информация и продвигается к выходу 13.1 ячейки. Благодаря этому процессу обеспечивается последовательная запись информации по строкам в однородной вычислительной структуре (фиг. 2). После завершения цикла записи информации работа ячейки может протекать в двух режимах: транзитном и операционно-транзитном. Транзитный режим. В этом режиме осуществляется транзит входных данных через мультиплексор 1 по одному из четырех входов 12.1-12.4 ячейки, определяемому настроечной информацией на входах 20.1-20.2 ячейки. Таким образом, в однородной вычислительной структуре (фиг. 2) возможен сдвиг информации вправо, влево, вверх, вниз. Операционно-транзитный режим. В этом режиме происходит обработка данных, поступающих с определенных информационных входов 12.1-12.4,14,16 ячейки, и выдача результата на информационном выходе 13.1 ячейки. Исходные данные подвергаются корреляционной обработке, в процессе которой определяется область множества ячеек 22 однородной вычислительной структуры (фиг. 2), в которых взаимно-корреляционная функция (ВКФ) текущего изображения F и эталонного изображения G не превышает заданный порог D. После записи во все ячейки 22 однородной вычислительной структуры (фиг. 2) соответствующих значений текущего изображения F = {f oo.....f (N-1)(M-1)}, где N, M - количество строк и столбцов однородной вычислительной структуры, процесс корреляционной обработки начинается с поступления на вход 19 начальной установки ячейки управляющего сигнала, который сбрасывает в нулевое состояние счетчик 3 блока 2 настройки. Затем синхронно с тактовыми импульсами по входам 14 каждой ячейки поступает Последовательность G ={goo.....gn-1)(m-1)}, где n х m – размерность поля эталонного изображения G, а на вход 16 каждой ячейки поступает серия импульсов D ={d o,... d I d (L-1)}, сумма единичных значений которых задает степень отличия текущего изображения F от эталонного изображения G, dI = 0,1. С помощью логического f элемента И 6 блока 2 настройки выполняется перемножение величины ij с текущим значением gI последовательности G, где I - номер тактового импульса, I = 0,..., L-1, i= 0,.... N-1, j= 0.....М-1. Поскольку выходы элементов И 8 и И 9 соединены соответственно с вычитающим и суммирующим входами счетчика 3, то выполняются следующие действия в ячейках с приходом переднего фронта I-го тактового импульса при определенном соотношении величин fij , gI, d I: так при выполнении условия увеличение на единицу содержимого счетчика 3; при соотношении, когда fij fij fij fij ×gI = 0, d I =1 происходит ×gI=1, d I=0, - уменьшение на единицу содержимого счетчика3; а в случае, когда ×gI = 0, d I = 0, а также ×gI = 1, d I=1 содержимое счетчика 3 не изменяется. В момент, когда содержимое счетчика 3 становится меньше нуля, на его инверсном выходе признака "меньше нуля", появится нулевой сигнал. Через L тактов, где L = n x m, в счетчиках 3 будут зафиксированы величины ВКФ двумерных изображений F и G в пределах заданного порога А. С приходом управляющего сигнала на вход 15 разрешения записи ячейки произойдет запись во всех ячейках информации из счетчика 3 в триггер 4 блока 2 настройки. Пример конкретного выполнения корреляционной обработки информации в предлагаемой однородной структуре представлен для случая, когда N = М = 4 (фиг. 3а) и n= m = 3 (фиг. 36). В процессе корреляционной обработки содержимое всех ячеек 22 однородной вычислительной структуры будет сдвигаться влево, вверх и вправо по заднему фронту соответствующих тактовых импульсов согласно приведенному на фиг. 3б примеру сканирования эталонного изображения G (показано стрелками). В соответствии с принятыми сканированием эталонного изображения G, но в противоположном направлении сдвигается текущее изображение F. На фиг. 3в приведена реальная картина корреляционной обработки в однородной вычислительной структуре размерностью (N + n - 1)х( М+ m - 1) = 6 х 6 для примера (фиг. 3а, б) по тактам с указанием "окна" размерностью N х М (фиг. 3), информация в котором совпадает с данными на фиг. 3в. При указанном сканировании эталонного изображения G на информационный вход 14 каждой ячейки однородной вычислительной структуры поступает последовательность сигналов F {100110010}, а на информационный вход 16 - последовательность сигналов D = {111000000}, т.е. в результате должна быть L -1 D = S dI I= 0 в определена область множества ячеек однородной структуры размерностью N х М, где параметр данном случае равный трем, при неотрицательном значении содержимого счетчика 3 определяет местонахождение левого верхнего углового отсчета фрагментов изображения в поле текущего изображения F, совпадающих с точностью до D отсчетов с эталонным изображением G. Таким образом, при D = 3 определяется область множества точек текущего, изображения F, соответствующих левому верхнему угловому отсчету тех фрагментов текущего изображения F, отличие которых от эталонного изображения G не превышает трех отсчетов. С приходом нулевого тактового импульса (фиг. 3) по его переднему фронту в счетчике 3 тех ячеек однородной структуры, где fij ×gI = 0, выполняется увеличение на единицу его содержимого, а в остальных f ячейках, где ij ×gI =1, состояние счетчика 3 остается без изменений, поскольку в течение этого такта d o = 1. По заднему фронту нулевого тактового импульса происходит сдвиг влево содержимого всех ячеек однородной структуры. С целью сохранения информации о текущем изображении F при его сдвиге размерность однородной структуры должна быть не меньше (N + n - 1)х(М + m - 1). На 1-м и 2-м тактах происходит аналогичное изменение содержимого счетчиков 3 всех ячеек однородной структуры (фиг. 3г), поскольку d 1=d 2 = 1 и g 1=gо1 = 0; g2=go2 = 0. На 5-м, 6-м, 8-м тактах не происходит изменения содержимого счетчиков 3 всех ячеек однородной структуры, поскольку gI = 0 для I = 5, 6, 8, следовательно, fij ×gI= 0 и d I= 0. f На всех тактах, когда gI = 1, I = 3, 4, 7, с учетом того, что d I = 0, при выполнении условия ij ×gI = 0 не происходит изменения состояния счетчиков 3 в соответствующих ячейках однородной структуры, а при f условии, что ij ×gI= 1 выполняется уменьшение на единицу содержимого соответствующих счетчиков 3. На фиг. 3в показаны поля текущего изображения F с соответствующим сдвигом информации, а на фиг. 3г содержимое счетчиков 3 соответствующих ячеек однородной структуры размерностью N х М. После завершения формирования ВКФ двумерных изображений F и G выполняется процесс выборки битовых срезов ВКФ, определяющих местонахождение начальных отсчетов тех фрагментов текущего изображения F, у которых "искажения" по сравнению с эталонным изображением G равны величине р, где р =0,,.., D. Для этого выполняется установка в нулевое состояние триггера 4 всех ячеек по сигналу на входе 18 сброса ячейки. В приведенном примере (фиг. 3г) уже на 7-м такте формируется окончательный результат корреляционной обработки текущего изображения F, который свидетельствует о том, что все ячейки однородной структуры, кроме ячеек с координатами (1,3), (3,1), (3,3), составляют область левых верхних угловых отсчетов (согласно выбранному способу сканирования эталонного изображения G) фрагментов текущего изображения F с "искажениями" по сравнению с эталонным изображением G, которые не превышают трех отсчетов. Причем координаты тех ячеек структуры, у которых содержимое счетчика 3 равно величине D, определяют местонахождение левого верхнего углового отсчета фрагментов, "искажения" которых по сравнению с эталонным изображением G равны нулю. Аналогично, если содержимое счетчиков 3 определенных ячеек однородной структуры равно величине (D-р), то координаты этих ячеек позволяют определить местонахождение левого верхнего углового отсчета фрагментов текущего изображения F, "искажения" которых по сравнению с эталонным изображением G равны величине р. Таким образом, при поступлении на входы 21.1-21.к выборки битовых срезов величины (D-р) в двоичном коде и при наличии единичного сигнала на входе 15 разрешения записи всех ячеек однородной структуры произойдет выборка тех ячеек однородной структуры, у которых содержимое счетчиков 3 равно величины (D-р). В результате триггер 4 соответствующих ячеек установится в единичное состояние, поскольку единичный сигнал на выходе элемента И 7 появится при наличии единичного сигнала как на выходе компаратора 5, на входы которого поступает в двоичном коде информация с выходов счетчика 3 и с входов 21.1 -21.k выборки битового среза ячейки, так и на инверсном выходе признака "меньше нуля" счетчика 3. В случае же отрицательного значения содержимого счетчика 3 нулевой сигнал с инверсного выхода признака "меньше нуля" этого счетчика 3 не приведет к изменению начального нулевого состояния триггера 4 соответствующей ячейки однородной структуры. В приведенном примере при поступлении на входы 21.1-21.k выборки битового среза ячейки величины (Dр) = 3 при D =3 в единичное состояние установятся триггеры 4 тех ячеек, содержимое счетчиков 3 которых равно 3 (фиг. 3г), т.е. ячейка с координатами (1.1). Таким образом, определены координаты левого верхнего углового отсчета фрагмента текущего изображения F, полностью совпадающего с эталонным изображением G (р =0). Аналогично при поступлении на входы 21.1-21.k выборки битового среза ячейки величин (D-р) = 2,1.0 в единичное состояние установятся триггеры 4 тех ячеек, содержимое счетчиков 3 которых равно соответственно 2,1,0. В результате определяются координаты левого верхнего ) углового отсчета фрагментов текущего изображения F, "искаженных" по сравнению с эталонным изображением G; на один отсчет (р = 1) (0,0); на два отсчета ((р = 2) - (1,0) и (2.1); на три отсчета (р = 3) -(0.1). (0,2), (0,3), (1,2),(2.0),(2,2),(2,3),(3,0),(3,2)(фиг. 3г).Таким образом осуществляется выборка р-го битового среза ВКФ, т.е. битового среза ВКФ, несущего информацию о расположении начальных отсчетов фрагментов текущего изображения F с "искажением" равным р по сравнению с эталонным изображением G (р =1..... D). Начальные отсчеты обнаруженных фрагментов изображения F с "искажениями" в пределах А фиксируются наличием единичного сигнала на выходе триггера 4 в соответствующих ячейках однородной структуры. Координаты начальных отсчетов обнаруженных фрагментов изображения F можно считать в процессе работы всех ячеек в транзитном режиме, т.е. путем сдвига полученной информации в транзитном режиме.