第6章信道编码

第6章信道编码信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：如何正确接收载有信息的信号－－线路编码如何避免少量差错信号对信息内容的影响－－纠错编码

描述编码：用于对特定数据信号的描述:

不归零码（NotReturntoZero，NRZ）约束编码：用于对特定信号特性的约束:HDB3码扩频编码：用于扩展信号频谱为近似白噪声谱并满足某些

相关特性:m序列纠错编码：用于检测与纠正信号传输过程中因噪声干扰导

致的差错：循环码信道编码的作用和分类消息m信道编码

编码信道

信道译码

码字C接收向量R消息^m编码信道模型编码信道n-1

当码字C和接受向量R均由二元序列表示，称编码信道为二元信道。如果对于任意的n都有：P(r/c)=∏p(ri/ci)则称此二进制信道为无记忆二元信道如果转移概率：p(0/1)=p(1/0)=pb则称此信道为无记忆二元对称信道BSC几个概念BSC转移概率BSC编码信道BSC输入输出关系等效为差错图案：随机序列或

第i位上的一个随机错误：差错图案e例如:C=[10000],e=[01000],R=?R=(11000)码元的组成及关系消息序列m总以k个码元为一组传输，称k个码元的码组为信息码组。信道编码器按一定规则对每个信息码组附加一些多余的码元，构成长为n个码元的码组c（信道编码）。附加的r=n-k个码元称为监督码元。检纠错是根据信道输出序列r,判断r是否可能是发送的c，或纠正导致r不等于c的错误。冗余编码：码字c的长度n一定大于消息m的长度k

纠错编码编码码率R：每个码字的序列符号（或码元）平均传送的消息比特数检错和纠错目的性质偶（或奇）校验方法：实现检纠错目的的一个基本方法。

一个偶校验位P是对消息m使得如下校验方程成立的二进制符号，即一个偶校验码码字

校验方程为1表明一定有奇数个差错，校验方程为0表明可能有偶数个差错。

检错和纠错方法重复消息位：实现检纠错目的第二个基本方法

一个n重复码是一个码率R为1/n的码，仅有两个码字C0和C1，传送1比特（k=1）消息。n重复码可以检测出任意小于n个差错的错误图案，纠正任意小于n/2个差错的错误图案。等重码或定比码：实现检纠错的第三个方法。

设计码字重量(码字中非0元素个数)w(c)恒为常数，即

5中取3等重码

1234567890010111100110110110100011110101111000111010011011015中取3等重码可以检测出全部奇数位差错，对某些码字的传输则可以检测出部分偶数位差错。纠错码的应用方式：前向纠错方式（FEC），自动请求重发（ARQ）方式，混合纠错（HEC）方式以及信息反馈（IRQ方式）FEC与ARQ纠错应用方式

检错和纠错方式

常用汉明距离来描述检纠差错的数目，对于两n长向量u，v汉明距离为：

最小汉明距离dmin（最小码距d）：任意两码字之间的汉明距离的最小值。检错和纠错能力定理:

对一个最小距离为dmin纠错码，如下三个结论仅有其中任意一个结论成立，

（1）

可以检测出任意小于等于个差错；

（2）

可以纠正任意小于等于个差错；（3）可以检测出任意小于等于l同时纠正小于等于t个差错，其中l和t满足最小码距与检纠错能力

纠错码的分类根据信息元和监督元之间的关系分为：线性码：信息元与监督元之间呈线性，可用一组线性方程联系起来；非线性码：信息元与监督元之间不具有线性关系。§6.2线性分组码

§6.2.1线性分组码的矩阵描述根据对信息码元处理方法的不同分为：

分组码：信息序列以每k个码元进行分组，每组k个信息元按一定规律产生r个监督码元，输出序列长为n=k+r，r只与k个信息位有关，记（n，k）。分组码分为循环码和非循环码。卷积码：以k个码元分段，r不仅与k个信息位有关，还与前面L段的信息元有关，记为（n，k，L）。线性分组码：通过预定的线性运算将长为k的信息码组变成长为n的码字（n>k），由2n个码字组成的集合称为线性分组码。（n，k）线性码：信息位长k，码字长n，监督位r=n-k，编码效率线性分组码线性分组码的矩阵描述一个（n,k）线性分组码C是称为码字c的n维向量的集合

C={c|c=mG}其中m为任意的k维向量并称为消息向量。线性分组码的生成矩阵例:(6,3)二进制分组码的输入信息组是m=(m2m1m0),码组输出是c=(c5c4c3c2c1c0)。已知输入、输出码元之间的关系式c5=m2,c4=m1,c3=m0,c2=m2+m1,c1=m2+m1+m0,c0=m2+m0，求码集C以及编码时的映射算法。解：将关系式列成线性方程组，然后写成矩阵形式如下：生成矩阵信息组

(m2m1m0)

码字（c5c4c3c2c1c0

)000000000000001011010010110011011101100100111101101100110110001111111010例6.2.13重复码是一个（3，1）线性分组码例6.2.2（4，3）偶校验码是一个（4，3）线性分组码n-k个校验位可用k个已知的信息位表示出来一致校验矩阵一致校验矩阵H与任意一个码字之积为零，因此有由G的每一行都是一个码字，因此有一直校验矩阵与生成矩阵的关系G是k行n列的秩为k（n≥k）的生成矩阵系统码：生成矩阵G具有如下形式对于系统码相应的一致校验矩阵Hs对偶码：以线性分组码的一致校验矩阵为生成矩阵称为原线性分组码的对偶码。例6.2.3一个（5，3）线性分组码的其中到的行初等变换过程为：？

例：考虑一个（7，4）码，其生成矩阵是：①对于信息组m=(1011),编出的码字是什么？②若接收到一个7位码r=(1001101),检验它是否为码字？解：设输入信息组编码后的码字①由c=mG可知，将m和G的值代入，可得对应码字本题由于是系统码，

前4位不必计算，后3个校验位可以根据生成矩阵G的分块阵P列出现行方程组如下将代入方程组，得所以码字为c=[1011000]。②H矩阵如下：根据式，如果接受到的r是属于码集C的某码字，必有；反之，如，说明r必定不是码字。将H和r=[1001101]代入式，得：说明r与H不正交，接收的r=(1001101)不是码字。检错译码：译码器输出为当前接收向量r和r是否有差错的标志s，即y=(r,s)。§6.2.2线性分组码的译码纠错译码的译码成功状态：译码器能够在达到译码码字差错概率最小条件下输出一个确切的码字，即。纠错译码的译码失败状态：译码器不能输出一个确切的码字，通常此时的输出y与检错译码输出相同。

伴随式S：(n,k）线性分组码的伴随式是一个r(r=n-k)维向量，则传输中一定有错误发生。，则传输中要么无差错发生，要么差错图案恰好为一个码字。

（1）汉明码汉明码不是指一个码，而是代表一类码；汉明码码长n和信息位k服从以下规律：(n,k)=(2m-1,2m-m-1)；汉明码的最小距离d=3；所以，纠错能力t=1；§6.2.3码例与码的重构例6.2.4一个二元（7，4）Hamming码的系统码形式的矩阵和校验矩阵分别为

等价的编码方程为

伴随式计算方程：（2）Hadamard码Hadamard码是由Hadamard矩阵派生出的一种纠错码

阶实Hadamard矩阵由元素为+1，-1的矩阵递归定义：Hadamard矩阵为正交矩阵，即中的任意不同两行（列）的点积为0，即

超正交矩阵：Hadamard矩阵中的第1列（全+1列）去掉后任两行的点积为-1。

将Hadamard矩阵元素+1/-1映射为0/1，则Hadamard矩阵映射后的行向量为一个二元向量，以这些二元向量的部份或全体就构成标准0/1二元意义上的分组码，并称为Hadamard码。具体的Hadamard码的选择构成有正交码、双正交码和超正交码三种形式。

（A）正交码：以的全部行向量的0/1映射向量为码字。（B）双正交码：以和-的全部行向量的0/1映射向量为码字。

（C）超正交码：以的全部行向量的0/1映射向量为码字。

例6.2.5（7，3）超正交码的超正交矩阵H8和生成矩阵G分别为

(3)里德-穆勒（Reed-Muller）码r阶码RM(r,m)是一种(n,k,d)线性分组码，满足其中各个子矩阵的定义为：1）G0为矩阵，由全1向量构成。2）G1为矩阵，由所有可能的m元组组成矩阵的列向量。3）G2为G1的所有两个不同行向量的叉积构成其全部行向量的矩阵。两向量的叉积为4）G3为G1的所有三不同行向量的叉积构成其全部行向量的矩阵。5）Gr为G1的所有r个不同行向量的叉积构成其全部行向量的矩阵。例6.2.6m=3的r阶RM码的各个子矩阵有（4）戈雷码

二元戈雷码是一种就纠3个错的完备线形分组码，满足：{n=23k=12由于

因此某种二元（23,12）码一定可以纠正任意小于等于3个差错，所以

(1)扩展(2)打孔(3)增广(4)删信(5)延长(6)缩短(7)乘积(8)级联(9)交织6.3循环码循环码是一种特殊的线性分组码，属于线性分组码的一个重要子类，也是目前研究最为透彻的一类码，大多数有实用价值的纠错码都是循环码。循环码与一般的线性分组码相比具有以下优点：循环码的编码及译码易于用简单的具有反馈连接的移位寄存器来实现。

定义：一个线性分组码，若具有下列特性，称为循环码。设码字c＝（cn-1，cn-2，…，c1，c0）若将码元左移一位，得c(1)＝（cn-2，…，c1，c0，cn-1）c(1)是同一个码序列C的一个码字。循环码的主要特点是：①理论成熟：可利用成熟的代数结构深入探讨其性质；②实现简单：可利用循环移位特性在工程上进行编、译码；③循环码的描述方式有很多，但在工程上最常用的是采用多项式的描述方法。信息码元码字00000000000010011101010010011101101110101001001110101101001111011010011111110100表1循环码的例子循环码的多项式描述

设有循环码字c=(cn-1cn-2…c1c0)

，则可以用一个次数不超过n-1的多项式惟一确定，其相应的多项式可表示为：

(1)

由循环码的特性可知，若c=(cn-1cn-2…c1c0)是循环码C的一个码字，则c(1)

=(cn-2cn-3…c0cn-1)

也是该循环码的一个码字，它的码多项式为：

(2)

比较式(1)和式(2)，得：

码多项式的系数码多项式的次数(cn-1≠0)该式说明，码字循环一次的码多项式C(1)(x)是原码多项式乘x后再除以xn+1所得的余式，即：

由此可以推知，C(x)的i次循环移位C(i)(x)是原码多项式C(x)乘xi

后再除以xn+1所得的余式，即：

表2(7,3)循环码的循环移位循环次数码字码多项式00011101x4+x3+x2+110111010x(x4+x3+x2+1)mod(x7+1)=x5+x4+x3+x21110100x2(x4+x3+x2+1)mod(x7+1)=x6+x5+x4+x231101001x3(x4+x3+x2+1)mod(x7+1)=x6+x5+x3+141010011x4(x4+x3+x2+1)mod(x7+1)=x6+x4+x+150100111x5(x4+x3+x2+1)mod(x7+1)=x5+x2+x+161001110x6(x4+x3+x2+1)mod(x7+1)=x6+x3+x2+x循环码的生成多项式定义：若g(x)是一个(n-k)次多项式，且是(xn+1)的因式，则由g(x)可以生成一个（n，k）循环码，g(x)称为该循环码的生成多项式。两个结论（1）（n，k）循环码中，存在着一个次数为(n-k)的首一码多项式g(x)（首一：多项式最高幂次项系数gn-k=1

）（gn-k=1）

使得所有码多项式v(x)都是g(x)的倍式，即：

故循环码完全由它的生成多项式确定。(2)(n，k)循环码的生成多项式g(x)一定是(xn+1)的因子，即

相反，如果g(x)是xn+1的n-k次因子，则g(x)一定是（n，k）循环码的生成多项式。生成多项式不唯一。（n，k）循环码的构造（1）对(xn+1)做因式分解，找出(n–k)次因式；（2）以该(n–k)次因式为生成多项式g(x)与不高于k–1次信息多项式u(x)相乘，即得到对应消息序列的码多项式v(x)。【例】一个长度n=7的循环码的构造方法（1）对x7+1作因式分解

故x7+1有如下因式：

一次因式：

三次因式：

四次因式：

（一个）

（两个）

（两个）

六次因式：

（一个）

n–k=1，k=6，生成一种（7，6）循环码；n–k=3，k=4，生成两种（7，4）循环码；n–k=4，k=3，生成两种（7，3）循环码；n–k=6，k=1，生成一种（7，1）循环码；（2）若以n-k次因式作为生成多项式，可供选择的有:例：要得到（7，4）循环码，可选n–k=3次多项式1+x2+x3或1+x+x3为生成多项式：

以g（x）=1+x2+x3为例，（信息位长度为4）

设信息多项式为：

则：循环码编码后的码多项式为：

例：

对于上述（7，4）循环码，有4个信息位，对应有16个信息序列，利用16个信息序列多项式与生成多项式的乘法运算，可得全部（7，4）循环码得16个码字，如下表所示：信息位码字信息位码字信息位码字信息位码字00010010010010000111111010110001011001011001011001011000011000111000101000101001101101100111110010101101000111010111010111010011010011010011010011110011100000000000011011111111循环组1循环组2循环组3循环组4任何码字的循环移位仍是码字，并非由一个码字循环移位可以得到所有码字，上述（7，4）码的码集由4组码字循环构成。结论：当一个循环码给定其生成多项式g（x）后，根据生成多项式就可以进行编码。（n，k）循环码是n维线性空间一个具有循环特性的k维的子空间，故（n，k）循环码的生成矩阵可用码空间中任一组k个线性无关的码字构成，即k个线性无关的码字构成（n，k）循环码的基底，基底不唯一。如何得到k个线性无关的码字？

方法：当循环码的生成多项式g（x）给定后，可以取g（x）本身加上移位k–1次所得到的k–1码字作为k个基底，即：

→构成基底

循环码的生成矩阵

若：

则：

各多项式对应的矢量分别为：

这k个矢量是线性无关的，且由g（x）循环移位得到，故都是码字，由它们构成一个k×n的矩阵，它们就是循环码的生成矩阵。按照g(x)系数的升幂排列【例】（7，4）循环码：

当一个循环码的生成矩阵确定后，其编码规则为：

按照g(x)依次循环右移得到xg(x)等等循环码的校验多项式一般情况下，多项式xn+1可因式分解为xn+1=g(x)·h(x)

g(x):(n，k)循环码的生成多项式，

h(x):(n，k)循环码的一致校验多项式，在因式分解中，g(x)和h(x)处于同等地位，既可以用g(x)去生成一个循环码，也可以用h(x)去生成一个循环码。设由g(x)生成的码为C，在由h(x)生成的码就是C的对偶码C⊥。

循环码的校验矩阵设

则：将上述矢量按逆序排列作为一个（n-k）×n矩阵的行矢量，则该矩阵就是码C的校验矩阵。按照h(x)系数的降幂排列注意若：G按照g(x)系数的升幂排列，则H要按照h(x)系数的降幂排列；若：G按照g(x)系数的降幂排列，则H要按照h(x)系数的升幂排列；系统循环码

1、系统循环码的编码步骤：(1)将k个消息位按升幂排列的次序写成消息多项式u（x）

；

(2)用xn–k

乘以u（x）得到一个次数≤(n-1)的多项式；

(3)用xn–k

u（x）除以生成多项式g（x）得余式p(x)（一致校验元）；

(4)联合p(x)和xn–k

u(x)得到系统循环码多项式v(x)=p(x)+xn–k

u(x)；

(5)将码多项式转换为码字。【例】（7，4）循环码：

求

的系统循环码字。

【解】

，n＝7，k＝4

（1）

（2）P(x)（3）（4）2、系统循环码的生成矩阵（1）由生成矩阵做初等行变换，将其变为形式，即为系统循环码的生成矩阵（单位阵在后，信息位在尾部）。

求系统形式的生成矩阵。【例】（7，4）循环码：

(2)分别求除以g(x)的余式（记为），由余式对应的矢量作行矢量构成的k×(n-k)的分块矩阵P，联合k×k的单位阵I就构成系统形式的生成矩阵：求系统形式的生成矩阵。【例】（7，4）循环码：

3、系统循环码的校验矩阵

（1）对非系统形式的校验矩阵作初等行变换，

变成[In-k，PT]的形式；（2）

(3)分别求除以h(x)的余式记为，由余式对应的逆矢量可得到系统形式的校验矩阵：【例】（7，4）循环码：

（1）（2）（3）k=4，n–k–1=2

循环码的伴随多项式若接收向量r的多项式表示为r(x)r(x)=c(x)+e(x)则s(x)=r(x)modg(x)=e(x)modg(x)若s(x)=0则无差错，若s(x)不等于0，则一定有差错产生。6.4卷积码将信息序列分隔成长度为k的一个个分组某一时刻的编码输出不仅取决于本时刻的分组，而且取决于本时刻以前的m个分组。称m为记忆长度称m＋1为约束长度最重要的三个参数(n,k,m)卷积码定义(n,k,m)卷积编码示意图

第i分组第i-1分组第i-2分组……第i-m分组

输入

卷积编码器（线性组合器）

c0ic1i…cn-2icn-1i

…………………………编码输出C

i卷积编码器的一般结构m0i-L……m0i-2m0i-1m0im1i-L……m1i-2m1i-1m1i串并变换线性组合器并串变换mk-1i-L……mk-1i-2mk-1i-1mk-1ic0ic1icn-2icn-1i…...........信号mi编码输出ci一个简单的卷积码编码例子初始状态：00设输入m