《ldpc编译码原理课件》由会员分享，可在线阅读，更多相关《ldpc编译码原理课件（88页珍藏版）》请在金锄头文库上搜索。
1、LDPC码 2011-4-191 目录 引言引言 LDPC码概述 LDPC码构造 和积算法 LDPC码解码 性能分析 2011-4-192 引言 Turbo码的发现引发了对基于图模型的编码设 计和迭代译码算法的研究热潮； Mackey等人发现由Gallager早在1962年提出 的一种低密度奇偶校验码（Low Density Parity Check Codes，LDPC码）也是一种实 用的好码； 与Turbo码相比，LDPC码具有描述简单、解 码复杂度低、实用灵活等特点。 2011-4-193 引言 LDPC码目前可达到的性能: AWGN信道中最接近信道容量的仿真结果 无限码长：距离香侬极限
2、0.0045dB 码长为107：误码率为10-6时距离香侬极限0.04dB 众多下一代通信标准的信道编码方案: DVB-S2 中国地面广播电视标准-CMMB WiMAX 802.16e 802.11n提案 深空探测推荐方案 2011-4-194 CMMB: 码率LDPC码为例 4608*9216的矩阵，每行有6个“1” 目录 引言 LDPC码概述码概述 LDPC码构造 和积算法 LDPC码解码 性能分析 2011-4-195 LDPC码概述 H矩阵 二分图 维度分布函数 参数 2011-4-196 LDPC码概述 H矩阵 LDPC码是一种线性分组码. LDPC码的校验矩阵H是稀疏矩阵: 每一行
3、表示一个校验方程约束，包含j个码元, 每一列表示一个码元参加 k个校验方程, 任意两个校验方程包含至多一个相同码元. 2011-4-197 LDPC码概述 H矩阵 11110000000000000000 00001111000000000000 00000000111100000000 00000000000011110000 00000000000000001111 10001000100010000000 01000100010000001000 00100010000001000100 00010000001000100010 00000001000100010001 10000100
4、000100000100 01000010001000010000 00100001000010000010 00010000100001001000 00001000010000100001 2011-4-198 LDPC码概述 H矩阵 LDPC码的校验矩阵 j和k为常数的H矩阵的零空间构成正则LDPC 码，记作（n, j, k ）正则LDPC码. j 和k不是常数的H矩阵的零空间构成非正则 LDPC码. 2011-4-199 LDPC码概述 二分图 LDPC码可以用二分图来表示. LDPC码对应的二分图包括两种节点: 变量节点（variable nodes） 校验节点（check node
5、s） 2011-4-1910 c c1 1 c c2 2 c c3 3 c c4 4 c c5 5 v v1 1 v v2 2 v v3 3 v v4 4 v v5 5 v v6 6 v v7 7 v v8 8 v v9 9 v v10 10 LDPC码概述 二分图 变量节点（Variable Node）与LDPC码的一个码元相对应， 其个数等于码长n； 校验节点（Check Node）与校验方程对应，其个数和码 的校验矩阵H的行数相同; 变量节点j和校验节点i之间的联线表示与对应的第i校验方 程中含有第j个码元. 2011-4-1911 c c1 1 c c2 2 c c3 3 c c4 4
6、 c c5 5 v v1 1 v v2 2 v v3 3 v v4 4 v v5 5 v v6 6 v v7 7 v v8 8 v v9 9 v v10 10 LDPC码概述 二分图 相互之间有连接线的节点互为邻点（Neighbor）， 一个节点的邻点数量称为这个节点的维度（Degree）, 回路（cycle，环） 从一个端点出发，经过不重复的边回到出发端点 经过的边数定义为回路的长度 图中最短回路长度称为图的周长（girth） 2011-4-1912 c c1 1 c c2 2 c c3 3 c c4 4 c c5 5 v v1 1 v v2 2 v v3 3 v v4 4 v v5 5 v
7、 v6 6 v v7 7 v v8 8 v v9 9 v v10 10 LDPC码概述 维度函数 变量节点维度分布函数： 表示在二分图中，与维度为i的变量节 点相联的边（Edge）占所有边的比例; 表示变量节点的最大维度. v d i i i xx 2 1 : )( i v d 2011-4-1913 LDPC码概述 维度函数 校验节点维度分布函数： 表示在二分图中，与维度为i的校验节 点相联的边（Edge）占所有边的比例; 表示校验节点的最大维度 . c d i i i xx 2 1 :)( i c d 2011-4-1914 LDPC码概述 维度函数 k=3, j=6的（3, 6）正则码中
8、 ， 维度分布函数表示的LDPC码记为 5 )(xx 2 )(xx )(),(xx 2011-4-1915 LDPC码概述 参数 设总边数为B，则变量节点数n为 设变量节点数为n,则总边数B为， 1 0 ( ) i nn B x dx i 1 0 ( ) ii B nBBx dx ii 2011-4-1916 LDPC码概述 参数 设总边数为B，则校验节点数m为 设校验节点数为m,则总边数B为， 1 0 ( ) i mm B x dx i 1 0 ( ) ii B mBBx dx ii 2011-4-1917 LDPC码概述 参数 维度为i的变量节点数: 维度为i的校验节点数: 1 0 2 /
9、 / ( ) / v ii id j j ii Binn x dx j 1 0 2 / / ( ) / c ii id j j ii Bimm x dx j 2011-4-1918 LDPC码概述 参数 码率: 1 m r n 1 0 1 0 ( ) 1 ( ) x dx x dx 2011-4-1919 目录 引言 LDPC码概述 LDPC码构造码构造 和积算法 LDPC码解码 性能分析 2011-4-1920 LDPC码构造 构造目标 构造准则 构造方法 2011-4-1921 LDPC码构造-目标 构造一个二进制稀疏矩阵 任意两行之间至多只有一个共同的位置有1 任意两列之间至多只有一个共
10、同的位置有1 二分图中没有长度为4的环（cycle 4 free） 衡量好坏的标准 误码率 通过仿真得到 2011-4-1922 LDPC码构造-准则 获得更好的误码性能 更大的环 译码采用迭代译码前提：节点间传递的信息统计独立 校验矩阵对应的二分图中有环存在某一个节点发出的信息经过一个环长 的传递会被传回本身，从而造成自身信息的叠加，破坏了独立的假设，影 响译码的准确性。 希望：大环多，小环少，尤其避免最短环4（4-cycle）。 定理：LDPC码的任意一个长为L的环，满足L4，且L是2的倍数。 更大的最小码距 高信噪比下降低error floor 更均匀的环分布特性 更快更均匀地收敛 更规
11、则的H矩阵结构 便于工程实现 23 LDPC码构造-方法 随机搜索 最初的方法 图的方法 PEG（Progressive Edge Growth）算法 Bit-Filling算法 代数的方法（结构化的方法） 有限几何方法 基于RS码的方法 组合数学的方法（BIBD平衡不完全区块设计） 置换矩阵的方法 2011-4-1924 目录 引言引言 LDPC码概述 LDPC码构造方法 和积算法和积算法 LDPC码解码 性能分析 2011-4-1925 和积算法 对数似然比 概率的对数似然比 对数似然比与概率等价 +1 ( )log 1 P u LLR u P u ( ) ( ) ( ) +1 1 1 1
12、 1 LLR u LLR u LLR u e P u e P u e 2011-4-1926 和积算法 奇偶校验和的对数似然比 编码系统中，各个符号之间存在校验和关系 利用对数似然比可以推导出 已知各个校验和的置信度，求出参与校验的各个符号 的置信度 已知各个符号的置信度，求出各个校验和的置信度 2011-4-1927 和积算法 奇偶校验和的对数似然比 开始推导前的假设与定义 数字符号 ui 遵从 N 个校验和 Sn，其中 ui 之外的数字符号只出现一次 ui 之外的数字符号相互独立 2011-4-1928 和积算法 奇偶校验和的对数似然比 将数字符号 ui从校验和Sn中除去，得到 “修正校验
13、和”Sn “修正校验和”的似然比数字符号 ui的似然比 校验和包含的其余符号似然比”修正校验和” 的似然比 2011-4-1929 和积算法 奇偶校验和的对数似然比 修正校验和举例: 有数字符号u1，u2，u3满足校验关系 S1= u1+u2+u3=0+1； 去除符号u1的作用，得到修正校验和 S1= u2+u3=1-1, if u1=1 （-1）; S1= u2+u3=0+1, if u1=0（+1）; 2011-4-1930 引入“修正校验和”Sn后的概率 1 (1,1,1,2,) (1,1,2,/1)(1) (1,1,2,)(1) (1)(1) in nii ni N ni n P us
14、nN P snN uP u P snNP u P sP u 2011-4-1931 和积算法 从校验和的置信度得到符号的置信度 和积算法 从校验和的置信度得到符号的置信度 引入“修正校验和”Sn后的概率 1 (1,1,1,2,) (1,1,2,/1)(1) (1,1,2,)(1) (1)(1) in nii ni N ni n P usnN P snN uP u P snNP u P sP u 2011-4-1932 1 1 1 (1,1,1,2,) ( )log (1,1,1,2,) (1)(1) loglog (1)(1) (1)(1) loglog (1)(1) (1) ()log (1) in i in N ni n ni N ni n ni N i n n i P usnN LLR u P usnN P sP u P sP u P sP u P sP u P u LLR s P u 2011-4-1933 和积算法 从校验和的置信度得到符号的置信度
