收稿日期 :2010‐01‐22
基金项目 :中央高校基本科研业务费专项基金资助项目 (JY10000901017) ;973 资助项目(2010CB328300) ;111 基地资助项目 (B08038)
作者简介 :杨 洋 (1981‐) ,男 ,西安电子科技大学博士研究生 ,E‐mail :
yy
ang@ mail .xidian .edu .cn .
doi :10 .3969/ j .issn .1001‐2400 .2010 .05 .004
L D PC 码 串 行 译 码策 略的 收 敛 速 度 分 析
杨 洋 , 陈 超 , 白 宝 明 , 王 新 梅
(西安电子科技大学 综合业务网理论及关键技术国家重点实验室 ,陕西 西安 710071)
摘要 :基于校验节点分组的 LDPC 码串行译码策略具有很高的收敛速度 ,但当分组数过多 ,并行度过低
时译码时延很大 .针对此问题 ,利用外信息转移(EXIT )图技术找到收敛速度和译码时延的平衡点 .首先
推导不同分组数下串行译码策略的 EXIT 函数 ,然后通过比较函数对应的 EXIT 曲线估计出在不牺牲收
敛速度的前提下该策略能达到的最大并行度 .仿真结果验证了 EXIT 图分析的正确性 .
关键词 : LDPC 码 ;迭代译码 ;串行译码策略 ;收敛速度 ;外信息转移图
中图分类号 :T N911 .22 文献标识码 :A 文章编号 :1001‐2400(2010)05‐0795‐06
Analysis of the convergence rate of serial schedule
based decoding for LDPC codes
Y A NG Y an
g
, C H E N Chao , BA I B ao
‐
min
g
, W A NG X in
‐
mei
(
State Key Lab . of Integrated Service Networks , Xidian Univ . , Xi摧an 710071 , China)
Abstract : Serial schedule based decoding for LDPC codes , in w hich check nodes are partitioned into
g
roups , converges very fast . How ever , if there are too many groups , the low degree of parallelism will
incur high decoding latency . T he extrinsic information transfer ( EXIT ) chart technique is adopted to find
out a balance between convergence rate and decoding latency . EXIT functions for serial schedule based
decoding with different group partitions are derived , and a comparison among corresponding EXIT curves
is made to estimate the maximum parallelism that serial schedule based decoding may achieve without
sacrificing the convergence rate . Simulation results validate the EXIT chart analysis .
Key Words : LDPC code ; iterative decoding ; serial schedule based decoding ; convergence rate ;
EXIT chart
近年来 ,低密度校验(LDPC)码
[1‐2]
受到编码界和工业界的广泛关注 ,其中一个重要的原因是可以采用
实用的和积算法(SPA )进行译码 .利用 SPA 译码 ,LDPC 码可以达到接近香农限的性能 ,且译码复杂度仅随
码长线性增加 .根据并行度的不同 ,SPA 可以用不同的消息更新策略实现 .由硬件知识可知 ,并行度高的策
略译码时延小 ,但硬件实现复杂度高 ;并行度低的策略硬件实现简单 ,但译码时延大 .最常见的洪水策略
[1]
(Flooding Schedule ,FS )是一种全并行策略 ,拥有最小的译码时延 .但由于每轮迭代需要同时更新所有的检
验节点(变量节点)消息 ,其硬件实现时内部连线复杂 ,且存储和运算单元需求量非常大
[3]
.Mansour 等在文
献[4]中提出了一种串行策略 ,将校验节点分成若干组 ,每轮迭代依次更新各个组的检验节点消息 .这种组内
并行 ,组间串行的策略被形象地称为洗牌策略(Shuffled Schedule ,SS ) .与 FS 相比 ,SS 降低了处理并行度 ,
故硬件实现复杂度大大降低 .通过仿真 ,人们发现在相同的信噪比下 ,全串行 SS (即分组数等于校验节点数 ,
每组仅含一个校验节点 ,此时收敛最快)仅需要 FS 约一半的迭代轮数即可收敛
[4]
.Sharon 等在文献[5]中利
用计算树方法证明了全串行 SS 传播消息的速度比 FS 高一倍 ,从而在理论上肯定了 SS 的快速收敛特性 .然
而 ,虽然 SS 有收敛速度上的优势 ,但当分组数较多 ,并行度很低时其译码时延远大于 FS .
笔者利用外信息转移(EXIT )图技术
[6]
研究 SS 在不同分组数下的收敛速度 .首先 ,推导出不同分组数下
2010 年 10 月
第 37 卷 第 5 期
西安电子科技大学学报(自然科学版 )
JOURNAL OF XIDIAN UNIV ERSITY
Oct .2010
Vol .37 N o .5