91影视

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

The $4脳4$matrix of FFT is,

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

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

localid="1658922894437" $蝇\text{'}=e^{\frac{2蟺i}{n}}$ 鈥︹�� (2)

Extra information base calculation value 鈥�4鈥� for 鈥渘鈥� in the Equation (2). Thus, the value of $蝇$is,

$蝇\text{'}=e^{\frac{2蟺i}{n}}$

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

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

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

localid="1658923197401" $$\begin{gathered} 蝇=\cos \left(\frac{蟺}{2}\right)+i\sin \left(\frac{蟺}{2}\right) \\ =\cos \left(90\right)+i\sin \left(90\right)鈥�鈥�\left(3\right) \end{gathered}$$

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

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

$$\begin{gathered} M_4\left(蝇\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脳{\mathrm{i}}^2=-1 \\ {\mathrm{i}}^9={\mathrm{i}}^6脳{\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(蝇\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(蝇\text{'}\right)脳A......\left(9\right)$ 鈥︹�� (9)

Alternative of calculation related value of 鈥淎鈥� matrix and $M_4\left(蝇\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]脳\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$蝇=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({蝇}^{-1}\right)$鈥︹�� (10)

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

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

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

$M_4\left({蝇}^{-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]鈥�鈥�\left(13\right)$ 鈥︹�� (13)

So, there is inverse FFT (B) is,

The inverse FFT (B)$=\frac{1}{4}B{M}_n\left({蝇}^{-1}\right)$ 鈥︹�� (14)

Substitute the value of 鈥淏鈥� matrix and $M_n\left({蝇}^{-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]脳\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)$

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({蝇}^{-1}\right)$ 鈥︹�� (16)

Substitute the value of 鈥淐鈥� matrix and $M_n\left({蝇}^{-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]脳\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 .