方向可以有如此深厚的理论基础与之媲美我的一个学生就认为 : 理论上的完备性与数学上的优美表达正是编码的魅力所在但理论上的完备性并不能使其直接应用于实际, 因此从码字构造的方向来说, 如何将 LDPC 码应用于实际工作才是值得深入研究的为了保证其实现性, 性能上就要有所妥协在编码方面, 以准循

Size: px

Start display at page:

Download "方向可以有如此深厚的理论基础与之媲美我的一个学生就认为 : 理论上的完备性与数学上的优美表达正是编码的魅力所在但理论上的完备性并不能使其直接应用于实际, 因此从码字构造的方向来说, 如何将 LDPC 码应用于实际工作才是值得深入研究的为了保证其实现性, 性能上就要有所妥协在编码方面, 以准循"

伤倪
5 years ago
Views:

1 第八章 LDPC 码 8. 研究 LDPC 码的原因码编道信码组分线性码非线性码循环码非循环码 BCH 码 RS 码奇偶校验码汉明码码积卷系统卷积码非系统卷积码 Mackay 等人的再发现 Turbo 码 LDPC 码可以看到, 信道编码的发展可以简单的归纳为分组码卷积吗分组码这样一个过程 ( 在这里按其结构将 Turbo 码也归入卷积码的范畴 ) 其中 Turbo 码的出现以及迭代译码的思想引入使得信道编解码产生了前所未有的飞跃, 但 Turbo 码之后卷积码却没有更大的发展, 究其原因就是其没有完备的理论基础, 使得人们不能给出其性能上严密的数学解释于是在那之后可以说是一种退化或者是返朴归真,Mackay 等人再次发掘了 Gallager 于 962 年提出的一种具有稀疏校验矩阵的分组纠错码, 即 LDPC 码 LDPC 码自身的矩阵结构引入了交织特性, 而且其采用迭代译码的方法, 使其性能比以往的线性分组码有很大程度的提高由于其基本原理是基于最原始的线性分组码, 因此它有强大的数学工具作为其理论依据, 几乎融图论组合数学概率论矩阵论代数几何代数数论黎曼几何于一炉在通信的其它领域, 我们很难再找到某个

2 方向可以有如此深厚的理论基础与之媲美我的一个学生就认为 : 理论上的完备性与数学上的优美表达正是编码的魅力所在但理论上的完备性并不能使其直接应用于实际, 因此从码字构造的方向来说, 如何将 LDPC 码应用于实际工作才是值得深入研究的为了保证其实现性, 性能上就要有所妥协在编码方面, 以准循环 LDCP 码, 即 QC-LDPC 码为例, 为了降低硬件上的存储空间以及易于编码, 就要以牺牲 LDPC 码先天的优势交织特性为代价, 这样便做出了性能与实现上的折中但这种折中是有意义的, 为 LDPC 码的实际应用开辟了道路而且, 通过某些方法, 可以使设计出的码字在易于存储实现的同时, 还能保证一定的性能在译码方面, 种种方法都可以归结为和积算法 (SPA) 的变形, 都是在其基础上做出改进, 从而保证译码性能前提下使译码器尽可能的简单相对于 Turbo 码,LDPC 码的解码迭代次数还是过高, 这样在实际应用中的竞争力便大打折扣于是, 怎样在保证性能的前提下降低译码时间是现在译码研究的主要工作 8.2 LDPC 码简介 996 年 Mackay Spielman 和 Wiberg 几乎同时发现 :Gallager 早在 962 年提出的低密度校验码 ( 简称 LDPC 码, 也称 Gallager 码 ) 也是一个好码, 具有更低的线性译码复杂度 Gallager 提出 LDPC 码后一直没有得到编码界的重视, 只有 98 年 Tanner 从图论的角度研

3 究过 LDPC 码自 Mackay 等再发现 LDPC 码后, 人们的进一步研究表明 : 给予非规则双向图的 LDPC 长码的性能可以优于 Turbo 码, 而且这样的码的性能可以非常接近 Shannon 限一个原因在于 LDPC 码具有良好的距离特性较小的译码错误概率和较低的译码复杂度, 且码长大于 200 时不存在错误平台, 码率容易调整, 实验结果中几乎均为可检测错误, 所以 LDPC 码无论在理论上还是在实际上都具有极其重要的价值 LDPC 码的重新发现是继 Turbo 码后在纠错码领域又一重大进展 () 编码方面的简介无论 Gallager 还是 Mackay 都是用随机的方法构造 LDPC 码, 用随机法构造的 LDPC 码的码字参数选择灵活, 但对于高码率中短长度的 LDPC 码用随机法进行构造, 要避免短循环是困难的, 其没有一定的码结构, 编码复杂度高, 于是人们考虑用代数法构造 LDPC 码 LDPC 码代数构造可采用几何方法图论方法实验设计方法置换方法来设计不同的构造方法都是为了实现以下几个目的 : 增大图中最小循环长度, 即 Girth 值优化非规则码的节点分布, 减小编码复杂度, 构造的 LDPC 码要有好的码性能 M.G.Luby 等指出, 非规则 H 矩阵构造的码字性能优于相应的规则 H 矩阵构造的码字在寻找好的码结构方面,Mackay 等提出 : 能快速编码的 LDPC 矩阵通常具有下三角形结构 T.J.Richardson 探讨了如何构造编码矩阵, 使编码时间与码块长度实际上符合线性关系 ( 线形时间编码 ), 而非通常认为的平方关系

4 Y.Kou 和 S.Lin 等探讨了基于有限几何学的 LDPC 码结构 S.Lin 研究团队的 B.Ammar 等提出用均衡不完全区组设计方法 (BIBD) 构造好的 LDPC 码 (2) 译码方面的简介 Gallager 曾给出两种 LDPC 码的迭代译码算法 : 硬判决和软判决算法后者虽有好的性能, 但太复杂, 消息传递算法可以认为是二者的折衷消息传递算法 (MP,Message Passing) 有时也称置信传播 (BP,Belief Propagation) 算法在 MP 译码算法中, 节点到节点的消息是通过 Tanner 图传递的译码算法的改进和优化离不开译码性能的分析在译码性能分析的研究方面, T.J.Richardson 等开发了一种在码块无限长假设条件下, 跟踪 LDPC 码 Tanner 图中消息概率的技术, 称为密度进化算法的数值程序, 来近似估计噪声门限 ( 在该门限以下可望成功地采用 BP 算法 ), 提出了一种通用方法来确定任何二元输入无记忆信道中采用 MP 译码的 LDPC 码的性能特别对于 BP 译码算法, 该方法可提供任何所需精度的性能估计 S.Y.Chung 等将消息离散化, 通过计算机迭代搜索寻找最优的节点次数分布, 特别适合于非规则码的分析, 在二进制输入 AWGN 信道下, 设计码率 /2 码长 0 7 的非规则 LDPC 码在错误概率 0-6 时离 Shannon 限仅 dB 这是迄今为止报到处的性能最接近 Shannon 限的信道编码 8.3 LDPC 码的基本概念

5 LDPC 码是用一个稀疏的非系统的校验矩阵 H 定义的线性码行重 :H 矩阵每行中的个数, 其值远远小于 H 矩阵的列数列重 :H 矩阵每列中的个数 LDPC 码可以按照 H 矩阵分为规则 (regular) 和非规则 (irregular) 两种规则 LDPC 码中, 各行的行重是一致的, 各列的列重也是一致的, 而行重或者列重不一致就称为非规则 LDPC 码下面给出规则 LDPC 码的定义 : 一个 (n, j, k) 的规则 LDPC 码由它的校验矩阵 H 定义, 校验矩阵有 n 列,m 行, 列重 j, 行重 k, 其中 m / = n j k,j<k,j<<m,k<<n LDPC 码的 H 矩阵一般都是用非系统形式给出的例如我们生成一个 (6,2,4) 的校验矩阵 : H = 如例所示的规则 H 矩阵行重为 4, 列重为 2 同一般的线性分组码,H 矩阵的码率可以如下计算 : R=(n-m)/n=(k-j)/k; 则图 4 的矩阵可以用来实现码率 /2 的编码 LDPC 码的校验矩阵的行对应着校验方程 ( 校验节点 ), 列对应着传输的比特 ( 比特节点 ), 它们之间的关系可以用 Tanner 图来表示, 图的左边有 n 个节点, 每个节点表示码字的信息位, 称为信息节点 {x j, j=, 2,, n}, 是码字的比特位, 对应于校验矩阵的各列, 信息节点也成为变量节点 ; 右边有 m 个节点, 每个节点表示码字的一个

6 校验集, 称为校验节点 {r i, i=, 2,, m}, 代表校验方程, 对应于校验节点的各行 ; 与校验矩阵中元素相对应的左右两节点之间存在连接边我们将这条边两端的节点称为相邻节点, 每个节点相连的变数成为该节点的度 (Degree), 每个信息节点与 j 个校验节点相连, 称为该变量节点的度为 j; 每个校验节点与 k 个信息节点相连, 称为校验节点的度为 k 例如上面的 H 矩阵对应的 Tanner 图如下 : x x 2 r = x+ x2 + x4 + x5 x 3 r2 = x+ x3+ x5 + x6 x 4 r3 = x2 + x3 + x4 + x6 x 5 x 6 图 Tanner 图 LDPC 码校验矩阵 H 中, 一个很重要的概念 :H 矩阵的最小圈长, 即 girth 一个 4 循环 (girth=4) 在图中表示为 :

7 x x 2 r = x+ x2 + x4 + x5 x 3 r2 = x+ x3+ x5 + x6 x 4 r3 = x2 + x3 + x4 + x6 x 5 x 6 图 2 Girth 值为 4 的短循环对应于 H 矩阵, 此 4 循环可以表达为 : H 0 0 = 同理, 对于 6 循环我们有 : H 0 = 0 0 上式所示的矩阵 H 表示校验矩阵 H 中的一个子矩阵短循环对于矩阵性能的影响 : 在 LDPC 码的译码算法中, 我们都假设传递的消息满足彼此独立的假设当 H 矩阵中存在长度为 2L 的环路时, 则这些消息只在前 L 轮迭代过程中满足独立性假设 ( 注意 :

8 解码的迭代过程包括一次比特节点更新和一次校验节点更新 ) 因此短循环的存在会影响 LDPC 码的解码性能另外简单的解释 : 例如在图 2 所示的 H 矩阵中, 存在一个 4 循环于是这个 4 循环对应的校验方程为 : r = x+ x2 + x4 + x5 r2 = x+ x3+ x5 + x6 由于 4 循环的存在, 我们可以看到, 上面两个校验方程含有共同的比特节点 x 与 x 5, 直观地说, 如果这两个校验方程均出错, 则我们无法确定 x 与 x 5 中究竟哪个出错, 所以从这个角度也可以说明短循环对于性能带来的影响 8.4 LDPC 码的编码方法 LDPC 码属于线性分组码, 利用其校验矩阵 H 可以生成编码矩阵 G, 从而可以生成码字, 其校验矩阵 H 可以体现 LDPC 码的特点与性能, 所以我们首先介绍 H 矩阵的构造方法 8.4. LDPC 码校验矩阵 H 的构造 Gallager 的 H 矩阵构造方法每一行有 j 个 ; 满足行重要求每一列有 k 个 ; 满足列重要求任意两列具有共同的个数不大于 ; 满足 girth 值大于 4 j 和 k 分别与 H 矩阵中的列数和行数相比小得多 ; 满足 H 矩阵的稀疏性

9 设矩阵 H 0 为 : 利用 H 0, 我们可以通过列交换的方法得到校验矩阵 H: 例如下图就是由这种方法构造出的校验矩阵 : Mackay 的构造方法此方法中, 校验矩阵的列重为 j, 每行的平均重量为 k( 即此方法所构造出的 H 矩阵 ), 且任意两列具有共同的个数不大于 ( 保证不存在 4 循环 ) 构造法 A

10 这是一种基本的构造方法, 每一列具有固定的列重 j 随机构造矩阵, 使其平均行重为 k, 且任意两列具有共同的个数不大于构造矩阵如图 3 所示 : 3 3 图 3(j=3,k=6,R=/2) 可以按照上面的方法生成一个 H 矩阵, 例如构造法 2A 与构造法 A 类似, 引入一些列重为 2 的列, 使得 H 矩阵的 girth 值增大, 其中列重为 2 的列数为 m/2, 这一部分是由两个 m/2 m/2 的单位阵上下重叠起来构成的如下图所示 : 3

11 图 4 可以按照上面的方法生成一个 H 矩阵, 例如构造法 B 和 2B 从构造法 A 和 2A 中删除一些仔细选择的列, 使得 H 矩阵中 girth 值满足相应的要求超轻矩阵将 Mackay 的构造方法推广, 进一步增加列重为 2 的列数, 即用更多的更小的单位矩阵连续重叠现将两个 m/2 m/2 的单位矩阵重叠, 再是 m/4 m/4 的单位矩阵重叠, 以此类推, 最终最多是 m 个列重为 2 的列如下图所示 3 例如, 图 5

12 QC-LDPC 码的构造在构造 LDPC 码校验矩阵时, 随机构造方法不利于硬件实现, 于是人们想到利用几何代数的方法来构造 LDPC 码的校验矩阵, 于是就产生了 QC-LDPC 码, 即准循环 LDPC 码 (Quasi-Cyclic LDPC codes) 首先, 这类码有严谨的数学结构, 构造和性能分析更加精确, 甚至最小汉明距离都是可以计算的 ; 其次, 和随机构造的 LDPC 码相比, 它具有更低的误码平台 ; 第三, 这类码字具有准循环结构, 极大地降低了编码复杂度, 也为译码提供了更方便的选择 QC-LDPC 码的数学基础首先, 介绍 QC-LDPC 码的数学基础, 以及重要的定理群 : 群 (G) 是具有二元运算的集合, 并且适合一下条件 : 结合律成立, 即 ( ab) c = a( bc), a, b, c G ; G 中存在一个元 e: ea = ae = a, a G ; 对 G 中的任意元 a, 存在 a G, 使 aa = a a = e 环 : 有两个二元运算 ( 分别叫做加法和乘法 ) 的代数系统 ( A, +, ) 叫做一个环, 如果 ( A, + ) 是一个加法群 ;

13 ( A,) 是一个半群 ( 只对结合律成立 ); 乘法对加法的左右分配律都成立域 : 一个交换的除环叫做一个域一个重要的定理 :( 费马定理 ) 设 p 为素数, 则有 :a p- = (mod p), 即 a p =a (mod p) QC-LDPC 码的定义定义 H 矩阵的 m n 的母矩阵 M(H), 将 M(H) 中的 0 与分别用 L*L 的全 0 子矩阵与 L*L 的循环子矩阵 p 替换, 就可得到校验矩阵 H, 其中循环移位子矩阵 P 定义为 a ij P = 例如定义一个全母矩阵为 : M(H) = m n 将上式中的每个替换成一个 L L 的子矩阵 ml nl 的 H 矩阵 : a p ij, 得到一个

14 a a a(n-) a p p p p a a a2(n-) a p p p p H= a a am(n-) a p p p p 2 n n m m2 mn 其中 a ij (i=,2,,m; j=,2,,n) 为移位项将单位阵向右循环移位 a ij 得到循环子矩阵 a p ij 在存储 H 矩阵的时候, 我们只需要存储上式中每一个 a ij 的值, 而不需要存储每个的位置基于有限几何 (Finite Geometries) 的 LDPC 码的构造方法有限几何指的是一个由点和边组成的集合,a 为其中一个 m 元组点, 即 a GF( q) m 在构造 LDPC 码的时候, 有限几何 G 是由 n 个点和 m 条边组成, n 和 m 分别对应于 H 矩阵的列数和行数我们要构造规则的 H 矩阵, 所以这些点和边具有下列性质 : 每一条边含有 j 个点对应 H 矩阵的行重每一个点都位于 k 条边上对应 H 矩阵的列重任意两个点仅仅通过一条边相连确保没有 4 循环任意两条边或平行或只相交于一点对于这样的有限几何 G, 所构造 H 矩阵的行和列分别对应其中的边和点, 当 H 矩阵中 h i,j = 时, 表示 G 中的第 i 条边包含了第 j 个点基于有限环的构造方法有限环构造的优点 : 由定义可知, 环与域的区别在于除法和对于乘法的交换律因此

15 环的限制比域小得多更重要的是环的基数可以做到连续, 这样使得所构造的码长可以连续基于这种理论我们可以构造出 girth 值为 0, 且码长连续的 LDPC 码 H 矩阵 LDPC 码的线性编码基本编码方法 T 通过矩阵的初等变换, 把 H 矩阵变化成系统形式 : H = [P,I] ; 得到该 H 矩阵对应的生成矩阵 G = [I, P] ; 用信息比特去乘生成矩阵 G, 就得到了编码后的码字 ; 2 此方法的复杂度为 On ( ) Richardson 的 LDPC 码编码算法 ) 公式推导 : 通过行列置换将 H 矩阵化为近似下三角形状, 即 : A( mg - ) ( nm - ) B( mg - ) g T( mg - ) ( mg - ) H= Cg ( n- m) Dg g E, g ( m- g) 其中 T 为下三角阵即 H 可以转化为 : m n

16 用式 I 0 - -ET 假设码字为符号图 6 I 所示矩阵左乘矩阵 H, 得到 A B T - - -ET A -ET B + D 0 s x= p p 于是由 Hx=0 有 : 2, 其中 s 表示信息符号,p 和 p 2 表示校验 As + Bp + Tp 2 = (-ET A + C)s + (-ET B + D)p = 0 - 定义 : φ = (-ET B + D), 并且假设 φ 非奇异, 于是有 : p =- 2) 复杂度分析 : - - φ (-ET As + Cs), p = -T (As + Bp ) - 2

17 表 p =- - - φ (-ET As + Cs) 的复杂度计算操作注释复杂度 As 稀疏矩阵乘以向量 On ( ) - T As - T As = y As = Ty On ( ) - -ET As 稀疏矩阵乘以向量 On ( ) Cs 稀疏矩阵乘以向量 On ( ) - -ET As + Cs 向量相加 On ( ) p =- - - φ (-ET As + Cs) 密集矩阵乘以向量 2 Og ( ) - 表 2 p 2 = -T (As + Bp ) 的复杂度计算操作注释复杂度 As 稀疏矩阵乘以向量 On ( ) Bp 稀疏矩阵乘以向量 On ( ) As + Bp 向量相加 On ( ) - - -T (As + Bp ) 3) 编码过程总结 : -T (As + Bp ) = y -(As + Bp ) = Ty On ( ) 预处理, 输入 : 非奇异矩阵 H; 输出 : 形如阵, 使得 - -ET B + D 非奇异 :[ 近似下三角化 ] 通过行列置换将矩阵 H 变形如似下三角矩阵, 并使 g 尽可能的小 2:[ 秩校验 ] 利用高斯消元法完成矩阵运算 A B T C D E A B T C D E 的等价矩的近

18 I 0 A B T A B T = ET I C D E -ET A -ET B + D 0 - 检验矩阵 -ET B + D 是否非奇异, 如果奇异, 则进一步进行行列置换使之非奇异编码 : 输入 : 形如异, 向量 s; 输出 : 向量 : 通过表计算 p 2: 通过表 2 计算 p 2 此方法的复杂度为 g 尽量小 A B T C D E s x= p p On 2 - 的非奇异矩阵, 并且 -ET B + D 非奇 2 ( g) 8.5 通过 H 矩阵的设计简化编码复杂度, 使得 Hx=0 +, 为了降低编码复杂度, 应当使在利用 LDPC 码 H 矩阵编码的时候, 一般都需要先得到 G 矩阵, 随后生成所需要的码字在 H 矩阵转化为 G 矩阵的过程中所需要的计算量是相当大的而且在硬件存储方面,H 矩阵为稀疏矩阵, 需要存储每个的位置, 但是 G 矩阵是一个密集矩阵加上一个单位阵的形式, 这就需要开辟很大的存储空间所以如果编码时不需要生成 G 矩阵, 而直接通过 H 矩阵编码, 这样就将编码复杂度大大简化最简单的方法这种方法是构造 H sys 形式的 H 矩阵即先构造一个矩阵 H, 随后

19 在 H 的后面添加一个单位阵构造出 H 矩阵即 : 图 7 利用这种 H 矩阵可以实现线性时间编码递推编码的方法由于上面的方法最右边存在一个单位阵, 导致最右边列重为, 即最右边每个比特只参与一个校验方程这样使得校验节点对比特节点的保护就不够, 造成性能上的降低于是为了增加对右边比特的保护, 我们可以采用下面 H 矩阵构造方式将 H 矩阵构造为如下形式 : p, p,2 p,(n-m) p,(n-m+) p2, p2,2 p2,(n-m) p2,(n-m+) p2,(n-m+2) 0 0 H= p p p p p p p m, m,2 m,(n-m) m,(n-m+) m,(n-m+2) m,(n-m+3) m,n 其中 p i,j 为利用单位阵移位生成的循环子矩阵这种循环子矩阵有一个非常好的性质 : p i,j p T i,j =I; 即 p - i,j =p T i,j 这样我们就可以通过对矩阵求转置而得到矩阵的逆, 大大简化了计算量对于上式所示的 H 矩阵, 由其校验方程 Hx = 0, 可得 :

20 p,(n-m+) c =p,x +p,2x 2 + +p,(n-m) xn-m p2,(n-m+) c +p2,(n-m+2) c 2 =p2,x +p2,2x 2 + +p2,(n-m) xn-m p c +p c + +p c =p x +p x + +p x m,(n-m+) m,(n-m+2) 2 m,n m m, m,2 2 m,(n-m) n-m T c =p,(n-m+) ( p,x +p,2x 2 + +p,(n-m) xn-m ) T c 2 =p2,(n-m+2) ( p2,x +p2,2x 2 + +p2,(n-m) x n-m +p2,(n-m+) c) 则 ; T c m =pm,n( pm,x +pm,2x 2 + +pm,(n-m) x n-m +pm,(n-m+) c +pm,(n-m+2) c 2+ ) x x n-m x = 其中 c cm, 利用递推算法可以得到相应的 c, c,, c 2 m ; 8.6 LDPC 码的译码主要方法有比特翻转 (Bit-Flipping) 译码加权大数逻辑 (Weighted Majority-Logic) 译码和积 (Sum-Product) 算法等

422 东南大学学报 ( 自然科学版 ) 第 47 卷数方法 ) 来构造的一类非常重要的 LDPC 码, 其校验矩阵具有类循环特性, 实现复杂度低, 可以采用简单的移位寄存器硬件来实现编码器, 易于硬件实现 [67]. LDPC 码的校验矩阵主要基于停止集和围长来进行构造. 停止集及其停止距离制约

422 东南大学学报 ( 自然科学版 ) 第 47 卷数方法 ) 来构造的一类非常重要的 LDPC 码, 其校验矩阵具有类循环特性, 实现复杂度低, 可以采用简单的移位寄存器硬件来实现编码器, 易于硬件实现 [67]. LDPC 码的校验矩阵主要基于停止集和围长来进行构造. 停止集及其停止距离制约第 47 卷第 3 期 2017 年 5 月东南大学学报 ( 自然科学版 ) JOURNALOFSOUTHEASTUNIVERSITY(NaturalScienceEdition) Vol.47 No.3 May2017 DOI:10.3969/j.isn.1001-0505.2017.03.001 低存储可线性编码的 QC LDPC 码设计 1,2 孔令军姜 1 明 1 赵春明 ( 1 东南大学移动通信国家重点实验室,