《集成电路课程翻译》由会员分享，可在线阅读，更多相关《集成电路课程翻译（9页珍藏版）》请在金锄头文库上搜索。
1、 基于电压图的 LDPC 码摘要：几种知名的基于结构化构造的 LDPC 码，比如基于置换和循环矩阵码，特别是准循环的 LDOC 码，可以通过代数电压分配来译码。我们解释这种译码方法并且说明这种来自拓扑图理论的方法是如何对这些 LDPC 码的许多知名的性能进行简单的证明。此外，介绍了 abelian-inevitable 圈的概念，并且归类了产生这些圈的子图。我们也预测了如何通过使用更精密的电压分配来得到优秀的新型 LDOC 码。1、引言由于其高效的解码算法和在多个通信信道的卓越性能，基于图的代码已经引起了广泛的关注。然而，理论表明什么时候适合采用基于图的码和怎样去设计这种基于图的码是很困难的。
2、许多工作重点研究这些码长趋于无穷的代码的系统的渐近性能。考虑到实际的实现，需要代数构造短到中等长度码的设计。一些研究者已经提出了这种代码的结构化构造，每种构造旨在于优化结果图的一个或者多个性能，直观地改善结果代码的性能，比如 girth（围长）、扩张、直径、停止集、伪码字。最近吸引人的一个领域是原模图 LDOC 码，这种基于图的代码是通过选择适当的基图或者原模图进行随机置 1 得到的。然而，许多这种构造法出现问题，并且在设计这种基于图的代码时具有很严重的数学理论缺乏的问题！在本文中，我们旨在通过统一几个不同图的代码的家族在一个共同的构架下来改善这一缺陷，也就是产生电压图的图的码。我们以拓扑图理
3、论的观点来考虑一种电压图，其中，图的特定位的置 1 是通过电压分配来确定的，比如，一种叫做电压群的元素分配，对应于基图的边，从而代数置 1。这种置 1 的代数特性是一种分析一些图性质的有力工具，产生的上升特性使用基图的性质。在本文中，这个工具被用于适合电压图译码的码，从而有利于研究他们的图的性能。本文的结构如下，我们介绍了在第二部分的初步定义和符号，特别是，我们回顾了电压图的术语。在第三部分中，我们展示了如何从电压图用代数法获得基于图的码，并且举了这种使用 SFT LDPC 码和阵列 LDPC 码作为例子。在第四部分中，介绍了 abelian-inevitable 圈的概念，在 LDPC Ta
4、nner 图中用于产生这些圈的同构子图类（相当于矩阵子结构）被定义和分类。这里给出的结果是正确的，并且以后将对这项工作从【16 】进行延伸。在第五部分中概述了目前正在进行的工作是如何将这个方法应用于构造新的 LDPC 和其他基于图的代码。2. PRELIMINARIES二进制低密度奇偶校验（LDPC）码是用稀疏校验矩阵 H 来定义的，或者是通过与 H 相关联的 Tanner 图。左边和右边的顶点分别称为变量节点和校验节点。所有的码字是每个校验节点对变量节点的二进制分配，变量节点与校验节点连线条数的总和模 2 等于 0。在伪码字的解释中，覆盖图的概念用来分析基于图的迭代解码器11, 14, 17
5、, 25.在一个完全不同的背景下，不同的研究者通过对特殊的已选的基图进行随机置 1 或者原模图产生所谓的原模图代码来构造 LDPC 码家族 24, 6, 7, 19。用在这些构造的思想是这些基图的属性可能揭示了覆盖图的属性，并由此揭示了生成代码的属性。事实上，随机构造法已经被大量研究过（比如，见18, 1, 2）。虽然随机构造法构造的码已经展现出了良好的性能，但是我们相信用代数法构造的码可以在很多方面优于用随机构造法，比如能够良好地处理代码性能，最短距离，围长，停止集和伪码字。1970s Gross 和 Tucker 提出了一种具体覆盖空间图的代数法构架。给出一个图 X=(VX，E X)，其中
6、 X 在每边都有一个正方向和负方向，函数 叫做普通电压分配，把正方向的边映射到叫做电压组的一个选定的有限的组 G 中的一个元素。每条边负方向的电压和正方向的电压是相反的元素。基图 X 和函数 叫做普通电压图。 在每条边的值就是电压。一种新的 X 图，叫做（右）导出图，是 X 的一个|g| 度，顶点设为 VX， ，边设为 EXXG,如果在 X 中（u ，v）是一条正方向的边,电压 h G,那么对于每一 g G，在 X 中都有一条边从(u,g) 映射到 (v,gh)。图 1 显示了对每条边分配电压的基图 X，从添加剂组整数模 5（比如 G=Z/5Z)，从这种电压分配获得相应的右导出图。电压组是 n
7、 元素的对称组 Sn，在这种情况下，也可以把 (X,)对看成是置换电压组。置换导出图 X 具有顶点集 VX1,.,n 和边集 EX 1,.,n.如果 Sn 是 X 边 e = (u,v)的置换电压，那么在 X 中存在 (u,i) 和(v,(i) 一一对应，其中 i=0,1,2.n。需要注意的是 X 是 X 的 n 度而不是 n！看作是一个普通的导出图如上所述。用 e+ 、e -分别表示边 e 的正方向和负方向。在电压配置为 的电压图中，Walk 可以表示带方向边的遍历的结果，比如 ，其中 i 可正科负，是 G 中的边。在这种设置中，walk W 的网电压被定义为 W 的各条边按顺序的电压的电压
8、组乘积 。例如，在图 1 电压图中 Walk 的网电压为 0-2-0+1=1=4 Z/5Z。下面的一些定理是很有用的。定理 2.1：让 W 是一个游动的 X 电压图首次公开发行（IPO ），然后每个顶点顶点V（v， g）gG（x 有一个独特的游走在 X 是 W G（v，g）在起飞计划到 W W = E11e2enn 是闭的， backtrackless 和 tailless。然后任何 W G，gG，是一个循环如果只在 X 和电压如果网 W 是认 G。电压图已被成功地用于获得很多具有极值特性图的实例；看到 9 ， 4 ， 5 ， 3 。3、使用电压术语描述码我们现在分别描述在22, 23, 10
9、 和8中提出的三类流行的准循环LDPC 码，并且展示如何通过电压图翻译这些码。A. SFT 码22, 23q 是素数，integers ， 0,1，q1 非自由场此外，我和 Q 的乘积模，即，有限域 f q。非零元素组成的循环 multiplicative f q（）Q 的 Q - 1）阶。设 J 和 K 因子是不同的）设 A 和 B 是 q1 元素和 fQ 与订单（a）= K 和（b）= J，分别。JK 表的Q P F 上矩阵它已经在（S， T）的输入 P，S，T = b（s1）（t1 ），1sj 和t1。在 LDPC 码的奇偶校验是由指定的处理研究特别是用矩阵 H，H JK）式阵列下面的循
10、环子矩阵如图所示：其中 Ix 是一个循环 Q Q 矩阵的行身份左移 X 位置。循环子矩阵在位置（ s，t）在 H 是通过循环移位了一排排的身份矩阵左 P S，T 的地方。的生成的二进制奇偶校验矩阵大小JQKQ，这意味着相关的代码有一个速率 R1（J / K）。的码构造准循环与使用这种技术期 K，即，一个码字的循环移位的位置在每一个循环子矩阵 K 块（其中每个块由 Q 码位）在另一个码字的结果。示例：3.1 155,64,20 SFT 的代码集（ Q = Q = 31）：31、K 和 J = 5 = 3。然后我们可以乘 b25，F 大调 31 有一个（a）和（b）= k = j 和奇偶校验矩阵给
11、出了用其中 Ix 是一个 3131 是一个具有行移身份矩阵通过循环的 X 位置的左边。如图 2 所示，在 15 ，Tanner 图此代码可以被看作是派生图产生在完全二部置换的电压分配图 3 和 5 K 3 右左节点，其中的电压任务来自对称群 S 31 31 元素，和电压排列的元素产量的变化作为建筑了。例如，进入我的 5 T 2 的奇偶校验矩阵对应的要求一些MOD（Q）单独的走就是边的遍历，不带电压值-走的网电压 S 号左节点之间的边缘，S = 0，4，和T 日正确的节点，T = 0,1,2 在基础图 K 3,5 和电压相当于一个置换元素，产生一个循环移位2 的 5（mod 31）。因此，我 1
12、 对应的循环矩阵对电压元件（1 2 331）31 分从 0 日至0 日左边缘节点对节点 K 3。循环我 2 对应的元素（电压）（1 3 5 7 931 2 4 630）31 分配到边缘从 1 日左节点 k 二 0 日右节点等在。B、阵列 LDPC 码在 10 引进了阵列 LDPC 码。我们展现了这种构架并且解释了如何用直接译码的方式用置换电压导出图来翻译这些结构化的码。 对于一个素数 q 和正整数 JQ，阵列码的的奇偶校验矩阵 H 定义为其中 I 是 qXq 单位阵，P=I q-1 是单位阵右循环移动一位得到的。阵列吗是码长 N=q2 码率的准循环码。上述码的 Tanner 图可以通过基于置换
13、电压图 Kj,q 的电压配置获得， Kj,q 是关于左顶点 q 和右顶点 j 的完整的二分图。在 Kj,q 中 连接左节点 Sth 和右节点 tth 的边是 ts 的置换，其中 0 s q1 ， 0 t j1， = (1 2 3 . q)是对称组 Sq 的置换， ts 是 置换 ts 次得到的。为了得到一种更高效的编码，Eleftheriou 等人提出了上述结构码的模型。阵列码的模型是用奇偶校验矩阵 H(q,j,k)来定义的，其中 q j 3G。因此，在任何情况下，我们有 N3G，对定理的证明。5、正在进行的工作我们目前正在应用此电压图分析理解派生图以及其他的特性结果基于图论码的影响。同时同时，我们研究了 LDPC 码的结构特定的电压分配。我们正在考虑一个电压组序列的基础图中的应用同时还利用塔组电压组应用于一个具体的基准图生成这些家庭 LDPC 码。该技术可能产生新的代码完善现有的结构如 SFT 代码，基于阵列码，和其他家庭。我们的初步结果表明，采用适当的非阿贝尔群电压分配可能产生更好的代码。这部小说电压图的方法并不局限于 LDPC 码；而，它可以应用于其它图的代数基础设计代码如 Turbo 码，重复累积码，串行 级联码，等。事实上，重复一些构造累积码有偏移的功能可以是相关的电压分配函数。致谢第二作者的工作是支持部分由美国国家科学基金会资助 dms-0602332。参考文献
