# Consistency in definition of Fast Fourier Transform

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?

• I have not checked it, but maybe the difference (if there is any) relates to the "shifting" that is required to move the origo of the transform. In Matlab we sometimes need to use "fftshift" and "ifftshift" to get the zero frequency coefficient to be where we want it to be. Mar 22, 2022 at 20:07
• I think it should be $Y(k)=\sum_{j=1}^n \dots$, so the index $j$ goes form $1$ not from $0$. Mar 22, 2022 at 22:48
• Also, the convention for what is the forward and what the inverse transform seems to be switched. Usually the positive sign in the exponent is associated with the reconstruction or inverse transform, the negative sign with the coefficient computation in the forward transform. This is correct in the matlab case. Mar 23, 2022 at 3:53
• @Salfalur You're right. Sorry for the typo. I'll correct it now.
– user95199
Mar 23, 2022 at 3:55

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}}.$$
• At the point were you introduce $W_n$ in the long equation chain you lose a sign in the exponent. The order should stay as in the exponent before, $W_n^{k(m-j)}$. Mar 26, 2022 at 9:00
• @LutzLehmann, you are totally right. Oh man, i tried to fix that mistake, but it leads always to $W_n^{-kj}$. So maybe, (as in your comment described) Faires also switched the inverse and the 'normal' DFT. Thanks for pointing out my mistake. Mar 28, 2022 at 10:26