Question

Practice with polynomial multiplication by FFT.

(a) Suppose that you want to multiply the two polynomials x + 1 and ${\mathit{x}}^{\mathbf{2}}\mathbf{+}\mathbf{1}$using the FFT. Choose an appropriate power of two, find the FFT of the two sequences, multiply the results component wise, and compute the inverse FFT to get the final result.

(b) Repeat for the pair of polynomials $\mathbf{1}\mathbf{+}\mathit{x}\mathbf{+}\mathbf{2}{\mathit{x}}^{\mathbf{2}}$and 2 + 3x.

Short answer

1. FTT of two sequence: (4,0,0,0)
2. FTT of two sequence: ( 20, - 5 -i, -2 , - 5 +i )

Step-by-step solution

Solution of part (a)

Multiplication of polynomials by Fast Fourier Transform (FFT):

Fast Fourier Transform (FFT):

The $4\times 4$matrix of FFT is,

localid="1659009189962" $M_4\left({\omega }^{\text{'}}\right)=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& \omega & {\omega }^2& {\omega }^3\\ 1& {\omega }^2& {\omega }^3& {\omega }^6\\ 1& {\omega }^3& {\omega }^6& {\omega }^9\\ & & & \end{array}\right].....\left(1\right)$

The difficult result of a nth fundamental plus unity is,

${\omega }^{\text{'}}=e^{\frac{2\mathrm{\pi i}}{n}}$ …… (2)

Alternative in Equations, the value of " n " is " 4 " (2). As a result, the value of is

$$\begin{gathered} {\omega }^{\text{'}}=e^{\frac{2\mathrm{\pi i}}{4}} \\ =e^{\frac{\pi i}{2}} \end{gathered}$$

Note: $e^{ix}=\cos \left(x\right)+i\sin \left(x\right)$

Thus, $e^{\frac{\mathrm{\pi i}}{2}}$has already been prepared in accordance with the information provided:

$$\begin{gathered} \omega =\cos \left(\frac{\mathrm{\pi }}{2}\right)+i\sin \left(\frac{\mathrm{\pi }}{2}\right) \\ =\cos \left(90\right)+i\sin \left(90\right) \\ =0+i\left(1\right) \\ \omega =i...........\left(3\right) \end{gathered}$$

Alternative Equation (3) in Equation (1).

$M_4\left({\omega }^{\text{'}}\right)=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& i& i^2& i^3\\ 1& i^2& i^3& i^6\\ 1& i^3& i^6& i^9\\ & & & \end{array}\right].....\left(4\right)$

In general, the value of $i,i^2,i^3,i^4$are,

$$\begin{gathered} i=i \\ {i}^2=-1 \\ {i}^3=-i \\ {i}^4=1 \end{gathered}$$ ...........(5)

The counting value of $i^6,i^9$is,

$$\begin{gathered} i^6=i^4\times i^2=-1 \\ {i}^9=i^6\times i^3=i \end{gathered}$$ …… (6)

Alternative counting values are $i,i^2,i^3,i^4,i^6,i^9$in Equation (4). The FFT matrix is,

$M_4\left({\omega }^{\text{'}}\right)=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& i& -1& -i\\ 1& -1& 1& -1\\ 1& -i& -1& i\\ & & & \end{array}\right].....\left(7\right)$

Polynomial multiplication:

Question now been written in accordance with the information provided.

$A\left(x\right)=a_0+a_{1}x+....+a_d{x}^d.....\left(8\right)$

The first polynomial is x + 1 …… (9)

Similarity equations (8) and (9),

$a_0=1,a_1=1,a_2=0\mathrm{and}{a}_3=0.....\left(10\right)$

Considering the polynomials into matrix transformation formula..

localid="1659009567989" $A=\left[\begin{array}{c}{a}_0\\ a_1\\ a_2\\ a_3\\ \end{array}\right]$ …… (11)

2^nd part of the above values of $a_0,a_1,a_2,a_3$ in Equation (11).

$A=\left[\begin{array}{c}\begin{array}{c}1\\ 1\\ 0\\ 0\end{array}\end{array}\right]...\left(12\right)$

The FFT of A ( 1, 1, 0, 0 )is calculated as follows:

FFT of $A=M_4\left(\omega \right)\times A..........\left(13\right)$

Substitute the values $M_4\left(\omega \right)$from Equation (7) and A from Equation (12) in Equation (13).

$=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& i& -1& -i\\ 1& -1& 1& -1\\ 1& -i& -1& i\end{array}\right]*\left[\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right]$

$$\begin{gathered} =\left[\begin{array}{c}1+1+0-0\\ 1+\mathrm{i}+0+0\\ 1-1+0+0\\ 1-\mathrm{i}+0+0\end{array}\right] \\ \mathrm{FFT}\mathrm{of}\mathrm{A}=\left[\begin{array}{c}2\\ \mathrm{i}+1\\ 0\\ \mathrm{i}-1\end{array}\right]....\left(14\right) \end{gathered}$$

The 2^nd polynomial is $x^2+1$ …… (15)

equal equations (8) and (15)

$$\begin{gathered} a_0=1 \\ {a}_1=0 \\ {a}_2=1........\left(16\right) \\ {a}_3=0 \end{gathered}$$

Take a look there at formula on converting a polynomial to something like a matrix..

localid="1659011072851" $B=\left[\begin{array}{c}{a}_0\\ a_1\\ a_2\\ a_3\\ \end{array}\right]$ …… (17)

Alternative the above values of $a_0,a_1,a_2,a_3$in Equation (17).

$B=\left[\begin{array}{c}1\\ 0\\ 1\\ 0\end{array}\right]$ …… (18)

The FFT of B ( 1,0,1,0) is calculated as follows:

$\mathrm{FFT}ofB=M_4\times B$…… (19)

Within Equations (7), replace all values of Equation (18) with M₄(w) the values from Equation (7). (19).

localid="1659067306314" $$\begin{gathered} \mathrm{The}\mathrm{FFT}\mathrm{of}B=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& i& -1& -i\\ 1& -1& 1& -1\\ 1& -i& -1& i\end{array}\right]\times \left[\begin{array}{c}1\\ 0\\ 1\\ 0\end{array}\right] \\ =\left[\begin{array}{c}1+0+1+0\\ 1+0-1+0\\ 1+0+1+0\\ 1+0+1+0\end{array}\right] \\ \mathrm{FFT}\mathrm{of}\mathrm{B}=\left[\begin{array}{c}2\\ 0\\ 2\\ 0\end{array}\right]............\left(20\right) \end{gathered}$$

This polynomial's combination is. X+1and x² +1 is

Product = (X+1) * (x² +1)

= x³ + x + x² +1

= 1 + x + x²+ x³ …… (21)

Let the product of FFT of A and B be P. The product is calculated as shown below:

P = A * B …… (22)

,

Substitute the value of “ A” from Equation (14) and “B” from Equation (20) in Equation (22).

$$\begin{gathered} P=\left[\begin{array}{c}2\\ i+1\\ 0\\ i-1\end{array}\right]*\left[\begin{array}{c}2\\ 0\\ 2\\ 0\end{array}\right] \\ =\left[\begin{array}{c}4\\ 0\\ 0\\ 0\end{array}\right]\dots \dots \left(23\right) \end{gathered}$$

Inverse FFT:

Use the inverse FFT, which equals Inverse FFT, to get the final result. $FFT=\frac{1}{n}$ $\mathrm{Mn}\left({\mathrm{w}}^{-1}\right)$ …… (24)

Here, from Equation (3), the value of $\omega =i$Thus, the value of ${\omega }^{-1}$is:

$$\begin{gathered} {\omega }^{-1}={\left(i\right)}^{-1}={\left[\cos \frac{\mathrm{\pi }}{2}+i\sin \frac{\mathrm{\pi }}{2}\right]}^{-1} \\ =\cos \left(-\frac{\mathrm{\pi }}{2}\right)+i\sin \left(-\frac{\mathrm{\pi }}{2}\right) \\ =\cos \left(\frac{\mathrm{\pi }}{2}\right)-i\sin \left(\frac{\mathrm{\pi }}{2}\right) \\ =0-i\left(1\right) \\ {\omega }^{-1}=-i..........\left(25\right) \end{gathered}$$

To get the value of $M_4\left({\omega }^{-1}\right)$, substitute i =-iin Equation (7).

localid="1659067624148" $M_4\left({\omega }^{-1}\right)=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& -i& -1& i\\ 1& -1& 1& -1\\ 1& i& -1& -i\end{array}\right]$…… (26)

The inverse FFT of P is calculated as shown below:

$\mathrm{Inverse}\mathrm{FFT}\left(P\right)=\frac{1}{4}P{M}_n\left({\omega }^{-1}\right)$…… (27)

Substitute the value of $M_4\left({\omega }^{-1}\right)$from Equation (26), P from Equation (23) in Equation (27).

role="math" localid="1659067795192" $$\begin{gathered} \mathrm{Inverse}\mathrm{FFT}\left(P\right)=\frac{1}{4}\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& -i& -1& i\\ 1& -1& 1& -1\\ 1& i& -1& -i\end{array}\right]\times \left[\begin{array}{c}4\\ 0\\ 0\\ 0\end{array}\right] \\ =\frac{1}{4}\left[\begin{array}{c}4\\ 4\\ 4\\ 4\end{array}\right] \\ \mathrm{Inverse}\mathrm{FFT}\left(P\right)=\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]........\left(28\right) \end{gathered}$$

Formula (28)'s polynomial reflection of all the above matrix seems to be $1+x+x^2+x^3$.

As a result, this polynomial's composition is $1=x+x^2+x^3$and its FFT is (4,0,0,0) .

Solution of part (b)

The first polynomial is $1+x+2x^2$ …… (29)

Compare equations (8) and (29)

a₀= 1

a₁= 1

a₂= 2

a₃= 0 …… (30)

Consider the formula of polynomial to matrix transformation.

$A=\left[\begin{array}{c}{a}_0\\ a_1\\ a_2\\ a_3\end{array}\right]$…… (31)

,

Substitute the above values of $a_0,a_1,a_2,a_3$in Equation (31).

$A=\left[\begin{array}{c}1\\ 1\\ 2\\ 0\end{array}\right]$…… (32)

The FFT of A $(1,1,2,0)$is calculated as follows:

$\mathrm{FFT}\mathrm{of}A=M_4\left(\omega \right)\times A............\left(33\right)$

Substitute the values $M_4\left(\omega \right)$ from Equation (7) andA from Equation (32) in Equation (33).

$$\begin{gathered} \mathrm{FFT}\mathrm{of}A=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& i& -1& -i\\ 1& -1& 1& -1\\ 1& -i& -1& i\end{array}\right]\times \left[\begin{array}{c}1\\ 1\\ 2\\ 0\end{array}\right] \\ =\left[\begin{array}{c}1+1+2+0\\ 1+i-2+0\\ 1-1+2+0\\ 1-i-2+0\end{array}\right] \\ \mathrm{FFT}\mathrm{of}A=\left[\begin{array}{c}4\\ i-1\\ 2\\ -i-1\end{array}\right]....\left(34\right) \end{gathered}$$

The second polynomial is 2+3x…… (35)

Compare equations (8) and (35)

localid="1659069567337" $$\begin{gathered} a_0=2 \\ {a}_1=3 \\ {a}_2=0 \\ {a}_3=0 \end{gathered}$$…… (36)

Consider the formula of polynomial to matrix transformation.

$B=\left[\begin{array}{c}{a}_0\\ a_1\\ a_2\\ a_3\end{array}\right]$……(37)

Substitute the above values of $a_0,a_1,a_2,a_3$in Equation (37).

$B=\left[\begin{array}{c}2\\ 3\\ 0\\ 0\end{array}\right]$ .........(38)

The FFT of B ( 2, 3, 0, 0 ) is calculated as follows:

$\mathrm{FFT}\mathrm{of}B=M_4\left(\omega \right)\times B$…… (39)

Substitute the values $M_4\left(\omega \right)$from Equation (7) and B from Equation (38) in Equation (39).

localid="1659070329001" $$\begin{gathered} \mathrm{FFT}\mathrm{of}B=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& i& -1& -i\\ 1& -1& 1& -1\\ 1& -i& -1& i\end{array}\right]\times \left[\begin{array}{c}2\\ 3\\ 0\\ 0\end{array}\right] \\ =\left[\begin{array}{c}2+3+0+0\\ 2+3i+0+0\\ 2-3+0+0\\ 2-3i+0+0\end{array}\right] \\ \mathrm{FFT}\mathrm{of}B=\left[\begin{array}{c}5\\ 2+3i\\ -1\\ 2-3i\end{array}\right] \end{gathered}$$

The product of the polynomial is $1+x+x^2$and $2+3x$is

$$\begin{gathered} Product=(1+x+2x^2)\times (2+3x) \\ =2+3x+2x+3x^2+4x^2+6x^3 \\ =2+5x+7x^2+6x^3......\left(41\right) \end{gathered}$$

,

Let the product of FFT of A and FFT of B be P. The product is calculated as shown below:

$\mathrm{P}=\mathrm{FFT}\mathrm{of}\mathrm{A}\times \mathrm{FFT}\mathrm{of}\mathrm{B}$…… (42)

Substitute the values of FFT of “A” from Equation (34) and FFT of “B” from Equation (40) in Equation (42).

$$\begin{gathered} P=\left[\begin{array}{c}4\\ i-1\\ 2\\ -i-1\\ \end{array}\right]\times \left[\begin{array}{c}5\\ 2+3i\\ -1\\ 2-3i\\ \end{array}\right] \\ =\left[\begin{array}{c}20\\ 2+3i^2+-2-3i\\ -2\\ -2i-3i^2-2-3i\\ \end{array}\right] \\ =\left[\begin{array}{c}20\\ -2-i-3\\ -2\\ -2+i-3\\ \end{array}\right] \\ =\left[\begin{array}{c}20\\ -5-i\\ -2\\ -5+i\\ \end{array}\right] \end{gathered}$$

The inverse FFT of P is calculated as shown below:

Inverse FFT(P) $\frac{1}{4}P{M}_n\left({\omega }^{-1}\right)$ …… (44)

Substitute the value of $M_4\left({\omega }^{-1}\right)$from Equation (26), P from Equation (43) in Equation (44).

Inverse of FFT (P) role="math" localid="1659073083704" $$\begin{gathered} \mathrm{Inverse}\mathrm{FFT}\left(P\right)=\frac{1}{4}\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& -i& -1& i\\ 1& -1& 1& -1\\ 1& i& -1& -i\\ & & & \end{array}\right]\times \left[\begin{array}{c}20\\ -5-i\\ -2\\ -5+i\\ \end{array}\right] \\ =\frac{1}{4}\left[\begin{array}{c}20-5-i-2-5-i\\ 20-i(-5-i)-2-i(-5+i)\\ 20-(-5-i)-2-1(-5+i)\\ 20+i(-5-i)-(-2)-i(-5+i)\\ \end{array}\right] \\ =\frac{1}{4}\left[\begin{array}{c}8\\ 20\\ 28\\ 24\\ \end{array}\right] \\ \mathrm{Inverse}\mathrm{FFT}\left(P\right)=\left[\begin{array}{c}2\\ 5\\ 7\\ 6\\ \end{array}\right].....\left(45\right) \end{gathered}$$

The polynomial representation of the above matrix from Equation (45) is

$2+5x+7x^2+6x^3$.

Therefore, the product of the polynomial is $2+5x+7x^2+6x^3$and its FFT is

$(20,-5-i,-2,-5+i)$.