↑ 點擊上方「玩轉單片機」關注我們
下面兩道題關於使用複利葉變換的， 這應該是很常見的嵌入式問題：
A) 系統用 adc (小於 16-bit) 採樣 50Hz 交流電流電壓， 採樣頻率800hz, 試求出電流電壓幅值以及功率和功率因數。
B) 上面的50hz 電壓中， 混入了另一個 55hz 的電壓， 求出這兩個電壓的幅值。
這兩道題使用 16-bit, 32-bit 的整數運算， 不使用浮點運算， 可以在 mcu 上實現。
下面一道題， 因為我聽說宇宙飛船有一個變速不變調的專利(我現在懷疑此傳說的真實性)， 所以切磋一下：
C) 完成一個 wav 聲音文件的變速不變調的程序。
複利葉變換在 mcu 上可能不常用， 所以不知道有多少感興趣的同學。
(1) 複數的基礎知識
在講解 fourier transform 前， 大家必須知道一點基本的複數知識。
在複平面上的一個點 P (x, y) 用複數表示為:
P = x + i y
用極坐標表示為：
P = r * e^(i a)
這裡, r = sqrt(x*x + y*) 是點 (x, y) 到原點的距離， a = arctan2(x, y) 是角度, e 是自然常數。這裡引出了一個非常重要的表達式：
e^(i a) = cos(a) + i sin(a)
這個表達式，是利用複數完成角度變換和三角函數變換的利器。例如，把點 P 旋轉 b 角度，那麼新點(x1, y1) 的角度為 a+b, 距離仍為 r.
P1 = x1 + i y1
= r * e^(i (a+b))
= r*e^(i a) * e^(i b)
= (x + i y) * (cos(b) + i sin(b))
= (x * cos(b) - y * sin(b)) + i ( y * cos(b) + x * sin(b))
(2) 傅立葉變換的基礎知識
傅立葉變換是一個積分變換， 公式就不提供了， 有興趣的同學可以直接訪問下面的連接， 以獲得更詳盡的解釋：
http://zh.wikipedia.org/zh-cn/%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2
(3) 離散傅立葉變換(DFT)
http://zh.wikipedia.org/zh-cn/%E7%A6%BB%E6%95%A3%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2
離散傅立葉變換的公式：
X(k) = ∑ x(n) * e^(i -2*PI* n/N * k) / N
這裡 X(k) 是第 k 次諧波的複數;N 為周期採樣點數;x(n)為輸入，n從0 到N-1;
用偽代碼更直觀地說明：
void CalculateHarmonic(Complex* X, int harmonic)
{
for (int i=0; i
X->Real = x(i) * cos( 2*PI* i/N * harmonic) / N;
X->Image = x(i) * sin(-2*PI* i/N * harmonic) / N;
}
}
可以看到，離散傅立葉變換基本運算其實很簡單， 沒有那麼複雜。只要有了 N 個輸入，比如說通過AD 採樣了 N 個數據後，可以輕易的計算出各個諧波，雖然計算量大了些。下面要做的就是減少計算量，這可以用兩種方法， 一種當然就是熟知的 FFT, 還有一種就是遞推。
(3) 遞推離散傅立葉 (Recursive DFT)
傅立葉變換是一個積分變換，積分當然可以使用迭代遞推來減少運算，尤其是周期性的函數。只要把最後一個數據仍出去，保持其他 N-1 個數據不變，加入一個新的數據就可以了。為了理解這一點，先考慮一下移動平均濾波算法：
Y(k-1) = (x(k-1) + x(k-2) + … + x(k-N)) /N
上面的這個公式可以寫成迭代也就是遞推的形式：
Y(k) = Y(k-1) + (x(k) – x(k-N)) /N
同理，由於sin, cosin函數的周期性，dft 可以由多項式乘法和的形式變換成迭代遞推的形式：
Y(k) = Y(k-1) + x(k) * e^(i -2*PI* k /N * harmonic) / N
- x(k - N) * e^(i -2*PI* (k–N) /N * harmonic) / N
= Y(k-1) + (x(k) - x(k- N)) * e^(i -2*PI* k /N * harmonic) / N
C 代碼：
x(i) = GetFromADC();
X->Real += (x(i) – x(i-N)) * cos( 2*PI* i/N * harmonic) /N;
X->Image += (x(i) – x(i-N)) * sin(-2*PI* i/N * harmonic) /N;
由於 cos, sin 是周期函數，所以 cos(2*PI* (i * harmonic) / N) 與cos(2*PI* (i * harmonic % N) / N) 是一樣的，(i * harmonic % N) 的取值範圍：0 to N-1.
總結一下：
傅立葉變換可以很深奧，也可以很淺顯。對於離散的傅立葉變換的公式， 只要認真的看看很容易看明白，更何況還有代碼說明。通過理解 dft 如何計算出某一個諧波，就可以進一步計算出所有諧波，再想像一下， 某一個算法，可以快速的計算出所有的諧波，這樣，就可以很容易的理解 fft.
按以下識別二維碼關注！
電子路上，一起走！