Part (a) Need to prove the above properties of the DFS for periodic sequences.
The DFS for a periodic sequence \(\tilde{x}\left ( n\right ) \) of period of length \(N\) is defined as \(\tilde{X}\left ( k\right ) ={\sum \limits _{n=0}^{N-1}}\tilde{x}\left ( n\right ) W_{N}^{kn}\) and \(\tilde{x}\left ( n\right ) =\frac{1}{N}{\sum \limits _{k=0}^{N-1}}\tilde{X}\left ( k\right ) W_{N}^{-kn}\) where \(W_{N}=e^{-j\frac{2\pi }{N}}\).
number 1
sequence: \(\tilde{x}\left ( n+m\right ) ,\) DFS: \(W_{N}^{-km}\tilde{X}\left ( k\right ) \)
Let \(x_{1}\left ( n\right ) =\tilde{x}\left ( n+m\right ) \), let the DFS of \(x_{1}\left ( n\right ) =X_{1}\left ( k\right ) \), hence\begin{align*} X_{1}\left ( k\right ) & ={\sum \limits _{n=0}^{N-1}}x_{1}\left ( n\right ) W_{N}^{kn}\\ & ={\sum \limits _{n=0}^{N-1}}\tilde{x}\left ( n+m\right ) W_{N}^{kn} \end{align*}
Let \(r=n+m\), the above becomes\begin{align*} X_{1}\left ( k\right ) & ={\sum \limits _{r=m}^{N-1+m}}\tilde{x}\left ( r\right ) W_{N}^{k\left ( r-m\right ) }\\ & =W_{N}^{-km}{\sum \limits _{r=m}^{N-1+m}}\tilde{x}\left ( r\right ) W_{N}^{kr}\ \end{align*}
But \({\sum \limits _{r=m}^{N-1+m}}\tilde{x}\left ( r\right ) W_{N}^{kr}={\sum \limits _{r=0}^{N-1}}\tilde{x}\left ( r\right ) W_{N}^{kr}\) since \(\tilde{x}\left ( r\right ) \) is periodic in \(N\), so any range of length \(N\) will do, hence the above becomes\[ X_{1}\left ( k\right ) =W_{N}^{-km}{\sum \limits _{r=0}^{N-1}}\tilde{x}\left ( r\right ) W_{N}^{kr}=W_{N}^{-km}\tilde{X}\left ( k\right ) \] number 2
sequence: \(\tilde{x}^{\ast }\left ( n\right ) ,\) DFS: \(\tilde{X}^{\ast }\left ( -k\right ) \)
Let \(x_{1}\left ( n\right ) =\tilde{x}^{\ast }\left ( n\right ) \), let the DFS of \(x_{1}\left ( n\right ) =X_{1}\left ( k\right ) \), hence \begin{equation} X_{1}\left ( k\right ) ={\sum \limits _{n=0}^{N-1}}x_{1}\left ( n\right ) W_{N}^{kn}={\sum \limits _{n=0}^{N-1}}\tilde{x}^{\ast }\left ( n\right ) W_{N}^{kn}\tag{1} \end{equation} But \(\tilde{X}^{\ast }\left ( -k\right ) =\left ({\sum \limits _{n=0}^{N-1}}\tilde{x}\left ( n\right ) W_{N}^{-kn}\right ) ^{\ast }={\sum \limits _{n=0}^{N-1}}\left ( \tilde{x}\left ( n\right ) W_{N}^{-kn}\right ) ^{\ast }={\sum \limits _{n=0}^{N-1}}\tilde{x}^{\ast }\left ( n\right ) \left ( W_{N}^{-kn}\right ) ^{\ast }\)
But \(\left ( W_{N}^{-kn}\right ) ^{\ast }=\left ( e^{j\frac{2\pi }{N}kn}\right ) ^{\ast }=e^{-j\frac{2\pi }{N}kn}=W_{N}^{kn}\), hence \(\tilde{X}^{\ast }\left ( -k\right ) ={\sum \limits _{n=0}^{N-1}}\tilde{x}^{\ast }\left ( n\right ) W_{N}^{kn}\) which is the same as (1) above, therefore\[ X_{1}\left ( k\right ) ={\sum \limits _{n=0}^{N-1}}\tilde{x}^{\ast }\left ( n\right ) W_{N}^{kn}=\tilde{X}^{\ast }\left ( -k\right ) \]
number 3
sequence: \(\tilde{x}^{\ast }\left ( -n\right ) ,\) DFS: \(\tilde{X}^{\ast }\left ( k\right ) \)
Let \(x_{1}\left ( n\right ) =\tilde{x}^{\ast }\left ( -n\right ) \), let the DFS of \(x_{1}\left ( n\right ) =X_{1}\left ( k\right ) \), hence \begin{equation} X_{1}\left ( k\right ) ={\sum \limits _{n=0}^{N-1}}x_{1}\left ( n\right ) W_{N}^{kn}={\sum \limits _{n=0}^{N-1}}\tilde{x}^{\ast }\left ( -n\right ) W_{N}^{kn}\tag{1} \end{equation} Let \(m=-n\), hence\[ X_{1}\left ( k\right ) ={\sum \limits _{m=0}^{-N+1}}\tilde{x}^{\ast }\left ( m\right ) W_{N}^{-km}\] But \({\sum \limits _{m=0}^{-N+1}}\tilde{x}^{\ast }\left ( m\right ) W_{N}^{-km}={\sum \limits _{m=0}^{N-1}}\tilde{x}^{\ast }\left ( m\right ) W_{N}^{-km}\) since \(\tilde{x}^{\ast }\left ( m\right ) \) is periodic in \(N\), so any range of length \(N\) will do, hence the above becomes\begin{align*} X_{1}\left ( k\right ) & ={\sum \limits _{m=0}^{N-1}}\tilde{x}^{\ast }\left ( m\right ) W_{N}^{-km}\\ & ={\sum \limits _{m=0}^{N-1}}\left ( \tilde{x}\left ( m\right ) \left ( W_{N}^{-km}\right ) ^{\ast }\right ) ^{\ast }\\ & ={\sum \limits _{m=0}^{N-1}}\left ( \tilde{x}\left ( m\right ) W_{N}^{km}\right ) ^{\ast }\\ & =\left ({\sum \limits _{m=0}^{N-1}}\tilde{x}\left ( m\right ) W_{N}^{km}\right ) ^{\ast }\\ & =\tilde{X}^{\ast }\left ( k\right ) \end{align*}
Hence \(X_{1}\left ( k\right ) =\tilde{X}^{\ast }\left ( k\right ) \)
number 4
sequence: \(\operatorname{Re}\left [ \tilde{x}\left ( n\right ) \right ] ,\) DFS: \(\tilde{X}_{e}\left ( k\right ) \)
Let \(\tilde{x}\left ( n\right ) =\tilde{a}\left ( n\right ) +j\tilde{b}\left ( n\right ) \,\ \)where \(\tilde{a}\left ( n\right ) =\operatorname{Re}\left [ \tilde{x}\left ( n\right ) \right ] \) and \(\tilde{b}\left ( n\right ) =\operatorname{Im}\left [ \tilde{x}\left ( n\right ) \right ] \)
Let \(x_{1}\left ( n\right ) =\operatorname{Re}\left [ \tilde{x}\left ( n\right ) \right ] =\tilde{a}\left ( n\right ) \), let the DFS of \(x_{1}\left ( n\right ) =X_{1}\left ( k\right ) \), hence\begin{align} X_{1}\left ( k\right ) & ={\sum \limits _{n=0}^{N-1}}x_{1}\left ( n\right ) W_{N}^{kn}\nonumber \\ & ={\sum \limits _{n=0}^{N-1}}\tilde{a}\left ( n\right ) W_{N}^{kn}\tag{1} \end{align}
But \begin{align*} \tilde{X}_{e}\left ( k\right ) & =\frac{1}{2}\left [ \tilde{X}\left ( k\right ) +\tilde{X}^{\ast }\left ( -k\right ) \right ] \\ & =\frac{1}{2}\left [{\sum \limits _{n=0}^{N-1}}\tilde{x}\left ( n\right ) W_{N}^{kn}+\left ({\sum \limits _{n=0}^{N-1}}\tilde{x}\left ( n\right ) W_{N}^{-kn}\right ) ^{\ast }\right ] \\ & =\frac{1}{2}\left [{\sum \limits _{n=0}^{N-1}}\tilde{x}\left ( n\right ) W_{N}^{kn}+{\sum \limits _{n=0}^{N-1}}\tilde{x}^{\ast }\left ( n\right ) W_{N}^{kn}\right ] \\ & =\frac{1}{2}\left [{\sum \limits _{n=0}^{N-1}}\left ( \tilde{a}\left ( n\right ) +j\tilde{b}\left ( n\right ) \right ) W_{N}^{kn}+{\sum \limits _{n=0}^{N-1}}\left ( \tilde{a}\left ( n\right ) -j\tilde{b}\left ( n\right ) \right ) W_{N}^{kn}\right ] \\ & =\frac{1}{2}{\sum \limits _{n=0}^{N-1}}2\tilde{a}\left ( n\right ) W_{N}^{kn}\\ & ={\sum \limits _{n=0}^{N-1}}\tilde{a}\left ( n\right ) W_{N}^{kn} \end{align*}
Compare the above result to (1), we see it is the same.
number 5
sequence: \(j\operatorname{Im}\left [ \tilde{x}\left ( n\right ) \right ] ,\) DFS: \(\tilde{X}_{o}\left ( k\right ) \)
Let \(\tilde{x}\left ( n\right ) =\tilde{a}\left ( n\right ) +j\tilde{b}\left ( n\right ) \,\ \)where \(\tilde{a}\left ( n\right ) =\operatorname{Re}\left [ \tilde{x}\left ( n\right ) \right ] \) and \(\tilde{b}\left ( n\right ) =\operatorname{Im}\left [ \tilde{x}\left ( n\right ) \right ] \)
Let \(x_{1}\left ( n\right ) =j\operatorname{Im}\left [ \tilde{x}\left ( n\right ) \right ] =j\tilde{b}\left ( n\right ) \), let the DFS of \(x_{1}\left ( n\right ) =X_{1}\left ( k\right ) \), hence\begin{equation} X_{1}\left ( k\right ) ={\sum \limits _{n=0}^{N-1}}x_{1}\left ( n\right ) W_{N}^{kn}={\sum \limits _{n=0}^{N-1}}j\tilde{b}\left ( n\right ) W_{N}^{kn}\tag{1} \end{equation} But \begin{align*} \tilde{X}_{o}\left ( k\right ) & =\frac{1}{2}\left [ \tilde{X}\left ( k\right ) -\tilde{X}^{\ast }\left ( -k\right ) \right ] \\ & =\frac{1}{2}\left [{\sum \limits _{n=0}^{N-1}}\tilde{x}\left ( n\right ) W_{N}^{kn}-\left ({\sum \limits _{n=0}^{N-1}}\tilde{x}\left ( n\right ) W_{N}^{-kn}\right ) ^{\ast }\right ] \\ & =\frac{1}{2}\left [{\sum \limits _{n=0}^{N-1}}\tilde{x}\left ( n\right ) W_{N}^{kn}-{\sum \limits _{n=0}^{N-1}}\tilde{x}^{\ast }\left ( n\right ) W_{N}^{kn}\right ] \\ & =\frac{1}{2}\left [{\sum \limits _{n=0}^{N-1}}\left ( \tilde{a}\left ( n\right ) +j\tilde{b}\left ( n\right ) \right ) W_{N}^{kn}-{\sum \limits _{n=0}^{N-1}}\left ( \tilde{a}\left ( n\right ) -j\tilde{b}\left ( n\right ) \right ) W_{N}^{kn}\right ] \\ & =\frac{1}{2}{\sum \limits _{n=0}^{N-1}}2j\tilde{b}\left ( n\right ) W_{N}^{kn}\\ & ={\sum \limits _{n=0}^{N-1}}j\tilde{b}\left ( n\right ) W_{N}^{kn} \end{align*}
Compare the above result to (1), we see it is the same.
Find the DFT of these sequences, each of length \(N\)
Let \(X\left ( k\right ) \) be the DFT of the sequence \(x\left ( n\right ) \). The definition of the \(X\left ( k\right ) \) is (equation 3.26, page 100 of textbook)\[ X\left ( k\right ) =\left \{ \begin{array} [c]{cc}{\sum \limits _{n=0}^{N-1}}x\left ( n\right ) W_{N}^{nk} & 0\leq k\leq N-1\\ 0 & otherwise \end{array} \right . \] Where \(W_{N}^{nk}=e^{-j\frac{2\pi }{N}nk}\)
(a)For \(x\left ( n\right ) =\delta \left ( n\right ) \) we have\[ X\left ( k\right ) ={\sum \limits _{n=0}^{N-1}}\delta \left ( n\right ) W_{N}^{nk}=W_{N}^{0}=1 \] (b)For \(x\left ( n\right ) =\delta \left ( n-n_{0}\right ) \) we have\[ X\left ( k\right ) ={\sum \limits _{n=0}^{N-1}}\delta \left ( n-n_{0}\right ) W_{N}^{nk}=W_{N}^{n_{0}}=e^{-j\frac{2\pi }{N}n_{0}k}\] (c)For \(x\left ( n\right ) =a^{n}\) we have\begin{equation} X\left ( k\right ) ={\sum \limits _{n=0}^{N-1}}a^{n}W_{N}^{nk}={\sum \limits _{n=0}^{N-1}}\left ( aW_{N}^{k}\right ) ^{n}=\frac{1-\left ( aW_{N}^{k}\right ) ^{N}}{1-aW_{N}^{k}}\tag{1} \end{equation} But \(\left ( aW_{N}^{k}\right ) ^{N}=a^{N}e^{-j\frac{2\pi }{N}kN}=a^{N}e^{-j2\pi k}=a^{N}\) since \(e^{-j2\pi k}=\cos 2\pi k-j\sin 2\pi k\) and \(k\) is an integer, so we obtain \(1\), hence (1) becomes\[ X\left ( k\right ) =\frac{1-a^{N}}{1-aW_{N}^{k}}\]
\(f_{s}=10khz\), hence sampling period is \(T_{s}=\frac{1}{10000}\sec \). and number of samples is \(N=1024\).
We can view the \(1024\) samples as making up one period of the signal being sampled. Hence the time duration of this period is \(N\times T_{s}\)
The \(1024\) samples are distributed equally around one cycle. So, a spacing in frequency axis which represents one cycle per second must be the same as the cycle divided equally over the period of the sequence, which is \(N\times T_{s}\)
In other words, if we let the spacing in frequency be \(\Delta \), then \[ \Delta =\frac{1}{NT_{s}}=\frac{1}{1024\times \frac{1}{10000}}=9.\,765Hz \] or in radians\[ \Delta =\frac{2\pi }{NT_{s}}=\frac{2\pi }{1024\times \frac{1}{10000}}=19.531\pi =61.359\text{ radians per sec}\] In other words, each bin on the frequency axis will be \(9.765\,6Hz\) wide. So, resolution less than this amount can’t be detected.
We see that, the larger the number of samples is (keeping the sampling period constant), the smaller \(\Delta \) will be. Hence a more detailed frequency spacing can be obtained by having more samples. i.e. the bin width will become smaller and smaller, the larger the number of samples. Hence, frequencies which exist over very small bandwidth’s can now be seen more clearly since the frequency resolution is higher. By appending zeros to the sequence before FFT, we can increase the resolution since we have increased \(N\) this way.
This definition means that the first second half of the sequence \(x\left ( n\right ) \) is negative of the first half half. To see this, I tried \(N=3\) and \(N=4\), (even and odd terms) to obtain this
For \(N=3\)
| \(n\) | \(x\left ( n\right ) \) | \(-x\left ( N-1-n\right ) \) |
| \(0\) | \(x\left ( 0\right ) \) | \(-x\left ( 2\right ) \) |
| \(1\) | \(x\left ( 1\right ) \) | \(-x\left ( 1\right ) \) |
| \(2\) | \(x\left ( 2\right ) \) | \(-x\left ( 0\right ) \) |
For \(x\left ( 1\right ) \) to be the same as \(-x\left ( 1\right ) \), then \(x\left ( 1\right ) =0\). Hence for odd numbered sequence, the midterm must be zero. So, an example of the above sequence is \(x=\left \{ 5,0,-5\right \} \)
If \(N\) is even, we also get the same result, but there is no middle term in this case, for example, for \(N=4\)
| \(n\) | \(x\left ( n\right ) \) | \(-x\left ( N-1-n\right ) \) |
| \(0\) | \(x\left ( 0\right ) \) | \(-x\left ( 3\right ) \) |
| \(1\) | \(x\left ( 1\right ) \) | \(-x\left ( 2\right ) \) |
| \(2\) | \(x\left ( 2\right ) \) | \(-x\left ( 1\right ) \) |
| \(3\) | \(x\left ( 3\right ) \) | \(-x\left ( 0\right ) \) |
So, this is an example of the sequence: \(x=\left \{ 5,2,-2,-5\right \} \)
We hence see that the sum of the sequence will always be zero. Now to answer the question as the way they wanted use to do it. \[ X\left ( k\right ) ={\sum \limits _{n=0}^{N-1}}x\left ( n\right ) W_{N}^{nk}\hspace{20pt}k=0\cdots N-1 \] Let \(k=0\), and the above becomes the DC terms only\[ X\left ( 0\right ) ={\sum \limits _{n=0}^{N-1}}x\left ( n\right ) \] But the sum of the sequence is zero. Hence \(X\left ( 0\right ) =0\)
Now we are told that \(N\) is always even, and that \(x\left ( n\right ) =x\left ( N-1-n\right ) \), so let us make a small table to see better what this means
| \(n\) | \(x\left ( n\right ) \) | \(x\left ( N-1-n\right ) \) |
| \(0\) | \(x\left ( 0\right ) \) | \(x\left ( 3\right ) \) |
| \(1\) | \(x\left ( 1\right ) \) | \(x\left ( 2\right ) \) |
| \(2\) | \(x\left ( 2\right ) \) | \(x\left ( 1\right ) \) |
| \(3\) | \(x\left ( 3\right ) \) | \(x\left ( 0\right ) \) |
So, an example of such a sequence is \(x=\left \{ 5,2,2,5\right \} \), so this is a sequence is which the first half is duplicated in the second half.\[ X\left ( k\right ) ={\sum \limits _{n=0}^{N-1}}x\left ( n\right ) W_{N}^{nk}\hspace{20pt}k=0\cdots N-1 \] hence \[ X\left ( \frac{N}{2}\right ) ={\sum \limits _{n=0}^{N-1}}x\left ( n\right ) W_{N}^{n\frac{N}{2}}={\sum \limits _{n=0}^{N-1}}x\left ( n\right ) e^{-j\frac{2\pi }{N}n\frac{N}{2}}={\sum \limits _{n=0}^{N-1}}x\left ( n\right ) e^{-j\pi n}\] But \(e^{-j\pi n}=\cos \pi n-j\sin \pi n\) and since \(n\) is an integer, then this becomes \(\cos \pi n\). So when \(n\) is even, \(\cos \pi n=1\) and when \(n\) is odd \(\cos \pi n=-1\) so the above can be written as\[ X\left ( \frac{N}{2}\right ) ={\sum \limits _{n=0}^{N-1}}x\left ( n\right ) \left ( -1\right ) ^{n}\] break the sum into 2 halves, even \(n^{\prime }s\) and the odd \(n^{\prime }s\)\begin{align*} X\left ( \frac{N}{2}\right ) & ={\sum \limits _{n\ odd}^{N-1}}x\left ( n\right ) \left ( -1\right ) +{\sum \limits _{n\ even}^{N-1}}x\left ( n\right ) \left ( +1\right ) \\ & =-{\sum \limits _{n\ odd}^{N-1}}x\left ( n\right ) +{\sum \limits _{n\ even}^{N-1}}x\left ( n\right ) \end{align*}
But \({\sum \limits _{n\ odd}^{N-1}}x\left ( n\right ) ={\sum \limits _{n\ even}^{N-1}}x\left ( n\right ) \) from the definition of \(x\left ( n\right ) \), hence \(X\left ( \frac{N}{2}\right ) =0\)
\[ X\left ( k\right ) ={\sum \limits _{n=0}^{N-1}}x\left ( n\right ) W_{N}^{nk}\ \ \ \ \ \ \ \ \ \ \ \ \ \ k=0\cdots N-1 \] hence taking the DFT of the above, we obtain\begin{align*} x_{1}\left ( n\right ) & ={\sum \limits _{k=0}^{N-1}}X\left ( k\right ) W_{N}^{kn}\ \ \ \ \ \ \ \ \ \ \ \ \ \ r=0\cdots N-1\\ & ={\sum \limits _{k=0}^{N-1}}\left ({\sum \limits _{m=0}^{N-1}}x\left ( m\right ) W_{N}^{mk}\right ) W_{N}^{kn}\\ & ={\sum \limits _{m=0}^{N-1}}x\left ( m\right ){\sum \limits _{k=0}^{N-1}}W_{N}^{k\left ( n+m\right ) }\\ & ={\sum \limits _{m=0}^{N-1}}x\left ( m\right ) \left ( \frac{1-W_{N}^{\left ( n+m\right ) N}}{1-W_{N}^{\left ( n+m\right ) }}\right ) \end{align*}
But \(\frac{1-W_{N}^{\left ( n+m\right ) N}}{1-W_{N}^{\left ( n+m\right ) }}=\frac{1-e^{-j2\pi \left ( n+m\right ) }}{1-e^{-j\frac{2\pi }{N}\left ( n+m\right ) }}=\left \{ \begin{array} [c]{cc}1 & m=rN-n\\ 0 & otherwise \end{array} \right . \), hence the above becomes\[ x_{1}\left ( n\right ) ={\sum \limits _{r=0}^{N-1}}x\left ( \left ( rN-n\right ) \right ) _{N}\] For example, if \(x\left ( n\right ) =\{\underset{\uparrow }{1},2,3,4\}\), and is zero otherwise, then \(N=4\) and \[ x_{1}\left ( n\right ) =x\left ( \left ( -n\right ) \right ) _{4}+x\left ( \left ( N-n\right ) \right ) _{4}+x\left ( \left ( 2N-n\right ) \right ) _{4}++x\left ( \left ( 3N-n\right ) \right ) _{4}\] hence \begin{align*} x_{1}\left ( 0\right ) & =x\left ( \left ( 0\right ) \right ) _{4}+x\left ( \left ( 4\right ) \right ) _{4}+x\left ( \left ( 8\right ) \right ) _{4}++x\left ( \left ( 12\right ) \right ) _{4}\\ & =x\left ( 0\right ) +x\left ( 0\right ) +x\left ( 0\right ) ++x\left ( 0\right ) \\ & =1+1+1+1\\ & =4 \end{align*}
and\begin{align*} x_{1}\left ( 1\right ) & =x\left ( \left ( -1\right ) \right ) _{4}+x\left ( \left ( 3\right ) \right ) _{4}+x\left ( \left ( 7\right ) \right ) _{4}++x\left ( \left ( 11\right ) \right ) _{4}\\ & =x\left ( 3\right ) +x\left ( 3\right ) +x\left ( 3\right ) ++x\left ( 3\right ) \\ & =4+4+4+4\\ & =16 \end{align*}
and\begin{align*} x_{1}\left ( 2\right ) & =x\left ( \left ( -2\right ) \right ) _{4}+x\left ( \left ( 2\right ) \right ) _{4}+x\left ( \left ( 6\right ) \right ) _{4}++x\left ( \left ( 10\right ) \right ) _{4}\\ & =x\left ( 2\right ) +x\left ( 2\right ) +x\left ( 2\right ) ++x\left ( 2\right ) \\ & =3+3+3+3\\ & =12 \end{align*}
and\begin{align*} x_{1}\left ( 3\right ) & =x\left ( \left ( -3\right ) \right ) _{4}+x\left ( \left ( 1\right ) \right ) _{4}+x\left ( \left ( 5\right ) \right ) _{4}++x\left ( \left ( 9\right ) \right ) _{4}\\ & =x\left ( 1\right ) +x\left ( 1\right ) +x\left ( 1\right ) ++x\left ( 1\right ) \\ & =2+2+2+2\\ & =8 \end{align*}
To verify:
Another way I can write the answer is\[ x_{1}\left ( n\right ) =N\ x\left ( \left ( N-n\right ) \right ) _{N}\] Using the above example, we obtain\begin{align*} x_{1}\left ( 0\right ) & =4\ x\left ( \left ( 4-0\right ) \right ) _{4}=4\ x\left ( \left ( 4\right ) \right ) _{4}=4\ x\left ( 0\right ) =4\times 1=4\\ x_{1}\left ( 1\right ) & =4\ x\left ( \left ( 4-1\right ) \right ) _{4}=4\ x\left ( \left ( 3\right ) \right ) _{4}=4\ x\left ( 3\right ) =4\times 4=16\\ x_{1}\left ( 2\right ) & =4\ x\left ( \left ( 4-2\right ) \right ) _{4}=4\ x\left ( \left ( 2\right ) \right ) _{4}=4\ x\left ( 2\right ) =4\times 3=12\\ x_{1}\left ( 3\right ) & =4\ x\left ( \left ( 4-3\right ) \right ) _{4}=4\ x\left ( \left ( 1\right ) \right ) _{4}=4\ x\left ( 1\right ) =4\times 2=8 \end{align*}
equation 3.26 is \(\tilde{X}\left ( k\right ) ={\sum \limits _{n=0}^{N-1}}\tilde{x}\left ( n\right ) W_{N}^{kn}\) and \(\tilde{x}\left ( n\right ) =\frac{1}{N}{\sum \limits _{k=0}^{N-1}}\tilde{X}\left ( k\right ) W_{N}^{-kn}\)
We start with the relation that says the DFT of \(x_{1}(n) x_{2}(n)\) is the circular convolution of \(\tilde{X}_{1}(k)\) with \(\tilde{X}_{2}(k)\).
Hence \begin{align*}{\sum \limits _{n=0}^{N-1}}\left [ x_{1}\left ( n\right ) x_{2}\left ( n\right ) \right ] W_{N}^{kn} & =\tilde{X}_{1}\left ( k\right ) \underset{N}{\circledast }\tilde{X}_{2}\left ( k\right ) \\ & =\frac{1}{N}{\sum \limits _{k=0}^{N-1}}\tilde{X}_{1}\left ( \left ( k\right ) \right ) _{N}\tilde{X}_{2}\left ( \left ( n-k\right ) \right ) _{N} \end{align*}
Let \(x_{1}\left ( n\right ) =x_{2}\left ( n\right ) =x\left ( n\right ) \) hence the above becomes\[{\sum \limits _{n=0}^{N-1}}x^{2}\left ( n\right ) W_{N}^{kn}=\frac{1}{N}{\sum \limits _{k=0}^{N-1}}\tilde{X}^{2}\left ( k\right ) \] where I used the fact that circular convolution of \(\tilde{X}\left ( k\right ) \) with itself becomes \(\tilde{X}^{2}\left ( k\right ) \). Taking the absolute value of each side gives\begin{align*} \left \vert{\sum \limits _{n=0}^{N-1}}x^{2}\left ( n\right ) W_{N}^{kn}\right \vert & =\left \vert \frac{1}{N}{\sum \limits _{k=0}^{N-1}}\tilde{X}^{2}\left ( k\right ) \right \vert \\{\sum \limits _{n=0}^{N-1}}\left \vert x^{2}\left ( n\right ) \right \vert \left \vert W_{N}^{kn}\right \vert & =\frac{1}{N}{\sum \limits _{k=0}^{N-1}}\left \vert \tilde{X}^{2}\left ( k\right ) \right \vert \end{align*}
But \(\left \vert W_{N}^{kn}\right \vert =1\)\[{\sum \limits _{n=0}^{N-1}}\left \vert x^{2}\left ( n\right ) \right \vert =\frac{1}{N}{\sum \limits _{k=0}^{N-1}}\left \vert \tilde{X}^{2}\left ( k\right ) \right \vert \] or\[{\sum \limits _{n=0}^{N-1}}\left \vert x\left ( n\right ) \right \vert ^{2}=\frac{1}{N}{\sum \limits _{k=0}^{N-1}}\left \vert \tilde{X}\left ( k\right ) \right \vert ^{2}\]