3
$\begingroup$

I would like to add multiple sequences with different FFT/IFFT sizes. For instance, we have 3 vector signals, $\vec{x_1}$, $\vec{x_2}$, and $\vec{x_3}$, having FFT/IFFT sizes of 512, 1024, and 2048, respectively (i.e., the 3 vectors have different lengths). Especially, they do not overlap each other in the frequency domain (i.e., allocated in non-overlapping set of frequency bins). According to my readings, I should choose a common size of FFT/IFFT to add the signals together? Please correct me if I was wrong.

Thank you for your help.

$\endgroup$
2
  • $\begingroup$ Zero-padding and doing a same size of FFT, adding in the frequency domain and then IFFT will give you the same result as just adding them in the time domain. $\endgroup$
    – ZR Han
    Nov 30, 2021 at 8:12
  • $\begingroup$ Thank you, I think zero-padding is the way. $\endgroup$ Nov 30, 2021 at 14:02

2 Answers 2

2
$\begingroup$

Do you meant something like this?

clear all;
close all;

N1 = 512;
N2 = 1024;
N3 = 2048;

N4 = 2*max(N3, max(N2,N1))

x1 = zeros(N4);
x2 = zeros(N4);
x3 = zeros(N4);

x1 = rand(1,N1);
x2 = rand(1,N2);
x3 = rand(1,N3);

X1 = fft(x1, N4);
X2 = fft(x2, N4);
X3 = fft(x3, N4);

X4 = [X1 X2 X3];

$\vec{x_1}$, $\vec{x_2}$ and $\vec{x_3}$ can have an actual data

$\endgroup$
3
  • $\begingroup$ Nice jomega. I think he means x4 = X1 + X2 + X3 in your solution? Also there is no reason for the lines x1 = zeros(N4) etc since you just write over those with the lines where you create the random vectors. The fft will zero pad on its own by assigning the fft length N4. $\endgroup$ Nov 30, 2021 at 11:52
  • 1
    $\begingroup$ Sure fft will zero-pad the input but I want to give an impression (kind of redundant) about the lengths of the input vectors. Summing up the spectrum is the OP question but I want to ask OP about non-overlapping with [X1 X2 X3] and the next step could be adding the spectrum. $\endgroup$
    – jomegaA
    Nov 30, 2021 at 12:10
  • $\begingroup$ Thank you. I mean somethings like x1 = ifft(x1,N1); x2 = ifft(x2,N2); x3 = ifft(x3,N1); How to perform x4 = x1 + x2 + x3 with nonoverlapping frequency domain $\endgroup$ Nov 30, 2021 at 14:06
1
$\begingroup$

I assume the OP has the FFT results, with different sizes, and from that alone wants to create the FFT result we would get if we added the time domain samples of those original signals.

Assuming the sampling rate of the time domain samples was the same (and we just have longer durations), we could simply take the inverse FFT of each, zero pad the time domain samples to be the same length, and then add the resulting vectors sample by sample, and then FFT that to get the frequency domain result.

Is there a more efficient solution to this? I haven't yet found one. I realized my previous answer to this ended up reducing to simply doing this (in a very long roundabout way), but it does offer some interesting DFT properties so will leave that result here (and in case it can lead to further improvement).

My solution was to interpolate the DFT result directly such that the time domain signal would be zero padded (zero padding in the time domain interpolates more samples in between the existing ones in the frequency domain). If we can do that easily, we can then add these DFT results directly in the frequency domain to achieve the OP's desired result.

Following this process, an interpolated DFT is samples on the DTFT (Discrete Time Fourier Transform in contrast to Discrete Fourier Transform), and can be determined by circular convolution of the DFT samples with the Dirichlet Kernel (as @DSPRookie describes in great detail here). The simplest approach to do just that is to take the FFT of a zero padded rectangular window to get the Dirichlet Kernel and then use FFT's to do the circular convolution. Doing just this ends up being a very long winded way of saying take the inverse FFT, zero pad and then take the FFT, which is the approach given in my second paragraph (ugh!).

Interpolating the Frequency Domain to Get a Zero Padded Time Domain

To follow this with an approach in the frequency domain with two FFT's one shorter as $X_1[k]$ of length $M$ and the longest as $X_2[k]$ of length $N$, we interpolate the $M$ samples of the shorter FFT $X_1[k]$ out to length $N$ by doing a zero insert and then circular convolution with the Dirichlet Kernel $D[k]$ of length $N$. (we would do this with all shorter length FFT's in order to add directly with the longest FFT to get the OP's desired result). Circular convolution of two generic signals $x$ and $y$ is done efficiently using:

$$x\circledast y = \text{ifft}\{ \text{fft}\{ x \} (\text{fft}\{ y \})^* \} \label{1}\tag{1}$$

Where $\circledast$ represents circular convolution and $()^*$ represents conjugation. So in our case, $x$ is the Dirichlet Kernel $D[k]$ which is the FFT of a zero padded rectangular window ($M$ samples zero-padded out to $N$ samples) and $y$ is $X_1[k]$ with zero-inserts out to length $N$, which I will now refer to as $\hat X_1[k]$:

$$X_1[k] = [X[0], X[1], X[2] ,\ldots], \space\space\space k = 0\ldots M-1$$

$$\hat X_1[k] = [X[0], (N/M-1 \text{ zeros}), X[1], (N/M-1 \text{ zeros}), X[2] ,\ldots],\space\space\space k = 0 \ldots N-1$$

Rewriting \ref{1} for interpolating our signal $X_1[k]$ in the frequency domain including scaling the result by dividing by the length of the shorter sequence results in:

$$D[k]\circledast \hat X_1[k] = \text{ifft}\{ \text{fft}\{ D[k] \} (\text{fft}\{ \hat X_1[k] \})^* \}/M \label{2}\tag{2}$$

It can be shown that the following is equivalent to \ref{2}, where we swap operations of FFT and inverse FFT:

$$D[k]\circledast \hat X_1[k] = \text{fft}\{ \text{ifft}\{ D[k] \} (\text{ifft}\{ \hat X_1[k] \})^* \}\times M \label{3}\tag{3}$$

But here we see the great simplification that brings us back to just doing what I laid out in my second paragraph: $\text{ifft}\{ D[k] \} $ is simply an array of $M$ ones zero padded out to a total length $N$, and this is multiplied by the inverse FFT of $\hat X_1[k] $, which was a zero-inserted $X[k]$. Doing zero inserts in frequency creates repetition in time, so $\text{ifft}\{ \hat X_1[k] \}$ is $\text{ifft}\{ X_1[k] \} $ repeated in time for every zero inserted. But $\text{ifft}\{ D[k] \} $ masks this to create $\text{ifft}\{ X_1[k] \} $ zero padded out to length $N$! So this is saying my approach of interpolating samples in the frequency domain to create the equivalent of what would be a zero padded vector in the time domain was to do just that: inverse FFT the original frequency domain sequence, zero pad it, and take the FFT of that.

So the question remains, is there a more efficient approach to doing frequency interpolation of the DFT result that is better than IFFT, zero pad, FFT? Perhaps this is a separate question to ask.

$\endgroup$
1
  • $\begingroup$ You explained the method comprehensively. Thank you. After reading several references, I believe the frequency interpolation is the good way. $\endgroup$ Dec 3, 2021 at 15:41

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.