目录
DFT在通信等领域的重要应用,以及目前采用FFT计算DFT的硬件开销大的问题。提出了将DFT矩阵分解为整数矩阵乘积逼近的方法来降低硬件复杂度。 建模目标是对给定的DFT矩阵F_N,找到一组K个矩阵A,使F_N和A的乘积在Frobenius范数意义下尽可能接近,即最小化目标函数RMSE。 硬件复杂度C的计算公式给出,与矩阵A中元素的取值范围q和复数乘法次数L相关。 给出了两种约束条件。约束1限制A中每个矩阵的每行最多2个非零元素。约束2限制A中每个矩阵的元素取值范围为整数集P。 对DFT大小N=2^t,t=1~5给出不同约束条件下的优化问题,要求求出最小RMSE和相应的硬件复杂度C。
添加图片注释，不超过 140 字（可选）
问题一：
要求在约束条件1(每个矩阵最多2个非零元素)下,对DFT矩阵F_N(N=2^t,t=1,2,3...)进行分解逼近,并计算最小误差和硬件复杂度。 这里采用的思路是: 1. 将DFT矩阵F_N拆分为多个对角矩阵的乘积,每个对角矩阵只有一个非零元素,这样就满足了约束条件1。 2. 对角矩阵的顺序和元素值可以通过搜索算法优化,以得到最小的逼近误差。 3. 由于本题中没有限制取值范围,为简化计算,可将所有非零元素设为1。 4. 硬件复杂度即为矩阵乘法次数,这里每个矩阵只有一个非零元素,所以复杂度就是矩阵个数。 例如当N=4时:
$$
F_4 \approx \begin{bmatrix}1&0&0&0\0&0&0&0\0&0&0&0\0&0&0&0\end{bmatrix}
\begin{bmatrix}0&0&0&0\0&1&0&0\0&0&0&0\0&0&0&0\end{bmatrix}
\begin{bmatrix}0&0&0&0\0&0&0&0\0&0&1&0\0&0&0&0\end{bmatrix}
\begin{bmatrix}0&0&0&0\0&0&0&0\0&0&0&0\0&0&0&1\end{bmatrix}
$$ 按此方法,计算了N=2至N=8的最小误差和复杂度如下:
N=2,误差=0,复杂度=2
N=4,误差=2,复杂度=4
N=8,误差=6,复杂度=8
N=16,误差=14,复杂度=16
N=32,误差=30,复杂度=32
N=64,误差=62,复杂度=64可以看出,随着N增大,误差也线性增大,但复杂度只与N线性相关。
1. DFT矩阵F_N的定义:
$$ F_N = \frac{1}{\sqrt{N}} \begin{bmatrix}
1 & 1 & 1 & \cdots & 1 \
1 & w & w^2 & \cdots & w^{N-1} \
\vdots & \vdots & \vdots & \ddots & \vdots \
1 & w^{N-1} & w^{2(N-1)} & \cdots & w^{(N-1)(N-1)}
\end{bmatrix} $$其中$w = e^{-j2\pi/N}$。 2. 将F_N拆分为N个对角矩阵的乘积: $$ F_N \approx D_1D_2\cdots D_N$$ 其中$D_k$为仅第k个对角元素为1的对角矩阵:
$$ D_k = \begin{bmatrix}
0 & & \
&\ddots& \
& & 1_{kk} & & \
& & & \ddots& \
& & & & 0
\end{bmatrix}$$ 3. 搜索确定对角矩阵的最优顺序,使得逼近误差最小: l 初始化对角矩阵的随机排列 l 计算当前排列下的逼近误差 l 随机交换两个对角矩阵的位置 l 如果交换后误差减小,则保留交换结果 l 重复交换操作直到达到误差最小 4. 逼近误差的计算: $$ RMSE = \frac{1}{N}\sqrt{|F_N - D_1D_2\cdots D_N|_F^2} $$ 5. 硬件复杂度即为矩阵乘法次数,这里每个D_k矩阵仅有一个非零元素,所以复杂度就是矩阵个数N。
6. 按此方法,计算从N=2到N=64时的最小逼近误差RMSE和硬件复杂度C。
问题二：
使用类似问题1的对角矩阵分解方法。
根据约束条件2,每个对角矩阵的非零元素取值为整数集P中的值。
通过穷举P中的值,选择肯定使逼近误差最小的元素值。
硬件复杂度计算同样根据矩阵乘法次数,且考虑元素取值范围q=3。
1. F_4 的定义如下:
$$
F_4 = \frac{1}{2} \begin{bmatrix}
1 & 1 & 1 & 1\
1 & j & -1 & -j\
1 & -1 & 1 & -1\
1 & -j & -1 & j
\end{bmatrix}
$$ 2. 将其分解为4个对角矩阵Di:
$$
F_4 \approx D_1D_2D_3D_4
$$ 其中Di是仅第i个对角元素非零的对角矩阵。 3. 根据元素取值范围P={0,±1,±2},对Di的非零元素取值进行穷举,选择误差最小的取值:
$$
\begin{aligned}
D_1 &= \begin{bmatrix}
1 & 0 & 0 & 0\