用于CMMB 的低运算复杂度LDPC 解码算法


用于 CMMB 的低运算复杂度 LDPC 解码算法 姜小波, 聂正华 ( 华南理工大学电子与信息学院, 广东广州 510641) 摘 要: 本文提出了两种基于变量节点可靠度的 LDPC 解码算法. 第一, 针对传统的可靠度判决算法会产生比 较严重的误判现象, 导致译码性能降低. 本文提出了一种改进的可靠度判决算法, 它降低了变量节点的误判概率. 在 AWGN 和瑞利信道仿真中, 性能都有显著的提高, 性能超过了标准 BP 算法. 第二, 提出了分层可靠度算法. 和标准 BP 算法相比较, 性能提高了 01dB, 收敛速度提高了一倍, 计算复杂度降低大约 65% . 关键词: LDPC; CMMB; 分层译码; 瑞利衰落信道 中图分类号: TN91122 文献标识码: A 文章编号: 03722112 ( 2010) 07161204 Low Computational Complexity Algorithms of LDPC Decoder for CMMB JIANG Xiaobo,NIE Zhenghua ( School of Electronic and Information Engineering, South China University of Technology, Guangzhou, Guangdong 510641, China) Abstract: In the paper, two LDPC decoding algorithms based on reliability are proposed. First, the conventional early detec tion method is poor performance due to misjudgment. A new early detection method is proposed, which reduces the probability of misjudgment and lead to performance improvement. At AWGN and Rayleigh fading channel simulation, the performance of the new algorithm exceed standard BP algorithm. Second, the layered reliability decoding algorithm is proposed. Compared w ith standard BP algorithm, the performance is increased by 01dB, velocity of the convergence is tw ice faster and computational complexity is de creased by 65% . Key words: low density parity check ( LDPC) ; China mobile multimedia broadcasting ( CMMB) ; layered decoding; rayleigh fading channel 1 引言 中国移动多媒体广播 CMMB( China Mobile Multime dia Broadcasting) 传输系统采用 LDPC( Low Density Parity Check) 码技术作为信道编解码方案. 并指定采用码长为 9216, 码率为 1/ 2 和 3/ 4 的高度结构化的 LDPC 码作为 编解码标准. 不像Turbo 码, LDPC 码可以很容易的实现 并行解码, 只需要执行一些简单的运算操作像加法、比 较、查找表[ 1] . 而且可以很容易地通过调整解码并行度 来对解码吞吐率和解码复杂度进行折中. 然而 CMMB 的 LDPC 的解码需要比较多的迭代次数去接近香农限, 也 就产生比较多的运算操作, 比较大的功耗[ 2] 和比较长的 延时. 所以进一步降低运算复杂度是十分必要的. 在文 献[ 3, 4] 中, 通过分析变量节点的伪后验概率和非法校 验方程数目, 提前终止可靠度高的变量节点参与后续迭 代更新来降低运算复杂度. 但是如果有变量节点被错误 地终止, 后续的译码过程将无法修正它们, 导致译码性 能较差. 本文提出了一种改进的可靠度判决算法来减少 变量节点被误判的概率, 同时还可以保证高的可靠度变 量节点所输出的信息更为可靠, 有助于邻近的其它节点 更新, 改进的算法性能超过了标准 BP 算法. 在文献[ 5~ 7] 中介绍了一种分层译码法, 理论和仿 真表明: 分层算法的收敛的速度比标准 BP 算法快一 倍, 但分层算法在每次迭代过程中的运算量并没有降 低. 本文采用改进的可靠度判决算法对分层算法进行改 进, 提出了分层可靠度算法来减少运算复杂度. 2 改进的可靠度判决算法 在文献[ 3, 4] 中给出了可靠度判决算法, 采用变量 节点的可靠度结合非法校验方程数来判决变量节点的 可靠度. 通过提前终止部分高可靠度变量节点参与后续 迭代来降低计算复杂度. 在校验矩阵 H 中, 每一行代表 一个校验方程, 正确的码字必须满足所有的校验方程. 记 ri ( i= 0, 1, 2, , M) 为第 i 个校验方程的结果, 满足 则为 0, 否则为 1. 在迭代译码过程中, 第 j 个变量节点 所参与的非法校验方程数Sj 可以这样表示: 收稿日期: 20090527; 修回日期: 20091224 基金项目: 国家自然科学基金( No. 60976031) 第 7期 2010 年 7月 电 子 学 报 ACTA ELECTRONICA SINICA Vol.38 No. 7 Jul. 2010 sj = i ! M (j ) ri 如果 Sj = 0 且| q0 j - q1 j | > TH, 则认为节点 j 为高可 靠度变量节点, TH 为一个预先设定的阈值, 称这一算 法为 Reliability Criteria Belief Propagation( RCBP) . 这个算 法比较容易产生误判的现象[ 4] . 一旦有变量节点被误 判, 则这个码字在后续的迭代中再也不可能被正确解 码了, 导致译码性能的下降. 本部分提出一种改进的可靠度判决算法: 在每次 迭代过程中, 对前面已经判决为高可靠度变量节点再 次判决它们可靠度来减少误判的概率. 判决为高可靠 度的变量节点停止参与校验节点的更新, 但判决为高 可靠度变量节点每次都进行变量节点更新. 可能存在 这样的变量节点, 在某次迭代中被错误地判决为高可 靠度变量节点, 但在后续的迭代中通过接受来自邻近 节点的校验信息而得到更正, 使得误判的变量节点可 以被更正. 把这一算法记为 Improved RCBP( IRCBP) 算 法. 仿真结果表明 IRCBP 算法可以较大地提高译码性 能. 因为: 第一, 误判概率降低了. 第二, 可以保证高可 靠度的变量节点所输出的信息更为可靠, 有助于加快 邻近的其它节点更新. 接下来在理论上证明它的合理 性. 以规则( dv, dc )LDPC 码为例, 来分析两种算法的误 判概率大小. 在文献[ 8] 中有对 RCBP 算法的误判概率 的推导. 定义一下事件: 记事件 Ej 为: 根据伪后验概率 对变量节点 j 的判决结果是错误的. 记事件 Tj 为: 第 j 个变量节点的伪后验概率满足| q0 j - q1 j | > TH . 记事件 Aj 为: 变量节点 j 所参与的校验方程都满足. 记事件 Bj 为: 变量节点 j 后验概率译码错误但被判为高可靠度节 点而停止更新. 在每次迭代后, 对于任意变量节点 j , 事 件 Ej 发生的概率为P ( Ej ) = Pe, 事件 Tj 发生的概率为 P( Tj ) = Pth. 对某一变量节点 j , 事件 Bj 发生的概率为: p ( Bj ) = P( EjTjAj ) ( 1) 而 Tj 与其他两个事件是独立的, 因此式( 1) 可以写为: p ( Bj ) = P( Tj ) P( Ej ) P (Aj / Ej ) ( 2) 在事件 Ej 发生的情况下, 对于 j 参与的每一个校 验方程, 只要另外再有奇数个变量硬判决错误, 则校验 方程同样满足. 因此对于可靠性准则 RCBP, 事件 Bj 发 生的概率为: P( Bj )= PthPe[ ( dc- 1)/ 2 j = 1 C2j- 1 d c- 1P2j- 1 e ( 1- Pe) dc- 2j ] dv ( 3) 对于 IRCBP 算法, 记事件 Dj 为: 误判为高可靠度的 变量节点 j 被修正, 记事件 bj 为: 变量节点 j 后验概率 译码错误但被判为高可靠度节点. 对于事件 Dj 发生的 概率为P( Dj ) = Pd . 事件 bj 发生的概率为: P( bj ) = P( Bj ) - P ( Dj / Bj ) < P ( Bj ) ( 4) 采用对数域的具体译码步骤如下: 令 ui , j = ln( r 0 ij / r1 ij ), vi, j= ln( q0 ij / q1 ij) , vj= ln( q0 j / qi j ) ( 1) 初始化 vi, j = 2yj/ 2, stop [ j ] = 0( j = 0, 1, 2, , N- 1) ( 2) 校验节点更新 ui , j ( t+ 1) = 2tanh- 1[ ∀k ! N( i) \ j 且stop[ k]= 0 tanh( vi, k ( t) / 2) ] ( 3) 变量节点更新 vi, j ( t+ 1) = uj ( 0) + k ! M ( j) \ i uk, j ( t+ 1) ( 4) 后验概率计算 vj= uj( 0) + k! M( j ) uk , j ( t+ 1) ( 5) 非法校验方程数计算 sj = i! M( j ) ri ( 6) stop [ j ] = 0 ( j = 0, 1, 2, , N- 1) ( 7) 如果 Sj = 0 且| vj | > Tb, 则 stop [ j ] = 1. ( 8) 迭代终止判断 若 vj> 0, 则 xj = 0, 否则 xj = 1. 若 HT x= 0 或者迭 代次数达到最大迭代次数, 则结束本次译码. x 作为译 码输出, 否则转到步骤( 2) 继续迭代. 定义运算量为: 迭代次数乘以平均参与迭代的变量 节点个数. 由图 1 可知, IRCBP 和 RCBP 算法平均参与迭 代的变量节点个数几乎相等, 也即运算量几乎相等, 但 都比标准 BP 算法的运算量低, 而且迭代次数越大运算 1613第 7 期 姜小波: 用于 CMMB 的低运算复杂度LDPC 解码算法 量越低. 由图 2 中的仿真结果可知: IRCBP算法在性能上 优于 RCBP 算法. 在误码率为 10- 4时, 提高大约 008dB. 以上仿真结果基于 AWGN(Additive White Gaussion Noise) 信道, 采用 BPSK 调制, 接受信息 6 位均匀量化, 中间信 息 9 位均匀量化, 并采用 CMMB 标准所定义的规则 LDPC 码( 9216, 4068) , 行重为 6, 列重为 3, 最大迭代次数为 30 次. 本文同时给出了基于瑞利衰落信道[ 9] 的定点[ 10, 11] 仿 真结果, 接受信息采用 6 位均匀量化, 中间信息采用 9 位 均匀量化, 结果如图 3, 在误码率为 10- 4时, IRCBP 算法 比 RCBP 算法在性能上提高大约 055dB. 3 分层可靠度算法 在文献[ 5] 中给出了一种分层译码算法, 和标准 BP 算法区别在于: 在迭代中当更新完 H 矩阵中某一行非 零元素的校验信息后, 马上更新每个非零元素对应列 的所有非零元素的比特信息, 然后再对 H 矩阵的下一 行进行译码. 这样可以提前用到已经更新好了的变量 节点信息, 加快收敛速度. 但是分层算法每次迭代的运 算量跟标准 BP 算法一样大. 基于分层算法每次迭代的运算量还是很大. 本部分 给出了一种改进的算法 # # # 分层可靠度算法, 是通过采 用本文第二部分所提出的 IRCBP 算法对分层算法进行 改进. 通过分析分层算法的变量节点的伪后验概率和非 法校验方程数目, 提前终止可靠度高的变量节点参与后 续迭代更新, 来降低运算复杂度. 这个算法同时具有 IR CBP算法运算量低和分层算法收敛速度快的优势. 采用对数域的具体译码步骤如下: (1) 初始化 vi , j = 2yj / 2, stop[ j ] = 0 ( j = 0, 1, 2, , N- 1) (2) 校验节点和变量节点更新, 按下面程序更新 For i= 0, 1, , M- 1 For j ! N( i) ui, j ( t+ 1) = 2tanh- 1[ ∀k! N ( i) \ j 且stop[ k] = 0 tanh( vi , k ( t) / 2) ] End For j ! N( i) vj = vj - ui, j ( t) + ui, j ( t+ 1) End End (3) 计算非法校验数 sj = i ! M( j ) ri (4) stop [ j] = 0 ( j = 0, 1, 2, , N - 1) (5) 如果 Sj = 0 且| vj | > Tb , 则 stop [j ] = 1. (6) 迭代终止判断 若 vj > 0, xj = 0, 否则 xj= 1. 若 HT x= 0 或者迭代次 数达到最大迭代次数, 则结束本次译码. x 作为译码输 出, 否则转到步骤( 2) 继续迭代. 由图 4 可知: 当信噪比为 16dB, 迭代次数为 20 时, 分层可靠度算法每次迭代的平均运算量比标准 BP 算 法降低大约 65% . 由图 5 可知: 分层可靠度算法比标准 BP 算法在性能上得到了很大的提高. 当误码率为 10- 4 时, 性能提高大约 01dB. 由图 7 可知: 分层可靠度算法 比标准 BP 算法在迭代次数上降低大约一倍. 以上仿真 结果基于 AWGN 信道, 采用 BPSK 调制, 接受信息 6 位 均匀量化, 中间信息 9 位均匀量化, 并采用 CMMB 标准 1614 电 子 学 报 2010 年 所定义的规则 LDPC 码( 9216, 4068) , 行重为 6, 列重为 3, 最大迭代次数为 30 次. 本文同时给出了基于瑞利衰 落信道的定点仿真结果, 接受信息采用 6 位均匀量化, 中间信息采用 9 位均匀量化, 结果如图 6, 在误码率为 10- 4时, 分层可靠度算法在性能上比标准 BP 算法提高 大约 045dB. 4 总结 传统的可靠度判决算法的性能之所以不太高的原 因是误判的概率比较大. 本文提出的 IRCBP 通过判断 为高可靠度的变量节点在下次迭代中重复进行判断, 以减低码字被误判的概率, 从而大大的提高了译码性 能, 超过了标准 BP 算法. 另外一种算法是通过用 IRCBP 对分层算法进行改进而提出了分层可靠度算法, 这样 大大减少了分层算法的运算量. 和标准 BP 算法比较, 计算复杂度比标 准 BP 降低大 约 65% ; 性能 提高了 01dB; 收敛速度提高了一倍. 而且, 仿真结果表明, 改进 的两种算法在AWGN 和瑞利信道中都有效. 参考文献: [ 1] R G Gallager. Low density parity check code[ J] . IEEE Trans actions on Information Theory, 1962, 8( l) : 21- 28. [ 2] Yang Sun, Joseph R Cavallaro. A low power 1Gbps reconfig urable LDPC decoder design for multiple 4G wireless standards [ A] . Proceedings of IEEE International SOC Conference[ C] . Newport Beach, CA, United states, Sept 2008. 367- 370. [ 3] EunA Choi, DaeIK Chang, DeockGil Oh, JiWon Jung. Low computational complexity algorithms of LDPC decoder for DVBS2 Systems[ A] . Proceedings of the IEEE 62nd Vehicular Technology Conference ( VTC2005Fall) [ C ] . IEEE Press, Sept 2005. 536- 539. [ 4] 郭锐, 刘济林. LDPC 码的一种底复杂度 BP 译码算法[ J] . 浙江大学学报, 2008, 42( 3) : 450- 455. Guo Rui, Liu JiLin. New low complexity belief propagation decoding of low density parity check codes[ J] . Journal of Zhe jiang University, 2008, 42( 3) : 450- 455. ( in Chinese) [ 5] Rovini M, Rossi F, Ciao P, Linsalata N, Fanucci. Layered de coding of nonlayered LDPC codes[ A] . Proceedings of the 9th Euromico Conference on Digital System Design [ C ] . Dubrovnik, Croatia, August 2006. 537- 544. [ 6] Zhang J, Wang Y, Fossorier M, Yedidia J S. Replica shuffled Iterative decoding[ A] . Proceedings of IEEE International Sym posium on Information Theory [ C ] . Adelaide, Australia, September 2005. 454- 458. [ 7] Radosavljecvic P, De Baynast A, Cavallaro J R. Optimized message passing schedules for LDPC decoding[ A] . Prceedings of the ThirtyNinth Asilomar Conference on Signals, Systems and Computers [ C] . Pacific Grove, CA, USA, 2005. 591 - 595. [ 8] 陈昕, 门爱东. 基于可靠性更新的低复杂度 BP 译码[ J] . 电子与信息学报, 2009, 31( 10) : 2421- 2426. Chen Xin, Men Aidong. Low complexity BP decoding algo rithm based on reliability updating schedule[ J] . Journal of Elec tronics & Information Technology, 2009, 31( 10) : 2421- 2426. ( in Chinese) [ 9] 林家儒, 吴伟陵. 非规则 LDPC 码在 RICE 信道中的性能 分析[ J] . 电子学报, 2005, 33( 1) : 43- 46. Lin Jiaru, Wu Weiling. Performance of irregular LDPC codes on rician fading channels[ J] . Acta Electronica Sinica, 2005, 33 ( 1) : 43- 46. ( in Chinese) [ 10] Liu Binbin, Bai Dong, Mei Shunliang. Min sum approximation decoding of LDPC codes with adaptive nonuniform quantiza tion[ J] . Chinese Journal of Electronics, 2008, 17( 3) : 503- 506. [ 11] 孙韶辉, 孙蓉, 王新梅. 低密度校验码 BP 译码算法中量 化问题的研究[ J] . 电子学报, 2003, 33( 2) : 217- 220. Sun Shaohui, Sun Rong, Wang Xinmei. Some quantization issues for decoding of low density parity check codes with BP algorithm[ J] . Acta Electronica Sinica, 2003, 33 ( 2) : 217 - 220. ( in Chinese) 作者简介: 姜小波 男, 2004 年从 中科 院微 电子所 获 得博士学位,1997 年、1994 年分别 从浙江大 学硅 材料国家重点实验室、浙江大学获得硕士和学士 学位. 2004~ 2006年在韩国三星电子从事 移动多 媒体基带芯片设计. 目前在华南理工大学电子信 息学院从事教学科研工作.主要研究方向为差错 控制编码设计、低功耗集 成电路设 计、通信 基带 芯片设计. Email:xbjiang@gmail. com 聂正华 男,1984 年 6 月 出生于 江西 抚州. 2008年进入华 南理 工大 学电 子与 信息 学院. 现 为在读硕士读生, 主要从事于 LDPC 译码算 法及 硬件实现等方向的研究. Email: 351610856@ qq. com 1615第 7 期 姜小波: 用于 CMMB 的低运算复杂度LDPC 解码算法
还剩3页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

zwpgip

贡献于2011-12-05

下载需要 8 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf