# What is the general formula for stacked DFT on the same signal?

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?

• DFT is a 4th root of the identity map and a 2nd root of the (time-)reversal map. You go from here. Commented Jul 18, 2021 at 22:49
• Does this answer your question? How do you interpret FFT of an FFT of a discrete signal? Commented Jul 18, 2021 at 22:49
• 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. Commented Jul 18, 2021 at 23:54
• 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. Commented Jul 19, 2021 at 1:39

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))

• 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}$$ Commented Jul 18, 2021 at 23:51
• @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. Commented Jul 19, 2021 at 1:17
• 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? Commented Jul 19, 2021 at 1:32
• @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$. Commented Jul 19, 2021 at 1:38