1
$\begingroup$

I am trying to find the discrete Fourier transform of $y_k=\left[k-\frac{m-1}{2}\right]^{2},$ but I am not sure of the step by step for going about this computation.

how is the first step??

thank you very much!!

  • 6
    @nname: By removing the equations from your question, you made it impossible to understand. That constitutes vandalism. If you do something like that again, you may be suspended.2012-06-18

2 Answers 2

4

I assume you want a DFT of $(y_0,y_1,\cdots,y_{n-1})$ given $n$. First write out the FT and then expand:

$\begin{array}{c l}\widehat{y}_r & =\sum_{k=0}^{n-1}\left(k-\frac{m-1}{2}\right)^2\exp\left(-2\pi i\frac{kr}{n}\right) \\ & = \left(\sum_{k=0}^{n-1}k^2 \big(e^{-2\pi i r/n}\big)^k\right)-(m-1)\left(\sum_{k=0}^{n-1}k\big(e^{-2\pi i r/n}\big)^k\right)+\left(\frac{m-1}{2}\right)^2\left(\sum_{k=0}^{n-1}\big(e^{-2\pi i r/n}\big)^k\right).\end{array}$

Now some tricks come in handy. First, the geometric sum formula:

$\sum_{k=0}^{n-1} z^k=\frac{z^n-1}{z-1}.$

Differentiating this and then multiplying by $z$ gives:

$\sum_{k=0}^{n-1} kz^{k}=\frac{(n-1)z^{n+1}-nz^n+z}{(z-1)^2}. \tag{*}$

Plugging in $z=e^{-2\pi i r/n}$ will give the middle term of our expression, and the geometric sum formula itself works on the last term (it's zero unless $r=0$, in which case it's a sum of $1$'s), but what about the first term? Differentiate $(*)$ and multiply by $z$ again to get another formula...

  • 0
    @nanme: You mean compute the Fourier transforms of various functions? There are many sources, though I'm not familiar with what's good for DFT's in particular (maybe a signal analysis text). Note that the formulas and derivations needed for *this* problem are given or hinted at in my answer - if you need further clarification don't be shy.2012-06-19
2

You are asking how to find the DFT of sequence of the form $y(k) = k^2 + bk + c$ for $k=0,1,2,\ldots$, and with $b$ and $c$ both constants. The DFT is a linear operator, so the DFT of the above is simply $\mathrm{DFT}(k^2) + b \cdot \mathrm{DFT}(k) + \mathrm{DFT}(c)$. There are countless derivations of these three DFTs available through google'ing.