1
$\begingroup$

Let us assume a finite, aperiodic signal $x[n]$ upon which we perform DFT n times, as such:

DFT{DFT{DFT{...{DFT{$x[n]$}}...}

How can we calculate this directly instead of applying the DFT n times?

$\endgroup$
4
  • 2
    $\begingroup$ DFT is a 4th root of the identity map and a 2nd root of the (time-)reversal map. You go from here. $\endgroup$
    – Jazzmaniac
    Jul 18 '21 at 22:49
  • 1
    $\begingroup$ Does this answer your question? How do you interpret FFT of an FFT of a discrete signal? $\endgroup$
    – AlexTP
    Jul 18 '21 at 22:49
  • $\begingroup$ there are two issues. one is that DFT doesn't really give a rat's ass whether the original finite segment of signal was periodic or not. it makes it periodic by periodically extending it. $$ x[n+N] = x[n] \qquad \forall n \in \mathbb{Z} $$ The other issue is about scaling the DFT. There is a version of the DFT in which you need not worry about growth of energy every time it's applied. $\endgroup$ Jul 18 '21 at 23:54
  • $\begingroup$ here's something that will spell out what options you have regarding scaling. look at the "unitary" scaling convention of the DFT. that might be helpful for expressing what you are doing. $\endgroup$ Jul 19 '21 at 1:39
1
$\begingroup$

Let $\text{DFT}_2 = \text{DFT}(\text{DFT}(...))$. Then,

$$ \begin{align} \text{DFT}_2(x[n]) &= N \cdot x[-n] \\ \text{DFT}_3(x[n]) &= N \cdot \text{DFT}(x[-n]) \\ \text{DFT}_4(x[n]) &= N^2 \cdot x[n] \end{align} $$ and thus

$$ \text{DFT}_M(x[n]) = N^{\lfloor M/2 \rfloor} \cdot \begin{cases} \sum_{n=0}^{N-1} x[n\cdot (-1)^{\lfloor M/2 \rfloor}] e^{-j2 \pi k n /N}, & M=\text{odd} \\\ x[n\cdot(-1)^{\lfloor M/2 \rfloor}], & M=\text{even} \end{cases} $$

Note that $\text{DFT}_4(x[n])/N^2 = x[n]$.

Testing

import numpy as np
from numpy.fft import fft


def dft(x):
    N = len(x)
    out = np.zeros(N, dtype='complex128')
    for k in range(N):
        for n in range(N):
            out[k] += x[n] * np.exp(-2j*np.pi * k * n / N)
    return out

def dft_M(x, M=1):
    N = len(x)
    sign = (-1)**(M//2)

    if sign == -1:
        x_flip = np.zeros(N, dtype=x.dtype)
        x_flip[0] = x[0]
        x_flip[1:] = x[1:][::-1]
        x = x_flip

    if M % 2 == 0:
        out = N**(M//2) * x
    else:
        out = N**(M//2) * dft(x)
    return out


for N in (128, 129):
    x = np.random.randn(N) + 1j*np.random.randn(N)
    assert np.allclose(fft(x), dft(x))

    assert np.allclose(fft(fft(x)), dft_M(x, 2))
    assert np.allclose(fft(fft(x)), dft_M(x, 2))
    assert np.allclose(fft(fft(fft(x))), dft_M(x, 3))
    assert np.allclose(fft(fft(fft(fft(x)))), dft_M(x, 4))
$\endgroup$
4
  • $\begingroup$ Since you are breaking it out to $M$ even and $M$ odd, I might express it as $$ \mathcal{DFT}_M \Big\{x[n] \Big\} = \begin{cases} N^{(M-1)/2} \ \sum\limits_{n=0}^{N-1} x \big[n\cdot (-1)^{ (M-1)/2} \big] e^{-j2 \pi k n /N}, & M \ \text{odd} \\ \\ N^{M/2} \cdot x \big[n\cdot(-1)^{M/2} \big], & M \ \text{even} \\ \end{cases} $$ you won't really need the $\lfloor$ floor $\rfloor$ operator. And you do really have to confirm that $x[\cdot]$ is periodic with period $N$. $$ x[n+N] = x[n] \qquad \forall n \in \mathbb{Z} $$ $\endgroup$ Jul 18 '21 at 23:51
  • $\begingroup$ @robertbristow-johnson We get $n \cdot i$ without floor, and fractional powers of $N$ (latter's valid depending on normalization). As for periodicity... sure, if we want to interpret it in terms of an infinite continuous-time function. $\endgroup$ Jul 19 '21 at 1:17
  • $\begingroup$ if you look, there are no fractional powers of $N$ in the expression in my comment. the reason why something like periodicity needs to be explicit is because sometimes you have $x[-n]$. how are you gonna define the meaning of $x[-5]$ or similar? $\endgroup$ Jul 19 '21 at 1:32
  • 1
    $\begingroup$ @robertbristow-johnson Right, I missed that @ frac. On $-n$, absolutely, we define it to extend periodically - I meant on between $0$ and $N-1$, or inferring on $x(t)$ without having samples outside $0$ and $N-1$. $\endgroup$ Jul 19 '21 at 1:38

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.