信道编码_第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 flo

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

4、LDPC的简化译码算法和并行解码并 不会让系统过于复杂； 同时，单纯就时延来看，LDPC虽然迭代解码时延略 大，但是本身分集特性分集特性减少了交织交织的过程，整体和 Turbo相当。 根据校验矩阵中各行各列的“1”的个数是否相等分为规 则（Regular）码和不规则（Irregular）码。根据LDPC码 的值域划分为二进制LDPC码和多进制LDPC码。 这样LDPC码分为规则二进制LDPC码、不规则二进制 LDPC码、规则多进制LDPC码、不规则多进制LDPC码 四种。 通常情况多进制码的性能优于二进制码；同一域的 LDPC码，不规则码性能优于规则码。但复杂度正好相 反，规则二进制码最简单，

5、多进制不规则码最为复杂。 实际应用时根据需要，在系统性能和实现复杂度两者之 间权衡。 4、LDPC码的分类码的分类 二进制规则（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的元素

6、所在的行号的 集合 Cij = j:hji=1j -集合Ci中扣除了行号j后剩余的集合 pi = Pr(ci=1| ri) 收码ri条件下,发码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 1 R2=0,3,6, R23=0, 6 C4=1,3, C43 =1 f0 f0 f2 c0 c1 c2 c0 位翻转译码位翻转译码 1 1 0 1 0 1 0 1 1 1 0 0 1 除去本身路径的校验和 采用三中取二的原则做判决 Soft-decision decoding The above de

7、scription of hard-decision decoding was mainly for educational purpose to get an 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 ide

8、a is exactly the same as in propagation hard decision decoding. Before resenting 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

9、 belief that yi is a ”0” or a ”1”. rji is a message sent by the check node fj to 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

10、. All variable nodes send their qij messages. Since no other information is avaiable 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 i

11、s exactly what Vji means). This propability is equal to the probability rji(0) that ci 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. C

12、ij 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 eve