現今在許多的數位訊號處理應用中，離散型傅立葉轉換(Discrete Fourier Transform, DFT)被廣泛地使用來分析訊號之功率頻譜密度。為取得較精細的時-頻譜分析結果，一種滑動式弦波轉換為基礎的方法被發展出來，作為短時間內提供足夠的頻譜資訊，例如：滑動式離散型傅立葉轉換(Sliding DFT, SDFT)與跳躍式離散型傅立葉轉換(Hopping DFT, HDFT)。然而，在現有的SDFT/HDFT演算法中多半存有穩定性、準確性及計算複雜度等潛在性問題。因此，如何有效克服上述問題便成了本文的發展重點。近年來，基於滑動程序之頻譜分析方式已從過去的單一維度漸漸地被延伸運用於多維度的訊號處理上，為了取得一較低的計算量，遞迴式計算方法相繼被提出，由於架構與傳統的單一維度SDFT架構相似，因此也意謂著會存有上述之潛在性問題。
本論文提出一個基於行/列二維離散傅立葉轉換(2-D DFT)概念與結合滑動視窗特性，推演出一新穎具前饋式路徑之2-D SDFT演算法，該演算法是採降維度方式及radix-r蝴蝶架構來加以實現，同時又不具有回饋路徑的計算方式，故能達到高穩定性、高準確性及低計算複雜度等性質。另外，本論文亦提出一個基於降維度概念來實現兼具前瞻性應用的2-D HDFT演算法，可進一步與現有的1-D HDFT演算法搭配使用。為了避免潛在性問題的發生，將採用radix-r蝴蝶架構來設計新穎1-D HDFT演算法。
各項評測條件設定如下：(1)滑動視窗(N)大小為16 × 16；(2)視窗時間跳躍(L)長度為2；(3)測試樣本為可適性視訊編碼(Scalable Video Coding, SVC) 灰階影像，影像格式則選用30 FPS的通用影像傳輸格式(Common Intermediate Format, CIF)與4倍通用影像傳輸格式(4 times Common Intermediate Format, 4CIF)；(4)複數乘法將等效於4個實數乘法與2個實數加法。根據評測結果，本論文所提出的2-D SDFT架構與最新由Park所提出的架構相比，在運算複雜度方面，實數乘法與實數加法分別減少43.8%及增加33%之運算量；在執行時間方面，完成CIF與4CIF 各自100幀影像處理所需時間相較於Park平均分別可節省10.8%與10.9%。綜觀整體效能比較，本論文所提出的架構相較於Park而言仍略勝一籌。在2-D HDFT運算複雜度評比上，本文架構相較於傳統VRFFT架構及Park的2-D SDFT架構，實數乘法運算量分別改善76.82%與67.28%；實數加法運算量分別改善62.93%與2.79%。執行時間量測上，CIF影像分別改善53.8%與31.4%；4CIF影像分別改善54%與31.6%。在核心1-D SDFT/HDFT之效能評比方面，計算複雜度相較於oSDFT架構，實數乘法僅增加2個常數運算量，實數加法則有16%改善量；相較於典型的HDFT架構，實數乘法運算量及實數加法運算量分別改善58.33%與增加3.45%。從整體結果顯示，本論文所提出的方法與架構將更有效與合適應用於即時性時頻分析轉換。此外，由於演算法是採降維度之方法，使得不僅可被用於計算1-D SDFT/HDFT，同時也可被用於求得2-D SDFT/HDFT之頻譜資訊，特別是在混合型應用之中。

In many applications of digital signal processing, Discrete Fourier Transform (DFT) has been widely employed to analyze the signal power spectral density (PSD). To observe the variety of time-frequency spectrum in details, a sliding sinusoidal transform, such as sliding DFT (SDFT) and hopping DFT (HDFT), is proposed to offer enough information in a short-time period. However, most of the existing SDFT/HDFT algorithms have the potential problems such as stability, accuracy, and computational complexity. Therefore, how to effectively overcome the above problems is the purposes of this work. Recently, the Fourier spectrum analysis based on the sliding transform process has been applied in multi-dimension signal processing. In order to gains the advantages of low computational complexity, the recursive calculation methods have been proposed. Because the 2-D structure is similar to the traditional 1-D SDFT one, it implies that there are the potential problems on 2-D issues.
Based on the concept of the row-column 2-D DFT and the property of the shifted window, we derive a novel forward-path 2-D SDFT algorithm in this work. This algorithm is implemented by using the descending dimension method (DDM) and the radix-r butterfly-based structure. Simultaneously, since the calculation method is without feedback loops, the properties of high-precision, high-stable, and low computational complexity can be easily achieved. Considering the prospective applications, a 2-D HDFT algorithm based on the same concept, i.e., the DDM is proposed in this work. The algorithm can be further realized by combining with the existing 1-D HDFT algorithm. In order to avoid the occurrence of potential problems, a novel radix-r butterfly-based 1-D HDFT algorithm is also proposed in this work.
For performance metrics, we set (1) the window size (N) to 16 × 16; (2) the number of time hops (L) to two; (3) the test pattern to SVC grayscale video, and the formats are CIF and 4CIF with 30fps; (4) one multiplication involves four real multiplication and two real additions. The evaluation results show the proposed 2-D SDFT method reduced the multiplications by 43.8% and increased the additions by 33% compared with the state-of-the-art Park’s method. For first 100 frames of the CIF and 4CIF sequences, the processing time of the proposed method can be, respectively, saved on average by 10.8% and 10.9% as compared to Par’s methods. Overall, the performance of the proposed architecture outperforms that of Park in computation. For the comparison of computational complexity in the 2-D HDFT process, the results show that the proposed algorithm reduces the number of real multiplications by 76.82% and 67.28% as compared to the VRFFT and 2-D SDFT, respectively. And, the number of real additions of the proposed algorithm is 62.93% and 2.79% less than those of the VRFFT and 2-D SDFT, respectively. Compared with the VRFFT and 2-D SDFT, the processing time of the proposed method can greatly save 53.8% and 31.4% on CIF sequences, save 54% and 31.6% on 4CIF sequences. For the kernel computation of 1-D SDFT/HDFT, the proposed method compared with oSDFT has two more multiplications, the numbers of additions can be saved by 16%. Compared with the typical HDFT structure, the numbers of multiplications can be improved by 58.33% and the numbers of additions is increased by 3.45%. The results show that it would be more efficient and more suitable than previous works for an instant time-frequency analysis. Moreover, the proposed DDM-based algorithms can be applied to calculate not only 1-D but also 2-D SDFT/HDFT spectrums, especially in a hybrid application.

[1] J. W. Cooley and J. W. Tukey, "An algorithm for the machine calculation of complex Fourier series," Mathematics of computation, vol. 19, no. 90, pp. 297-301, 1965.
[2] S. G. Johnson and M. Frigo, "A Modified Split-Radix FFT With Fewer Arithmetic Operations," IEEE Transactions on Signal Processing, vol. 55, no. 1, pp. 111-119, 2007.
[3] Y. Wen-Chang and J. Chein-Wei, "High-speed and low-power split-radix FFT," IEEE Transactions on Signal Processing, vol. 51, no. 3, pp. 864-874, 2003.
[4] S. Winograd, "On computing the discrete Fourier transform," Mathematics of computation, vol. 32, no. 141, pp. 175-199, 1978.
[5] Wikipedia contributors. Orthogonal frequency-division multiplexing. Available: https://en.wikipedia.org/w/index.php?title=Orthogonal_frequency-division_multiplexing&oldid=867089038
[6] W.-S. Hwang. MIMO-OFDM. Available: http://wshnt.kuas.edu.tw/network/n1/MIMO%20OFDM.htm
[7] E. ETSI, "201 980 V3. 1.1,“," Digital radio mondiale (DRM)-system specification," August, 2009.
[8] N. Sadeghi, V. C. Gaudet, and C. Schlegel, "Analog DFT Processors for OFDM Receivers: Circuit Mismatch and System Performance Analysis," IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 56, no. 9, pp. 2123-2131, 2009.
[9] C. Burrus and P. Eschenbacher, "An in-place, in-order prime factor FFT algorithm," IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 29, no. 4, pp. 806-817, 1981.
[10] G. Goertzel, "An algorithm for the evaluation of finite trigonometric series," American Math. Monthly, vol. 65, pp. 34-35, 1958.
[11] J.-F. Yang and F.-K. Chen, "Recursive discrete Fourier transform with unified IIR filter structures," Signal Processing, vol. 82, no. 1, pp. 31-41, 2002.
[12] F. Chih-Peng and S. Guo-An, "Novel recursive discrete Fourier transform with compact architecture," in The 2004 IEEE Asia-Pacific Conference on Circuits and Systems, 2004, vol. 2, pp. 1081-1084.
[13] V. Lan-Da and Y. Chih-Chyau, "High-speed area-efficient recursive DFT/IDFT architectures," in 2004 IEEE International Symposium on Circuits and Systems, 2004, vol. 3, pp. III-357.
[14] L. Van, Y. Yuan-Chu, H. Chun-Ming, and L. Chin-Teng, "Low computation cycle and high speed recursive DFT/IDFT: VLSI algorithm and architecture," in IEEE Workshop on Signal Processing Systems Design and Implementation, 2005., 2005, pp. 579-584.
[15] C. Fan and G. Su, "Efficient recursive discrete Fourier transform design with low round-off error," Int. J. Elect. Eng, vol. 13, no. 1, pp. 9-20, 2006.
[16] L.-D. Van, C.-T. Lin, and Y.-C. Yu, "VLSI architecture for the low-computation cycle and power-efficient recursive DFT/IDFT design," IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. 90, no. 8, pp. 1644-1652, 2007.
[17] S. Lai, S. Lei, C. Chang, C. Lin, and C. Luo, "Low Computational Complexity, Low Power, and Low Area Design for the Implementation of Recursive DFT and IDFT Algorithms," IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 56, no. 12, pp. 921-925, 2009.
[18] S. Lai, W. Juang, C. Chang, C. Lin, C. Luo, and S. Lei, "Low-Computation-Cycle, Power-Efficient, and Reconfigurable Design of Recursive DFT for Portable Digital Radio Mondiale Receiver," IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 57, no. 8, pp. 647-651, 2010.
[19] S. Lai, S. Lei, W. Juang, and C. Luo, "A Low-Cost, Low-Complexity, and Memory-Free Architecture of Novel Recursive DFT and IDFT Algorithms for DTMF Application," IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 57, no. 9, pp. 711-715, 2010.
[20] S. Lai et al., "Hybrid Architecture Design for Calculating Variable-Length Fourier Transform," IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 63, no. 3, pp. 279-283, 2016.
[21] A. V. Oppenheim and R. W. Schafer, Discrete-Time Signal Processing. Prentice Hall Press, 2009.
[22] E. Jacobsen and R. Lyons, "The sliding DFT," IEEE Signal Processing Magazine, vol. 20, no. 2, pp. 74-80, 2003.
[23] E. Jacobsen and R. Lyons, "An update to the sliding DFT," IEEE Signal Processing Magazine, vol. 21, no. 1, pp. 110-111, 2004.
[24] K. Duda, "Accurate, Guaranteed Stable, Sliding Discrete Fourier Transform," IEEE Signal Processing Magazine, vol. 27, no. 6, pp. 124-127, 2010.
[25] S. Lai, W. Juang, Y. Juan, C. Luo, and W. Tsai, "Low-Cost and Low-Complexity Sliding Discrete Fourier Transform Based on a Compact Recursive Structure for Real Input Sequence," in 2016 International Conference on Applied System Innovation (ICASI), 2016, pp. 1-4.
[26] W.-H. Juang, S.-C. Lai, C.-H. Luo, and S.-Y. Lee, "Extending the S.-C. Lai et al.’s Sliding DFT Approach: A Low-cost and Low-coefficient Architecture Design," in Internatinonal Computer Symposium 2018 (ICS 2018), 2018.
[27] S. Mishra, D. Das, R. Kumar, and P. Sumathi, "A Power-Line Interference Canceler Based on Sliding DFT Phase Locking Scheme for ECG Signals," IEEE Transactions on Instrumentation and Measurement, vol. 64, no. 1, pp. 132-142, 2015.
[28] P. Sumathi and P. A. Janakiraman, "Integrated Phase-Locking Scheme for SDFT-Based Harmonic Analysis of Periodic Signals," IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 55, no. 1, pp. 51-55, 2008.
[29] C. M. Orallo, I. Carugati, S. Maestri, P. G. Donato, D. Carrica, and M. Benedetti, "Harmonics Measurement With a Modulated Sliding Discrete Fourier Transform Algorithm," IEEE Transactions on Instrumentation and Measurement, vol. 63, no. 4, pp. 781-793, 2014.
[30] I. Carugati, C. M. Orallo, P. G. Donato, S. Maestri, J. L. Strack, and D. Carrica, "Three-Phase Harmonic and Sequence Components Measurement Method Based on mSDFT and Variable Sampling Period Technique," IEEE Transactions on Instrumentation and Measurement, vol. 65, no. 8, pp. 1761-1772, 2016.
[31] C. Park, "Fast, Accurate, and Guaranteed Stable Sliding Discrete Fourier Transform," IEEE Signal Processing Magazine, vol. 32, no. 4, pp. 145-156, 2015.
[32] C. Park, "Guaranteed-Stable Sliding DFT Algorithm With Minimal Computational Requirements," IEEE Transactions on Signal Processing, vol. 65, no. 20, pp. 5281-5288, 2017.
[33] S. Liu and T. Guo, "An adaptive DFT algorithm for measuring power system synchrophasors based on rectangular coordinate," in 2015 IEEE PES Asia-Pacific Power and Energy Engineering Conference (APPEEC), 2015, pp. 1-5.
[34] S. Liu, T. Guo, J. Li, and J. Wu, "Adaptive DFT algorithm for measuring synchrophasors based on shifting window symmetrical," in 2015 5th International Conference on Electric Utility Deregulation and Restructuring and Power Technologies (DRPT), 2015, pp. 722-726.
[35] M. A. Ali, M. Hossain, and M. N. Bhuiyan, "Automatic speech recognition technique for Bangla words," International Journal of Advanced Science and Technology, vol. 50, 2013.
[36] I. Ding, "Enhancement of speech recognition using a variable-length frame overlapping method," in 2010 International Symposium on Computer, Communication, Control and Automation (3CA), 2010, vol. 1, pp. 375-377.
[37] W. A. Sethares, Rhythm and transforms. Springer Science & Business Media, 2007.
[38] C. Park and S. Ko, "The Hopping Discrete Fourier Transform," IEEE Signal Processing Magazine, vol. 31, no. 2, pp. 135-139, 2014.
[39] Q. Wang, X. Yan, and K. Qin, "High-Precision, Permanently Stable, Modulated Hopping Discrete Fourier Transform," IEEE Signal Processing Letters, vol. 22, no. 6, pp. 748-751, 2015.
[40] W. Juang, S. Lai, K. Chen, W. Tsai, and C. Luo, "Low-complexity hopping DFT design based on a compact recursive structure," Electronics Letters, vol. 53, no. 1, pp. 25-27, 2017.
[41] W. Juang, S. Lai, C. Luo, and S. Lee, "VLSI Architecture for Novel Hopping Discrete Fourier Transform Computation," IEEE Access, vol. 6, pp. 30491-30500, 2018.
[42] L. R. Rabiner and B. Gold, Theory and application of digital signal processing. Englewood Cliffs, NJ, Prentice-Hall, Inc., 1975, p. 388.
[43] Tanimoto, "An Optimal Algorithm for Computing Fourier Texture Descriptors," IEEE Transactions on Computers, vol. C-27, no. 1, pp. 81-84, 1978.
[44] F. Lehmann, "Turbo Segmentation of Textured Images," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 1, pp. 16-29, 2011.
[45] K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian, "Image denoising with block-matching and 3D filtering," in Image Processing: Algorithms and Systems, Neural Networks, and Machine Learning, 2006, vol. 6064, p. 606414: International Society for Optics and Photonics.
[46] A. Meraoumia, S. Chitroub, and A. Bouridane, "Efficient person identification by fusion of multiple palmprint representations," in International Conference on Image and Signal Processing, 2010, pp. 182-191: Springer.
[47] P. d. Chazal, J. Flynn, and R. B. Reilly, "Automated processing of shoeprint images based on the Fourier transform for use in forensic science," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 27, no. 3, pp. 341-350, 2005.
[48] M. Ghafoor, I. A. Taj, and M. N. Jafri, "Fingerprint frequency normalisation and enhancement using two-dimensional short-time Fourier transform analysis," IET Computer Vision, vol. 10, no. 8, pp. 806-816, 2016.
[49] K. R. Rao, D. N. Kim, and J. J. Hwang, Fast Fourier transform-algorithms and applications. Springer Science & Business Media, 2011, pp. 185-193.
[50] C. Park, "2D Discrete Fourier Transform on Sliding Windows," IEEE Transactions on Image Processing, vol. 24, no. 3, pp. 901-907, 2015.
[51] W.-H. Juang, S.-C. Lai, C.-H. Luo, and S.-Y. Lee, "A Hardware Accelerator Design for Novel Hybrid 1D-2D Sliding Discrete Fourier Transform Algorithm," in The 29th VLSI Design/CAD Symposium, Taiwan, 2018.
[52] W.-H. Juang, S.-C. Lai, C.-H. Luo, and S.-Y. Lee, "Novel Two-dimension Sliding Discrete Fourier Transform Algorithm and its Hardware Architecture Design," in 2017 Taiwan and Japan Conference on Circuits and Systems (TJCAS), Okayama, Japan, 2017.
[53] V. Kober, "Fast algorithms for the computation of sliding discrete sinusoidal transforms," IEEE Transactions on Signal Processing, vol. 52, no. 6, pp. 1704-1710, 2004.
[54] E. Chu and A. George, Inside the FFT black box: serial and parallel fast Fourier transform algorithms. CRC Press, 1999, pp. 111-116.
[55] K. R. Rao, D. N. Kim, and J. J. Hwang, Fast Fourier transform-algorithms and applications. Springer Science & Business Media, 2011, pp. 127-131.
[56] R. Tolimieri, M. An, and C. Lu, Mathematics of multidimensional Fourier transform algorithms. Springer Science & Business Media, 2012, pp. 163-164.
[57] R. Neuenfeld, M. Fonseca, and E. Costa, "Design of optimized radix-2 and radix-4 butterflies from FFT with decimation in time," in 2016 IEEE 7th Latin American Symposium on Circuits & Systems (LASCAS), 2016, pp. 171-174.
[58] W. Song, D. Tjondronegoro, and S. Azad, "User-Centered Video Quality Assessment for Scalable Video Coding of H.264/AVC Standard," in Advances in Multimedia Modeling, Berlin, Heidelberg, 2010, pp. 55-65: Springer Berlin Heidelberg.