2
$\begingroup$

I am trying to compute a single coefficient of the DFT of a linearly ramping sequence, $x[n]=an$ where $a$ is a constant that changes from sequence to seqeunce. I have looked at loads of DFT transform property and pairs tables, but this is a simple case I have not been able to find an analytical expression for. I don't want to have to compute the entire DFT of the sequence just to extract a single coefficient.

My first approach was to notice that multiplication by $n$ in the time domain is like differentiation in the $k$-domain. However, since the DFT of $a$ is an impulse function at $k=0$, I haven't found a way to come up with an analytical expression to take the derivative.

In my application, the number of samples in the sequence, $N$, and the coefficient of interest, $k$, will frequently change. It's just such a simple case that, given $a$, there must be a way for me to predict the value of the DFT of the sequence at a particular value of $k$ without actually doing the transform. Is the only way to do this to numerically create a look-up table of all possible $N$ and $k$ of interest, and then scale by $a$?

$\endgroup$
3
$\begingroup$

There is indeed a better way; you can derive the analytical expression for the DFT of a ramp. Let's start with the discrete-time Fourier transform (DTFT) of a finite length sequence (i.e., the sequence is zero outside the interval $[0,N-1]$):

$$X(e^{j\omega})=\sum_{n=0}^{N-1}x[n]e^{-jn\omega}\tag{1}$$

We also need the DTFT correspondence

$$nx[n]\Longleftrightarrow j\frac{dX(e^{j\omega})}{d\omega}\tag{2}$$

The DTFT of the constant signal $x[n]=a$, $n\in [0,N-1]$ (and zero otherwise) is

$$X(e^{j\omega})=a\sum_{n=0}^{N-1}e^{-jn\omega}=\begin{cases}aN,&\quad\omega=0\\\displaystyle a\frac{1-e^{-jN\omega}}{1-e^{-j\omega}},&\quad\text{otherwise}\end{cases}\tag{3}$$

From $(2)$ and $(3)$ we get

$$\begin{align}a\sum_{n=0}^{N-1}ne^{-jn\omega}&=j\frac{dX(e^{j\omega})}{d\omega}\\&=-a\frac{Ne^{-jN\omega} (1-e^{-j\omega})-(1-e^{-jN\omega})e^{-j\omega}}{(1-e^{-j\omega})^2},\quad\omega\neq 0\end{align}\tag{4}$$

which is the DTFT of the given sequence. For $\omega=0$ we simply have

$$a\sum_{n=0}^{N-1}n=a\frac{N(N-1)}{2}\tag{5}$$

Now we only need to remember that for finite length sequences, the DFT is a sampled version of the DTFT with $\omega_k=2\pi k/N$. From $(4)$ and $(5)$ we obtain

$$\text{DFT}_N\{an\}[k]=\begin{cases}\displaystyle a\frac{N(N-1)}{2},&\quad k=0\\-a\displaystyle\frac{N}{1-e^{-j2\pi k/N}},&\quad k\in[1,N-1]\end{cases}\tag{6}$$

$\endgroup$
  • $\begingroup$ This was exactly what I was looking for, thank you! $\endgroup$ – deltamac Sep 27 '16 at 18:43

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.