Matlab Models - 2023.2 English

The figure below shows a block diagram of a 2D PFA transform. It’s corresponding Matlab model is shown immediately below. The algorithm consists of the following five steps:

• An input permutation is applied to the input data. The specific input permutation depends on the values of the relative prime factors $N_1$ and $N_2$ as outlined below.

• The data is organized into an $N_2 \times N_1$ matrix and 1D FFT’s are performed along the rows of that matrix.

• A “matrix transpose” operation converts the data flow from “row-wise” to “column-wise” ordering for the subsequent column-based transforms. This amounts to delivering the data using a “strided” addressing pattern.

• A second set of 1D FFT’s are performed along the columns of the original matrix.

• An output permutation is applied to the output data after being read column-wise out of its 2D matrix form. The specific output permutation depends on the values of $N_1$ and $N_2$ as outlined below.

The Matlab code below shows all of these five steps clearly. The routine compute_perm_2d() computes the input permutation P_i and output permutation P_o applied based on the values of $N_1$ and $N_2$.

function [sig_o] = fft_pfa_2d( sig_i, N1, N2 )
    [P_i,P_o,N] = compute_perm_2d(N1,N2);
    % Input permutation
    data = reshape(sig_i(1+P_i),N2,N1);
    % Row transform
    for rr = 1 : N2
      data(rr,:) = fft(data(rr,:));
    end
    % Col transform
    for cc = 1 : N1
      data(:,cc) = fft(data(:,cc));
    end
    % Output permutation
    data_o = reshape(data,1,[]);
    sig_o(1+P_o) = data_o;
end

The figure below shows a block diagram of a 3D PFA transform. It’s corresponding Matlab model is shown immediately below. The algorithm consists of the same steps similar to the 2D case above with the following differences:

• The I/O permutations now depend on three relatively prime factors $N_1$, $N_2$ and $N_3$. The mathematics specific to these 2D and 3D permutations is given in detail below.

• The data is now organized in a $N_1 \times N_2 \times N_3$ cube instead of an $N_1 \times N_2$ rectangle. Transforms are taken in 1D along each of these dimensions in order, first along $N_1$, then along $N_2$ and finally along $N_3$.

• The “matrix transpose” operations required to extract data in the $N_2$ and $N_3$ dimensions involve slightly more complicated “stride” patterns. These patterns are computed by the Matlab routine compute_addr_3d.m.

function [sig_o] = fft_pfa_3d( sig_i, N1, N2, N3 )
    [P_i,P_o,N] = compute_perm_3d(N1,N2,N3);
    % Input permutation:
    data = reshape(sig_i(1+P_i),N1,N2,N3);
    % Transforms
    for cc = 1 : N2
      for dd = 1 : N3
        data(:,cc,dd) = fft(data(:,cc,dd));
      end
    end
    for rr = 1 : N1
      for dd = 1 : N3
        data(rr,:,dd) = fft(data(rr,:,dd));
      end
    end
    for rr = 1 : N1
      for cc = 1 : N2
        data(rr,cc,:) = fft(data(rr,cc,:));
      end
    end
    % Output permutation:
    data_o = reshape(data,1,[]);
    sig_o(1+P_o) = data_o;
end

The full suite of Matlab models illustrating the operation of the PFA transforms is given in the matlab folder of the repo.