基4 FFT（Fast Fourier Transform，快速傅立葉變換）算法是一種用於計算離散傅立葉變換（DFT）的高效算法。它通過將長序列的DFT分解為較短的序列來減少計算量。基4 FFT算法的特點是每次蝶形運算處理4個數據點。
基本原理：
FFT算法的基本思想是將長序列的DFT分解為較短序列的DFT，通過減少蝶形運算的數量來提高計算效率。
基4 FFT算法是FFT算法的一種實現方式，它每次處理4個數據點，相比基2 FFT（每次處理2個數據點）和基8 FFT（每次處理8個數據點），基4 FFT在處理特定大小的序列時具有優勢。
計算過程：
計算過程包括逐級分解，直到可以處理2點的DFT。
基4 FFT算法通過特定的蝶形運算來實現，這些運算比基2 FFT中的蝶形運算更高效。
碼位倒置排序：
在FFT中，碼位倒置是一個重要的步驟，它確保了輸出結果的順序與輸入序列的順序一致。
碼位倒置可以通過簡單的位運算實現，或者使用疊代方法進行計算。
實現細節：
實現基4 FFT算法需要定義複數類型、輸入序列、變換核等數據結構。
算法中包含多個函式，如初始化變換核、變址、複數加法、複數乘法等，這些函式共同完成FFT的計算過程。
參考搜尋結果：
提供了對基4 FFT算法的基本原理、計算過程、碼位倒置排序以及實現細節的概述。