The following is a collection of bilinear forms for linear convolution. In each case describes a bilinear form for n point linear convolution. That is
computes the linear convolution of the n point sequences h and x.
For each Dn we give Matlab programs that compute Dnx and Dntx, and for each Fn we give a Matlab program that computes Fntx. When the matrix exchange algorithm is employed in the design of circular convolution algorithms, these are the relevant operations.
D2 can be implemented with 1 addition, D2t with two additions.
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);
D3 can be implemented in 7 additions, D3t in 9 additions.
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;
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);
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;
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);
F18 and the program F18t are too big to print.