Question

This problem illustrates how to do the Fourier Transform (FT) in modular arithmetic, for example, modulo .(a) There is a number such that all the powers $\mathit{\omega }\mathbf{,}{\mathit{\omega }}^{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathit{\omega }}^{\mathbf{6}}$ are distinct (modulo ). Find this role="math" localid="1659339882657" $\mathit{\omega }$, and show that $\mathit{\omega }\mathbf{+}{\mathit{\omega }}^{\mathbf{2}}\mathbf{+}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{+}{\mathit{\omega }}^{\mathbf{6}}\mathbf{=}\mathbf{0}$. (Interestingly, for any prime modulus there is such a number.)

(b) Using the matrix form of the FT, produce the transform of the sequence $\mathbf{(}\mathbf{0}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{}\mathbf{5}\mathbf{,}\mathbf{2}\mathbf{)}\mathbf{}\mathbf{}$ modulo 7; that is, multiply this vector by the matrix ${\mathit{M}}_{\mathbf{6}}\mathbf{\left(}\mathit{\omega }\mathbf{\right)}$, for the value of $\mathit{\omega }$you found earlier. In the matrix multiplication, all calculations should be performed modulo 7.

(c) Write down the matrix necessary to perform the inverse FT. Show that multiplying by this matrix returns the original sequence. (Again all arithmetic should be performed modulo 7.)

(d) Now show how to multiply the polynomials and using the FT modulo 7.

Short answer

1. $\omega =3$
2. Transformation of the sequence $(0,1,1,1,5,2)is(3,6,4,2,3,3).$ .
3. Transformation of the sequence $(3,6,4,2,3,3)is(0,1,1,1,5,2).$ .
4. Transformation of the sequence $(3,6,4,2,3,3)is(-1,1,1,3,1,1).$.

Step-by-step solution

Solution of part (a) and (b)  

a.)

Find the value of $\omega$:

On observing, the value of $\omega =3$ ……

The powers of w are distinct modulo:

Value of ${\omega }^2$:

• Substitute $\omega =3$ in localid="1659340352169" ${\omega }^2$and take modulo .

$$\begin{gathered} {\omega }^2=3^{2}mod7 \\ =9mod7 \\ =2 \end{gathered}$$

Value of ${\omega }^3$:

• Substitute $\omega =3in{\omega }^3$ and take modulo .

$$\begin{gathered} {\omega }^3=27mod7 \\ =6 \end{gathered}$$

Value of ${\omega }^4$:

• Substitute $\omega =3in{\omega }^4$ and take modulo .

localid="1659340501146" $$\begin{gathered} {\omega }^4=3^{4}mod7 \\ =81mod7 \\ =4 \end{gathered}$$

Value of ${\omega }^5$:

• Substitute $\omega =3in{\omega }^5$ and take modulo .

$$\begin{gathered} {\omega }^5=3^{5}mod7 \\ =243mod7 \\ =5 \end{gathered}$$

Value of ${\omega }^6$:

• Substitute $\omega =3in{\omega }^6$ and take modulo .

$$\begin{gathered} {\omega }^6=3^{6}mod7 \\ =729mod7 \\ =1 \end{gathered}$$

The values of $(\omega =3,{\omega }^2=2,{\omega }^3=6,{\omega }^4=4,{\omega }^5=5,{\omega }^6=1)$ are distinct.

To show $\omega +{\omega }^2+{\omega }^3+{\omega }^4+{\omega }^5+{\omega }^6=0$ :

• Substitute the values $(\omega =3,{\omega }^2=2,{\omega }^3=6,{\omega }^4=4,{\omega }^5=5,{\omega }^6=1)$and take modulo in following:

$\omega +{\omega }^2+{\omega }^3+{\omega }^4+{\omega }^5+{\omega }^6\dots \dots \left(2\right)$

Thus,

$$\begin{gathered} (\omega +{\omega }^2+{\omega }^3+{\omega }^4+{\omega }^5+{\omega }^6)mod7 \\ =(3+2+6+4+5+1)mod7=21mod7 \\ =0 \end{gathered}$$

Therefore, $\omega +{\omega }^2+{\omega }^3+{\omega }^4+{\omega }^5+{\omega }^6=0$

Solution of part   (b).  

b.)

Coefficient representation of $6\times 6$matrix of FFT (Fast Fourier Transform)$M_6\left(\omega \right)$ ,is shown below:

$M_6\left(\omega \right)=\left[\begin{array}{cccccc}1& 1& 1& 1& 1& 1\\ 1& \omega & {\omega }_2& {\omega }_3& {\omega }_4& {\omega }_5\\ 1& {\omega }_2& {\omega }_4& {\omega }_6& {\omega }_8& {\omega }_{10}\\ 1& {\omega }_3& {\omega }_6& {\omega }_9& {\omega }_{12}& {\omega }_{15}\\ 1& {\omega }_4& {\omega }_8& {\omega }_{12}& {\omega }_{16}& {\omega }_{20}\\ 1& {\omega }_5& {\omega }_{10}& {\omega }_{15}& {\omega }_{20}& {\omega }_{25}\end{array}\right]$ (3).....

From section (a) the value of powers of are obtained as:

$\omega =3,{\omega }^2=2,{\omega }^3=6,{\omega }^4=4,{\omega }^5=5,{\omega }^6=1$ (4) ……

The value of is,

$$\begin{gathered} {\omega }^8=3^8=6561mod7=2 \\ {\omega }^9=3^9=19683mod7=6 \\ {\omega }^{1}0=3^{1}0=59049mod7=4 \\ {\omega }^{1}2=3^{1}2=531441mod7=1 \\ {\omega }^{1}5=3^{1}5=14348907mod7=6 \\ {\omega }^{1}6=3^{1}6=143046721mod7=4 \\ {\omega }^{2}0=3^{2}0=3486784401mod7=2 \\ {\omega }^{2}5=3^{2}5=84728809443mod7=3 \end{gathered}$$ …… (5)

Substitute the powers of w from equation (4) and equation (5) in equation (3).

localid="1659341811588" $M_6\left(\omega \right)=\left[\begin{array}{cccccc}1& 1& 1& 1& 1& 1\\ 1& 3& 2& 6& 4& 5\\ 1& 2& 4& 1& 2& 4\\ 1& 6& 1& 6& 1& 6\\ 1& 4& 2& 1& 4& 2\\ 1& 5& 4& 6& 2& 3\end{array}\right]$. (6)....

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

FFT of $A=M_6\left(\omega \right)\times A$ …… (7)

Substitute the values $M_6\left(\omega \right)$from Equation (6) and A as $(0,1,1,1,5,2)$ in Equation .

Multiplying the sequence $(0,1,1,1,5,2)$ with equation (6) .

localid="1659341818991" $FFTofA=\left[\begin{array}{cccccc}1& 1& 1& 1& 1& 1\\ 1& 3& 2& 6& 4& 5\\ 1& 2& 4& 1& 2& 4\\ 1& 6& 1& 6& 1& 6\\ 1& 4& 2& 1& 4& 2\\ 1& 5& 4& 6& 2& 3\end{array}\right]$

$=\left[\begin{array}{cccccc}\left(1\times 0\right)& \left(1\times 1\right)& \left(1\times 1\right)& \left(1\times 1\right)& \left(1\times 5\right)& \left(1\times 2\right)\\ \left(1\times 0\right)& \left(3\times 0\right)& \left(2\times 1\right)& \left(6\times 1\right)& \left(4\times 5\right)& \left(5\times 2\right)\\ \left(1\times 0\right)& \left(2\times 1\right)& \left(4\times 1\right)& \left(1\times 1\right)& \left(2\times 5\right)& \left(4\times 2\right)\\ \left(1\times 0\right)& \left(6\times 1\right)& \left(1\times 1\right)& \left(6\times 1\right)& \left(1\times 5\right)& \left(6\times 2\right)\\ \left(1\times 0\right)& \left(4\times 1\right)& \left(2\times 1\right)& \left(1\times 1\right)& \left(4\times 5\right)& \left(2\times 2\right)\\ \left(1\times 0\right)& \left(5\times 1\right)& \left(4\times 1\right)& \left(6\times 1\right)& \left(2\times 5\right)& \left(3\times 2\right)\end{array}\right]$

$=\left[\begin{array}{c}10\\ 41\\ 25\\ 30\\ 31\\ 31\end{array}\right]$...... (8)

Taking modulo for equation .

$\left[\begin{array}{c}10mod7\\ 14mod7\\ 25mod7\\ 30mod7\\ 32mod7\\ 31mod7\end{array}\right]=\left[\begin{array}{c}3\\ 6\\ 4\\ 2\\ 3\\ 3\end{array}\right]$

Therefore, the transformation of the sequence $(0,1,1,1,5,2)is(3,6,4,2,3,3)$

Solution of part (c).  

c.)

Inverse FFT of $(3,6,4,2,3,3):$:

Let $P=(3,6,4,2,3,3)$ …… (9)

Coefficient representation of $M_6({\omega }^{(}-1))$ is shown below:

Inverse $FFT\left(P\right)=\frac{1}{6}P{M}_6\left({\omega }^{-1}\right)$…… (10)

To represent the matrix form for the inverse FFT with modulo first find the modular inverse. Modular inverse of,

$$\begin{gathered} 1mod7=1 \\ 2mod7=4 \\ 3mod7=5 \\ 4mod7=2 \\ 5mod7=3 \\ 6mod7=6\dots \dots \left(11\right) \end{gathered}$$

To get localid="1659345943519" $M_6\left({\omega }^{-1}\right)$, substitute the inverse of each values. Thus,

localid="1659346430928" $M_6\left({\omega }^{-1}\right)=\left[\begin{array}{cccccc}\frac{1}{1}& \frac{1}{1}& \frac{1}{1}& \frac{1}{1}& \frac{1}{1}& \frac{1}{1}\\ \frac{1}{1}& \frac{1}{5}& \frac{1}{4}& \frac{1}{6}& \frac{1}{2}& \frac{1}{3}\\ \frac{1}{1}& \frac{1}{4}& \frac{1}{2}& \frac{1}{1}& \frac{1}{4}& \frac{1}{2}\\ \frac{1}{1}& \frac{1}{6}& \frac{1}{1}& \frac{1}{6}& \frac{1}{1}& \frac{1}{6}\\ \frac{1}{1}& \frac{1}{2}& \frac{1}{4}& \frac{1}{1}& \frac{1}{2}& \frac{1}{4}\\ \frac{1}{1}& \frac{1}{3}& \frac{1}{2}& \frac{1}{6}& \frac{1}{4}& \frac{1}{5}\end{array}\right]$ …

Substitute equation (9), equation (12) in equation (10).

localid="1659346499692" $InverseFTT\left(P\right)=1/6\left[\begin{array}{cccccc}\frac{1}{1}& \frac{1}{1}& \frac{1}{1}& \frac{1}{1}& \frac{1}{1}& \frac{1}{1}\\ \frac{1}{1}& \frac{1}{5}& \frac{1}{4}& \frac{1}{6}& \frac{1}{2}& \frac{1}{3}\\ \frac{1}{1}& \frac{1}{4}& \frac{1}{2}& \frac{1}{1}& \frac{1}{4}& \frac{1}{2}\\ \frac{1}{1}& \frac{1}{6}& \frac{1}{1}& \frac{1}{6}& \frac{1}{1}& \frac{1}{6}\\ \frac{1}{1}& \frac{1}{2}& \frac{1}{4}& \frac{1}{1}& \frac{1}{2}& \frac{1}{4}\\ \frac{1}{1}& \frac{1}{3}& \frac{1}{2}& \frac{1}{6}& \frac{1}{4}& \frac{1}{5}\end{array}\right]\times \left[\begin{array}{c}3\\ 6\\ 4\\ 2\\ 3\\ 3\end{array}\right]$……

Thus, substitute the arithmetic value for the arithmetic value $\frac{1}{1}$, for the arithmetic value $1,\frac{1}{2}$, for the arithmetic value $5,\frac{1}{4}$, for the arithmetic value $2,\frac{1}{5}$, for the arithmetic value 3 and $\frac{1}{6}$ for the arithmetic value 6 from equation (11) in equation (13) to find the inverse.

$InverseFTT\left(P\right)=1/6\left[\begin{array}{cccccc}\frac{1}{1}& \frac{1}{1}& \frac{1}{1}& \frac{1}{1}& \frac{1}{1}& \frac{1}{1}\\ \frac{1}{1}& \frac{1}{5}& \frac{1}{4}& \frac{1}{6}& \frac{1}{2}& \frac{1}{3}\\ \frac{1}{1}& \frac{1}{4}& \frac{1}{2}& \frac{1}{1}& \frac{1}{4}& \frac{1}{2}\\ \frac{1}{1}& \frac{1}{6}& \frac{1}{1}& \frac{1}{6}& \frac{1}{1}& \frac{1}{6}\\ \frac{1}{1}& \frac{1}{2}& \frac{1}{4}& \frac{1}{1}& \frac{1}{2}& \frac{1}{4}\\ \frac{1}{1}& \frac{1}{3}& \frac{1}{2}& \frac{1}{6}& \frac{1}{4}& \frac{1}{5}\end{array}\right]\times \left[\begin{array}{c}3\\ 6\\ 4\\ 2\\ 3\\ 3\end{array}\right]$

$$\begin{gathered} =6\times \left[\begin{array}{cccccc}\left(1\times 3\right)& \left(1\times 6\right)& \left(1\times 4\right)& \left(1\times 2\right)& \left(1\times 3\right)& \left(1\times 3\right)\\ \left(1\times 3\right)& \left(5\times 6\right)& \left(4\times 4\right)& \left(6\times 2\right)& \left(2\times 3\right)& \left(3\times 3\right)\\ \left(1\times 3\right)& \left(4\times 6\right)& \left(2\times 4\right)& \left(1\times 2\right)& \left(4\times 3\right)& \left(2\times 3\right)\\ \left(1\times 3\right)& \left(6\times 6\right)& \left(1\times 4\right)& \left(6\times 2\right)& \left(1\times 3\right)& \left(6\times 3\right)\\ \left(1\times 3\right)& \left(2\times 6\right)& \left(4\times 4\right)& \left(1\times 2\right)& \left(2\times 3\right)& \left(4\times 3\right)\\ \left(1\times 3\right)& \left(3\times 6\right)& \left(2\times 4\right)& \left(6\times 2\right)& \left(4\times 3\right)& \left(5\times 3\right)\end{array}\right] \\ =6\times \left[\begin{array}{c}21\\ 76\\ 55\\ 76\\ 51\\ 68\end{array}\right] \\ =\left[\begin{array}{c}126\\ 456\\ 330\\ 456\\ 306\\ 408\end{array}\right] \end{gathered}$$ …… (14)

Taking modulo 7 for equation ( 14 ).

$=\left[\begin{array}{cc}126& mod7\\ 456& mod7\\ 330& mod7\\ 446& mod7\\ 306& mod7\\ 408& mod7\end{array}\right]=\left[\begin{array}{c}0\\ 1\\ 1\\ 1\\ 5\\ 2\end{array}\right]$

Therefore, the transformation of the sequence $(3,6,4,2,3,3)is(0,1,1,1,5,2).$.

Solution of part (d).  

d.)

The standard form for degree-d polynomial is

$A\left(x\right)=a_0+a_{1}x+\cdots +a_d{x}^d\dots \dots \left(15\right)$

The first polynomial is $x^2+x+1\dots \dots \left(16\right)$

Compare equation (15) and (16) equation

$$\begin{gathered} a_0=1 \\ {a}_1=1 \\ {a}_2=1 \\ {a}_3=0 \\ {a}_4=0 \\ {a}_5=0\dots \dots \left(17\right) \end{gathered}$$

Consider the formula of polynomial to matrix transformation.

localid="1659427656504" $\left[\begin{array}{c}{a}_0\\ a_1\\ a_2\\ a_3\\ a_4\\ a_5\end{array}\right]$ ……

Substitute the values of $a_0,a_1,a_2,a_3,a_4,a_5$ in Equation (18)

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

Find FFT of $(1,1,1,0,0,0):$:

Substitute the values $M_6\left(\omega \right)$ from Equation (6) and A from Equation (19) in Equation (7) .

localid="1659418277264" $$\begin{gathered} FFTofA=\left[\begin{array}{cccccc}1& 1& 1& 1& 1& 1\\ 1& 3& 2& 6& 4& 5\\ 1& 2& 4& 1& 2& 4\\ 1& 6& 1& 6& 1& 6\\ 1& 4& 2& 1& 4& 2\\ 1& 5& 4& 6& 2& 3\end{array}\right]\times \left[\begin{array}{c}1\\ 1\\ 1\\ 0\\ 0\\ 0\end{array}\right] \\ =\left[\begin{array}{cccccc}\left(1\times 1\right)+& \left(1\times 1\right)+& \left(1\times 1\right)+& \left(1\times 0\right)+& \left(1\times 0\right)+& \left(1\times 0\right)\\ \left(1\times 1\right)+& \left(3\times 1\right)+& \left(2\times 1\right)+& \left(6\times 0\right)+& \left(4\times 0\right)+& \left(5\times 0\right)\\ \left(1\times 1\right)+& \left(2\times 1\right)+& \left(4\times 1\right)+& \left(1\times 0\right)+& \left(2\times 0\right)+& \left(4\times 0\right)\\ \left(1\times 1\right)+& \left(6\times 1\right)+& \left(1\times 1\right)+& \left(6\times 0\right)+& \left(1\times 0\right)+& \left(6\times 0\right)\\ \left(1\times 1\right)+& \left(4\times 1\right)+& \left(2\times 1\right)+& \left(1\times 0\right)+& \left(4\times 0\right)+& \left(2\times 0\right)\\ \left(1\times 1\right)+& \left(5\times 1\right)+& \left(4\times 1\right)+& \left(6\times 0\right)+& \left(2\times 0\right)+& \left(3\times 0\right)\end{array}\right] \\ =\left[\begin{array}{c}3\\ 2\\ 7\\ 8\\ 7\\ 10\end{array}\right]......\left(20\right) \end{gathered}$$

Taking modulo 7 for the FFT of equation (20) .

$\left[\begin{array}{cc}3& mod7\\ 6& mod7\\ 7& mod7\\ 8& mod7\\ 7& mod7\\ 10& mod7\end{array}\right]=\left[\begin{array}{c}3\\ 6\\ 0\\ 1\\ 0\\ 3\end{array}\right]$

Therefore, the transformation of the sequence $(1,1,1,0,0,0)is(3,6,0,1,0,3)$

The second polynomial is $x^3+2x-1$……

Compare equations (21) and equation (15)

$$\begin{gathered} a_0=-1 \\ {a}_1=2 \\ {a}_2=0 \\ {a}_3=1 \\ {a}_4=0 \\ {a}_5=0\dots \dots \left(22\right) \end{gathered}$$

The value of is so take modulo as shown below:

$-1mod7=6\dots \dots \left(23\right)$

Thus,$a_0=-1$ substitute $a_0$ as 6 in equations (22)

$\begin{array}{c}{a}_{0=6}\\ a_1=2\\ a_2=0\\ a_3=1\\ a_4=0\\ a_5=0\end{array}$

Consider the formula of polynomial to matrix transformation.

$B=\left[\begin{array}{c}{a}_0\\ a_1\\ a_2\\ a_3\\ a_4\\ a_5\end{array}\right].....\left(24\right)$

Substitute the values of $a_0,a_1,a_2,a_3,a_4,a_5$ in Equation (24) .

$B=\left[\begin{array}{c}6\\ 2\\ 0\\ 1\\ 0\\ 0\end{array}\right].....\left(25\right)$

Find FFT of $(6,2,0,1,0,0)$:

Substitute the values $M_6\left(\omega \right)$from Equation (6) and B from Equation (25) in Equation (7) .

$$\begin{gathered} FFTofB=\left[\begin{array}{cccccc}1& 1& 1& 1& 1& 1\\ 1& 3& 2& 6& 4& 5\\ 1& 2& 4& 1& 2& 4\\ 1& 6& 1& 6& 1& 6\\ 1& 4& 2& 1& 4& 2\\ 1& 5& 4& 6& 2& 3\end{array}\right]\times \left[\begin{array}{c}6\\ 2\\ 0\\ 1\\ 0\\ 0\end{array}\right] \\ =\left[\begin{array}{cccccc}\left(1\times 6\right)& \left(1\times 2\right)& \left(1\times 0\right)& \left(1\times 1\right)& \left(1\times 0\right)& \left(1\times 0\right)\\ \left(1\times 6\right)& \left(3\times 2\right)& \left(2\times 0\right)& \left(6\times 1\right)& \left(4\times 0\right)& \left(5\times 0\right)\\ \left(1\times 6\right)& \left(2\times 2\right)& \left(4\times 0\right)& \left(1\times 1\right)& \left(2\times 0\right)& \left(4\times 0\right)\\ \left(1\times 6\right)& \left(6\times 2\right)& \left(1\times 0\right)& \left(6\times 1\right)& \left(1\times 0\right)& \left(6\times 0\right)\\ \left(1\times 6\right)& \left(4\times 2\right)& \left(2\times 0\right)& \left(1\times 1\right)& \left(4\times 0\right)& \left(2\times 0\right)\\ \left(1\times 6\right)& \left(5\times 2\right)& \left(1\times 0\right)& \left(6\times 1\right)& \left(2\times 0\right)& \left(3\times 0\right)\end{array}\right] \\ =\left[\begin{array}{c}9\\ 18\\ 11\\ 24\\ 15\\ 22\end{array}\right].....\left(26\right) \end{gathered}$$

Taking modulo 7 for equation (26)

$=\left[\begin{array}{cc}9& mod7\\ 18& mod7\\ 11& mod7\\ 24& mod7\\ 15& mod7\\ 22& mod7\end{array}\right]=\left[\begin{array}{c}2\\ 4\\ 4\\ 3\\ 1\\ 1\end{array}\right]$

Therefore, the transformation of the sequence $(6,2,0,1,0,0)is(2,4,4,3,1,1)$

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

$P=A\times B\dots \dots \left(27\right)$

Substitute the value of “ A” from Equation (19) and “B ” from Equation (25) in Equation(27) .

$$\begin{gathered} P=\left[\begin{array}{c}3\\ 6\\ 0\\ 1\\ 0\\ 3\end{array}\right]\times \left[\begin{array}{c}2\\ 4\\ 4\\ 3\\ 1\\ 1\end{array}\right] \\ =\left[\begin{array}{c}6\\ 3\\ 0\\ 3\\ 0\\ 3\end{array}\right]....\left(28\right) \end{gathered}$$ ……

Modular inverse of,

$$\begin{gathered} 6mod7=6 \\ 24mod7=24 \\ 0mod7=0 \\ 3mod7=3 \\ 0mod7=0 \\ 3mod7=3....\left(29\right) \end{gathered}$$

Substitute the Equation in Equation . Thus, the product is shown below:

$P=\left[\begin{array}{c}6\\ 3\\ 0\\ 3\\ 0\\ 3\end{array}\right]....\left(30\right)$

Inverse FFT:

To get the final polynomial in coefficient representation takes the inverse FFT for the product.

Substitute equation (30) , equation (12) in equation (10) .

$InverseFTT\left(P\right)=\frac{1}{6}\left[\begin{array}{cccccc}\frac{1}{1}& \frac{1}{1}& \frac{1}{1}& \frac{1}{1}& \frac{1}{1}& \frac{1}{1}\\ \frac{1}{1}& \frac{1}{5}& \frac{1}{4}& \frac{1}{6}& \frac{1}{2}& \frac{1}{3}\\ \frac{1}{1}& \frac{1}{4}& \frac{1}{2}& \frac{1}{1}& \frac{1}{4}& \frac{1}{2}\\ \frac{1}{1}& \frac{1}{6}& \frac{1}{1}& \frac{1}{6}& \frac{1}{1}& \frac{1}{6}\\ \frac{1}{1}& \frac{1}{2}& \frac{1}{4}& \frac{1}{1}& \frac{1}{2}& \frac{1}{4}\\ \frac{1}{1}& \frac{1}{3}& \frac{1}{2}& \frac{1}{6}& \frac{1}{4}& \frac{1}{5}\end{array}\right]\times \left[\begin{array}{c}6\\ 3\\ 0\\ 3\\ 0\\ 3\end{array}\right]......\left(31\right)$

Thus, substitute the arithmetic value $\frac{1}{1}$ for the arithmetic value 1, $\frac{1}{2}$ for the arithmetic value $4,\frac{1}{3}$ for the arithmetic value $5,\frac{1}{4}$ for the arithmetic value $2,\frac{1}{5}$ for the arithmetic value 3 and $\frac{1}{6}$ for the arithmetic value 6 from equation in(11) equation (13) to find the inverse.

localid="1659426193884" $$\begin{gathered} InverseFTT\left(P\right)=6\times \left[\begin{array}{cccccc}\frac{1}{1}& \frac{1}{1}& \frac{1}{1}& \frac{1}{1}& \frac{1}{1}& \frac{1}{1}\\ \frac{1}{1}& \frac{1}{5}& \frac{1}{4}& \frac{1}{6}& \frac{1}{2}& \frac{1}{3}\\ \frac{1}{1}& \frac{1}{4}& \frac{1}{2}& \frac{1}{1}& \frac{1}{4}& \frac{1}{2}\\ \frac{1}{1}& \frac{1}{6}& \frac{1}{1}& \frac{1}{6}& \frac{1}{1}& \frac{1}{6}\\ \frac{1}{1}& \frac{1}{2}& \frac{1}{4}& \frac{1}{1}& \frac{1}{2}& \frac{1}{4}\\ \frac{1}{1}& \frac{1}{3}& \frac{1}{2}& \frac{1}{6}& \frac{1}{4}& \frac{1}{5}\end{array}\right]\times \left[\begin{array}{c}6\\ 3\\ 0\\ 3\\ 0\\ 3\end{array}\right] \\ =6\times \left[\begin{array}{cccccc}\left(1\times 6\right)+& \left(1\times 3\right)+& \left(1\times 0\right)+& \left(1\times 3\right)+& \left(1\times 0\right)& +\left(1\times 3\right)\\ \left(1\times 6\right)+& \left(3\times 3\right)+& \left(2\times 0\right)+& \left(6\times 3\right)+& \left(4\times 0\right)& +\left(5\times 3\right)\\ \left(1\times 6\right)+& \left(2\times 3\right)+& \left(4\times 0\right)+& \left(1\times 3\right)+& \left(2\times 0\right)& +\left(4\times 3\right)\\ \left(1\times 6\right)+& \left(6\times 3\right)+& \left(1\times 0\right)+& \left(6\times 3\right)+& \left(1\times 0\right)& +\left(6\times 3\right)\\ \left(1\times 6\right)+& \left(4\times 3\right)+& \left(2\times 0\right)+& \left(1\times 3\right)+& \left(4\times 0\right)& +\left(2\times 3\right)\\ \left(1\times 6\right)+& \left(5\times 3\right)+& \left(4\times 0\right)+& \left(6\times 3\right)+& \left(2\times 0\right)& +\left(3\times 3\right)\end{array}\right] \\ =6\times \left[\begin{array}{c}12\\ 48\\ 27\\ 62\\ 27\\ 48\end{array}\right]\begin{array}{}\\ \\ \\ \\ \\ \end{array} \\ =\left[\begin{array}{c}90\\ 288\\ 162\\ 360\\ 162\\ 288\end{array}\right]......\left(32\right) \end{gathered}$$

Taking modulo for equation .

$=\left[\begin{array}{cc}90& mod7\\ 288& mod7\\ 162& mod7\\ 360& mod7\\ 162& mod7\\ 288& mod7\end{array}\right]=\left[\begin{array}{c}6\\ 1\\ 1\\ 3\\ 1\\ 1\end{array}\right]......\left(30\right)$

From equation (23) substitute 6 as -1 in equation (33)

$InverseFFTof\left(P\right)=\left[\begin{array}{c}-1\\ 1\\ 1\\ 3\\ 1\\ 1\end{array}\right]$

Therefore, the transformation of the sequence $(3,6,4,2,3,3)is(-1,1,1,3,1,1).$ .