fftmi#

Purpose#

Computes a multi-dimensional inverse FFT.

Format#

y = fftmi(x, dim)#
Parameters:

  • x (Mx1 vector) – data.

  • dim (Kx1 vector) – size of each dimension.

Returns:

y (Lx1 vector) – inverse FFT of x.

Examples#

Here’s an example, this time working with a 2x3x2x3 hypercube. The variable dim contains the dimensions of x, beginning with the highest dimension. The last element of dim is the number of columns, the next to the last element of dim is the number of rows, and so on. Thus

dim = { 2, 3, 3 };

indicates that the data in x represents is a 2x3x3 three-dimensional array, i.e., two 3x3 matrices of data.

Suppose that x1 is the first 3x3 matrix and x2 the second 3x3 matrix, then:

x = vecr(x1)|vecr(x2)

The size of dim tells you how many dimensions x has.

// Set dimensions of array
dim = { 2, 3, 2, 3 };

/*
** Assign matrices to place in
** first cube
*/
let x1_1[2, 3] = 1 2 3 4 5 6;
let x2_1[2, 3] = 6 5 4 3 2 1;
let x3_1[2, 3] = 1 2 3 5 7 11;

/*
** Form cube one by using vecr
** to vectorize x1_1, x2_1, x3_1
** then vertically concatenating
** the results
*/
xc1 = vecr(x1_1)|vecr(x2_1)|vecr(x3_1);

This results in three 2x3 matrices, x1_1, x2_1, and x3_1 and an 18x1 vector xc1:

x1_1 = 1.0000   2.0000   3.0000   x2_1 = 6.0000   5.0000   4.0000   x3_1 = 1.0000   2.0000   3.0000
       4.0000   5.0000   6.0000          3.0000   2.0000   1.0000          5.0000   7.0000  11.0000

xc1 = 1.0000
      2.0000
      3.0000
      4.0000
      5.0000
      6.0000
      6.0000
      5.0000
      4.0000
      3.0000
      2.0000
      1.0000
      1.0000
      2.0000
      3.0000
      5.0000
      7.0000
      11.0000

To assign the second cube we will leave out the vecr() step. Instead we will construct x1, x2, and x3 as vectors to using let.

/*
** Assign matrices to place in
** second cube
*/
x1_2 = { 1, 1, 2, 3, 5, 8 };
x2_2 = { 1, 2, 6, 24, 120, 720 };
x3_2 = { 13, 17, 19, 23, 29, 31 };

/*
** Form cube two
** by vertically concatenating
** the x1_2, x2_2, and x3_2
** vectors
*/
xc2 = x1_2|x2_2|x3_2;

This results in three 6x1 vectors x1_2, x2_2, and x3_2 and an 18x1 vector xc2: We will concatenate xc1 and xc2 and use fftm() to find the Fourier Fast Transform:

// Hypercube
xh = xc1|xc2;
xhfft = fftm(xh, dim);

dimi = { 2, 4, 2, 4 };
xhffti = fftmi(xhfft, dimi);

The arrays have to be padded in each dimension to the nearest power of two. Thus the output array can be larger than the input array.

In this example, xh is an 36x1 vector and xhfft is a 64x1 vector. This is because in the case of the 2x3x2x3 hypercube example, x is padded from 2x3x2x3 out to 2x4x2x4. Hence, the input vector contains 36 elements, while the output vector would contain 64 elements. You may have noticed that we use a dim with padded values at the end of the example to check our answer.

Remarks#

The multi-dimensional data are laid out in a recursive or hierarchical fashion in the vector x. That is to say, the elements of any given dimension are stored in sequence left to right within the vector, with each element containing a sequence of elements of the next smaller dimension. In abstract terms, a 4-dimensional 2x2x2x2 hypercubic x would consist of two cubes in sequence, each cube containing two matrices in sequence, each matrix containing two rows in sequence, and each row containing two columns in sequence. Visually, x would look something like this:

\[\begin{split}X\_hyper = X\_cube1|X\_cube2\\ X\_cube1 = X\_mat1|X\_mat2\\ X\_mat1 = X\_row1|X\_row2\\\end{split}\]

Or, in an extended GAUSS notation, x would be:

Xhyper = x[1,.,.,.] | x[2,.,.,.];
Xcube1 = x[1,1,.,.] | x[1,2,.,.];
Xmat1 = x[1,1,1,.] | x[1,1,2,.];
Xrow1 = x[1,1,1,1] | x[1,1,1,2];

To be explicit, x would be laid out like this:

x[1,1,1,1] x[1,1,1,2] x[1,1,2,1] x[1,1,2,2]
x[1,2,1,1] x[1,2,1,2] x[1,2,2,1] x[1,2,2,2]
x[2,1,1,1] x[2,1,1,2] x[2,1,2,1] x[2,1,2,2]
x[2,2,1,1] x[2,2,1,2] x[2,2,2,1] x[2,2,2,2]

If you look at the last diagram for the layout of x, you’ll notice that each line actually constitutes the elements of an ordinary matrix in normal row-major order. This is easy to achieve with vecr(). Further, each pair of lines or matrices constitutes one of the desired cubes, again with all the elements in the correct order. And finally, the two cubes combine to form the hypercube. So, the process of construction is simply a sequence of concatenations of column vectors, with a vecr() step if necessary to get started.

Source#

fftm.src

See also

Functions fft(), ffti(), fftn()

On this page
Show Source