快速傅里叶变换和卷积算法PDF电子书下载

第一章 绪言 1

1.1 引言 1

1.2 记号 2

1.3 本书的组成 3

第二章 数论和多项式代数基础 5

2.1 初等数论 6

2.1.1 整数的整除性 6

2.1.2 同余和剩余 6

2.1.3 原根 14

2.1.4 二次剩余 21

2.1.5 麦森数和费马数 24

2.2 多项式代数 28

2.2.1 群 29

2.2.2 环和域 31

2.2.3 剩余多项式 32

2.2.4 多项式代数中卷积和多项式乘积算法 34

第三章 快速卷积算法 40

3.1 利用循环卷积进行数学滤波 41

3.1.1 重迭相加算法 41

3.1.2 重迭保留算法 42

3.2 短卷积和多项式乘积的计算 43

3.2.1 利用中国余数定理计算短卷积 43

3.2.2 以割圆多项式为模的乘法 46

3.2.3 矩阵交换算法 49

3.3 利用短卷积嵌套计算长卷积 53

3.3.1 Agarwal-Cooley算法 53

3.3.2 分裂嵌套算法 57

3.3.3 复卷积 64

3.3.4 数字滤波器的最佳分段长度 67

3.4 利用多维方法的数字滤波 68

3.5 利用多项式的递推嵌套计算卷积 73

3.6 分配运算 78

3.7 短卷积和多项式乘积算法 80

3.7.1 短圆卷积算法 81

3.7.2 短多项式乘积算法 89

3.7.3 短非周期卷积算法 96

第四章 快速傅里叶变换 98

4.1 离散傅里叶变换 98

4.1.1 DFT的性质 99

4.1.2 实序列的DFT 102

4.1.3 奇序列和偶序列的DFT 103

4.2 快速傅里叶变换算法 104

4.2.1 基2FFT算法 106

4.2.2 基4FFT算法 111

4.2.3 FFT算法的实现 114

4.2.4 FFT中的量化效应 117

4.3 Rader-Brenner FFT 120

4.4 多维FFT 123

4.5 Bruun算法 125

4.6 卷积的FFT计算法 130

第五章 用线性滤波法计算离散傅里叶变换 134

5.1 线性调频z变换算法 134

5.1.1 利用线性调频z变换进行卷积和DFT的实时计算 136

5.1.2 线性调频z变换的递推计算 137

5.1.3 线性调频滤波器中的因式分解 138

5.2 Rader算法 139

5.2.1 复合算法 141

5.2.2 Rader算法的多项式公式表示 143

5.2.3 短DFT算法 146

5.3 素因子FFT 148

5.3.1 一维DFT的多维映射 149

5.3.2 素因子算法 151

5.3.3 分裂的素因子算法 154

5.4.1 算法推导 157

5.4 Winograd傅里叶变换算法(WFTA) 157

5.4.2 混合算法 163

5.4.3 分裂的嵌套算法 164

5.4.4 多维DFT 166

5.4.5 编制程序和量化噪声问题 167

5.5 短DFT算法 170

5.5.1 2点DFT 171

5.5.2 3点DFT 171

5.5.3 4点DFT 172

5.5.4 5点DFT 172

5.5.5 7点DFT 173

5.5.6 8点DFT 174

5.5.7 9点DFT 174

5.5.8 16点DFT 176

6.1 引言 178

第六章 多项式变换 178

6.2 多项式变换的一般定义 183

6.2.1 根在多项式域中的多项式变换 185

6.2.2 具有复合根的多项式变换 189

6.3 多项式变换和简化的计算 192

6.4 利用多项式变换的二维滤波 195

6.4.1 利用多项式变换和多项式乘积算法计算二维卷积 195

6.4.2 利用多项式变换计算二维卷积的例子 199

6.4.3 嵌套算法 200

6.4.4 与常规的卷积算法的比较 203

6.5 在修正环中定义的多项式变换 204

6.6 复卷积 208

6.7 多维多项式变换 209

第七章 利用多项式变换计算离散傅里叶变换 213

7.1 利用多项式变换计算多维DFT 213

7.1.1 简化的DFT算法 214

7.1.2 算法的一般定义 218

7.1.3 多维DFT 227

7.1.4 嵌套和素因子算法 229

7.1.5 利用在多项式修正环中定义的多项式变换计算DFT 231

7.2 利用多维相关和多项式变换计算DFT 236

7.2.1 算法推导 236

7.2.2 两种多项式变换方法的组合 240

7.3 与常规FFT的比较 242

7.4 奇DFT算法 243

7.4.1 简化的DFT算法.N=4 246

7.4.2 简化的DFT算法.N=8 246

7.4.3 简化的DFT算法.N=9 246

7.4.4 简化的DFT算法.N=16 247

第八章 数论变换 248

8.1 数论变换的定义 248

8.1.1 NTT的一般性质 250

8.2 麦森变换 254

8.2.1 麦森变换的定义 255

8.2.2 以麦森数为模的算法 258

8.2.3 示例 259

8.3 费马数变换 261

8.3.1 费马数变换的定义 261

8.3.2 以费马数为模的算法 264

8.3.3 利用FNT计算复卷积 267

8.4 字长和变换长度的限制 268

8.5 伪变换 270

8.5.1 伪麦森变换 271

8.5.2 伪费马数变换 274

8.6 复NTT 277

8.7 与FFT的比较 280

参考文献 283

术语索引 288