The MSC FFT

Today I want to introduce the multi-path serial commutator (MSC) FFT. This type of architecture is the parallel version of the serial commutator (SC) FFT.

We proposed the SC FFT in 2016 in the paper:

Mario Garrido, Shen-Jui Huang, Sau-Gee Chen and Oscar Gustafsson, “The Serial Commutator (SC) FFT”, IEEE Trans. Circuits Systems II, Vol. 63, No. 10, pp. 974-978, Oct. 2016 (Open Access).

The SC FFT solved the challenge of designing a serial FFT with minimum number of butterflies and 100% utilization of them. Until the SC FFT was proposed, FFT architectures did not utilize butterflies fully. This was very noticeable in the case of the single-path delay feedback (SDF) FFT, which had 50% utilization of butterflies in case of radix-2 and 25% utilization in case of radix-4.

The SC FFT solved this issue by including circuits that reorder data arriving in series. This allowed for placing in consecutive clock cycles pairs of data that must be computed together in the butterflies. This way, the butterflies do not longer have to wait for a many clock cycles to gather data. This waiting time is what caused the low utilization, but was removed with the SC FFT.

Additionally, the SC FFT had another key advantage. In the SC FFT, rotations only must be calculated in samples arriving every other clock cycle. This way, rotators can take two clock cycles to calculate them, which halves the complexity of rotators.

Since we proposed the SC FFT, many works have continued this research line. Nowadays, there are efficient SC FFT architectures for real-valued FFT, as well as SC FFTs that reduce the hardware complexity of the original SC FFT.

Given the success of the SC FFT, a few years ago we thought that it could be interesting to explore an SC FFT for parallel data, the MSC FFT. As an initial work, we proposed an implementation for 128 points and 4 parallel data in the work:

Shun-Che Hsu, Shen-Jui Huang, Sau-Gee Chen, Shin-Che Lin and Mario Garrido, “A 128-Point Multi-Path SC FFT Architecture, IEEE International Symposium on Circuits and Systems, Sevilla (Spain), Oct. 2020.

Later, we decided to expand this inital design and analyze the MSC in depth for any radix-2^k and any parallelization. This analysis was presented last year in the paper:

Guang-Ting Deng, Mario Garrido, Sau-Gee Chen and Shen-Jui Huang, “Radix-2^k MSC FFT Architectures”, IEEE Access, 2023 (Open Access).

In this work, we observed that the MSC FFT can reduce the number of rotators and their complexity with respect to previous parallel FFT archictures. This occurs due to two reasons. First , the MSC keeps the advantage of the SC FFT of calculating rotations only every other clock cycle, which reduces the complexity of the rotators. Second, in the MSC FFT, rotations are grouped in sets, called symetric angle sets (SAS), in such a way that rotations in the same SAS can be easily calculated by symmetries in the complex plane at low hardware cost. By applying this idea, in the MSC FFT each rotator only rotates by angles in a few SAS, which results in low complexity.

To continue with the development of the MSC FFT, recently we have observed that some parts of the architecture can be further improved and simplified, leading to an even more efficient design. Nowadays, Zeynep Kaya is working on this line and we expect to submit a new paper in this topic in the following months.

This work has been carried out in the frame of the project "FPGA Implementation of Data-Intensive Algorithms: Neural Networks and FFT", APOYO-JOVENES-21-TL23SB-116-I4FOMC, funded by Comunidad de Madrid through the call "Ayudas de Estímulo a la Investigación de Jóvenes Doctores de la Universidad Politécnica de Madrid, 2021".