《编码理论》课件第8章

第8章卷积码和其他纠错码

8.1卷积码8.2秩距离码8.3突发错误的纠正8.4级联码及交织码8.5

Turbo码 8.1卷积码

8.1.1离散卷积表述

分组码和卷积码两者主要差异在于卷积码编码器在任意给定的时段，编码器的n0个输出不仅与此时段的k0个输入有关，而且也与前m0个输入(记忆器件中存储的)有关。因此卷积码一般可采用(n0，k0，m0)来表示，其中k0为输入码元数，n0为输出码元数，而m0则为编码器的存储器数。典型的卷积码一般选n0和k0(k0<n0)值较小，但存储器m0可取较大值(m0<10)，以获得既简单又高性能的信道编码。卷积码的编码器是由一个有k0个输入端、n0个输出端，且具有m0节移位寄存器所构成的有限状态的有记忆系统，通常称它为时序网络。

描述这类时序网络的方法很多，它大致可分为两大类型，解析表示法与图形表示法。在解析法中又可分为离散卷积法、生成矩阵法、码多项式法等；在图形表示法中也可分为状态图法、树图法、格图法等。描述卷积码编译码的过程，可以用不同的描述方法，如矩阵法、码树法、状态图法和篱状图法等。采用何种方法与卷积码的译码方法有很大关系。例如，在代数译码时，用矩阵法对译码原理的叙述和理解较方便。而借助树码和篱状图能更为清晰地分析和了解概率译码的过程和码的性能。卷积码(n0，k0，m0)在任何一段规定时间内编码器产生的n0个码元，不仅取决于这段时间中的k0个信息码元，而且还取决于前m0段规定时间内的信息码元，设N=m0+1,编码过程中相互关联的码元为Nn0个。它表明编码过程中互相约束的码元数，这时，监督位监督着这N段时间内的信息。这N段时间内的码元数目Nn0称为这种卷积码的约束长度。其编码效率为R＝k0/n0。

设卷积码编码器输入码序列（待编码的信息序列）为U＝u0(1)u0(2)…u0（k0）u1(1)u1(2)…u1(k0)…us(1)us(2)…us(k0)…设编码器输出码序列为C＝c0(1)c0(2)…c0(n0)c1(1)c1(2)…c1(n0)…cs(1)cs(2)…cs(n0)…则编码器输出码序列中任一子码可以由如下卷积关系给出：（j＝1，2，…，n0）(8－1)式中：g(i，j)——非系统卷积码的生成序列。系统卷积码的码序列中任一子码Cs

，也是有n0个码元，其前k0位与待编码的信息序列中的第s信息组us(i)相同，而后n0-k0位监督元由生成序列生成。由于每个码中的前k0位就是此时刻待编码的k0位信息元，所以在生成序列g(i,j)中有k0×k0个生成序列是固定的，即:只有k0×(n0-k0)个生成序列需要给定,以便确定每个子码中n0-k0个监督元,则码字:cs(j)＝us（i）；(i＝j＝1，2，…，k0)(j＝k0＋1，…，n0)（8－2）式中：g(i，j)——系统卷积码的生成序列。

【例8－1】已知(3，1，2）系统卷积码的生成序列为：g（1，1）＝[100]g（1，2）＝[g0（1，2）g1（1，2）g2（1，2）]＝[100]g（1，3）＝[g0（1，3）g1（1，3）g2（1，3）]＝[101]其任一子码为:cs（1）＝us（1）【例8－2】已知（3，2，2）系统卷积码的生成系列为：

g（1，3）＝[g0（1，3）g1（1，3）g2（1，3）]＝[101]

g（2，3）＝[g0（2，3）g1（2，3）g2（2，3）]＝[110]

该码的任一子码Cs中前两位与us（1）、us（2）相同，而后一位的监督元由式（8-2）确定,即

cs(1)＝us(1)

cs(2)＝us(2)8.1.2矩阵表述

类似(n，k)线性分组码，卷积码也用生成矩阵和监督矩阵来描述。对于任意一个(n0,k0,m0)卷积码，其生成矩阵G∞是一个半无限矩阵，即（8－3）

【例8－3】设(3，1，2)卷积码的生成子矩阵求:（1）卷积码的生成矩阵G∞。（2）若输入信息序列U=［1011010100…］，求卷积码的输出码字序列。

解已知基本生成矩阵 则(3，1，2)卷积码的生成矩阵G∞为当已知卷积码的生成矩阵G∞时，进行C=UG∞运算即可实现编码。当输入信息序列为U=［1011010100…］时，(3，1，2)卷积码的输出码字序列为=[111010110101011…]

【例8－4】设(3，2，1)卷积码生成子矩阵分别为：

求:（1）卷积码的生成矩阵G∞。（2）若输入信息序列U=［1011010100…］，求卷积码的输出码字序列。

解该码的基本生成矩阵 ，则(3，2，1)卷积码的生成矩阵为当输入信息序列为U=［1011010100…］时，(3，2，1)卷积码输出码字序列为即

以上两个卷积码的码字序列中，各子码都具有系统码的特征。例如(3，2，1)卷积码的码字序列=101110010011001…中，每个子码的前两位就是输入信息序列U中的对应信息组11010100…。

由卷积码的定义可知，(n0，k0，m0)码的任意N个连续的子码之间有着相同的约束关系，此外，在卷积码的代数译码中，也只考虑一个编码约束长度内的码序列。所以，不失一般性，只考虑编码器初始状态全为0时，编码器输入N个信息组，即N.k0个信息元后，编码器输出的首N个子码，即Nn0个码元之间的约束关系即可，这首N个子码组成的码组称为卷积码的初始截短码组C，即：（8－5）式中：Ci＝ci(1)ci(2)…ci(n0)(i＝0，1，2，…，m0)。根据初始截短码组的定义，C可以表示成矩阵方程：C＝UG

（8－6）式中:U＝[U0U1U2…],且Ui＝ui(1)ui(2)…ui(k0),i＝0,1,2,…,m0；（8-7）称G为初始截短码组的生成矩阵，相应的基本生成矩阵g为：

在系统码条件下，由于k0k0个生成序列是已知的，即当i＝j时，g(i，j)＝1；当ij时，g(i，j)＝0，i＝1，2，…，k0；j＝1，2，…，k0。且每个子码中的前k0个码元与相应的k0个信息元相同。而后n0—k0个监督元则由信息序列与生成序列的卷积运算得到(见式(8-2)。由此可知，系统码的初始截短码组的Nk0Nn0生成矩阵为（8-9）（8-10）系统卷积码初始截短码组的基本生成阵为：(8-11)[例8-5](3，1，2)系统码的生成序列为：它的初始截短码组的基本生成矩阵是=[111010001]生成矩阵为若设U＝[u0(1)u1(1)u2(1)]＝[101]，则初始截短码组C为C＝UG＝[111010llO](n0，k0，m0)码的基本监督矩阵为(8-12)式中：h－(n0—k0)n0N阶矩阵。(n0，k0，m0)码的监督矩阵：(8-13)式中：Ｈ－(n0—k0)N×n0N阶矩阵。由以上关于生成矩阵G，监督矩阵H的讨论可以看到，它们与码的生成序列g(i，j)有密切的联系，只不过是以矩阵的方式描述了卷积码的卷积关系式(8-1)或(8-2)。所以，在卷积码的应用中，经常是给定码的g(i，j)，有了生成序列g(i,j)后，就可以确定卷积码的编码电路及其矩阵表示式。

[例8-6]设(3，1，2)系统码的生成序列：

g(1,1)＝1

g(1,2)＝[g0(1,2)g1(1,2)g2(1,2)]

g(1,3)＝[g0(1,3)g1(1,3)g2(1,3)]

求该码的监督矩阵？

解：由式（8-13）得(3，1，2)码的监督矩阵为：也可以得到如下矩阵方程：CT＝0T

其中：CT

－初始截短码组的转置，C＝[c0(1)c0(2)c0(3)c1(1)

c1(2)c1(3)

c2(1)c2(2)c2(3)]；0T－是一个6×1阶全0阵；它的基本监督阵是一个2×9阶阵，即：则

编码后输出n0个多项式，分别代表并行输出的门路码元信号。最后经并／串变换，n0路编码信号合为一路输出，码多项式为C(D)，如图8-1所示。图8-1卷积码的转移函数矩阵卷积编码器可视做一个k0端入口、n0端出口的线性多端口网络。网络理论可以用转移函数矩阵来描述卷积编码器的输入/输出关系。所不同的是这里的输入、输出均是多项式，因此相应的转移函数矩阵也是由多项式元素构成的多项式矩阵。

若定义多项式并行输入矩阵、输出矩阵为：(8-14)（8-15）

这里，Up(D)，Cp(D)的下标p表示它们是U(D)，C(D)的并行形式，虽然U(D)和在数量上有对应关系，然而在数学表达上不能等同。

编码系统k0路输入、n0路输出的转移关系(即编码关系)可写成：（8－16）G(D)是k0×n0多项式矩阵，称为转移函数矩阵，即（8－17）其中:由式（8-17）和（8-18）可知，第j个支路的输出是所有输入支路对它影响的总和，即：（8-19）最后，利用并／串变换公式将n个输出多项式合并成一个多项式：（8－20）[例8-7]

二进制(3，1，2)卷积生成序列如果输入信息流是101101011100…，求输出码字序列。

解:本题为1路输入、3路输出，因此转移函数矩阵是13的多项式矩阵。1路输入由（8-17）得卷积编码器的转移函数矩阵：由（8-19）得它们的系数序列分别是：利用并／串变换，即从左上角开始按列的顺序送出，得输出序列为：或者利用公式(8-20)化为多项式形式：其系数正是输出码元序列。[例8-8]某二进制(3，2，1)卷积生成序列：如输入信息流是 ，求输出码字序列。解：本题为两路输入、三路输出，因此转移函数矩阵是23的多项式矩阵。原输入为输入序列经串／并变换后分成两个并行输入，则该卷积编码器的转移函数矩阵是：由式(8-19)得：它们的系数序列分别是：利用并／串变换，即从左上角开始按列的顺序送出，得输出序列为：或者利用公式(8-20)化为多项式形式：其系数正是输出码元序列。[例8-8]某二进制(3，2，1)卷积生成序列：如输入信息流是，求输出码字序列。

解：本题为两路输入、三路输出，因此转移函数矩阵是23的多项式矩阵。原输入为输入序列经串／并变换后分成两个并行输入，则该卷积编码器的转移函数矩阵是：由式(8-19)得：利用公式(8-20)并／串变换得其系数正是输出码元序列：101001000111010011…。8.1.4卷积码的编码

1．串行输入、串行输出的编码电路。

构造这种类型编码电路的基础是式(8-1)和(8-2)。根据式(8-1)构造的是非系统编码器，而式(8-2)则是系统码编码电路的依据。图8-2所示的是(n0，k0，m0)非系统卷积码的串行编码电路，图8-3是系统码的编码电路。图8-2(n0，k0，m0)非系统码卷积码串行编码电路图8-3(n0，k0，m0)系统码卷积码串行编码电路图8-4（2，1，3）码编码电路

该式表明任一时刻编码器的输出可以由信息元与生成序列的离散卷积运算求出。这就是卷积码名称的由来。设则编码器的两个输出端的序列分别为：而码序列C为

【例8－10】二进制(3，1，2)卷积生成序列为：要求画出对应的编码器。解：编码电路如图8-5所示。图8－5二元(3,1,2)卷积编码电路[例8-11]二进制(3，2，1)卷积生成序列：要求画出对应的编码器？

解：编码电路如图8-6所示。图8-6二元(3,2，1)卷积编码电路

2．(n0—k0)m0级移位寄存器构成的并行编码电路

(n0—k0)m0这是系统码形式的一种编码电路，又称I型编码电路。将式(8-2)展开后可以改写成如下形式:cs(j)＝us(i),

j＝i＝1,2,…,k0

j=k0+1,…,n0

(8-21)式(8-21)表明，在并入并出方式下，为了获得第s个子码的(n0—k0)个监督元，需要(n0—k0)个移位寄存器组，每一组移位寄存器的数目为m0级。它们根据生成序列g(i，j)所确定的关系存储了第s个信息组相邻的前m0个信息组。(n0，k0，m0)码Ⅰ型编码电路如图8-7所示。图8－7

(n0，k0，m0)码Ⅰ型编码电路式中：j＝k0＋1，…,n0。由式(8－22)可见，只需将第s时刻的k0个信息元与前m0个时刻的诸信息元按生成序列所确定的关系模2相加，就可以得到此时此刻的n0-k0个监督元。Ⅱ型编码电路由k0个移位寄存器组构成，每一组有m0级移位寄存器，它们分别寄存了前m0时刻进入编码器的第一个到第k0个信息元。(n0，k0，m0)码Ⅱ型编码电路如图8－8所示。图8－8

(n0，k0，m0)码Ⅱ型编码电路8.1.5状态流图

以上的卷积码描述方法将矩阵、多项式与编码器结构的关系揭示得清清楚楚，但并没能揭示卷积码的内在特性。在这一点上，状态图和网格图提供了很好的描述工具。

卷积编码器在i时刻编出的码字不仅取决于本时刻的输入信息组，而且取决于i之前存入记忆阵列的个信息组，换言之，取决于记忆阵列的内容，称之为编码器的状态。如图8-5所示的卷积编码器中，除本时刻的输入外还有两个存储器存放i—1和i—2时刻的输入，即和内容，其内容的组合有四种可能，即00，01，10和11，就说这种编码器有四个状态。更一般地，移存器阵列分割成两块，（8-23）式中：(8－24)编码矩阵第i行第j列的元素表示由状态转移到下一状态时发送的码字，矩阵元素“．”说明这种状态转移是不可能事件。比如从状态转移到下一状态就不可能，因为输入比特(状态机触发信号)只有0或1两种，对应的转移也只能有两种。从编码矩阵看出，状态只能转移到状态或。

(3，1，2)卷积码的状态流图如图8-9所示。图8-9（3，1，2）卷积码状态流图图中圆圈代表状态节点，因需标注状态号，所以没有像一般的信号流图那样用一个黑点表示节点。箭头代表转移，与箭头对应的标注，比如0／010，表示输入信息0时的编出码字010。每个状态都有两个箭头发出，对应输入分别是0，1两种情况下的转移路径。假如输入信息序列是1011010111…，从状态流图可以轻易地找到输入／输出和状态的转移关系。可从状态出发，根据输入找到相应箭头，随箭头在状态流图上移动，得到以下结果：

【例8－13】某二进制(3，2，1)卷积编码器电路如图8－6所示，试分别用编码矩阵和状态流图来描述该码。如果输入信息流是101101011100，求输出码字序列。

解图8－6所示的编码器有2路输入、3路输出，2个移存器、4种状态。由于i时刻并行输入2b，相当于有限状态机的触发信号由2b组成，所以从某一状态出发，下一个状态可以是4种状态之一，则(3，2，1)卷积编码器的编码矩阵为由上可知其状态流图如图8－10。若初始状态是S0，则将输入序列划分成2b组(10，11，01，01，11，00，…)。

在图8－10所示的状态流图中，根据2bit输入信息组寻找其状态转移路径，并确定转移过程中发出的码字序列，可得到如下转移：可见，码字序列为（101，001，000，111，010，011，…）。图8-10（3，2，1）卷积码状态流图8.1.6网格图

状态流图展示了状态转移的去向，但不能记录状态转移的轨迹。网格图(或称格栅图)可以弥补这一缺陷。它可以将状态转移展开在时间轴上，使编码的全过程跃然纸上，是分析卷积码的有力工具。网格图以状态为纵轴，以时间(抽样周期T)为横轴，将平面分割成格状。状态和状态转移的定义画法与流图法一样，也是用一个箭头表示转移，伴随转移的表示转移发生时的输入信息组／输出码组。所不同的是，网格图还体现时间的变化，一次转移与下一次转移在图上头尾相连。

[例8-14]二进制(3，1，2)卷积编码器如图8-5所示，试用网格图来描述该码。如果输入信息序列是(1011010…)，求输出码字序列。

解：参见例8-12所得的编码矩阵和状态流图，可得网格图和编码轨迹如图8-11所示。图中，当输入5位信息10110时，输出码字和状态转移是：图8－11

(3，1，2)卷积码网格图

从图8-11看到，网格图分成两部分，一部分是对编码器的描述，告诉人们从本时刻的各状态可以转移到下一时刻的哪些状态，伴随转移的输入信息／输出码字是什么；另一部分是对编码过程的记录，一条半无限的水平线(纵轴上的常数)标志某一个状态，一个箭头代表一次转移，每隔时间T(相当于移存器一位移存D)转移一次，转移的轨迹称为路径。两部分可以合画在一起，也可单独画。比如，在描述卷积编码器本身而并不涉及具体编码时，只需第一部分网格图就够了；当状态很多、转移线很密，网格图上难以标全伴随所有转移的输入／输出码字信息时，利用编码矩阵可看得更清楚。

[例8-15]

某二进制(3，2，1)卷积编码器如图8-6所示，试用网格图来描述该码。如果输入信息流是，求输出码字序列。

解：由[例8-13]所得的编码矩阵和状态流图，可得网格图和编码轨迹如图8-12所示。图8－12

(3，2，1)卷积码网格图和编码轨迹当输入信息(10，11，01，01，11，00，…)时，输出码字和状态转移是：

至此，介绍了描述卷积码的五种方法：离散卷积描述、生成矩阵、多项式转移函数矩阵、状态流图和网格图。这几种方法从不同的侧面来描述卷积码，各有所长。其中，生成矩阵和多项式转移函数矩阵可视为同一类，这两种方法沿用了表示分组码的基本思想，建立了代数与卷积编码器的联系。它们的特点是物理意义清楚，代数量(多项式系数、矩阵元素)与编码电路连接线之间的对应关系十分明确，非常有利于用VHDL等硬件描述语言来表达，以及用FPGA、DSP等来物理实现。状态流图和网格图属于另外一类表示法，状态流图可借助信号流图等图论工具或理论来分析卷积码的特性；网格图则特别适合用于计算机的穷尽搜索，它使状态能在时域展开，所得的状态轨迹是研究差错事件、卷积码距离特性以及维特比最大似然序列译码最得力的工具。

8.2秩距离码

8.2.1基本概念

1．矩阵的秩及矢量秩的性质

设H是GF(qm)上的ab阶矩阵（8－25）H在GF(q)上的秩定义为GF(q)上的最大线性无关的列数或行数，用r(H，q)表示。（8－26）则r(aX，q)＝r(X，q)，X∈GFn(qm)即对X乘以常数，不会改变X的秩。

2.秩距离及性质

两个矢量X，Y∈GFn(qm)之间的秩距离定义为dr(X，Y)＝r(X-Y，q)（8－27）秩距离dr(X，Y)有以下性质：

(1)对称性即若X，Y是特征不为2域中的元素，则秩距离不满足对称性，但在特征为2的域中，则满足对称性。(2)非负性

dr(X，Y)≥0。

(3)满足距离三角不等式。

可见，除了对称性以外，秩距离的性质与汉明距离的性质相同。8.2.2矩阵表述

下面先介绍秩距离码的定义，然后介绍最大秩距离码以及它的校验矩阵和生成矩阵。

秩距离度量下的GF(q)上n维线性空间中的k维子空间，定义为GF(q)上的（n，k)秩距离码。可见秩距离码也是一个线性码，除距离度量不同之外，与以前介绍的线性分组码没有根本不同。

GF(q)上的秩距离码C的最小距离定义为：（8-28）

设Cl，C2是二个秩距离为dr，码长为n的秩距离码。设它们的码字数目分别为

|C1|＝M1(n，dr)和＝M2(n，dr)。ri(X)(i＝1，2)表示码Ci中码字X的秩距离。若对所有码字X，有r1(X)≤r2(X)，则M1(n，dr)≤M2(n，dr)（8-29）

类似汉明距离度量，对所有线性分组码有，同样对秩距离码也有相同的限。因此对于任何线性(n，k)秩距离码，秩距离dr≤n—k＋1。事实上，选择rl＝(X，q)，r2＝rH(X)为汉明意义上的矢量X的重量。显然r(X，q)≤rH(X)（8-30）若使d＝n-k＋1，则这种码称为最大秩距离码，用MRD表示。由于MRD码在构造各种密码体制和认证系统中起着重大作用，因此下面主要介绍这类码的一些基本性质。

设H和G分别是秩距离码C的校验矩阵和生成矩阵。

定理8-1

当且仅当对GF(q)上任何秩距离为dr－1的（dr－1）n阶矩阵Y，有r(YHT，qm)＝dr—1(8-31)则码C的最小秩距离为dr，且必在GF(q)上存在一个dr×n阶矩阵Y0，有r(Y0HT，qm)<d

(8-32)

定理8-2

当且仅当GF(q)上的（n—k)×n阶矩阵Y的秩为n一k时，即r(YHT，qm)＝n—k

（8-33）则由此H矩阵所确定的码C是MRD码。

定理8-3MRD码的对偶码也是MRD码。

上述三个定理的证明，请参阅有关资料，这里不再介绍。下面介绍最大秩距离码的构造。

设hi∈GF(qm)(i＝1，2，…，n)，且假定这些元素在GF(q)上线性无关。设drn，则有以下监督矩阵（8-34）

事实上对于dr＝n-1这是非常明显的,因为由定理8-1在GF(q)上存在有一组线性无关的元素 满足以下关系(s＝1，2,…,n-2)(8-36)8.2.3.秩循环码

设GF（qN)上的所有N重集合{(x0，x1，…，xN—1)｜xi∈GF（qN)}为FN。令X＝（x0，x1，…,xN-1）∈FN

（8-37）称（8-38）为X的[s]循环移位。其中[s]＝qs，显然是由X右循环移位，且X的每一分量同时升高qs幂得到的。一个秩距离分组码M中任一码组Ｃ的[s]循环移位后得到的，若也是该码的码字，则称M是[s]循环码。当然，Ｃ与有相同的秩。下面主要介绍GF(q)上的[1]循环码。

由有限域上循环码的理论可知，循环码是模xn－1多项式剩余类环中的一个主理想。同样[1]循环码也是模z[N]－z线性化多项式剩余类环LN[z]上的一个主理想。它的生成元G(z)是z[N]－z的一个因子，它就是[1]循环码的生成多项式：z[N]－z＝G(z)H(z)（8-39）式中：它们是GF(q)上的线性化多项式，分别称为[1]循环码的生成多项式与校验多项式。若G(z)为N—K次多项式，则由它生成一个[n，k]秩距离循环码，它的每一码字：C(z)＝U(z)·G(z)（8-40）式中：U(z)＝u0z[0]十ulz[l]＋…＋uk—1zk-1是GF(q)上的线性化信息多项式。该码的生成矩阵与监督矩阵分别为：（8-41）（8-42）式中：r＝N－K，且G（z）＝G0z[0]＋G1z[1]＋…＋Grz[r]H(z)＝H0z[0]＋H1z[1]＋…＋Hkz[k]

8.3突发错误的纠正

8.3.1基本概念

对于给定的纠突发错误能力b和码长n，当然希望它能有最小的冗余度n－k。下面的结论将给出这种基本关系。

(1)一个(n，k)线性码，若要发现长度不大于b的突发错误，其充要条件是n－k≥b,因为能发现错误的充分条件是伴随式不为零。

可以证明，对于任何长度不大于b的突发Eb，可使Sb＝EbHT≠0，故可检错。其次,长度不大于b的突发Eb不能作为一个码字，否则无法区分错误与正确。为做到这一点，在任意给定位置上的两个突发Eb1和Eb2不能出现在标准阵列的同一陪集中，否则Eb1＋Eb2＝Eb3就要成为一个码字。因此包括零长度突发错误在内的共2b个突发错误必须分布在不同陪集中，因此2n-k≥2b，即n-k≥b。

(2)一个(n，k)线性码，若要纠正所有长度不大于b的突发错误，则n－k≥2b。

若要纠正不大于b的突发错误，则任何长度为b的两个突发E1和E2不能出现在同一陪集中，否则若E1放在陪集首，E2就无法纠正。E1和E2不能放在同一陪集中，这不仅意味着E1和E2的组合不能作为码字，还意味着在任意给定的两个位置上的所有不大于b的突发错误的不同组合不能出现在同一陪集中，这种组合共有22b种，所以应有2n-k≥22b，即n-k≥2b。

(3)一个(n，k)线性码，若能纠正不大于b的所有突发错误，同时又能发现所有长度不大于s的突发错误，其中s≥b，则n-k≥b+s。

因为s≥b，所以n-k≥s＋b≥2b，所以能纠正长度不大于b的所有错误。如果在纠正上述突发错误的同时还要发现长度不大于s的所有突发错误，则这两种突发错误的组合不能成为一个码字，这意味着在任意给定位置上的两种突发错误的不同组合不能出现在阵列的同一陪集中，而这种组合共有2b＋s种，它们应处在不同陪集中，所以n-k≥b＋s。8.3.2纠突发错误的码

1.法尔(Fire)码

法尔码是最大的一类用分析方法构造的纠单个突发错误的二进制循环码。它的构造方法和译码都比较简单，因此是一类比较实用的码。

令P(x)是指数为e的m次不可约多项式，即e是使P(x)|x6-1的最小正整数。法尔码的生成多项式和码长分别为：g(x)＝P(x).(x2b-1＋1)n＝lcm（2b-1,e）(8-43)(8-44)显然n一k＝m＋2b一1。

【例8－16】设b＝5，P(x)＝x5＋x2＋1。求对应法尔码生成多项式和码长。

解由于P(x)是本原多项式，所以e＝25－1＝31。

因此g(x)＝(x9＋1)(x5＋x2十1)＝x14＋x11＋x9＋x5＋x2＋1n＝lcm(9,31)＝279因此该法尔码是一个(279，265)的纠正不大于5位的单个突发错误的循环码。

2.伯顿(Burton)码

伯顿码是一种纠单个定段突发错误的循环码，b个相邻码元为一个码段。设P(x)是指数为e的b次不可约多项式，且与xb＋1互素，则伯顿码的生成多项式和码长分别为：

g(x)＝P(x)·(xb＋1)（8-45）（8-46）它的构造方法完全与法尔码类似，是能纠正单个定段突发错误的(n，n－2b)码。 8.4级联码及交织码

8.4.1级联码

级联码是一种由短码构造长码的一类特殊的、有效的方法。它首先是由范尼(Forney)于1966提出的。用这种方法构造出的长码不像一般长码那样需要复杂的译码设备。通常采用一个二进制的(n1，k1)码C1作内编码，另一个非二进制的(n2，k2)码C2作外编码就能组成一个简单的级联码。一般的外编码C2采用的是RS码，而内编码C1既可采用分组码亦可采用卷积码。其原理性方框图如图8－13所示。图8－13串联级联码原理性方框图

在编码时，首先将k1、k2个二进制信息元划分为k2个字节，每一个字节有k1个信息元。同时每一个字节内的k1个信息元按照二进制分组码或卷积码编成(n１，k1)的内码C1，即字节间共有k2个字节，则一般按照非二进制RS码编成(n2

，k2)的外码。最后将两者串接构成总共有n１n2码元的编码(n１n2

，k1k2)＝(n１k1)·(n2

k2)。若内码与外码的最小距离分别为d1和d2，则它们级联后的级联码最小距离至少为d1·d2

，级联码编译码亦可分为两步进行，其设备仅是C1与C2直接组合，显然,它比直接采用一个长码构成时设备要简单得多。

1984年美国NASA给出一种用于空间飞行数据网的级联码编码方案，以后被人们称为标准级联码系统，它采用(2，1，7)卷积码作为内码、(255，223)RS码作为外码，并加上交织器与去交织器。该级联码在AWGN信道的深空通信中，当Eb/N0=2.53dB时，Pb≤10-6，其方框图如图8－14所示。图8－14标准级联码系统8.4.2交织码

在某种意义上说，交织编码是一种信道改造技术，它通过信号设计将一个原来属于突发差错的有记忆信道改造为基本上是独立差错的随机无记忆信道。交织编码原理方框图如图8－15所示。图8－15交织编码原理方框图下面，通过一个简单的例子来讨论交织器与去交织器的设计，以及如何利用交织与反交织变换，将一个突发错误的有记忆信道改造为独立差错的无记忆信道。假若发送一组信息X＝［x1x2…x24x25］，首先将X送入交织器，同时将交织器设计成按列写入、按行取出的5×5阵列存储器；然后从存储器中按行输出送入突发差错的有记忆信道，并将其送入反交织器，便完成了交织器的相反变换，即按行写入、按列取出的仍是一个5×5阵列存储器。反交织器的输出，即阵列存储器中按列输出信息的差错规律就变成了独立差错。其示意图如图8－16所示。图8－16分组交织编码实现方框图

因为X＝［x1x2x3x4……x23x24x25］

(8-47)则交织矩阵:（8-48）对此矩阵按列写入、按行读出，得：(8-49)假设突发信道产生以下两个突发:第一个突发产生于x1至x21连错5个；第二个突发产生于x13至x4连错4个。故(8－50)则去交织矩阵为（8-51）对此矩阵按行写入、按列读出，得:X[3]＝[y1x2x3y4x5y6x7x8x9x10y11x12y13x14

x15y16x17x18x19x20y21x22y23x24x25]由上述分析可见，经过交织矩阵与反交织矩阵的信号设计变换后，原来信道中产生的突发错误，即5个连错和4个连错变成了无记忆随机性的独立差错。推广至一般情况，则称这类交织器为周期性的分组交织器，其分组长度为L＝M×N

(8-53)故又称之为(M，N)分组交织器。它将分组长度L分成M列N行并构成一个交织矩阵，该交织矩阵存储器是按列写入按行读出，读出后送至发