Given, $x(n)=\{1,1,1,1,1,1,0,0\}$ and $N=8=2^{3}$

Step 1: $\mathrm{x}(n)$ is written in bit reversed order i.e. $\{1,1,1,0,1,1,1,0\}$ is the input for step $1 .$

The phase factor for step 1 is $W_{2}^{0}=e^{0}=1$

The butterfly computations for step 1 are:

Output of step 1 is $\mathrm{V}(\mathrm{k})=\{2,0,1,1,2,0,1,1\}$

Step 2: Output of step 1 forms the input for second step

The phase factor for step $2 \quad W_{4}^{0}=e^{0}=1, W_{4}^{1}=e^{-j 2 \pi / 4}=\cos \frac{2 \pi}{4}-j \sin \frac{2 \pi}{4}=0-j=-j$

The butterfly computations for step 2 are:

Output of step 2 is $\mathrm{F}(\mathrm{k})=\{3,-j, 1, j, 3,-j, 1, j\}$

Step 3: Output of step 2 forms the input for third step Phase factors for step 3 are $W_{8}^{0}=e^{0}=1$

$W_{8}^{1}=e^{-j 2 \pi / 8}=\cos \frac{2 \pi}{8}-j \sin \frac{2 \pi}{8}=\frac{1}{\sqrt{2}}-j \frac{1}{\sqrt{2}}$

$W_{8}^{2}=e^{-j 4 \pi / 8}=\cos \frac{4 \pi}{8}-j \sin \frac{4 \pi}{8}=0-j \times 1=-j$

$W_{8}^{3}=e^{-j 6 \pi / 8}=\cos \frac{6 \pi}{8}-j \sin \frac{6 \pi}{8}=\frac{-1}{\sqrt{2}}-j \frac{1}{\sqrt{2}}$

The butterfly computations for step 3 are:

Output of step 3 = $\{6,-0.7071-1.7071 j, 1-j, 0.7071+0.2929j, 0, 0.7071-0.2929 j, 1+j, -0.7071+1.7071 j\}$

Hence, the DFT of given sequence $\mathrm{x}(\mathrm{n})$ is

$\mathrm{X}(\mathrm{k})=\mathrm{DFT}\{\mathrm{x}(\mathrm{n})\}=\{6,-0.7071-1.7071 j, 1-j, 0.7071+0.2929j, 0, 0.7071-0.2929 j, 1+j, -0.7071+1.7071 j\}$