1
$\begingroup$

I am having trouble finding the same answer as the solution manual for this sequence.

The problem asks to compute the DFT of $$ x[n] = \begin{cases} 1 & \text{for even } n \in \{0\ldots N-1\} \\ 0 & \text{for odd } n \in \{0\ldots N-1\} \end{cases} $$

Setting up the DFT equation I agree with the solution manual $$ X[k]=\sum_0^{N-1}x[n]W^{kn}_{N}=\sum_0^{\frac{N}{2}-1}W^{k2n}_{N}=\sum_0^{\frac{N}{2}-1}e^{\frac{-j2\pi k(2n)}{N}} $$

However when apply the closed form geometric series formula $\sum_0^Na^k=\frac{1-a^{N+1}}{1-a}$ I get $$ \frac{1-e^{-j2\pi k}}{1-e^{\frac{-j2\pi k}{N}}} $$

while the solution manual says its
$$\frac{1-e^{-j2\pi k}}{1-e^{\frac{-j\pi k}{N}}}$$

Note their lower exponent does not have a 2. Could someone explain where and how the 2 goes away? Or does someone agree that the provided answer is incorrect?

This is question 8.5c from Oppenheim's Discrete-Time Signal Processing 3e.

$\endgroup$
3
$\begingroup$

Assuming $N$ even :

$$ \begin{align} X[k] &= \sum_{n=0}^{N-1} x[n] ~ W_N^{kn} ~~~,~~~k=0,1,...,N-1\\ \\ &= \sum_{n=0}^{N/2-1} 1 ~ W_N^{k ~2n} \\ \\ &= \sum_{n=0}^{N/2-1} e^{-j 4\pi kn/N} \\ \\ & = \frac{ 1 - e^{-j \frac{4\pi k}{N}N/2 }}{ 1 - e^{-j 4\pi k/N}} \\ \\ & = \frac{ 1 - e^{-j 2\pi k}}{ 1 - e^{-j 4\pi k/N}}~~~,~~~k=0,1,...,N-1\\ \end{align} $$

The result equals: $$ X[k] = \begin{cases}{ ~~~ N/2 ~~~ ,~~~ k = 0, N/2 \\ ~~~~~~ 0 ~~~~~ ~ ,~ ~\text{otherwise} } \end{cases} $$

$\endgroup$
6
  • 1
    $\begingroup$ glad you posted this, I wrote an answer up and was hesitant to post it seeing that my answer didn't match either of OP's hah. $\endgroup$ – user67081 Jan 17 at 23:31
  • $\begingroup$ @Fat32 thanks for the explanation. I didn't realize either was not correct. The relationship between the big N and little n keeps confusing me. based on your steps 3-4 I can see the little n is based on the summation length while the big N is based on the overall sequence length.. am I correct with this assumption? Could you also explain how you got the result to equal $N/2$? Is there some formula or assumptions you are making? $\endgroup$ – scott Jan 18 at 0:35
  • $\begingroup$ @Fat32 I guess I may be misunderstanding something, for either one of them if k goes to $0$ or $N/2$ I see the exp going to either 1 (for $0$) or some other value (for $N/2$). $\endgroup$ – scott Jan 18 at 19:54
  • $\begingroup$ @Fat32 I am still unsure how you are getting the final result. How does final value result in $N/2$ when it is based on the exponent? Is there some property of the exponential I am missing? For example - case $k=0$ i see it resulting in $\frac{1-e^0}{1-e^0}=\frac{1-1}{1-1}=0$? Maybe I am misunderstanding some concept about $e$? $\endgroup$ – scott Jan 18 at 20:18
  • $\begingroup$ @Fat32 so after thinking a bit more, I am assuming it is connected to the fact $e$ is representing a sinusoidal signal. I will evaluate it using Euler’s equations and update. $\endgroup$ – scott Jan 18 at 20:25
1
$\begingroup$

Figured I'd post this since I wrote it anyway, just a confirmation of Fat32's answer.

Letting $N' = \frac{N}{2} - 1$ we have $\sum_{0}^{\frac{N}{2} - 1} e^{\frac{-j2\pi k (2n)}{N}} = \sum_{0}^{N'} e^{\frac{-j2\pi k n}{(N'+1)}}$

Then plugging in the geometric sum formula:

$=\frac{1 - e^{\frac{-j2\pi k(N'+1)}{(N'+1)}}}{1-e^{\frac{-j2\pi k}{(N'+1)}}}=\frac{1 - e^{\frac{-j2\pi k}{1}}}{1-e^{\frac{-j2\pi k}{(N'+1)}}}$

and finally reverting back to our original variable $N=2(N'+1)$ gives $=\frac{1 - e^{\frac{-j2\pi k}{1}}}{1-e^{\frac{-j4\pi k}{N}}}$

$\endgroup$

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.