数 理 着考处 自 Cooley和 Teke算法提出之后,新的算法不断涌现,概括起来, 快速傅里叶变换的发展有两个方向,一是针对N等于2的整数次幂的 算法,如基2算法、基4算法、实因子算法和分裂基算法等,二是针 对N不等于2的整数次幂的算法,它是以 Winograd为代表的一类算法 (如素因子算法、 Winograd算法)。 可以证明,在基4下,一个4点DFT可以不用乘法而只用加法来 实现,因此,基4算法比基2算法更有效。1984年提出的分裂基算法, 即同时使用基2和基4的算法,被认为是目前对N等于2的整数次幂的 各类算法中最为理想的一种算法。Cooley Tekey 2 2 4 2 Winograd Winograd 4 4 4 2 1984 N N DFT 自 和 算法提出之后，新的算法不断涌现，概括起来， 快速傅里叶变换的发展有两个方向，一是针对 等于 的整数次幂的 算法，如基 算法、基 算法、实因子算法和分裂基算法等，二是针 对 不等于 的整数次幂的算法，它是以 为代表的一类算法 （如素因子算法、 算法）。 可以证明，在基 下，一个 点 可以不用乘法而只用加法来 实现，因此，基 算法比基 算法更有效。 2 4 N 2 年提出的分裂基算法， 即同时使用基 和基 的算法，被认为是目前对 等于 的整数次幂的 各类算法中最为理想的一种算法