Parallel implementation of multidimensional transforms without interprocessor communication

This paper presents a modular algorithm which is suitable for computing a l arge class of multidimensional transforms in a general purpose parallel env ironment without interprocessor communication. Since it is based on matrix- vector multiplication, it does not impose restrictions on the size of the i nput data as many existing algorithms do. The method is fully general since it does not depend on the specific nature of the transform kernel and, the refore, it may be used for a wide variety of transforms. Moreover, since so me one-dimensional Fast Fourier Transform algorithms map the input sequence onto two or more dimensions, the new method also may be employed to effici ently compute the 1D FFT in parallel. In addition, the proposed algorithm i s exploited to derive a fully systolic VLSI architecture performing multidi mensional transforms, which does not need the transposer required by classi cal architectures.