基于最小均方差准则的LDPC分层BP译码算法及译码器结构

摘要

一种基于最小均方差准则的LDPC分层BP译码算法，该算法通过构造线性方程来逼近BP算法中校验节点处的运算公式来降低算法实现的复杂度，并且使用最小均方差准则求得线性方程系数的最优解来提高算法的译码性能。同时该算法引入分层译码的思想，可以提高算法的收敛性，减小对存储空间的需求。基于该算法，本发明提出一种用于多媒体无线传感网中，具有部分并行结构的LDPC码译码器结构。该译码器支持多种码长码率的LDPC码译码，并且具有占用系统资源少，数据吞吐率高，系统功耗低等优点。

说明书

技术领域

本发明涉及多媒体无线传感网通信系统，特别涉及多媒体无线传感网基带信号处理中的LDPC作为信道纠错码的译码方法及译码器结构实现。

背景技术

WMSN(多媒体无线传感网)是在传统WSN(无线传感器网络)基础上引入了音频、视频、图像等多媒体信息感知功能的一种新型传感器网络。它借助于节点上多媒体传感器感知周边环境的多媒体信息，通过多跳中继方式将数据传到信息汇聚中心。它综合了现代传感器技术，微电子技术，通信技术，嵌入式计算技术和分布式信息处理技术等多个学科，是新兴的交叉研究领域。并且由于其在军事国防，工农业，环境监测，生物医疗等重要领域具有十分广阔的应用前景，已经引起许多国家学术界和工业界的高度重视。

LDPC码是Gallager于1962年首先提出来的，近年来被Mackay等人重新发现，是继Turbo码后又一种性能接近香农限的纠错码，它的某些分类已经超过了Turbo码的性能并且无Turbo码的平层效应。LDPC码是一种线性纠错码，它的校验矩阵是一个稀疏矩阵，因而它的码字之间具有很好的距离特性。QC-LDPC(准循环低密度校验码)码，不同于一般的LDPC码，使用了准循环子矩阵来构造奇偶校验矩阵H(如下图所示)，也就是说奇偶校验矩阵H包含J×K个循环置换的单位子矩阵，每个子矩阵的大小都是m×m。其中表示一个大小为m×m的单位矩阵每行向右循环s_x，y得到的新矩阵。位置偏移量s_x，y是由公式a^(x-1)×b^(y-1)计算得到，其中a和b是Galois域(GF(m))元素。QC-LDPC码结合了一般LDPC码随机性的特点，又具有准循环结构的特性，其信道性能接近随机构造的LDPC码，其编译码电路大为简化，成为LDPC码走向应用的一种重要手段。QC-LDPC码在众多领域得到了广泛采用，许多工业标准已经采用或提案采用QC-LDPC码作为信道编码方案，同时还有望成为第四代移动通信的信道编码标准。本专利的具体实施将面向IEEE802.16e标准中使用的QC-LDPC码，包括1/2，2/3，3/4，5/6等多种码率。其单位子矩阵的大小从24到96，间隔为4，共19种，同时其码长从576到2304，间隔为96，共19种：

$H=\left(\begin{array}{ccccc}{I}_{s_{\mathrm{1,1}}}& I_{s_{\mathrm{1,2}}}& I_{s_{\mathrm{1,3}}}& ...& I_{s_{1,K}}\\ I_{s_{\mathrm{2,1}}}& I_{s_{\mathrm{2,2}}}& I_{s_{\mathrm{2,3}}}& ...& I_{s_{2,K}}\\ ·& ·& ·& & ·\\ ·& ·& ·& ...& ·\\ ·& ·& ·& & ·\\ I_{s_{J,1}}& I_{s_{J,2}}& I_{s_{J,3}}& ...& I_{s_{J,K}}\end{array}\right)$

目前应用最广泛的LDPC码译码算法是BP算法。其每次迭代包括两步：校验节点的处理和变量节点的处理。在每次迭代中，所以校验节点从其相邻的变量节点处接收消息，处理后，再传回到相邻的变量节点；然后所以的变量节点进行同样的过程；最后变量节点收集所有可以利用的消息进行判决。BP算法的译码性能优越，但其校验节点处的计算包含复杂的三角函数运算，使得其难于硬件实现，很难在实际工程中得到应用。

目前，LDPC码译码器结构包括完全并行结构、完全串行结构和部分并行结构。完全并行结构指校验矩阵中的校验节点和变量节点完全映射到硬件实现中，其译码速度快，数据吞吐量大，但是占用硬件资源多，复杂度高。完全串行结构指只采用一个校验节点处理单元和一个变量节点处理单元来串行的处理各个校验节点和变量节点。优点是可以大量节省硬件资源，但是译码速度太慢，数据吞吐量太小，特别是码长很大时。而部分并行结构，其介于完全并行结构和完全串行结构之间，在硬件实现复杂度和译码吞吐量之间取得了很好的折衷。

3.发明内容

本发明第一个目的是提供一种基于最小均方差准则的LDPC分层BP译码算法。

为了方便说明，下面定义算法中用到的变量。

表示第q次迭代中从变量节点n传递给校验节点m的信息(记为变量信息)。

表示第q次迭代中从校验节点m传递给变量节点n的信息(记为校验信息)。

Λ_n表示变量节点n的判决信息。

Nm表示和校验节点m相连的变量节点的集合。

与传统的BP算法不同，分层译码算法将LDPC码校验矩阵的行从上往下划分为组(每组包含相同数目的行)，称为层。然后依次在每层中进行译码，每层的输出以及信道信息作为下一层的输入进行译码。最后一层译码结束后进行奇偶校验来判决译码是否结束。对于某一层的译码，其算法如下：

$Q_{m,n}^q={\Lambda }_n-R_{m,n}^{q-1}---\left(1\right)$

$R_{m,n}^q=(\underset{j\in \{\mathrm{Nm}\backslash n\}}{\Pi }-\mathrm{sgn}\left(Q_{m,j}^q\right))\times ({\beta }_0+{\beta }_1\times \underset{j\in \{\mathrm{Nm}\backslash n\}}{\min }{Q}_{m,j}^q+{\beta }_2\times \underset{j\in \{\mathrm{Nm}\backslash n\}}{\sec .\min }{Q}_{m,j}^q...+{\beta }_{\rho }\times \underset{j\in \{\mathrm{Nm}\backslash n\}}{\max }{Q}_{m,j}^q)---\left(2\right)$

${\Lambda }_n=Q_{m,n}^q+R_{m,n}^q---\left(3\right)$

式(2)中信息的数目由该校验节点的度数决定，并按从小到大的顺序排列，其系数β₀，β₁，L，β_ρ可以通过下述过程求得。

针对传统的BP算法中校验信息的计算(见式(4))包含三角函数运算，硬件实现很复杂。本发明提出一种具体的改进方法如下：

$R_{m,n}^{q+1}=2\arctan h\left(\underset{j\in \{\mathrm{Nm}\backslash n\}}{\Pi }\tanh \frac{Q_{m,j}^q}{2}\right)---\left(4\right)$

首先定义某一个校验方程中除去某一符号外的其他符号绝对值组成的集合如式(5)，集合中的元素按升序排列，ρ为校验矩阵的行重。

$S=\{s_1,s_2,L,s_{\rho }\}=\left\{Q_{m,j}^q\right|j\in \{\mathrm{Nm}\backslash n\}\}---\left(5\right)$

再次构造线性方程R＝β₀+β₁s₁+β₂s₂+L+β_ρs_ρ(6)去逼近式(4)。

最后通过最小均方差准则来求得β₀，β₁，L，β_ρ的最优值，分三步获得。

第一步：计算(6)式和(4)式(即R和)差值的均方差。

$\Delta ({\beta }_0,{\beta }_1,L,{\beta }_{\rho })=E\left[{(R-R_{m,n}^{q+1})}^2\right]$

$=E\left[{({\beta }_0+{\beta }_1{s}_1+{\beta }_2{s}_2+L+{\beta }_{\rho }{s}_{\rho }-R_{m,n}^{q+1})}^2\right]$

$={\beta }_0^2+\underset{i=1}{\overset{\rho }{\Sigma }}\underset{j=1}{\overset{\rho }{\Sigma }}{\beta }_i{\beta }_{j}E\left[s_i{s}_j\right]+E\left[{\left(R_{m,n}^{q+1}\right)}^2\right]$

$+2{\beta }_0\underset{i=1}{\overset{\rho }{\Sigma }}{\beta }_{i}E\left[s_i\right]-2{\beta }_{0}E\left[R_{m,n}^{q+1}\right]$

$-2\underset{i=1}{\overset{\rho }{\Sigma }}{\beta }_{i}E\left[s_i{R}_{m,n}^{q+1}\right]$

第二步：求上述差值的均方差相对于系数β0，β1，L，βρ的偏导数。

$\left(\begin{array}{c}\frac{\partial \Delta ({\beta }_0,{\beta }_1,L,{\beta }_{\rho })}{\partial {\beta }_0}=2{\beta }_0+2\underset{i=1}{\overset{\rho }{\Sigma }}{\beta }_{i}E\left[s_i\right]-2E\left[R_{m,n}^{q+1}\right]\\ \frac{\partial \Delta ({\beta }_0,{\beta }_1,L,{\beta }_{\rho })}{\partial {\beta }_1}=2{\beta }_{0}E\left[s_1\right]+2\underset{i=1}{\overset{\rho }{\Sigma }}{\beta }_{i}E\left[{s_{1}s}_i\right]-2E\left[s_1{R}_{m,n}^{q+1}\right]\\ M\\ \frac{\partial \Delta ({\beta }_0,{\beta }_1,L,{\beta }_{\rho })}{\partial {\beta }_{\rho }}=2{\beta }_{0}E\left[s_{\rho }\right]+2\underset{i=1}{\overset{\rho }{\Sigma }}{\beta }_{\rho }E\left[s_{\rho }{s}_i\right]-2E\left[s_{\rho }{R}_{m,n}^{q+1}\right]\end{array}\right)$

第三步：令可以求解各个系数的值。如下：

$\left(\begin{array}{c}{\beta }_0\\ {\beta }_1\\ M\\ {\beta }_{\rho }\end{array}\right)={\left(\begin{array}{ccccc}1& E\left[s_1\right]& E\left[s_2\right]& L& E\left[s_{\rho }\right]\\ E\left[s_1\right]& E\left[s_1{s}_1\right]& E\left[s_1{s}_2\right]& L& E\left[s_1{s}_{\rho }\right]\\ M& M& M& M& M\\ E\left[s_{\rho }\right]& E\left[s_{\rho }{s}_1\right]& E\left[s_{\rho }{s}_2\right]& L& E\left[s_{\rho }{s}_{\rho }\right]\end{array}\right)}^{-1}\left(\begin{array}{c}E\left[R_{m,n}^{q+1}\right]\\ E\left[s_1{R}_{m,n}^{q+1}\right]\\ M\\ E\left[s_{\rho }{R}_{m,n}^{q+1}\right]\end{array}\right)$

其中除了系数β₀，β₁，L，β_ρ以外的其他值可以通过在一定信噪比下对一定的样本求统计平均得到，然后就可以解方程组求得各个系数。同时从式(2)我们可以看到，在中可以通过自左至右地选取S中的任意大于等于1小于ρ个元素来得到的近似值。当然，从S中选取越多个元素来进行线性化近似，得到的结果越接近但是算法复杂度也越高，这就需要根据实际的应用来决定，在本发明中将选取前两个元素。

本发明的第二个目地是基于上述分层译码算法提出一种部分并行译码器结构，应用于多媒体无线传感网中。如图1所示，本发明提出的译码器包括控制模块，输入输出缓存，存储器模块，分层信息处理模块，奇偶校验模块和互连BENES网络等等。

本发明与现有技术相比具有下述方面的改进。

(1)本发明中分层信息处理模块采用逐级细化流水线的设计方法来实现，有效的降低了译码器的关键路径延迟，可以提高译码器电路的工作频率和吞吐量。同时通过分析译码器结构中的潜在可复用性来降低硬件资源的消耗，提高硬件利用率。

(2)众多文献表明，对于LDPC译码器，超过一半的功耗都是由读写存储器引起的，本发明采用内存旁路(memory bypassing，MB)技术来减少译码过程中对存储器的读写次数来降低功耗。可以看出，采用该技术后，读写存储器的次数可以达到50％的降幅。

4.附图说明

图1为本发明部分并行译码器结构示意图。

图2为本发明分层信息处理模块示意图。

图3a为本发明3∶2比较器示意图；图3b为本发明4∶2比较器示意图；

图3c为本发明10∶2比较器示意图。

图4为本发明BENES网络结构示意图。

图5为校验矩阵具有3行7列的一LDPC码实例的示意图。

图6为本发明内存旁路技术示意图。

5.具体实施方式

下面结合附图与具体实施方式对本发明作进一步说明：

本发明提出的支持多种码长码率的译码器针对的是IEEE 802.16e标准中提出的QC-LDPC码，共包括1/2，2/3，3/4和5/6四种码率。其校验矩阵每行包括24个子矩阵，每列的子矩阵数目由码率决定(例如码率为2/3时，每列包括8个子矩阵)。同时子矩阵的大小(也称扩展因子)一共19种，包括从24到96步长间隔为4。因此该码包括从576到2304共19种码长。如图1所示，译码器结构包括控制模块，输入输出缓存，96组7位减法器，96组分层信息处理模块，96组7位加法器，2个存储器模块(第一存储器和第二存储器)，1个奇偶校验模块，以及用来传递消息的BENES网络。

本处选择减法器、处理模块和加法器的数量选择，是考虑到本专利具体实施所面向的QC-LDPC码是在IEEE 802.16e标准中定义使用的；其单位子矩阵的最大为96(已在背景说明中加入了相关说明)；因此此处选择减法器、处理模块和加法器的数量选择都为96组，并且下述BENES网络的输入输出数目也为96。如果针对不同的QC-LDPC码，需要选择不同数量。

控制模块，用来控制整个译码器的工作过程，各个模块的工作状态及时序，包括信道信息的输入控制，迭代是否继续的控制，信息处理模块的使能控制，以及译码器结果的输出控制等等。同时，要实现多种码率码长的译码需求，BENES网络的参数也需通过控制模块设置。

输入缓存用来存储信道传来的对数似然比信息。

输出缓存用来存储译码器的输出判决比特，并完成译码数据打包。

R信息存储器(记为存储器1)用来保存分层信息处理模块产生的校验节点信息。判决信息存储器(记为存储器2)用来保存每次迭代译码产生的节点判决信息

分层信息处理模块完成式(4)中的运算，将和当前校验节点相连的变量节点信息，根据所述译码算法进行处理，处理完的信息将存入存储器1中。如图2所示，处理模块包括10个输入和10个输出，每个输出由其相应的输入之外的9个输入值中的最小值经过R＝β₀+β₁L_min得到。其中10∶2比较器用来求取10个数值中的最小值和第二小值，由4个3∶2比较器和2个4∶2比较器组成，如图3所示。

奇偶校验单元用来判断迭代译码过程是否终止。本发明通过判断相邻两次迭代产生的变量节点n的判决信息的符号位是否相同来进行判决。如果所有判决信息的符号位都相同，则译码终止，否则继续。

改进型Benes互连开关网络用来在分层信息处理单元和存储器之间传递信息。该网络由三个参数决定：P，C和P_M。其中参数P代表QC-LDPC码子矩阵扩展因子的大小。参数C代表子矩阵的循环移位数。参数P_M代表当前网络允许的最大输入数目，初始值设为96。如图4所示，该网络可以通过配置网络中的2×2开关(到BAR状态或者CROSS状态)来实现输入输出间的任意循环移位变换，从而可以实现译码器支持多种码率码长LDPC码译码的功能。与传统BENES网络相比，改进网络优化了网络中使用的开关，可以减少网络面积带来的硬件开销。此外，本发明还提出一种并行算法来产生控制信号，可以减少整个网络传递消息的延时。如下所示，函数Floor(x)为向下取整函数。函数Ceil(A)为向上取整函数。

BENES网络控制信号生成算法：

Algorithm I：{

对于指定的(p，c，P_M)，

如果P_M＝3调用Algorithm B

否则调用Algorithm A

返回}

Algorithm A：{

步骤A0：检测参数p和c的最低位，计算Ceil(p/2)和Ceil((p-c)/2).

将Benes网络中的所有2×2开关都默认设置为BAR状态。

步骤A1：将当前网络的第一级和最后一级的2×2开关按如下设置：

如果p为偶数并且c为偶数，

调用Algorithm I(p/2，c/2，P_M/2)和

Algorithm I(p/2，c/2，P_M/2)。

如果p为偶数并且c为奇数，

将当前网络第一级的前Ceil(p/2)个开关设置为CROSS状态。

调用Algorithm I(p/2，Ceil(c/2)，P_M/2)和

Algorithm I(p/2，Floor(c/2)，P_M/2)。

如果p为奇数并且c为偶数，

将当前网络第一级的第Ceil((p-c)/2)个开关和第Ceil(p/2)个开关之间的所有开关，(包括这两个开关在内)设置为CROSS状态。

将最后一级的第Ceil(p/2)个开关设置为CROSS状态。

调用Algorithm I(Floor(p/2)，c/2，P_M/2)和

Algorithm I(Ceil(p/2)，c/2，P_M/2)。

如果p为奇数并且c为奇数，

将当前网络第一级的前Ceil((p-c)/2)-1个开关设置为CROSS状态。

调用Algorithm I(Ceil(p/2)，Ceil(c/2)，P_M/2)和

Algorithm I(Floor(p/2)，Floor(c/2)，P_M/2)。

步骤A2：返回}

Algorithm B：{

步骤B0：将3×3开关按如下规则设置：

如果(2，1，3)，将开关1设置为CROSS状态。.

如果(3，1，3)，将开关2和3设置为CROSS状态。

如果(3，2，3)，将开关1和3设置为CROSS状态。

否则将所有开关设置为BAR状态。

步骤B1：返回}

该译码器的译码过程，共包含有5步骤：

(1)初始化：将输入缓存中的信道对数似然比信息读入存储器2的相应位置。存储器1值均初始设为零。同时根据LDPC码的校验矩阵来配置BENES网络。

(2)减法器运算：存储器2中各节点判决信息通过BENES网络传递到减法器输入端，从存储器1中读取相应的校验节点信息，两者相减可以得到变量节点信息。

(3)分层信息处理：对和该校验节点相连的各变量节点信息(步骤(2)的结果)进行如式(4)运算，得到校验节点信息，写入存储器1相应位置。

(4)加法器运算：将校验节点信息(步骤(3)的结果)和相应变量节点信息相加，得到节点判决信息，并通过BENES网络写入存储器2。

(5)奇偶校验：每次迭代译码的结果通过奇偶校验单元来判断是否满足校验方程。如果满足，则译码过程结束，否则，如果未达到最大迭代次数，则迭代过程继续。

为了提高译码器电路的工作频率和吞吐率，如图2所示，分层信息处理模块采取流水线的工作方式。其划分为四级流水线处理，第一级用来获取输入的绝对值，第二级计算出其中最小的两个绝对值，第三级通过比较选择获取除了和本次输出相应的输入之外的最小绝对值，第四级通过添加符号和输出运输得到校验节点处理单元的输出值。通过采用流水线工作方式，译码器电路的工作频率可以由66.37MHz提高到93.66MHz，吞吐率也由149.92Mbps提高到176.88Mbps。

由于多媒体传感网对功耗的严格要求，本发明提出的译码器具有低功耗的优点。许多文献表明，对于LDPC译码器，大约74％的功耗都是由读写存储器引起的。本发明将采用MB技术来减少对存储器的读写次数，从而降低功耗。在分层译码器结构中，每层信息处理模块从存储器1中读取信息，经过计算后再写入存储器中供下一层使用。如果使用MB技术，当相邻两层在相同列上都有非零元素时，上一层的信息处理模块结果可以无须写入存储器，而直接送给下一层使用。这样就可以省下上一层对存储器的写操作，和下一层对存储器的读操作。下面通过图5所示例子加以说明，其校验矩阵具有三层结构，每层包含七列。图6显示的是没有MB的分层译码过程，三层译码共需对存储器进行12次读操作和12次写操作。采用MB技术后(图中虚线框所示)，读写存储器次数分别降低到6次，可以达到50％的降幅。例如，第二层译码时，对一列和三列相应存储器的读操作可以省略，第三层译码时，对二列和一列相应存储器的读操作可以省略。

在不背离本发明精神及其实质的情况下，熟悉本领域的技术人员当可根据本发明作出各种相应的改变和变形，但这些相应的改变和变形都应属于本发明所附的权利要求的保护范围。