Question

Practice with the fast Fourier transform.

(a) What is the FFT of (1,0,0,0)? What is the appropriate value of $\mathit{\omega }$in this case? And of which sequence is (1,0,0,0)the FFT?

(b)Repeat for (1,0,1,-1).

Short answer

Part (a)

FTT of (1,0,0,0) is: (1,1,1,1)

Approximate value of $\omega$is: i

Sequence is:$\left(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4}\right)$

Part (b)

FTT of (1,0,1,-1) is:(1,i,3,-i)

Step-by-step solution

Solution of part (a)

Fast Fourier Transform (FFT) of $\left(1,0,0,0\right)$& the numbers of $\omega \text{'}$:

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

${\mathrm{M}}_4\left(\mathrm{\omega }\text{'}\right)=\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& \mathrm{\omega }& {\mathrm{\omega }}^2& {\mathrm{\omega }}^3\\ 1& {\mathrm{\omega }}^2& {\mathrm{\omega }}^4& {\mathrm{\omega }}^6\\ 1& {\mathrm{\omega }}^3& {\mathrm{\omega }}^6& {\mathrm{\omega }}^9\end{array}\right)$ …… (1)

The nth root of unity's complicated value $\omega$is,

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

Extra information base calculation value “4” for “n” in the Equation (2). Thus, the value of $\omega$is,

$\omega \text{'}=e^{\frac{2\pi i}{n}}$

$=e^{\frac{\pi i}{2}}$

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

Thus, $e^{\frac{\pi i}{2}}$has been written as given details:

localid="1658923197401" $$\begin{gathered} \omega =\cos \left(\frac{\pi }{2}\right)+i\sin \left(\frac{\pi }{2}\right) \\ =\cos \left(90\right)+i\sin \left(90\right)\dots \dots \left(3\right) \end{gathered}$$

$$\begin{gathered} =0+i\left(1\right) \\ \omega =i \end{gathered}$$

Alternative calculation of Equation (3) in Equation (1),

$$\begin{gathered} M_4\left(\omega \text{'}\right)=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& i& i^2& i^3\\ 1& i^2& i^4& i^6\\ 1& i^3& i^6& i^9\end{array}\right]......\left(4\right) \\ \mathrm{In}\mathrm{general},\mathrm{the}\mathrm{value}\mathrm{of}\mathrm{i},\begin{array}{ccc}{\mathrm{i}}^2& {\mathrm{i}}^3& {\mathrm{i}}^4\end{array}\mathrm{are}, \\ \mathrm{i}=\mathrm{i} \\ {\mathrm{i}}^2=-1 \\ {\mathrm{i}}^3=-\mathrm{i} \\ {\mathrm{i}}^4=1......\left(5\right) \\ \mathrm{The}\mathrm{calculation}\mathrm{value}\mathrm{of}\begin{array}{cc}{\mathrm{i}}^6,& {\mathrm{i}}^9\end{array}\mathrm{is}, \\ {\mathrm{i}}^6={\mathrm{i}}^4\times {\mathrm{i}}^2=-1 \\ {\mathrm{i}}^9={\mathrm{i}}^6\times {\mathrm{i}}^3=\mathrm{i}......\left(6\right) \\ \mathrm{Alternative}\mathrm{calculation}\mathrm{values}\mathrm{are}i,i^2,i^3,i^4,i^6,i^9\mathrm{in}\mathrm{Equation}\left(4\right).\mathrm{The}\mathrm{FFT}\mathrm{matrix}\mathrm{is}, \end{gathered}$$

$$\begin{gathered} 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) \\ \mathrm{Let}\mathrm{the}\mathrm{given}\mathrm{matrix}\mathrm{be} \\ \mathrm{A}=\left[\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right]......\left(8\right) \end{gathered}$$

The FFT of A is,

The FFT of $\left(1,0,0,0\right)=M_4\left(\omega \text{'}\right)\times A......\left(9\right)$ …… (9)

Alternative of calculation related value of “A” matrix and $M_4\left(\omega \right)$in Equation (9),

$$\begin{gathered} =\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\\ 0\\ 0\end{array}\right] \\ =\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right] \end{gathered}$$

As a result of Calculation (3), the correct value of$\omega =i$and the FFT of (1,0,0,0) is (1,1,1,1).

Progression of FFT it is priceless$\left(1,0,0,0\right)$:

Apply the inverted FFT, which equals to determine the FFT sequence,

Inverse FFT$=\frac{1}{n}{M}_n\left({\omega }^{-1}\right)$…… (10)

Here, from Equation (3), the value of . Thus, the value of is:

role="math" localid="1658981947890" $$\begin{gathered} ={\left[\cos \frac{\pi }{2}+i\sin \frac{\pi }{2}\right]}^{-1} \\ =\cos \left(-\frac{\pi }{2}\right)+i\sin \left(\frac{\pi }{2}\right) \\ =\cos \left(\frac{\pi }{2}\right)-i\sin \left(\frac{\pi }{2}\right) \\ {\omega }^{-1}=-i\dots \dots \left(11\right) \end{gathered}$$

Accepting the value of role="math" localid="1658982023034" $M_4\left({\omega }^{-2}\right)$substitute i=-i in Equation (4)

$M_4\left({\omega }^{-2}\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(12\right)$

Now let us say the matrix is

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

So, there is inverse FFT (B) is,

The inverse FFT (B)$=\frac{1}{4}B{M}_n\left({\omega }^{-1}\right)$ …… (14)

Substitute the value of “B” matrix and $M_n\left({\omega }^{-1}\right)$in Equation (14),

$$\begin{gathered} =\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}1\\ 0\\ 0\\ 0\end{array}\right] \\ =\frac{1}{4}\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right] \end{gathered}$$

Therefore, the sequence of FFT that has the$\left(1,0,0,0\right)\mathrm{is}\left(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4}\right)$

Solution of part (b)

Fast Fourier Transform (FFT) of ( 1,0,1,-1 ) :

Let the given matrix be,

$C=\left[\begin{array}{c}1\\ 0\\ 1\\ -1\end{array}\right]......\left(15\right)$

The FFT of ( 1,0,10-1 ) is,

The FFT of $\left(1,0,1,-1\right)=C{M}_n\left({\omega }^{-1}\right)$ …… (16)

Substitute the value of “C” matrix and $M_n\left({\omega }^{-1}\right)$in Equation (16),

$$\begin{gathered} =\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\\ -1\end{array}\right] \\ =\left[\begin{array}{cccc}1+& 0+& 1-& 1\\ 1+& 0-& 1+& i\\ 1+& 0+& 1+& 1\\ 1+& 0-& 1-& i\end{array}\right] \\ =\left[\begin{array}{c}1\\ i\\ 3\\ -1\end{array}\right] \end{gathered}$$

Therefore, the FFT of $\left(1,0,1,-1\right)\mathrm{is}\left(1,i,3,-i\right)$is .