摘要：
针对压缩感知重构算法中正交匹配追踪(OMP)算法在每次迭代中不能选取最优原子问题，对OMP算法进行优化设计，保证了每次迭代的当前观测信号余量最小，并提出了一种基于FPGA 实现的优化OMP算法硬件结构设计。在矩阵分解部分采用了修正乔列斯基(Cholesky)分解方法，回避开方运算，以减少计算延时，易于FPGA实现。整个系统采用并行计算、资源复用技术，在提高运算速度的同时减少资源利用。在Quartus II 开发环境下对该设计进行了RTL 级描述，并在FPGA仿真平台上进行仿真验证。仿真结果验证了设计的正确性。
中文引用格式：蒋沅，沈培，代冀阳，等. 一种基于FPGA实现的优化正交匹配追踪算法设计[J].电子技术应用，2015，41(10)：73-76，80.
英文引用格式：Jiang Yuan，Shen Pei，Dai Jiyang，et al. An orthogonal matching pursuit algorithm optimization design based on FPGA implementation[J].Application of Electronic Technique，2015，41(10)：73-76，80.
❖
0 引言
传统信号获取和处理过程主要采用奈奎斯特采样定律实现，而奈奎斯特采样定律要求采样频率不得低于模拟信号频谱中最高频率的两倍，这使得高频信号采集实现受到极大限制。随着信息技术快速发展，信号带宽急剧增加，工业进入大数据时代，因此对信号处理能力和硬件设备要求也越来越高，给庞大数据处理带来了挑战[1]。
压缩感知理论[2]具有数据采集与压缩同时进行处理的优点，用较少的数据就可以准确地恢复原始信号，从而使得受制于奈奎斯特采样定理的采样频率能够挣脱束缚，在较低的采样频率下也能够实现。压缩感知理论包括三方面内容：信号稀疏表示、测量矩阵的构造、信号重构算法设计。信号重构算法设计是压缩感知理论研究关键的优化算法和基于贪婪迭代的匹配追踪算法。以正交匹配追踪算[4](Orthogonal Matching Pursuit，OMP)为代表的贪婪类及其改进算法[5-6]相对于其他方法具有信号重建速度快、运算量小等优点。
目前，压缩感知信号重构硬件设计还处于初步阶段，仍有许多问题值得探究，学者们在这方面做了一系列工作。文献[7]对压缩感知信号重构算法进行超大规模集成电路(Very Large Scale Integration，VLSI)设计。按照特定顺序对OMP算法硬件设计执行资源复用技术，提高了资源利用率，运行速率更快[8]。文献[9]阐述了基于FPGA的LU分解方法，能够在计算机平台上得到很好的加速性能，然而，在LU分解过程中存在大量矩阵乘除法运算，需要占用FPGA大量硬件资源，导致运算延迟。本文在矩阵分解部分采用修正Cholesky分解方法，回避了开方运算，减少了乘法运算次数，使运算速度更快。
1 正交匹配追踪算法
在压缩感知采样过程中，原始信号x∈RN稀疏度为K(K<
2 优化正交匹配追踪算法设计
2.1 优化正交匹配追踪算法原子选择准则
利用参考文献[6] 结论，得出测量值y在Vn+1上的正交投影式：
在式(3)基础上得出y在Vn+1上的正交投影系数为（其中K=1，2，…，n）：
经过第n+1次迭代后，||rn+1||2=||y||2-〈Py，y〉测量值y固定不变，要使观测信号余量r最小，等价于〈Py，y〉最大化，由式(1)~式(4)可得：
2.2 优化正交匹配追踪算法计算步骤
分析了优化正交匹配追踪算法原子选择准则后，优化后的OMP算法的重构算法计算步骤如下：
步骤1：初始化=0，r0=0，n=1。
步骤2：选择当前观测信号余量rn-1最匹配的原子索引n=argmaxl=1，2，…，N Cl。
步骤3；更新候选子集?祝n=?祝n-1∪?姿n，记录传感矩阵中的重构原子集合n=[n-1，f]。
步骤4：利用索引集中现有的原子逼近原始信号：n=argminy-n。
步骤5：更新残差：
步骤6：n=n+1，如果n
2.3 优化正交匹配追踪算法硬件结构设计
优化OMP算法可以分为4个模块，第1个模块对应重构算法计算步骤2，经过原子选择，利用式(1)~式(5)求出残差最匹配原子。
第2个模块对应重构算法计算步骤3，通过更新候选子集?祝，生成增广矩阵n。
第3个模块对应重构算法计算步骤4，求解l0范数最小模型问题，解决最小二乘法问题，得到原始信号的估计值。求解增广矩阵逆的方法来得出原始估计值。然而，矩阵是非方形矩阵，对于求非方形矩阵一般是使用伪逆(Moore-Penrose)的方法求解，矩阵伪逆可以表示为：
式(7)中，令G=T×，以上问题就直接转换成求解G逆。G∈Rt×t是一个对称正定矩，如直接进行求解，在FPGA上不易实现，可以先对矩阵G进行矩阵分解，再求逆。
矩阵分解有QR分解[10]、奇异值分解、LU分解、Cholesky分解[11]。QR分解和奇异值分解计算过程复杂，不易于FPGA的实现，LU分解在分解过程中会有大量的矩阵乘法和除法的计算操作，它一方面占用FPGA硬件资源，另一方面影响计算效率。虽然，在Cholesky分解计算中会产生开方操作的延时以及除法计算，但是复杂度相对于LU分解较少。针对Cholesky分解在计算中产生开方操作的延时问题，利用Cholesky分解，回避了开方运算带来的延时问题。具体修正Cholesky分解计算公式如下：
第4个模块对应重构算法计算步骤5，计算残差r，为下次迭代做准备。
3 基于FPGA实现的优化OMP算法
硬件电路主要由四个模块组成，分为两大部分。具体电路图如图1所示。
第一部分给定两个输入量，分别是测量矩阵观测矢量y，由输入的观测矢量y∈RN对残差r进行初始化。每个矩阵的列向量长为N，设计N个乘法器和N-1个加法器并行处理，它们可以在一个时钟周期内完成工作，测量矩阵?椎和残差r同时也在一个时钟内完成。观测矢量y用多个寄存器组进行存储，用多个RAM存储测量矩阵值。利用式(1)~式(6)优化后的原子选择准则求出原子索引?姿n，通过步骤3更新候选子集得到重构矩阵，得出矩阵G。
第二部分对矩阵G求逆过程，硬件电路由Cholesky分解硬件电路、矩阵L求逆硬件电路和相乘运算硬件电路组成。利用修正的Cholesky分解矩阵G，分解矩阵G分别要求出下三角矩阵L和对角矩阵D。然后进行相乘，使得G=L×D×LT，从而回避平方操作。其中矩阵L和矩阵D之间是相互依存的，其元素必须按照特定的顺序进行计算。最后对G-1求解，G-1=(L-1)T×D-1×L-1，可以先令O=(L-1)T×D-1，对O进行计算，然后可方便计算G-1=O×L-1。
4 仿真验证
通过一维信号对优化OMP算法和OMP算法进行重建实验比较。假设稀疏信号x的长度N=256，稀疏系数k=6，OMP、优化OMP算法采用高斯随机测量矩阵RM×N，分别记录优化OMP算法和OMP算法的重建成功率，将其结果绘制成图，如图2所示。
在同样处理器工作下，通过二维图像信号实验验证优化OMP算法的有效性。实验中选取尺度为256像素×256像素的经典实验图像Lena，采用高斯随机矩阵作为测量矩阵。OMP算法与本文优化OMP算法进行重构实验对比，重构结果如图3所示。
当采样率M/N=50%，采用Lena图像测试时，优化OMP算法、OMP算法信噪比分别为34.53 dB、33.72 dB。因此，优化后的OMP算法比OMP算法重建精度要高。
通过FPGA仿真软件Modelsim对优化OMP算法硬件电路进行了仿真，如图4所示。
5 结论
本文通过优化原子选择准则，使得OMP重建本文算法能够在很短的时间内选择最优原子，缩短了信号重构时间，提高了算法重建速率。同时，本文优化设计了FPGA硬件结构，较好地平衡了占用资源和运算时间。本设计采用硬件描述语言Verilog HDL对优化OMP重建算法实现，运用Quartus软件进行算法综合，进行了RTL级描述，通过Matlab和Modelsim进行联合仿真，得到了较好的重建效果。结果表明，优化后的OMP算法能够以较少时间恢复原始信号。
参考文献
[1] 任越美，张艳宁，李映.压缩感知及其图像处理应用研究进展与展望[J].自动化学报，2014，40(8)：1563-1575.
[2] DONOHO D.Compressed sensing[J].IEEE Trans.Info.Theory，2006，52(4)：1289-1306.
[3] 莫禹钧，柏正尧，黄振，等.正交匹配追踪算法的优化设计与FPGA实现[J].电子技术应用，2014，50(10)：79-82.
[4] WANG J，KWON S，SHIM B.Generalized orthogonal matching pursuit[J].IEEE Trans.on Signal Processing，2012，60(12)：6202-6216.
[5] WU R，HUANG W，CHEN D R.The exact support recoveryof sparse signals with noise via orthogonal matching pursuit[J].IEEE Trans.on signal processing letters，2013，20(4)：403-406.
[6] 李少东，裴文炯，杨军，等.贝叶斯模型下的OMP重构算法及应用[J].系统工程与电子技术，2015，37(2)：246-252.
[7] SEPTINUS A，STEINBERG R.Compressive sampling hardware reconstruction[C].Circuits and systems(ISCAS)，Proc.of2010 IEEE Internatioal symposium on.IEEE，2010：316-3319.
[8] BLACHE P，RABAH H，AMIRA A.High level prototyping and FPGA implementation of the orthogonal matching pursuitalgorithm[C].Information Scien，Signal Processing and their Applications(ISSPA)，2012：1336-1340.
[9] WU G，DOU Y，PETERSON G D.Blocking LU decomposi-tion for FPGAs[C].IEEE.Proceeding of FCCM′10.ChArlotte：IEEE，2010：109-112．
[10] STANISLAUS J.L.V.M，MOHSENIN T.High performance compressive sensing reconstruction hardware with QRD process[C].Circuits and Systems(ISCAS)，2012，IEEE.International Symposium on.IEEE，2012：29-32.
[11] 魏婵，娟张春，水刘健.一种基于Cholesky分解的快速矩阵求逆方法设计[J].电子设计工程，2014，22(1)：159-164.