【六】DIT - SplitRadix FFT的程序实现
你已经发现SplitRadix的L型运算比Radix2的直接分两半的简单粗暴的方式复杂,意味着我们要往控制流程里塞更多东西……
我个人不喜欢这么做,尤其是在FFT这种密集计算的场合下。为什么呢?因为你仔细看蝶形图和我们之前Radix2 FFT的代码会发现,FFT的运行流程和输入的数据没有半点关系,只和FFT点数有关!无论你输入的数据是什么,控制流程始终是一成不变的!
而实际应用中我们往往只会在一段程序中用到少数几种不同大小的FFT。
由此计算和流程控制混合会降低效率。
而且计算和流程控制混合使你难以排错。
以上两个理由使我决定设计SplitRadix具体实现时把控制流程和计算分开进行。
我的SplitRadix实现包括三个步骤:
1. 根据FFT点数构建出一个指令表(计算流程)。
2. 倒序运算
3. 按照指令表依次进行不同大小的L型运算、4或2点运算。
当你重复进行同样大小的FFT时,就可以用已经存在的指令表进行运算,而不必重新生成指令表。测试表明1024点FFT,SplitRadix比我们之前实现的Radix2快了将近一倍。
我们先来看怎么生成指令表。这个操作简直就像个小“编译器”,根据输入的FFT级数生成“字节码”,然后丢给一个只会做FFT运算的小“解释器” “运行”……
你已经发现SplitRadix的L型运算比Radix2的直接分两半的简单粗暴的方式复杂,意味着我们要往控制流程里塞更多东西……
我个人不喜欢这么做,尤其是在FFT这种密集计算的场合下。为什么呢?因为你仔细看蝶形图和我们之前Radix2 FFT的代码会发现,FFT的运行流程和输入的数据没有半点关系,只和FFT点数有关!无论你输入的数据是什么,控制流程始终是一成不变的!
而实际应用中我们往往只会在一段程序中用到少数几种不同大小的FFT。
由此计算和流程控制混合会降低效率。
而且计算和流程控制混合使你难以排错。
以上两个理由使我决定设计SplitRadix具体实现时把控制流程和计算分开进行。
我的SplitRadix实现包括三个步骤:
1. 根据FFT点数构建出一个指令表(计算流程)。
2. 倒序运算
3. 按照指令表依次进行不同大小的L型运算、4或2点运算。
当你重复进行同样大小的FFT时,就可以用已经存在的指令表进行运算,而不必重新生成指令表。测试表明1024点FFT,SplitRadix比我们之前实现的Radix2快了将近一倍。
我们先来看怎么生成指令表。这个操作简直就像个小“编译器”,根据输入的FFT级数生成“字节码”,然后丢给一个只会做FFT运算的小“解释器” “运行”……