# DFT conjugate of $X^*[k]$, how to prove its formula in terms of $x^*[n]$?

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?

• 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. – robert bristow-johnson Jan 25 at 3:27
• is it also true that x[N - n] = x[n]? and x[-n] = X[N-n]? – MrCasuality Jan 25 at 3:51
• if you are curious where i'm at now... its Shaum's DSP outline, 2nd edition, page 262, problem 6.11(b). – MrCasuality Jan 25 at 3:53
• 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. – robert bristow-johnson Jan 25 at 21:14

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.

• 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.. – MrCasuality Jan 25 at 12:51
• I think x[n] is implicitly modulus when dealing with DFT X[k]... so you really don't need to write it explicitly... – MrCasuality Jan 25 at 12:59
• 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$.. – Fat32 Jan 25 at 20:07
• just a notational curiosity? why do you put the asterisk in different places for $X^*[\cdot]$ and $x[\cdot]^*$? – robert bristow-johnson Jan 25 at 21:16
• 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$. – robert bristow-johnson Jan 25 at 21:18