目录 1
第一章 绪论 1
1.1 快速算法引论 1
1.2 快速算法的应用 4
1.3 计算用的数系 5
1.4 数字信号处理 6
1.5 快速信号处理算法的历史 12
习题 13
注 14
第二章 抽象代数导论 15
2.1 群 15
2.2 环 18
2.3 域 21
2.4 向量空间 24
2.5 矩阵代数 26
2.6 整数环 31
2.7 多项式环 34
2.8 中国余数定理 41
习题 45
注 47
第三章 短序列卷积的快速算法 48
3.1 循环卷积和线性卷积 48
3.2 Cook-Toom算法 51
3.3 Winograd短序列卷积算法 55
3.4 短序列线性卷积算法设计 62
3.5 以多项式为模的多项式乘积 66
3.6 短序列循环卷积算法的设计 68
3.7 普通域和环里的卷积 72
3.8 卷积算法的复杂性 74
习题 81
注 83
第四章 离散傅里叶变换的快速算法 84
4.1 Cooley-Tukey快速傅里叶变换 84
4.2 小基数Cooley-Tukey算法 86
4.3 Good-Thomas快速傅里叶变换 93
4.4 Goertzel算法 95
4.5 用卷积来计算的傅里叶变换 97
4.6 Winograd小快速傅里叶变换 105
习题 112
注 113
第五章 数论和代数域理论 114
5.1 初等数论 114
5.2 基于整数环的有限域 118
5.3 基于多项式环的域 121
5.4 最小多项式和共轭值 122
5.5 割圆多项式 123
5.6 本原元 126
习题 127
注 128
第六章 替代域中的计算 129
6.1 替代域中的卷积 129
6.2 费马数变换 132
6.3 默森数变换 133
6.4 有限域中的卷积算法 135
6.5 替代域中的复数卷积 137
6.6 整数环变换 142
6.7 Chevillat数变换 146
6.8 Preparata-Sarwate算法 146
习题 147
注 148
7.1 嵌套卷积算法 150
第七章 快速算法与多维卷积 150
7.2 Agarwal-Cooley卷积算法 153
7.3 分裂算法 159
7.4 累接算法 163
7.5 扩张域的多项式表示法 167
7.6 多项式扩张域卷积 169
7.7 Nussbaumer多项式变换 170
7.8 多项式的快速卷积 172
习题 176
注 177
第八章 快速算法和多维变换 178
8.1 小基数Cooley-Tukey算法 178
8.2 嵌套变换算法 182
8.3 大数组的Winograd快速傅里叶变换 186
8.4 Johnson-Burrus快速傅里叶变换 191
8.5 分裂算法 194
8.6 改进的Winograd快速傅里叶变换 197
8.7 Nussbaumer-Quandalle置换算法 198
习题 208
注 209
第九章 滤波器和变换器的结构 210
9.1 分段卷积 210
9.2 短滤波器节算法 214
9.3 累接滤波器节 216
9.4 对称和斜对称滤波器 220
9.5 抽选和插值滤波器 224
9.6 自相关和互相关 227
9.7 变换计算机的结构 232
9.8 限制范围的傅里叶变换 236
注 237
习题 237
第十章 基于加倍策略的快速算法 239
10.1 减半和加倍策略 239
10.2 数据结构 242
10.3 分类问题的快速算法 243
10.4 递推基2快速傅里叶变换 244
10.5 快速转置 247
10.6 矩阵乘法 248
10.7 递推欧几里德算法 250
10.8 三角函数的计算 254
习题 258
注 259
第十一章 Toeplitz系求解的快速算法 260
11.1 Levinson和Durbin算法 260
11.2 Trench算法 267
11.3 Berlekamp-Massey算法 271
11.4 递推Berlekamp-Massey算法 277
11.5 基于欧几里德算法的一些方法 280
习题 284
注 284
第十二章 格和树搜索的快速算法 286
12.1 格和树搜索 286
12.2 Viterbi算法 289
12.3 堆栈算法 291
12.4 Fano算法 293
习题 297
注 297
附录A 循环卷积算法汇编 299
附录B Winograd小FFT算法汇编 308
参考文献 316
汉英名词对照索引 323