第一章序论 >编码理论的内容包括三个方面 ◆以保证数字信息传输和处理的可靠性为目的的差错控制编 码(error-control coding),又称为信道编码（channel coding) ◆以提高数字信息传输、存储处理的有效性为宗旨的信源编 码(Source coding); ◆以增加数字信息传输、存储的安全性为目标的数据加密编 码(data encryption); >我们主要讨论差错控制编码技术。 5
第一章 序论 编码理论的内容包括三个方面 以保证数字信息传输和处理的可靠性为目的的差错控制编 码（error-control coding），又称为信道编码（channel coding）； 以提高数字信息传输、存储处理的有效性为宗旨的信源编 码（Source coding）； 以增加数字信息传输、存储的安全性为目标的数据加密编 码（data encryption）； 我们主要讨论差错控制编码技术。 5
>差错控制编码技术是适应数字通信抗噪声干 扰的需要而诞生和发展起来的，它是于1948 年、著名的信息论创始人C.E.Shannon(香 农)在贝尔系统技术杂志发表的“A Mathematical Theory of Communication"- 文，开创了一门新兴学科和理论：信息论和 编码理论。 6
差错控制编码技术是适应数字通信抗噪声干 扰的需要而诞生和发展起来的，它是于1948 年、著名的信息论创始人C. E. Shannon（香 农 ） 在贝尔系统技术杂志发表的 “ A Mathematical Theory of Communication”一 文，开创了一门新兴学科和理论：信息论和 编码理论。 6
1.1信道编码的历史及研究现状 >1948年，Shannon发表的“通信的数学理论”，标志着 信息与编码理论这一学科的创立。该文指出，任何一个通 信信道都有确定的信道容量C,如果通信系统所要求的传 输速率R小于C,则存在一种编码方法，当码长充分大并 应用最大似然译码（MLD,Maximum Likelihood Decdoding)时，信息的错误概率可以达到任意小。 MLD算法的复杂性随n或N的增加呈指数增加，因此当n或 N较大时，MLD在物理上是不可实现的。因此，构造物理 可实现编码方案及寻找有效译码算法一直是信道编码理论 与技术研究的中心任务。 > Shannon指出了可以通过差错控制码在信息传输速率不 大于信道容量的前提下实现可靠通信，但却没有给出具体 实现差错控制编码的方法。 7
1.1 信道编码的历史及研究现状 1948年，Shannon发表的“通信的数学理论” ，标志着 信息与编码理论这一学科的创立。该文指出，任何一个通 信信道都有确定的信道容量C，如果通信系统所要求的传 输速率R小于C，则存在一种编码方法，当码长n充分大并 应用最大似然译码 （ MLD ， Maximum Likelihood Decdoding）时，信息的错误概率可以达到任意小。 MLD算法的复杂性随n或N的增加呈指数增加，因此当n或 N较大时，MLD在物理上是不可实现的。因此，构造物理 可实现编码方案及寻找有效译码算法一直是信道编码理论 与技术研究的中心任务。 Shannon指出了可以通过差错控制码在信息传输速率不 大于信道容量的前提下实现可靠通信，但却没有给出具体 实现差错控制编码的方法。 7
> 20世纪40年代，R.Hamming提出了第一个实用的差 错控制编码方案。当时他作为一个数学家受雇于贝尔 实验室，主要从事弹性理论的研究。他发现计算机经 常在计算过程中出现错误，而一旦有错误发生，程序 就会停止运行。这个问题促使他编制了使计算机具有 检测错误能力的程序，通过对输入数据编码，使计算 机能够纠正这些错误并继续运行。 > Hamming,所采用的方法就是将输入数据每4个比特分 为一组，然后通过计算这些信息比特的线性组合来得 到3个校验比特，然后将得到的7个比特送入计算机。 计算机按照一定的原则读取这些码字，通过采用一定 Hamming,1915-1998 的算法，不仅能够检测到是否有错误发生，同时还可 以找到发生单个比特错误的比特的位置，该码可以纠 正7个比特中所发生的单个比特错误。这个编码方法 就是分组码的基本思想，Hamming提出的编码方案 后来被命名为汉明码。 8
20世纪40年代，R.Hamming提出了第一个实用的差 错控制编码方案。当时他作为一个数学家受雇于贝尔 实验室，主要从事弹性理论的研究。他发现计算机经 常在计算过程中出现错误，而一旦有错误发生，程序 就会停止运行。这个问题促使他编制了使计算机具有 检测错误能力的程序，通过对输入数据编码，使计算 机能够纠正这些错误并继续运行。 Hamming所采用的方法就是将输入数据每4个比特分 为一组，然后通过计算这些信息比特的线性组合来得 到3个校验比特，然后将得到的7个比特送入计算机。 计算机按照一定的原则读取这些码字，通过采用一定 的算法，不仅能够检测到是否有错误发生，同时还可 以找到发生单个比特错误的比特的位置，该码可以纠 正7个比特中所发生的单个比特错误。这个编码方法 就是分组码的基本思想，Hamming提出的编码方案 后来被命名为汉明码。 Hamming, 1915-1998 8
>虽然汉明码的思想是比较先进的，但是它也存在许多难以接 受的缺点。首先，汉明码的编码效率比较低，它每4个比特 编码就需要3个比特的冗余校验比特。另外，在一个码组中 只能纠正单个的比特错误。 >M.Goly研究了汉明码的这些缺点，并提出了两个以他自己 的名字命名的高性能码字：一个是二元Goly码，在这个码 字中Goly将信息比特每12个分为一组，编码生成11个冗余 校验比特，相应的译码算法可以纠正3个错误。另外一个是 三元Goly码，它的操作对象是三元而非二元数字。三元 Goly码将每6个三元符号分为一组，编码生成5个冗余校验 三元符号。这样由11个三元符号组成的三元Goly码码字可 以纠正2个错误。 9
虽然汉明码的思想是比较先进的，但是它也存在许多难以接 受的缺点。首先，汉明码的编码效率比较低，它每4个比特 编码就需要3个比特的冗余校验比特。另外，在一个码组中 只能纠正单个的比特错误。 M.Golay研究了汉明码的这些缺点，并提出了两个以他自己 的名字命名的高性能码字：一个是二元Golay码，在这个码 字中Golay将信息比特每12个分为一组，编码生成11个冗余 校验比特，相应的译码算法可以纠正3个错误。另外一个是 三元Golay码，它的操作对象是三元而非二元数字。三元 Golay码将每6个三元符号分为一组，编码生成5个冗余校验 三元符号。这样由11个三元符号组成的三元Golay码码字可 以纠正2个错误。 9