《快速傅里叶变换和卷积算法》求取 ⇩

第一章 绪言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 实序列的DFT102

4.1.3 奇序列和偶序列的DFT103

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 FFT120

4.4 多维FFT123

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 素因子FFT148

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 多维DFT166

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

5.5 短DFT算法170

5.5.1 2点DFT171

5.5.2 3点DFT171

5.5.3 4点DFT172

5.5.4 5点DFT172

5.5.5 7点DFT173

5.5.6 8点DFT174

5.5.7 9点DFT174

5.5.8 16点DFT176

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 利用多项式变换计算多维DFT213

7.1.1 简化的DFT算法214

7.1.2 算法的一般定义218

7.1.3 多维DFT227

7.1.4 嵌套和素因子算法229

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

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

7.2.1 算法推导236

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

7.3 与常规FFT的比较242

7.4 奇DFT算法243

7.4.1 简化的DFT算法.N=4246

7.4.2 简化的DFT算法.N=8246

7.4.3 简化的DFT算法.N=9246

7.4.4 简化的DFT算法.N=16247

第八章 数论变换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 复NTT277

8.7 与FFT的比较280

参考文献283

术语索引288