1
$\begingroup$

Trying to prove that:

$$ X^{*}[k] = \sum^{N-1}_{n=0} x^{*}\left((N-n)\right)_N\ W_N^{nk} $$

Where: $$((x))_N \text{ = x modulus N}$$

$$W_{N}^{nk} = e^{-j\ 2\pi / N}$$

So I start out with definition for DFT:

$$ X[k]=\sum^{N-1}_{n=0} x[n]\ W_{N}^{nk} $$

Then I conjugate both sides of equation.

$$ X^{*}[k]=\left[\sum^{N-1}_{n=0} x[n]\ W_{N}^{nk}\right]^{*} $$

$$ X^{*}[k]=\sum^{N-1}_{n=0} x^{*}[n]\ W_{N}^{-nk} $$

then somehow the -n changes to N-n which i'm guessing is this:

$$((-n))_N = N - n$$

I don't really understand it... but, seems its equivalent if you do this inside of an exponent… to just randomly take a modulus of a negative signed number and replace it with its modulus equivalent?

$$ X^{*}[k]=\sum^{N-1}_{n=0} x^{*}[n]\ W_{N}^{(N-n)k} $$

Then, I get stuck on the proof because somehow $x^{*}[n]$ changes to $x^*((N-n))$,

and $W_{N}^{(N-n)k}$ somehow changes to $W_{N}^{nk}$.

and thus, i'm unable to obtain final result of:

$$ X^{*}[k] = \sum^{N-1}_{n=0} x^{*}((N-n))_N\ W_N^{nk} $$

still wondering what the rules are to apply to get there?

$\endgroup$
  • 1
    $\begingroup$ to deal with the $\mathrm{mod}$ operator, just periodically extend $x[n]$ so that $$ x[n+N] = x[n] \qquad \forall n \in \mathbb{Z} $$ then just get rid of all that $\mathrm{mod}$ crap. $\endgroup$ – robert bristow-johnson Jan 25 at 3:27
  • $\begingroup$ is it also true that x[N - n] = x[n]? and x[-n] = X[N-n]? $\endgroup$ – MrCasuality Jan 25 at 3:51
  • $\begingroup$ if you are curious where i'm at now... its Shaum's DSP outline, 2nd edition, page 262, problem 6.11(b). $\endgroup$ – MrCasuality Jan 25 at 3:53
  • $\begingroup$ it is true that $x[N-n]=x[-n]$ but it is not true in general that $x[-n]=x[n]$. it could be the case, but that is a special case with even symmetry. $\endgroup$ – robert bristow-johnson Jan 25 at 21:14
3
$\begingroup$

So you want to show $X^*[k]$ ?

Actually it follows very simply from the fundamental properties

  • $x[n] \longleftrightarrow X[k]$
  • $x[-n] \longleftrightarrow X[-k]$
  • $x[n]^* \longleftrightarrow X^*[-k]$

and by combining the last two you have:

  • $x[-n]^* \longleftrightarrow X^*[k]$

which shows that $X^*[k]$ is given by the forward DFT of the signal $x[-n]^*$.

Note that, due to periodicity of DFT sequences, the negative index can be repaced by $-n = N-n$, and hence $x[-n]^* = x[N-n]^*$ too.

Direct derivation is as follows:

$$ X[k] = \sum_{n=0}^{N-1} x[n] W_N^{nk} $$

where $W_N= e^{-j \frac{2\pi}{N} }$.

Take conjugate of both sides: $$ X^*[k] = (\sum_{n=0}^{N-1} x[n] W_N^{nk})^* $$

$$ X^*[k] = \sum_{n=0}^{N-1} x^*[n] W_N^{-nk} $$

replace $n$ with $-n$ so that forward DFT appaers:

$$ X^*[k] = \sum_{n=0}^{N-1} x^*[-n] W_N^{nk} $$

which again shows that $X^*[k]$ is given by DFT of $x[-n]^*$. Note again that periodicity of $x[n]$ is utilized to rearrange the limits.

$\endgroup$
  • $\begingroup$ Thanks, that answers it... then the last step is to replace x*[-n] with x*[N-n] so that index is within 0 to N-1 range... not sure why they also add modulus to x*[N-n] as well since range of sum is 0 to N-1..., but, i think that's not really needed.. $\endgroup$ – MrCasuality Jan 25 at 12:51
  • $\begingroup$ I think x[n] is implicitly modulus when dealing with DFT X[k]... so you really don't need to write it explicitly... $\endgroup$ – MrCasuality Jan 25 at 12:59
  • $\begingroup$ Every (repeat every) expression involving DFT sequences can be written using modulus operator. And indeed it's implicitly implied as well. Note that for $ 0 \leq n \leq N-1$ , we have $\text{mod}(n,N) = n$ and $\text{mod}(-n,N) = N-n$.. $\endgroup$ – Fat32 Jan 25 at 20:07
  • $\begingroup$ just a notational curiosity? why do you put the asterisk in different places for $X^*[\cdot]$ and $x[\cdot]^*$? $\endgroup$ – robert bristow-johnson Jan 25 at 21:16
  • $\begingroup$ oh, and i think that there is one pesky exception. for $1 \le n < N$ then $$ \mod(-n,N) = N-n $$ but not for $n=0$. $\endgroup$ – robert bristow-johnson Jan 25 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.