低密度奇偶校验.docx

低密度奇偶校验码 莎拉 .J.约翰逊电气工程和计算机科学学院纽卡斯尔大学 澳大利亚电子邮件：.au专题 1： 低密度奇偶校验码1.1 简介低密度奇偶校验码（LDPC）是一种前向纠错码，首次在在麻省理工学院的 Gallager 1962 博士学位论文被提出。当时，他们令人难以置信的潜力仍未被发现，由于计算的要求还处于电子管被第一个晶体管取代的时代。在过去 35 年，他们仍然很大程度上被忽视。在平均时间的前向纠错中占主导地位的高度结构化的代数块和卷积码。尽管这些代码实用获得巨大成功，但其表现远低于香农在其1948年文章中讲的极限容量。到20 世纪 80 年代晚期，尽管经过几十年的努力,研究人员大大臣服于看似不可逾越的theory-practice差距。 相对静止的编码字段被彻底改变了，引入“涡轮码”被Berrou,Glavieux，Thitimajshima提出。1993年,在所有成功的纠错编码的关键因素替换:涡轮码涉及很少的代数,采用迭代,分配平均算法,重点(而不是最坏的)性能、和依靠软(或概率)信息提取从通道。一夜之间,是香农极限的差距是淘汰,使用解码器和可控的复杂性。1990年代研究人员努力通过理解为什么涡轮代码以及他们所做的工作,两位研究者,麦凯和尼尔,介绍一种新的分组码设计拥有许多的特点新涡轮码。很快就认识到,这些分组码实际上是一个重新发现Gallager年前开发的LDPC码。事实上,算法用于解码涡轮码随后被证明是一个特殊的LDPC码的译码算法。新的概括Gallager LDPC码的研究人员,包括露比,米成马赫一起Shokrollahi Spielman,理查森和Urbanke,产生新的不规则LDPC码容易表现最好的涡轮码,以及提供一些实用的优点,可以说清洁设置理论结果。今天,对LDPC码设计技术存在,使代码的构造接近香农的能力。这一领域进步快速,今天在许多编码理论从其国家十年前方式认不出来了。除了很强的LDPC码的理论兴趣,这样的代码已经被采用卫星数字视频广播和长途光通信标准,极有可能采用IEEE无线局域网标准,并考虑运用于长期进化的第三代移动电话1.2 使用奇偶校验纠错在这里,我们只会考虑二进制消息的传播消息由0和1的字符串。转发错误控制编码的基本思想是增强这些消息和故意引入冗余比特吗额外的检查部分的形式产生一个消息的代码字。这些检查部分添加的方式密语是足够的另一个传播的消息可以在接收方正确推断,即使一些位代号在传输过程中在通道中损坏。 尽可能简单的编码方案是一个奇偶校验码(SPC)。程控涉及添加一个额外的位二进制信息,的价值取决于比特的信息。在一个更平价代码中,额外添加到每个消息确保1 s在每个偶数代号。示例1.1.7-位的字母的 ASCII 字符串 S 是1010011，和奇偶校验位是要添加作为第八位。字符串 S 已经有偶数个部分 (即四个） 和奇偶校验位的值是 0，和的码字为 S 是 10100110.更正式，为7-位 ASCII 加偶校验的代码我们一个代码 dene-wordc具有以下结构： c = c1 c2 c3 c4 c5 c6 c7 c8,在每个c我要么是0或1，和约束每一个码字 satisesc1 c2 c3 c4 c5 c6 c7 c8 = 0. ( 1.1)方程 (1.1) 被称为奇偶校验方程，在其中，符号 代表发言-模支架-2另外。示例1.2.A7-位 ASCII 字母编码与单奇偶校验检查代码从考试-ple 1.1。由此产生的码字是发送虽然有噪声信道和字符串y = 1 0 0 1 0 0 1 0收到了。要检查是否 y 是我们测试有效码字 ywith (1.1)。y1 y2 y3 y4 y5 y6 y7 y8 = 1 0 0 1 0 0 1 0 = 1。 由于总和是 1，奇偶校验方程不是 satised 和y不是有效码字。我们检测到至少一个错误发生在期间传输。虽然单个位的反演由于信道噪声很容易被检测到用一个奇偶校验码,这个代码不是强大表明这一点,或者事实上,倒。此外,由于任何偶数位倒置,产生一系列满足约束条件(1.1)模式甚至通过这个简单的代码数量的错误不被发现。示例1.3.代码C包括所有长度六个字符串c = c1 c2 c3 c4 c5 c6,其中满足所有三个奇偶校验方程：c1 c2 c4 = 0c2 c3 c5 = 0c1 c2 c3 c6 = 0 (1.2) 码字的限制往往都写在矩阵形式，所以约束(1.2) 成为矩阵H称为parity-check矩阵。每一行的对应H的parity-check方程和每一列对应于一点的代号。因此,对于一个二进制代码与m parity-check约束和长度n密语parity-check矩阵是一个二进制矩阵mn。在矩阵形式字符串y =c1 c2 c3 c4 c5 c6)是一个有效的代码与parity-check代号矩阵H当且仅当它满足矩阵方程H yT= 0.（ 1.4）1.2.1编码为了区分消息的代码字位,奇偶校验位的例子1.3我们重写代码parity-check约束,这样每一个解决不同的代码字位。示例1.4.从示例 1.3 代码约束可以作为重新写入c4c =1 c2c5c =2 c3c6c =1 c2 c代码字位c1,c2,c3包含三位消息,c1,c2,c3,c4代码字部分,c5、c6包含三个parity-check碎片。这种方式编写的代码字约束展示如何编码的消息。示例1.5.使用消息的 (1.5) 中的约束110生成奇偶校验位c41 = 1 = 0，c51 = 0 = 1，c61 = 1 0 = 0，此消息的码字是如此c = 1 1 0 0 1 0.再次这些约束可以写矩阵形式，如下所示：在矩阵G代码的生成矩阵。信息比特常规标签由u =u1,u2,英国,向量u保存在哪里k的消息部分。因此,c代码字对应于二进制信息u =u1u2u3可以找到使用矩阵方程 c = uG (1.7)与k消息位二进制代码和长度n密语生成器矩阵,G,kn二进制矩阵。k / n比率被称为代码的速度。代码与k消息部分包含2 k密语。这些密语总可能的子集2二进制向量长度n。示例1.6.代的每个238 =不同的邮件c1c2c3= 000、 001、.、 111到以下设置的重码的代码从方程 (1.7) 收益率1.3 的示例：0 0 0 0 0 00 0 1 0 1 10 1 0 1 1 10 1 1 1 0 01 0 0 1 0 11 0 1 1 1 01 1 0 0 1 01 1 1 0 0 1 （1.8） 这段代码被称为系统因为第一次k代码字位包含信息位。系统码的生成矩阵包含了kk身份、动力学、矩阵作为其前k列。(单位矩阵、本土知识是kk方阵二进制矩阵与对角 1 条目的左上角右下角和其他地方 0 条目。)A 发电机矩阵与奇偶校验矩阵的代码H可以通过找到对执行高斯约旦消除H若要获取该窗体中H = A、nk , (1.9)凡A是(n k) k 二进制矩阵和我nk 是恒等矩阵n k 。发电机矩阵然后是G = Ik、T . (1.10)h . G的行空间正交因此如果G的生成矩阵代码与parity-check矩H GHT= 0.之前结束这一节中,我们注意到一块代码可以被描述超过一套parity-check约束。一组约束是有效的方程(1.4)的代码提供了适用于所有的密语代码。低密度parity-check码parity-check矩阵的选择特别重要。1.2.2错误检测和更正假设一个代号已下放一个二进制对称信道和一个以上的代码字位可能是翻。任务大纲部分和下面的,是发现任何翻比特和,如果可能的话,正确的他们。首先,我们知道,每一个代码字代码中必须满足(1.4),等可以检测到任何错误收到的话并不满足这个方程。1.8的例子演示了代码块的使用检测传输错误,但假设通道甚至吵着和三位了产生的字符串y =0 0 1 0 1 1。替换成(1.4)告诉我们,y是一个有效的代码字,所以我们不能检测的传输错误呢发生。一般来说,一个分组码只能检测一组位错误,如果错误不改变一个代号到另一个。 两个编码词之间的汉明距离被定义为的数量有些职位,他们是不同的。例如密语1 0 1 0 0 1 1 0和(1 0 0 0 0 1 1 1)在两个不同位置,第三和八个代号位,因此它们之间的汉明距离是两个。测量能力代码检测错误的最小汉明距离或只是最低码的距离。一个代码的最小距离,dmin,定义为最小汉明距离任何一对 t dmin. 在一般情况下,代码与最小距离dmin,e翻转可以被选择最近的代码字只要纠正e(dmin1)/ 2。在?x?最多x是最大的整数。代码越小速度越小的2 n二进制向量子集密语,所以更好的可以达到的最小距离吗通过代码长度n。最小距离的代码的重要性定其性能反映在分组码的的描述三个参数(n,k,dmin)。 误差校正通过直接比较每一个接收到的字符串代码中的代码字,选择最接近的,称为最大似然解码,因为它是保证返回最可能的代号。然而,这样一个穷举搜索是可行的,只有当k很小。为规范与成千上万的信息比特代码字变得太计算昂贵的直接比较接收到的字符串2 k的每一个人在代码中密语。许多巧妙的解决方案被提出使这个任务不那么复杂,包括选择和利用代数编码其结构加快解码或者,至于LDPC码,设计解码方法不毫升,但可以执行很好得多降低复杂性。1.3低密度parity-check(LDPC)码顾名思义,LDPC码与parity-check矩阵分组码这只包含一个非常少量的非零项。这是稀疏的H既保证解码的复杂性,只有线性增加与代码长度和最小距离也线性增加代码长度。除了要求H是稀疏的,并通过代码本身也不例外其他代码块。事实上现有的分组码可以成功使用的LDPC迭代译码算法是否可以用一个稀疏parity-check矩阵。然而,一般来说,找到一个稀疏parity-check矩阵为现有的代码是不实际的。而不是LDPC码设计的构造一个稀疏parity-check矩阵,然后确定一个发电机矩阵的代码. LDPC码和古典分组码的最大区别他们是如何解码。古典分组码通常与ML解码解码算法,通常短和代数而设计的这个任务不那么复杂。然而LDPC码迭代译码使用图形表示的parity-check矩阵和设计也是如此H的属性作为焦点。 一个LDPC码parity-check矩阵被称为(wc,wr)-regular如果每个代码包含在固定数量,wc,和每个parity-check奇偶校验检查方程包含固定数量,wr,代码部分。示例1.8.码字c = 1 0 1 1 1 0从代码中的示例 1.3 是通过发送二进制对称信道和字符串y = 1 0 1 0 1 0收到。代入方程 (1.4) 给出结果是零，那么该