信道编码第6章

1、第六章第六章 LDPC 编码编码介绍了LDPC 码的定义、分类Tanner 图表示；对其编码和译码方法进行了简单的讨论一、一、LDPC 码概述码概述1、 LDPC码历史码历史Robert Gallager 1960 年在MIT Ph. D. 论文中提出，当时由于1. 计算量大2. RS码的引入3. RS卷积码被认为是最佳搭配 因此该码被忽视了几十年 MacKay (1999) 和Richardson/Urbanke(1998) 重新发现了该码的优点和利用方式.LDPC码码是Low-Density Parity-Check Codes（低密度校验码低密度校验码） 的简称。是一类特殊的线性奇偶检验

2、分组码奇偶检验分组码，其奇偶校验矩阵是稀疏的：只有很小数目的非0矩阵元素（对于二进制码来说，非0元素即为元素1），其他元素都为0。一个矩阵的密度表示矩阵中非0元素所占的比例，一个矩阵的密度小于0.5时可以被认为是稀疏的。2、LDPC码的定义码的定义逼近Shannon限，例如码长1 million （1000000）的非正则（Irregular） LDPC码，离香农限0.3 dB (Richardson:1999)最接近的记录离香农容量0.0045 dB (Chung:2001)纠码字差错block error的性能好差错平台error floor低 最小距离正比于码长译码复杂度与码长是线性关系

3、 适合并行译码运算3、LDPC 码性能码性能信道编码定理信道编码定理具体公式见第一章1、为满足一定误码率的要求，可以增加信道容量2、在码率一定的情况下，增加分组码的长度（增加分组信号持续时间）可使误码率随着分组码长的增加呈指数下降。由于码长的增加，在码率一定的情况下，可能导致发送的码字迅速增加，增加了译码的复杂性。但指出了减少误码的另一个方向。LDPC 就是基于上面第二条，以增加算法的复杂度为代价，获得更好的性能。这是复杂性和通信可靠性两者之间的一个权衡，即在保证可靠性的基础上适当增加复杂性。与Turbo相比，LDPC的简化译码算法和并行解码并不会让系统过于复杂；同时，单纯就时延来看，LDPC

4、虽然迭代解码时延略大，但是本身分集特性分集特性减少了交织交织的过程，整体和Turbo相当。根据校验矩阵中各行各列的“1”的个数是否相等分为规则（Regular）码和不规则（Irregular）码。根据LDPC码的值域划分为二进制LDPC码和多进制LDPC码。这样LDPC码分为规则二进制LDPC码、不规则二进制LDPC码、规则多进制LDPC码、不规则多进制LDPC码四种。通常情况多进制码的性能优于二进制码；同一域的LDPC码，不规则码性能优于规则码。但复杂度正好相反，规则二进制码最简单，多进制不规则码最为复杂。实际应用时根据需要，在系统性能和实现复杂度两者之间权衡。4、LDPC码的分类码的分类二

5、进制规则（Regular）码的奇偶校验矩阵有如下特征：每列包括j个元素，每行包括k元素，其中j、k都是较小的正整数（j 1 0 如如L 1 算法所用符号定义算法所用符号定义qij 从比特节点ci 传递到校验节点fj的消息 rji 从校验节点fj传递到比特节点ci 的消息 Rj = i:hji=1 - H矩阵第j行中,值为1的元素所在的列号的集合 Rji =i:hji=1i -集合Rj中扣除了列号i后剩余的集合Ci = j:hji=1 - H矩阵第i列中,值为1的元素所在的行号的集合Cij = j:hji=1j -集合Ci中扣除了行号j后剩余的集合pi = Pr(ci=1| ri) 收码ri条件

6、下,发码ci=1的概率比如H 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1R2=0,3,6, R23=0, 6C4=1,3, C43 =1 f0 f0 f2 c0 c1 c2 c0位翻转译码位翻转译码1 1 0 1 0 1 0 11 1 0 01除去本身路径的校验和采用三中取二的原则做判决Soft-decision decodingThe above description of hard-decision decoding was mainly for educational purpose to get an

7、 overview about the idea. Soft-decision decoding of LDPC codes, which is based on the concept of belief propagation, yields in a better decoding performance and is therefore belief the prefered method. The underlying idea is exactly the same as in propagation hard decision decoding. Before resenting

8、 the algorithm lets introduce some notations: Pi = Pr(ci = 1|yi) qij is a message sent by the variable node ci to the check node fj. Every message contains always the pair qij(0) and qij(1)which stands for the amount of belief that yi is a ”0” or a ”1”. rji is a message sent by the check node fj to

9、the variable node ci. Again there is a rji(0) and rji(1) that indicates the (current) amount of believe in that yi is a ”0” or a ”1”.The step numbers in the following description correspond to the hard decision case.1. All variable nodes send their qij messages. Since no other information is avaiabl

10、e at this step, qij(1) = Pi and qij(0) =1 Pi.2 . The check nodes calculate their response messages rji:So they calculate the probability that there is an even number of 1s amoung the variable nodes except ci (this is exactly what Vji means). This propability is equal to the probability rji(0) that c

11、i is a 0.3. The variable nodes update their response messages to the check nodes. This is done according to the following equations,whereby the Konstants Kij are chosen in a way to ensure that qij(0)+qij(1) = 1. Cij now means all check nodes except fj.At this point the v-nodes also update their current estimation ci of their variable ci. This is done by calculating the propabilities for 0 and 1 and voting for the bigger one. The used equations are quite similar to the ones to compute qij(b) but now the information from every c