简介：我们在使用FFT IP核设计FPGA时，需要了解FFT相关的运算理论，如FFT蝶形运算引起的位宽扩展，FFT实现的资源与性能的平衡，如何实时更新FFT转换点、缩放等相关配置和FFT运算顺序等。本文将详细介绍这些问题。
1.有限字长考虑突发I/O架构，通过连续传递输入数据来处理一组数据数组。在每个进程中，算法执行基数-4或基数-2的蝶形运算，其中每个蝶形运算获得四个或两个复数，并在同一存储器中返回四个或两个复数。IP返回内存的数量可能大于从内存中提取的数量。必须采取策略来适应这种动态范围的扩展。
对于Radix-4 DIT FFT，蝶形阶段计算的值按照以下因素增加，即带来3 bit位宽扩展。
公式1 Radix-4 DIT butterfly计算位宽增长。
对于Radix-2 DIT FFT，蝶形阶段计算的值可以通过以下因素增加，即2位位宽将变宽。
公式2 Radix-2 DIT FFT butterfly计算位宽增长。
位宽的增加可以通过三种方式处理：
在不进行缩放的情况下执行计算，并在计算结束时进位所有有效整数位。使用固定的缩放方案在每个级别进行缩放。使用块浮点自动缩放。1.1使用全精度无缩放算法时，全精度算法考虑保留所有整数位。增加数据路径位宽以适应蝶形运算引起的位宽增加。乘法产生的小数位数的增加在乘法后被截断(或四舍五入)。输出位宽为(输入宽度log2(变换长度)1)，这是最差的位宽增长方案。
考虑未缩放的Radix-2 DIT FFT:数据路径的每一级必须增加1位，因为蝶形运算中的加法器和减法器可能会对两个满量程值进行加法/减法运算，并生成宽度增加1位的样本。这将导致log2(变换长度)部分，其中输出宽度相对于输入宽度增加。复数乘法器保持输入数据的幅度(当它在复数平面上应用旋转时)。当输入幅度大于1时，位宽理论上会增加(例如1 j会使幅度增加1.414倍)。这意味着在整个FFT过程中必须考虑复数乘法器的比特增长。例如，包括1个整数位、15个小数位和1024点转换的16位输入将具有27位宽的输出，包括12个整数和15个小数位。请注意，IP核不指定二进制点的位置。保持与输入和输出相同的二进制点位置。对于16位输入，3位整数和13位小数，输出将是27位，包括14位整数位和13位小数。
注：对于无标度算法、有标度算法和块浮点算法，IP核没有明确的二进制点位置。输出二进制点的位置与输入数据和每一级的标度移位有关。
1.2.缩放算法考虑到使用缩放时，每一级的缩放因子可以是1、2、4或8。如果缩放不充分，碟形运算的输出可能会带来位宽增加，超出动态范围，从而造成溢出。当缩放处理应用于FFT实现时，缩放因子s定义如下：
3公式比例因子的定义
其中bi是第I级的比例因子。因此，使用缩放因子的FFT/IFFT输出结果被因子1/s校正.
4公式比例因子对FFT/IFFT计算的影响
如果Radix-4算法在每一级以因子4进行缩放，则因子1/s相当于IFFT中的1/N。对于基数-2，每个小数位数是2，由因子1/n提供。
1.3.块浮点算法考虑(自动缩放)使用块浮点算法。每一级都采用足够的伸缩保证不溢出，伸缩采用块索引跟踪。
2.浮点考虑FFT可以可选接收32位单精度浮点数据，包括1位符号位、8位整数位和23位小数。数据组织符合Xilinx浮点运算IP要求。在FPGA中实现全浮点需要大量的资源。FFT内核浮点实现使用高精度定点来实现与全浮点相似的噪声性能。
图3-14说明了两级噪声性能。通过选择24位和25位相位因子w
将结果与第三方模型(如MATLAB)进行比较时，应注意通常需要一个比例因子来确保结果匹配。规模取决于数据，因为输入数据在内部定点核心之前指定了所需的标准化级别。由于内核在浮点模式下不提供该比例因子，如有必要，可以在内核输出后应用比例因子。
当选择浮点输入数据时，所有优化选项(存储器类型和DSP的优化)仍然可用，允许您在转换范围内权衡资源时间。
FFT内核的浮点接口不支持反规范数。为了匹配Xilinx浮点运算符内核的行为，内核将非规格化操作数视为零，符号取自非规格化数。
如果内核在输入端检测到NaN或无穷大的值，则与当前输入帧相关的所有输出样本都设置为NaN。符号设置为零，所有指数和分数位设置为1。
3.实数输入考虑到FFT内核接收复数数据样本，但它可以通过将所有虚拟输入样本设置为零来对实值数据执行转换。
由于上述有限字长效应，转换过程中会引入噪声，导致输出数据不完全对称。并且由于不同的计算顺序，DIT FFT算法和DIF FFT算法具有不同的噪声效果。噪声在低频箱中更突出。因此，Xilinx建议在执行实FFT时，使用输出数据的上半部分(N/2 1至N点)。
4.舍入实施在所有架构中，都有一个在蝶形阶段之后对数据应用收敛舍入的选项。但是，选择此选项不会对数据路径中字长缩短的所有点应用收敛舍入。
具体而言，FFT数据路径中所有复数乘法器的输出都被截断，以减小数据路径宽度(同时仍保持足够的精度)，并且在小数位数上添加一个简单的舍入常数。该常数实现了对负无穷大的非对称舍入，并且会给大量样本的FFT结果带来很小的偏差。
5.FFT架构选择FFT核提供了四种可供选择的计算架构，可以在资源和转换之间权衡时间。包括：
流水线I/O:允许连续的数据处理。
Radix-4突发I/O:使用迭代方法分别加载和处理数据。使用的资源大小小于管道解决方案，但是转换时间更长。
基数-2突发I/O:使用与基数-4相同的迭代方法，但是使用更小的蝶形。使用比base -4更少的资源，但是transform时间更长。
Radix-2 Lite突发I/O:基于base 2架构，该变体采用时间复用方式，以更长的转换为代价，用更小的内核进行蝶形运算时间。
图2说明了四种架构的吞吐量和资源使用之间的权衡。根据经验，每个架构提供的资源与下一个架构相差2倍。
图二。不同架构的资源和吞吐量比较
所有四种架构都可以配置为定点接口，使用三种定点算术方法之一(非定标、定标或块浮点)，或者可以使用浮点接口。
5.1自然顺序和逆序问题每个架构都提供了输入数据自然顺序和输出数据自然顺序或逆序的选择。FFT算法在处理过程中对样本进行重新排序，使得以自然顺序输入的数据以相反的顺序输出。IP核可以选择以自然顺序输出数据。但是，这会给每个架构带来成本(消耗更多资源，尤其是RAM资源)。对于突发I/O架构，这将导致转换时间变得更长，因为卸载数据不能与加载下一帧的输入数据同时进行，所以需要单独的卸载和加载阶段。在流水线结构中，它需要额外的RAM存储来执行重新排序，这会消耗更多的RAM资源。
5.2流水线I/O架构流水线I/O解决方案将多个基2蝶形处理引擎模块化，提供连续的数据处理。每个处理引擎都有自己的RAM来存储输入和中间数据(图3)。IP核可以为下一帧数据加载输入数据，对当前帧数据进行转换计算，卸载前一帧数据的结果。可以连续传输数据，计算延迟后可以连续卸载结果。这种结构允许每个框架之间有间隙。
图3。流水线输入输出体系结构
注意：连续的流数据并不意味着来自FFT内核的AXI4流的等待状态可以忽略。某些情况下，FFT内核可能需要插入等待状态来暂停输入的采样数据。
在定点缩放模式下，数据在每对基数的第二阶之后进行缩放。浮点模式可能比缩放模式使用更多的资源，因为它必须保持额外的精度，以允许动态缩放而不影响性能。所以，如果输入数据很好理解，不太可能有大的波动，那么使用缩放算法(适当缩放时间表，避免已知最坏情况下溢出)就足够了，可以节省资源。
5.3 radix -4突发I/O (radix -4突发I/O)对于Radix-4突发I/O方案，FFT内核使用Radix-4磁盘处理引擎，如图4所示。它独立加载和卸载(输出)数据，数据I/O和处理不是同时进行的。当FFT开始时，输入数据载入，一帧完全载入后，FFT内核计算转换结果。计算完成后，可以输出数据，但在计算过程中不能加载或输出数据计算结果。如果按照数字相反的顺序卸载数据，则数据加载和卸载过程可以同时进行。从图4中可以看出，蝶形运算的输出结果反馈到数据输入端的RAM，实现了RAM共享，减少了资源占用。
图4。基数-4突发I/O
这种架构比流水线I/O架构占用资源少，但转换时间更长，支持64~65536点转换。和数据相位因子可以存储在BRAM或分布式RAM中。
5.4 radix -2突发I/O对于Radix-2突发I/O方案，FFT内核使用Radix-2磁盘处理引擎，如图5所示。加载一帧数据后，必须暂停输入数据流，直到转换计算完成后才能加载数据。与Radix-4突发I/O架构类似，如果数据以数字相反的顺序卸载，则数据加载和卸载过程可以同时执行。该架构支持8~65536点转换。和数据相位因子可以存储在BRAM或分布式RAM中。
图5。基数-2突发I/O
Radix-2突发I/O的架构整体上与Radix-4突发I/O类似，但蝶形运算结构不同。
5.5 Radix-2 Lite突发I/O该结构不同于Radix-2突发I/O碟形处理引擎。它使用共享的加法器/减法器，从而减少碟形运算的资源和额外延迟。与Radix-4突发I/O架构类似，如果数据以数字相反的顺序卸载，则数据加载和卸载过程可以同时进行。该架构支持8~65536点转换。
图6。Radix-2 Lite突发I/O
Radix-2 Lite突发I/O架构省略了更多的RAM资源和多路复用器资源，但换来的是更长的转换时间时间。
6.运行时配置FFT IP内核本节讨论的所有运行时配置选项都是使用配置通道进行编程的。有关更多信息，请参阅上一篇文章配置通道。运行时配置主要包括FFT转换点、FFT/IFFT配置、缩放因子和循环前缀插入。运行时配置需要检查FFT IP内核接口中的运行时可配置转换长度，如图所示。
图7。运行时配置参数
6.1转换点数(NFFT)NFFT FFT/IFFT IP核支持图8所示的转换点数。请注意，每个体系结构支持的最新转换点数量略有不同。该参数在与配置通道s_axis_config_tdata相对应的NFFT字段中进行配置。
图8。FFT/IFFT内核支持的转换点数
6.2 FFT/IFFT选择和缩放因子FFT/IFFT选择和缩放因子配置也是通过s_axis_config_tdata口进行的。您可以在图7中看到这三个字段的占用顺序。请注意，每个字段由8-8位字节界定。先说比例因子。
突发I/O架构比例因子以连续比例实现。可以通过配置通道设置适当的SCALE_SCH字段。对于基数-4、突发I/O和基数-2架构，SCALE_SCH字段值使用位对[.N4，N3，N2，N1，N0]，并且每对值对应于相应的缩放级别。每一级计算都从阶段0开始，使用2位LSB。级数的计算：用log4(转变点数)或log2(转变点数)计算基4和基2级数。在每个阶段，数据可以移位0、1、2、3位，分别对应于SCALE_SCH值00、01、10、11。
例如，对于基数-4，N=1024，比例因子[01 10 00 11 10]。N=1024对应5级dish操作，所以stage0右移2 ^ 2302位，stage1右移3位，stage2右移0位，stage3右移2位，stage4右移1位。缩放方案总共移位8位，缩放因子是1/256。N=1024，在Radix-4突发I/O架构中，避免溢出的保守方案SCALE_SCH=[10 10 10 10 11]。在Radix-2架构中，保守方案SCA hle _ sch=[01 01 01 01 01 01 1 0]具有10个标度。
流水线I/O架构的比例因子对于流水线I/O架构，将每对相邻的Radix-2级视为一组。例如，组0包含阶段0和阶段1，组1包含阶段2和阶段3，依此类推。每一级的比例因子SCALE_SCH域类似于突发I/O架构，[.N4，N3，N2，N1，N0】。每个组缩放值对应于相应的2-2位LSB值。例如，如果N=1024个点，[10，10，00，01，11]，那么group0(包括stage0和stage1)右移3位，group0(包括stage2和stage3)右移1位，group2(包括stage4和stage5)右移0位，group3(包括stage6和stage7)对于这个点转换，保守的比例因子SCALE _ SCH=[10 10 10 10 10 11]可以避免数据溢出。如果转换点数不是4的幂，则最后一组只有一级，该组的最大位数增加到1位。所以最高两位msb只能是00或者01。对于N=512，保守比例因子SCALE_SCH=[01 10 10 10 11]。
6.3循环前缀插入(CP)循环前缀占据FFT输出的一部分，它被添加到转换的开始。输出数据包含输出前缀(输出数据的结束副本)，它跟在完整的输出数据后面，并且已经全部自然输出。循环前缀仅在自然顺序输出中可用。
当使用循环前缀时，可以在帧之间插入循环前缀的长度，而不中断帧处理过程。插入数据的长度可以设置为小于转换长度的任何值。长度由配置通道CP_LEN域设置。例如，当N=1024时，循环前缀长度可以设置为从0到1023的任何值，并且CP_LEN=0010010110将输出数据设置为包含150个采样输出循环前缀值。
6.4配置FFT IP核FFT转换使用配置通道进行配置。当IP核加载新的帧数据处理时，它将检查新的配置是否应用配置通道。如果是这样，FFT处理内核会在加载帧之前使用新配置。否则，IP核心使用最后的配置信息。如果未配置IP核心，IP核心将使用重置的默认配置。将配置数据应用到特定帧的过程取决于IP核心的当前状态：
在上电或空闲周期后将配置应用于第一帧；将配置应用于帧序列中的下一帧。为确保在帧处理前正确配置IP内核，应按照以下顺序将配置信息写入配置通道：
实时模式：在第一个数据被写入数据输入通道之前，配置数据被写入配置通道至少一个时钟周期。如果写入失败，IP核使用之前的配置进行转换。非实时模式：配置数据可以在第一个数据写入数据输入通道之前或同时写入。在系统设计中，最简单的方法是在系统初始化时完成IP核相关的初始化配置。
7.FFT转换状态问题7.1溢出问题定点数据输出和状态通道的OVFLO域只用于缩放算法。当输出数据帧中的任何一点溢出时，OVFLO输出为高电平。对于多通道内核，每个通道都有一个独立的OVFLO域。当内核溢出时，转换后的数据无法用于大多数应用。
浮点数据当FFT处理浮点数据时，溢出域用于指示溢出指数幂。基于内部结果符号，输出样本溢出设置为。当NaN值出现在输出中时，不会插入溢出字段。当输入数据帧具有NaN或值时，FFT的输出将具有NaN值。
7.2块指数输出数据和状态通道BLK _指数字段包含块指数幂(仅用于块浮点选项)。对于多通道内核，每个通道包含一个独立的BLK指数字段。该域中的值表示转换过程中的总缩放位数。例如，如果BLK _指数=00101=5，这意味着输出数据(XK_RE，XK_IM)缩放5位(右移5位)。换句话说，为了充分利用输出数据路径的可用动态范围并防止溢出，输出结果除以32。
7.3 XK索引XK _索引字段(如果使用数据输出通道)，给出XK_RE/XK_IM数据的采样数。在自然顺序输出中，XK指数从0增加到N-1(转换点数)，当以逆序输出时，XK指数也以逆序输出。例如，8点FFT如表1所示。
1.8点FFT XK指数
当使用循环前缀时，首先卸载循环前缀，并且XK索引从(N-(循环前缀长度))计数到(N-1)。循环前缀仅用于自然顺序输出。
8.FFT IP内核操作序列内核在以下情况下开始处理帧：a)上游主机通过向进程提供数据来请求处理帧，以及b)当它可以处理帧时。选定的架构和循环前缀插入是影响内核何时可以处理新帧的主要配置选项。
下面的序列图是实际行为的总结，用于显示IP核在处理帧时经历的每个阶段，以及这些阶段如何重叠。不同阶段的长度是不可缩放的，并且处理时间可能比输入或输出帧时间所需的时间长得多。
特别是，由于数据输入通道缓冲数据(非实时模式下16个符号，实时模式下1个符号)，TREADY在输入数据通道上的行为并不完全准确。然而，这些数据会在缓冲器中等待，直到FFT处理内核准备就绪。这些图中的数据输入通道TREADY用于指示FFT处理核心何时需要数据，而不是AXI通道(及其缓冲器)何时需要数据。
8.1无循环前缀的流水线I/O时序当采用流水线I/O架构且未插入循环前缀时，IP核可以处理加载的帧，同时输出前一帧。如果上游主模块在前一帧之后立即输出新的数据帧，IP核将立即加载该数据帧进行处理。图9示出了流水线架构中背靠背数据帧的一般处理序列。
图9。无循环前缀流水线结构的处理序列
在图9中，可以看出在第一帧加载和处理后的数据输出之间有一定的延迟。延迟取决于Vivado IDE中IP核的参数设置。当延迟结束时，后续处理帧将按背靠背顺序输出。
8.2使用循环前缀的流水线I/O时序当使用循环前缀插入时，处理的帧长度将大于加载的数据帧长度。此时，图3-42所示的背靠背帧不能出现在IP核心输入帧中，每帧之间必须插入循环前缀长度的间隔，如图3-43所示。输入通道的TREADY信号用于指示何时输入新帧。
图11。使用循环前缀流水线架构的处理序列
8.3突发I/O架构突发I/O架构不允许像流水线I/O那样进行帧重叠处理，当使用自然序列输出时，IP核需要完成当前帧的处理和输出后才能加载下一帧。
使用反向输出时，IP核仅在加载新帧时输出数据。这意味着加载的N-1帧将与输出的N帧重叠。但是，当数据帧开始卸载时，如果上游主模块没有向IP核提供数据，则IP核需要手动刷新输出，然后加载和卸载阶段不会重叠。
图12显示了自然序列输出突发I/O架构的一般转换时序。这需要完全独立的装载、处理和卸载阶段。上游模块不断尝试向下游从属模块发送数据帧。在这个例子中，循环前缀的影响没有被显示，并且在卸载阶段被扩展。
图12。自然se的I/O模数时序
如图12所示。上行模块将所有数据帧a加载到FFT IP核的数据输入通道中，当FFT IP核处理数据时，通道缓冲区中没有数据。然而，主模块立即开始发送帧B。图中A点，由于FFT正在处理帧A，不再从数据输入通道取数据，帧B可以送到数据输入通道缓冲。当S _ axis _ data _ tread变为低电平时，可以认为帧B正在被缓冲。输入通道一直在等待，FFT直到B点才能接收到上游主模块数据，此时FFT已经输出完A帧，开始加载B帧到处理核，处理核会读取数据输入通道的缓冲区，解除上游主机的阻塞。然后重复帧A相同过程.
需要强调的是：
输入通道的AXI接口上的活动不一定与FFT中的活动相关。例如，在点A之前，通道载入帧B的样本数据，而FFT正在处理帧A的数据。上游模块必须始终输出数据流，而不参考s _ axis _ data _ tread信号。FFT载入新帧之前，必须先卸载转换后的帧数据。
图13。反向突发的I/O模数时序
图13和图14类似，除了FFT被配置为逆序输出。上游模块始终输出数据，允许同时加载和卸载。
图14。反向突发的I/O模数时序(内核刷新帧)
图14和图13类似，除了上游主模块将不输出数据帧B，直到IP核开始刷新输出帧A.在加载B帧之前，IP核必须先完成A帧的刷新输出，加载和卸载同时进行。
图13和图14之间的时间差异在于两点：
是否可以同时处理装货和卸货；输入通道上游主模块的数据流加载是否一直处于加载状态。9.总结本文详细介绍了FFT/IFFT核运算的理论知识，有些地方比较详细和枯燥。有些内容通过例子可以更好的理解；关于FFT架构的选择，我们要根据实际的项目需求做出取舍，比如转换时间是否满足实时处理要求，是否需要时分复用节省资源等。本文还给出了如何计算和配置比例因子的详细示例。
阅读：数字信号处理(三):Xilinx FFT IP核详解(二)
