Ячейка однородной структуры

Ячейка однородной структуры

Иллюстрации

Показать все

Реферат

 

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

СОГОЗ СQIÇI: И:КИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

IsI>s G 06 F 7/00

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР)

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

4М

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4814993/24 (22) 16.04,90 (46) 30.11,92. Бюл, N. 44 (71) Винницкий политехнический институт (72) В.Б. Гайда, Т.Б. Мартынюк, А,Т. Теренчук и Б.М. Ковальчук (56) 1, Авторское свидетельство СССР

N 1397899, кл G 06 F 7/00, 1986.

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

N 1363180, кл. G 06 F 7/00, 1985. (54) ЯЧЕЙКА ОДНОРОДНОЙ СТРУКТУРЫ (57) Изобретение относится к вычислительной технике и может быть использовано для построения однородных структур, наприИзобретение относится к ьычислительной технике и может быть использовано для построения однородных структур, например матричнь х и систолических процессоров.

Известна ячейка однородной среды (1), содержащая два регистра команд, три дешифратора, три арифметико-логических элемента, четыре элемента задержки, пять мультиплексоров и пять демультиплексоров, причем информационные входы первого, второго и третьего мультиплексоров соединены с информационными входами ячейки, настроечные входь: первой группы которой соедлнены с настроечными входами первого регистра команд, настроечный вход которого соединен с первым настроечным выходом ячейки, информационные выходы которои соединены с выходами первого, второго, третьего и четвертого демультиплексоров, первый выход первого ре.. Ж 1778757 А1 мер матричных и систолических процессоров, Цель изобретения — расширение функциональных возможностей. Ячейка однородной структуры содержит мультиплексор и блок настройки, состоящий из счетчика, первого и второго триггеров, элементов И и НЕ, группу информационных входов, группу информационных выходов, информационные входы, настроечные входы, управляющие входы. Однородная структура, выполненная на предлагаемых ячейках, обладает функциональными возможностями, позволяющими использовать ее для корреляционной обработки двумерных изображений. 3 ил. гистра команд соединен с входом первого дешифратора, выход которого соединен с настроечным входом первого арифметикологического элемента, информационные входы которого. соединены с выходами первого и второго мультиплексоров, управляющие входы которых соединены с вторым выходом первого регистра команд, третий выход которого соединен с управляющим входом первого элемента задержки, информационный вход которого соединен с выходом первого арифметико-логического элемента, выход первого элемента задержки соединен с информационным входом первого демультиплексора, управляющий вход которого соединен с четвертым выходом первого ре-истра команд, пятый выход которого соединен с управляющими входами второго, третьего и четвертого демультиплексоров, информационный вход второго демультиплексора соединен с выхо1778757

35

45

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

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

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

D-триггера, выходы первого демультиплексора соединены с информационными выходами первой группы ячейки, первый вход блока настройки соединен с первыми входами элемента И, первого элемента И вЂ” НЕ и входом первого элемента НЕ, выход которого соединен с информационным входом Dтриггера, инверсный выход которого соеДинен с вторым входом элемента И, выход которого соединен со счетным входом счетчика, вход сброса которого соединен с одноименными входами 0-триггера и RSтриггера и входом начальной установки блока настройки, второй вход которого соединен с входом второго элемента НЕ и вторым входом первого элемента И вЂ” НЕ, выход которого соединен с единичным входом

RS-триггера, прямой выход которого соединен с первыми входами второго, третьего и четвертого элементов И вЂ” НЕ, вторые входы которых соединены соответственно с первым и вторым входами счетчика и прямым выходом D-триггера, установочные входы которых соединены соответственно с выходами второго. третьего и четвертого элементов И вЂ” НЕ, первый и второй выходы блока настройки соединены с управляющими входами второго и третьего демультиплексоров, входы синхронизации которых соединены с одноименными входами мультиплексора и первого демультиплексора и с третьим выходом блока настройки, первый и второй входы которого соединены с настроечными входами первой и второй групп, ячейки и информационными входами второго и третьего демультиплексоров, выходы которых соединены с настроечными выходами первой и второй групп ячейки, информационные входы второй группы которой соединены с вторым входом арифметико1778757

45 триггера блока настройки, вход начальной 50

55 логического элемента„второй выход которого соединен с информационными выходами второй группы ячейки.

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

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

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

30 соответственно со входом первого элемента

КЕ и выходом второго элемента НЕ блока настройки, первый и второй входы второго элемента И которого соединены соответственно с выходом второго триггера блока нас1ройки и входом разрешения записи ячейки.

На фиг. 1 представлена функциональная схема ячейки однородной структуры; на фиг. 2 — фрагмент вычислительной структуры нэ основе предлагаемой ячейки; на фиг, 3 — пример выполнения корреляционной обработки информации, Ячейка однородной структуры (фиг. 1) содержит мультиплексор 1 и блок 2 настройки. который содержит счетчик 3, триггеры 4, 5, элементы И 6 — 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 настройки соединен с входом установки в нуль триггера 5 блока 2 настройки, вход установки в единицу которого подключен к входу обнуления счетчика 3 и входу начальной установки 19 ячейки. Выход триг- гера 5.блока 2 настройки соединен с вторым входом элемента И 7, выход которого подключен к входу установки B единицу триггера 4 блока 2 настройки, информационный вход которого подключен к выходу мультиплексора 1, управляющие входы которого соединены с настроечными входами 20.1, 20.2 ячейки, Однородная структура (фиг. 2) содержит матрицу ячеек 21.Ц, где! — номер строки, J— номер столбца матрицы, Информационные входы 14 и 16 каждой ячейки 21 подключены к информационным шинам 22 и 23 матрицы соответственно, управляющие входы 15, 17, 1778757

18, 19 — к управляющим шинам 24-27 матрицы соответственно, настроечные входы

20.1, 20.2 — к шинам 28 настройки матрицы, Информационные выходы 13.1-13.4 каждой ячейки 21 соединены с информационными входами 12.1-12.4 ячеек 21, являющихся соседними справа, сверху, слева, снизу, Ячейка однородной структуры работает следующим образом.

Перед началом решения задачи производится установка в нулевое состояние триггера 4 по сигналу на входе 18 сброса ячейки, а затем запись в триггер 4 информации, поступающей по информационному входу 12,1 в мультиплексор 1 при наличии на управляющих входах 20.1 — 20.2 мультиплексора 1 соответствующих настроечных сигналов. Через вход 12.1 ячейки последовательно разряд за разрядом заносится входная информация и продвигается к выходу 13.1 ячейки, Благодаря этому процессу обеспечивается последовательность запись информации по строкам в однородной вычислительной структуре (фиг. 2). После завершения цикла записи информации работа ячейки может протекать в двух режимах: транзитном и операционно-транзитном, Транзитный режим. В этом режиме осуществляется транзит входных данных через мультиплексор 1 по одному из четырех входов 12.1 — 12,4 ячейки, определяемому настроечной информацией на входах

20.1 — 20,4 ячейки, Таким образом, в однородной вычислительной структуре (фиг. 2) возможен сдвиг информации вправо, влево, вверх, вниз.

Операционно-транзитный режим. В этом режиме происходит обработка данных, поступающих с определенных информационных входов 12.1-12.4, 14, 16 ячейки и выдача результата на информационном выходе 13,1 ячейки. Исходные данные подвергаются корреляционной обработке, в процессе которой определяется областьмножествэ ячеек 21 однородной вычислительной структуры (фиг. 2), в которых взаимно-корреляционная функция (ВКФ) текущего изображения F и эталонного изображения G превышает заданный порог Л, После записи во все ячейки 21 однородной вычислительной структуры (фиг. 2) соответствующих значений текущего изображения, F--(foo,....fg-1,у->), где N, М вЂ” количество строк и столбцов однородной вычислительной структуры, процесс корреляционной обработки начинается с поступления на вход 19 начальной установки ячейки управляющего сигнала, который сбрасывает в нулевое состояние счетчик 3 и устанавливает в единичное состояние триггер 5 блока 2 настройки. Затем синхронно с тактовыми импульсами по входам 14 каждой ячейки поступает последовательность

G=(goo,"..gn-1, 1), где n,m — размерность

5 поля эталонного изображения G, а на вход

16 каждой ячейки поступает серия импульсов Л = (д, .... Bi, „., д ->), сумма единичных значений которых задает степень отличия текущего изображения F от эталон10 ного изображения G, д = (0,1}, С помощью логического элемента И 6 блрка 2 настройки выполняется перемножение величины 7 с текущим значением gl последовательности

6, где I — номер тактового импульса, I 0„„,1—

15 1, I=O,...,N 1,)=O....,M 1. Поскольку выходы элементов И 8 и 9 соединены соответственно с вычитающим и суммирующим входами счетчика 3, то выполняются следующие действия в ячейках с приходом переднего

20 фронта I-го тактового импульса при определенном соотношении величин fij, 9ь д . так, при выполнении условия f I gi=-О, äI =1 происходит увеличение на единицу содержимого счетчика 3; при соотношении. когда

f gl= 1. д = О, — уменьшение на единицу содержимого счетчика 3; а в случае, когда

fi> gi= О, д = О, а также fi) g)= 1, д = 1 содержимое счетчика 3 не изменяется, В момент, когда содержимое счетчика 3 становится меньше нуля, единичный сигнал на

его выходе признака "меньше нуля" приведет к обнулению триггера 5. Через L тактов, где L=nxm, в триггерах 5 будут зафиксированы позиции, в которых ВКФ двумерных изображений F u G будут превышать заданный порог Ь. С приходом управляющего сигнала на вход 15 разрешения записи ячейки произойдет запись во всех ячейках информации из триггера 5 в триггер 4 блока 2 настройки.

Пример выполнения корреляционнои обработки информации в предлагаемой однородной структуре представлен для случая, когда N=M=4 (фиг. За) и п=п1=3 (фиг, Зб), В процессе корреляционной обработки содержимое всех ячеек 21 однородной вычислительной структуры будет сдвигаться влево, вверх и вправо по заднему фронту соответствующих тактовых импульсов согласно приведенному на фиг. Зб примеру сканирования эталонного изображения G (показано стрелками). В соответствии с принятым сканированием эталонного изображения G, но в противоположном направлении сдвигается текущее иэображение F, На фиг. Зв приведена реальная картина корреляционной обработки в однородной вычислительной структуре размерностью (М+и-1)x(M+m-1)=6х6 для примера (фиг. За, б) по тактам с указанием "окна" размерно1778757

10 стью N x N (фиг. 3r), информация в котором совпадает с данными на фиг. Зв.

При указанном сканировании эталонного иэображения G на информационный вход

14 каждой ячейки однородной вычислитель- 5 ной структуры поступает последовательность сигналов G=(100110010}, а на информационный вход 16 — последовательность сигналов Л = (100000000), т.е, в результате должна быть определена область 10 множества ячеек однородной структуры размерностью NxM, где параметр (=1

Л = д, в данном случае равный едини15 це, при неотрицательном значении содержимого счетчика 3 и соответствующем единичном значении триггера 5 определяет местонахождение левого верхнего углового отсчета фрагментов изображения в поле текущего иэображения F, совпадающих с точностью до Л отсчетов с эталонным изображением G. Таким образом, при Л=- 1 определяется область множества точек текущего изображения F, соответствующих левому верхнему угловому отсчету тех фрагментов текущего изображения F, отличие которых от эталонного изображения G не превышает одного отсчета.

С приходом нулевого тактового импульса (фиг. Зг) по его переднему фронту в счетчике 3 тех ячеек однородной структуры, где

fij @=О, выполняется увеличение на единицу его содержимого, а в остальных ячейках, где fi> . gi=-1, состояние счетчика 3 остается без изменений, поскольку в течение этого такта д = 1. По заднему фронту нулевого тактового импульса происходит сдвиг влево содержимого всех ячеек однородной структуры, С целью сохранения информации о 40 текущем изображении F при его сдвиге размерность однородной структуры должна быть не меньше (К+и-1) x (M+m-1). На 1-м, 2-м, 5-М, 6-м, 8-м тактах не происходит изменения содержимого счетчиков 3 всех яче- 45 ек однородной структуры, поскольку ц =О для I= 1, 2, 5, 6. 8, следовательно, ftj ц = О и

äj =О. На всех тактах, когда @=1, t=3,4,7, с учетом того, что (>i =- О. при выполнении условия

1,1 составляют область левых верхних угловых отсчетов {согласно выбранному способу сканирования эталонного изображения G) двух фрагментов текущего изображения F, "искажения" которых по сравнению с эталонным изображением G не превышаютодного отсчета. Таким образом, только при условии Л -- О можно определить фра гменты текущего изображения F, полностью совпадающие с эталонным изображением G. В случае. когда Л > О, в область зафиксированных в соответствующих ячейках однородной структуры начальных отсчетов входят как начальные отсчеты эталонного изображения G в поле текущего изображения Г, у которого "искажения" равны нулю, так и начальные отсчеты "искаженного" эталонного изображения G с "искажениями" 1, 2...., Л . Начальные отсчеты обнаруженных фрагментов иэображения F с "искажениями" в пределах Л фиксируются наличием единичного сигнала на выходе триггера 5 в соответствующих ячейках однородной структуры. В дальнейшем координаты начальных отсчетов обнаруженных фрагментов изображения F можно определить в процессе работы всех ячеек в транзитном режиме, т,е, путем сдвига полученной информации в однородной структуре.

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

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

1778757

Фиг.I.

Фиг.2. типлексора, выход которого соединен с информационным входом первого триггера блока настройки, тактовый вход которого соединен с тактовым входом счетчика блока настройки и тактовым входом ячейки, вход 5 сброса которой соединен с входом установки в "0" первого триггера блока настройки, выходы третьего и четвертого элементов И которого соединены соответственно с вычитающим и суммирующим входами счетчика 10 блока настройки, выход признака "Меньше нуля" счетчика соединен с входом установки в "0" второго триггера блока настройкй, вход начальной установки ячейки соединен с входом обнуления счетчика и входом уста- 15 новки в "1" BTopol триггера блока настройки, выход первого элемента И которого соединен с входом второго элемента НЕ и первым входом третьего элемента И блока настройки, второй вход третьего элемента И которого соединен с выходом первого элемента НЕ блока настройки, первый и второй входы четвертого элемента И которого соединены соответственно с входом первого элемента HF и,выходом второго элемента

НЕ блока настройки, первый и второй входы второго элемента И которого соединены соответственно с выходом второго триггера блока настройки и входом разрешения записи ячейки.

1778757 J

020Ъ

-е

010

0 ° о °

1 О4ОО

О 4 ° °

Ь Ъ °

-г-20 !

«г

0

t

0.0 тот

-г

«!

0 ! г

Ъ

-г

«!

2 г

Ъ!.й ТА22Т

2-0 тл3ц

-г

«1

1 г

Ъ-й TACT

«2

«!

0 ! г

4-й ТА22Т

° г

«1

Э

1 г

И TACT

-0

«!

1 г

6-й тдкт

-г

«!

1 г

Ъ

«0

« «l

l г

7-й ТА22Т

8-w TACT

Фиг.3.

Составитель Т.Мартынюк

Техред M.Ìîðãåíòàë Корректор Н.Тупица

Редактор

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

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

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

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