文档介绍：LDPC码历史
Robert Gallager 1960 年在MIT Ph. D. 论文中提出
由于
1. 计算量大
2. RS码的引入
3. RS+卷积码被认为是最佳搭配
因此该码被忽视了几十年
MacKay (1999) 和Richardson/Urbanke(1998) 重新发现了该码的优点和利用方式.
1
LDPC 码性能
逼近Shannon限,例如
码长1 million (1000000)的非正则(Irregular) LDPC码, dB (Richardson:1999)
dB (Chung:2001)
纠码字差错block error的性能好
差错平台error floor低
最小距离正比于码长
译码复杂度与码长是线性关系
适合并行译码运算
2
线性分组码基础
可用一个生成矩阵G或校验矩阵H来描述The structure
纠错能力由最小距离dmin 决定。
最小距离dmin 等于生成矩阵G中最轻行的重量
最小距离dmin也等于校验矩阵H的秩加1
比如(7, 4)汉明码
G = H =
1 0 0 0 1 1 1
0 1 0 0 1 1 0
0 0 1 0 1 0 1
0 0 0 1 0 1 1
1 1 1 0 1 0 0
1 1 0 1 0 1 0
1 0 1 1 0 0 1
3
LDPC 码特点
(n,k)分组码校验矩阵H (m行n列)是稀疏矩阵,
即每行和每列只有极少个“1”,
而其最小距离dmin又较大。
这里m=n-k。
规则的LDPC码
H矩阵每列都有同样的 Wc 个“1”,
每行都有同样的 Wr 个“1”,
且 Wr = Wc · ,
这里Wc << m,也意味着Wr << n.
对于一个好码,应有Wc 3 .
如行和列中“1”的个数不是常数,称该码为
不规则LDPC码.
通常,不规则LDPC码的性能优于规则LDPC码。
n
m
4
一个简单LDPC 码的例子
本例中
Wc = 3
任何两列至多有一个“1”在位置上是重叠的(处于同一行)。稀疏的特点使我们能够做到这点。
矩阵的列线性无关,
即从列的线性组合得不出全“0”列。
上列特点使该码的 dmin 较大;
G 可以用高斯消去法求得
校验矩阵H 可以写成H =[ PT ¦ I ]形式
生成矩阵G 可以写成G =[I ¦ P ]
1 1 0 0 …
0 0 0 0 …
0 1 1 0 …
0 0 0 0 …
1 0 1 1 …
H = 1 0 0 0 …
0 0 0 1 …
0 0 0 0 …
0 1 0 1 …
0 0 1 0 …
. . . . …
. . . . …
5
LDPC 码的编码
一般系统线性分组码的编码
C = mG = [ m ¦ mP ]
一般编码方法用于 LDPC码会产生的问题
G的维数巨大,G一般也并不稀疏。比如一个(10000,5000) LDPC码,P矩阵将是5000×5000矩阵。假设“1”,编码所作的运算也有
×(5000×5000)=×106 次
(注:H在系统化之前是稀疏矩阵,系统化后就不一定了,因此G也一般并不稀疏)
简化编码的方法之一是利用代数或几何途径来设计LDPC码,使之能用移位寄存电路实现编码.
6
LDPC 码的迭代译码
一般线性分组码的译码方法:
当C是码字时,有CHT = 0
对于BSC信道, R=CE,其中E是差错矢量。译码器的
任务是要找出E,把它加到接收码上C=R E。
译码算法一般是基于线性代数。
LDPC 码通常采用基于图的译码算法,比如
1. 和-积(Sum-product)算法
(用在基于一般图的编码)
(BCJR)算法
(用在基于网格图的编码)
( Message passing)算法
(用在基于二分图的码)
7
Tanner 图
二分图(Bipartite graph)
二分图是一种无向图,基本元素是节点(node)和边(edge),
节点分成两类(class),一条边所连接的两个节点必须分属不同的两类。
Tanner图
Tanner图里有两类节点:比特(bit)节点和校验(check)节点。例如一个(8,4)乘积码
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
校验节点(行) f0 f1 f2 f3 fj
ci
比特节点(列) c0 c1 c2 c3 c4 c5 c6 c7
8
消息传递(Mes