Bilinear Forms for Linear Convolution

Bilinear Forms for Linear Convolution

The following is a collection of bilinear forms for linear convolution. In each case (D_n,D_n,F_n) describes a bilinear form for n point linear convolution. That is

y=F_n{D_n,h,*,D_n,x}(1)

computes the linear convolution of the n point sequences h and x.

For each D_n we give Matlab programs that compute D_nx and D_n^tx, and for each F_n we give a Matlab program that computes F_n^tx. When the matrix exchange algorithm is employed in the design of circular convolution algorithms, these are the relevant operations.

2 point linear convolution

D₂ can be implemented with 1 addition, D₂^t with two additions.

D₂=[

1	0
0	1
1	1

](2)

F₂=[

1	0	0
-1	-1	1
0	1	0

](3)

 function y = D2(x) y = zeros(3,1); y(1) = x(1); y(2) = x(2); y(3) = x(1) + x(2); 

 function y = D2t(x) y = zeros(2,1); y(1) = x(1)+x(3); y(2) = x(2)+x(3); 

 function y = F2t(x) y = zeros(3,1); y(1) = x(1)-x(2); y(2) = -x(2)+x(3); y(3) = x(2); 

3 point linear convolution

D₃ can be implemented in 7 additions, D₃^t in 9 additions.

D₃=[

1	0	0
1	1	1
1	-1	1
1	2	4
0	0	1

](4)

F₃=

1

6

[

6	0	0	0	0
-3	6	-2	-1	12
-6	3	3	0	-6
3	-3	-1	1	-12
0	0	0	0	6

](5)

 function y = D3(x) y = zeros(5,1); a = x(2)+x(3); b = x(3)-x(2); y(1) = x(1); y(2) = x(1)+a; y(3) = x(1)+b; y(4) = a+a+b+y(2); y(5) = x(3); 

 function y = D3t(x) y = zeros(3,1); y(1) = x(2)+x(3)+x(4); a = x(4)+x(4); y(2) = x(2)-x(3)+a; y(3) = y(1)+x(4)+a; y(1) = y(1)+x(1); y(3) = y(3)+x(5); 

 function y = F3t(x) y = zeros(5,1); y(1) = 6*x(1)-3*x(2)-6*x(3)+3*x(4); y(2) = 6*x(2)+3*x(3)-3*x(4); y(3) = -2*x(2)+3*x(3)-x(4); y(4) = -x(2)+x(4); y(5) = 12*x(2)-6*x(3)-12*x(4)+6*x(5); y = y/6; 

4 point linear convolution

D₄=D₂⊗D₂(6)

F₄=[

1	0	0	0	0	0	0	0	0
-1	-1	1	0	0	0	0	0	0
-1	1	0	-1	0	0	1	0	0
1	1	-1	1	1	-1	-1	-1	1
0	-1	0	1	-1	0	0	1	0
0	0	0	-1	-1	1	0	0	0
0	0	0	0	1	0	0	0	0

](7)

 function y = F4t(x) y = zeros(7,1); y(1) = x(1)-x(2)-x(3)+x(4); y(2) = -x(2)+x(3)+x(4)-x(5); y(3) = x(2)-x(4); y(4) = -x(3)+x(4)+x(5)-x(6); y(5) = x(4)-x(5)-x(6)+x(7); y(6) = -x(4)+x(6); y(7) = x(3)-x(4); y(8) = -x(4)+x(5); y(9) = x(4); 

6 point linear convolution

D₆=D₂⊗D₃(8)

F₆=

1

6

[

6	0	0	0	0	0	0	0	0	0	0	0	0	0	0
-3	6	-2	-1	12	0	0	0	0	0	0	0	0	0	0
-6	3	3	0	-6	0	0	0	0	0	0	0	0	0	0
-3	-3	-1	1	-12	-6	0	0	0	0	6	0	0	0	0
3	-6	2	1	-6	3	-6	2	1	-12	-3	6	-2	-1	12
6	-3	-3	0	6	6	-3	-3	0	6	-6	3	3	0	-6
-3	3	1	-1	12	3	3	1	-1	12	3	-3	-1	1	-12
0	0	0	0	-6	-3	6	-2	-1	6	0	0	0	0	6
0	0	0	0	0	-6	3	3	0	-6	0	0	0	0	0
0	0	0	0	0	3	-3	-1	1	-12	0	0	0	0	0
0	0	0	0	0	0	0	0	0	6	0	0	0	0	0

](9)

          function y = F6t(x) y = zeros(15,1); y(1) = 6*x(1)-3*x(2)-6*x(3)-3*x(4)+3*x(5)+6*x(6)-3*x(7); y(2) = 6*x(2)+3*x(3)-3*x(4)-6*x(5)-3*x(6)+3*x(7); y(3) = -2*x(2)+3*x(3)-x(4)+2*x(5)-3*x(6)+x(7); y(4) = -x(2)+x(4)+x(5)-x(7); y(5) = 12*x(2)-6*x(3)-12*x(4)-6*x(5)+6*x(6)+12*x(7)-6*x(8); y(6) = -6*x(4)+3*x(5)+6*x(6)+3*x(7)-3*x(8)-6*x(9)+3*x(10); y(7) = -6*x(5)-3*x(6)+3*x(7)+6*x(8)+3*x(9)-3*x(10); y(8) = 2*x(5)-3*x(6)+x(7)-2*x(8)+3*x(9)-x(10); y(9) = x(5)-x(7)-x(8)+x(10); y(10) = -12*x(5)+6*x(6)+12*x(7)+6*x(8)-6*x(9)-12*x(10)+6*x(11); y(11) = 6*x(4)-3*x(5)-6*x(6)+3*x(7); y(12) = 6*x(5)+3*x(6)-3*x(7); y(13) = -2*x(5)+3*x(6)-x(7); y(14) = -x(5)+x(7); y(15) = 12*x(5)-6*x(6)-12*x(7)+6*x(8); y = y/6; 

8 point linear convolution

D₈=D₂⊗D₂⊗D₂(10)

F₈=[

1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
-1	-1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
-1	1	0	-1	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	1	-1	1	1	-1	-1	-1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
-1	-1	0	1	-1	0	0	1	0	-1	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0
1	1	-1	-1	-1	1	0	0	0	1	1	-1	0	0	0	0	0	0	-1	-1	1	0	0	0	0	0	0
1	-1	0	1	1	0	-1	0	0	1	-1	0	1	0	0	-1	0	0	-1	1	0	-1	0	0	1	0	0
-1	-1	1	-1	-1	1	1	1	-1	-1	-1	1	-1	-1	1	1	1	-1	1	1	-1	1	1	-1	-1	-1	1
0	1	0	-1	1	0	0	-1	0	1	1	0	-1	1	0	0	-1	0	0	-1	0	1	-1	0	0	1	0
0	0	0	1	1	-1	0	0	0	-1	-1	1	1	1	-1	0	0	0	0	0	0	-1	-1	1	0	0	0
0	0	0	0	-1	0	0	0	0	-1	1	0	-1	-1	0	1	0	0	0	0	0	0	1	0	0	0	0
0	0	0	0	0	0	0	0	0	1	1	-1	1	1	-1	-1	-1	1	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	-1	0	1	-1	0	0	1	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	-1	-1	1	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0

](11)

 function y = F8t(x) y = zeros(27,1); y(1) = x(1)-x(2)-x(3)+x(4)-x(5)+x(6)+x(7)-x(8); y(2) = -x(2)+x(3)+x(4)-x(5)+x(6)-x(7)-x(8)+x(9); y(3) = x(2)-x(4)-x(6)+x(8); y(4) = -x(3)+x(4)+x(5)-x(6)+x(7)-x(8)-x(9)+x(10); y(5) = x(4)-x(5)-x(6)+x(7)-x(8)+x(9)+x(10)-x(11); y(6) = -x(4)+x(6)+x(8)-x(10); y(7) = x(3)-x(4)-x(7)+x(8); y(8) = -x(4)+x(5)+x(8)-x(9); y(9) = x(4)-x(8); y(10) = -x(5)+x(6)+x(7)-x(8)+x(9)-x(10)-x(11)+x(12); y(11) = x(6)-x(7)-x(8)+x(9)-x(10)+x(11)+x(12)-x(13); y(12) = -x(6)+x(8)+x(10)-x(12); y(13) = x(7)-x(8)-x(9)+x(10)-x(11)+x(12)+x(13)-x(14); y(14) = -x(8)+x(9)+x(10)-x(11)+x(12)-x(13)-x(14)+x(15); y(15) = x(8)-x(10)-x(12)+x(14); y(16) = -x(7)+x(8)+x(11)-x(12); y(17) = x(8)-x(9)-x(12)+x(13); y(18) = -x(8)+x(12); y(19) = x(5)-x(6)-x(7)+x(8); y(20) = -x(6)+x(7)+x(8)-x(9); y(21) = x(6)-x(8); y(22) = -x(7)+x(8)+x(9)-x(10); y(23) = x(8)-x(9)-x(10)+x(11); y(24) = -x(8)+x(10); y(25) = x(7)-x(8); y(26) = -x(8)+x(9); y(27) = x(8); 

18 point linear convolution

D₈=D₂⊗D₃⊗D₃(12)

F₁₈ and the program F18t are too big to print.