第一章序论 >编码理论的内容包括三个方面 ◆以保证数字信息传输和处理的可靠性为目的的差错控制编 码(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
>汉明码和Golay码都是将q元符号按每k个分为一组.然后通 过编码得到-k个q元符号作为冗余校验符号，最后组成码长 为n的码字。分组码编码码率为k/n,一般记为(q,n,k,t)码，t 为纠错能力。二元分组码可以简记为(n,k,)码或者(n,k)码。 >Golay码之后最主要的一类分组码就是Reed-Muller码。它是 Muller在1954年提出的，此后Reed在Muller提出的分组码的 基础上得到了一种新的分组码，称为Reed-Muller码，简记 为RM码。在1969年到1977年之间，RM码在火星探测方面 得到了极为广泛的应用。即使在今天，RM码也具有很大的 研究价值，其快速的译码算法非常适合于光纤通信系统。 10
汉明码和Golay码都是将q元符号按每k个分为一组．然后通 过编码得到n-k个q元符号作为冗余校验符号，最后组成码长 为n的码字。分组码编码码率为k/n，一般记为(q,n,k,t)码，t 为纠错能力。二元分组码可以简记为(n,k,t)码或者(n,k)码。 Golay码之后最主要的一类分组码就是Reed-Muller码。它是 Muller在1954年提出的，此后Reed在Muller提出的分组码的 基础上得到了一种新的分组码，称为Reed-Muller码，简记 为RM码。在1969年到1977年之间，RM码在火星探测方面 得到了极为广泛的应用。即使在今天，RM码也具有很大的 研究价值，其快速的译码算法非常适合于光纤通信系统。 10
>RM码之后人们又提出了循环码的概念。循环码是分组码的 一种，但它的码字具有循环移位特性，即码字比特经过循环 移位后仍然是码字集合中的码字。这种循环结构大大简化了 编译码结构。循环码的另一个特点就是它可以用一个幂次为 n-k的多项式来表示，这个多项式记为g(D),称为生成多项 式，其中D为延迟算子。 >循环码也称为循环冗余校验(CRC,Cyclic Redundancy Check)码，并且可以用Meggitt译码器来实现译码。由于 Meggitt译码器的译码复杂性随着纠错能力t的增加而呈指数 形式的增加，因此通常CRC码用于纠正只有单个错误的应用 情况，常用做检错而非纠错。 11
RM码之后人们又提出了循环码的概念。循环码是分组码的 一种，但它的码字具有循环移位特性，即码字比特经过循环 移位后仍然是码字集合中的码字。这种循环结构大大简化了 编译码结构。循环码的另一个特点就是它可以用一个幂次为 n-k的多项式来表示，这个多项式记为g(D)，称为生成多项 式，其中D为延迟算子。 循环码也称为循环冗余校验(CRC，Cyclic Redundancy Check)码，并且可以用Meggitt译码器来实现译码。由于 Meggitt译码器的译码复杂性随着纠错能力t的增加而呈指数 形式的增加，因此通常CRC码用于纠正只有单个错误的应用 情况，常用做检错而非纠错。 11
>循环码的一个非常重要的子集就是分别由 Hocquenghem在1959年、Bose和Ray- Chaudhuri研究组在1960年几乎同时提出 的BCH码，BCH码的码字长度为n=qm1, 其中m为一个整数。二元BCH码(q=2)的 纠错能力限为tk(2m.1)/2。 >1960年，Reed和Solomon将BCH码扩展到非二元 (q>2)的情况，得到了RS(Reed-Solomon)码。 1967年，Berlekamp给出了一个非常有效的译码算法后， RS码得到了广泛的应用。此后，RS码在CD播放器、 DVD播放器中得到了很好的应用。 12
循环码的一个非常重要的子集就是分别由 Hocquenghem在1959年、Bose和RayChaudhuri研究组在1960年几乎同时提出 的BCH码，BCH码的码字长度为n＝qm-1， 其中m为一个整数。二元BCH码（q=2）的 纠错能力限为t2）的情况，得到了RS（Reed-Solomon）码。 1967年，Berlekamp给出了一个非常有效的译码算法后， RS码得到了广泛的应用。此后，RS码在CD播放器、 DVD播放器中得到了很好的应用。 12
>虽然分组码在理论分析和数学描述方面已经非常成熟，并且 在实际的通信系统中也已经得到了广泛的应用，但分组码固 有的缺陷大大限制了它的进一步发展。首先，由于分组码是 面向数据块的，因此，在译码过程中必须等待整个码字全部 接收到之后才能开始进行译码。在数据块长度较大时，引入 的系统延时是非常大的。分组码的第二个缺陷是它要求精确 的帧同步，即需要对接收码字或帧的起始符号时间和相位精 确同步。另外，大多数基于代数的分组码的译码算法都是硬 判决算法，而不是对解调器输出未量化信息的软译码，从而 造成了一定程度的增益损失。 13
虽然分组码在理论分析和数学描述方面已经非常成熟，并且 在实际的通信系统中也已经得到了广泛的应用，但分组码固 有的缺陷大大限制了它的进一步发展。首先，由于分组码是 面向数据块的，因此，在译码过程中必须等待整个码字全部 接收到之后才能开始进行译码。在数据块长度较大时，引入 的系统延时是非常大的。分组码的第二个缺陷是它要求精确 的帧同步，即需要对接收码字或帧的起始符号时间和相位精 确同步。另外，大多数基于代数的分组码的译码算法都是硬 判决算法，而不是对解调器输出未量化信息的软译码，从而 造成了一定程度的增益损失。 13
>卷积码改善了分组码存在的缺点，卷积码是Elias 在1955年提出的。卷积码与分组码的不同在于： 它充分利用了各个信息块之间的相关性。通常卷 积码记为(，k,N)码。卷积码的编码过程是连续 进行的，依次连续将每k个信息元输入编码器，得 到个码元，得到的码元中的检验元不仅与本码的 信息元有关，还与以前时刻输入到编码器的信息 元有关。同样，在卷积码的译码过程中，不仅要 从本码中提取译码信息，还要充分利用以前和以 Elias,1923-2001 后时刻收到的码组.从这些码组中提取译码相关 信息，而且译码也是连续进行的，这样可以保证 卷积码的译码延时相对比较小。 14
卷积码改善了分组码存在的缺点，卷积码是Elias 在1955年提出的。卷积码与分组码的不同在于： 它充分利用了各个信息块之间的相关性。通常卷 积码记为(n，k，N)码。卷积码的编码过程是连续 进行的，依次连续将每k个信息元输入编码器，得 到n个码元，得到的码元中的检验元不仅与本码的 信息元有关，还与以前时刻输入到编码器的信息 元有关。同样，在卷积码的译码过程中，不仅要 从本码中提取译码信息，还要充分利用以前和以 后时刻收到的码组．从这些码组中提取译码相关 信息，而且译码也是连续进行的，这样可以保证 卷积码的译码延时相对比较小。 Elias, 1923-2001 14