<< Chapter < Page | Chapter >> Page > |
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
computes the linear convolution of the $n$ point sequences $h$ and $x$ .
For each ${D}_{n}$ we give Matlab programs that compute ${D}_{n}x$ and ${D}_{n}^{t}x$ , and for each ${F}_{n}$ we give a Matlab program that computes ${F}_{n}^{t}x$ . When the matrix exchange algorithm is employed in the design of circular convolutionalgorithms, these are the relevant operations.
${D}_{2}$ can be implemented with 1 addition, ${D}_{2}^{t}$ 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);
${D}_{3}$ can be implemented in 7 additions, ${D}_{3}^{t}$ 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);
${F}_{18}$ and the program F18t are too big to print.
Notification Switch
Would you like to follow the 'Automatic generation of prime length fft programs' conversation and receive update notifications?