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

	2 AP 02 Chemical Level of Organization MCQ By OpenStax Start Quiz
©flickr: Luis	Chemistry Final Review By Madison Christian Start Exam
	10 Biology 10 Cell Reproduction MCQ By OpenStax Start Quiz
	Excel 2007 Quiz By Lakeima Roberts Start Quiz
	Deciduous Forest By Hope Percle Start Quiz
	Biology Exam Final By Savannah Parrish Start Exam
	10 Neuroanatomy 10 Corticospinal Tract By Stephen Voron Start Quiz
	24 AP 24 Metabolism Nutrition Essay By OpenStax Start Flashcards
	Concepts of biology By OpenStax Read Online Course
©flickr: Dave	Infection Control By Cath Yu Start Quiz