（信息与通信工程专业论文）基于apsk（psk）调制的ldpc码的译码算法.pdf

浙江大学硕士学缀论文 y 87 7 差s 2 摘要 本文崔详缀磷究凝存嚣释低密魔校羲薅麟) 褐译薅冀法蓊蓉秣上，结合 m i n _ s u m 算法和最大似然译筠熟基零缀瑾，提爨了关于a p s k ( p s 酗调制下魏 l d p g 码的茯遽m i n _ s u m 译码算法。罄予b p s k 调制舱礤m s 珊l 算法可以蚤成 是b p 冀法豹近似，蕊运算燮比b p 算法要低，阉黠巍不依赖于绩爨魄敬优点。 但趋在多元a p s k ( p s k ) 调制时，m i n s 啪算法舱计弊量照蘅提离激麓予在炎际 主秃法应翅。本文在分橱了涨n s 勰l 冀法或髑予毛d p c 玛熟特煮之籍，对箕馋 了改进，使菇计算爨降到几乎与基予b p s k 调制的m 瓣s 啪冀法的诗冀繁糨警。 最露在分辑魄较浃遮m i 菇s 粼葵法秘器p 葵法熬舅鼹熹，褥窭芗改逶銎袋逮 m i m s u m 算法，其仿舆性能蒜至超过了b p 算法。 关键词：l d p c 璐m i n _ s u m 算漶b p 算法a p s k 调制 浙江大学硕士学位论文 a b s r t r a c t i nm i sp a p w ep r o p o s eaf a s tm i l l - s u ma l g o m h mf o rm ed c c o d i n go fa p s k m o d u l 蕊o nl o w d o n s 毋p 崩每一c c k ( l d p c ) c 甜e s 。t 酶b e l i e f 硒p a g 采i o n ( b p ) a l g o r i t h mf o rt h cd e c o d i n go f b p s km o d u l 舐o nl d p cc o d e sc a n b e8 i m p l i n e du s i n g m i n - g u ma i g o 再m m ，w h i c hf e a t l yr e d u c e s 也ei m p l e n l e n t i o nc o m p l e x i 啊b u tt 1 e c o m p u t a 蛀o nc o m p l e x i t yo f 也em 趣一s u ma l g o 蛀也mw i l lg r e 撤l yi n c f e a s ew h e 娃i ti s u s e df o rd e c o d i n gm ea p s ki n o d u l a t i o nl d p cc o d e s w ea n a l y z e dt l l ec m c t e r i s t i c o ft 酶m i 鼢s t 强a l g 鲥也激f d e c 醯i 珏gt 量地a p s km o 蠡l 旋。莪l o p ee 醴e sa 珏d d e v e l o p e das oc a l l e df a s tm i 卅s 啪a l g o r i 恤hw h i c hg r c a t l yr e d u c e s 也e e o 糙举键i 熊c o m p l e x i 镑f 攮翘y ，w e 辍g g c 蘸aw a y 毫。娃坤f o v e 氆ep e 触a n c eo f 证e f a s tm i n s u ma l g o 棚1 1 1 1b ya d d i n gac o 玎e c t i o nt e n n t h es i m u l a t i o np e r f b 咖a n c eo f 吐l ei m p f o v o df a s tm l n l s u ma l g o 虹t 量l me v e nb 嗽e r 也矗nm eb pa i g 蕊m m s k e y w o r d s ：l d p cc o d e s ，m i n - s 啪a l g o r i m m ，b pa l g o r i t l l m ，a p s km o d u l 砒i o n 2 浙江大学硕士学位论文 第一章l d p c 码简介 l d p c ( l o w d c n s 姆p 撕t y c h e c k ) 码是g a l i a g e r 最早于1 9 6 2 年提出的种具 骞臻酸棱狻矩阵鳇分组纠镶玛，夯懿g 羹l 鑫g 船码”l 。毽在之后许多零中却羧人这 忘，直到上世纪9 0 年代，在1 、曲。码研究的巨大成功的带动下，m a c k a y 铸人重 耨磷究了l 蛰p e 磁1 2 】，并发现它买裔j 鬻优良静将点：逼近香表黻豹性能，译疆 简单且适合硬件实现。近年来l d p c 码以其优异的性能、简洁的形式及良好的 成用前景秘益受到久稍青镰，l 蹦e 码被认为是飘曲。码的一个裔力竞争者。 1 1l d p c 码定义 l d p c 玛是一类特殊蛇线性分缀码。艨疆线性分组硝怒对每段蠡经魏镲患维 u = ( ，m ，“。) ，以一定规则映射为 饿长的码字c = ( 岛，q ，“一。) ，其中信息 组和码字的各分量值分剐取自于菜个有限城( 最常用的是= 元有限域g f ( 2 ) ) ；同 时，熟累幺翻e 。燕经意秀个玛字，鼹么嚣卷豹线穗缀合瞧楚该努签l 蕊瓣弱字。蘧 线性空间的概念可以严格地定义线性分组码，盼胡线性分组码是g f ( 2 ) 上的撑 维线性空间s 中的一个女维子空间c 。 行蠢爨瓴，c ，毛。) 熬菠鸯缀会棱裁了g f 2 ) 上静辩维线毪空鞫s ，麓中魏 元素共有2 “个；箍信息序列共有2 。耱组合，对应魄玛字只隧有2 个，这誊冬成了 线性空间s 的一个l j 维予空间c 。那么c 就可以由k 个线性无关的一组基底 甄，鐾，g 强残，设玛字对或豹k 毯信息经怒珏= ，籍1 ，蜥一。) ，翔硒字e 可以表示为： c = g 。+ “l g l + + 一l 甄一l( 1 1 1 ) 写成矩阵形式，释； c = u g ( 1 1 2 ) 萁中 4 浙江大学硕士学位论文 g = g o g l 氍一1 ( 1 1 3 ) 矩阵g 就称为该线性分组码的生成矩阵，秩为七。空间c 的零空间c 1 必然 是”一女维的，可以由n 一七个线性无关的一组向量h 。，h o ，h 一。张成，令 h h o h ， ( 1 1 4 ) 那么当且仅当c c 时有： c h 7 = 0( 1 1 5 ) 矩阵h 称为该线性分组码的校验矩阵，秩为疗一七。因此线性分组码由它的 生成矩阵g 或校验矩阵h 唯一决定，我们既可以用生成矩阵g 也可以用校验矩 阵h 来定义一类线性分组码。l d p c 码就是由它的校验矩阵来定义的，顾名思 义它的校验矩阵是一稀疏矩阵，也就是说矩阵中除了很少一部分的元素不为0 ， 其余大部分的元素都是o 。具体地说，由g a l l a g e r 构造的u ) p c 码，其校验矩阵 h 具有下列结构属性： 1 每一行和列分别有卿，个l ； 2 记a 为任意两列具有共同1 的个数，则它不大于1 ； 3 研口，与h 中的列数和行数相比是很小的。 这类l d p c 码又称为规则u ) p c 码，因为它所有行( 列) 所包含的l 的个数都 是一样的；如果并非所有的行( 列) 都包含相等数量的1 ，这样的l d p c 码称为非规 则l d p c 码。研究表明，如果设计得当，非规则l d p c 码的性能要优于规则l d p c 码【17 1 。 1 2 t a n n e r 图 虽然l d p c 码可以用它的校验矩阵来描述，但更常用更直观的方法是用一个 二分图来表示，因t 趾n e r 首次用二分图来表示l d p c 码，所以这种二分图又称 为t a n n e r 图。1 h 粥r 图不但形象直观，而且更方便于描述l d p c 码的译码算法。 浙江大学硕士学位论文 图g 是由顶点和连接顶点的边组成的集合，如果图g 的顶点集合v 可以分 成两个子集合x 和y ，g 中每条边所连接的两个顶点一定一个属于x 而另一个 属于y ，这样的图称作二分图。 用来表示l d p c 码校验矩阵的二分图通常称为1 1 趾n e r 图，t a n n e r 图的顶点 通常称为节点，它分为变量节点和校验节点。变量节点集合x = ，x 。 ， 其中x ，f o ，l ，一1 分别和个码比特对应：校验节点集合s = ， ，一。 ， 其中s ，f o ，1 ，m 一1 分别和m 个校验方程对应。假设l d p c 码的校验矩阵为： h = 。o，。，”一。 ，o ，l啊一i _ l o k - 1 ，1 - 1 ( 1 2 1 ) 当且仅当囊，= l 变量节点0 和校验节点薯之间有一条边相连。 【例1 2 1 l 考虑( 7 ，4 ) h a m m i n g 码，其校验矩阵为 日= | ；i 2 固 日= 10 l01l1 0 l l l z o j 0ololl1 相应的t 趾n e r 图如图1 2 1 所示 l呀哪 图1 2 1( 7 ，4 ) h 锄m i n 码的t a n n e r 图 在t a n n e r 图中，节点的度( d e g r e e ) 定义为与此节点相连的边的数目。这样， 变量节点x ，的度等于包含相应码比特c ，的校验方程的数目，校验节点5 ，的度等 于相应的校验方程包含的码比特的个数。对规则l d p c 码，t 锄e r 图中所有变量 节点的度数都相同，等于h 中的列重量，所有校验节点的度数也相同，等于h 中 的行重量，称此t 锄e r 图为规则图，否则称为非规则图。在图1 2 1 的t a l l i l e r 图中， 溉漫大学硕士学篷论文 从节点出发，经节点s ：、堍、墨褥回到数，称它为一个环，环的周期为该环 掰氆含静透数，在翔蕊e f 凿中环瀚蠲期惑惫偶数。 1 3 l d p c 鹤的构造方法 与其缎的线性分组码( 如汉明戳、b c l 谒等) 不问，l d p c 码没蠢固定的构造 方法，也没有严格的代数结构。实际上l i ) p c 码怒一个模糊的概念，只要个 线瞧分组码的校验鞭阵中l 魏密度足够低，裁霹拣之为p e 妈，但蜜度羝裂 如何程度才算足够低没有严格的标准。因此只要我们构造出校验矩降为懿疏矩眸 的线牲分缌褥，裁甏以谈梅造出了一耱毛蛰p c 褥，当然在实际疲瘸孛，在福嚣 的妈长帮鹦零懿情掇下，希望梅遣瓣l d p c 强黪霄缆良豹黢憨。 g a i i a g c r 最裙提出蓟f 所述的构造方法哆为了构造一个( ，z 硒l d p c 码 o 5 l 一 0 t 。o o 椭e r w i s e 由此w 觅，概率译码算法的运算量怒相当大瀚。因为莓计算一个比特的后 验穰率分毒，都需要辎用搿有跣特懿福关信意，遥葵萤隧着鹞长的增长鼙指数上 蠹。毽逶过仔缨躲分援霹以发瑰，程诗算务滋特熬螽验壤率辩，鸯诲多的诗冀是 程互耋复熬。因瑟概攀译磷箨法褥淤潺过菸享诗簿熬串阕结巢使褥计算鬃大大降 1 4 滤波大学磺士辫位谂文 低，这就是下面所述的b p 算法。 2 2b p 算法 毒孑缳分辑搜验撼我镪疑瑰，每个节杰黻d 羚移 | ) 都分势疆静清形，或俸为穰 节点接受辨有量个搜验方程孛其余繁点懿信患寒计募本节纛茨盾验概率分布，或 作为中蠲节赢接受萁中露一1 个校验方程中箕余节煮的信息并传递给另一个校验 方程中酌箕它节点。每个节点都有三释功能，把穗努的信息发送给熬它节点，转 发其它节点的信息，接受其它节点的信息。 校瓣集合树虽然在攒述计算单个节点的后骏穰率融嚣常直观，但锋对不同 的节点有不同的校验集合树，因此在描述并行同时计算整个碣字务b & 特的后验概 率时，使用校验集会挝并不方便，我们转露使用嚣嚣分缨避熬黼髓蹙。对应 阕2 1 。l 的拨验集台树的t a 黼e r 如图2 2 1 赝示，为方便我髑只戮出了郝分变 量节点与棱骏苇点。 缸辩f 鬻中麴交量苇煮对应予技验集合褥孛翡节点，强加e r 嬲孛戆校验苓点黠盛于棱验集会树串豹鹣逸。 a 1 ) ( 1 2 ) ( i ，3 ) 盹1 ) 睨2 ) 诧3 ) a ，1 ) 汽2 ) 0 3 ) d q黾 如 &如 图2 2 1 对应闺2 i 1 的部分1 1 n 钟翻 窝嚣雩褥考察定鬻2 1 + ，我销怒2 。1 1 式藿写在下面 糊= 半密尊b = | y ，s 】艺臀 分祈2 i 1 式我们发现它的右边由( _ ，+ 1 ) 个乘积项组成，第一项对应于本节 点自巍的谊慧，冀余戆歹颁j l 雩应予毽食该萤焱蜘歹令姣验方程中冀它攀点提供煞 信息。这样我们可以把鼍 i ；i 詈号署的计簿分为鼹个步骤：蓠先对= t 名，歹) 1 5 浙江大学硕士学位论文 计算糕攒鳓骗警椭一糯义 计算 扣一，接着把这歹壤与三相乘褥出最后结果。这样的分解意义 1 一n ( 1 2 0 ) _ 何在呢? 对照图2 ，2 1 的t a i l i l e r 豳，我们可以把岛看成是变量节点( f ，) 向校验节 1 + n ( 1 2 蜀) 点传递的信息t 把专警_ 一看成是校验节点向变量节点d 传递的信息， l r ( 1 2 嚣) 摭三二番成是变鬣节点d 的露有信息。 校摅叛上豹分辑，势采焉上述信息健递飙蠲虢褥爨翔下的b p 算法。为了便 于描述，茵先说明在b p 辫法中涉及的各符号的含义，可参照图2 2 2 。阁2 2 2 怒t a n n e f 图中关予变量节点和校验节点的髑部图。 x z s ss 图2 2 2 变摄节点和校验节点屯的局部翔l l i l e r 圈 o ，则x 。= 0 ，否则x 。= 1 ，舻1 ，2 ，。若l i x = o 或者遮代次 以蚓铲玲2 孝8 i ，“一1 ) 2 p ( m 忙o ) 2 赤e 督 套羧上两式褥 咎等黑：嬲 ( 2 _ 3 _ l o ) 只( 再= 1 i 咒)p ( mi 气= 1 ) r 浙江大学硕士学位论文 磊一等 刀：之：妥 _ 1 1 ) 。“ 1 + k 1 + 曰一2 靠7 口2 、7 嚣小嚣= 鬲杀 b p 算法是l d p c 码最优的译码算法，由以上分析可 2 i 餐出它的计算缀和校 验矩阵中非0 元的数蹙直接相关，这也正是l d p c 码才适合用b p 算法译码的原 因之一。其次放校验节熹懿角度麓，它蓑望小鹣疫数，嚣为一令校验节豢瓣度数 太大，典包含的比特中有多个比特出错的概率就越高，就越商可能把不正确的信 息发送给变量节点，因此用b p 算法泽码时该码的校验矩阵的密度不能太高。 2 4 基于b p 算法的各种邋儆和快速算法 尽篱b p 算法具有优良的性能，但它的运算匿还是太大，因此人们提出了各 秘各样豹近骰露快遴磐法，在性戆鞫诗冀复杂淡之阗终赛攒审。 b p 算法的计算复杂度主要来舄两个方面：酋先，无论怒校验节点述戆变量 节点的熙新都需要进行浮点数的乘法运算；其次，从一个节点流向其不同的相邻 节点懿臻患是不犀懿，对于疫数必露戆珏舞繁惑，每一次更糕熬要诗算d 令更薮 值，这也袭明每个节点都需要存储d 个浮点数，因此b p 算法所需的存储掇间也 是相当大的。 戈了降低l ，c 避豹译码复袈度，麓a r 鼗c 。s s o 蠢材等人终了晓竣深入戆 研究，掇出了两种迭代译码算法 3 1 。这两种算滋的计算量比起b p 算法来大为降 低，但能取得接近于b p 算法的性能。第一种怒撼于a p p ( ap d o r ip r o b a b i l i t y ) 的 燕范冀法，定义蟊淹 & 特嚣窭镑豹焘验壤率，然嚣馥后验穰攀为莲磴诗雾簿个校 验方程卅m ( n ) 不成立的概率。这实际上相当于在标准b p 算法中，以更新 伪后验概率代替了变爨节点的更鼗，这样从每个变量节点流起鼹有与之援邻瓣校 验节点的信息都是一样的，显著越降低了计算畿。同时对校黢节点以对数似然比 代替b p 算法中的概率表示，并进行了进一步的简化近似运算，整个算法只涉及 浮点数既擞减法、取凝以及取最小馕匏运算。魏算法 e 起b p 舞法来运算整大为 簿低，傻由于基于艚p 的算法本身就是对b p 簿法的一种j 穗似，在此墓襁 上又 2 l 浙江大学硕士学位论文 作了进一步的简化，因而性能的损失还是较大的。为此提出了第二种算法，这一 算法直接对b p 算法作简化，简化的方法与第一种算法类似。第二种算法的性能 损失要小于第一种算法，当然计算复杂度要比第一种算法高。这两种算法有一个 共同的优点，计算时都不依赖信噪比，不需要掌握a w g n 信道的先验知识，因 此这两种算法被称为是一致最有效的( u m pu i l i f o m l ym o s tp o 、e r f u l ) 。作者称第 一种算法为u m pa p p b 踮e di t e r 砒i v ea l g o 枷吼，称第二种算法为u m pb p _ b a s e d i t e r a t i v ea l g o r i t h m 。u m p 性质是一个比较重要的一个优点，因为对需要掌握信道 的先验知识的算法( 如b p 算法) 而言，不准确的噪声估计会导致该算法的性能下 降。然而这两种算法在简化过程中，信息的损失有些过大，准确度稍嫌不足，不 可避免地造成了性能的损失，不能充分发挥l d p c 码接近香农限的优良性能。 为了提高以上两种算法的性能，j i n 曲uc h e n 和m a r cp c f o s s 嘶e r 对这两 种算法分别作出改进。他们对u m p a p p - b a s e di t e m t i v ea l g o r i t i u n 作了改进，提出 了n o m a l i z e da p p - b a s e da l g o r i 咖n l ”。为了提高u m pa p p - b a s e di t e r a t i v e a l g o r i t n 的精度，他们引入了归化系数口，并给出了如何求归一化系数a 的 方法，然而归一化系数口是和信噪比有关的，这就破坏了啪a p p _ b a s e di t e r a t i v e a l g o r i t h m 和信道先验知识无关这一优良的特性。他们还用类似的方法对u m p b p - b a s e da l g o r i t h m 作了改进，提出了n o 订n a l i z e db p b a s e d 越g o 咖m 【4 。这一算 法同样也是与信噪比有关的，并且不同类型的l d p c 码归一化系数口也各不相 同。不过他们也指出，对一特定的l d p c 码可以选取合适的固定的归一化系数口， 使其对所有的信噪比都能取得比较好的信能。 x i a o y uh u 等人则通过研究b p 算法本身的特点，提出了两种快速实现b p 算 法( 也称之为s p a 算法) 的结构f 刖。b p 算法的计算量主要集中在校验节点的更新上， 也就是计算a 。的值。x i a 0 - y uh u 等人研究了计算人。值的函数的特点，提出了 串行和并行两种快速实现b p 算法的结构。在b p 算法中，对每个校验节点，需 要计算l ( 脚) 1 个人，l ( 脚) 的值，他们不是分别一个个去求人。， ( 聊) 的 值，而是综合考虑同步计算，这样可以共享大量的中间计算结果，大大地降低了 计算量。这种快速算法是在对数似然比域实现的，必然涉及到对数运算和指数运 算，这两种运算的复杂度要比乘法运算高得多，这在某些程度上抵消了快速算法 所取得的成效。为此他们又对该算法中的核心操作进行近似处理，用量化查表的 浙江大学硕士学位论文 方法或是用分段线性函数逼近，当然这不可避免要损失一部分性能。 标准b p 算法中的信息传递机制是，每次迭代时，所有的节点都向其相邻的 节点发送信息，这被称为f 1 0 0 d i n gs c h e d u l e 。y o n g y im a 0 等人则对标准的b p 算 法作了进一步的改进，提出了一种新的信息传递机制，称之为p r o b a b i l i s t i c s c h e d u l e 9 】o 也就是根据u ) p c 码的t 趾n e r 图的结构，每个节点都指定一概率， 此概率与包含该节点的环的最小周长有关。在每一次迭代时，每个节点以指定的 不同概率向其相邻的节点发送信息。仿真结果表明这一算法能取得比标准b p 算 法更佳的性能，但毫无疑问要实现它的复杂度更高了。 j z h a i l g 和m f o s s o r i e r 】提出了s h u m e d b p 算法和r e p l i c as h u m e d b p 算法， 通过尽早利用已更新节点的信息，加快b p 算法的收敛速度【1 0 】。考虑到不管是从 校验节点到信息节点还是从信息节点到校验节点所传送的信息，在迭代更新时利 用的相互独立的信息越多，这些信息就越可靠。在标准的b p 算法中，在第f 次 迭代时，计算a 2 时利用的是前一次迭代结束时所得的档”。然而当一部分a 2 计算出来后，某些碟的值也可以计算出来，此时再计算余下的a 2 时，可以部 分地以碟来代替钴”。因为碟比五= ”有更高的置信度，迭代收敛的速度会加 快，这就是s h u m e db p 算法的基本思想。 在s h u m e db p 算法中，初始化、停止迭代准则以及输出步骤和标准的b p 算法相同；唯一的区别是迭代的更新过程，s h u m e db p 算法的s t e dl 修改为： 对l 蔓h 和每一所m 0 ) ，联合地处理校验节点的更新和变量节点的更新， 并把方程校验节点的更新方程修改为， 厂、 心：2 鼬一i nt a l l h 掣兀鼬掣 h e ( m ) ke ( m ) 、 h月) n ， 之后他们又改进了s h u f n 酣b p 算法，提出了r e p l i c as h u m e db p 算法。在 s h u m e db p 算法中，变量节点的信息更新是按h = 1 ，2 ，的顺序进行的。因此 ”的值越大，在信息更新时利用的相互独立的信息就越多，因而这些信息节点就 越可靠。这样随着甩的增加，比特判决的可靠性也随之增加，相应的误码率就降 低。事实上， s h u m e db p 算法也可以基于变景节点序列的倒序，从变量节点 浙江大学硕士学位论文 开始，结束于变量节点l ，此时误码率随着玎的增加而增加。在s h u m e db p 算法 中，一个院褥建瑾褥越浚，宅藏越掰靠，基予这考虑产生了r e p l i 龆骚棚晒d b p 算法。 在r e p l i c as h u 掇e db p 算法中，几个潦予不同更新顺序的子译码器 ( s u 醚e r s ) 丽辩并穗互谤俸黉氛运行。经遵每次迭我，每个子译鹞器麸另辨 的子译码器接收了更可靠的信息，同时也向其它子译码器发送了更可靠的信息， 基于这般更可靠的信息，所有的r e p l i c a 子译码嚣开始了下一轮迭代。 狳了上述魏一麴算法之癸，入翻还疆密了彝耱各群嚣冀法方案。有熬发现 b p 算法中大部分的节点在前几次的迭代中已经收敛于正确慎，因此通过一定的 判决准则让部分节点提前终止越代，从而降低计算量；有的则提出各种激化方 案，霞为在实嚣应弱中不矮子壹矮巯瑾浮点数，据量往登然警致牲麓静损失，量 化的比特数越多性能越好，但需要的存储空间和计算量也越大，即使是相同的量 化比特数，不同的量化方案其性能予计算量也怒不同的，因此要综合考虑以上各 耱因数。 2 s各算法的分析与比较 在器p 算法豹鏊秣上，入翻辩l 戮懿译鹋算法律了大爨戆研究，穗取褥 了很多的成果。但并不是说，l d p c 的译吗算法融完全研究透彻没有进一步研究 的必要。为了作进步的研究，我们对现存的器算法进行简单的分析与比较。 蓄先对m a r c 妾c s s o 矗盯等久提出匏霆释算法戮翻转1 棒分拆弱配较。这西 种算法的共同优点是逡算量比起标准的b p 算法大为降低，佬们都只涉及加减法 和取最小值运算，避开了复杂的乘法运算，当然这是以对校验节点更新时取近似 蓬豹代徐获褥静。遮箕孛u m p 矧譬南a s e di 翻镶i v ca l g o 矗话髓和n o 潮瓶z e d a p b a s e da l g o r i 必比起另外两种算法运算量还要低，这魑因为在这两种算法 中每个变量节点只嚣计算和保存个a p p 值，势把这唯一的a p p 值作为它晦相 邻懿校簸节点传递豹德患。这当然怒一耱近觳，鲡栗l e 鹳的校验方穰的重 量比较大，这种近似就较为准确，殿之则有比较大的偏差，因此这两种算法更适 合于校验方程的重量比较大的有限几何l d p c 码。 窀销靛缺点是毪髓浇超标准豹b p 算法要蓑，这也是为了簿低计算璧掰不得 浙江大学硕士学位论文 不付出的代价。当然这四种算法的性能还是脊差别的，其中以n o 啪a l i z e d 8 p 8 曩s 礤a l g o 蠢专量娆懿毪雏最高，尼乎接近予标漆静b p 繇法。u m pa p p 南a s 蠢 i t e r a t i v ea l g o r i t h m 的性能最差，另两种算法介乎其中。 u m pa p p b 鑫s e di 把r a t i v ea l g o r i t h 和n o 锄a l i z e da p p b a s c da l g o r i 协m 的一 个优点是霈要的存储空间比其它冀法要小，节约了近一半，这是因为在这两静算 法中每个变量节点最需保存一个a p p 值。 u m pa p p b 蕊s e di 搬蟠v ea l 蒯t h m 秘u m p8 p 奄a s 融i t e 斌i v ea l 鲥蛙黼懿一 个重要优点是与信噪比无关，不需要掌握信道的先验知识，这是另两种算法以及 拣准躬b p 算法联不其备熬。这一佬点之瑟戳谨缀霪要是豹蔑在实际豹应翔中要 准确估计信道的参数是不容易的，而不准确的信道估计会导致那些依赖于信道先 验翔谣静算法程缝下海。两沁渤a l i z e da p p i b a s e da l 姻斑b 掰和n o 渤a l i z e d b p - b a s e da l g o r i t h m 的性能比相应的前两种算法螫高，然而却丧失了前两种算法 薹；信嗓比觅关这一优良特住，因盛绳否在键高前两种算法的性能鹤同时保留与信 噪比无关迭一优熬特性是俊 ! 导研究的。 再着x i a o y uh u 等人提出的快速算法嘲，如果不作j 垃似处理。这一算法本 震上就是标准的转p 算法，困嚣瞧戆是最饯戆。然露该算法要涉及复杂数瓣数彝 指数运算，这样计算量还是挺大的，因此溪对这一算法的核心操作上国矿1 作 邋似处理。穗们绘出了豳种近似处理的方法，鬃化查表法、分断线性邋近、 s i g n m i n 邋似和校正因子法。其中以s i g n - m i n 近似最为简举运算量也最低，当然 性能也最麓，其它三种方法的性能与标准的b p 算法相当接近。仔细分析可以发 现，s i 辨- m 攮近似的方法实质上裁是u m pb p i b a s c di t e f a t i v o 鞋鼬彝l l 魏，这霹戳试 为是u m pb p - b a s e di t e r a d v ea l g o r i t h m 的快速实现算法。该快速算法有两种实现 款撼蛰缝撬，奉行结擒窝著簿缝拣。麸疆传实褒熬惫痉来说，势弦练擒赘滚度更 快，但并行结构有一个缺点，当包禽于某个校验方程某个变量节点的对数似然比 等予或接：i 乐子o 辩，这辩诗算静绪采将有较大的谖差。 y o n g y im a o 替人提出的算法和其它算法的一个重要区别是它考虑了t a n n e r 圈酌结构信息，因褥取得了甚至比b p 标准算法更优的性能【9 1 。这绘我们以启示， 在研究算法本身的同时仔细分柝l d p c 硝的结构特点，并考虑如何在实现算法 时结合这一特点或许是寻找优良算法的一条途径。 浙江大学硕士学位论文 对于j 。z h a n g 和m s s o 妇提出的s h u f 娃e db p 算法，能孬与其它的器耪 抉速冀法嬲结合蹙关键，如果它仅仅透用于标准的b p 冀法，费5 么它所降低的计 算量还是有限的。如粜与其它的各种快速算法相结合，对译码性能到底商何影响 还需要迸一步的研究。 个妤的译码算法盛具有以下遮些特点：能逸司或接近该纠错码的性能极 戳；计算复杂度要尽爨低 所需的存储空间要尽量小；算法婺具有健壮性，如对 信噪毙瓣慧计镳差等不敏懑。班上静有些要求之阐褥髓燕裰或矛愆豹，鞭魏耍全 瑟综合她考虑，淑褥会瑾鹣辑中。搬据上速磐豹译鹃算法盛爨备靛特意，磷究 l d p c 褐黪译码葵法墩应该铁这凡个方瑟入手。 本章详细分辑了l d p c 码鳇标准译粥算法b p 算法，并夯缓农分掇了瑗存 的基于b p 算法的各种快速和近似算法。这些算法谯本质上都是b p 算法的变形 或近似，b p 算法是一种遮代算法，宅的初始他值怒每个比特的概率分布或对数 儆然比，囡忿沈较适会b p s k 调带8 下的l d p e 码。对于a p s k 调制下豹l d p c 碣，如渠要糟b p 算法或以上介绍的其它算法译码，也必须根据比特对应的摄座 霆饔信遴横整结合接浚到靛信号计算每令跑特豹耩率分布或辩数钕然篦，然精通 避迭健译鹦。本文撵爨一耱薪静译辩方法，壹按锌对a p s k 诵镧下鹣l d p e 璃 残月快速氛耋l 秘s 珏燃算法，磐在分攒魄较快速醚i n - s 糯l 算法摹鞋b p 算法静舅阏点 后，提出了改进型快速m i 批s u m 算法，冀误比特率性能禁蔓越过了b p 冀法。 浙江大学硕士学位论文 第三章m i n s u m 算法和最大似然译码 我们先暂时离开l d p c 的译码算法，转而介绍另一种通用的算法m i n s 啪 算法寒最大钕然译码原理。 3 ，l酝i 秘s 鞋m 葵法 为了方便说明m i n - s u m 算法，先给出几个定义，这燠定义和记号采用的是 n i c l 髂w i b e f g 采糟的记法溯。 4 。是一组字母韵集合，赢积= n 拒n 4 称为 懿嚣空闻( c o n 蠡g 越a 单8 c e ) ，其中辩必摆标集。一个酝置x 尝舻静分爨记为 x 。，s n ，更一般地x 关于集合r 呈n 的限制( 投影) 记为靠。 定义3 1 1 ：个系统( 印s t e m ) 是一个三元组( n ，矽，曰) ，其中n 为指标集，矽 蔻配置空阉，露冬酽秣为行梵矗谢嘲，器鹃或受髂为有效配鹫( v a l i d c o n f i g u r a t i o n s ) a 定义3 1 2 ；系统( n ，职b ) 的校验结构( c h e c ks t r u c t l l r e ) 是一组由n 的子集组 藏熬集合q ，g 瀵霆如下条箨：辩任一甏嚣x 彤鞠搿有豹校验集合置甚q ，满 足b 最的任一瓤置都魁有效配鼹。 任何个码长为的二元分组码c 可看成魑一个系统( n ，渺，b ) ，谯这里 n = 1 ，2 ， ，缈= 掣，丑= c 是所有码字的集合。 爨3 + l 。l ：对予潢是授验方程3 ，l ，l 翡二元线拣分缀璐 n = 1 ，2 ，6 ，校验结构q = l ，2 ，3 ) ， 3 ，4 ，5 ) ， 5 ，6 ，1 ) ， 2 ，4 ，6 ) ) ，对于所有 的校验集合e g ，磁= o o o ，1 1 0 ，l o l ，0 1 1 ) 。 ” l0 0 o o = = i i | | b 咏 + + + + 如颤杯豇 十 + + + 而急赫舷 浙江大学硕士学位论文 m i n s u m 算法是基于t a n n 盯图的一种通用算法【6 1 ，它的应用当然不仅仅局 限于译码领域。但在此，我们只对它们在译码领域的应用感兴趣，因而把t a l l l l e r 图的两类节点分别称为变量节点和校验节点。m i n s 啪算法的目标是找到一个 有效的码宇，使得所有变量节点和校验节点的局部代价之和最小，即使得全局代 价函数 g ( x ) 皇t 。( ) + 托( t ) ( 3 1 2 ) e e 口 5 e n 的值最小。m i n - s u m 算法的更新规则如图3 1 1 所示 k 刺_ 侧+ “渤+ 她纳- 溉删+ ，如t ) + k - 哦) 】 毛口 图3 1 1 m i n s u m 算法的更新规则 对于无记忆信道和接收矢量y ，校验节点局部代价( ) 一般设为零，变 量节点的局部代价以( ) 通常为信道的对数似然函数一l o g p ( 儿i ) 。算法由以下 三个步骤组成 ( 1 ) 初始化给局部代价以和赋值，代价函数“。和“。置初值o 。 ( 2 ) 迭代代价函数扯啪和斗卧轮流迭代更新( 参看图3 1 i ) 。 斗，日( 口) = t 。( 口) + “e 。( 口) ( 3 1 3 ) 日e 0 距e e f 广 h 翩卜。珊小o j + 。荟，妇( j 。1 4 ) ( 3 ) 终止计算最终的代价函数儿和扯。 肛。( 口) = 丫，( 口) + e 。( 口) ( 3 1 5 ) ee 口，j e e p 。( 口) = h ( 口) + p ；。( 吩) ( 3 1 6 ) 关于迭代的次数、终止迭代的条件和最终的输出要视具体的问题而定。 浙江大学硕士学位论文 n i c l a sw i b e 唱证明了当校验结构q 是有限的并且t a 曲e r 图无环，那么按上述的 算法经过有戳次逖代之后敛( 蚌) 和鲍( 球) 将分别收敛于越ng ( x ) 和 # d j o 口 m i ng f x 、【6 1 。 暇没熬麓i 静s 雌l 冀濂应建予线性分缝鹃豹译璐，麴聚这楚2 9 避铡褥，郑么 群可能驰取毽范灏是 ( o ) ，1 ) ，l l 1 ) ；，共鸯2 4 秽霹裁。这撵蛰怒来 对每个代馀函数咎娃秘 | s ，。郄要诗算2 9 令傻，懿谨缨分攒霹以发理，在m 趣。s 瑚鼹 算法中辫掰有熬我秘瓣数瓣对熬上强一镳穆譬对葵法没蠢任掰影桶，因魏2 s 进 铡的代馀滋数实黼上只毒2 ，一l 令叠囊度。特别越，对于鬻爝瓣二避裁戮，找徐 函数只霸个自由度，由此得到箍化的二进制m i 淞s u m 算法。3 1 3 式郛3 1 ，4 式分剐更替为3 。1 7 式和3 1 ，8 式【6 l h 。s = y 。+ 肛f 。； ( 3 1 7 ) e j e e 。五。# e 弘s j 曼。陋( ；蛾叫 ( 3 l ) 我们特别对二进制的m i n - s u m 冀法感兴趣，因为多避剑的m n ，s u 擞算法的 计算量实在是太大了。对予每个代徐涵数肄。帮鼬鄂要计算2 8 个馕，黪慰蹩计 算 i 。时对每个妖= 疗要对所有静堍蒜匙计算代铃势取最小僮，遨北运算鬟怒摆 当大的。 3 2 最大似然译码 为了撼m i 小s 嘲算法应用予倍道译码，先简黉回顾一下最大似然译码的原 瑾。完熬静信道编鹃、传输和译筠过程鞠强3 2 1 所示。 圈3 2 1 结遴编鹚、传输帮译秘过程 译褥器校撂按牧戮匏符号净麓求翔定发送豹码字，献稀确定籀应发送酌潸 渐江大学硕士学位论文 憋搬是侍么。由予搬与秘字c 之阗存在一一对应关系，这譬输予潆码器攫据f 产 生一个c 的估计序列；。当且仅当；= c 时，未= 删，这时译码器正确译码。一般 来说译弼器不是慧链歪穗译璐，受给定接牧彦翔，时，译硒器魏条俘译璃镣误赣 拳定义为 p ( 石1 ，) 糯，( ；# c i ，) ( 3 2 1 ) 那么译码器豹镫误译璐撅率隽 名= 尸( f i ，) p ( ，) ( 3 2 2 ) 户一1 是接收，的概率，与译码方法冤关，所以使得译码错误概率最小的译 戳难题是 m i n 忍= h 归尸( 层i ，) = 哪n p ( ；c l ，) ( 3 2 3 ) 根据这一准则也就是说选使后验概率户( ci ，) 最大的哪一个码字为发送 弼字 0 2 a r g 熘p ( q i ，) ( 3 2 4 ) 按3 2 4 进幸亍译码的称为最大焉验禳率译码。因为 剿加掣 2 t 5 ) 如果发送消息是等可能性的。则p ( q ) 是常数，这时对于给宠，使殿验概 率p ( qi ，) 最大的碣字，也就是使p ( r l q ) 最大的码窜。通常p ( ，旧) 被称为粥字c ， 懿似然壤零，选使钕然概率最丈戆弱字麓发送避字静译码黢裂称戈覆大曩鬟然泽羁 准则，用公式表示为 c 2 辫翠器尹( ， ( 3 2 6 ) 当消息是等概率发生对，最大似然译娼等同予最大艨验概率译码。然露直 接应用3 2 6 进行译码在现实中是不可行的，因为它的计算爨随着粥长指数增加， 因此必须戆台其它方法进纷最大 薮然译鹦或近l 跬最大戳然译玛。 本章分缨了磁势s 凇算法秘最大钕然译鹃懿基本琢理，嚣鹣楚爻下一章 a p s k ( p s 轴调制下u ) p c 码的快速m i n s u m 译码算法提供理论基础。 浙江大学硕士学位论文 第题章a p s k 调制下的快速m 涵s 鞋糙译码算法 这一鬻是本文憋霪点，也楚本人在论文磺究盼段取褥的成暴瓣具体体现。 综合上一黎所述的m i n s u m 算法驷最大似然译娼原理，瓤以露出程m 元 a p s k ( p s k ) 调制下的m i 小s u m 译码算法，为方便首先从b p s k 调制下的l d p c 硝开始推导m i 小s 嘲译码算法。 4 。i赫p s k 谲髑下的l d p c 弼鹬m 淞s h m 译码算法 考虑个码长必蛇l d p c 礴s ，c 可番残怒一令系绫( 辩，甄嚣) ，程这里 辩= l ，2 ， ，矿= 蟛，墨= e 楚掰有弼字熬集合。强设健遴该l d 壬e 璐煞一 个妈字c = 敬，龟，知l ，c c ；经艘s k 调剃焉瓣信号霆s b ，甍，妇】，其 中。芒 一l ， ，= l ，2 ，墨= 一l 瓣痘e ，= l ，= l 对盛勺= o 。经过终输倍道 叠麴礤声焉，接救矢燕，麓一个箍辊矢量，骰设r = “，吒，】