DFT类矩阵的整数分解逼近

离散傅里叶变换（Discrete Fourier Transform，DFT）傅里叶分析方法是信号分析的最基本方法，傅里叶变换是傅里叶分析的核心，通过它把信号从时间域变换到频率域，进而研究信号的频谱结构和变化规律。在芯片设计中，DFT计算的硬件复杂度与其算法复杂度和数据元素取值范围相关。算法复杂度越高、数据取值范围越大，其硬件复杂度就越大。常规的降低硬件复

杂度的方法如快速傅里叶变换已经渐渐无法满足芯片日益增长的需求。因此，急需设计新的算法，此算法不仅能是误差控制在一定范围内，又能有效降低 DFT 过程带来的硬件复杂度过大的问题。

针对第一问，本问不用考虑分解后矩阵A的取值范围的问题，只需要满足分解后的矩阵每行至多只有2个非零元素，以及最小误差尽可能低的约束条件下，计算出近似矩阵的硬件复杂度。本问选择了三种模型来计算 DFT 矩阵的最小误差和硬件复杂度。奇异值分解法通过特征向量将DFT矩阵进行分解，同时还达到了降维的目的，通过将DFT矩阵分解成三个矩阵来使误差达到最小；分块矩阵分解法通过将 DFT 矩阵分解成一个个小的分块矩阵，因为维数越小分块子矩阵形式越简单，误差显著降低；矩阵乘法拟合则利用 DFT 矩阵的对称性和穷举法将矩阵分解成多个矩阵连乘的形式。

针对第二问，本问不用考虑每行非零元素个数的问题，只需要满足分解后的矩阵每个元素的取值范围，以及在N=2，4，8，16，32的情况以及最小误差尽可能低的约束条件下，计算出近似矩阵的硬件复杂度。本问选择了三种模型来计算 DFT 矩阵的最小误差和硬件复杂度。蝶形运算分解法运用了快速傅里叶变换的思想，在此基础上利用蝶形变换将DFT矩阵进行分解；分块矩阵分解法和矩阵乘法拟合在解决问题二是仍然适用。

针对第三问，本问需要同时考虑每行非零元素个数的以及分解后的矩阵每个元素的取值范

围的约束条件，在此基础上，在最小误差尽可能低的约束条件下，计算出近似矩阵的硬件复杂度。本问选择了两种模型来计算 DFT 矩阵的最小误差和硬件复杂度，即分块矩阵分解法和矩阵乘法拟合。这两种方法在多种约束条件下仍能够很好的解决问题。

针对第四问，本问需要考虑如何对 4 点 DFT矩阵与8 点 DFT 矩阵的 Kronecker 积的矩阵FN进行矩阵分解，在最小误差尽可能低的约束条件下，计算出近似矩阵的硬件复杂度。本问选择通过 SVD+穷举法的模型来计算 DFT 矩阵的最小误差和硬件复杂度。首先对 4 点 DFT 矩阵与8点DFT矩阵进行SVD分解，之后利用Kronecker积的性质将FN矩阵转化为多个矩阵相乘的形式。

针对第五问，本问需要同时考虑每行非零元素个数的以及分解后的矩阵每个元素的取值范围的约束条件，在此基础上增加将精度限制在0.1以内，即RMSE≤0.1的要求，计算出近似矩阵的硬件复杂度。本问选择分块矩阵分解模型对第三问结果矩阵进行进一步优化，在满足题目要求下，计算出分解后矩阵的最小误差和硬件复杂度。

关键词：离散傅里叶变换、奇异值分解法、分块矩阵分解法、矩阵乘法拟合、蝶形

运算分解法、Kronecker积 

一、问题背景及分析

1.1问题背景

离散傅里叶变换（Discrete Fourier Transform，DFT）作为一种基本工具广泛应用于工程、科学以及数学领域。例如，通信信号处理中，常用DFT实现信号的正交频分复用。另外在信道估计中，也需要用到逆DFT（IDFT）和DFT以便对信道估计结果进行时域降噪。  

在芯片设计中，DFT计算的硬件复杂度与其算法复杂度和数据元素取值范围相关。算法复杂度越高、数据取值范围越大，其硬件复杂度就越大。目前在实际产品中，一般采用快速傅里叶变换（Fast Fourier Transform，FFT）算法来快速实现DFT，其利用DFT变换的各种性质，可以大幅降低 DFT 的计算复杂度。FFT 算法，是离散傅里叶变换的快速算法，它是根据离散傅里叶变换的奇、偶、虚、实等特性，对离散傅里叶变换的算法进行改进获得的，在计算机系统或者说数字系统领域是重大进步。然而，随着无线通信技术的演进，天线阵面越来越大，通道数越来越多，通信带宽越来越大，对FFT的需求也越来越大，从而导致专用芯片上实现FFT的硬件开销也越大。以进一步降低芯片资源开销为目的，提出了一种可行的思路，即将DFT矩阵分解成整数矩阵连乘的形式。

目前使用 FFT 进行 DFT 计算的方案硬件复杂度较高，虽然大幅降低了硬件复杂度，但损失了一定的计算精度。因此本题希望研究一种替代方案来降低 DFT 计算的硬件复杂度，但同时对精度也有一定要求。因此本题希望通过设计一种矩阵分解方式，使分解后的矩阵既能最小化RMSE，同时又使得乘法器的数量尽量少。

1.2问题分析

1.2.1问题一分析
          根据题意，问题一的目标是降低硬件复杂度，即对 DFT 矩阵的分解方法进行优化，然后通过数学方法，例如线性规划或整数规划等求解题目中的目标函数并使分解矩阵集中的各元素符合约束条件1，即每行中非零元素不多于两个，相当于对矩阵的稀疏性进行限制，然后在此

条件下找到合适的矩阵𝓐和缩放因子使RMSE最小化以寻求符合题意的最佳分解方案。

1.2.2问题二分析
          问题二的目的同问题一：在降低硬件复杂度的同时，最小化分解误差，但是是在约束2的条件下，即对分解矩阵中各元素的实部和虚部的取值范围进行了约束，相当于在考虑元素取值范围的情况下，探究出一种最合适的分解方案。

1.2.3问题三分析
          在同时满足约束1和约束2的条件下，优化DFT矩阵的分解，最小化误差和硬件复杂度。可以理解为此题是建立在问题一和问题二的基础上，对矩阵的稀疏性和各元素的取值范围进行了限制，但最终目的仍为对 DFT 矩阵分解方案的探究，因此可以借鉴前两题的分解方案，然后根据约束条件对方法进行优化。

1.2.4问题四分析

对于DFT矩阵

F 和 N1

FN2

的Kronecker积

F 进行研究。要求在

N 1

=

4,

N

2

=

8

，满足约束1、

约束2的条件下，对A和进行优化，找到最小误差的方案并计算复杂度C。

1.2.5问题五分析
          本题的重点在于在问题三的基础上加上精度的限制来研究矩阵分解方案，即需要在同时满

足约束1和约束2的情况下，满足最小误差

RMSE0.1

的条件，通过对模型变量进行优化，以减少硬件复杂度

二、模型假设

⚫     本题中硬件复杂度指标仅考虑乘法器的个数和每个乘法器的复杂度；

⚫     本题中乘法器的个数为复乘的次数，乘法器的复杂度只跟矩阵中各元素的取值范围有关；

⚫     在复数计算中，与0、±1、±𝑗或(±1 ± 𝑗)相乘时不计入复数乘法次数。

三、符号定义及说明

符号	意义
𝑁	矩阵的维数
𝐅𝑁	N维DFT矩阵
𝓐	矩阵分解后的矩阵集
RMSE(𝓐, 𝛽)或 RMSE	精度
𝐶	硬件复杂度
q	分解后的矩阵𝐀𝑘中元素的取值范围
L	复数乘法的次数
𝛽	实值矩阵缩放因子
K	𝓐中矩阵的个数

 

对于给定硬件复杂度计算式：

C

=

q



L

          由于q指示分解后的矩阵中元素的取值范围，由分解结果可知元素实部和虚部的取值范围为[-1，0，1]，即q=1。即硬件复杂度计算式C=1×0=0。

对于给定最小误差计算式：

当β位于FN前面时，由公式可得：

min RMSE( ,	,	)	=	1	‖F − N	A A 1	2	A	2 ‖ K F
				N

当β位于A1A2A3前面时，由公式可得：

min RMSE( ,	,	)	=	1	‖F − N	A A 1	2	A	2 ‖ K F
				N

将矩阵分解结果借助MTLAB工具对目标函数进行分析，得到结果为：

图5.2 原目标函数下β取值时的最小误差

 

图5.3 修改后目标函数下β取值时的最小误差

          分析结果可得，无论β取何值，当N=4时，最小误差皆为0，此时β取值均为一，此时精度达到最高，硬件复杂度也达最低值。

t=3，N=8时：

问题总结与评价

6.1模型优点

分块矩阵分解模型优点：对矩阵进行适当分块，可使高阶矩阵的运算转化为低阶矩阵的运算，同时也使原复杂矩阵的结构显得简单而清晰，从而能够大大简化运算步骤。本文通过构造分块矩阵分解模型，通过对矩阵进行分块运算，减少了矩阵分解的运算量，并且使得分解后的矩阵形式简洁清晰。

矩阵乘法拟合方法优点：矩阵乘法拟合主要根据 DFT 矩阵的对称性，选择参数变量 a 的定义域来找到DFT近似矩阵，由于其定义域的确定和穷举法的结合，使得DFT的分解矩阵满足题目中的约束。

          奇异值分解法优点：此方法基于在线性代数中矩阵常见的分解方法奇异值（SVD）分解，所以有很多成熟的程序函数对其进行分解，计算效率高。

6.2模型缺点与改进方向

分块矩阵分解模型改进：分块矩阵的应用可以简化矩阵分解的运算和降低分解维数，本文构造的分块矩阵分解模型在维数较低时分解较容易，如二维或四维矩阵，但在高维矩阵时，即使运用了分块矩阵的思想也仍具有一定的复杂度。故应用该模型前，可先用矩阵的常规分解方法先对矩阵进行初步的预处理，再运用分块矩阵分解模型对矩阵进行适当分块，即可提高矩阵分解效率以及准确性。

          矩阵乘法拟合方法的改进：矩阵乘法拟合对于取值范围较小的 N 来说可以很好的进行计算。但是随着N值的增长，使用穷举法进行搜索空间会呈指数级增长，使得问题计算量倍增。

因此在N值较大时需要使用梯度下降法确定一定的取值范围后再使用穷举法进行计算

代码

部分matlab源程序代码

n=8;

for B=0:0.01:1

  f=dftmtx(n);

A1=[        1,0,0,0,1,0,0,0;

  0,1,0,0,0,1-i,0,0;

  0,0,1,0,0,0,-i,0;

  0,0,0,1,0,0,0,-1-i;

  1,0,0,0,-1,0,0,0;

  0,1,0,0,0,-1-i,0,0;

  0,0,1,0,0,0,i,0;

  0,0,0,1,0,0,0,1-i];

  A2=[1,1,1,1,0,0,0,0;

  1,1-i,-i,1-i,0,0,0,0;

  1,-i,-1,-i,0,0,0,0;

  1,1-i,-i,1-i,0,0,0,0;

  0,0,0,0,1,1,1,1;

  0,0,0,0,1,1-i,-i,1-i;

  0,0,0,0,1,-i,-1,-i;

  0,0,0,0,1,1-i,-i,1-i];

  A3=[1,0,0,0,0,0,0,0;

  0,0,1,0,0,0,0,0;

  0,0,0,0,1,0,0,0;

  0,0,0,0,0,0,1,0;

  0,1,0,0,0,0,0,0;

  0,0,0,1,0,0,0,0;

  0,0,0,0,0,1,0,0;

  0,0,0,0,0,0,0,1];

  C=B*f-A1*A2*A3;

  C=norm(C,'fro');

  C=abs(C);

  RMSE=C/n;

  RMSE=RMSE/sqrt(n);

  plot(B,RMSE,'r>');

  hold on

end

第4问最小误差公式实现

  w=[0,0,4+i,4+i;

  0,0,3i,-5-i;

  0,0,-4+i,4;

  0,0,-5i,-3-i];

  u=[3-i,0,0,0,0,0,0,0;

  3i,0,0,0,0,0,0,-i;

  0,0,0,0,2+2i,0,0,0;

 

  0,0,0,0,0,0,0,3i;

  0,0,-4,0,0,0,0,-4;

  1+3i,0,2-i,0,0,0,0,0;

  0,0,5-i,0,-4-i,0,0,0;

  -3i,0,-3+i,0,0,0,0,0];

  s=[1,0,0,0;

  0,1,0,0;

  0,0,1,0;

  0,0,0,1];

  d=[1,0,0,0,0,0,0,0;

  0,1,0,0,0,0,0,0;

  0,0,1,0,0,0,0,0;

  0,0,0,1,0,0,0,0;

  0,0,0,0,1,0,0,0;

  0,0,0,0,0,1,0,0;

  0,0,0,0,0,0,1,0;

  0,0,0,0,0,0,0,1];

  q=[-1,0,0,0;

  0,1,0,0;

  0,0,i,9+i;

  0,0,1,-3+2i];

  v=[0,0,0,0,0,-1,0,0;

  0,-4i,0,4-4i,0,0,0,0;

  -9+i,0,0,0,0,0,0,0;

  0,2-4i,4+4i,0,0,0,0,0;

  0,0,0,0,0,0,1,0;

  0,0,0,0,0,0,0,2+2i;

  0,1,0,0,0,0,0,0;

  0,0,3i,0,0,0,0,0];

A=kron(w,u);

B=kron(s,d);

C=kron(q.',u.');

C=C.';

n=32;

for i=-5:0.01:0

  f=dftmtx(n);

  D=i*f-A*B*C;

  D=norm(D,'fro');

  D=abs(D);

  RMSE=D/n;

  RMSE=RMSE/sqrt(n);

  plot(i,RMSE,'r>');

  hold on

end