纠错码综述

计算机网络 检错码与纠错码

在通信系统中广泛应用的差错控制技术是差错控制编码技术。而差错控制编码包括检错码和纠错码两种，其中检错码是为传输的数据信号增加冗余码，以便发现数据信号中的错码，但不能纠正错码；纠错码是为传输的数据信号增加冗余码，以便发现数据信号中的错码，并自动纠正这些错码。下面介绍几种检错码和纠错码的校验方法。

1．奇偶校验码

奇偶校验码是一种最简单的无纠错能力的检错码，其编码规则是先将数据代码分组，例如，将ASCⅡ码中的一个字符或若干个字符分为一组。在各组数据后面附加一位校验位，使该数据连校验位在内的码元中1的个数恒为偶数则为偶校验，恒为奇数则为奇校验。奇偶校验无纠错能力，它只能检测出码元中的任意奇数个错误，若有偶数个错误必定漏检。由于奇偶校验码容易实现，所以当信道干扰较弱，并且数据码长较短时，使用奇偶校验码效果很好，在计算机网络的数据传输中经常使用该检错码。

根据数据代码的分组方法，奇偶校验码可以分为水平奇偶校验、垂直奇偶校验和垂直水平奇偶校验。

 水平奇偶校验

如表3-1所示，在水平奇偶校验中，把数据先以适当的长度划分成小组，并把码元按表中所示的顺序一列一列地排列起来，然后对水平方向的码元进行奇偶校验，得到一列校验位，附加在其他各列之后，最后按行的顺序进行传输。水平奇偶校验能查出水平方向上奇数个错误和不大于数据代码长度的突发错误，无纠错能力，但产生校验码及校验逻辑相对复杂。

表 3-1 水平奇偶校验

位 码元 偶校验位 1 2 3 4 5 6 7 8 9 10

1 1 0 0 1 1 1 0 0 0 1 1

2 0 1 1 0 1 0 1 0 1 0 1

3 1 1 0 1 1 0 0 0 0 1 1

4 0 0 1 1 1 0 0 0 1 0 0

5 1 1 1 0 1 1 1 1 0 1

0

 垂直奇偶校验

如表3-2所示，在垂直奇偶校验中，把数据先以适当的长度划分成小组，并把码元按表中所示的顺序一列一列地排列起来，然后对垂直方向的码元进行奇偶校验，得到一行校验位，附加在其他各行之后，然后按列的顺序进行传输。垂直奇偶校验能够查出列上的奇数个错误，只能查处50%的突发错误，无纠错能力，但产生校验码及校验逻辑相对简单。

第２卷第１１期　２０１６年１１月　网络与信息安全学报　Ｃｈｉｎｅｓｅ　Ｊｏｕｍａｌ　ｏｆＮｅｔｗｏｒｋ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　、，０１．２　Ｎｏ．１ｌ　Ｎｏｖｅｍｂｅｒ　２０１６　基于纠错码的数字签名技术综述　任方　，一，郑东　，范九伦　（１．西安邮电大学无线网络安全技术国家工程实验室，陕西西安７１０１２１　２．西安邮电大学通信与信息工程学院，陕西西安７１０１２１）　摘要：量子算法的出现对当前广泛使用的基于数论困难问题的数字签名算法造成了严重威胁，而基于纠错　码的数字签名算法可以抵抗已知的量子算法攻击，近年来，得到了众多研究者的关注，成为最有发展潜力的　数字签名技术之一。基于纠错码的数字签名算法具有较高的安全性和较快的运算速度，其研究成果遍及普通　签名、盲签名、环签名、群签名等多个领域。对基于纠错码的数字签名技术进行了综述，分析和评价了当前　的主流算法，并指出未来可能的研究方向。　关键词：纠错码；数字签名；校验子译码；后量子密码　中图分类号：ＴＰ３０９．２　文献标识码：Ａ　ｄｏｉ：１０．１１９５９／ｊ．ｉｓｓｎ．２０９６－１０９ｘ．２０１６．００１０８　Ｓｕｒｖｅｙ　ｏｆ　ｄｉｇｉｔａｌ　ｓｉｇｎａｔｕｒｅ　ｔｅｃｈｎｏｌｏｇｙ　ｂａｓｅｄ　ｏｎ　ｅｒｒｏｒ　ｃｏｒｒｅｃｔｉｎｇ　ｃｏｄｅｓ　ＲＥＮ　Ｆａｎｇ　，一，ＺＨＥＮＧ　Ｄｏｎｇ　，ＦＡＮ　Ｊｉｕ—ｌｕｎ　（１．ＮａｔｉｏｎａｌＥｎｇｉｎｅｅｒｉｎｇＬａｂｏｒａｔｏｒｙｆｏｒＷｉｒｅｌｅｓｓ　Ｓｅｃｕｒｉｔｙ，Ｘｉ’ａｌｌＵｎｉｖｅｒｓｉｔｙｏｆＰｏｓｔｓ　ａｎｄＴｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｘｉ’ａｎ　７１０１２１，Ｃｈｉｎａ；　２．Ｄｅｐａｒｔｍｅｎｔ　ｏｆＣｏｍｍｕｎｉｃａｔｉｏｎ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｘｉ’ａｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆＰｏｓｔｓ　ａｎｄ　Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｘｉ’ａｎ　７１０１２１，Ｃｈｍａ）　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｅｍｅｒｇｅｎｃｅ　ｏｆ　ｑｕａｎｔｕｍ　ａｌｇｏｒｉｔｈｍｓ　ｈａｖｅ　ｔｈｒｅａｔｅｎｅｄ　ｔｈｅ　ｓｅｃｕｒｉｔｙ　ｏｆ　ｄｉｇｉｔａｌ　ｓｉｇｎａｔｕｒｅ　ａｌｇｏｒｉｔｈｍｓ　ｗｉｄｅｌｙ　ｕｓｅｄ　ｃｕｒｒｅｎｔｌｙ，ｍｏｓｔ　ｏｆ　ｗｈｉｃｈ　ｂａｓｅｄ　ｏｎ　ｓｏｍｅ　ｈａｒｄ　ｐｒｏｂｌｅｍｓ　ｉｎ　ｎｕｍｂｅｒ　ｔｈｅｏｒｙ．Ｔｈｅ　ｄｉｇｉｔａｌ　ｓｉｇｎａｔｕｒｅ　ａｌｇｏｒｉｔｈｍｓ　ｂａｓｅｄ　ｏｎ　ｅｒｒｏｒ　ｃｏｒｒｅｃｔｉｎｇ　ｃｏｄｅｓ，ｗｈｉｃｈ　ｃａｌｌ　ｒｅｓｉｓｔ　ｑｕａｎｔｕｍ　ａｔｔａｃｋ，ｈａｓ　ｂｅｅｎ　ｓｔｕｄｉｅｄ　ｂｙ　ｍａｎｙ　ｒｅｓｅａｒｃｈｅｒｓ　ｉｎ　ｒｅｃｅｎｔ　ｙｅａｒｓ　ａｎｄ　ｔｈｅｒｅ　ｈａｖｅ　ｂｅｅｎ　ｍａｎｙ　ｒｅｓｅａｒｃｈ　ｒｅｓｕｌｔｓ　ｉｎ　ｄｉｆｆｅｒｅｎｔ　ａｒｅａｓ，ｓｕｃｈ　ａｓ　ｎｏｒｍａｌ　ｄｉｇｉｔａｌ　ｓｉｇｎａｔｕｒｅ，ｂｌｉｎｄ　ｓｉｇｎａｔｕｒｅ，ｒｉｎｇ　ｓｉｇ－　ｎａｔｕｒｅ，ｇｒｏｕｐ　ｓｉｇｎａｔｕｒｅ．Ｂｅｃａｕｓｅ　ｏｆ　ｔｈｅ　ｆａｓｔ　ｃｏｍｐｕｔａｔｉｏｎ　ｓｐｅｅｄ　ａｎｄ　ｈｉｇｈ　ｓｅｃｕｒｉｔｙ，ｉｔ　ｈａｓ　ｂｅｃｏｍｅ　ｏｎｅ　ｏｆ　ｔｈｅ　ｍｏｓｔ　ｐｒｏｍｉｓｉｎｇ　ｄｉｇｉｔａｌ　ｓｉｇｎａｔｕｒｅ　ｔｅｃｈｎｏｌｏｇｉｅｓ．Ａ　ｃｏｍｐｒｅｈｅｎｓｉｖｅ　ｉｎｔｒｏｄｕｃｔｉｏｎ　ｗａｓ　ｇｉｖｅｎ　ａｎｄ　ｄｉｇｉｔａｌ　ｓｉｇｎａｔｕｒｅ　ｔｅｃｈｎｏｌｏｇｉｅｓ　ｂａｓｅｄ　ｏｎ　ｅｒｒｏｒ　ｃｏｒｒｅｃｔｉｎｇ　ｃｏｄｅｓ　ｗｅｒｅ　ｓｕｍｍａｒｉｚｅｄ，ｔｈｅ　ｋｅｙ　ｔｅｃｈｎｏｌｏｇｉｅｓ　ｗｅｒｅ　ａｎａｌｙｚｅｄ　ａｎｄ　ｔｈｅ　ｐｏｓｓｉｂｌｅ　ｒｅｓｅａｒｃｈ　ｄｉ－　ｒｅｃｔｉｏｎｓ　ｉｎ　ｔｈｅ　ｆｕｔｕｒｅ　ｗｅｒｅ　ｐｏｉｎｔｅｄ　ｏｕｔ．　Ｋｅｙ　ｗｏｒｄｓ：ｅｒｒｏｒ　ｃｏｒｒｅｃｔｉｎｇ　ｃｏｄｅｓ，ｄｉｇｉｔａｌ　ｓｉｇｎａｔｕｒｅ，ｓｙｎｄｒｏｍｅ　ｄｅｃｏｄｉｎｇ，ｐｏｓｔ　ｑｕａｎｔｕｍ　ｃｒｙｐｔｏｇｒａｐｈｙ　言　嚣妻　暑　公钥密码与数字签名技术　。　出现于２０世纪　了大量重要的成果，成为密码领域发展最为蓬勃　收稿日期；２０１６．０９．１２；修回日期：２０１６．１０—１９。通信作者：任方，ｒｅｎｆａｎｇ　＠　．．８１　１６３　ｃｏｒｎ　基金项目：国家自然科学基金资助项目（Ｎｏ．６１２７２０３７，Ｎｏ．６１４７２４７２）；陕西省自然科学基础研究计划基金资助项目　（Ｎｏ．２０１５ＪＱ６２６２）；陕西省教育厅专项科研计划基金资助项目（Ｎｏ．１５ＪＫ１６６９）　Ｆｏｕｎｄａｔｉｏｎ　Ｉｔｅｍｓ：Ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｉｎａ（Ｎｏ．６１２７２０３７，Ｎｏ．６１４７２４７２），Ｔｈｅ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｂａｓｉｃ　Ｒｅｓｅａｒｃｈ　Ｐｌａｎ　ｏｆ　Ｓｈａａｎｘｉ　Ｐｒｏｖｉｎｃｅ（Ｎｏ．２０１５ＪＱ６２６２），Ｓｃｉｅｎｔｉｆｉｃ　Ｒｅｓｅａｒｃｈ　Ｐｒｏｇｒａｍ　Ｆｕｎｄｅｄ　ｂｙ　Ｓｈａａｎｘｉ　Ｐｒｏｖｉｎｃｉａｌ　Ｅｄｕｃａ—　ｔｉｏｎ　Ｄｅｐａｒｔｍｅｎｔ（Ｎｏ．１５ＪＫ１６６９）　

第３１卷第１期　

Ｖｎｌ３ｌ　Ｎｏ．１　长春师范学院学报（人文社会科学版）　

Ｊｏｕｒｎａｌ　ｏｆ　Ｃｈａｎｇｃｈｕｎ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ（Ｈｕｍａｎｉｔｉｅｓ　ａｎｄ　Ｓｏｃｉａｌ　Ｓｃｉｅｎｃｅｓ）　２０１２年１月　

Ｊａｎ．２０ｌ２　

交互理论与教师纠错性反馈综述　

周舒怡　

（兰州商学院外语学院，甘肃兰州７３００２０）　

［摘要】语言教学过程是信息双边传递的过程，在语言学习和教学过程中如能将语言输入、语言输出　

和有效反馈三者结合在一起，教和学的效果将会更好。本文着重从交互理论角度出发阐述教师纠错性　

反馈的必要性、教师纠错反馈类型和实施纠错过程中的注意事项。　［关键词】交互性理论；纠错性反馈；明确纠错；重铸；形式协商法　

［中图分类号】Ｈ３１９　【文献标识码】Ａ　［文章编号】１００８—１７８Ｘ（２０１２）０１—０１６３—０２　

关于二语习得的较有影响的理论大致可以分为三类：强调外在语言环境作用的理论；强调语言习得先　

天性的理论；强调内在语言习得机制和外在语言环境因素相互影响的理论。传统的环境论是以“行为主义　

理论”为基础的，认为语言习得取决于外部环境，语言习得是一种行为形成的过程。２Ｏ世纪６０年代以后，　

大部分研究者对语言环境在语言习得中所起作用的看法发生了根本性的变化，　“先天论”成为主流理论。　

至２０世纪８０年代，在对“先天论”进一步补充和完善的基础上，交互式学习理念开始兴起。交互假说的　

核心理念是参与教学活动的对象和要素通过相互交流和互动来进行活动，从而促进二语习得的发生。这种　

言语互动的过程包括教师向学生呈现学习内容、向学生提出问题、对学生回答做出反馈、向学生发出活动　

指令等。总之，师生互动的过程是一个语言输入、语言输出、教师反馈和语言输入循环往复的动态过程。　

鉴于课堂互动中教师话语在语言教学中所起的重要作用，以辛克莱为首的伯明翰学派从１９７０年起便开始系　

统地研究课堂上的语言交流，并得出了教师与学生回话的Ｉ—Ｒ—Ｆ结构（ｉｎｉｔｉａｔｉｏｎ—ｒｅｓｐｏｎｓｅ—ｆｅｅｄｂａｃｋ）。其中　

1 / 6

信道编码综述

学院：

学号：

姓名：

2013年11月13日 2 / 6

信道编码综述

摘要：信道编码是通过信道编码器和译码器实现的用于提高信道可靠性的理论和方法。本文综合概述了信道编码的历史背景、要求和编码的基本原理。

关键词：信道编码；历史背景；基本原理

0 引言：

随着现代通信技术和计算机技术的迅速发展，每天都在不断涌现新的通信业务和信息业务，同时用户对通信质量、数据传输速率和可靠性的要求也在不断提高。数字信号在传输中往往由于各种原因，使得在传送的数据流中产生误码，从而使接收端产生图象跳跃、不连续、出现马赛克等现象。所以通过信道编码这一环节，对数码流进行相应的处理，使系统具有一定的纠错能力和抗干扰能力，可极大地避免码流传送中误码的发生。提高数据传输效率，降低误码率是信道编码的任务。信道编码的本质是增加通信的可靠性。随着信道编码理论和数字通信技术不断发展，信道编码技术会在通信工程领域得到越来越广泛的应用。

1 信道编码技术的发展史

1948年，Bell实验室的C.E.Shannon发表的《通信的数学理论》，是关于现代信息理论的奠基性论文，它的发表标志着信息与编码理论这一学科的创立。Shannon在该文中指出，任何一个通信信道都有确定的信道容量C，如果通信系统所要求的传输速率R小于C，则存在一种编码方法，当码长n充分大并应用最大似然译码（MLD，Maximum Likelihood Decoding）时，信息的错误概率可以达到任意小。

Shannon指出了可以通过差错控制码在信息传输速率不大于信道容量的前提下实现可靠通信，但却没有给出具体实现差错控制编码的方法。20世纪40年代，R.Hamming和M.Golay提出了第一个实用的差错控制编码方案，使编码理论这个应用数学分支的发展得到了极大的推动。通常认为是R.Hamming提出了第一个差错控制码。汉明码是在原编码的基础上附加一部分代码，使其满足纠错码的条件。它属于线性分组码，由于线性码的编码和译码能轻易实现，至今仍是3 / 6 应用最广泛的一类码。汉明码的抗干扰能力较强，但付出的代价也很大，比如8bite汉明码有效信息只有总编码长度的一半，可以纠正1个差错发现2个差错，就要加大码距，使代码冗余度大大增加，通信效率下降。