一种基于无标度复杂网络LDPC码的压缩感知方法

摘要

本发明提供了一种基于无标度复杂网络LDPC码的压缩感知方法，该压缩感知方法包含感知矩阵的构造和信号重构算法两个过程，其特征在于包括以下步骤：将信号x采用合适的基函数来稀疏表示；构造低复杂度无标度网络不规则LDPC码的校验矩阵H；将无标度网络LDPC码的校验矩阵H作为压缩感知算法的感知矩阵Φ，并计算测量值y=Φx；利用置信度传播（BP）译码算法从测量值中重构原始信号。本发明将所构造的良好性能的无标度网络LDPC码应用于压缩感知中，并利用其译码方法实现了压缩感知信号重构。可应用于信号处理、图像处理、纠错编码以及雷达成像等领域，具有广阔的应用前景。

说明书

技术领域

本发明涉及信号处理领域，更具体的说，涉及信号处理中的采样与信 号重构技术领域。

背景技术

压缩感知（Compressive Sensing,CS）是近年来出现的一种全新的、 快速发展的信息获取与处理的理论。压缩感知的问题就是从M维线性测 量y=Φx中恢复出N维信号x∈R^N，其中，y∈R^M，Φ是一已知的M×N矩 阵。当M＜＜N时，线性系统是欠定的。但是如果信号x是非常稀疏的， 那么即使M＜＜N，压缩感知也能从很少的线性测量y中重建信号x。压 缩感知以其优越于传统采样定理和信号重构的性能，得到了众多研究 人员的重视和广泛的研究。压缩感知的研究主要集中在三个方面，一 是优秀的感知矩阵的构造研究；二是优秀的信号重构算法的研究；三 是压缩感知的应用研究。

压缩感知与纠错编码之间有着密切联系。压缩感知在伽罗华域GF(2)域 中从线性测量中重建信号的问题相当于设计二进制线性纠错码。即本 质上压缩感知和编码理论均是需要设计感知矩阵及相应的译码算法。 因此，纠错码的译码算法可以用于压缩感知稀疏信号的重构。

基于编码理论的信号重建方法也被应用于压缩感知的信号重建中，但 是有的设计中感知矩阵是稠密的，因而计算复杂度较高；有的虽然设 计了稀疏的低密度奇偶校验（Low Density Parity Check,  LDPC）码感知矩阵，但使用的是规则的LDPC码。

不规则LDPC码较规则LDPC码有着不同的度分布，因而具有更好的、逼 近香农极限的误码性能。信息传递算法（Message Passing Algori thm）是一种用来逼近最大似然法译码最优性能的迭代译码算法，基于 Tanner图模型的LDPC译码是一种置信度传播（Belief Propagation,  BP）算法，其迭代路径的长短对迭代译码的时间有重要的影响。

无标度网络是较接近现实世界的一种网路模型，其重要特性是节点的 连接度分布满足幂律分布规律，大部分节点具有很小的连接数，只有 一小部分节点具有很大的连接数。与其他网络相比，无标度网络具有 最小数目的连接数，能够达到最短的平均路径。

据此，我们将编码理论应用于感知矩阵的构造并将其译码算法用于CS 信号的重构。我们需要构造具有无标度网络特性的不规则LDPC码，以 及将其置信度传播（Belief Propagation，BP）译码用于CS稀疏信号 的重构。这样，能够以更少的测量值来重构原始稀疏信号，降低算法 复杂度。

发明内容

为了解决上述问题，本发明设计一种基于无标度复杂网络LDPC码的压 缩感知方法，其结合编码译码理论的角度来对压缩感知中感知矩阵的 构造以及信号重构算法进行研究，在无标度不规则LDPC码的感知矩阵 构造过程中同时关注了利用置信度译码算法对压缩感知信号的重构。

本发明提出了一种基于无标度复杂网络LDPC码的压缩感知方法，该压 缩感知方法包含感知矩阵的构造和信号重构算法两个过程， 其特征在于包括以下步骤：将信号x采用合适的基函数来稀疏表示；构 造低复杂度无标度网络不规则LDPC码的校验矩阵H；将无标度网络LDP C码的校验矩阵H作为压缩感知算法的感知矩阵Φ，并计算测量值y=Φ x；利用置信度传播（BP）译码算法从测量值中重构原始信号。本发明 将所构造的良好性能的无标度网络LDPC码应用于压缩感知中，并利用 其译码方法实现了压缩感知信号重构。

通过本发明提出的方案利用无标度网络具有最小数目的连接数和最短 的平均路径的特性，构造了性能优良且复杂度较低的无标度网络不规 则LDPC码；然后，将稀疏的不规则LDPC码校验矩阵作为压缩感知矩阵 ，利用信道编码理论中的置信度传播BP算法实现了信号重构。

附图说明

图1为本发明提出的构造无标度不规则LDPC码作为感知矩阵的方法流程 图。

图2为根据本发明的无标度网络LDPC码的构造方法所得到的一种感知矩 阵示例。

图3为将本发明的无标度网络LDPC码与现有的采用密度进化构造的好码 的迭代次数对比实验结果。

图4为将本发明的构造无标度不规则LDPC码作为感知矩阵，并采用置信 度译码算法实现严格稀疏信号重构的实验结果。

图5为将本发明的构造无标度不规则LDPC码作为感知矩阵，并采用置信 度译码算法实现近似稀疏信号重构的实验结果。

图6为将本发明的构造无标度不规则LDPC码作为感知矩阵，并采用置信 度译码算法实现可压缩信号重构的实验结果。

具体实施方式

以下结合附图对本发明的原理和特征进行描述，所举实例只用于解释 本发明，并非用于限定本发明的范围。

压缩感知（Compressive Sensing,CS）是近年来出现的一种全新的、 快速发展的信息获取与处理的理论。压缩感知的问题就是从M维线性测 量y=Φx中恢复出N维信号x∈R^N，其中，y∈R^M，Φ是一已知的M×N矩 阵。当M＜＜N时，线性系统是欠定的。但是如果信号x是非常稀疏的， 那么即使M＜＜N，压缩感知也能从很少的线性测量y中重建信号x。压 缩感知以其优越于传统采样定理和信号重构的性能，得到了众多研究 人员的重视和广泛的研究。压缩感知的研究主要集中在三个方面，一 是优秀的感知矩阵的构造研究；二是优秀的信号重构算法的研究；三 是压缩感知的应用研究。

压缩感知与纠错编码之间有着密切联系。压缩感知在伽罗华域GF(2)域 中从线性测量中重建信号的问题相当于设计二进制线性纠错码。即本 质上压缩感知和编码理论均是需要设计感知矩阵及相应的译码算法。 因此，纠错码的译码算法可以用于压缩感知稀疏信号的重构。

基于编码理论的信号重建方法也被应用于压缩感知的信号重建中，但 是有的设计中感知矩阵是稠密的，因而计算复杂度较高；有的虽然设 计了稀疏的低密度奇偶校验（Low Density Parity Check, LDPC ）码感知矩阵，但使用的是规则的LDPC码。

不规则LDPC码较规则LDPC码有着不同的度分布，因而具有更好的、逼 近香农极限的误码性能。信息传递算法（Message Passing Algori thm）是一种用来逼近最大似然法译码最优性能的迭代译码算法，基于 Tanner图模型的LDPC译码是一种置信度传播（Belief  Propagation, BP）算法，其迭代路径的长短对迭代译码的时间有重 要的影响。

无标度网络是较接近现实世界的一种网路模型，其重要特性是节点的 连接度分布满足幂律分布规律，大部分节点具有很小的连接数，只有 一小部分节点具有很大的连接数。与其他网络相比，无标度网络具有 最小数目的连接数，能够达到最短的平均路径。

据此，我们将编码理论应用于感知矩阵的构造并将其译码算法用于CS 信号的重构。我们需要构造具有无标度网络特性的不规则LDPC码，以 及将其置信度传播（Belief Propagation，BP）译码用于CS稀疏信号 的重构。这样，能够以更少的测量值来重构原始稀疏信号，降低算法 复杂度。

因此，本发明提出了一种基于无标度复杂网络LDPC码的压缩感知方法 ，其利用无标度复杂网络连接度最小和平均路径长度最短的特性，构 造出低复杂度无标度网络不规则LDPC码的校验矩阵H；然后将无标度网 络LDPC码的校验矩阵H作为压缩感知算法的感知矩阵Φ，并计算测量值 y=Φx；最后利用置信度传播（BP）译码算法从测量值中重构原始信号 。

图1示出了本发明提出的构造无标度不规则LDPC码作为感知矩阵的方法 流程图。步骤如下：

步骤1，根据无标度网络幂律分布，给出变量节点的度分布序列，限制 校验节点的度数为2个常数值。

步骤2，控制度为i的变量节点按照i大小，按照升序从矩阵的左至右排 列；

步骤3，使用PEG算法在步骤2的约束下，构造矩阵H；

步骤4，检验H矩阵中是否含有四环，如有则找出，并利用四环搜索算 法删除一定数量1达到无四环矩阵。

这时，将得到最终的无标度不规则LDPC码感知矩阵，其具有迭代路径 短，收敛速度快等优点。

图2示出了根据本发明的无标度网络LDPC码的构造方法所得到的一种感 知矩阵，其参数如下：码长为1008，校验位长度为504。

在得到了构造的无标度网络不规则LDPC码的校验矩阵后，进行仿真实 验。采用AWGN信道，BPSK调制，仿真结果如图3所示。图3示出了将本 发明的无标度LDPC码与现有的采用密度进化构造的好码进行迭代次数 对比的实验结果。从图3中可以看出，与密度进化的好码相比，迭代路 径缩短后，迭代次数有所降低。

压缩感知在伽罗华域GF(2)中从线性测量中重构信号的问题相当于设计 二进制线性纠错码。即本质上压缩感知和编码理论均是需要设计测量 矩阵Φ及相应的译码算法，使得当x为稀疏信号时，能够从线性测量y =Φx中可靠重建信号x。因此，纠错码的译码算法可以用于压缩感知稀 疏信号的重构。

基于无标度网络LDPC码的压缩感知处理方法分以下步骤：

步骤1，利用两状态的高斯混合分布模型来建模稀疏信号的系数。其概 率密度函数分别表示为：

$f\left(X\left(i\right)\right|Q\left(i\right)=1)~N(0,{\sigma }_1^2)---\left(1\right)$

$f\left(X\left(i\right)\right|Q\left(i\right)=0)~N(0,{\sigma }_0^2)---\left(2\right)$

其中Q为状态变量。

步骤2，构造低复杂度无标度不规则LDPC码的校验矩阵H；

按照低复杂度无标度LDPC码的算法流程图1，构造出平均路径 最短、性能优良的无标度LDPC校验矩阵H。

步骤3，将无标度LDPC码的校验矩阵H作为压缩感知算法的感知矩阵Φ ，计算测量值y=Φx；

压缩感知问题可看作为校正子信源编码问题^]，即通过校正子s=Hx将N 维信号x∈F^N压缩到M维观测矢量，其中H∈F^M×N为线性分组码(N,K)的奇 偶校验矩阵。由于无标度LDPC码的校验矩阵H非常稀疏，因此得到较少 的测量值。

步骤4，利用置信度BP译码算法从测量值中重建原始信号。

译码通过在与测量矩阵Φ相关联的二分图上利用置信传播算法来实现 ，即在已知信源x的先验知识时，译码器通过使后验概率Pr(x|s)最大 来重建x。

LDPC码的BP译码算法中置信消息在节点上处理后沿着校验节点和变量 节点之间的边进行传递。每次迭代包括校验节点和变量节点的处理。 每次迭代中，所有校验节点从其相邻的变量节点处接收消息，处理后 ，再传回到相邻的变量节点；然后所有的变量节点进行同样的过程； 最后变量节点收集所有可以利用的消息进行判决。

即采用迭代更新规则:

$m_{v\to c}\left(v\right)=\underset{u\in n\left(v\right)/\left\{c\right\}}{\Pi }{m}_{u\to c}\left(v\right)---\left(3\right)$

$m_{v\to c}\left(v\right)=\underset{~\left\{v\right\}}{\Sigma }\left(\mathrm{con}\left(n\left(c\right)\right)\underset{w\in n\left(c\right)/\left\{v\right\}}{\Pi }{m}_{u\to c}\left(w\right)\right)---\left(4\right)$

$f\left(v\right)=\underset{u\in n\left(v\right)}{\Pi }{m}_{u\to c}\left(v\right)---\left(5\right)$

其中，m_v→c(v)表示从变量节点到校验节点的信息，由m_c→v(v)表 示从校验节点到变量节点的信息；n(v)和n(c)分别为二分图中变量节 点和校验节点的邻集；con(n(c))表示变量节点集n(c)上的约束；～{ v}表示去除v后校验节点的邻集。给定变量节点的边缘分布f(v)通过计 算所有沿着连接到该节点的边的信息乘积来得到。

采用下列仿真参数，分别针对严格稀疏信号、近似稀疏信号以及可压 缩信号的情况，进行了基于无标度网络LDPC码的压缩感知处理方法的 仿真实验，利用置信度传播BP译码算法实现了信号重构。

信号长度：N=1008   稀疏信号方差： （严格稀疏信号情况） （近似稀疏信号情况）  稀疏度：0.02   噪声方差：    可压缩信号系数：q=0.5      稀疏测量矩阵H维度：M=504   N=1008

图4、图5和图6分别示出了针对严格稀疏信号、近似稀疏信号、可压缩 信号，将构造的无标度不规则LDPC码作为感知矩阵，并采用置信度译 码算法实现压缩感知信号重构的实验结果。计算得到原始信号与重构 信号的均方误差分别为1.12、26.09和36.09。可见，本发明提出的基 于无标度复杂网络LDPC码的压缩感知方法能够利用很少的测量值来实 现信号的重构。

以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发 明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包 含在本发明的保护范围之内。