0.8 Appendix: bilinear forms for linear convolution

Automatic generation of prime Page 1 / 1

Appendix: 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\}

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.

2 point linear convolution

$D_{2}$ can be implemented with 1 addition, $D_{2}^{t}$ with two additions.

D_{2} = [\begin{matrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{matrix}]

F_{2} = [\begin{matrix} 1 & 0 & 0 \\ -1 & -1 & 1 \\ 0 & 1 & 0 \end{matrix}]

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_{3}$ can be implemented in 7 additions, $D_{3}^{t}$ in 9 additions.

D_{3} = [\begin{matrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & -1 & 1 \\ 1 & 2 & 4 \\ 0 & 0 & 1 \end{matrix}]

F_{3} = \frac{1}{6} [\begin{matrix} 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 \end{matrix}]

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_{4} = D_{2} \otimes D_{2}

F_{4} = [\begin{matrix} 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 \end{matrix}]

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_{6} = D_{2} \otimes D_{3}

F_{6} = \frac{1}{6} [\begin{matrix} 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 \end{matrix}]

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_{8} = D_{2} \otimes D_{2} \otimes D_{2}

F_{8} = [\begin{matrix} 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 \end{matrix}]

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_{8} = D_{2} \otimes D_{3} \otimes D_{3}

$F_{18}$ and the program F18t are too big to print.

<< Chapter < Page Page > Chapter >>

Read also:

Get Jobilize Job Search Mobile App in your pocket Now!

100% Free Mobile Applications
Receive real-time job alerts and never miss the right job again

Source: OpenStax, Automatic generation of prime length fft programs. OpenStax CNX. Sep 09, 2009 Download for free at http://cnx.org/content/col10596/1.4

Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Automatic generation of prime length fft programs' conversation and receive update notifications?

Ask

	Anthropology Language Culture By Richley Crapo Start Assignment
	16 AP 16 Neurological Essay Exam By OpenStax Start Flashcards
	Real Estate Finance Exam 2003 By Tod McGrath Start Exam
	2 Muscular System MCQ By Nick Swain Start Quiz
	Assembly Programming Language By JavaChamp Team Start Quiz
	1 CDL Quiz - Air Brakes Endorsement Part 1 By Jazzycazz Jackson Start Quiz
	2 Timeshare 2 By Jams Kalo Start Quiz
	9 Domain Driven Design By JavaChamp Team Start Quiz
	25 AP Key Terms 25 The Urinary System By OpenStax Start Key Terms
	19 Biology 19 The Evolution of Populations MCQ By OpenStax Start Quiz