Устройство для вычисления свертки

 

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СВЕРТКИ, содержащее блок памяти и L групп вычислительных блоков по К блоков в каждой, где L-K - длина входной последовательности, о т .личающееся тем, что, с це-, лью упрощения устройства, оно содержит (L-1) элементов задержки и L коммутаторов , причем информационный выход блока памяти подключен к первому информационному входу L-ro коммутатора и входу первого элемента задержки , выход i-ro (, 2) элемента задержки подключен к первому информационному входу i-ro коммутатора и входу (i-l)-ro элемента задержки, выход первого элемента задержки подключен к первому информационному входу первого коммутатора, второй информационный вход которого подключен к выходу блока памяти, причем каждый. вычислительный блок содержит первый и второй регистры результата, сумматор , умножитель, первый и второй буферные регистры и регистр коэффициента , выход которого подключен к первому входу умножителя, выход которого подключен к информационному входу первого регистра результата, выход которого подключен к первому входу сумматора, выход которого подключен к информационному входу второ го регистра результата, второй вход умножителя подключен к выходу первого буферного регистра, информаS ционный вход которого подключен к выходу второго буферного регистра, информационные выходы первого буферного регистра и второго регистра результата k-ro (, К-1) вычислительнрго блока -й (, L) группы подключены, соответственно к информационному входу второго г;уфер:О X) ного регистра и второму входу сумматора (k+J)ro вычислительного блока :л -й группы, выходы первого буферного э :л регистра и второго регистра результата k-ro вычислительного блока т-й группы

СОЮЗ СОВЕТСНИХ

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

РЕСПУбЛИН (191 (! () ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

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

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 3739634/24-24 (22) 14. 05. 84 (46) 15.!2.85. Бюл. Р 46 (71) Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) А.В. Выжиковска, P. Выжиковски (РЬ) и Ю.С. Каневский (53) 681.32(088.8) .(56) Авторское свидетельство СССР

9 1057940, кл. G 06 F 15/332, 1982, Kung Н.Т., Ricard R.L. Hardvare .pipeline for muftidimensiona7 signaX convolution and resampXing—

IEEE Computer Society on Computer

Architecture for Pattern Analysis

and Image Database Management, 1981, р. 273-278. (54)(57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

СВЕРТКИ, содержащее блок памяти и

Ь групп вычислительных блоков по К блоков в каждой, где L-К вЂ” длина входной последовательности, о т— ,л и ч а ю щ е е с я тем, что, с це.лью упрощения устройства, оно содержит (Ь-1) элементов задержки и L коммутаторов, причем информационный вы ход блока памяти подключен к первому информационному входу L-го коммутато. ра и входу первого элемента задержки, выход i-го (i L-1, 2) элемента задержки подключен к первому информационному входу i-го коммутатора и входу (i-1)-го элемента задержки, выход первого элемента задержки подключен к первому информационному вхо.. ду первого коммутатора, второй.информационный вход которого подключен (5})4 6 06 Р 1 5/353 ° Н 03 Н 1 7/04 к выходу блока памяти, причем каждый. вычислительный блок содержит первый и второй регистры результата, сумматор, умножитель, первый и второй буферные регистры и регистр коэффициента, выход которого подключен к первому входу умножится, выход которого подключен к информационному входу первого регистра результата, вы" ход которого подключен к первому входу сумматора, выход которого подключен к информационному входу второго регистра результата, второй вход умножите я подключен к выходу первого буферного регистра, информационный вход которого подключен к выходу второго буферного регистра, информационные выходы первого буферного регистра и второго регистра результата k-го (1с=1, К-1) вычислительного блока 2-й (I=l, L) группы подключены, соответственно к информационному входу второго буферного регистра и второму входу сумматора (k+1)-ro вычислительного блока

f-й группы, выходы первого буферного регистра и второго регистра результата М-ro вычислительного блока

m-й группы (m=I L-1) подключены соответственно к второму информационному входу (m+1)-го коммутатора и второму входу сумматора первого вычислительного блока (m+1)-й группы, выход второго регистра результата

К-ro вычислительного блока L-й группы подключен к информационному входу блока памяти, а выход Р-го коммутатора подключен к информационному входу второго буферного регистра первого вычислительного блока P-й группы.! 1 98535

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

На фиг. изображена общая схема устройства; на фнг. 2 — схема вычислительного.,блока; на фиг, 3 и 4— блок-схема алгоритма работы устройства при вычислении результата y(n)

- одномерной свертки, на фиг. 5 — временная диаграмма функционирования устройства при вычислении одномерной свертки (соответствует К L=-3) .

Устройство содержит К L вычислительных блоков 1.1,1.2,...,1.К 1.) блок 2 памяти, элементы 3.1 3.2..., З.L-I задержки (каждая длиной Н-К), Ь коммутаторов 4.1, 4.2, ...„4 L, Каждый из вычислительных блоков

I.q (q I.2,...,Ê 1.) содержит буферные регистры 5.q, б.q, регистр 7.q коэффициента, умножнтель 8.q, регистр 9.q результата, сумматор 10.q, регистр !I.q результата.

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

Базовая операция А выполняется в тенение одного такта в вычислительном блоке I.q следующим образом.

В исходный момент времени в буферном (2) регистре б.q хранится операнд а который затем поступает на вход умножителя 8.q, на другой вход которого с выхода регистра 7,q коэффициента поступает коэффициент ч(К"L-q+1).

Затем умножитель 8.о формирует произведение w(KiL-q+I)a < которое с приходом. тактового импульса записывается в регистр 9.q результата. Под воздействием тактового импульса происходит также перезапись содержимого а буферного регистра 6.(q-l) (11 н содержимого а буферного регистра

5 . о соотв е тс тв ейно в буферный ре -. гис тр 5 . q и буферный регистр б . q (в случае блока l . 1 в буферный регистр 5 . q записывается новый входной отсчет) .

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

В исходный момент времени в регис тре 9,q результата и регистре

11. (q-1) результата хранятся соответ (г) ственно произведение w(K L- +1)а

% и частичный результат Ь, которые

5 затем поступают на входы сумматора

IО.q, формирующего.их сумму. С приходом тактового импульса указанная сумма записывается в регистр 11 q результата.

Рассмотрим формирование отсчета выходной последовательности с номером n(n=l 2..., P-К L+l), определяемого выражением

y(n)=w(D) x(n+D-1)+w(D-1) x(n+D-2)+

+х(п+Р-3) w(D-2)+... +w(1) х(п), где D=K L.

Поступление отсчетов входной последовательности, которые участвуют в формировании у(п), начинается в

20 такте с номером и, когда в буферный регистр 5. поступает отсчет x(n).

Затем в течение последующих D-! тактов продолжается поступление отсчетов х(п+1), x(n+2),...,х(п+Р-l), причем каждый новый входной отсчет записывается в регистр 5.1, а ранее поступившие. отсчеты сдвигаются на одну позицию в регистре сдвига, который образуется буферными регистра30 ми S.q и б.q. Таким образом, в такте n+D отсчет x(n+D-1) поступает в буферный регистр 6.1, а отсчеты

x(n+D-2), x(n+D-3),...х(а) записываются в следующих позициях укаэанного регистра сдвига. Формирование результата y(n) начинается в такте

n+D+1 в течение которого в блоке

i.I выполняется базовая операция

А, в результате которой в регистр

40 9.1 результата записывается произведение w(D) ° x(n+D-l). Кроме того, отсчет х(п+Р-2) записывается в регистр 6.2, отсчет x(n+D-3) — в регистр 5.3, отсчет x(n+D-4) - в !

45 регистр 6.3 и т.д.

Такт n+D+2. В блоке 1.1 выполняются базовая операция В, в результате которой во второй регистр 11.1

50 результата записывается сумма у(п)» 0+w(D) i x(n+D-l ) (на вход сумматора 10.1 всегда подается код нуля), а в блоке 1,2 выполняется базовая операция А, в результате которой

55 в регистр 9.2 результата записывается произведение w(D-l)x(n+D-2).

Кроме того, отсчет x(n+D-3) записывается в регйстр 6.3, отсчет x(n+D-4) !

198535 в регистр 5.4, отчет x(n+D-5) — в регистр 6.4 н т.д.

Такт n+D+3. В блоке I.2 выполняется базовая операция В, в результате которой в регистр 11.2 результата записывается сумма у(п) =у(п) +w(D-I.

xx(n+D-3), Кроме того, отсчет x(n+D-4) записывается в регистр 6.4, отсчет x(n+D-5) — в регистр 5.5 и т.д.

Такт n+D+4. В блоке 1.3 выполняется базовая операция В, в результате которой в регистр 1! .3 результата записывается сумма y(n) х= у(п) +м(Р-2) x(n+D-З), а в блоке.

1.4 выполняется базовая операция А, в результате которой в регистр 9.4 результата записывается произведение

w(D-3) x(n+D-4). Кроме того, отсчет х{п+Р-5) записывается в регистр 5.5, отсчет x(n+D-6) — в регистр 6.5 и

T ед

Такт n+2D. В блоке 1. (Р-1) выполняется базовая операция В, в результате которой в регистр 11 . .(D-3) результата записывается сумма y{n)p =

=y(n) +w(2) ° x(n+l), а в блоке 1.D выполняется базовая операция А, в рез уль тате ко торой произв еденне

w(3) х(п) записывается в регистр

9.Р результата.

Такт n+2D+,. В блоке I.Р выполняется базовая операция В„ в результате которой в регистр 11.D результата записывается окончательное значение

y(n), откуда поступает в блок ? памяти.

При выполнении двумерной свертки устройство работает следующим образом.

В регистре 7.q коэффициента, где q KE+k, хранится коэффициент

w(K k+1 У). Одновременно с подачей сигнала "Двумерная свертка", который поступает на управляющий вход устройства, с выхода блока 2 памяти на вход элемента 3.(L-I) задержки со скоростью одного отсчета на такт начинают пс"тупать отсчеты входного массива. При этом указанные отсчеты передаются по столбцам, т.е. в такте с номером

R(n,m)=(m-1), N+n на вход элемента

3(L-1) задержки поступает отсчет х(п,m), который затем задерживается на р(N-к) тактов (р=1,2,...,L-!) в цепи, состоящей из элементов

3 .(L †), 3.(Ь-2), ...,3. (Ь-р) задержки, чтобы в такте R+p(й-k)

5 =(m+p-I)N K+n поступить на инфор) мационный вход коммутатора 4.(Ь-р), который (поскольку на его управляющий вход поступает сигнал "Двумерная свертка") передает отсчет х(п,m) на информационный вход блока 1.(L-p-l) К+1. С выхода блока

2 памяти отсчеты входного массива поступают также непосредственно на информационный вход коммутатора

4.Ь, который передает их на информационный вход блока 1.(1 -1) ° К+1.

Рассмотрим формирование произвольного отсчета y(n,m) выходного массива (n=l,2,...,N-К+1; ш=1,2,..., М-L+1), определяемого выражением к

k (, ) = + Ь (!(, () > (Aik - 3, рi) Ф .Е W(g,2 j. к=1 к» к

x(nil I>m ijw...1.Еар,tj x(n+L 1,m> L 113 п п ) ) (п,в, " g (п,т}.

Отсчеты входного массива, которые участвуют в формировании у (n,m), с выхода элемента 3.1 задержки пе30 редаются посредством коммутатора

4.1 на информационный вход блока

I.I, на iная с такта S=R(n,m)+

+(L-1)i (N-k)=(m+L-2)- N-(L-l)- K+n, когда в буферный регистр 5.1 поступает отсчет х(п,m). Затем в течение последующих (К-1) тактов продолжается поступление отсчетов x(n+1 m), х(п+2,m)..., пока в такте S+K-1 отсчет x(n+K-1 m) не поступит в щ регистр 5.1. Формирование yI(п,m) начинается в такте S+K+I в течение которого в блоке 1.1 выполняется базовая операция А, в результате которой в регистр 9.1 результата записывается произведение w(K, I ) х

xx(n+K-l,m) . Кроме того, отсчет х(п+К-З,ш) записывается в регистр 6. 2, отсчет х(п+К-З,m) — в регистр 5.3,отсчет

x(n+K-4,m) — в регистр 6.3 и т.д.

gp Такт S+K+2. В блоке I 1 выполняется базовая операция В, в результате которой в регистр 11 1 результата записывается сумма у (n,m)= 0+w(K, 1) x(n+K-l,m), а в блоке ! .2 выполняется базовая операция А, . в результате которой в регистр 9.2 результата записывается произведение w(K-1,1) x(n+K-2,m) . Кроме того, 1198535

20

30 отсчет х (n+K-З,ш) записывается в регистр 6. 3, отсчет x(n-К+4,m) регистр 5.4, отсчет х(п+К-5,ш) в регистр 6.4 и т.д.

Такт S+K+3 В блоке 1.2 выполняется базовая операция В, в результате которой в регистр 1).2 результата записьвается сумма у (п,m)

=у (n,m) +w(K-1, l ) ° x (n+K-2,m), а в блоке 1.3 выполняется базовая операция А, в результате которой в регистр 9.3 результата записьвается произведение w(K-2, 1) ° х(п+К-Ç,m).

Кроме того, отсчет x(n+K-4,m) записывается в регистр 6.4, отсчет х(п+К-5,m) — в регистр 5.5 и т.д.

Такт S+2K+1 И блоке 1.К выполняется базовая операция В, в результате которой в регистр 11.К резуль() тата записывается сумма у (п,ш)= у1 1(п,in) =у 1(п,m) +ч(1, 1) х (n,m) . Од— новременно, т.е. начиная с такта

R(n,m+1)+.(L-2)(N-k) = S+k, отсчеты входного массива х(п,ш+1), х(п+1, ш+1)..., которые участвуют в формировании у (п,ш), с выхода

3 элемента 3.2 задержки передаются посредством коммутатора 4.2 на информационный вход блока 1. (К+1), вплоть до отсчета х(п+К-l, ш+1),. который в такте S+2K-1 записывается в регистр 5. (К+1) . Формирование у (п,m) начинается в такте S+2K+l, в течение которого в блоке 1.(К+1) выполняется базовая операция А, в результате которой в регистр

9.(K+1) результата записывается произведение ч(К,2)x(n+K-l, m+1). Кроме того, отсчет х(п+К-2, m+1) записывается в регистр 6.(К+2), отсчет 40 х(п+К-З, ш+1) — в регистр 5.(К+3), отсчет x(n+K-4, ш+1) — регистр

6.(К+3) и т.д.

Такт S+2K+2. В блоке 1.(К+1) вы- 45 нолняется базовая операция В, в результате которой в регистр 11.(K+1) результата записывается сумма у (n,m) у1(n,m)+w(K,2) x(n+K-l,ø+1), а в блоке 1.(К+2) выполняется базовая операция А, в результате которой в регистр 9.(К+2) результата записывается произведение w(K-1,2)x хх (n+K-2, m+1) . Кроме того, отсчет х (п+К-З, m+1) записывается в регистр

6. (К+3) отсчет х(п+К-4, ш+1) — регистр 5. (K+4), отсчет x(n+K-5, m+1)регистр 6. (К+4) и т.д. ь

Такт S+2K+3. В блоке 1. (К+2) выполняется базовая операция В, в результате которой в регистр 11. (К+2) результата записывается сумма у (n,m) =у (n,m)+w(K-l 2) ° x (m+K-2, 2

m+1), а в блоке .(К+3 выполняется базовая операция А, в результате которой в регистр 9. (К+3 ) результата записывается произведение

w(K-2,2) x(n+K-3), m+1 ) . Кроме того, отсчет x(n+K-4, m+1) записывается в регистр 6.(К+4), отсчет

x(n+K-5, ш+1) — в регистр 5.(К+5) и т.д.

Такт Б+ЗК+1. В блоке 1.2К выполняется базовая операция В, в результате которой в регистр 11.2К результата записывается сумма у (n,m) „=у 2(n,m)+y (п,m) у (п,m) +

+w (1, 2). x (n, ø+1) .

Такт S+L K+1. В блоке 1. (L-1)К выполняется базовая операция В, в результате которой в регистр

l 1. (L-1)К результата эаписьвается сумма у" (n,m)=y1(п,m)+y (n,ш)+

+. ° .+у " "(n,m). Одновременно, т.е. начиная с такта R(n,m+L-l} (m+L-2)., N+n=S+(L-l)K, отсчеты входного массива x(n,ø+Ü-l}, х(п+1, m+L-l)..., которые участвуют в формировании у (n,m) с выхода блока 2 памяти передаются посредством коммутатора

4.Ь на информационный вход блока

1.(L-1) K+1 вплоть до отсчета

x(n+K-1, m+L-l), который в такте

S+2 К-1 записьвается в регистр

5.(L-1)К+1. Формирование у"(n,m) начинается в такте S+L К+1, в течение которого в блоке 1.(Ь-1) К+1 выполняется базовая операция А, в результате которой в регистр 9.(L-1)К+1 результата записывается произведение w(K, Ь) ° х (n+K-1,ш+Ь-1) . Кроме того, отсчет x(n+K-2,m+L-1) записывается в регистр 6.(Ь-1)K+2, отсчет

x(n+K-3, m+L-1) — в регистр 5.(Ь-1)х

»К+2 и т.д.

Такт S+L К+2. В блоке 1. (L-1)К+1 выполняется базовая операция В, в результате которой в регистр 11.(L-1) хК+1 результата записывается сумма у (n,m), =у (n,ш) <+w(K,L) х(п+К-l, m+L-l), а в блоке 1. (Ь-l)K+2 выполняется базовая операция А, в результате которой в регистр 9.(Ь-l)K+2 результата записывается произведение w(K-l, L) ° х (m+K-2,m+L-l ) . Кроме того, отсчет х (и+К-З,m+L-1) эапи7 сывается в регистр 6. (L- I ) K+3, отсчет x(п+К.-4,m+L-1) — в регистр

5. (L-1)K+4 и т.д.

Такт S+(L+l)K+I. В блоке I.К L выполняется базовая операция В, в

1198535 результате которой в регистр 1! .К. L результата записывается окончательное значение y(n,ш), откуда поступает на информационный вход блока 2 па5 мЯти.

1 198535!

198535

1198535

Эаказ 7723/49 Тираж 709

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

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

Подписное

Филиал ППП "Патент", r. Ужгород, ул, Проектная, 4

Составитель А. Баранов

Редактор И. Рыбченко Техред Т.Фанта Корректор Е. Сирохман