suitable application for 2d FFT

I have been building a convolution library for multichannel audio and am using FFTW as the main FFT transform library. There are 4 channels of audio in play at any one time and they are interleaved, so one "frame" contains 4 separate samples - one from each channel.

I have been using the Real to Complex 2D functions up until now, but I am starting to be concerned that multichannel audio is perhaps not the right application for this - even though it fits with the documented data structure.

Should I be using 4 separate 1D transforms instead of a single 2D FFT pass?

• Use whichever is more efficient. Test it and judge yourself. I would prefer 1D for simplicity. Dec 19 '16 at 11:30
• I'm really trying to determine whether there is a technical reason why I shouldn't do this. The code I have at the moment is humming along nicely, but I am running into a few challenges implementing deconvolution in a similar manner. Does a 2D FFTW treat each "channel" as entirely separate, as if it is a separate unique FFT process across each channel, or is there interaction between the channels spectrally?
– Mark
Dec 19 '16 at 11:32

You should consider what you're doing.

Let me draw your audio data in the manner I understood it's in your memory. I'll call your channels A,B,C,D, and number their respective samples increasingly:

A0 B0 C0 D0 A1 B1 C1 D1 A2 B2 C2 D2 …

Now, if you want to apply a 2D FFT, your data needs to have the structure of 2D data – i.e. a matrix. You didn't quite specify, but I assume you've got a matrix

$$\mathbf S = \begin{pmatrix} A_0 & B_0 & C_0 & D_0\\ A_1 & B_1 & C_1 & D_1\\ A_2 & B_2 & C_2 & D_2\\ A_3 & B_3 & C_3 & D_3\\ \vdots & \vdots & \vdots & \vdots\\ A_{N-2} & B_{N-2} & C_{N-2} & D_{N-2}\\ A_{N-1} & B_{N-1} & C_{N-1} & D_{N-1}\\ \end{pmatrix}$$ And you're applying the $4\times N$ DFT (FFT):

\begin{align} \hat{\mathbf{S}} &= \text{DFT}_{4\times N}\left\{\mathbf S\right\}\\ &= \left(\frac1{\sqrt{4N}}\sum_{n=0}^N\sum_{m=0}^4 S_{n,m}\, e^{j2\pi\left(\frac{nk}N + \frac{ml}4\right)} \right)_{k,l}\tag1\\ &=\left(\frac1{2\sqrt N}\sum_{n=0}^N A_n e^{j2\pi\left(\frac{nk}N + 0\right)} + B_n e^{j2\pi\left(\frac{nk}N + \frac l4\right)} + C_n e^{j2\pi\left(\frac{nk}N + \frac {2l}4\right)} + D_n e^{j2\pi\left(\frac{nk}N + \frac {3l}4\right)} \right)_{k,l}\\ &=\left(\frac1{2\sqrt N}\sum_{n=0}^N A_n e^{j2\pi\frac{nk}N} + B_n e^{j2\pi\frac{nk}N} e^{j\frac12\pi l} + C_n e^{j2\pi\frac{nk}N} e^{j\pi l} + D_n e^{j2\pi\frac{nk}N} e^{j\pi \frac32 l} \right)_{k,l} \end{align}

Looking at the last line: you've got to ask yourself whether you really want to have the DFT over each of your 4-channel frames – that sounds intuitively wrong.

Look at eq. $(1)$: you can swap the summations; hence, it doesn't matter if you first take the FFT of every channel column vector in "time direction", and then the row-wise FFT of the resulting matrix in "channels direction", or first do the row-wise FFT over all four channels, and then over all times.

I think you really want 4 1D-FFTs of length $N$, and not one $N\times 4$ 2D-FFT.

Luckily, the advanced 1D-FFT real-to-complex API of FFTw makes it really easy to do four identical FFTs on interleaved data. I annotated the API with the values that seem to be apporpriate for your use case:

fftw_plan fftw_plan_many_dft_r2c(int rank, // Dimensionality == 1
const int *n,       // FFT input length == N
int howmany,        // Amount of FFTs == 4
double *in,     // pointer to A0
const int *inembed, // pad/truncate input ? No --> NULL
int istride,        // Distance between input elements that belong to the *same* FFT == 4
int idist,      // Distance between the first elements of different FFTs == 1
fftw_complex *out,  // pointer to output space
const int *onembed, // see above inembed
int ostride,        // same as above
int odist,      // same as above
unsigned flags);    // allow destruction of input buffer? Measure or guess the best algorithm?
• Thankyou Marcus. 4 x 1D FFTs it is. Back to the compiler...
– Mark
Dec 19 '16 at 13:06
• @Mark hope my edit helps Dec 19 '16 at 13:19
• I'm a novice at all of this - surprised I have managed to get as far as I have - so ploughing on until I hit the next brick wall. I'll be hitting you up for some advice on deconvolution soon!
– Mark
Dec 19 '16 at 13:20