低密度奇偶校验码(low density parity check code, LDPC)最早见于1962年Gallager^[1]的博士学位论文, 但是限于当时的仿真条件, LDPC码并没有受到应有的重视。1996年, Mackay等^[2]重新发现LDPC码, 并指出它与Turbo码一样, 具有逼近香农极限的能力。随着对LDPC码研究的深入, 人们发现其优越的译码性能, 并将LDPC码应用于更广泛的场景之中。

信道编码盲识别指接收端在对接收信息编码方式未知的条件下, 实现对接收信息的译码。随着信道编码技术的广泛使用, 信道编码盲识别的应用越来越多。例如在非协作通信领域, 可以为接收信息的译码提供可靠的技术支持; 在协作通信领域, 当训练信息不能准确到达时, 接收端可以对传输信息进行译码; 在智能移动通信和多点广播通信领域, 当发端采用自适应编码时, 接收端可以对信号内容进行识别和利用。

目前, 国内外学者对线性码提出几种盲识别方案。针对线性分组码, Valembois^[3]归纳为联合判决问题, 提出基于校验向量的二元线性分组码的盲识别方法; Mathieu^[4]基于Valembois的思想, 通过生成一系列低码重的码字来实现迭代译码, 实现码长较短且误码率低的线性分组码的盲识别。上述两种方法在LDPC码长未知且码字起点未同步的情况下并不适用。

针对未删除卷积码, 有学者提出基于快速何冲算法^[5]的盲识别方法和基于欧几里得算法的盲识别^[6]。针对删除的卷积码, 有学者提出基于生成多项式的盲识别方法和基于校验矩阵与生成矩阵正交关系的盲识别方法^[7-8]。上述方法在LDPC码字序列的起始位置未知时并不适用, 且计算量巨大。

可见, 已有的研究方法虽然对LDPC码盲识别研究有一定的借鉴意义, 但不能解决在码长未知且起点未知的情况下的逆向识别, 并且计算繁复。

本文利用校验关系和后验概率的对数似然比, 对LDPC码逆向识别技术进行研究, 提出一种基于后验概率对数似然比(log likelihood ratio, LLR)均值判断校验矩阵的方法。我们假设接收到的信号样本在统计学意义上彼此独立, 通过期望值最大算法^[9](expectation-maximization algorithm, EM)对噪声参数进行预测, 并确定合理的LLR均值判断阈值, 实现码字起始位置的准确识别, 并从可选的LDPC码校验矩阵集合中找到发送方编码所使用的LDPC码校验矩阵。

1 基于后验概率LLR的LDPC码逆向识别算法原理

每一种LDPC码有唯一的校验矩阵, 因此, 如果将校验矩阵与接收码字建立关系, 就能够明确地找到编码使用的校验矩阵θ。本文首先计算LLR, 然后计算每个校验矩阵对应的平均LLR, 以此为依据, 选择编码矩阵。

1.1 对数似然比

二元随机变量向量X的对数似然比表示为

$ {l_X}(x) = \ln \frac{{\Pr \{ x = 0\} }}{{\Pr \{ x = 1\} }}, $

即为X取值为0和1概率比值的自然对数。对于给定的另外一个随机变量Y, X关于Y的条件对数似然比可以表示为

$ {l_X}|Y(x|y) = \ln \frac{{\Pr \{ x = 0|y\} }}{{\Pr \{ x = 1|y\} }} $

(1)

根据贝叶斯公式, 可以得到以下关系式:

$ {l_{X|Y}}(x|y) = {l_{Y|X(y|x)}} + {l_X}(x) $

(2)

在以下的公式表达中, 本文对表达方式进行简化, 并且分别用l_X(x), l_X|Y(x|y)和l_Y|X(y|x)代替l(x), l(x|y)和l(y|x), 用符号⊕表示有限域中的二进制加法, 用*表示以下运算法则:

$ \begin{array}{c} l({x_1} \oplus {x_2} \oplus ... \oplus {x_n}) = \mathop *\limits_{j = 1}^n l({x_j})\\ = l({x_1})*l({x_2})*...*l({x_n})\\ = \ln \frac{{1 + \prod\limits_{j = 1}^n {(\tanh (l({x_j})/2))} }}{{1 - \prod\limits_{j = 1}^n {(\tanh (l({x_j})/2))} }} \end{array} $

(3)

1.2 LLR在LDPC码逆向识别中的应用

从编码器集合Θ中选择θ′, 可以确切地知道此编码器对应的校验矩阵${\mathit{\boldsymbol{H}}_{\theta '}} \in Z_2^{(n - k) \times n}$^10], 其中n表示码字码长, k表示信息位个数。由校验关系可知, ${\mathit{\boldsymbol{H}}_{\theta '}}c_v^\theta = {\bf{0}}$当且仅当θ′=θ时成立, 其中$c_v^\theta $表示发送端由校验矩阵H_θ编码得到的第v个LDPC码字, 0是(n-k)×1的零向量^[9]。

用$\mathit{\boldsymbol{l}}_i^{\theta '} = {[{l_{i1}},\;{l_{i2}},\;...,\;{l_{i{N_i}}}]^{\rm{T}}}(0 \le {l_{i1}} < {l_{i2}} < ... < {l_{i{N_i}}} \le n - 1)$表示校验矩阵H_θ'第i行非零元素的位置, N_i表示第i行非零元素的总数。LDPC码字表示为c_v^θ[c_{v, 0}, c_{v, 1}, …, c_{v, n-1}]^T, 因此校验关系可以表示为${c_{v{l_{i1}}}} \oplus {c_{v{l_{i2}}}} \oplus \ldots \oplus {c_{v{l_{i{N_i}}}}} = 0,\;\;\forall 1 < i < n - k,$当且仅当θ′=θ时成立。

对于LDPC码, 本文假设各发送信息的码元是统计学意义上独立同分布的。由于这一性质, 接收到的信号的码元也相互独立。因此有

$ l({c_{v,j}}|{y_v}) = l({y_{v,j}}|{c_{v,j}}),\;\;\;0 \le j \le n - 1, $

其中y_v表示接收端收到的LDPC的码字。

由于LDPC码字中各码元取0和1的概率相同, 因而发送端信息码元的后验概率对数似然比为0。我们计算H_θ'中第i个校验关系对于第v个码字的后验概率的对数似然比率, 公式如下:

$ \begin{array}{l} \gamma _{v,i}^{\theta '} = \mathop {{\rm{ }}*}\limits_{j = 1}^{{N_i}} l({c_{v,{l_{ij}}}}|{y_{v,{l_{ij}}}})\\ \;\;\;\;\; = \ln \frac{{1 + \prod\limits_{j = 1}^{{N_i}} {\tanh } (l({y_{v,{l_{ij}}}}|{c_{v,{l_{ij}}}})/2)}}{{1 - \prod\limits_{j = 1}^{{N_i}} {\tanh } (l({y_{v,{l_{ij}}}}|{c_{v,{l_{ij}}}})/2)}},\;\;1 \le i \le n - k, \end{array} $

(4)

$ l({y_{v,{l_{ij}}}}|{c_{v,{l_{ij}}}}) = \ln \frac{{\exp \left[ { - \frac{{{{({y_{v,{l_{ij}}}} - {A_v})}^2}}}{{2\sigma _v^2}}} \right]}}{{\exp \left[ { - \frac{{{{({y_{v,{l_{ij}}}} + {A_v})}^2}}}{{2\sigma _v^2}}} \right]}} = \frac{{2{A_v}{y_{v,{l_{ij}}}}}}{{\sigma _v^2}} $

(5)

根据对数似然比的定义以及校验关系可知:当θ ′=θ时, 对数似然比率一定为正, 对所有校验位的后验概率的对数似然比求平均, 取值也一定为正; 当θ′≠θ时, 每个校验位的后验概率对数似然比的正负是不确定的, 所以对所有校验位的后验概率LLR进行平均值运算时, 数值之间会相互抵消。

接收到的第v个码字的平均LLR可以表示为

$ \Gamma _v^{\theta '} = \frac{1}{{n - k}}\sum\limits_{i = 1}^{n - k} {\gamma _{v,i}^{\theta '}} $

(6)

不同的校验矩阵有不同的n和k值, 因此n-k(即校验位的个数)的值显然是不同的。对编码矩阵的选择可以表示为

$ {\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\frown$}} \over \theta } _v} = \arg \mathop {\max }\limits_{\theta ' \subset \Theta } \Gamma _v^{\theta '} $

因此, 需要对编码矩阵集合中的所有校验矩阵进行计算。

为了加速逆向识别过程, 本文对前h个校验位计算平均LLR值, 如果此时可以判断出编码矩阵, 则停止对其后的校验关系的计算; 如果无法判断, 则再计算累加h个校验关系的平均LLR值。

通过对校验矩阵集合中每一个校验矩阵的平均LLR值的计算, 选择使得平均LLR值最大的校验矩阵为信息编码矩阵, 实现对LDPC码的闭集逆向识别。

2 基于后验概率LLR的LDPC码逆向识别算法实现

从LLR计算公式可知, 需要知道信道对发送信号的影响(包括幅度增益和噪声功率), 因而首先对接收信号中信道的影响进行估计。在仿真时, 假设码长和码字起点未知, 需要设计逆向搜程序找寻码字起始位置。由于判决时选择LLR均值作为指标, 因而需要选取阈值作为判断标准, 当LLR均值大于阈值时, 认为此时进行判决的校验矩阵即为接收信息对应的正确矩阵。

2.1 EM算法对信道参数预测

EM算法^[10]中定义接收信息y是不完整数据, 完整数据定义为cd=[y^T, a^T]^T, 即获得的接收数据y以及各接收数据的正负符号组成的向量a^[10]。用Q(θ_i^*; θ_i-1)表示完整数据的似然函数的期望, 其中参数向量值θ_i与在接收信息y条件下的完整数据以及θ_i-1相关。

$ Q({\theta _i};\;{\theta _{i - 1}}) = {E_{{\rm{cd}}|y;\;{\theta _{i - 1}}}}[\log {f_{{\rm{cd}}}}({\bf{cd}};\;\;{\theta _i})] $

(7)

在此算法第i次迭代中, 参数θ_i即为使得上述期望公式最大的值:

$ {\theta _i} = \arg \mathop {\max }\limits_{{\theta _i}} Q({\theta _i};\;\;{\theta _{i - 1}}) $

(8)

直到特定条件, EM算法会收敛到似然函数的一个极大值。

期望公式的推导如下:

$ \begin{array}{l} \;\;\;Q({\theta _i},\;\;{\theta _{i - 1}})\\ = \sum\limits_{n = 1}^N {\left\{ {C - \frac{1}{2}\log \sigma _i^2 - \frac{{y_n^2 - 4{p_{n,\;i - 1}}{y_n}{h_i} + 2{y_n}{h_i} + h_i^2}}{{2\sigma _i^2}}} \right\},} \end{array} $

(9)

其中C是常数。定义第n个信息位由在接收到的信息和第(i-1)次迭代参数向量计算出的期望值为

$ {q_{n,\;j - 1}} = \tanh \left( {\frac{{{y_n}{h_{i - 1}}}}{{\sigma _{i - 1}^2}}} \right) $

(10)

带入Q的表达式中, 得到参数表达式:

$ {h_i} = \sqrt {\frac{1}{N}{\mathit{\boldsymbol{y}}^{\rm{T}}}{P_i}\mathit{\boldsymbol{y}}} $

(11)

$ \sigma _i^2 = \frac{1}{N}{\mathit{\boldsymbol{y}}^{\rm{T}}}P_i^ \bot \mathit{\boldsymbol{y}} $

(12)

$ {P_i} = \frac{{{\mathit{\boldsymbol{q}}_i}\mathit{\boldsymbol{q}}_i^{\rm{T}}}}{N} $

(13)

$ P_i^ \bot = I - {P_i} $

(14)

最后得到的预测结果为

$ {{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\frown$}} \over \rho } }_R} = \frac{{{\mathit{\boldsymbol{y}}^{\rm{T}}}}}{{{\mathit{\boldsymbol{y}}^{\rm{T}}}}}\frac{{{P_I}\mathit{\boldsymbol{y}}}}{{P_I^ \bot \mathit{\boldsymbol{y}}}} $

(15)

I是最终迭代次数, 由迭代终止条件决定。

对上述预测结果的偏差进行处理, 其结果的表达式为

$ {{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\frown$}} \over \rho } }_{R - RB}} = \frac{{N - 3}}{N}\frac{{{\mathit{\boldsymbol{y}}^{\rm{T}}}{P_I}\mathit{\boldsymbol{y}}}}{{{\mathit{\boldsymbol{y}}^{\rm{T}}}P_I^ \bot \mathit{\boldsymbol{y}}}} - \frac{1}{N} $

(16)

利用EM迭代方法, 可以获得接收信号的幅度与噪声方差的预测值, 即

$ {A_v} = {h_I},\;\;\omega = {\sigma _I} $

2.2 仿真选码准则

LDPC码具有近香农极限的误码性能、无错误平层、译码速度快等优点, 但其校验矩阵具有随机性, 编码较为复杂。QC-LDPC码是一种基于几何构造的LDPC码, 继承了LDPC码的优点, 同时降低了编译码复杂度, 可实现性强, 被IEEE802.11n (WLAN), IEEE802.16e (WiMAX)和CCSDS等多个通信标准采用, 实际上, 常用的LDPC码多为QC-LDPC码或其变种。本文选用QC-LDPC码进行仿真, 选择的2016码长和1008码长的QC-LDPC码的校验矩阵(均经密度推演算法优化), 具有代表性和常用性。备选校验矩阵中的部分QC-LDPC校验矩阵在加性高斯白噪声信道(AWGN)下的误码性能如图 1所示。

2.3 判断阈值的确定

根据逆向识别原理可知, 当被检测的校验矩阵即为编码所用的校验矩阵时, 利用接收到的LDPC码计算得到的平均LLR值一定为正; 当被检测的校验矩阵不是编码所用的校验矩阵时, 单个校验方程计算的LLR值可正可负, 因此所有校验方程计算的均值LLR也可正可负。为了区分上述两种情况(平均LLR都为正), 本文设定一个判决阈值。当平均LLR大于判决阈值时, 认为当前被检测的校验矩阵即为发送端产生LDPC码所使用的, 反之, 则放弃这个校验矩阵, 对下一个校验矩阵进行检验^[9-10]。

对上述阈值的选择采用仿真来确定。仿真条件是, 在信噪比为-2 dB时, 对2016码长、5/8码率的LDPC码在每一个阈值仿真200次, 统计选择起始位置正确的概率, 结果如表 1所示。

从图 2可以看出, 当阈值在29~35之间时, 起点判断正确率为100%。当阈值设定小于29时, 由于阈值较小, 非对应的校验矩阵的均值LLR也有可能会超过阈值, 造成起点判断错误。当阈值选择过大, 如大于35时, 不仅非对应的校验矩阵的均值LLR无法超过阈值, 对应的校验矩阵也可能小于阈值, 造成无法选择出起点位置, 使得起点选择的准确率降低。

表 2和图 3为在-2 dB信噪比下, 对1/2码率、1008码长LDPC码阈值确定的仿真结果。

对2016码长和1008码长的QC-LDPC, 分别在信噪比为6和-2 dB的起点选择准确率与阈值关系进行仿真, 结果如图 4所示。

从图 4和5的仿真结果可以看出, 对于备选集合中的LDPC码的校验矩阵, 其起点选择准确率与阈值的关系在信噪比[-2, 6]dB范围内的变化基本上相同。实际应用中, 不能因为信噪比的变化以及校验矩阵的不同而改变阈值, 所以阈值与起点选择准确率关系的稳定性很重要。

2.4 逆向盲搜程序设计

接收端对收到的信息进行逆向识别前, 需要设计逆向盲搜程序来确定码字的起始位置。

逆向盲搜程序的设计原则与逆向识别原则相同, 都依赖于每个LDPC独特的校验关系。如果LDPC码与校验矩阵匹配, 则校验码的平均后验概率LLR为正, 本文设定了阈值, 当均值LLR大于此阈值时, 认为LDPC码与校验矩阵匹配。

基于这一原则, 以第一个码元为起点, 取连续n位构成一个待测LDPC, 将其与给定的校验矩阵集中的每一个校验矩阵进行运算, 计算平均LLR值。如果LLR值大于给定的判定阈值, 即认为该LDPC码的第一个码元的位置为码字的起始位置; 否则, 以第二个码元为起点, 重复上述步骤。依此递推, 计算得到接收信号中码字的起点。

为了验证找到的起点的正确性, 仿真时发送端连续发送多个LDPC码字(这样仿真是合理的, 因为在实际通信中需要传输大量的信息, 因而传输的码字一定不只一个)。本文认为, 在一次传输中采用同一个校验矩阵生成LDPC码。在可能的起点后, 连续取5个LDPC码进行逆向识别检验。如果这些码字逆向识别得出的校验矩阵都相同, 则认为起点选择准确; 如果不完全相同, 则认为起点选择错误, 从该起点的下一比特开始重新搜索。闭集逆向识别程序设计如图 6所示。

3 仿真分析

本文对码长为2016 bit的LDPC码进行仿真。备选矩阵集中, 2016码长矩阵有7个(码率为1/4、3/8、1/2、5/8、7/8的矩阵各1个, 码率为3/4的矩阵有两个); 码长为1008的矩阵1个(码率为1/2), 即闭集集合规模为8。加入不同码长的校验矩阵实现未知码长条件下的闭集识别, 在逆向识别中将阈值定为33。

仿真结果如表 3~5所示, 其中SNR为信噪比, Ber为误比特率, Suc_r为逆向识别准确率。

从表 3~5可以看出, 当阈值为33时, 发送方无论选取何种码率的LDPC码进行编码, 无论新信道质量好坏, 接收方均可以100%准确地判断发送方所使用的LDPC码校验矩阵, 因此, 逆向识别准确率可以达到100%。

4 结论

本文对LDPC码逆向识别技术进行研究, 利用后验概率LLR的均值对接收到的LDPC码字的校验矩阵进行逆向识别。通过对接收信噪比进行估计, 实现对接收码字的信道增益以及信道噪声方差值的估计, 得到计算后验概率LLR所需要的信道增益和噪声功率的估计值。通过盲搜程序, 实现对码字起始位置的查找。依据后验概率LLR均值最大化原则, 成功实现对LDPC码字的逆向识别。本文对在不同阈值下校验矩阵和码字起点确定的准确率进行仿真, 确定最优阈值, 提高了盲识别判决准确率。仿真结果表明, 在最优阈值下, 接收方可以利用本文提出的LDPC码逆向识别技术, 准确无误地实现LDPC码校验矩阵的闭集逆向识别。