北邮信息论课件-第7章 有噪信道编码

1、第第7章章 有噪信道编码有噪信道编码信息与通信工程学院许文俊2/66第第7章章 有噪信道编码有噪信道编码 本章主要内容：本章主要内容： 1.概述概述 2.常用译码准则常用译码准则 3.费诺费诺(Fano)不等式不等式 4.序列的最佳译码准则序列的最佳译码准则 5.有噪信道编码定理有噪信道编码定理 3/66 7.1 7.1 概述概述 为为提高传输的可靠性提高传输的可靠性，必须进行，必须进行信道编码信道编码。 信道编码就是按一定的规则给信源输出序列增加某些冗余信道编码就是按一定的规则给信源输出序列增加某些冗余 符号，使其变成满足一定数学规律的码序列（或符号，使其变成满足一定数学规律的码序列（或 码

2、字），码字）， 再经信道进行传输。（再经信道进行传输。（注意：与信源编码比较注意：与信源编码比较）l 信道译码就是按与编码器同样的数学规律去掉接收序列中信道译码就是按与编码器同样的数学规律去掉接收序列中 的冗余符号的冗余符号, 恢复信源消息序列。恢复信源消息序列。 l 一般地说，所加的冗余符号越多，纠错能力就越强，但传一般地说，所加的冗余符号越多，纠错能力就越强，但传 输效率降低。因此在输效率降低。因此在信道编码中明显体现了传输有效性与信道编码中明显体现了传输有效性与 可靠性的矛盾可靠性的矛盾。l 在数据在数据 传输传输 系统中译码过程总要比编码过程复杂系统中译码过程总要比编码过程复杂,这样采

3、这样采 用的译码算法对系统的性能影响很大。用的译码算法对系统的性能影响很大。4/66 本节主要内容：本节主要内容： 1. 1. 错误概率错误概率 2. 2. 译码（判决）规则译码（判决）规则5/667.1.1 7.1.1 错误概率错误概率 两种错误概率的描述：误码率和误字率。两种错误概率的描述：误码率和误字率。 误码率误码率是指传输码元出错概率（对二进制也称误比特率）是指传输码元出错概率（对二进制也称误比特率）. . 误字率是指码字出错概率。误字率是指码字出错概率。 一个码字一般由多个码元构成，任何一个或多个码元出错一个码字一般由多个码元构成，任何一个或多个码元出错 都使得码字出错。都使得码字

4、出错。 所以对同一通信系统，所以对同一通信系统，误字率总比误码率高误字率总比误码率高。 错误概率的大小与信噪比大小有关。错误概率的大小与信噪比大小有关。 信噪比大，则错误概率小；信噪比大，则错误概率小； 反之信噪比小，则错误概率大。反之信噪比小，则错误概率大。 错误概率还与译码规则的选择有关。错误概率还与译码规则的选择有关。 适当地选择译码规则使平均错误概率最小是提高传输可靠适当地选择译码规则使平均错误概率最小是提高传输可靠 性的重要措施之一性的重要措施之一。6/667.1.2 译码（判决）规则译码（判决）规则1.单符号译码规则设信道的输入与输出分别为X和Y， ，分别取自符号集A和B，且 ，

5、定义译码（判决）规则为 对于所有 （7.1.1） 含义：当接收到 就判定发送符号是 因此， 每一个信道输出都必须有一个信道输入与之对应。 所以译码（判决）规则是一个有唯一结果的函数。,xX yY12 ,rAa aa12 ,sBb bb(),jiF yba1, ,1,ir jsjbia7/662错误概率的计算错误概率的计算设信道的转移概率为 ，采用的译码规则为： 对于所有 （7.1.2）（7.1.2）式可简记为 。在接收到 的条件下，若实际上发送的是 ，则译码正确，反之就出现差错。因此满足译码规则（7.1.2）的条件错误率为： /(|)Y XjiijPybxap*(),jF yba1, ,1,i

6、r js*( )F yxjb*a*/(|)iX YijaaPxayb8/66正确率为 ：所以平均错误率为： （7.1.3）（7.1.3）式的含义是，如果输出y与未被y作为译码结果的输入同时出现就属于译码错误。 还可计算平均正确率为 （7.1.4） */(|)X YjPxayb*/()(|)iEYjX YijjaaPP ybPxa yb*( )( /)yx xp yp x y*1()yp x y)(1*yEEyxpPP9/667.27.2常用译码准则常用译码准则 为提高可靠性，所采用的译码准则都应该使为提高可靠性，所采用的译码准则都应该使平均平均错误概率最小错误概率最小。最常用的就是。最常用的就

7、是最大后验概率译码准则最大后验概率译码准则和和最大似然译码准则最大似然译码准则。本节主要内容：本节主要内容： 1. 1. 最大后验概率译码准则最大后验概率译码准则 2. 2. 最大似然译码准则最大似然译码准则10/667.2.1 最大后验概率译码准则最大后验概率译码准则对所有 i，当满足 （7.2.1）时，则选择译码函数为F(y)=a*，称此准则为最大后验概率 (MAP，Maximum a Posteriori) 准则。MAP准则就是将具有最大后验概率的信道输入符号 作为译码输出。由（7.2.1）式，得)()|()()()|()(*ypaxypaxpypaxypaxpii*(| )(| )ip

8、 xayp xay11/66所以 ，对所有 i，当 （7.2.2）时，则选择译码函数为F(y)=a*。其中， 为似然比，（7.2.2）式表示的是似然比检验。可见，MAP准则可归结为似然比检验。 MAP准则是使平均错误最小的准则, 原因： )()()|()|(*axpaxpaxypaxypii*( |) ()( |) ()iip y xap xap y xa p xa*(, )(, )ip xayp xa y*1()EyPp x y 12/667.2.2 最大似然译码准则最大似然译码准则若输入符号等概，即 p(ai)=1/r 时， （7.2.2）变为：对所有 i, 当 （7.2.3）则选择译码函

9、数为 F(y)=a*，称此准则为最大似然译码准则。注：注：1）当）当输入符号等概或先验概率未知时输入符号等概或先验概率未知时，采用此准则。，采用此准则。 2）当）当输入符号等概时输入符号等概时，最大似然准则等价于最大后验概，最大似然准则等价于最大后验概 率准则。率准则。)|()|(*iaxypaxyp13/66例例7.2.1设信道输入X取值为(a1,a2,a3), 信道输出Y取值为(b1,b2,b3)，转移概率矩阵如下 求利用最大似然（ML）译码准则的判决函数。解解 : 每个输出符号给定，当 y=b1时， p(y/ a1)=0.5, p(y/ a2)=0.2, p(y/ a3)=0.3 ，利用

10、（7.2.3），得判决函数, F(b1)=a1， 同理得其它最大似然判决函数：F(b2)=a3（或F(b2)=a1或F(b2)=a2），F(b3)=a2。0.50.30.20.20.30.50.30.30.414/66两种准则使用要点：两种准则使用要点：1MAP准则准则 i）由转移概率矩阵的每行分别乘 p(x)，得到联合概率矩阵； ii）对于每一列（相当于 y 固定）找一个最大的概率对应的 x 作为译码结果； iii）所有译码结果所对应的联合概率的和为正确概率, 其他矩阵元素的和为错误概率。2ML准则准则 i）对转移概率矩阵中每列选择最大的一个元素对应的x作为译码结果； ii）输入符号等概时，

11、所有译码结果所对应的转移概率的和再乘以 1/r 为 正确概率，其他矩阵元素的和再乘以1/r为错误概率。15/66例例7.2.1（续） 求最大似然准则的错误率。解：解： 错误率 PE=1-(0.5+0.3+0.5)/3=0.5667。16/66例例7.2.2 已知信道的转移概率矩阵为现有两种译码规则：规则A： 规则B：设输入等概，求两种译码规则的错误率。1/21/31/61/61/21/31/31/61/2111222333()()()F ybaF ybaF yba111223332()()()F ybaF ybaF yba17/66解：解：设判决函数为 ，根据（7.1.3），得 *( )F y

12、a*( )( |)/3Eya apAp y xa 3/)3/ 16/ 1 () 6/ 13/ 1 () 3/ 16/ 1(2/1*( )( |)/3Eya apBp y xa 3/)2/ 16/ 1 () 2/ 13/ 1 () 3/ 16/ 1(3/218/667.3费诺费诺(Fano)不等式不等式 主要内容：主要内容： 1. 信道疑义度信道疑义度 2. 费诺费诺(Fano)不等式不等式 3. 序列费诺序列费诺(Fano)不等式不等式 19/667.3.1信道疑义度设信道的输入与输出分别为X、Y，定义条件熵H(X|Y)为信道疑义度。它包含如下含义：1）信道疑义度表示接收到 Y 条件下X的平均

13、不确定性；2）根据 I(X;Y)=H(X)-H(X|Y)，信道疑义度又表示X经信道传输信息量的损失；3）接收的不确定性由信道噪声引起，在无噪情况下，H(X|Y)=0。20/667.3.2费诺费诺(Fano)不等式不等式设信道的输入与输出分别为 X、Y，输入符号的数目为r，那么信道疑义度满足 （731）其中， 为平均错误率。证：证：设译码规则由（7.1.2）确定，那么(| )()log(1)EEH X YH pprEp(|)()log(1)EEH X YH ppr( )log ( | )log(1)log(1)(1)EEEEExyp xyp x yppppp log r 21/66上式=yxxE

14、yxxrpxypyxpxyp*1log)()|(log)(*()log (| )()log(1)Eyyp x yp xyp x yp*1( )log()log(1) ( | )(| )EEyyx xppp x yp x yrp x yp xy*1()1() 1(log )(1) ( | )(| )EEyyx xppp xyp x yerp x yp xy *( )( , )(1) ( )()(log )(1)EEyyyyx xx xpp yp x yp p yp x yer0)1 ()1 (EEEEpppp22/66当下面两个条件同时成立时，等号成立：当下面两个条件同时成立时，等号成立：i）

15、ii） 上面条件表明，当上面条件表明，当y给定后判决错误的概率给定后判决错误的概率 相等时相等时，不等式取等号。证毕。，不等式取等号。证毕。10( | )(1) ( | )1EEx xppp x yrp x yr EEpyxpyxpp1)|(01)|(1*23/66注释：注释：i）无论什么译码规则，费诺不等式成立；译码规则变化只会改变pE的值；ii）信道疑义度由信源、信道及译码规则所限定；因为信源决定p(x)，r，而p(x)，p(y|x)及译码规则决定pE iii）对不等式的含义的理解：当接收到Y后，关于 X 平均不确定性的解除可以分成两步来实现： 第 1步是确定传输是否有错， 解除这种不确定

16、性所需信息量为 H(pE)；第2步是当确定传输出错后，究竟是哪一个错解除这种不确定性所需最大信息量是log(r-1)。24/66 图7.3.1费诺不等式示意图图图7.3.17.3.1为费诺不等式示意图。图中，曲线下面的区为费诺不等式示意图。图中，曲线下面的区域为信道疑义度被限定的区域。现求曲线的极大值。域为信道疑义度被限定的区域。现求曲线的极大值。25/66仅当 即 时等式成立。由于 当 时，有 。)1log()(rppHEEEEEEppprp11log)1 (1logEEppr111rrpE11Ep1Ep()log(1)log(1)EEH pprr11log(1)log1EEEErpprpp

17、26/667.3.3 序列费诺序列费诺(Fano)不等式不等式 (教材无)若信道的输入与输出为多维随机变量 和 ，定义 （732）其中， 是第 个符号出错的概率，则 Fano不等式成立： （733）其中r为输入符号集中元素的个数。LXLYLlEElpLp11lEpl1(|)()log(1)LLEEH XYHpprL 27/66证：证：利用引理4，有 利用（731）式，有 ) 1log()()|(rppHYXHllEEllLlELlELlllLLrpLpHLYXHLYXHLll111) 1log(1)(1)|(1)|(1) 1log(11rppLHLlEEl) 1log()(rppHEE1(|)

18、(|)lLLLllH XYH XY28/667.4序列的最佳译码准则序列的最佳译码准则 主要内容：主要内容： 1. 汉明距离 2. 序列最大似然译码 29/667.4.1 汉明距离汉明距离设两码字为 ，定义它们的汉明距离为 （7.4. 1）其中， 为模二加运算。例如，码字 和码字 的汉明距离为6。一个码字集合中任意两码的汉明距离最小值，称为码的最小距离，用dmin来表示。 ,.,.,11nnyyyxxx1( , )nkkkd x yxy 1101110 x1010001y30/667.4.2 序列最大似然译码序列最大似然译码 设信道的输入与输出分别为多维随机矢量集合： ， 其中，序列 ； 分别

19、取自符号集A和B，且 ， ，其中 ， ， 。 1,nnXXX1,nnYYYnnXxxx,.,1nnYyyy,.,1,iiiixXyY12 ,rAa aa12 ,sBb bbnkAnlB1,nkr1,nls31/66如果对于所有k，满足（7.4.2）那么就选择译码函数为 ，称为序列的最大似然译码准则。转移概率 称为似然函数。与单符号情况相同，当消息序列等概或概率未知时用最大似然译码准则。( | )p y x *( |)( |)kp y xp y x*)(yF32/66定理定理7.4.1 对于对于无记忆二元对称信道无记忆二元对称信道，最大似然译，最大似然译码准则等价于最小汉明距离准则码准则等价于最

20、小汉明距离准则。证：证： 设信道的输入与输出分别为序列 ，似然函数为 （7.4.3）设 的汉明距离为 ，如果 出错，那么 与 不同，从而使汉明距离增加1。又根据二元对称信道的特性，有 其中 ，所以（7.4.3）式变为 ,.,1nxxx ,.,1nyyy 1( | )(|)niiip y xp yx yx,dixiyix(|)1iiiiiipxyp yxpxy1/2p ( | )(1)n ddp y xpp 33/66取对数，得 （7.4.4）因为 n 是定值，当信道固定后，p也是定值 ，而又有 ，所以， 当 d 最小时可使（7.4.4）的值最大。这样对于固定的 ，选择的所有可能的输入序列，将与

21、 汉明距离最小的序列x作为译码输出，这种译码方法也称为最小汉明距离准则。证毕。 log ( | )log(1)log/(1)p y xnpdpp 1/2p yy34/66例例7.4.1 对等概信源符号0和1进行重复码编码，对应的码字为 000，111； 编码序列通过错误概率为 p （1/2）的二元对称信道传输， 接收端利用最大似然译码准则；求译码错误率pE。解：解：此时可利用最小汉明距离准则。二元对称信道三次扩展信道转移矩阵为： YX 000001010011100101110111000(1-p)3(1-p)2p(1-p)2p(1-p)p2(1-p)2p(1-p)p2(1-p)p2 p311

22、1 p3(1-p)p2(1-p)p2(1-p)2p(1-p)p2(1-p)2p(1-p)2p(1-p)3判决 000 000 000 111 000 111 11111135/66分别计算 y 的每一个可能序列与 000 和 111的汉明距离， 将汉明距离小的输入序列作为译码输出。例如，接收为010，与 000的距离为1，而和111的距离为2，所以译码输出为 000； 依次类推，得到表中的下面一行。通过计算，得正确率：1-pE=(1-p)3+3(1-p)2p， 错误率： pE =p3+3(1-p)p2。36/66vP133 例7.3vP134 (n,k)线性分组码的码率vP135 例7.5vP

23、136 定理7.2 例7.637/66 7.5有噪信道编码定理有噪信道编码定理 设有一离散无记忆平稳信道的容量为设有一离散无记忆平稳信道的容量为C，则只要信，则只要信息传输率息传输率 RC时，对任何编码方式，译码差错率大于时，对任何编码方式，译码差错率大于0。（香农第二定理香农第二定理)(与香农第一定理的比较，与香农第一定理的比较， P93) 定理的证明见附录定理的证明见附录.下面重点对定理的含义进行说下面重点对定理的含义进行说明。明。 38/66 图 7.5.1为编码器与信道模型图， 这里考虑的是分组信道编码。假定由信源发出 M 个等概率信息，经信道编码后生成M个码字，其中码符号集的大小为r

24、，码长为n；生成的 n 长码字 为信道输入，n长序列 为信道输出。xy 图7.5.1编码器与信道模型图39/66说明：1信息传输速率为 R=(logM)/n ，表示每个码符号携带的信息量。2随机编码：独立、随机地从r n种信号序列中选取M个长度为n的序列，组成码字集合。每次选择允许重复， 则选择的码字集合种类数有 rnM，每种码被选择的概率为r-nM。而且 对于每一个 n 长序列中的每一个符号也按概率独立选取。 这种编码方式称随机编码（注意“随机”仅指选择方式“随机”，当选择后，码集合便确定）。3. 译码准则：采用最大似然译码准则，或其它译码准则，例如联合典型序列译码。( |)max ( |)

25、( )kikip y xp y xF yx 40/664. 译码平均错误率 pE 的估计：由于寻找最佳，即 pE 最小时的编码很困难，所以采用求 的方法，即对所有的随机编码进行平均若 时， 任意小，那么至少有一种编码满足要求。5. 定理仅指出编码的存在性，并未给出编码的具体方法。6. 定理的意义该定理纠正了人们认为的提高可靠性必须要降低 有效性的传统的观念， 提出高效（接近容量）和高可靠性的编码是存在的， 为信道编码理论和技术的研究指明Ep)(CECEpEp nEp41/66了方向。定理给出了信道编码的理想极限性能，是信道编码理论的基础。7. 寻找最佳信道编码的困难1) 要求编码序列足够长，“

26、难实现”；2） 很大，“难寻找”；3）采用随机编码，“难分析”。8. 信道容量是进行可靠传输的最大信息传输速率。nMr42/66 有噪信道编码定理的证明有噪信道编码定理的证明1正定理证明正定理证明证证: 利用联合典型序列的方法证明。设离散无记忆平稳信道的转移概率为 ，输入与输出分别为序列 和 ，n 为序列长度；达到信道容量的输入概率为 ，信道输出为 ，输入与输出的联合概率为 ， 设输入/ 输出序列 : ，并设 为序列中 取值 ijijp,.,1nxxx ,.,1nyyy ()kiP xip1kn()kiijiP yjp p()kkiijP x yijp p1 122,nnxyx y x yx

27、y ijnkkx y43/66的数目。我们有 (7.5.1)如果 ，对每个 ，那么就称 为 典型序列。对任何 典型序列 ，有 (7.5.2) 设 为输入序列中取值 i 的符号数，那么 ,()()ijniiji jp xyp p (1)ijiijnnp p, i jxy xy ,log ()(1)log()()(1)iijiiji jp xyp pp pH XYn in(1)(1)iijiijijjnnnp pnp44/66所以，如果 是 典型序列，那么 也是 典型序列。同理，如果 是 典型序列，那么 也是 典型序列。对于 典型序列 ，有下面的关系： (7.5.3) (7.5.4) (7.5.5

28、)对每个 典型序列 ，定义使得 为 典型序列的的 集合为 。如果 不是 典型序列，那么 为空集。对于 典型序列 ，根据(7.5.5)、(7.5.3)，有 ，xy xxy yxy ()(1)()2nH XYp xy ()(1)( )2nH Xp x()(1)( )2nH Yp y yxy xyFyyFxy ()(1)( )2nH Yp y ()(1)()2nH XYp xy 45/66所以 。设 中元素的个数为 ，则所以 (7.5.6)下面，我们选择一种由M个输入序列 （每个序列的长度为 n）组成的码。 并随机地选择每个序列中的每一个符号,且每个符号的概率使信道达到容量。译码原则采用仙农提出的“

29、典型序列”原则： 给定一接收序列 ，选择唯一的消息 ，使得码字 在 中。如果 中不包含任何码字或包含多于一个的码字，就拒绝译码，此时译码出错。如果编码器的输入是消息 ，那么仅当 不是典型()(1)()(1)( / )2nH XYnH Yp x yyFyFyF()(1)( )(1)1( | ) |2nH XYnH Yyxp x yF 12,Mx xx ymmxyFyFmmx y ()(1)( )(1)2nH XYnH Y46/66序列（即 不是典型序列或 ） 或对任何其它码字 ，有 时，译码出错。设 为 典型序列 的集合，在随机编码集合中，错误概率不依赖于消息m，并且序列集合 的每一个元素 都独

30、立地以概率 选取， 所以错误率的上界为 (7.5.7) 除发送码字 之外的每个其它码字独立于接收序列而每个 典型序列 的概率最大为 ，因此利用(7.5.6)，其中 ，得 (7.5.8) ymyxFmymxFTxy nnmX Ykkx yiijp p( ) (1( ) (1) ()nymP EP TMP XF nmXnYnmX()(1)2nH X()nymP XF ()(1)2nH X(/ )()( )2n H X YH XYH Y ( )()( )2n CH XH XYH Y( )max()(|)p xCH XH X Y47/66信息传输速率为 （比特/符号）。如果 ,那么 ，(7.5.7)

31、中 M-1 用 M 代替，得 (7.5.9)选择 ,那么(7.5.9)变为:对于任何 ，我们选择n足够大，使得且 ，那么对于足够大的n，有 。因为这对于在所有码集合中平均都成立，所以至少存在一种编码使结论成立。这里的错误概率是误字率，而误符号率不大于误字率，所以只要没有错误传播，误符号率就会任意小。 2()/Rlog MnRC0CR( )(1()P EP T()()( )2nH XH XYH Y /2()()( )H XH XYH Y/2( )(1()2nP EP T0()1/2P T /22/2n( )P E48/662逆定理的证明逆定理的证明当信息传输率 RC 时，传输错误率必大于0。证证

32、: 仍然证明 DMC 情况。 对于图7.5.1，由数据处理定理有， ，因为信道无记忆 ,所以 ，即:根据 Fano 不等式，有 (7.5.10)将 ，代入(7.5.10)，得 (7.5.11);();(nnLLYXIVUInCYXInn);(nCVUILL);(nCVUHUHLLL)|()()1log()()|()(rppHLVUHnCUHEELLL()( )LLHULH U)1log()()(rppHLnCULHEEL)1log()()(rppHNLCUHNLEEL49/66这里 为信息传输速率。当时,(7.5.11)的右边大于零，所以 不为0，即出现译码差错)(UHNLRL0)(CUHNL

33、LEp50/66无失真信源信道编码定理v（信源信道编码定理）设有一离散无记忆平稳信道的每秒容量为C，一个离散信源每秒的熵为H，那么，如果HC时，对任何编码系统，译码差错率p0。(P144,例7.9)51/66 7. 6 接近信道编码性能界限的编码接近信道编码性能界限的编码 l Turbo 码l LDPC码7.6.1 Turbo 码 l Berrou等人于1993年提出； l 信道编码理论研究的重要里程碑；1. Turbo 码性能: l 在AWGN信道； l BPSK调制的1/2码率； l 采用65536的随机交织器； l 18次迭代译码； l 在误码率 时； l 所需信噪比为（突破了截止速率的

34、2.5dB,也远低于级联码所需的1.6dB，仙农限为0 dB）510eP52/662. Turbo 码的编译码原理l 卷积码与随机交织器巧妙地结合，实现了随机编码的思想；l 采用软输出迭代译码来逼近最大似然译码。l 编码器：两个并联系统卷积码的输入之间采用随机交织器l 框图如图7.6.1： 图7.6.1 Turbo 码编码器框图53/66 l 编码器工作原理: * 信息序列u经过一个N位交织器，形成新序列u1； * u与u1分别进入两个分量编码器（RSC1和RSC2） （两个分量编码器结构相同），生成序列x1和x2； * x1和x2经过删余（凿孔）器，周期性的删除一些校验位， 形成校验序列x；

35、 * u与x经过复用生成Turbo 码序列x。54/66l 译码器工作原理:* 译码器基本结构如图7.6.2，两个软输入软输出译码器 DEC1，DEC2经交织器串联构成。 图7.6.2 Turbo 码译码器框图55/66 * 交织器与编码器中使用相同； * 译码迭代过程： DEC1对最佳RSC1译码，产生u中的似然信息，并将其中的新信息经交织器送到DEC2； DEC2将此信息作为先验信息，对RSC2最佳译码，产生交织后的似然比信息，并将其中的外信息经解交织器送到DEC1。 * 经多次迭代后，进行硬判决，得到信息估计序列。 56/66l 交织器* 目的： 尽量随机地重新分配突发错误，使信息位之间

36、的 相关性降低使编码后码字的距离谱细化，改变码字的距离特性 * 常用交织器：Cyclic-T，Random-T，S-random等l 常用算法：MAP（最大后验概率）算法：SOVA（软输出Viterbi算法）算法3Turbo 码的缺点： 当信噪比很大时，译码错误率趋于平缓（地板效应）4Turbo 码的应用l 由美国空间数据系统顾问委员会作为深空通信标准；l 第三代移动通信系统（IMT-2000）的数据信道编码方案： WCDMA，cdma2000，TD-SCDMA57/66 7. 6. 2 LDPC码码1LDPC码的性能 l 低密度奇偶校验(LDPC：low density parity che

37、ck)码是由Gallager 于1962 年提出； l Turbo 码只是LDPC 码的一个特例，译码算法具有等价性； l LDPC 码具有许多比Turbo 码更优良的特性： * 纠错性能优于Turbo 码，更接近Shannon限： 码长为10,000的非规则的LDPC码距Shannon限有0.3dB，Chung5 等人又发现非规则二进制的LDPC码在码长N107、码率R1/2、AWGN信道，与仙农限几乎相等，仅差0.0045dB，远远超过了Turbo码的性能。 * 具有优异的分组码纠错性能。 * 译码复杂度低，是时间的线性函数。 * 可并行译码 * 无地板效应，最小码距正比于码字的长度。 5

38、8/662 LDPC码的结构l LDPC码的检验矩阵H与普通的分组码的校验矩阵不同，H的每行和每列中1的个数很少，即1的密度很小以期望得到较大的最小码距dmin（这也是LDPC码名称的由来）；l 分为规则码和不规则码（Gallager最初提出为规则LDPC码）； l 规定规则（n, k）LDPC码的校验矩阵每列有wc个1，每行有wr=wc(n/m)个1，其中m=n-k，并且wcm，即行向量中1的个数也远小于零的个数，从上面的结果还可以推出wrn，即行中1的个数也远小于零的个数。Gallager指出只有wc3才能构造出好的码字；l 如果H中各行和各列中1的个数不固定，则其对应的LDPC码为非规则

39、的；l 理论证明，非规则的LDPC的性能优于规则的LDPC码。 59/66l简单的实例： 1100000001100000101110000001000001010010H60/66例761 LDPC码的校验矩阵H的确定。 列中1的个数wc=3，对于H中的任意两列，1在列中同一 位置出现的次数（即两个列向量1的位置交叠的次数）最多 为一次。在图中所示的部分H中，可以看出任何一组列向量 对应元素求和得到的新的向量都不会为零。上述这些特性保 证了LDPC码具有较大的最小码距dmin。与传统的分组码相同， LDPC码的生成矩阵G可同对H进行变换得到，若H=PT I ， 则G= I P。61/663L

40、DPC码构造方法： l 最直接的方法是构造具有上述特性的低密度奇偶校 验矩阵H； l 随机地生成全零的矩阵H，然后随机地将矩阵中每 列的wc个元素变为1，这样产生的LDPC码可能是非 规则的； l 随机地产生重量为wc的列向量，并以这些列向量为 列组成矩阵H，并尽可能使H的行向量重量相同； l 随机生成的矩阵H每列1的个数为wc，每行1的个数为 wr，1在列中同一位置出现的次数至多为一次； l 应该保证H为满秩矩阵。62/664 LDPC的编码 l 如果构造出了矩阵H，就可以通过变换得到 LDPC码的生成矩阵G，G= I P； l 若原始信息序列为u，编码后序列为c，则进行线 性运算c=uG= I P= u uP就可以完成编码； l 需