3
$\begingroup$

I have a problem with expressing odd samples of X2 in terms of X1. I understand that the resulting DFT will be more precise in terms of expressing the exact spectrum of signal x[n], due to more samples. Moreover I know that even samples of X2(k) are copy of the spectrum of X1(k), however I do not know how to mathematically compute the odd ones.

The task is as follows:

Let $x[n]$ be a periodic sequence with period $N_1$ . Thus $x[n]$ is also periodic for period $N_2 = 2 N_1$ . We may compute $X_1[k]$: $N$-point DFT of $x[n]$ and $X_2[k]$: $2N$-point DFT of $x[n]$.

  • Express $X_2$in terms of $X_1$ Hint: it is easy with even samples $X_2[2m]$ , harder with odd ones $X2_[2m+ 1]$ , for $m$ integer.
$\endgroup$

1 Answer 1

4
$\begingroup$

Consider N-point sequence $x[n]$ whose N-point DFT is $X[k]$. To compute 2N-point DFT, $X_2[k]$, of $x[n]$, one should append N-zeroes to $x[n]$, and make it a 2N-point sequence, denoted $x_2[n]$. Obviously, first N-samples of $x[n]$ and $x_2[n]$ are identical, and last N-samples of $x_2[n]$ are just zeroes.

Write 2N-point DFT of $x_2[n]$:

$$ X_2[k] = \sum_{n=0}^{2N-1} x_2[n] e^{-j \frac{2 \pi}{2N} n k } ~~,~~ k=0,1,...,2N-1 \tag{1}$$

which is identical to: $$ X_2[k] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2 \pi}{N} n (k/2) } ~~,~~ k=0,1,...,2N-1 \tag{2}$$

Now, the even indexed samples of $X_2[k]$ can be shown to be $X[k/2]$, by setting $k_e=2m$ in Eq.2, $m=0,1,...,N-1$ :

$$ X_2[2m] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2 \pi}{N} n (2m/2) } = X[m] \tag{3}$$

The odd indexed samples of $X_2[k]$ can also be obtained similarly by setting $k_o = 2m+1$, in Eq.2:

$$ X_2[2m+1] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2 \pi}{N} n (\frac{2m+1}{2}) } = X[m+0.5] \tag{4}$$

Eq.4 is an interpolation statement; i.e., the sample $X[m+0.5]$ implies (but does not perform) interpolation between $X[m]$ and $X[m+1]$. However, it's not proper to set $k=m+0.5$ into the argument of a sequence, which is a mathematical array of numbers indexed by an integer; fractional indices make no literal sense. Nevertheless, Eq.4 means that taking 2N-point DFT of an N-point sequence, effectively, interpolates between samples of N-point DFT of the N-point sequence.

On the other hand, one can manipulate Eq.4 to see that:

$$ X_2[2m+1] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2 \pi}{N} n (\frac{2m+1}{2}) } = X[m+0.5] \tag{5}$$

$$ X_2[2m+1] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{ \pi}{N} n} e^{-j \frac{2 \pi}{N} n m } \tag{6}$$

denoting $x_o[n] = x[n] e^{-j \frac{ \pi}{N} n}$ yields $$ X_2[2m+1] = \sum_{n=0}^{N-1} x_o[n] e^{-j \frac{2 \pi}{N} n m} = X_o[m]\tag{7}$$

Where $X_o[m]$ is the N-point DFT of the sequence $x_o[n]$. Time-domain modulation of $x[n]$ by $ e^{-j \frac{ \pi}{N} n}$, performs half-sample shift of its N-point DFT $X[k]$, thus describe the so called interpolated values $X[k+0.5]$.

$\endgroup$
3
  • 1
    $\begingroup$ Thank you, I forgot about the shift in time property of DFT for solving this one. $\endgroup$
    – Celeborth
    Nov 25, 2018 at 12:08
  • $\begingroup$ Can you explain why we use here $$e^{-j\frac{\pi}{N}n}$$ and not $$e^{-j\frac{2\pi}{N}n}$$? $\endgroup$
    – Celeborth
    Nov 25, 2018 at 12:18
  • 1
    $\begingroup$ By elaborating on the DFT expression you can get it... $\endgroup$
    – Fat32
    Nov 25, 2018 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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