# Can a FFT be decomposed into multiple parallel channels?

Suppose I have a data stream that is sampled at a certain frequency, i.e. 1 GHz. I now want to perform a FFT on that data stream but since the hardware I have is limited to a maximum clock frequency of 250 MHz the data arrives in packets of 4. In other words, each clock-cycle, 4 different samples arrive. Is it possible to use 4 parallel FFT's to accomplish this?

Now I know that nothing can stop me from simply doing that, so my question is if I loose any precision in frequency? Each FFT only operates on 250 MHz so my fear is that the highest frequency that I can safely measure w.r.t. to Shannons's theorem is only 125 MHz compared to 500 MHz

So, decomposing a large DFT into smaller DFTs, where some computations are redudant, is exactly the trick the Cooley-Tukey algorithm uses. So, your FFT is already doing that internally, and I doubt you'll write a better FFT. 4 parallel FFTs aren't sufficient - you need a butterfly structure afterwards to combine them again. (your considerations with the four 250 MHz streams¹ spots the fact that your original signal has a bandwidth of 1 GHz, so if you just do an FFT on every fourth sample, you'll have aliasing; the butterfly effectively is a mathematical way to cancel that aliasing using the info from the other three FFTs.)

¹ what's wrong about your consideration is that your Nyquist bandwidth == sampling rate for all practical purposes, since the DFT deals with complex signals, not only real signals.

• Thank you for the answer! I should have elaborated more; I currently have an FFT implementation that I can use, it just doesn‘t allow me to enter samples parallel. So if I understand you correctly, what I need to do is add a final butterfly-stage at the end of the chain? Could I also instead simply double the length and pad with zeroes or some other trickery like that? Jan 5, 2022 at 18:09
• @Marcua- but is the OP’s data real or complex? If the data is real and there indeed is only one real channel per ADC then I think this point is mute since the resulting data will be complex conjugate symmetric and the OP’s consideration is not wrong. Or am I wrong? Jan 5, 2022 at 21:13
• you're not wrong! Let me think about this, I think the cancellation becomes easier, because it just becomes swapping real and imaginary part, but you're rightt. Jan 5, 2022 at 22:22

I have assembled a little python script that displays @Marcus's solution. I wanted to share this as proof of concept on how this works for anyone that is stuck on the same problem that I was.

The reason I need to use four separate channels is because I am working on an FPGA implementation that includes an FFT. I cannot choose an implementation that processes data in parallel but the data that I get always arrives in packets of 4.

Any improvements to this method are appreciated

from numpy.fft import fft, fftshift
import numpy as np
import matplotlib.pyplot as plt

size = 2048
n = np.arange(size)
x = np.e ** (-2j * np.pi * 0.3 * n) # some arbitrary data
N = 4 # the amount of channels
x_i = [x[idx::N] for idx in range(N)] # The data, rearranged for the channels

def bf_2(even, odd):
"""
2-point butterfly implementation
"""
points = len(even) + len(odd)
def w(k):
return np.e ** (-2j * np.pi * k / points)
twiddles = w(np.arange(points/2))
odd = odd * twiddles
even_ret = even + odd
odd_ret = even - odd
return np.concatenate([even_ret, odd_ret])

def bf_4(x0, x1, x2, x3):
"""
four-point butterfly implementation
"""
res_1 = bf_2(x0, x2) # equivalent to bit-reverse ordering
res_2 = bf_2(x1, x3) # equivalent to bit-reverse ordering
return bf_2(res_1, res_2)

# Compute four separate FFT's
A_i = map(fft, x_i)

# And re-assemble them using the butterfly-structure
x_restored = bf_4(*A_i)

mag = np.abs(x_restored)
f = np.linspace(-0.5, 0.5, len(mag))
plt.plot(f, fftshift(mag))
plt.show()