Application of Pre-corrected FFT in Statistical Power Analysis considering spatial correlations

In this paper, we introduce the Pre-corrected FFT (PFFT) algorithm in Statistical Power Analysis of CMOS ICs. We implemented PFFT to compute the Matrix Vector Product (MVP), resulted from the process of deducing the standard deviation of leakage current. To analyze power consumption statistically in a chip of N gates, the application of PFFT can reduce the computation complexity from O(N 2 )to O(Nlog 2 N). While maintaining an acceptable errors (less than 1%), the proposed method can dramatically accelerating the computation.