快速算法

　　快速算法是数字信号处理的支柱。本书是我国第一本综合论述数字信号处理中快速算法设计与分析的著作。它深入而系统地论述了卷积和离散富里叶变换的各种经典和现代的快速算法，Winograd富里叶变换算法，多项式变换及其应用，离散余弦变换和w变换的快速算法，有关Toeplitz矩阵及Toeplitz系统的快速算法，格与树搜索的快速算法等。本书所论及的算法，大部分已在实际应用中起着非常重要的作用。本书的宗旨是介绍数字信号处理中重要问题的最好快速算法，同时让读者懂得设计快速算法的一般技巧。本书可供无线电技术、电子工程、计算机与信息科学、计算数学以及相近专业的高年级学生、研究生、教师阅读，也可供广大科技工作者参考。

暂缺《快速算法》作者简介

第一章  卷积的快速算法                  
 1  卷积及其等价形式                  
 2  用分段循环卷积实现数字滤波                  
 2. 1  重叠保留法                  
 2. 2  重叠相加法                  
 3  短卷积的快速算法                  
 3. 1 Cook-Toom短卷积算法                  
 3. 2 Winograd短卷积算法                  
 3. 3  复数卷积及一般环中的卷积                  
 4  长卷积的计算                  
 4. 1  Agarwal-Cooley算法                  
 4. 2  分裂嵌套算法                  
 4. 3  迭代算法                  
 5  多维卷积的计算                  
 5. 1  多维循环卷积的计算                  
 5. 2  多维线性卷积的计算                  
 6  卷积的并行计算                  
 6. 1  基于直接计算的并行算法                  
 6. 2  快速算法的并行处理                  
 7  卷积的计算复杂性                  
 7. 1  算法和计算复杂性                  
 7. 2  矩阵乘向量的乘法次数下界                  
 7. 3  卷积的乘法复杂性                  
 附录A  短循环卷积的Winograd算法                  
 附录B  短多项式乘积算法                  
 参考文献                  
 第二章  离散富里叶变换及其快速算法                  
 1  一维离散富里叶变换                  
 1. 1  离散富里叶变换的性质                  
 1. 2  特殊序列的离散富里叶变换                  
 2  离散富里叶变换的快速算法                  
 2. 1  Cooley-TukeyFFT算法                  
 2. 2  基-2FFT算法                  
 2. 3  基-4FFT算法                  
 3  Rader-BrennerFFT算法                  
 3. 1  Rader-BrennerFFT算法                  
 3. 2  简化DFT的快速算法                  
 3. 3  实因子算法                  
 4  PreussFFT算法                  
 5  基-3FFT新算法                  
 6  多项式算法                  
 6. 1  Goertzel算法                  
 6. 2  z变换算法                  
 6. 3  递归割圆分解算法(RCFA)                  
 7  分裂基算法(SRFFT)                  
 8  快速富里叶变换的统一表示及并行计算                  
 8. 1  kronecker乘积及完全混合算子                  
 8. 2  富里叶变换矩阵的分解                  
 8. 3  FFT的并行计算                  
 8. 4  逆序置换矩阵的分解                  
 9  二维离散富里叶变换及其快速算法                  
 9. 1  二维DFT的行列算法                  
 9. 2  二维DFT的向量基算法                  
 10  DFT在计算卷积中的应用                  
 参考文献                  
 第三章  素因子算法(FPT)和Winograd富里叶变换算法(WFTA)                  
 1  Bluestein算法                  
 2  Rader算法                  
 2. 1  N=p尹的Rader算法                  
 2. 2  N=pc的复合算法                  
 2. 3  N＝2l的Rader算法                  
 3  Winograd小NDFT算法                  
 4  素因子FFT算法(FPA)                  
 4. 1  一维DFT的多维映射                  
 4. 2  Good-Thomas素因子算法                  
 4. 3  分裂素因子算法                  
 5  Winograd富里叶变换算法(WFTA)                  
 5. 1  二维DFT的嵌套算法                  
 5. 2  Winograd富里叶变换算法(WFTA)                  
 5. 3  FPA和WFTA的混合算法                  
 5. 4  Johnson-Burrus富里叶变换算法(JBFTA)                  
 附录  Winograd小NDFT算法                  
 参考文献                  
 第四章  多项式变换及其应用                  
 1  多项式变换的引进                  
 2  有理数域上的多项式变换                  
 2. 1  一维多项式变换                  
 2. 2  二维及多维多项式变换                  
 3  快速多项式变换一FPT                  
 3. 1  一维快速多项式变换(FPT)                  
 3. 2  FPT在计算机上的实现                  
 3. 3  二维快速多项式变换(2D-FPT)                  
 4  二维数字卷积的多项式变换算法                  
 4. 1  二维循环卷积的FPT算法及其在计算机上的实现                  
 4. 2  二维循环卷积FPT算法的改进                  
 4. 3  任意长二维循环卷积的多项式变换算法                  
 5  一维数字卷积的多项式变换算法                  
 5. 1  多项式乘积的FPT算法                  
 5. 2  一维循环卷积的FPT算法                  
 6  二维离散富里叶变换的多项式变换算法                  
 6. 1  p×p二维DFT的多项式变换算法                  
 6. 2  2l×2 二维DFT的FPT算法及其在计算机上                  
 的实现                  
 6. 3  任意长二维DFT的多项式变换算法                  
 参考文献                  
 第五章  其它离散变换及其快速算法                  
 1  各类离散余弦变换和正弦变换及其相互关系                  
 1. 1  各类DCT和DST及其相互关系                  
 1.  2  DFT的DCT算法                  
 2  离散余弦变换的快速算法                  
 2. 1  一维DCT的快速算法                  
 2. 2  二维DCT的快速算法                  
 3  离散w变换及其快速算法                  
 3. 1  w变换及其基本性质                  
 3. 2  用余弦正弦变换计算DWT                  
 3. 3  直接分解算法                  
 4  广义离散富里叶变换(GFT)及其快速算法                  
 4. 1  广义离散富里叶变换及其逆变换                  
 4. 2  GFT的快速算法                  
 5  DWT与GFT在卷积计算中的应用                  
 5. 1  用DHT计算循环卷积                  
 5. 2  用GFT和DWT计算斜循环卷积                  
 参考文献                  
 第六章  格和树的搜索算法                  
 1  格和树                  
 2  动态规划和Witerbi算法                  
 3  回溯法和Fano算法                  
 4  堆栈算法                  
 参考文献                  
 第七章  有关Toeplitz矩阵快快速算法                  
 1  Toeplitz矩阵求逆的快速算法                  
 1. 1  k循环矩阵求逆的FFT算法                  
 1. 2  Toeplitz矩阵求逆的Trench算法                  
 2  分块Toeplitz矩阵求逆的快速递归算法                  
 3  求解Toeplitz系统的Bareiss变换法以及Levinson算法                  
 4  求解一般Toeplitz系统的一种超快速算法                  
 5  求解对称正定Toeplitz系统的预条件共轭梯度算法(PCGM)                  
 6  Toeplitz矩阵相乘的快速算法                  
 参考文献