查看“︁快速演算法設計的原則”︁的源代码

{{multiple issues|
{{cleanup-jargon|time=2018-10-11T11:40:13+00:00}}
{{copyedit|time=2018-10-11T11:40:13+00:00}}
{{howto|time=2018-10-11T11:40:13+00:00}}
{{orphan|time=2018-10-11T11:40:13+00:00}}
}}

==快速演算法設計原理==
*快速演算法的主要目標為節省計算時間，採取手段主要如下：
*#減少加法數量
*#減少乘法數量
*#減少[[迴圈]]數量
**其中以減少乘法數量最為重要，可以最為高效率節省計算量。

==快速演算法的設計重要的四種概念==

===N-point DFT===
對於任何點數的[[離散傅里葉變換|離散傅立葉轉換(DFT)]]，都有其適合的快速演算法．

===線性非時變系統的運算複雜度===
由於[[線性非時變系統]]可以用[[卷積]]Convolution來表示，故我們可以說其運算複雜度為，三個傅立葉轉換的計算量（包括兩個FTs 以及一個IFT)<br>
⇒<math>3 \theta(NlogN) </math><br>
⇒<math> \theta(NlogN) </math><br>
若使用了快速演算法，我們可以將其運算複雜度降為<math> \theta(N) </math><br>

===Replacement of DFTs===
對於DFT的計算有複數(complex number)的問題，我們也可以透過矩陣的方式來處理．

===運算簡化技巧===
下面以四個例子來解說：

(1) <math>y_1 = ax_1 + 2ax_2 </math>
⇒<math>y_1=\begin{pmatrix} a & 2a \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}  </math><br>
⇒<math>y_1 = a(x_1 + 2x_2) </math><br>
⇒1 MULs, 1 ADD (一個乘法，一個加法)


(2)<math>\begin{pmatrix} y_1 \\ y_2 \end{pmatrix} =\begin{pmatrix} a & a \\ a & a  \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}  </math><br>
⇒<math>y_1 = a(x_1 + x_2) </math><br>
⇒<math>y_2 = y1</math><br>
⇒1 MULs, 1 ADD 


(3)<math>\begin{pmatrix} y_1 \\ y_2 \end{pmatrix} =\begin{pmatrix} a & b \\ b & a  \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}  </math><br>
⇒<math>\begin{pmatrix} y_1 \\ y_2 \end{pmatrix} =\begin{pmatrix} \frac{a+b}{2} & \frac{a+b}{2}  \\ \frac{a+b}{2}  & \frac{a+b}{2}  \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}+ \begin{pmatrix} \frac{a-b}{2} & -\frac{a-b}{2}  \\ -\frac{a-b}{2}  & \frac{a-b}{2}  \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}  </math><br>
⇒2MULs, 4 ADDs 


(4)<math>\begin{pmatrix} y_1 \\ y_2 \end{pmatrix} =\begin{pmatrix} a & b \\ c & a  \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}  </math><br>
⇒<math>\begin{pmatrix} y_1 \\ y_2 \end{pmatrix} =\begin{pmatrix} a & a  \\ a  & a  \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}+ \begin{pmatrix} 0 & b-a \\ c-a  & 0  \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}  </math><br>
⇒3MULs, 3 ADDs


==複數的乘法==
if <math>x = a + ib </math>  and <math>y = c + id</math> <br>
⇒<math>xy = ac-bd + i(ad+bc )</math><br>
令e為實數項，f為虛數項<br>
<math>\begin{pmatrix} e \\ f \end{pmatrix} =\begin{pmatrix} c & -d \\ d & c  \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix}  =\begin{pmatrix} c & c\\ c & c  \end{pmatrix}\begin{pmatrix} a \\ b \end{pmatrix} + \begin{pmatrix} 0 & -c-d\\ d-c & 0  \end{pmatrix}\begin{pmatrix} a \\ b \end{pmatrix} </math><br>
(1) let <math>x_1 = c(a + b) </math> ; <math>y_1 = x_1 </math><br>
(2) let <math>x_2 = (-c-d)b </math> ; <math>y_2 = (d-c)a </math><br>
⇒<math>e = x_1+x_2 </math> ; <math>f = y_1+y_2 </math>
⇒3MULs, 3～5 ADDs 
從這裡我們可以看出虛數的乘法量大致為實數乘法量的三倍<ref>Jian-Jiun Ding, Advanced Digital Signal Processing class note, the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2018&2020.</ref>。

==参考==
{{reflist}}

[[Category:计算机逻辑]]