Optimal time-distributed fast Fourier transform: Application to online iterative learning control-experimental high-speed nanopositioning example

In this paper, an optimal time-distributed fast Fourier transform algorithm and a time-distributed inverse fast Fourier transform (OTD-FFT/TD-IFFT) algorithm are proposed. This work is motivated by the need to implement FFT/IFFT online on general microprocessors (e.g., Intel's x86 microprocessors) in control applications and signal processing, for example, online implementation of frequency domain iterative learning control (FD-ILC) techniques. In these applications, the conventional FFT algorithm executes all the calculations within one single sampling period, thereby, becoming the bottleneck in online implementations of signal processing and control algorithms. In the proposed OTD-FFT technique, the FFT computation of an online sampled data sequence is optimally distributed among all the sampling periods without increasing the total computational complexity, arriving at the minimal per-sampling-period computational complexity. As a result, the entire Fourier transformed sequence is obtained without latency. The proposed approach is extended to online IFFT computation, and then applied to online FD-ILC implementation. The computational complexity analysis shows that by using the proposed approach, the per-sampling-period computational complexity is substantially reduced. The efficacy of the proposed OTD-FFT/TD-FFT for online implementation of FD-ILC technique is demonstrated through experiments of high-speed trajectory tracking on a piezoelectric actuator.