（信号与信息处理专业论文）数字电视地面广播系统中ldpc信道编码的应用开发.pdf

摘要 摘要 数字电视地面广播系统中l d p c 信道编码的应用开发 硕士研究生：王玲导师：赵力教授 东南大学无线电工程系 纠错编码技术是移动通信、卫星通信、光纤通信和磁盘存储等系统中的关键 技术之一。其中，由g a ll a g e r 在1 9 6 2 年首先提出的低密度奇偶校验码( l d p c ) 码，在沉寂了多年之后，受到t u r b o 码的启发，m a c k e y 和w i b e r g 等人对6 a l l a g e r 码重新进行了研究发现g a l l a g e r 码优异性能，l d p c 码再次成为通信技术研究的热 点。l d p c 码是一种具有稀疏校验矩阵的线性分组码，研究结果表明，采用迭代的 概率译码算法，l d p c 码可以达到接近香农极限的性能。 本论文较为系统的介绍了l d p c 码的构造、编码和译码。重点是l d p c 码的译 码算法和其在数字电视系统中的应用。本文首先研究了l d p c 码理论基础，如图结 构、线形分组码。之后介绍了几种构造方法，包括m a c k a y 随即构造、有限几何的 e g 构造，以及相应的编码算法。本文介绍了b f 、w b f 、l p - w b f 、b p 、b p _ b a s e d 和 n o r m a l i z e db p _ b a s e d 算法，详细的推导了b p 译码的各个步骤。给出了a w g n 信道 下几种l d p c 码在不同译码算法下的仿真性能。 同时，本文在b f 译码算法的基础上提出了改进算法i t e r a t ef - b f 算法，仿真 结果表明其对低列重的码有明显的改善。 最后，本论文对l d p c 码在数字电视地面广播系统中的应用进行了研究。文中 仔细分析7 b p 软译码的初始化问题，并且给出了a w g n 信道，多进制调制系统下的 仿真结果。然后，将l d p c 和o f d m 结合，在r a y l e i g h 信道下仿真了l d p c - o f d m 系统的 误码率性能，选用的系统是时域同步正交频分复用( t i m ed o m a i ns y n c h r o n o u s 0 f d m ，t d s o e d m ) 系统。 关键词：l d p c ，b p 译码，t a n n e r 图，e g 码，稀疏矩阵，数字电视地面广播 目录 a b s t r a c t a p p l i c a t i o no fl d p c f o rd i g i t a lt vt e r r e s t r i a lb r o a d c a s t i n gs y s t e m b yw a n gl i n s u p e r v i s e db yp r o f z h a ol i d e p a r t m e n to f r a d i oe n g i n e e r i n g s o u t h e a s tu n i v e r s i t y e r r o r - c o r r e c t i n g c o d e sa r e w i d e l y u s e di nm a n yf i e l d s ，s u c ha sm o b i l e c o m m u n i c a t i o n , s a t e l l i t ec o m m u n i c a t i o n , a n ds oo n l o w - d e n s i t yp a r i t y c o d e s ( l d p c ) o n ek i n do f e r r o r - c o r r e c t i o nc o d e s , i sd 娟n e d i nt e r m so f v e r ys p a r s em a t r i c e s ， a n dc a nb ed e c o d e db yi t e r a t i o na l g o r i t h m s i tw e r ef i r s ti n v e s t i g a t e di n1 9 6 2b y g a l l a g e r , b u ta p p e a rt oh a v eb e e nl a r g e l yf o r g o t t e n m a c k e ya n dw i b e r gr e d i s c o v e r e d t h e i re x c e l l e n tp r o p e r t yo fa c h i e v i n gi n f o r m a t i o nr a t e su pt ot h es h a n n o nl i m i t ，a f t e rt h e a x t r e m es u e a 3 e s ao f t u r b oc o d e s t h i sd i s s e r t a t i o np r e s e n t sas y s t e m a t i ci n v e s t i g a t i o no f l d p cc o d e s w ei n t r o d u c e t h et h e o r yf o u n d a t i o no f l d p c ，f i r s t l y , i n c l u d i n gt a n n e rg r a p h , s e v e r a lc o n s t r u c t i o n s a n dr e s p o n d e de n c o d i n gm e t h o d s t h a nw es t u d yt h em a j o rd e c o d i n ga l g o r i t h m s , b f , w b f , l p w a f , b pa n dt w oo t h e ri m p r o v e db pa l g o r i t h m s s o m es i m u l a t i o nr e s u l t sf o r a d d i t i v ew h i t eg a u s s i a nn o i s e ( a w g n ) c h a n n e la r es i y e n a so n eo f c o n t r i b u t i o n so f t h i sd i s s e r t a t i o n , a ni m p r o v e dd e c o d i n ga l g o r i t h mb a s e d o nt h eb fa l g o r i t h m0 t e r a t ef - b f ) i sp r o p o s e d c o m p a r e dw i t hb fa l g o r i t h m , i t a c h i e v e sc o n s i d e r a b l ei m p r o v e m e n tf o rl o wc o l u m nw e i g h tl d p cw i t ha l m o s tt h es a m e c o m p l e x i t y t h ea p p l i c a t i o n so f l d p cc o d e sa r es t u d i e d w ea p p l yt h el d p ct ot h et i m e d o m a i ns y n c h r o n o u so f d m ( t d s - - o f d m ) s y s t e mi ng a y l e i g hf a d i n gc h a n n e l s t h eo f d m p a r a m e t e r sa r es e l e c t e da c c o r d i n gt oc h i n e s ed i g i t a lt v t e r r e s t r i a l b r o a d c a s t i n gs t a n d a r d s k e y w o r d s ：l d p c ，b pd e c o d i n g ，t a n n e rg r a p h , e g - l d p c ，s p a r s em a t r i x , t e r r e s t r i a ld i g i t a lt v 独创性声明 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 研究生签名：至硷日期：型6 ：3 ：监 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印，缩印或其他复制手段保存论文。本人电 子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文 被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名： 王耳全 东南大学硕士学位论文 第一章绪论 本章首先介绍信道编码理论和l d p c ( l o w d e n s i t yp a r i t yc o d e ) 码的研究现状，然后概 述数字电视标准的发展，最后给出这次论文的主要内容和结构。 1 1 信道编码 通信的目的是将载有信息的信号可靠的传送给对方，然而由于在传输过程中数字信号受 到干扰，使信号码元波形变坏，接收端可能发生错误判断。信道中乘性干扰引起的码间干扰， 通常可以通过均衡技术纠正，而对于加性干扰，除了要选择合适的调制解调方法以及调节发 射功率外，纠错编码也是必须考虑的环节。 一个基本的数字通信系统如图卜1 所示。其中，信道编码器的作用是按某种算法，对信源 码适当的添加冗余比特，使得接收端信道译码器根据这些冗余比特尽量多地找出并纠正错码。 互 _ 由 图1 - 1 数字通信系统得基本模型 s h a n n o n 在其1 9 4 8 年发表的论文“通信的数学理论”中，首次阐明了在任何一种有扰信 道中均存在一个确定的信道容量只要信息以小于此信道容量的速率传输，传输错误概率就 可以任意小。s h a n n o n 定理的完整表述是：设r 是信息传输的速率，c 是离散无记忆信道的信 道容量，占是一个任意小正数，则只要f 3 ) 个1 ，每行有吃( 吃 巩) 个1 的正则码，将校验矩阵按行水平的分割为 矾个大小相同的子矩阵，每个子矩阵的任一列都只包含一个1 ，第一个子矩阵按特定的方式构 造而成，所有列只包含一个1 ，g a l l a g e r 文中是用的递减的形式排列，即第珩所有的1 都分布 在第到( f l k + l 到弦列。其它下面的- ，一1 个子矩阵都是是第一个子矩阵的随机列交换而 成。这种构造方法可如下表示 h 。为第一个子矩阵 h o = 1 1 l l 止 1 1 1 1 山 半 东南大学硕士学位论文 整个h 阵为 这里石代表对矩阵作列交换。 h =万：盈。) 石。( h 。) 这种构造方法简单，易于实现和分析，但不能控制矩阵的t a n n e r 图中短环的出现，影响 了b p 译码性能。 3 1 2m a c k a y 的构造 为消除校验矩阵中的短环，m a c k a y 在g a l l a g a r 的基础上提出了自己的构造思想 1 3 ，通 过删除一些列，达到消除短环的目的。当然，由于减少了一些列，在码率上也会有点损失， 并且行重不再是严格的相等。 具体的构造思想有如下四个； 构造法1 a ：这是最基本的构造方法该方法构造的矩阵每列的重量都为一固定值t ，而每两 列之间重叠的1 的个数不大于1 。 构造法2 a ：对于一个m n 矩阵，前m 2 列的重量都为2 ，并且各列重复不超过1 ，这些 重为2 的列由两个m 2 m 2 的单位矩阵构成，一个在上，一个在下。其余如1 a 。 oo ( a ) o 图2 - 1m a c k a y 的构造方法( a ) 1 a ；( b ) 2 a ( b ) 构造法1 b ，2 b ；由构造1 a 或构造2 a 构造校验矩阵，然后从该矩阵中删除一些仔细选择的列， 使得结果矩阵对应的二分图中没有小于某个给定长度的环，例如1 = 6 。 上图中的圈代表，圈中的数字3 代表此矩形中有该数字个排列矩阵的叠加，对角线表示单 1 4 东南大学硕士学位论文 位矩阵。 3 1 3p e g ( p r o g r e s s i v ee d g e - g r o w t h ) 码【15 】 构造思想是以增加g i r t h 为目的；p e g 方法的具体操作：给定变量节点的数目、校验节点的 数日m 和变量节点的分布序列，边选择程序开始放置新的边，选择新边时尽可能对t a n n e r 图的 g i r t h 有较小的影响；新边放置好后，继续搜索下一个边，直到结束。 3 1 4 有限几何构造 上述几种都是随机构造方法，是无结构的，在发送和接收端要用大量的空间来存储矩阵 信息，而且编码很复杂。而系统码有特定的结构，可以克服这些问题。l i ns h u 等人 6 提出 了基于有限几何( f i n i t eg e o m e t r i e s ) 的构造方法。这种码有如下优点：有很好的最小码距； 它的t a n n e r 图的g i r t h = 6 ；迭代译码的性能好，并且具有循环或半循环的性质，可以实现线性 时间编码，这是其它l d p c 码所不具备的性质。另外，硬判决性能较其它的码好，译码收敛快， 这个特点将在后面的仿真中体现。 为介绍这种码，我们需要先简单介绍一些有限几何的有关概念。 有限几何的定义：设g 是一个由点、线构成的有限几何，这些线点具有这些结构特点：1 ) 每条线上有p 个点：2 ) 两点之间有且只有一条线；3 ) 每个点上有y 条线通过；4 ) 两条线或 者平行，或者相交于一点。共有两种有限几何，分别是欧氏几何( e u c l i d e a ng e o m e t r i e s ) 和映射几何( p r o j e c t i v eg e o a e t r i e s ) 。 对于g “2 ) 域上的m n 的校验矩阵h ，h 的行代表几何空间里的线，列代表几何空间 里的点。第f 点在第，条线上，则矩阵中= l ，否则= 0 ；由有限空间的定义知，此矩 阵各行之间最多只有1 个位置重叠，因此不会有长度为4 的环。 l i ns h u 等人共提出四种e g - l d p c 码的构造方法 6 ，分别是1 ) t y p e - ie u c l i d e a ng e o m e t r y ( e g ) 一l d p c 码：2 ) t y p e - i ie g - l d p c 码：3 ) t y p e ip r o j e c t i v eg e o m e t r y ( f 6 ) 一l d p c 码：和 4 ) t y p e i ip g l d p c 码。这里只介绍t y p e ie g 的构造方法。 e g ( m , 2 ) 是定义在g f 伫。) 域上的m 维欧氏几何，有2 “个点，每个点是g f ( 2 i ) 上的口重， 全零向量o = ( o ，0 ，o ) 称为几何空间的原点。在g f ( 2 。) 上的2 “个重矢量构成了g f ( 2 i ) 上的 口维矢量空间，因此在e g ( n l ，2 ) i - _ f l c j 一条线要么是e g ( m ，2 ) 的一维子空间，要么是一维子空 间的陪集。因此e g ( i i i ，2 一) 上的每一条线均包含包括2 5 个点。 e g ( m , 2 ) 里共有 1 5 东南大学硕士学位论文 2 0 “。( 2 ”一1 ) ( 2 一1 ) 条线，每条线均有2 抽廿条线与之平行，每个点均有( 2 一i 摊一i ) 条 线相交于此。 g f q “) 是g 雌) 的扩域，在( 雌“) 里的每一个元素都可以表示g f 乜) 上的道。因此， 在g f ( 2 “) 里的每个元素可以用来表示e g ( m 2 ) 上的点，有限域g f ( 2 一) 可以表示欧氏几何 e g ( m ，2 ) 。设口是g f ( 2 “) 里的本原元素，口。，口。，口t ，口2 ，口2 m * - 2 就构成了e g ( m ，2 s ) 的2 “个点，这里0 = 口”是空间的原点，设口是非零点，则2 5 个点： 伽矗4 ) = 恤：g f ( 2 5 ) ) 构成空间e g ( 耻2 ) 中的一条线。设口1 ，口，是e g h 2 s ) 里的两 个线性独立的点，那么下面点的集合矗+ 钯，) ；矗+ j 勉，：g f ( 2 5 * 就是在e o h 2 - ) 中通过点口1 的一条线，则线白+ 触， 和矗+ 触 相交于点口。 假设何，0 是g 唯) 域上的矩阵，矩阵的行是e g ( m ，2 ) 中不过原点的线在g 雌8 ) 中 的映射向量，列是e g ( m ，2 。) 中的2 “一1 个非零点，第i 列对应于口。这样，日共有 m = 2 “- 1 ) ( 2 ”一1 ) ( 2 。一1 ) 行，2 ”一1 列。行重为p = 2 4 ，列重为( 2 “一1 ) ( 2 5 1 ) - 1 ， 因此，当码长很长时，矩阵就变得很稀疏；码字的最小距离至少是( 2 ”一1 ) ( 2 7 一1 ) 。 以阱( 2 5 5 ，1 7 5 ) 的校验矩阵日二( 2 ，4 ) 为例，说明第一类e g 码的构造过程。因为m = 2 ， 8 = 4 ，所以首先找出g 雌8 ) 域的本原多项式p ( 功= l + x 2 + + x 4 + x 8 ；其次，需要求出经 过某一点口的任意一条不过原点的直线上的所有点。己知通过点口的一条线上的点具有 矗。+ 触， ；矗。+ j h ，：f l g f ( 2 5 * 形式，如果我们取j = 2 5 4 ，就要求满足形式为 矗“+ 届口7 ) 的点，取y = 口( 2 i - 1 ) f “，则卢 o ，1 ，1 ，y 2 ，y 1 4 ，根据运算可以得到 一条含1 6 个点的一条直线。之后，由所得的直线去求出该直线的关联矢量，该矢量由2 5 5 个 点( 不包含原点在内) 组成，如果某点在直线上，则关联矢量该点处的值为l ，不在此直线上 则为o 。 最后，由所得的关联矢量作为校验矩阵的第一行，对该矢量向右循环移位2 5 4 次，每次得 到的矢量均作为校验矩阵的一行，就得到了二维欧氏几何l d p c 码的校验矩阵。码的参数如下 表所示： 1 6 东南大学硕士学位论文 表3 - 2t y p e - ie g 2 5 5 的参数 nk c l i 。 py 242 5 51 7 51 71 61 6 根据矩阵的构造知这个码具有循环特性，可用生成多项式g ( 功编码。求取它的生成多项式之 前先介绍一个符号伪) 的定义和定理3 11 1 8 定义3 1 ：令h 是小于2 “的非负整数，我们能把h 展成如下的以2 。为基的形式： 办= 8 0 + 4 2 1 + 十巧卜1 2 ”一1 式中0 五 2 。，其中0 i m 。则 ( 功表示 的2 5 重量。 伪) = ( 3 1 ) ( 3 2 ) 定理3 1 令口是0 ，j ) g f ( 2 。) 的本原元，这里= 0 。令i ，是小于2 “一l 的非负数。令 ( 。是 2 “一1 除2 l 矗所得余项，即 2 1 h = q ( 2 ”一n + h 。 ( 3 3 ) 这里o h 。 2 ”一1 ，h o = h 。长为2 “一l 的0 ，s ) e g 码的生成多项式g g ) 以口“为根的 充要条件是： o 。嚣伪o ) 印一一1 ) ( 2 5 1 ) ( 3 4 ) 定理3 1 表征了e g 码的生成多项式的根。下面给出生成多项式的求取算法： 1 ) 固定 是小于2 “的非负整数，当0 ， s 变化时，根据式( 3 - 3 ) 求取h ( t 2 ) 使h 在0 h 2 ”范围内变动，求出满足式( 3 - 4 ) 的所有h 。 1 7 东南大学硕士学位论文 3 ) 求出的k 个根 得到相应的甜“，就是多项式g 的根。 3 2 编码 编码就是在给定z 0 。的条件下，将一个信息序列s 映射成编码序列x ，使其满足 h = 0 其中x = g ，p ) ，s 是信息序列，p 是校验序列。 ( 3 - 5 ) 对于l d p c 码来说，一个需要面对的主要问题是看起来的高编码复杂度，l d p c 码编码的直 接实现具有码长n 的二次方的时间复杂度，而t u r b o 码可在线性时间内编码。 为降低复杂度，许多人都针对l d p c 编码进行了研究，s i p s e r 和s p i e l m a n 提出用级联图 而不是二分图以减小编码复杂度，m a c k a y ，w i l s o n 和d a v e y 建议强制性的使奇偶校验矩阵具 有下三角阵的形式。t j r i c h a r d s o n 和r lu r b a n k e 5 提出具有线性时间复杂度的有效 编码，而l i ns h u 等人提出的有限几何码 6 ，由于具有循环或准循环性，使用循环码的编码 方式，编码器设计简单，可实现线性时问的编码复杂度。 3 2 1 高斯消去法 首先对矩阵作预处理，利用行变换和列变换校验矩阵日x 变成一个下三角矩阵日村t 。， 如图3 - 2 所示 _ 。h ，p ，。i 一，- 厂”习 已矗二文刭 图3 2 下三角形形式的校验矩阵 矩阵的行变换并不会改变码字的结构，而列变换会改变t a n n e r 图的变量节点的位置，并 没有改变码字的最小距离，故不影响码的纠错能力。例3 - 1 将说明列变换对矩阵和t a n n e r 图 的影响。 1 8 东南大学硕士学位论文 例3 - 1 以例2 - 1 的矩阵为例，如果将第六列和第二列交换，得校验方程 f x l + x 4 + l x 3 + x 4 + 1x 。 + x ： + 【x 2 + x 3 + 相应的t n e r 图为： x6=0 x 5 = 0 x 5 = 0 x6=0 ( 3 - 6 ) 图3 - 3t a i l n e r 图 经过上述变化，原矩阵日 f 。，化成了下三角矩阵日。 ，) 。利用递归法，根据己知 信息序列s = g ，j ：，$ n - m ) 求出校验序列p = 0 。，p ：，p k ，) 。具体公式是 a = n 一- “e h 鹕+ 户i - i ，曩, j + n - u p j ( 3 7 ) 为了得到下三角矩阵，如果用软件实现，预处理部分的复杂度是d 0 3 ) ，具体为 三矿+三一：一三力次乘法，三矿一三胛次加法，而编码的复杂度是。g：)，具体为委”o+1)次32633 、7 2 、 乘法，j 1 聍o 1 ) 次加法。这么高的复杂度，是由于对矩阵作了高斯消去，使得矩阵h 已不再 是稀疏的。 3 2 2 近似下三角有效编码 首先我们假设矩阵h 的所有行都是线性无关的。如果矩阵行不是线性无关的，那么矩阵的 生成算法应该能够检测到行相关性，并重新运行直至生成一个满足行线性无关的校验矩阵， 或者也可消去矩阵h 中的冗余行。 与高斯消去法类似，在编码之前需要先对h 矩阵作预处理，预处理之后的矩阵仍具是稀 疏的。首先，选定一正整数r ，对矩阵的行和列进行重排，得到如下的近似下三角矩阵。 1 9 东南大学硕士学位论文 即为 ；冉咎 4 2 气。 t l ede 图3 - 4 近似下三角矩阵 h = 曙 三a m i ： 午 ；， j o ( 3 8 ) 其中，a 的维数是( m - g ) ( n - m ) ，b 是( m - g ) g ，t 是( m - g ) ( m g ) ，c 是g ( n - h i ) ， d 是g g ，最后e 是g ( l - g ) ，这些子矩阵都是稀疏的。左乘如下的矩阵 ( 一刍一。为 协 我们得到矩阵 至此，预处理结束。 p 占1 ( 3 - l o ) 一e t l a + c e t l b + d0 1 令编码序列x = ( s ，p l ，p 2 ) ，其中s = ( s l ，s 2 ，s n m ) ，p l = ( p j ，p 2 ，p g ) ， p 2 = ( p l ，p 2 ，p 地) ，那么方程h x 7 = o 可以分为2 个方程， a s 7 + 纠+ 矽；= 0 ( 3 1 1 ) ( 一e r l a + c ) s 7 + ( 一e r l 曰+ d ) 衍= 0 ( 3 1 2 ) 定义妒- e r l b + d ，如果矩阵妒非奇异，则可以根据下式由已知的信息序列s 得到p 1 、p 2 l g = 一妒1 ( 一e t 一1 a + c ) ， ( 3 1 3 ) 东南大学硕士学位论文 一= 一t 。1 ( 4 ，+ 印f ) 然后得到完整的码字x = ( s ，p i ，p 2 ) 。如果矩阵妒奇异矩阵，要先消除奇异。 ( 争1 4 ) 从计算公式知用软件实现编码时计算p l 的复杂度是d g + 9 2 ) ，计算p 2 的复杂度是d o ) ， 因此应该选择尽量小的g 。 3 2 3 循环编码 循环码的编码器硬件实现简单，可以用基于生成多项式的线性反馈移位寄存器来完成， 线性时间完成编码。例如对于一个“ r ，足) 的循环码( 信息比特长为n ，校验比特长为k ) ，编 码算法如下： 烈功= 肌( 功g ( 功+ d 功 ( 3 1 5 ) s ( x ) = 肌( 功“+ c ( 力 ( 3 - 1 6 ) 这里，g ( x ) 是生成多项式，m ( x ) 是信息序列，e ( x ) 是余项，p ( x ) 是商，而s ( x ) 是编码结果。 这个码的编码电路如下图所示 3 3 本章小结 图3 - 4 循环码编码器 卜固j 这一章主要介绍经典文献中有关l d p c 码的构造和编码。构造好码是保证l d p c 码良好的 纠错性能的基础，但只有低的编码复杂度才能使l d p c 真正成为实用的信道编码。但是由于线 性分组需要在接收到一帧中的所有比特后才能够进行编码，这引入了一定的编码时延。 2 1 - 锄 东南大学硕士学位论文 第四章l d p c 码的译码算法 l d p c 码之所以能有这样好的性能，很重要的原因是在译码中采用迭代算法，并且由于校 验矩阵的稀疏性，使得译码的复杂度和码长成线性关系，克服了分组码在码长较长时所面临 的计算复杂度问题；另外，在码长很长时，相距很远的信息比特参与同一校验，这使得连续 的突发差错对译码的影响不大，也就是说编码本生就具有抗突发差错的特性，一般情况下可 以不需要引入交织器。 l d p c 码的译码算法主要有基于编码二分图结构的m e s s a g ep a s s i n g 算法类，算法的性能随 量化阶数的增加而提高，同时复杂度也随之增加。大致可以分为硬判决和软判决。硬判决实 现简单，但性能不佳，软判决则正好相反，性能好，但实现复杂。 g a l l a g e r 最初就给出了两种迭代译码算法：硬判决( b i tf l i p p i n g ，b f ) 和软判决算法 ( p r o b a b i l i s t i cd e c o d i n g ) 。前者计算复杂度很低，但其译码性能不理想，后者虽然性能 更好，但复杂度太大。之后，研究者们对硬判决和软判决提出一系列改进算法。硬判决方面， 文献 6 中提出了一种简单的改进算法( w e i g h t e db f ) ，采用信道的软信息对比特翻转的判 据进行加权，可以在译码复杂度增加不大的情况下，提高译码性能。为了进一步缩小与软判 决算法的差距，在w b f 算法的基础上，又出现了两类算法：l p - w b f 算法 1 6 和w s w b f 算法 3 0 ，它们在基本不增加译码复杂度的情况下，使w b f 算法的译码性能有了较大的提高。另 外，针对有限几何码，还有大数逻辑译码，文献 6 中还提出了加权大数逻辑译码。 软判决方面，1 9 9 9 年m a c k a y 和n e a l 提出了将b p ( b e l i e fp r o p a g a t i o n ) 算法用于l d p c 译 码 1 3 ，也称为s u m p r o d u c t 算法，其译码性能比硬判决算法好的多，而相应的运算复杂度也 不大。f o s s o r i e r 对低复杂度的b p 算法作了进一步研究，提出7 b p - b a s e d 算法 7 ，简化t b p 算法。为了改善b p - b a s e d 算法因为校验节点上的简化处理而造成的性能损失，j c h e n 8 9 提出了两种改进算法：采用归一化的近似最佳b p - b a s e d 算法( 亦称为n o r m a l i z e db p - b a s e d 算 法) 和通过降低可靠性值来改善外附信息精度的o f f s e tb p b a s e d 算法。本章将主要研究上 面提到的b f 、w b f 、l p - w b f 和8 p 、b p - b a s e d 、n o r m a l i z e db p - b a s e d 算法。 这里我们假设信道是二进制对称信道( b s c ) ，信道噪声为加性高斯白噪声( a w g n ) ，噪 声均值为0 ，功率普密度是n o 2 。用b p s k 调制，能量为l ，编码后序列v = ( 加，v l ，v n i ) 被 映射成x = ( ，x n 一1 ) ，这里映射公式是t = 2 v f + 1 ，( o ， 占的比特的位置五。 6 如果己到最大迭代次数，则停止译码，输出结果。否则，减少门限艿，迭代次数 加1 ，进入步骤2 ，进行下一次迭代。 下面以码率为5 8 校验矩阵h 来说明b f 译码的一次迭代过程，这里只翻转判据最大的变量 节点。 设校验矩阵为： h = 1l 1o ol o 0 10 oo ol 1l 0 0 11 1o o1 lo o1 lo 01 假设发送端信息序列为d = ( 1 ，0 ，1 ，1 ，o ) ；则编码后的码字为v = ( 1 ，0 ，0 ，1 ，0 ， 1 ，1 ，0 ) ；经过调制之后的调制符号为x = ( 1 ，- 1 ，- 1 ，1 ，- 1 ，1 ，1 ，一1 ) 。经过a w g n 信 道后，接收端接收的序列忙( - 0 5 ，1 2 ，0 4 ，一1 3 ，一1 2 ，一0 3 ，0 8 ，0 6 ) ，译码器 的输入序列z = ( 1 ，0 ，0 ，1 ，1 ，1 ，1 ，o ) ；则计算得校验字s = ( 0 ，1 ，l ，o ) ；计算判 据得f = ( 1 ，1 ，0 ，1 ，2 ，1 ，1 ，1 ) ；下面以表格形式说明翻转判据的计算过程。 表4 - 1b f 各节点翻转判据的计算 校验节校验字 v lv 2v 3uv 5v 6 v 8 点c s c l o0ooo 东南大学硕士学位论文 已 1111l1 g 11l11 c 40 0o00 f11012111 由表格知，v5 的判据f 5 最大，故翻转v5 ，得到此次迭代的译码结果z 2 ( 1 ，0 ，0 ，1 ，0 ， 1 ，l ，0 ) 。 上面的算法介绍表明b f 算法只需要模二运算，硬件实现比较简单。但与后面介绍的软判 决算法相比，b f 算法的译码性能要差的多，所以b f 算法适合用于信道条件很好的情况。通常， 采用b f 算法来粗略的判断校验矩阵对应的l d p c 码是否具有良好的纠错性能。 4 2 力权b f ，w e i g h t e db i tf l i p p i n g ( w b f ) 如果在b f 翻转判据计算时，增加一些接收序列的软信息( r e l i a b i l i t yi n f o r = a t i o n ) ， 可以提高b f 的纠错能力。y k o u 6 提出了加权b f 算法( w e i g h t e db i tf l i p p i n g ) 算法。 对于接收序列，e a w g n 信道t ，接收符号y 。的可信度( 软信息) 是y 。的幅度iy 。 ，幅度 越大，则硬判决结果z 的可信度越高。因此在_ b f 算法中，用参加第j 个校验式的所有变量节 点对应的信道输出幅度iy 1 的最小值作为这一行所对应的校验节点的加权因子，之后再计算 翻转判据e 。 首先，给出下面3 个定义式 l y j k = m i n l y , l ：o i 创，h j j = 1 ( 4 - 4 ) 纷i = ( 2 s j 1 ) l y ji 。 ( 4 5 ) 和 e i = 触，) 纺， ( 4 6 ) w b f 具体的算法如下： 东南大学硕士学位论文 1 输入信道接收序列y = 订o ，y i ，y n 1 ) 和解映射结果z - = ( z o ，z 1 ，z m l ) ，初始化迭代 次数k ：1 。 2 计算校验子向量s 。如果所有校验方程皆满足( s 0 。= 0 ) ，则停止译码，输出译码 结果。否则进入步骤3 。 3 根据式( 4 4 ) 计算每个校验节点的加权值阢i 一。 4 根据式( 4 5 ) 计算各个校验节点c j 将传给每个节点v 。的软信息础 5 根据式( 4 6 ) 对每一个校验节点，计算其翻转判据e p 6 最大的比特的位置q 。 7 翻转z o 。 8 如果己到最大迭代次数，则停止译码，输出结果。否则，迭代次数加1 ，进入步骤2 ， 进行下一次迭代。 下面将仍以4