快速算法

维基教科书,自由的教学读本
跳到导航 跳到搜索

算法优化,最主要的目的是用来减少运算时间,像是加法、乘法的数目,以及所花的运算周期。此外还能降低硬件实现所花费的成本,像是减少缓冲器的数量、重复利用相同的硬件架构。

概览[编辑]

一般来说,快速算法的设计可以透过将运算展开,并进行归纳、分析,利用运算次数更少的乘法、除法(如乘以二、除以二等左移、右移)来完成运算,达到降低运算时间的目的。

而在设计的过程中,因为乘法的运算时间会远大于加法,因此通常会以使用多少个乘法来衡量整体的运算时间。此外,因为是从硬件的角度来看,所以对于乘上、0,都可以视为不需要任何的运算时间(trivial multiplications),因为对于乘上,或者除上,分别只要进行左移位元或右移位元的运算即可达成。

简单矩阵有关的算法优化设计[编辑]

以下举几个例子,用以说明如何优化算法,使得矩阵演算能够最优化。 1.

从上面这个式子来看,在左边的部分需要用到两个乘法、一个加法,然而经过一些化简、合并,在右边的地方就只需要一个乘法(乘2不需要运算时间)、一个加法。

2.

,因此从原本需要四个乘法、两个加法,变成只要一个乘法、一个加法。

3.

,因此从原本的四个乘法、两个加法,变成只需要一个乘法、二个加法。

4.

, 左边的部分可以参考例子2,右边则是例子3,因此从原本的四个乘法、两个加法,变成两个乘法、四个加法。

5.

左边的部分一样可以参考例子2,所以需要一个乘法、一个加法,右边的部分则需要两个乘法,最后要将左右两式相加,因此还需要两个加法才能得到,所以一共需要三个乘法、三个加法。

实际应用[编辑]

一般来说,做傅立叶转换会用到复数的乘法,会比一般实数的乘法多上四倍,若是利用快速算法,则可以化简如下:

因此左边的部分可以参考例子2,所以需要一个乘法,右边的部分则需要两个乘法,因此可以由四个乘法变为三个乘法。

另外举一个DFT的例子,一般来说DFT会需要个实数乘法:

,左边都是一些trivial multiplication,所以不需要乘法运算,右边则可以参考例子3,所以需要一个乘法。整个DFT的运算可以由下式表示:

所以最后一供需要个乘法。

参考资料[编辑]

[1]http://djj.ee.ntu.edu.tw/ADSP10.pdf

  1. 丁建均.高等数字信号处理.于2017年6月20日查阅.