Consistency in definition of Fast Fourier Transform

Question

The book Numerical Analysis by Faires defines the fft of a signal $y_{j}$ as

$$a_{k}+ib_{k}=\frac{(-1)^{k}}{m}c_{k}$$

where

$$c_{k}=\sum_{j=0}^{2m-1}y_{j}e^{ik\pi j/m}$$

for each $k=0,1,...,2m-1$. How does this correspond to fft() as implemented in MATLAB? There, $Y=\text{fft}(X)$ is defined as

$$Y(k)=\sum_{j=1}^{n} X(j) W_{n}^{(j-1)(k-1)}$$

where $W_{n}=e^{-2\pi i / n}$, but I don't see the equivalence. Could somebody please show me how these relate in the case of a one-sided transform?

Answer 1

Some information at first. Don't be confused if some authors use other normalization factors for the (discrete) Fourier transform (something like the $1/m$ in front). So here Faires uses the normalization $1/m$ and matlab does not. There is no right or wrong, it is just a matter of convenience. The second thing, that we have to take care of is that the original FFT only works for even number of samples, therefore Faires uses $2m$ samples. The FFT is only a fast version of the DFT, which work also for arbitrary number of samples. So, matlab calculates the DFT (in a fast way), so it also excepts other input length. In the following we will work with $2m=n$. And last thing that we have to consider is that Faires introduces his DFT (or FFT) by approximating the integral $$\int_{-\pi}^\pi f(x)e^{-ikx}dx,$$ while matlab introduces it's DFT (or FFT) by approximating the integral $$\int_{0}^{2\pi} f(x)e^{-ikx}dx.$$ Clearly, both integrals are equal. But this integration over different intverals is the main reason, why those two DFT's look different.

At first we need to point out the different representations of a vector $x \in \mathbb C^{2m}$. In the case of Faires the vector $(x^+_k)_{k=0}^{2m-1}$, corresponds to some function values $f(-\pi+j\pi/m)$, with $j=0,\dots,2m-1$. While in case of matlab the vector $(x^-_k)_{k=1}^{2m}$, corresponds to some function values $f(j\pi/m)$, with $j=0,\dots,2m-1$. Note, matlab counts $k$ form $1$ to $2m=n$, Faires counts from $0$ to $2m-1=n-1$. The $+$ and the $-$ above the $x_k$ is only to make clear, in which way we want to represent that vector (Faires or matlab). We can now translate our vector $x^+$ into $x^-$, since $f$ corresponds to a $2\pi$-periodic function. Concrete does this mean $$(\underbrace{x^-_1,\dots x^-_{m}}_{\approx f ( [0,\pi])},\underbrace{x^-_m,\dots,x_{2m}^-}_{\approx f ( [\pi,2\pi]})=(\underbrace{x_m^+,\dots,x_{2m-1}^+}_{\approx f ( [0,\pi])},\underbrace{x_0^+,\dots,x_{m-1}^+}_{\approx f ( [-\pi,0])})$$

We can now show the equivalence of both terms. Let $W_n=e^{-2\pi i /n}$. We start with the DFT of Faires for $k= 0 , \dots , 2m-1$ and define $y^+$ as \begin{align*} y^+_k&=\frac{(-1)^k}{m}\sum_{j=0}^{2m-1}x^+_je^{ik\pi j/m}\\ &=\frac{e^{-i\pi k}}{m}\sum_{j=0}^{2m-1}x^+_je^{ik\pi j/m}\\ &=\frac{1}{m}\sum_{j=0}^{2m-1}x^+_je^{i\pi k( j-m)/m}\\ &=\frac{1}{m}\sum_{j=0}^{2m-1}x^+_je^{-2\pi ik( m-j)/(2m)}\\ &=\frac{1}{m}\sum_{j=0}^{2m-1}x^+_jW_n^{k(j-m)}\\ &=\frac{1}m\left [ \sum_{j=0}^{m-1}x^+_jW_n^{k(j-m)} + \sum_{j=m}^{2m-1}x^+_jW_n^{k(j-m)} \right ]\\ \,^{\text{index shift}} &=\frac{1}m\left [ \sum_{j=0}^{m-1}x^-_{j+m+1}W_n^{k(j-m)} + \sum_{j=m}^{2m-1}x^-_{j-m+1}W_n^{k(j-m)} \right ]\\ &=\frac{1}m\left [ \sum_{j=m}^{2m-1}x^-_{j+1}W_n^{k(j-2m)} + \sum_{j=0}^{m-1}x^-_{j+1}W_n^{kj} \right ]\\ \,^{W_n^{2km}=1}&=\frac{1}m\left [ \sum_{j=m}^{2m-1}x^-_{j+1}W_n^{kj} + \sum_{j=0}^{m-1}x^-_{j+1}W_n^{kj} \right ]\\ &=\frac 1 m \sum_{j=0}^{2m-1}x^-_{j+1}W_n^{kj}\\ \,^{\text{index shift and } 2m=n}&= \frac 1 m \underbrace{\sum_{j=1}^nx^-_{j}W_n^{k(j-1)}}_{:=y^-_{k+1}}. \end{align*} Putting things together yields now for $$\underbrace{y^+}_{\text{Faires}}=(y_0^+,\dots,y_{2m-1=n-1}^+)=\frac 1 m (y_1^-,\dots,y_{2m=n}^-)=\frac 1 m\underbrace{y^-}_{\text{matlab}}.$$