Устройство для вычисления свертки Советский патент 1985 года по МПК G06F17/17 

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

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

Устройство содержит K-L вычислительных блоков 1.1,1.2,...,1.KLj блок 2 памяти, элементы 3.1,3,2..., 3.L-J задержки (каждая длиной N-K), L коммутаторов 4.1, 4.2, ...,4.L.

Каждый из вычислительных блоков 1 .q (q .2,.. . ,K«L) содержит буферные регистры 5.q, 6.q, регистр 7.q коэффициента, умножитель 8.q, регистр 9.q результата, сумматор lO.q, регистр ll.q результата.

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

Базовая операция А выполняется в течение одного такта в вычислительном блоке 1.q следующим образом В исходный момент времени в буферном регистре 6.q хранится операнда, который затем поступает на вход умножителя 8.q, на другой вход которого с выхода регистра 7.q коэффициента поступает коэффициент w(K L-q+l). Затем умножитель В.q формирует произведение w(K.L-q+l )а ai которое с приходом тактового импульса записывается в регистр 9.q результата. Под воздействием тактового импульса происходит также перезапись содержимого ад , буферного регистра 6.(q-l)

(1)

и содержимого а. буферного регистра 5.q соответственно в буферный регистр 5.q и буферный регистр 6.q (в случае блока 1.1 в буферный регистр 5.q записьшается новый входной отсчет) .

Базовая операция В выполняется в течение одного такта в вычислительном блоке 1.q следующим образом. В исходный момент времени в регистре 9.q результата и регистре 11.(q-1) результата хранятся соответ ственно произведение w(KL-(|+l)aa и частичный результат Ь™ . , которые

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

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

+x(n+D-3). w(D-2)-«-...+w(l).x(n), где .L,

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

такте с номером п, когда в буферный регистр 5.1 поступает отсчет х(п). Затем в течение последующих D-I тактов продолжается поступление отсчетов х(п+1), х(п+2),...,x(n+D-l),

причем каждый новый входной отсчет записьгеается в регистр 5.1, а ранее поступившие отсчеты сдвигаются на одну позицию в регистре сдвига, который образуется буферными регистрами 5.q и 6.q. Таким образом, в такте n+D отсчет x(n+D-l) поступает в буферный регистр 6.1, а отсчеты X (n+D-2), x() ,. . .x(n) записываются в следующих позициях указанного регистра сдвига. Формирование результата у(п) начинается в такте n+D+, в течение которого в блоке 1.1 выполняется базовая операция А, в результате которой в регистр

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

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

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

результата записьшается сумма

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

в регистр 9.2 результата записьшается произведение w(D-l)x(n+D-2). Кроме того, отсчет x(n+D-3) записывается в регистр 6.3, отсчет x(n+D-4), в регистр 5.4, отчет x(n+D-5) - в регистр 6.4 и т.д. Такт n+D+3. В блоке 1.2 выполняется базовая операция В, в результа те которой в регистр 11.2 результат записьюается сумма у(п)(п). +w(Dfx(n+D-2), а в блоке 1.3 выполняется базовая операция А, в результате которой в регистр 9.3 результата записывается произведение w(D-2)х xx(). Кроме того, отсчет x(n+D -4) записьшается в регистр 6.4, отсчет x(n-i-D-5) - в регистр 5.5 и т.д Такт n+D+4. В блоке .3 вьшолняется базовая операция В, в результа те которой в регистр 11.3 результата записьшается сумма у(п)з y(n)2+w(D-2)-хСп+О-З), а в блоке I.4 выполняется базовая операция А, в результате которой в регистр 9.4 результата записывается произведени w(D-3)«x(n+D-4). Кроме того, отсчет x(n+D-5) записывается в регистр 5.5 отсчет x(n+D-6) - в регистр 6.5 и т.д. Такт n+2D. В блоке l.(D-l) выполняется базовая операция В, в результате которой в регистр l.(D-l) результата записьтается сумма y(n))jj +w(2).x(n+l), а в блоке 1 .D выполняется базовая операция А, в результате которой произведение w(l)x(n) записьшается в регистр 9.D результата. Такт n+2D+,. в блоке 1.D выполня ется базовая операция В, в результа те которой в регистр 1I.D результат записьтаается окончательное значение у(п), откуда поступает в блок 2 памяти . При выполнении двумерной свертки устройство работает следующим образом. В регистре 7.q коэффициента, где , хранится коэффициент w(K-k+l, ). Одновременно с подачей сигнала Двумерная свертка, который поступает на управлянщий вход устройства, с выхода блока 2 памяти на вход элемента 3.(L-1) задержки со скоростью одного отсчета на такт начинают поступать от счеты входного массива. При этом указанные отсчеты передаются по столбцам, т.е. в такте с номером E(n,m) (m-l), N+n на вход элемента ) задержки поступает отсчет x(n,m), который затем задерживается на p(N-k) тактов (,2,...,L-1) в цепи, состоящей из элементов 3.(L-1), 3.(L-2)3.(L-p) задержки, чтобы в такте (N-k) (m+p-l) поступить на информационный вход коммутатора 4.(L-p), который (поскольку на его управляющий вход поступает сигнал Двумерная свертка передает отсчет х(п,т) на информационный вход блока I.(L-p-1)К+1. С выхода блока 2 памяти отсчеты входного массива поступают также непосредственно на информационный вход коммутатора 4.L, который передает их на информационный вход блока .(L-1)K+1. Рассмотрим формирование произвольного отсчета y(n,m) выходного массива (,2,...,N-K+I; ,2,..., M-L+1), определяемого выражением к,, tj((k.O-x(mk4,n,)fZw(k,2). х(пЛ- .., 1- Z w(n.L)X(.mt L-0 til , a -i) f(n.mV... + lj(n.mV Отсчеты входного массива, которые участвуют в формировании у (ii,m), с выхода элемента 3.1 задержки передаются посредством коммутатора 4.1на информационный вход блока 1.1, с такта (n,ra) + + (L-1) (N-k) (m+L-2)- N-(L-l)-K+n, когда в буферный регистр 5.1 поступает отсчет х(п,т). Затем в течение последующих (K-lJ тактов продолжается поступление отсчетов х(п+1,т), х(п+2,т)..., пока в такте S+K-1 отсчет х(п-«-К-1 ,га) не поступит в регистр 5.1. Формирование у (n,ni) начинается в такте S+K+I, в течение которого в блоке 1.I вьтолняется базовая операция А, в результате которой в регистр 9.1 результата записывается произведение w(K,1)х xx(n-i-K-I ,т) . Кроме того, отсчет х(п+К-3,т) записьшается в регистр 6.2, отсчет х(п+К-3,т) -в регистр 5.3, отсчет x(n+K-4,m) - в регистр 6.3 и т.д. Такт S+K+2. В блоке 1.1 вьтолняется базовая операция В, в результате которой в регистр 11.1 результата записьшается сумма у (п,т) 0+w(K,1) х(п+К-1 ,т), а в блоке 1.2выполняется базовая операция А,. в результате которой в регистр 9.2 результата записывается произведение w(K-l,)x(n+K-2,m). Кроме того.

5

отсчет x(n+K-3,m) записьшается в регистр 6.3, отсчет x(n-K+4,m) регистр 5.4, отсчет x(n+K-5,m) в регистр 6Л и т.д.

Такт S+K+3. В блоке 1.2 выполняется базовая операция В, в результате которой в регистр 11.2 результата записьтается сумма у (n,in) ,m)2+w(K-l, 1) . x(n+K-2,m), а в блоке 1.3 вьтолняется базовая операция А, в результате которой в регистр 9.3 результата записыва,ется произведение w(K-2,1) x{n+K-3, Кроме того, отсчет х(п+К-4,т) записывается в регистр 6.4, отсчет x(n+K-5,m) - в регистр 5.5 и т.д.

Такт S+2K+1. В блоке 1.К выпдлняется базовая операция В, в результате которой в регистр 11.К результата записьшается сумма ,т) ,m),m)+w(l,l)-x(n,m). Одновременно, т.е. начиная с такта R(n,m+l)+(L-2)(N-k) S+k, отсчеты входного массива х.(п,т+1), х(п+1, т+1)..., которые участвуют в формировании у(п,т), с выхода элемента 3.2 задержки передаются посредством коммутатора 4.2 на информационный вход блока l.(K-i-l), вплоть до отсчета х(п+К-1, т+1),который в такте S+2K-1 записьшается в регистр 5.(К+1). Формирование y(n,m) начинается в такте S+2K+1, в течение которого в блоке 1.(К+1) вьтолняется базовая операция А, в результате которой в регистр 9.() результата записьшается произведение w(K,2)x(n+K-l, m+1). Кроме того, отсчет х(п+К-2, т+1) записьшается в регистр 6.(К+2), отсчет х(п+К-3, т+1) - в регистр 5.(К+3), отсчет х(п+К-4, т+1) - регистр 6.(К+3) и т.д.

Такт S+2K+2. В блоке l.(K+l) выполняется базовая операция В, в результате которой в регистр 11. (K+l) результата записывается сумма у Cn,m)у Чп,т)+W(К,2) X(п+К-1,т+1) а в блоке 1,(К+2) выполняется базовая операция А, в результате которой в регистр 9.K+2J результата записьшается произведение w(K-l,2) хх(п+К-2, т+1). Кроме того, отсчет х(п+К-3, т+1) записьшается в регист 6.(К+3) отсчет х(п+К-4, ш+1) - регистр ЗДк+Д), отсчет х(п+К-5, т+1)регистр 6.{к+4) и т.д.

985356

Такт S+2K+3. В блоке 1.(к+2) выполняется базовая операция В, в результате которой в регистр J1.(К+2) результата записьшается сумма 5 y(n,m)(n,m)+w(K-1.2).x(m+K-2, m+1), а в блоке 1.,(к+3| выполняется базовая операция А, в результате которой в регистр 9.(К+З) результата записьшается произведение w(K-2,2).x(n+K-3), m+1). Кроме того, отсчет х(п+К-4, т+1) записьшается в регистр 6.(К+4), отсчет х(п+К-5, т+1) - в регистр 5.(к+5) и т.д.

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

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

сумма (п,т)у (п,т)+у (n,m) + + .. .,m) . Одновременно, т.е. начиная с такта R(n,m+L-l) (m+L-2).. (L-l)K, отсчеты входного массива x(n,m+L-l), х(п+1, m+L-1)..., которые участвуют в формировании у (n,m), с выхода блока 2 памяти передаются посредством коммутатора 4.L на информационный вход блока l.(L-l) К+1 вплоть до отсчета

5 х(п+К-1, m+L-1), который в такте S+2K-l записьшается в регистр 5. (L-1) К+1. Формирование у (п ,т) начинается в такте S+L-K+l, в течение которого в блоке l.(L-l) K+l

0 выполняется базовая операция А, в

результате которой в регистр 9. (L-1)К+1 результата записьшается произведение w(K,L)-x(п+К-1,m+L-1). Кроме того, отсчет х(п+К-2,m+L-1) записывается в регистр 6,(L-l)K+2, отсчет х(п+К-3, m+L-1) - в регистр 5.(L-1)I К+2 и т.д.

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

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

результате которой в регистр 11.K-L результата записьюается окончательное значение y(n,m), откуда поступает на информационный вход блока 2 памяти.

Фиг,1

I Ьлг г-лтг- /У ЛЛ -/; I Г

Г a4ejte Л

I : I ±

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СВЕРТКИ, содержащее блок памяти и 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 вычислительного блока т-й группы

. r f AlfM fr. 9.1-1

/-5

)