7
$\begingroup$

I've heard a million times that applying DFT twice will result in a reversed array, but that is not what actually happens. Instead, the first element remains where it was, and the rest of the elements are reversed. Is there an intuitive reason for that?

Octave code:

N = 16;
x = linspace(1, N, N);

fft(fft(x)) / N

Result:

1   16   15   14   13   12   11   10    9    8    7    6    5    4    3    2
$\endgroup$
2
  • 6
    $\begingroup$ You have heard a million false statements, or more like likely, you have misinterpreted what you were told. Applying the DFT twice to $x[n]$ gives $x[-n]$ (and so $x[-0] = x[0]$) showing that $x[0]$ stays in place. $\endgroup$ Nov 7 '20 at 14:44
  • 2
    $\begingroup$ all that is true @DilipSarwate but Pliny has to first accept that there is such a thing as $x[-n]$ and the inherent periodicity of the DFT. once he/she accepts that fact, then it is obvious that the reversal keeps $x[0]$ in the same place. $\endgroup$ Nov 7 '20 at 18:06
10
$\begingroup$

The sequence is exactly what you should expect:

$$x[-n]=x[N-n]\tag{1}$$

Clearly, for $n=0$ $x[n]$ and $x[-n]$ have the same value.

It seems like you were expecting to see the sequence $x[N-1-n]$ instead of $x[N-n]$. If you wanted that sequence you would need to modulate the result of the first DFT:

N = 16;
x = 1:N;
c = exp(-1i*2*pi/N*(0:N-1));
x2 = real( fft( ( fft(x) .* c ) ) ) / N;    % real() just to remove rounding errors
x2 =

  16  15  14  13  12  11  10  9  8  7  6  5  4  3  2  1
$\endgroup$
7
$\begingroup$

Yes reversed (!) but not in the programming sense !

The sequence $N \cdot x[-n]$ which results after applying DFT twice to the N-point sequence $x[n]$ is a time-reversed (and amplitude scaled by $N$) sequence indicated by the minus sign in its argument.

Remembering from your math courses, a function with a negated argument such as $f(-t)$ means the function $f(t)$ is flipped about the (vertical) y-axis.

Then the seqence $x[-n]$ is also flipped about the y-axis, hence reversed. This reversal, however, is special in the sense that it's a circular reversion (a DFT sequence reversion) indicated by the modulus notation :

$$ x[-n] = x[ (-n)_N ] $$

And for the range $0 \le n < N$ , the modulus expands like :

$$ x[(-n)_N] = x[ N- n ] .$$

Note that you can avoid the modulus operator, and reach the same conclusion by simply interpreting the DFT sequence $x[n]$ to be a periodic sequence $\tilde{x}[n]$. Then $\tilde{x}[-n]$ will be the reversed sequence.

$\endgroup$
7
$\begingroup$

Using the duality property of the Fourier transform, you have that $$x[n] \overset{\mathcal F}{\longleftrightarrow}X[k]\implies X[n] \overset{\mathcal F}{\longleftrightarrow} \begin{cases}Nx[N - k] & \text{for} & k = 1, \ldots, N -1 \\Nx\left[(k)_N\right]&\text{for}&k = 0\end{cases}$$

You have then:

\begin{align} X[0] & = Nx[0]\\ X[1] & = Nx[N - 1]\\ X[2] & = Nx[N - 2]\\ \vdots &\qquad \vdots\\ X[N-1] & = Nx[1]\\ \end{align}

Which, to the factor $N$, is the sequence you have with $k = 0, \ldots, 15$.

$\endgroup$

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.