低密度奇偶校验码及其译码算法实现
维普资讯 http://www.cqvip.com
第l卷 8
第2 期
苏州市 职业 大学学报
J u n lo u h u Vo ain lUnv ri o r a fS zo c t a iest o y
20 07年 5月
V0.8 No2 11 . Ma .2 0 y 07
低密度奇偶校验码及其译码算法实现
张 培
( 州市 职业 大学 电子信息工程系 , 苏 江苏 苏州 2 5 0 ) 1 14 摘 要 :根 据 L P D C码的构造 、 编码 、 译码原理 , 重点论述 了在 Ma Wok 公 司推 出的 M t b上的 L P t rs h al a D C编译码 器
的算法 实现 , 并给 出其 与 T ro 的简单性能对比 , 出 L P 码 的发展 前景。 ub 码 指 DC 关键词 :L P D C码 ;编码 ;译码 ;Ma a ;算 法 tb l 中图分 类号 : T 9 95 文献标识码 : A 文章编号 l 0 8 5 7 ( 0 7 0 _ 0 3 o P2 . 10 — 4 5 20 )2 0 7 一 3
0 引言
阵可以采用最大长度线性 同余序列( aia Lnt M x l eg m — h
Lna C nr n a Sqec) i r og et eune产生。 e u i l 如上所述一个(√ 训拘正则 L P 凡, D C码 由它的校
低 密 度 奇 偶 校 验 码 (D C o — esy L P :Lw D ni t
PryC ek C ds) G lgr最早 于 16 年 提 ai— hc oe 是 a ae t l 92
出的一种具有稀疏校验 矩阵 的分组 纠错码 ,亦称 G le l g aa r码。 之后 , T ro码研究巨大成功的带动 在 ub 下 ,Maky等人 重新 研 究 了 L P 码 , 现 它是 一 ca DC 发 种逼近香农限的新一代高性能纠错码。 LP D C码的特点是易实现, 并且系统复杂度低, 应用于采用正交频分复用技术的无线局域 网及高速
验矩阵 H来定义 , 中j kk n 其 < ,< 。校验矩阵有 凡 , 列
即码长 = , 凡 每列包含 1 的个数为列重 J每行包含 1 ,
的个数为行重 k 行数 =凡 ) k 码率为 k 。 。 ( /, / 其它元 n
素均为 0 。各行的行重相等, 各列的列重也相等。行 重或者列重不一致就称为非正则 L P D C码。 例如 , 一个( , ,) H矩阵可以表示如下: 1 36的 2
1 1 1 0 1 1 0 0 1 0 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 1 H= 1 1 0 0 1 0 0
0 0 1 1 1 0 0 1 1 1 0 1 1 0 1 0 0
光纤通信方面并取得 了良好 的性能 。相比传统 的纠 错码具有 良好的应用前景 , 几乎适用于所有信道 , 因 此成为近年来编码界研究 的热点 ,迭代信号处理技 术也渗透到通信链路的各个环节 中。
伪器H 嗍码 S制 发 ’ P 列 I 一卜B调 生l l K
A N信道 WG
,
0 0 1 1 1 0 0 1 0 0 1 1
2 译 码
信道编码 的译码算法是决定编码性能和应用前 景的一个重要 因素。 尤其是在长码的条件下, 译码算 法的复杂度决定了编码的前途。通常分组码 的译码
复杂度与码长成指数关系 ,导致码长增大到一定程 度后无法实际应用 。而 L P 码 的译码复杂度与码 DC 长成线性关系 ,克服 了上述分组码在长码长时所面
B统 P码卜 B 解 E 计H L 解 P 码 R D c S K
图 1L P D C编 码 、 制和 解码 框 图 调
1 构 造及编 码
L P 码是一种可以用非常稀疏的校验矩阵来定 DC 义的线性分组纠错码, 它是一种基于正则的稀疏二分 图的编码, 因此也称为正则低密度码。L P D C的编码主
临的巨大译码计算复杂度问题 ,使得长编码分组的
应 用 成 为可 能 。
LP D C码的译码相对 编码来说要 简单 。译码算 法 有多种 ,主要是基于 T ne 图的消息传递算法 anr
要是寻找一种合适的方法产生稀疏校验矩阵 H 该矩 ,
收稿 日期 :2 0 — 2 1 06 1 — 2
作者简介 :张培(9 9 )女 , 苏徐 州人 , 17 一 , 江 助教 , 硕士研 究生 , 究方向 : 研 通信与信 息 系统。
一
7 — 3
维普资讯 http://www.cqvip.com
苏州市职业 大学学 报
第 l 卷 8
M ( es ePsi )其 中最为常用的是和积译码 P M s g as g , a n 算法( u — r ut l rh 。为 了在译码性能和 S m Po c Ag i m) d ot
节点 的其它元素 , 其中 L( = t a 0 c 2Y / i ) 2 ( )软判决 3
L ()=L c + XLq ) E Qi ( ) rd, c ( )硬判决 4 如果 L ( <0c 1 Qi ) ,= / 如果 L () 0 C Q I ,=0 > / () 5 中止条件
复杂度之间达到更好的平衡 ,又出现了简化的和积 译码算法 : 最小和算法 ( n S m A g i m) Mi u l rh 。和积 ot 译码算法是一种迭代概率译码算法 ,
每一轮迭代都 需要对码字中各个比特关于接收码字和信道参数的 后验概率进行估算, 因此准确地说和积译码算法是
种逐 比特最大后验概率(A 簿 法。 M P 本文采用 的是 Lg o 域的 M 算法 , P 是一种基于对 数似然比测度的和积译码算法, 该算法的关键是迭代 运算部分的迭代计算后验概率( P ) A P 步骤。 对数似然 比测度下的和积译码算法的复杂度为码长的线性函 数, 由于引入了对数似然 比, 乘法运算转化 为加法运 算 ,降低 了每轮迭代的计算复杂度和硬件实现难度 , 在硬件中的并行实现能够极大地提高译码速度, 因此 对数似然比和积译码算法得到广泛认可。 该算法适合
一
伴随式 c 0 H 或到达最大迭代次数。
3 MA L T AB实现
M TA A L B是 18 94年 由美 国 M tWo s 司推 a h r 公 k 出 的荣 誉 产 品 。早 在 二 十 世 纪 八 十 年 代 中期 M TA A L B就曾在我国出现 , 但真正大规模流行是九 十年代 中期 以后 的事 。现在 , A L B已被从事科 M TA
学研究 、工程计算的广大科技工作者确认为必须掌 握的计算工具 , 是可信赖的科技资源之一。 因此本文
采用该软件实现 L P D C编解码。 限于篇幅 , 仅以部分
用 M TA A L B实现 , 解码性能较好 , 复杂度适 中。
解码算法为例。 LP D C码 的译码 时除 了 中( 函数 的计算 外, x ) 主 要是加法 ( 2 ) 模 加 运算 , 以下是校验点更新部分 的
代码 :
frj 1 o = : M
具体的译码算法可 以分为如下两个步骤 : 第一, 初始化。 对于高斯噪声信道 , 初始化比特点
L / Q= 仃
其 中 L 表示 比特更 新值 ,/ Q Y表示接受 到的信
息 比特 , 表示噪声方差 。
b = n ( (: = ) i f dHj) 0; ti ,一 o = : nt bt fril e g (i l h ) tm bt n (i = ii) e = if dbt bt); ( i  ̄ ()
第二 , 迭代运算。 定义 L :o P( F0/ ) , P c / ) () l c= g( C ) ( F 1 )
=
a apo(g(qje ); l = rds nL (tm) f i , )
%
.
(1 ‘ / )p
bt= t hpo(n(b(qje )2); ea2 a n (rdt has (tm.)) a a L , / )
其 中p (F )= 1e F pc 1 (+
时发送是 1的概率 。 ( )校验点更新 1
) 表示接受为
b t= l ( n ( m(l ( n ( s qj e ) ea -o t hs -o t ha ( (tm) ga u ga b L , .
/)/) =) ) ! 2; ) L(b ()a a bt; r,ii=l e j t) f a
ed n ed n
定义 Lq, r i )=l () () o g( O I)为校验 的
更新值 , 传递给 比特 b 。 记函数 )一ot h l =z ( )e ) = l a / g n 2 e / 1) ) 1 (
令 a s nL ( )  ̄ i (q i )是( qi)的符号 .g = j L( ) j
( : 校验点的数 目) 注 M: 以下是比特点更新部分的代码 :
o i : f r =lN
 ̄. b(q i) oasL ( )是(qi )的绝对值 = i L( ) j L( ) ( 刍 [ ri n j= - ) ∑ 合, i 】 E \) ), 0 i
c e k n ( (i = ) h c - dH :) o;  ̄ ,一
表示与第 个 cek hc 节点相连 的比特节点 的集
E \ 表示该集合中不包含第 i i 个比特节点 的其它元素 。 ( )比特点更新 2
L (= QO sm(r hc,) Q1 L (+u L( eki; ) c )
ed n
4 D C码与 T ro码的性能比较 L P u b
L ( )=Lc + ∑ r i qi j ( ) ( , , ),( \ ) JE t c
式 中 C表示与第 i b 节点相连 的 cek节 个 i t hc
T ro 又叫做并行 级联卷积码 ,由 CB r u u 码 b .e o r 等人在 19 年首次提 出。T ro 93 u b 码编码器通过交织 器 把两个递 归系统卷积码 ( S ) R C 并行 级联 , 对校验 位 采 取不 同的删 除方 式 来得 到各种 不 同速率 的
点的集合 E A『 - c 表示该 集合中不含第 个 cek hc
— —
7 — 4 —
维普资讯 http://www.cqvip.com
20 年第 2 07 期
张培 : 低密度奇偶校验码及其译码算法实现
T ro ;解码部分 由两个软输入 软输 出的子译码 ub 码 器(IO 采用多级级联结构组 成。T ro 通过对 SS ) ub 码 子码的伪随机交织实现大约长度 的编码 ,具有接近
的突发误码情况下 ,D C L P 码有更优 良的性能; 在编码 器和译码器 中不需要交织等等。因此可以说 ,D C LP 码是迄今为止纠错码理论界所发现的编解码复杂度 可接收的性能最好的纠错码之一。
5 结论
随机编码的特性 ,同时采用迭代算法使译码复杂度
达到中等水平 。T r 码
在低信噪 比条件下性能非 uo b
常优越, 但是在高信噪 比情况下性能却有所下降 , 原
因是它的码字间的最小欧式距离较小 ,误码 率曲线
随着译码算法的性能越接近香农限,它的改进 难度也越来越大 , 在未来 的研究 中, 如何提高 L P CC 码译码性能 , 如何降低译码复杂度 , 以及如何在这两 者 间找 到更好 的平衡点 将是研究 的方 向。 目前 , L P 码 已成为第 四代移动通 信编码技术 中 的首 DC
选, 使用通用 D P 实现 L P S来 D C的编码 、 译码也是
一
在误码率低于某个值 的时候斜率突然减小 ,出现所 谓 的 “ 板效 应 ” 地 。 T r 码 的提出为编码 研究带来 了新 的曙光 , ub o 突破 了传统码 的约束 , 真正挖掘 了级联码的潜力 。 在
T ro码 出现 以后 ,D C码 也 被 重 新 提 出 ,它 和 ub LP
个高效可行 的方法。
T ro码 有 着 相 似 的构 成 原 则 ,同 样 具 有 接 近 ub S ann容量极 限的性能 , h no 并且可 以实现并行译码 。 LP D C码在性 能和复杂度方 面被认 为是 T r ub o 码强有力的竞争者 , 二者基于相 同的思想: 约束随机码 参考文献 :
[】G L A E .1 d ni ai - hc cd sM . 1 ALG R R G o w- es y pry cek oe [ 】 t t
Ca r g , s : T P e s ,9 3 mb i eMa s MI r s 1 6 . d
集合和迭代解码算法。 最近对 L P D C码设计的改进和
硬件的实现 , 使其在性能和复杂度方面都能与 T r ub o 码媲美, 甚至超越 T ro码。现已经证明当分组长度 ub
[】MA K Y D JC G o r rC r c n o e ae n 2 C A . od Er or t g C dsB sd o o ei Ve S a e Ma i s 【.I E Tas n n r t n r p r t r e J E E rn o If ma o y s c 】 o i
T er, 9 ,5 2 3 9 4 1 h o 1 9 ( ): - 3 . y 9 4 9
[ T MA J Rcado a d R dgr L U b ne 3 HO S . ihrsn n a i . ra k . 】 e
E f in E cdn f L w - n i P rt - e k d e f ce t n o ig o o De st a y- i y i Ch c Co a
的限制条件为无穷大时, 码率 为 1 / 2的 L P 码的 DC 性能可在香农限 0 0 5 B以内可靠通信若分组长度
. 4d 0 为 1 0 该码的性能在离香农限 0 d . B以内其误码率 4 0 为 1 。而 L P O D C码迭代解码算法 的复杂度远低于 Tr ub o码并且现以证 明 L P 码编码器的复杂度低 DC 于解码器的复杂度。 此外 L P D C码优于 T ro ub 码的其
它特点是 :D C L P 码可以方便的任意改变码率和改变 码长进行编解码 不必 向T ro ub 码那样采用打孑方法 L 改变码率牺牲 了性能 ;D C没有不 可检测错误 , LP 也
[ .I E Ta s n no a o T er,2 0 ,7( ) J E E r o I r t n ho 】 n fm i y 0 14 2 :
39 4 1 9 - 3.
[ 4 】张志 涌 , 彦琴 , . T A 徐 等 MA L B教程一 于 6X版本 [ . 基 . M】 北 京: 空航天 大学 出版社 ,0 3 航 20 . [】高晟 , 5 杜百 川.L P D C码 研究及其 应用田. 电视技 术 , 现代
2 0 1 16 0 . 0 4, 0: 0 —1 9
[ 袁 东风,张海霞 , 宽带移 动通信 中的先进信道 编码技 6 】 等.
术[ . M】 北京: 邮电大学 出版社 ,0 4 20 .
就是说不存在错误平层 ,ub T ro却不然 ;D C码的吞 LP 吐量大, 更适合高码率应用 ; 在干扰 、 衰落等原因引发
( 责任编辑: 洁) 杜
Lo d n i rt c e k Co e n t c d n g rt m w- e st Pa i - h c d s a d Is De o i g Al o i y  ̄ h
ZHANG P i e
(uhu V ct nlU ie i,Szo 1 4C ia S zo oai a nvrt uhu 250 ,hn) o sy 1
A src:T i pp rf t nrd c ste s u tr n e p n il fL w D ni ai — hc (D C b ta t hs a e i l it u e h t c e a d t r c e o o - e sy P ry C ek L P ) s ry o r u h i ps t t
c dn a d d c dn , t e d s r e h w o i lme t i ag rtm o Malb F n l , i ie te o ig n e o ig h n e c b s o t mp e n t i s lo h i n t . ial a y t vs h g p r r n e c mp rsn b t e te DP a d he T r o c d s An e b la t ft r o e DP i e oma c o aio ewe n h
L C n t u b o e . f d t rl n uu e f t L C s h i i h
p it d o t on e u .
K e r s L C Co ig De o ig y wo d : DP ; dn ; c dn ;Malb Alo tm t ; a g rh i
一
7 — 5