信道编码(差错控制编码)课件.ppt

1、5.1 5.1 信道编码基本概念信道编码基本概念5.2 5.2 几种常用的检错码几种常用的检错码5.4 5.4 循环码循环码5.5 5.5 卷积码卷积码5.3 5.3 线性分组码线性分组码5.6 5.6 交织编码交织编码本章内容小结本章内容小结 信源编码的概念信源编码的概念 差错控制编码的分类及其工作原理差错控制编码的分类及其工作原理 常用的检错码常用的检错码 线性分组码线性分组码 循环码循环码 卷积码卷积码 交织码交织码 信源编码的概念和目的信源编码的概念和目的 差错控制编码检错与纠错原理差错控制编码检错与纠错原理 汉明码及编码过程（监督矩阵和生成矩汉明码及编码过程（监督矩阵和生成矩阵）阵）

2、循环码的编译码方法循环码的编译码方法 卷积码的编解码及图解表示卷积码的编解码及图解表示 信道编码（信道编码（channel codingchannel coding）是为了提）是为了提高通信系统传输可靠性而进行的一种信号变高通信系统传输可靠性而进行的一种信号变换。换。有的文献或书籍也称其为差错控制编码、有的文献或书籍也称其为差错控制编码、纠错编码、可靠性编码或抗干扰编码等。纠错编码、可靠性编码或抗干扰编码等。本章着重分析信道编码的基本概念、常本章着重分析信道编码的基本概念、常用纠错码、线性分组码、卷积码等的构造原用纠错码、线性分组码、卷积码等的构造原理及其应用。理及其应用。差错控制编码是检错码

3、和纠错码的总称。差错控制编码是检错码和纠错码的总称。具有检测差错能力的编码称为检错码，具有检测差错能力的编码称为检错码，具有纠正差错能力的编码称为纠错码。具有纠正差错能力的编码称为纠错码。差错控制编码的基本思路：在发送端将差错控制编码的基本思路：在发送端将被传输的信息附上一些多余的码元（称为监被传输的信息附上一些多余的码元（称为监督码元），这些监督码元与信息码元之间以督码元），这些监督码元与信息码元之间以某种确定的规则相互关联（约束）。某种确定的规则相互关联（约束）。接收端则按照既定的规则校验信息码元接收端则按照既定的规则校验信息码元与监督码元之间的关系，一旦传输发生差错，与监督码元之间的关系

4、，一旦传输发生差错，信息码元与监督码元的关系就受到破坏，从信息码元与监督码元的关系就受到破坏，从而接收端可以发现错误乃至纠正错误。而接收端可以发现错误乃至纠正错误。研究各种编码和译码方法是差错控制编研究各种编码和译码方法是差错控制编码所要解决的问题。码所要解决的问题。随着差错控制编码理论的完善和数字电随着差错控制编码理论的完善和数字电路技术的发展，信道编码已经成功地应用于路技术的发展，信道编码已经成功地应用于各种通信系统中，并且在计算机、磁记录与各种通信系统中，并且在计算机、磁记录与存储中也得到日益广泛的应用。存储中也得到日益广泛的应用。差错控制的根本目的是发现传输过程中差错控制的根本目的是发

5、现传输过程中出现的差错并加以纠正。出现的差错并加以纠正。差错控制的基本工作方式主要基于两种差错控制的基本工作方式主要基于两种基本思想：一是通过抗干扰编码，使得系统基本思想：一是通过抗干扰编码，使得系统接收端译码器能发现错误并能准确地判断错接收端译码器能发现错误并能准确地判断错误的位置，从而自动纠正它们；二是在系统误的位置，从而自动纠正它们；二是在系统接收端仅能发现错误，但不知差错的确切位接收端仅能发现错误，但不知差错的确切位置，无法自动纠错，必须通过请求发送端重置，无法自动纠错，必须通过请求发送端重发等方式达到纠正错误的目的。发等方式达到纠正错误的目的。按照这些基本思想，在数字通信中，利按照这

6、些基本思想，在数字通信中，利用差错控制编码进行差错控制的基本工作方用差错控制编码进行差错控制的基本工作方式一般分为三种：检错重发、前向纠错和混式一般分为三种：检错重发、前向纠错和混合纠错，如图合纠错，如图5-15-1所示。所示。这些方法的关键是要识别或纠正传输中这些方法的关键是要识别或纠正传输中的差错。的差错。差错控制编码有多种分类方法。差错控制编码有多种分类方法。按照信息码元和附加的监督码元之间的按照信息码元和附加的监督码元之间的检验关系，差错控制编码可以分为线性码和检验关系，差错控制编码可以分为线性码和非线性码。非线性码。若信息码元与监督码元之间的关系为线若信息码元与监督码元之间的关系为线

7、性关系，则称为线性码；反之，若两者不存性关系，则称为线性码；反之，若两者不存在线性关系，则称为非线性码。在线性关系，则称为非线性码。按照信息码元和监督码元之间的约束方按照信息码元和监督码元之间的约束方式不同，差错控制编码可以分为分组码和卷式不同，差错控制编码可以分为分组码和卷积码。积码。在分组码中，编码后的码元序列每在分组码中，编码后的码元序列每n n位分位分为一组，其中为一组，其中k k个是信息码元，个是信息码元，r r个是附加的个是附加的监督码元，监督码元，rr=n nk k。监督码元仅与本码组的信息码元有关，监督码元仅与本码组的信息码元有关，而与其他码组的信息码元无关。而与其他码组的信息

8、码元无关。卷积码的编码序列也划分为码组，但监卷积码的编码序列也划分为码组，但监督码元不但与本组信息码有关，而且与前面督码元不但与本组信息码有关，而且与前面码组的信息码元也有约束关系。码组的信息码元也有约束关系。按照信息码元在编码后是否保持原来的按照信息码元在编码后是否保持原来的形式不变，差错控制编码可划分为系统码和形式不变，差错控制编码可划分为系统码和非系统码。非系统码。在差错控制编码中，通常信息码元和监在差错控制编码中，通常信息码元和监督码元在分组内有确定的位置，一般是信息督码元在分组内有确定的位置，一般是信息码元集中在码组前码元集中在码组前k k位，而监督码元集中在后位，而监督码元集中在后

9、rr=n n k k位（有时两者也可以倒置）。位（有时两者也可以倒置）。在系统码中，编码后的信息码元保持原在系统码中，编码后的信息码元保持原样不变，而非系统码中信息码元则改变了原样不变，而非系统码中信息码元则改变了原有的信号形式。有的信号形式。系统码的性能大体上与非系统码相同，系统码的性能大体上与非系统码相同，但是在某些卷积码中非系统码的性能优于系但是在某些卷积码中非系统码的性能优于系统码。统码。由于非系统码中的信息位已由于非系统码中的信息位已“面目全面目全非非”，这对观察和译码都带来麻烦，因此很，这对观察和译码都带来麻烦，因此很少使用。少使用。系统码的编码和译码相对简单些，因而系统码的编码和

10、译码相对简单些，因而得到了广泛的应用。得到了广泛的应用。按照纠正错误的类型不同，差错控制编按照纠正错误的类型不同，差错控制编码可以分为纠正随机错误的码和纠正突发错码可以分为纠正随机错误的码和纠正突发错误的码。误的码。前者主要用于发生零星独立错误的信道，前者主要用于发生零星独立错误的信道，如卫星信道容易出现随机性错误；而后者则如卫星信道容易出现随机性错误；而后者则用于对付以突发错误为主的信道，如短波信用于对付以突发错误为主的信道，如短波信道或存储系统。道或存储系统。按照构造差错控制编码的数学方法来分按照构造差错控制编码的数学方法来分类，差错控制编码可以分为代数码、几何码类，差错控制编码可以分为代

11、数码、几何码和算术码。和算术码。代数码建立在近似代数学基础上，是目代数码建立在近似代数学基础上，是目前发展最为完善的编码。前发展最为完善的编码。线性码就是代数码的一个最重要的分支。线性码就是代数码的一个最重要的分支。需要指出的是，在传统的数字传输系统需要指出的是，在传统的数字传输系统中，纠错编码与数字调制是各自独立设计实中，纠错编码与数字调制是各自独立设计实现的。现的。目前已把编码器和调制器合成一个统一目前已把编码器和调制器合成一个统一的整体，这就是所谓的网格编码调制（的整体，这就是所谓的网格编码调制（TCMTCM）。）。限于篇幅，本书对此不作介绍。限于篇幅，本书对此不作介绍。各种分类方法之间

12、的关系如图各种分类方法之间的关系如图5-25-2所示。所示。前已述及，差错控制包括检错和纠错，它们能够前已述及，差错控制包括检错和纠错，它们能够有效地检测出通信过程中产生的差错，并进行纠正，有效地检测出通信过程中产生的差错，并进行纠正，从而提高通信质量。从而提高通信质量。通常，原始的待传输的数据码序列本身变化是随通常，原始的待传输的数据码序列本身变化是随机的，一般不带有任何规律性。机的，一般不带有任何规律性。但是，通过加进冗余码可使其具有某种规律性；但是，通过加进冗余码可使其具有某种规律性；在接收端，通过对规律性的检测，就可发现传输中在接收端，通过对规律性的检测，就可发现传输中的错误。的错误。

13、为了便于理解纠错和检错的基本原理，下面通过为了便于理解纠错和检错的基本原理，下面通过一个例子来说明。一个例子来说明。我们先考察由三位二进制码构成的码组：我们先考察由三位二进制码构成的码组：三位二进制码有三位二进制码有8 8种不同的组合，即种不同的组合，即000000，001001，010010，011011，100100，101101，110110，111111，我们用这，我们用这些组合表示些组合表示8 8种不同的天气，例如种不同的天气，例如000000（晴），（晴），001001（云），（云），010010（阴），（阴），011011（雨），（雨），100100（雪），（雪），101101（

14、霜），（霜），110110（雾），（雾），111111（雹）。（雹）。其中任一码组在传输中若发现错误，则其中任一码组在传输中若发现错误，则将变成另一码组，由于是其中的一个码组，将变成另一码组，由于是其中的一个码组，这时传输错误在接收端就无法发现。这时传输错误在接收端就无法发现。若将上述若将上述8 8种码组选择其中的种码组选择其中的4 4种作为许种作为许用码组，例如选择用码组，例如选择000=000=晴晴011=011=云云101=101=阴阴110=110=雨雨用来传输信息，令其余用来传输信息，令其余4 4种作为禁用码组，即种作为禁用码组，即001001，010010，100100，11111

15、1。本来本来4 4种不同信息，用两位二进制码的不种不同信息，用两位二进制码的不同组合表示即可，若用三位表示，则有一位同组合表示即可，若用三位表示，则有一位是多余的，称之为冗余码。是多余的，称之为冗余码。用三位二进制码的不同组合表示用三位二进制码的不同组合表示4 4种信息，种信息，在接收端可用来发现传输中的一位错误。在接收端可用来发现传输中的一位错误。例如，发送的是例如，发送的是000000（晴），传输中发生（晴），传输中发生了一位错误，可能变成了一位错误，可能变成001001（云），（云），010010（阴）（阴）或或100100（雪）。（雪）。这三个码组都是禁用码组，故接收端收这三个码组都是

16、禁用码组，故接收端收到禁用码组时，就判定传输中肯定发生了错到禁用码组时，就判定传输中肯定发生了错误。误。当发生三位错误时，当发生三位错误时，000000（晴）就变成（晴）就变成111111（雹），它也是禁用码组，故也能发现三（雹），它也是禁用码组，故也能发现三位错误。位错误。但是，这种编码不能发现两位错误，因但是，这种编码不能发现两位错误，因为错两位后产生的码组是许用码组。为错两位后产生的码组是许用码组。上述编码只能用于检测错误，而不能用上述编码只能用于检测错误，而不能用于纠正错误。于纠正错误。例如，当收到的码组是例如，当收到的码组是100100（雪）时，收（雪）时，收端无法判定是哪一位码发生

17、了错误造成的。端无法判定是哪一位码发生了错误造成的。因为因为000000（晴），（晴），110110（雨），（雨），101101（阴）三者（阴）三者错一位都可变为错一位都可变为100100（雪）。（雪）。要想纠正错误，还必须增加冗余。要想纠正错误，还必须增加冗余。例如，只选用两位码作为许用码组，如例如，只选用两位码作为许用码组，如000000（晴），（晴），111111（雹），其余的都是禁用码（雹），其余的都是禁用码组。这样，用三位二进制码代表两种不同的组。这样，用三位二进制码代表两种不同的信息，就有两位码是多余的。信息，就有两位码是多余的。此时，收端可以检测两位以下的错误，或此时，收端可以检

18、测两位以下的错误，或纠正一位的错误。纠正一位的错误。例如，当收端收到禁用码组例如，当收端收到禁用码组100100（雪）时，（雪）时，若认为只有一位错误，则可以纠正为若认为只有一位错误，则可以纠正为000000（晴）。（晴）。因为因为111111（雹）中任何一位错误都不可能（雹）中任何一位错误都不可能变为变为100100（雪）。（雪）。但是，若认为错码数不超过两位，则存但是，若认为错码数不超过两位，则存在两种可能性：在两种可能性：000000（晴）错一位变为（晴）错一位变为100100（雪），或者（雪），或者111111（雹）错两位变为（雹）错两位变为100100（雪），因而只能检测出有错误码位

19、而无法（雪），因而只能检测出有错误码位而无法纠正它。纠正它。香农定理告诉我们：信源编码的目的就香农定理告诉我们：信源编码的目的就是去冗余，提高编码的效率。是去冗余，提高编码的效率。但要注意并不是不压缩的信号抗干扰能但要注意并不是不压缩的信号抗干扰能力就一定很强，一般的信号都有大量的冗余，力就一定很强，一般的信号都有大量的冗余，但抗干扰能力并不好，主要是因为没有或无但抗干扰能力并不好，主要是因为没有或无法利用其冗余找到其相关性的规律。法利用其冗余找到其相关性的规律。因此，要先去掉冗余，再用更有效的编因此，要先去掉冗余，再用更有效的编码方法加进冗余，这就是在数字通信过程中码方法加进冗余，这就是在数

20、字通信过程中为什么要两次编码的原因。为什么要两次编码的原因。所谓冗余就是在信息中附加比特以便于所谓冗余就是在信息中附加比特以便于接收端进行错误检测。接收端进行错误检测。将无冗余度的信息码分组，为每组信息将无冗余度的信息码分组，为每组信息码附加若干位监督码的编码，称为分组码。码附加若干位监督码的编码，称为分组码。在分组码中，监督码元仅监督本码组中在分组码中，监督码元仅监督本码组中的信息码元。的信息码元。分组码一般可用符号分组码一般可用符号(n n,k k)表示，其中表示，其中n n是信息码组的总位数，又称为码组的长度是信息码组的总位数，又称为码组的长度（码长），（码长），k k是每组二进制信息码

21、元的数目，是每组二进制信息码元的数目，r r=n n k k为每码组中的监督码元数目，分组为每码组中的监督码元数目，分组码的结构如图码的结构如图5-35-3所示。所示。分组码的一个码组中分组码的一个码组中“1”1”的数目，称为的数目，称为码组重量，简称码重。码组重量，简称码重。两个码组对应位上数字不同的位数称码两个码组对应位上数字不同的位数称码组的距离，简称码距，又称为汉明（组的距离，简称码距，又称为汉明（HammingHamming）距离。距离。例如例如001001，010010，100100，111111这这4 4个码组之间，个码组之间，任意两个码组的距离均为任意两个码组的距离均为2 2。

22、我们把某种编码中各个码组之间距离的我们把某种编码中各个码组之间距离的最小值称为最小码距（最小值称为最小码距（d d0 0）。）。最小码距（最小码距（d d0 0）决定一种编码的抗干扰）决定一种编码的抗干扰能力的大小。能力的大小。因此，最小码距（因此，最小码距（d d0 0）是信道编码的一）是信道编码的一个重要参数。个重要参数。抗干扰编码理论的研究结果表明，最小抗干扰编码理论的研究结果表明，最小码距（码距（d d0 0）与检、纠错能力之间满足下列关）与检、纠错能力之间满足下列关系。系。奇偶监督码（又称为奇偶校验码）是一奇偶监督码（又称为奇偶校验码）是一种最简单也是最基本的检错码，在计算机数种最简

23、单也是最基本的检错码，在计算机数据传输中得到了广泛的应用。据传输中得到了广泛的应用。奇偶监督码又分奇监督码和偶监督码，奇偶监督码又分奇监督码和偶监督码，两者编码方法相同，就是在信息码元后面附两者编码方法相同，就是在信息码元后面附加一个监督码元，使得码组中加一个监督码元，使得码组中“1”1”的个数为的个数为奇数或偶数，奇数时称为奇监督码，偶数时奇数或偶数，奇数时称为奇监督码，偶数时称为偶监督码，统称为奇偶监督码。称为偶监督码，统称为奇偶监督码。信 息 码 元行监督码元01011011001010101001000011000011011000111001001111111100001001111

24、111101100001列监督码元00111000010 把信息码元中把信息码元中“1”1”的个数用二进制数字的个数用二进制数字表示，并作为监督码元放在信息码元的后面，表示，并作为监督码元放在信息码元的后面，这样构成的码称为群计数码。这样构成的码称为群计数码。例如，一码组的信息码元为例如，一码组的信息码元为10101111010111，其，其中中“1”1”的个数为的个数为5 5，用二进制数字表示为，用二进制数字表示为“101”101”，将它作为监督码元附加在信息码元，将它作为监督码元附加在信息码元之后，即传输的码组为之后，即传输的码组为10101111010111101101。群计数码有较强的

25、检错能力，除了同时群计数码有较强的检错能力，除了同时出现码组中出现码组中“1”1”变为变为“0”0”和和“0”0”变为变为“1”1”的成对错误外，它能纠正所有形式的错误。的成对错误外，它能纠正所有形式的错误。国际统一图书编号也是一种检错码，主国际统一图书编号也是一种检错码，主要目的是为了防止书号在通信过程中发生误要目的是为了防止书号在通信过程中发生误传。图书编号的格式有统一的规定。传。图书编号的格式有统一的规定。上一节介绍了一些简单编码，其中奇偶上一节介绍了一些简单编码，其中奇偶监督码的编码原理利用了代数关系式，这类监督码的编码原理利用了代数关系式，这类建立在代数学基础上的编码称为代数码。建立

26、在代数学基础上的编码称为代数码。在代数码中，最常见的是线性码。在代数码中，最常见的是线性码。作为差错控制编码的学习基础，本节讨作为差错控制编码的学习基础，本节讨论线性分组码，主要使用矩阵和多项式等数论线性分组码，主要使用矩阵和多项式等数学工具。学工具。线性分组码是建立在近代代数基础上的，线性分组码是建立在近代代数基础上的，利用代数关系构造的一种代数码。利用代数关系构造的一种代数码。在在(n n,k k)分组码中，若每一个监督码元都分组码中，若每一个监督码元都是码组中某些信息码元按线性关系相加得到是码组中某些信息码元按线性关系相加得到的，则称为线性分组码。的，则称为线性分组码。或者说，用线性方程

27、组表述规律性的分或者说，用线性方程组表述规律性的分组码称为线性分组码。组码称为线性分组码。例如，设某一例如，设某一(7,3)(7,3)分组码为分组码为 A A=a a6 6 a a5 5 a a4 4 a a3 3 a a2 2 a a1 1 a a0 0 其中前三位是信息码元，后四位是监督其中前三位是信息码元，后四位是监督码元，可以用下列线性方程组来表述，即码元，可以用下列线性方程组来表述，即 线性分组码是一类重要的纠错码，应用线性分组码是一类重要的纠错码，应用很广泛。很广泛。3642643165064aaaaaaaaaaaaa 汉明码是汉明码是19501950年由美国贝尔实验室汉明年由美国

28、贝尔实验室汉明（也译为海明）提出的，是第一个用于纠正（也译为海明）提出的，是第一个用于纠正一位错码的效率较高的线性分组码。一位错码的效率较高的线性分组码。目前，汉明码及其变型在数字通信系统、目前，汉明码及其变型在数字通信系统、数据存储系统中应用广泛。数据存储系统中应用广泛。本节以汉明码为例，介绍汉明码的构造本节以汉明码为例，介绍汉明码的构造原理以及线性分组码的一般原理。原理以及线性分组码的一般原理。由于由于S S取值有两种，因此只能代表有错和取值有两种，因此只能代表有错和无错两种信息，但不能指出错码的具体位置。无错两种信息，但不能指出错码的具体位置。不难想像，若将监督位增加一位，变成不难想像，

29、若将监督位增加一位，变成两位，则将能增加一个类似于式（两位，则将能增加一个类似于式（5-65-6）的监）的监督关系式。督关系式。两个校正子的可能值有两个校正子的可能值有4 4种组合：种组合：0000，0101，1010，1111，故能表示，故能表示4 4种不同的信息。种不同的信息。其中其中1 1种表示无错，而其余种表示无错，而其余3 3种就有可能种就有可能指示一种错码的指示一种错码的3 3种不同位置。种不同位置。依此类推，依此类推，r r个监督关系式就能指示出一个监督关系式就能指示出一位错码的位错码的2 2r r 1 1个可能位置。个可能位置。若要纠正一位错码，根据式（若要纠正一位错码，根据式

30、（5-75-7）可知，）可知，r r33。若取若取r=r=3 3，n=k+r=n=k+r=7 7。这里用这里用A A =a a6 6 a a5 5 a a4 4 a a3 3 a a2 2 a a1 1 a a0 0 表示表示这这7 7个码元，用个码元，用S S1 1，S S2 2，S S3 3表示由三个监督关表示由三个监督关系式得到的三个校正子，于是三个校正子的系式得到的三个校正子，于是三个校正子的值指示了值指示了8 8种不同的错误图样。种不同的错误图样。校正子与错码位置的对应关系如表校正子与错码位置的对应关系如表5-35-3所所示。示。S1 S2 S3错 码 位 置S1 S2 S3错 码

31、位 置0 0 1a01 0 1a40 1 0a11 1 0a51 0 0a21 1 1a60 1 1a30 0 0无错 在了解了汉明码的基本构造后，下面对在了解了汉明码的基本构造后，下面对线性分组码的一般原理进行讨论。线性分组码的一般原理进行讨论。前已述及，线性分组码是指信息位和监前已述及，线性分组码是指信息位和监督位满足一组线性方程关系的码。督位满足一组线性方程关系的码。式（式（5-115-11）就是这种线性方程，现将式）就是这种线性方程，现将式（5-115-11）改写为）改写为654321065432106543210111010001101010010110010aaaaaaaaaaaa

32、aaaaaaaaa 式中，上式还可以简记为上式还可以简记为 HHA ATT=O OT T 或或 A A H HT T=O O 式式中中H H称为监督矩阵，只要监督矩阵称为监督矩阵，只要监督矩阵H H给定，编给定，编码时监督位和信息位的关系就完全确定。码时监督位和信息位的关系就完全确定。上面上面H H矩阵也可以分成两部分，即矩阵也可以分成两部分，即 其中，其中，P P为为r r k k阶矩阵，阶矩阵，I Ir r为为r r r r阶方阵，阶方阵，将具有将具有 PIPIr r 形式的形式的H H矩阵称为典型阵。矩阵称为典型阵。式（式（5-125-12）也可以改写成）也可以改写成62514031 1

33、 1 01 1 0 11 0 1 1aaaaaaa 因此，若找到了码的生成矩阵因此，若找到了码的生成矩阵G G，则编码，则编码的方法就完全确定了。的方法就完全确定了。具有具有 I Ik kQ Q 形式的生成矩阵称为典型生成形式的生成矩阵称为典型生成矩阵。矩阵。由典型生成矩阵得出的码组由典型生成矩阵得出的码组A A中，信息位中，信息位不变，监督位附加其后，这种码被称为系统不变，监督位附加其后，这种码被称为系统码。码。发送码组在传输过程中可能由于干扰引入发送码组在传输过程中可能由于干扰引入差错，则接收码组一般来说与发送码组不一差错，则接收码组一般来说与发送码组不一定相同。定相同。设接收码组为一设接

34、收码组为一n n列的行矩阵列的行矩阵B B，即，即 B B=b bn n 1 1 b bn n 2 2 b b0 0 则发送码组则发送码组A A与接收码组与接收码组B B之差，即之差，即 B B A A=E E（模（模2 2）式中式中E E就是传输中产生的错码行矩阵就是传输中产生的错码行矩阵E E，设设 E E=e en n-1-1 e en-n-2 2 e e0 0 若若e ei i=0=0，表示该位无差错；若，表示该位无差错；若e ei i=1=1，表示该位接收码元有错。表示该位接收码元有错。这样式（这样式（5-245-24）也可以写成）也可以写成B B=A A+E E（模（模2 2和和）

35、线性分组码的一个重要性质就是它的封线性分组码的一个重要性质就是它的封闭性。闭性。所谓封闭性，是指一种线性码中的任意所谓封闭性，是指一种线性码中的任意两个码组之和仍为这种码的一个码组。两个码组之和仍为这种码的一个码组。这就是说，若这就是说，若A A1 1和和A A2 2是一种线性码中的两是一种线性码中的两个许用码组，则个许用码组，则(A A1 1+A A2 2)仍为其中一个码组。仍为其中一个码组。既然线性分组码具有封闭性，因而两个既然线性分组码具有封闭性，因而两个码组之间的距离必是另一码组的重量。码组之间的距离必是另一码组的重量。故码的最小距离即是码的最小码重（除故码的最小距离即是码的最小码重（

36、除全全0 0码组外）。码组外）。循环码是线性分组码的一个重要分支。循环码是线性分组码的一个重要分支。19571957年，普兰奇（年，普兰奇（PrangePrange）最早提出循）最早提出循环码的概念，在其后的环码的概念，在其后的2020多年中，人们对循多年中，人们对循环码的代数结构、性能和编译方法等方面进环码的代数结构、性能和编译方法等方面进行了大量的研究，并取得了许多重要成果，行了大量的研究，并取得了许多重要成果，从而大大推动了循环码在实际差错控制系统从而大大推动了循环码在实际差错控制系统中的应用。中的应用。由于循环码有许多特殊的代数性质，特由于循环码有许多特殊的代数性质，特别是它的编译码器

37、易于实现，而且综合性能别是它的编译码器易于实现，而且综合性能良好，目前其编码、译码、检测和纠错已由良好，目前其编码、译码、检测和纠错已由集成电路产品实现，其速度与软件算法相比集成电路产品实现，其速度与软件算法相比大大地提高了，是目前通信传送系统和磁介大大地提高了，是目前通信传送系统和磁介质存储器中广泛采用的一种编码。质存储器中广泛采用的一种编码。循环码是一种系统分组码，它除了具有循环码是一种系统分组码，它除了具有线性分组码的封闭性外，还具有循环性。线性分组码的封闭性外，还具有循环性。循环性是指任一许用码组经过循环移位循环性是指任一许用码组经过循环移位后所得到的码组仍为一许用码组。后所得到的码组

38、仍为一许用码组。若若C C=c c1 1c c2 2c cn n 是一个循环码组，一是一个循环码组，一次循环移位得到次循环移位得到C C（1 1）=c c2 2 c c3 3c cn n c c1 1 也也是许用码组，移位是许用码组，移位i i次得到次得到C C（i i）=c ci i+1+1 c ci i+2+2c cn n c c1 1 c ci i 也是许用码组。也是许用码组。不论右移或左移，移位位数多少，其结不论右移或左移，移位位数多少，其结果均为循环码组。果均为循环码组。如前所述，循环码的编码需要将一个多项如前所述，循环码的编码需要将一个多项式除以另一个多项式，这种操作是由多项式式除

39、以另一个多项式，这种操作是由多项式除法运算完成的，在硬件上是由多项式除法除法运算完成的，在硬件上是由多项式除法电路（带反馈的移位寄存器）实现的。电路（带反馈的移位寄存器）实现的。有两种不同的除法电路：一种采用有两种不同的除法电路：一种采用“内接内接”的异或（或模的异或（或模2 2和）电路；另一种采用和）电路；另一种采用“外接外接”的异或电路。的异或电路。在实际应用中，通常采用内接异或门电路在实际应用中，通常采用内接异或门电路的除法电路。的除法电路。内接异或门电路除法电路的工作过程与采内接异或门电路除法电路的工作过程与采用手算进行长除法的过程完全一致，每当一用手算进行长除法的过程完全一致，每当一

40、个个“1”1”移出寄存器进入反馈线时，相当于从移出寄存器进入反馈线时，相当于从被除式中被除式中“减去减去”除式（这里的除式（这里的“减减”也是也是模模2 2和）。和）。一般来说，译码器通常要比编码器复杂一般来说，译码器通常要比编码器复杂得多，特别是对纠错能力强的纠错码更是如得多，特别是对纠错能力强的纠错码更是如此。此。因此，对纠错码的译码研究主要集中在因此，对纠错码的译码研究主要集中在算法上。算法上。如前所述，校正子与错误图样之间存在某如前所述，校正子与错误图样之间存在某种对应关系。种对应关系。循环码的译码可以分以下三步进行：循环码的译码可以分以下三步进行：（1 1）由接收的码多项式）由接收的

41、码多项式r r(x x)计算出校正计算出校正子（伴随式）多项式子（伴随式）多项式s s(x x)；（2 2）由校正子（伴随式）多项式）由校正子（伴随式）多项式s s(x x)确确定错误图样定错误图样e e(x x)；（3 3）将错误图样）将错误图样e e(x x)与与r r(x x)相加，纠正相加，纠正错误。错误。为简化校正子的计算，上述校正子（伴为简化校正子的计算，上述校正子（伴随式）多项式随式）多项式s s(x x)可以用接收到的码多项式可以用接收到的码多项式r r(x x)除以生成多项式除以生成多项式g g(x x)所得到的余式。所得到的余式。用除法电路作校正子计算电路时，有一用除法电路

42、作校正子计算电路时，有一个重要性质：某码组循环移位个重要性质：某码组循环移位i i次的校正子等次的校正子等于原码组校正子在除法电路中循环移位于原码组校正子在除法电路中循环移位i i次所次所得的结果。得的结果。卷积码（又称连环码）是卷积码（又称连环码）是19951995年由麻省年由麻省理工学院的伊利亚斯（理工学院的伊利亚斯（P.EliasP.Elias）提出的。）提出的。它与前面所介绍的汉明码和循环码等分它与前面所介绍的汉明码和循环码等分组码不同，卷积码是一种非分组码，卷积码组码不同，卷积码是一种非分组码，卷积码在编码过程中充分利用各码组之间的相关性，在编码过程中充分利用各码组之间的相关性，其性

43、能要优于分组码，而且实现简单，因此其性能要优于分组码，而且实现简单，因此在通信领域应用越来越广泛。在通信领域应用越来越广泛。在以计算机为中心的数据通信系统中，在以计算机为中心的数据通信系统中，卷积码主要应用于前向纠错（卷积码主要应用于前向纠错（FECFEC）。）。分组码是在任何一段规定时间内把分组码是在任何一段规定时间内把k k个信个信息比特的序列编成息比特的序列编成n n个比特的码组，每个码组个比特的码组，每个码组的的(n nk k)个监督位仅与本码组的个监督位仅与本码组的k k个信息位有个信息位有关，而与其他码组无关。关，而与其他码组无关。卷积码编码的一般结构如图卷积码编码的一般结构如图5

44、-125-12所示，所示，它包括一个由它包括一个由N N段组成的输入移位寄存器，每段组成的输入移位寄存器，每段有段有k k级，共级，共NkNk位寄存器；一组位寄存器；一组N N个模个模2 2加法器；加法器；一个由一个由N N级组成的输出移位寄存器，对应于每级组成的输出移位寄存器，对应于每段段k kbitbit的输入序列，输出的输入序列，输出N Nbitbit。由图由图5-125-12可知，卷积码是把可知，卷积码是把k kbitbit信息段信息段编成编成n nbitbit的码组，所编的的码组，所编的n n长码组，不仅取决长码组，不仅取决于当前的于当前的k k个信息码元，而且还取决于前个信息码元，

45、而且还取决于前(N N1)1)个信息段，编码过程中相互关联的个信息段，编码过程中相互关联的k k个码元为个码元为NnNn个。个。这时，监督位监督着这这时，监督位监督着这N N段时间内的信息。段时间内的信息。这这N N段时间内的码元数目段时间内的码元数目NnNn称为这种卷积码的称为这种卷积码的约束长度。约束长度。注意约束长度的定义没有统一的标准，注意约束长度的定义没有统一的标准，有的书或文献把有的书或文献把N N或或(N N1)1)称为约束长度。称为约束长度。通常把卷积码记为通常把卷积码记为(n n,k k,N N)，其编码效率，其编码效率为为R=k/nR=k/n。下面用一个简单例子说明卷积码的

46、编码原理。下面用一个简单例子说明卷积码的编码原理。图图5-135-13所示的电路是一个简单的所示的电路是一个简单的(2,1,3)(2,1,3)卷积卷积码的编码器，它由有两个触点的转换开关和一组码的编码器，它由有两个触点的转换开关和一组3 3位位移位寄存器移位寄存器m m1 1，m m2 2，m m3 3及模及模2 2相加电路组成。相加电路组成。编码前各移位寄存器清零，信息码元按顺序编码前各移位寄存器清零，信息码元按顺序a a1 1a a2 2a aj j依次输入到编码器。依次输入到编码器。每输入一个信息码元每输入一个信息码元a aj j，开关依次为接到每一，开关依次为接到每一个触点各一次。个触

47、点各一次。如图如图5-135-13所示，编码器每输入一个信息码元，所示，编码器每输入一个信息码元，经该编码器后产生经该编码器后产生2 2个输出比特。个输出比特。假设该移位寄存器的起始状态全为零，编假设该移位寄存器的起始状态全为零，编码器的输出比特码器的输出比特c c1 1c c2 2表示为表示为c c1 1=m m1 1+m m2 2+m m3 3c c2 2=m m1 1+m m3 3其中，其中，m m1 1表示当前的输入比特，而表示当前的输入比特，而m m1 1m m2 2表示存表示存储的以前的信息。储的以前的信息。当第一个输入比特为当第一个输入比特为1 1时，即时，即m m1 1=1=1

48、，因，因m m3 3m m2 2=00=00，所以输出，所以输出c c1 1c c2 2=11=11，这时，这时m m1 1=1=1，m m3 3m m2 2=01=01，c c1 1c c2 2=01=01，依此类推，为保证输入，依此类推，为保证输入的信息的信息1101011010都能通过移位寄存器，还必须都能通过移位寄存器，还必须在输入信息位后填加在输入信息位后填加3 3个个0 0。为了说明编为了说明编码器的状态，采码器的状态，采用如图用如图5-145-14所示所示的图解方式给出的图解方式给出整个编码器的工整个编码器的工作过程。作过程。将上述编码过程列成表格形式，如表将上述编码过程列成表格

49、形式，如表5-85-8所示列出了它的状态变化过程。所示列出了它的状态变化过程。描述卷积码的方法有两类：图形表示和描述卷积码的方法有两类：图形表示和解析表示。解析表示。本节仅介绍卷积码的图形描述。本节仅介绍卷积码的图形描述。编码器中移位过程中可能产生的各种序编码器中移位过程中可能产生的各种序列可以用树图来表示，如图列可以用树图来表示，如图5-155-15所示。所示。从卷积码的树图可以看出，存在着重复性，据从卷积码的树图可以看出，存在着重复性，据此可以得到更为严重紧凑的图形表示。此可以得到更为严重紧凑的图形表示。在网格图中，把码树中具有相同的节点合并在在网格图中，把码树中具有相同的节点合并在一起，

50、码树中的上支路对应于输入比特一起，码树中的上支路对应于输入比特0 0，用实线，用实线表示；下支路对应于输入比特表示；下支路对应于输入比特1 1，用虚线表示。，用虚线表示。网格图中支路上标注的码元为输出比特，自上网格图中支路上标注的码元为输出比特，自上而下而下4 4行节点分别表示四种状态，如图行节点分别表示四种状态，如图5-165-16所示。所示。一般情况下有一般情况下有2 2N N1 1种状态，从第种状态，从第N N节（从左向节（从左向右计数）开始，网格图图形开始重复而完全相同。右计数）开始，网格图图形开始重复而完全相同。从树图的第三级各节点状态与第四级各从树图的第三级各节点状态与第四级各节点