笔者最近用FPGA实现的64点IFFT，记录一下作为笔记也可以为各位读者提供一个思路。（输入12bit实数+12bit虚数）

IFFT算法的原理这里就不再赘述，主要讲解算法的实现过程。

如图2：我们要用FPGA实现此算法的话，利用流水线的思想，可分为如下几步：1.输入重新排序。2.对应数据与旋转因子相乘。3.蝶形运算得到本级输出结果。4.输出作为输入参与下一级运算直到最后一级。

1.输入排序:如图1和图2所示，输入序列的顺序就是自然序的二进制的倒序对应的十进制数。

　　　　　　　　　　　　图1

 　　　　　　　　　　　　图2

 2.复乘运算：由于fpga实现浮点运算会消耗大量资源，所以这里采用定点运算。将旋转因子扩大到1024倍，取其定点值参与复乘运算。因为 在运算前将旋转因子×2^10，对于复乘后的结果要右移十位。此外，我们可以根据结果适当删去不需要的位数。例如由于旋转因子实部/虚部最大值也只能为1，所以这里的结果实部/虚部最大为13位。

3蝶形运算：蝶形运算的过程只是加法器对应输入与对应复乘结果相加/减得出对应输出。这里需要注意的是：我想每一级都是12bit输入，12bit输出，但是每一级输出只用12bit就需要对这一级结果进行截位，截位会怎么影响输出呢，还有怎样截位会使输出更加准确呢。下面是我对截位的一些想法。

先说截位怎么样影响输出：有IFFT原理可知每一级/2最后的输出也会/2，IFFT的输出最后要除以2^n(n是级数)才会是正确结果，所以每一级可以"免费"地截一位末位。

假设这里有两个操作实数A是m bit，B是n bit。那么A+B应该是max{m，n}+1bit，A×B是m+n bit。但在这里，因为旋转因子是有取值范围的，所以每一级的输出也是存在取值范围的，所以对每一级的输出截位要考虑这一级的输出取值范围。对于第一，二级，旋转因子只能为1或者j，所以输出结果的实部/虚部最多加一位“免费”地截取一位后刚好还是12位。对于第三级我们考虑一种极端情况(这里用2^12只是为了说明倍数关系，实际是对应位宽的最大值)：

(2^12+j*2^12)+(2^12+j*2^12)*(√2/2+j*√2/2)这时虚部会为 (1+√2)*2^12，也就是说，第三级要加两位(但这种极端输入情况对第一级的输入也有要求，笔者找出来一种会造成第三级输出为 (1+√2)*2^12的第一级输入的值对其进行IFFT之后在进行FFT得到的结果竟然不是原来的第一级输入的值，不知道是为什么。笔者暂时猜想是这种FFT数据并没有与之对应的实信号。但仅从每一级的角度来讲输出确实会出现为(1+√2)*2^12的情况)。对于这种情况笔者决定对第三级截取两位末尾，这样输出就还是十二位，只需要得出最后结果左移一位就行了。这样第三级的结果就很小，四五六级运算也只会增加一位然后“免费”的截掉就行。

附：对于批量编辑代码的问题，我们可以利用matlab提供的交互式操作方式去产生我们想要的结果复制后利用在文本编辑器的列模式下粘贴。