Automatic Generation of Prime Length FFT Programs by C. Sidney Burrus - HTML preview

/ Home / Mathematics (Academic) / Automatic Generation of Prime Length FFT Programs

PLEASE NOTE: This is an HTML preview only and some elements such as links or page numbers may be incorrect.
Download the book in PDF, ePub, Kindle for a complete version.

Chapter 9. Appendix: Bilinear Forms for Linear Convolution

Appendix: Bilinear Forms for Linear Convolution

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

(9.1) y = F_n {D_nh * D_nx}

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.

(9.2)

(9.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.

(9.4)

(9.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

(9.6) D₄ = D₂ ⊗ D₂

(9.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

(9.8) D₆ = D₂ ⊗ D₃

(9.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

(9.10) D₈ = D₂ ⊗ D₂ ⊗ D₂

(9.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

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

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

References

Solutions