无线通信系统-FFT与信道译码VLSI设计 课件 第4章Radix-2k FFT量化误差分析与VLSI结构优化

第4章Radix-2kFFT量化误差分析与VLSI结构优化4.1基于矩阵变换的混合radix-2kFFT算法分析4.2混合radix-2k算法量化误差分析4.3流水线FFT结构硬件参数的优化配置4.4仿真分析与实验测试本章小结

Radix-2k算法是FFT硬件设计中广泛应用的一类计算方案。与经典的radix-2k算法或混合基算法相比，利用radix-2k算法来设计FFT硬件结构，其优势有两点：一是radix-2k算法的蝶形运算以最简单的radix-2运算方式进行，降低了蝶形运算单元的VLSI设计难度和控制复杂度；二是radix-2k算法可以将非平凡旋转因子的数据加权在信号流图中进行集中，这样在流水线实现方式下，无需为每一级蝶形运算单元都配置复数乘法器，从而有助于降低FFT计算单元的硬件资源开销。

4.1基于矩阵变换的混合radix-2kFFT算法分析

一般地，N点DFT运算可以表示为(4.1)

4.1.1混合radix-2k算法的矩阵变换表示

在(4.2)中，

是一个用于完成

点倒位序次序变换的置换矩阵。为了给出

的具体表达式，首先定义S阶的跨步置换矩阵GS，将该矩阵作用于S维向量

可以得到

这样一来

可以分解为一组跨步置换矩阵连乘的形式，即

(4.3)

另一方面，(3-2)中的M个连乘项对应于级联的M个运算单元，这里

描述了执行radix-2k算法的运算单元所涉及的全部操作，其中参数cm表示前m个计算单元的算法阶数累积量，即

(4.4)

显然m=M将使得

。对于给定的cm，

对应的算术运算操作由km决定。

（1）当km为奇数且km>1时

，

可以表示为

其中N阶蝶形运算矩阵BF(u)具有如下形式：

4.1.2混合radix-

2k算法分量矩阵的数学性质

在(4.15)中，混合radix-2k算法使得DFT变换矩阵TN能够用数据排序矩阵

、蝶形运算矩阵BF(u)以及数据加权矩阵M1(u)，M2(u,v)，M3(u,v)等分量矩阵进行表示。不难验证TN满足

是酉矩阵。实际上，(4.15)中的各分量矩阵都具有类似的性质。证明这一点需要用到跨步置换矩阵的一些数学特性，因此我们首先给出如下的引理：

引理4.1：如果矩阵GS是跨步置换矩阵，那么GS可逆且其逆矩阵GS-1满足

。

另一方面，矩阵的Kronecker积具有如下性质：

4.2混合radix-2k算法量化误差分析

4.2.1可变数据位宽下的量化误差模型

在(4.15)中，DFT变换矩阵TN按照混合radix-2k算法进行分解后得到了L个蝶形运算矩阵

。对于实际的流水线FFT计算结构，BF(l)中涉及的radix-2蝶形运算和数据原位存储操作将通过流水线第l=1级的蝶形运算单元实现。

由于BF(l)不受参数

的影响，因而蝶形运算单元在定点计算中引入的量化误差将只由数据位宽决定。令wini和wfin分别表示FFT输入数据和计算结果实部与虚部的数据位宽，同时定义数据位宽向量

，其中wl对应于流水线第l=1级的蝶形运算单元和旋转因子加权单元在计算过程中所采用的数据位宽。在满足

的前提下，数据位宽向量w可以进行任意设置，而数据位宽非递减的约束旨在减小由数据截位所引入的量化误差。

在数据位宽固定的流水线结构中，参与radix-2蝶形运算的两个数据在计算前通常要进行缩放：数据的实部和虚部分别右移一位并根据数据最低位的取值对移位运算结果进行舍入，该操作在避免蝶形运算发生溢出的同时也引入了量化误差。而当流水线结构中的数据位宽可变时，在某一级增加数据位宽将使得后续的部分蝶形运算单元在不缩放输入数据的条件下也能够避免计算溢出。

图4.2radix-2km计算单元内的量化误差传播模型

4.2.2量化误差的功率估计

我们首先考虑(4.19)中舍入误差向量

，其元素对应于输入数据

在缩放过程中引入的误差。一般地，

包含的N个元素被认为是一组独立同分布的随机变量。在统计意义上，

中每一个元素的实部与虚部为非负数和负数的概率均为1/2，同时数据的最低位以相同概率取0和1，这保证了

中各元素的均值为0。进一步假设

中各元素的方差为

，我们可以得到

对应的功率为

对于(4.19)中的误差分量

，其元素对应于输入数据

在数据旋转操作中所引入的误差。和舍入误差

不同的是，

中的元素并非都是误差源，这是因为利用

或

等平凡旋转因子进行数据旋转可以通过对输入数据的实部与虚部进行互换和取反来完成，而这些操作并不引入量化误差。因此为了计算

对应的功率，首先需要确定数据加权矩阵

的主对角线上包含的非平凡旋转因子的个数。进一步考虑到

是由旋转因子矩阵

通过元素次序调整和维度扩展而产生的，我们的分析将从

入手。

(4.30)和(4.31)从信号功率的角度将radix-计算单元的特性概括为两个方面：首先输入信号

在经过radix-计算单元后各分量功率将变为原来的

倍；其次radix-计算单元在定点运算过程中还会引入功率为

的新误差项。将这一结论应用于混合radix-算法所包含的其他M-1个计算单元，可以得到如图4.3所示的信号功率传播模型。

图4.3混合

算法在定点运算方式下信号与量化误差功率传播模型

4.3流水线FFT结构硬件参数的优化配置

4.3.1流水线VLSI结构存储资源开销分析

本节以SDF结构和MDC结构为代表，对流水线VLSI结构存储资源开销进行分析。作为一种广泛应用的流水线FFT实现方案，SDF结构的主要特征在于每一级蝶形运算单元内用于实现数据次序调整的反馈连接。图4.4以N=16为例对采用radix-2算法的SDF流水线结构进行了描述。

图4.4采用FFT算法的SDF流水线结构（N=16

）

在MDC流水线结构中，蝶形运算单元利用双路换向器来调整参与运算的数据次序，图4.5以N=16为例对采用radix-22

算法的MDC结构进行了描述。与SDF结构类似，算法阶数向量k的调整只对流水线中数据旋转单元的数目以及分布位置产生影响。要实现N=2L点的FFT运算，MDC结构中蝶形运算单元所对应的存储开销为

(4.43)

图4.5采用radix-22FFT算法的MDC流水线结构（N=16

）

根据(4.13)，M3(u,v)中的参数v=1对应于算法阶数km=1，而令M2(u,v)中的参数v=3将使得

中的参数i=2且

，而这进一步要求算法阶数km是奇数且

。结合(4.41)，我们可以将MDC结构中旋转因子的存储开销表示为

4.3.2流水线VLSI结构计算资源开销分析

流水线FFT结构对计算资源的消耗主要来自于蝶形运算单元包含的复数加法器以及数据旋转单元包含的复数乘法器或CORDIC运算模块。在优化硬件参数来对计算准确度和硬件资源消耗进行折衷之前，有必要对基于混合radix-2k算法的流水线结构所消耗的计算资源进行估计。前面提到对于任意的算法阶数向量k，SDF和MDC流水线结构均包含L=log2N个蝶形运算单元，因此电路中复数加法的数目可以表示为

(4.45)

在复数乘法器的消耗方面，表4.1统计了混合radix-2k算法中位于第m级的radix-

计算单元

在SDF和MDC流水线结构中所占用的复数乘法器数目

。每个向量中包含的3个元素分别对应于radix-

计算单元内用于实现

相位旋转的复数乘法器以及通用复数乘法器的数目，这里对不同类型的复数乘法器分开进行统计是考虑到它们具有不同的硬件复杂度。

当算法阶数向量k给定时，我们可以将流水线结构中占用的复数乘法器数目fmu1记作

以各种类型的复数乘法器可以全部替换为CORDIC模块，这样流水线结构中需要配置的CORDIC模块的个数为

4.3.3FFT流水线VLSI结构硬件参数优化方法

在基于混合radix-2k算法的流水线结构中，选取合适的数据位宽向量w和算法阶数向量k可以实现计算准确度和硬件复杂度的有效折衷。从前面的分析中我们得出，w和k的选择将会在较大程度上影响FFT计算单元对存储器的消耗，同时k也决定了流水线FFT结构所占用的复数乘法器或CORDIC单元的数目。一般地，基于量化误差来优化FFT计算单元的硬件参数大致可归结为以下两类问题：

（1）硬件资源优先型，即在SQNR不低于给定基准TSQNR的前提下最小化FFT计算单元的硬件资源开销。以最小化系统对存储资源的消耗为例，可以得到以下优化问题：

(4.48)

2）计算准确度优先型，即在存储开销不高于给定约束Rc的条件下最大化FFT计算结果的SQNR，这可以描述为以下的优化问题：

(4.49)

实际上FFT计算单元对复数乘法器或CORDIC模块的消耗也可以作为约束条件或优化目标体现在(4.48)和(4.49)中，我们在这里仅将存储开销纳入上面的优化问题，这是因为存储资源的消耗与SQNR存在较强关联性并且直接决定了流水线FFT结构所占用的电路面积大小。确定最优的w,k

需要到对上面的非线性整数优化问题进行求解，而在经典优化理论框架下尚无有效的数学工具来解决这一NP难问题。我们注意到(4.48)和(4.49)的后两个约束条件给变量w,k

划定了可行域

，其中(w,k)

内包含的

参数对的个数为

当算法4.2的外循环达到最大次数或者历史最优解不进行更新时搜索过程终止，由于模拟退火算法是一种启发式算法，此时得到的w,k无法保证一定是全局最优解。然而注意到

能够保证每次产生的邻域解均落在可行域

内，这有助于提升模拟退火算法的搜索效率以及获得全局最优解的可能性。

4.4仿真分析与实验测试

4.4.1流水线结构SQNR与存储开销的仿真分析

为了研究流水线FFT结构在定点运算方式下计算结果的SQNR与存储开销的关系，我们用白噪声源来产生输入序列x0，其中每个数据的实部和虚部在[-1,1]的取值范围内均匀分布。因此

，代入(4.34)可以得到

将上面的

代入(4.49)描述的优化问题并改变参数Rc，我们可以得到在存储资源约束给定的情况下FFT计算单元的可达SQNR性能。图4.6在FFT长度N=512以及运算结果实部和虚部数据位宽wfin=16的情况下给出了SQNR与存储资源消耗的关系曲线。

图4.6流水线FFT结构输出数据SQNR与存储资源消耗的关系曲线

图4.6流水线FFT结构输出数据SQNR与存储资源消耗的关系曲线

图4.7和图4.8以基于SDF流水线结构实现的FFT计算单元为例，比较了在数据位宽向量w和算法阶数向量k的不同配置方式下，FFT计算结果准确度以及FFT计算单元的存储资源开销。

图4.7基于复数乘法器的SDF流水线结构的数据位宽配置方案比较（

N=32768）

图4.7基于复数乘法器的SDF流水线结构的数据位宽配置方案比较（

N=32768）

图4.7基于复数乘法器的SDF流水线结构的数据位宽配置方案比较（

N=32768）

图4.8基于CORDIC模块的SDF流水线结构的数据位宽配置方案比较（

N=32768）

图4.8基于CORDIC模块的SDF流水线结构的数据位宽配置方案比较（

N=32768）

图4.8基于CORDIC模块的SDF流水线结构的数据位宽配置方案比较（

N=32768）

4.4.2流水线FFT结构SQNR的实验测试

图4.9对比了在数据位宽向量

的不同配置下FFT计算结果SQNR的理论估计值与实测值。可以看到对于利用复数乘法器的SDF流水线结构，SQNR的估计值通常略高于其实际数值，这是因为我们在推导中为了得到SQNR的闭合表达式而假设流水线结构每一级所产生的量化误差是不相关的，而事实上这些误差之间存在着一定的相关性。当SDF结构使用CORDIC模块来实现数据旋转时，在某些参数配置方式下SQNR的估计值也会低于实测值，这主要是由于附录在分析CORDIC运算单元的量化误差时,采用的是残余角度误差方差的上界，相应地(4.35)对CORDIC运算单元量化误差方差的估计在某些情况下会大于实际数值。总体上来看，SQNR估计值和实测结果的差距不超过1.5dB，因此我们认为(4.34)能够为FFT硬件结构的设计提供计算准确度的有效参考。

图4.9SQNR理论估计值与实测值比较

图