第6章信道编码1 2012

1第6章信道编码6.1信道编码的概念

6.2信道编码定理

6.3线性分组码2第6章信道编码

信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：如何正确接收载有信息的信号 －－线路编码如何避免少量差错信号对信息内容的影响 －－纠错编码36.1信道编码的概念进行信道编码是为了提高信号传输的可靠性，改善通信系统的传输质量，研究信道编码的目标是寻找具体构造编码的理论与方法。从原理上看，构造信道码的基本思路是根据一定的规律在待发送的信息码元中人为地加入一定的多余码元(称为监督码)，以引入最小的多余度为代价来换取最好的抗干扰性能。

46.1.1信道编码的分类

对不同的信道需要设计不同类型的信道编码方案，按照信道特性进行划分，信道编码可分为：以纠独立随机差错为主的信道编码、以纠突发差错为主的信道编码和纠混合差错的信道编码。从功能上看，信道编码可分为检错(可以发现错误)码与纠错(不仅能发现而且能自动纠正)码两类，纠错码一定能检错，检错码不一定能纠错，平常所说的纠错码是两者的统称。

56.1.1信道编码的分类根据信息码元与监督码元之间的关系，纠错码分为线性码和非线性码。

线性码——信息码元与监督码元之间呈线性关系，它们的关系可用一组线性代数方程联系起来。非线性码——信息码元与监督校元之间不存在线性关系。

66.1.1信道编码的分类按照对信息码元处理的方法的不同，纠错码分为分组码和卷积码。

分组码----把信息序列以每k个码元分组，然后把每组k个信息元按一定规律产生r个多余的监督码元，输出序列每组长为n=k+r，则每一码字的r个校验元只与本码字的k个信息位有关，与别的码字的信息位无关，通常记分组码为(n,k)。

76.1.1信道编码的分类其中分组码又可分循环码和非循环码：对循环码而言，其码书的特点是，若将其全部码字分成若干组，则每组中任一码字中码元循环移位后仍是这组的码字；对非循环码来说，任一码字中的码元循环移位后不一定再是该码书中的码字。86.1.1信道编码的分类

卷积码----把信息序列以每k0(通常较小)个码元分段，编码器输出该段的监督码元r=n-k0

不但与本段的k0个信息元有关，而且还与其前面L段的信息码元有关，故记卷积码为(n,k0,L)。按照每个码元的取值来分，可有二元码和多元码。由于目前的传输或存储系统大都采用二进制的数字系统，所以一般提到的纠错码都是指二元码。

96.1.1信道编码的分类106.1.2与纠错编码有关的基本概念

在通信系统的接收端，若接收到的消息序列R和发送的码符号序列C不一样，例如R=(11000)，而C=(10001)，R与C中有两位不同，即出现两个错误，这种错误是由信道中的噪声干扰所引起的。116.1.2与纠错编码有关的基本概念1.码长、码重和码距码字中码元的个数称为码字的长度，简称码长，用n表示。码字中非“0”码元的个数称为码字的汉明重量(简称码重，记作W)。对二进制码来说，码重W就是码字中所含码元“1”的数目，例如码字“110000”，其码长n=6，码重W=2。两个等长码字之间对应码元不相同的数目称为这两个码组的汉明距离(简称码距)。例如码字“110000”与“100001”，它们的汉明距离D=2。

126.1.2与纠错编码有关的基本概念在某一码集C中，任意两个码字之间汉明距离的最小值称为该码的最小距离dmin，即：例如：码组C={0111100，1011011，1101001}的最小码距dmin=3。从避免码字受干扰而出错的角度出发，总是希望码字间有尽可能大的距离，因为最小码距代表着一个码组中最不利的情况。

136.1.2与纠错编码有关的基本概念2.错误图样为了定量地描述信号的差错，定义收、发码之“差”为差错图样。差错图样E＝发码C-

收码R

（模M）。例：8进制(M=8)码元，若发码 ：C=（0,2,5,4,7,5,2）收码变为：R=（0,1,5,4,7,5,4）差错图样 E=C-R=（0,1,0,0,0,0,6）（模8）二进制码：E=CR或

C=RE。

146.1.3错误的种类1、随机错误：由随机干扰引起。(前后位置无关，时间无关，差错以等概率发生)特点：因为干扰是随机的，所以各码元是否发生错误是相互独立的，不会成片出错。2、突发错误：由突发干扰引起（前后相关，成堆出现）。特点：因为突发干扰是突然出现的，且能持续一段时间，同时相对功率较大，所以错误往往成片出现。常见错误有两种：随机错误和突发错误

（在一个突发错误持续长度内，开头和末尾的码元总是错的，中间一些码元不一定都错，但错的码元数较多）如闪电和开关瞬态往往引起突发错误。156.1.2与纠错编码有关的基本概念3.重复码和奇偶校验码

1)重复码构成重复码的方法是当发送某个信源符号ai时，不是只发一个，而是连续重发多个，连续重发的个数越多，重复码的抗干扰能力就越强，当然效率也越低。

166.1.2与纠错编码有关的基本概念不重复时为(1，1)重复码，如图所示：重复一次时为(2，1)重复码，如图所示：

176.1.2与纠错编码有关的基本概念重复二次时为(3，1)重复码，如图所示：

186.1.2与纠错编码有关的基本概念

2)奇偶检验码奇偶校验是一种最基本的校验方法。构成奇偶检验码的方法是在每k个二进制信息位后加上一个奇(偶)监督位(或称校验位)，使码长n=k+r，同时使码中“1”的个数恒为奇数(或偶数)，如图所示。在奇偶校验码中，监督位r=1，它是一种码重W为奇数(或偶数)的系统分组码。

196.1.2与纠错编码有关的基本概念206.1.2与纠错编码有关的基本概念

奇校验----如果信息码元中“1”值的个数为奇数个，则校验码元值为“0”；如果信息码元中“1”值的个数为偶数个，则校验码元值为“1”。即所有信息码元与校验码元的模二和等于“1”。偶校验----如果信息码元中“1”值的个数为偶数个，则校验码元值为“0”；如果信息码元中“1”值的个数为奇数个，则校验码元值为“1”。即所有信息码元与校验码元的模二和等于“0”。

216.1.3检错与纠错原理

要纠正传输差错，首先必须检测出错误。而要检测出错误，常用的方法是将发送端要传送的信息序列(常为二进制序列)中截取出长度相等的码元进行分组，每组长度为k，组成k位码元信息序列M，并根据某种编码算法以一定的规则在每个信息组的后面产生r个冗余码元，由冗余码元和信息码元一起形成“n位编码序列”，即信号码字C，n位的码字比信息码长(有n=k+r个码元)，因而纠错编码是冗余编码。226.1.3检错与纠错原理译码就是利用校验关系进行检错、纠错的，在接收端收到的位码字中，信息码元与冗余码元之间也应符合上述编码规则，并根据这一规则进行检验，从而确定是否有错误。这就是差错控制的基本思想。

236.1.3检错与纠错原理分组码一般用符号(n,k)表示，其中k是每组二进制信息码元的数目，n是编码组的长度(简称码长)，即编码组的总位数，n-k=r为每码组中的校验码元(或称监督位)数目。通常，将分组码规定为具有如图所示的结构。图中前面k位为信息位，后面附加r个校验位。

24奇偶校验方法。增加偶(或奇)校验位使得对消息序列而言校验方程成立，当校验位数增加时，可以检测到差错图样的种类数也增加，但同时码率减小。n重复码方法。重复消息位使之可以检测出任意小于n个差错的错误图样。等重码方法。设计码字中的非“0”符号个数(若是二进制码则为“1”的个数)恒为常数，使码集C由全体重量恒等的n长矢量组成。6.1.3检错与纠错原理256.1.3检错与纠错原理表所示为一种用于表示数字“0”到“9”的五中取三等重码(所有码字的码重都等于“3”)的例子。

123456789001011110011011011010001111010111100011101001101101266.1.4检错与纠错方式和能力

1.检错与纠错方式自动请求重发方式----用于检错的纠错码在译码器输出端给出当前码字传输是否可能出错的指示，当有错时按某种协议通过一个反向信道请求发送端重传已发送的全部或部分码字，这种纠错码的应用方式称为自动请求重发方式(ARQ，Automatic-Repeat-reQuest)。27前向纠错方式----用于纠错的纠错码在译码器输出端总要输出一个码字或是否出错的标志，这种纠错码的应用方式称为前向纠错方式(FEC，Forward-errorcontrol)。另外用于检错与纠错的方式还有混合纠错(HEC，HybridErrorCorrection)。如图所示为上述几种检错与纠错方式示意图，图中有斜线的方框表示在该端检出错误。6.1.4检错与纠错方式和能力286.1.4检错与纠错方式和能力29ARQ方式：发送端用编码器对发送数据进行差错编码，通过正向信道送到接收端，而接收端经译码器处理后只是检测有无差错，不作自动纠正。如检测到差错，则利用反向信道反馈信号，请求发送端重发有错的数据单元，直到接收端检测不到差错为止。

6.1.4检错与纠错方式和能力30FEC方式：发送端用编码器对发送数据进行差错编码，在接收端用译码器对接收到的数据进行译码后检测有无差错，通过按预定规则的运算，如检测到差错，则确定差错的具体位置和性质，自动加以纠正，故称为“前向纠错”。6.1.4检错与纠错方式和能力31HEC方式：是检错重发和前向纠错两种方式的混合。发送端用编码器对发送数据进行便于检错和纠错的编码，通过正向信道送到接收端，接收端对少量的接收差错进行自动前向纠正，而对超出纠正能力的差错则通过反馈重发方式加以纠正，所以是一种纠检结合的混合方式。6.1.4检错与纠错方式和能力32

2.检错与纠错能力一个纠错码的每个码字都可以形成一个汉明球，因此要能够纠正所有不多于t位的差错，纠错码的所有汉明球均应不相交，判定纠错码的检、纠错能力可根据任意两个汉明球不相交的要求，由码的最小距离dmin来决定。

6.1.4检错与纠错方式和能力33定理1若纠错码的最小距离为dmin，那么如下三个结论的任何一个结论独立成立：①若要发现e个独立差错，则要求最小码距

②若要纠正t个独立差错，则要求最小码距

③若要求发现e个同时又纠正t个独立差错，则6.1.4检错与纠错方式和能力34

6.1.4检错与纠错方式和能力35定理说明，码的最小距离dmin越大，码的纠(检)错误的能力越强。但是，随着多余码元的增多，信息传输速率会降低得越多。通常用=k/n来表示码字中信息码元所占的比例，称为编码效率，它是衡量码性能的又一个重要参数。码率越高，信息传输率就越高，但此时纠错能力要降低，若=1时就没有纠错能力了。可见，码率与纠错能力之间是有矛盾。6.1.4检错与纠错方式和能力366.1.5矢量空间与码空间F表示码元所在的数域，对于二进制码，F代表二元域{0,1}。设n重有序元素的集合V={Vi

},若满足条件：V中矢量元素在矢量加运算下构成加群；V中矢量元素与数域F元素的标乘封闭在V中；分配律、结合律成立，则称集合V是数域F上的n维矢量空间，或称n维线性空间，n维矢量又称n重(n-tuples)。376.1.5矢量空间与码空间对于域F上的若干矢量

线性组合：

线性相关：其中任一矢量可表示为其它矢量的线性组合

线性无关或线性独立：一组矢量中的任意一个都不可能用其它矢量的线性组合来代替。386.1.5矢量空间与码空间一组线性无关的矢量，线性组合的集合就构成了一个矢量空间V，这组矢量就是这个矢量空间的基底。n维矢量空间应包含n个基底基底不是唯一的，例：线性无关的两个矢量（1,0）和（0,1）以及（-1,0）和（0,-1）可张成同一个两维空间。396.1.5矢量空间与码空间以（100）为基底可张成一维三重子空间V1，含21=2个元素，即以(010)(001)为基底可张成二维三重子空间V2，含22=4个元素，即以(100)(010)(001)为基底可张成三维三重空间V,含23=8个元素，V1和V2都是V的子空间。406.1.5矢量空间与码空间每个矢量空间或子空间中必然包含零矢量两个矢量正交：V1V2＝0两个矢量空间正交：某矢量空间中的任意元素与另一矢量空间中的任意元素正交正交的两个子空间V1、V2互为对偶空间(DualSpace)，其中一个空间是另一个空间的零空间（nullspace，也称零化空间）。416.1.5矢量空间与码空间码空间通常qn>>qk，分组编码的任务是要在n维n重矢量空间的qn种可能组合中选择其中的qk个构成一个码空间，其元素就是许用码的码集。

消息k长 (n,k)码字n长

qk

种分组编码器qn种

k维k重矢量n维n重矢量426.1.5矢量空间与码空间分组编码的任务：

①选择一个ｋ维n重子空间作为码空间。

②确定由k维k重信息空间到ｋ维n重码空间的映射方法。码空间的不同选择方法，以及信息组与码组的不同映射算法，就构成了不同的分组码。436.1.6随机编码运用概率统计方法在特定信道条件下对编码信号的性能作出统计分析，求出差错概率的上下限边界，其中最优码所能达到的差错概率上界称作随机码界。用这种方法不能得知最优码是如何具体编出来的，却能得知最优码可以好到什么程度，并进而推导出有扰离散信道的编码定理，对指导编码技术具有特别重要的理论价值。446.1.6随机编码在(N,K)分组编码器中随机选定的码集有qNM种，第m个码集(记作{c}m)被随机选中的概率是：设与这种选择相对应的条件差错概率是Pe({c}m)，那么全部码集的平均差错概率是：456.1.6随机编码必定存在某些码集某些码集若，就必然存在一批码集即差错概率趋于零的好码一定存在466.1.6随机编码码集点数M=qK占N维矢量空间总点数qN的比例是F=qK/qN

=q-(N-K)

。当K和N的差值拉大即冗余的空间点数增加时，平均而言码字的分布将变得稀疏，码字间的平均距离将变大，平均差错概率将变小。当F0即(N-K)时，能否让平均差错概率？Gallager在1965年推导了的上边界，并证明这个上边界是按指数规律收敛的。47

E(R)为可靠性函数，也叫误差指数。码率：R=(lbM)

/N

，

M是可能的信息组合数，M=qK，N是每码字的码元数，R表示每码元携带的信息量，单位是每符号比特（bit/symbol）。R在[0,R0]区间时E(R)~R曲线是斜率为-1（-45）的直线，E(R)反比于R；而当R=C时E(R)=0即可靠性为零。

6.1.7信道编码定理486.1.7信道编码定理49

正定理：只要传信率R小于信道容量C，总存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。逆定理：信道容量C是可靠通信系统传信率R的上边界，如果R>C，就不可能有任何一种编码能使差错概率任意小。6.1.7信道编码定理506.2纠错编译码的基本原理与分析

R不变，信道容量大者其可靠性函数E(R)也大；C不变，码率减小时其可靠性函数E(R)增大E(R) R0R1<R2C1

<C2

增大E(R)的途径516.2.1纠错编码的基本思路对于同样的码率，信道容量大者其可靠性函数E(R)也大；对于同样的信道容量，码率减小时其可靠性函数E(R)增大。可采取以下措施减小差错概率。(1)增大信道容量C增大E(R)的途径①扩展带宽。②加大功率。③降低噪声。52(2)减小码率R①q，N不变而减小K，这意味着降低信息源速率，每秒少传一些信息。②q，K不变而增大N，这意味着提高符号速率（波特率），占用更大带宽。③N，K不变而减小q，这意味着减小信道的输入、输出符号集，在发送功率固定时提高信号间的区分度，从而提高可靠性。6.2.1纠错编码的基本思路53(3)增加码长N随着N增大，矢量空间以指数量级增大，从统计角度而言码字间距离也将加大，从而可靠性提高。另外，码长N越大，其实际差错概率就越能符合统计规律。6.2.1纠错编码的基本思路54纠错能力的获取

(1)利用冗余度冗余度：在信息流中插入冗余比特，这些冗余比特与信息比特之间存着特定的相关性。冗余的资源：时间，频带，功率，设备复杂度。

6.2.1纠错编码的基本思路556.2.1纠错编码的基本思路

(2)噪声均化噪声均化：让差错随机化，以便更符合编码定理的条件从而得到符合编码定理的结果。基本思想：设法将危害较大的、较为集中的噪声干扰分摊开来，使不可恢复的信息损伤最小。①增加码长N②卷积③交错（或称交织）

566.2.2最优译码与最大似然译码译码器的任务是从受损的信息序列中尽可能正确地恢复出原信息。译码算法的已知条件是：①实际接收到的码字序列{r},r=(rn,rn-1,…,r1)②发端所采用的编码算法和该算法产生的码集Xn,满足③信道模型及信道参数。576.2.2最优译码与最大似然译码586.2.2最优译码与最大似然译码1.最佳译码(最大后验概率译码)在已知r的条件下找出可能性最大的发码作为译码估值，即令596.2.2最优译码与最大似然译码2.最大似然译码在已知r的条件下使先验概率最大的译码算法

也叫似然函数。利用贝叶斯公司可以建立先验概率和后验概率之间的关系：606.2.2最优译码与最大似然译码如果①构成码集的个码字以相同概率发送，满足。②对于任何r都有相同的值，满足。则最大等效于的最大，在此前提下最佳译码等效于最大似然译码。616.2.2最优译码与最大似然译码对于无记忆信道，

例：BSC信道的最大似然译码可以简化为最小汉明距离译码。汉明距离译码是一种硬判决译码。由于BSC信道是对称的，只要发送的码字独立、等概，汉明距离译码也就是最佳译码。626.3线性分组码m=(mk-1,…,m1,m0)c=(cn-1,…,c1,c0)码字c消息m(n,k)分组编码器

码集C能否构成n维n重矢量空间的一个k维n重子空间？如何寻找最佳的码空间？qk个信息元组以什么算法一一对应映射到码空间。

码率－－编码效率：Rc

=k/n

636.3线性分组码为了叙述方便，以下认为码失、码字、码组是同义词，对n重矢量、1n矩阵、行矢量等的数学表达式也不作严格区别。646.3线性分组码设有等概出现的M组待传信源消息，每组有k位，即。今加上r个多余位，使每组消息变成n=k+r位。而n位长的二进制序列共有2n个，但由于信息组只有2k个，故有2n-2k个n位序列不是码字。设码字的形式为：656.3.1生成矩阵和校验矩阵

线性分组码码空间C是由k个线性无关的基底张成的k维n重子空间，码空间的所有元素（即码字）都可以写成k个基底的线性组合，即这种线性组合特性正是线性分组码名称的来历。显然，研究线性分组码的关键是研究基底、子空间和映射规则，如图所示

666.3.1生成矩阵和校验矩阵Hn-k维n重对偶空间Dk维k重信息组空间mk维n重码空间cGn维n重空间Vn676.3.1生成矩阵和校验矩阵用gi表示第i个基底并写成矩阵再将k个基底排列成k行n列的G矩阵686.3.1生成矩阵和校验矩阵码空间的所有元素（即码字）都可以写成k个基底的线性组合。由于k个基底即G的k个行矢量线性无关，矩阵G的秩一定等于k。当信息元确定后，码字仅由G矩阵决定，因此我们称这k×n矩阵G为该(n,k)线性分组码的生成矩阵。696.3.1生成矩阵和校验矩阵1.生成矩阵G(k×n)的特点想要保证(n,k)线性分组码能够构成k维n重子空间，G

的k个行矢量gk-1,…,g1,g0必须是线性无关的，只有这样才符合作为基底的条件。由于基底不是唯一的，所以G也就不是唯一的。不同的基底有可能生成同一码集，但因编码涉及码集和映射两个因素，码集一样而映射方法不同也不能说是同样的码。706.3.1生成矩阵和校验矩阵2.系统形式的生成矩阵

(n,k)码的任何生成矩阵都可以通过行运算（以及列置换）简化成“系统形式”。

Ik是k×k单位矩阵，P是k×(n-k)矩阵。

716.3.1生成矩阵和校验矩阵3.生成的码字C

前k位由单位矩阵Ik决定，等于把信息组m原封不动搬到码字的前k位；其余的n-k位叫冗余位或一致校验位，是前k个信息位的线性组合。这样生成的（n,k）码叫做系统码。若生成矩阵G不具备系统形式，则生成的码叫做非系统码。系统化不改变码集，只是改变了映射规则。726.3.1生成矩阵和校验矩阵4.系统码若通过行运算和列置换能将两个生成矩阵G互等，则称这两个G等效。非系统码的G可通过运算转变为系统码的G。等效的两个G生成的两个(n,k)线性码也是等效的。因此，每个(n,k)线性码都可以和一个系统的(n,k)线性码等效。736.3.1生成矩阵和校验矩阵5.空间构成n维n重空间有相互正交的n个基底，选择k个基底构成码空间C，选择另外的(n-k)个基底构成空间H，C和H是对偶的CHT＝0,GHT=0。746.3.1生成矩阵和校验矩阵6.校验矩阵将H空间的n-k个基底排列起来可构成一个(n-k)×n矩阵，称为校验矩阵H。用来校验接收到的码字是否是正确的；G是(n,k)码的生成矩阵，H是它的校验矩阵；H是(n,n-k)对偶码的生成矩阵，它的每一行是一个基底。G则是它的校验矩阵。756.3.1生成矩阵和校验矩阵以(7,3)线性分组码为例。信息位k=3，则校验元个数为r=n-k，设码字为：,其中为信息元；为校验元。每个码元取值为“0”或“1”。设某(7,3)线性分组码各码字的校验元与信息元之间的关系由下述方程决定：766.3.1生成矩阵和校验矩阵

称此方程为该（7,3）线性分组码的校验方程，由于该码系的所有码字都按同一规则确定与校验，故又称为一致校验方程。776.3.1生成矩阵和校验矩阵如：信息组为101，即代入一致校验方程得：所以由信息组101编出的可送给信道传输的、具有一定纠错能力的码字为：1010011。同理可求出与其他7个信息组相对应的码字见下表：信息组对应码字对应码字信息组00000101001111111010110001110100100111001110100000001110100110100110100111001110786.3.1生成矩阵和校验矩阵为了运算方便，可将一致校验方程组写成矩阵形式：796.3.1生成矩阵和校验矩阵设则：或：（4×3）单位子阵806.3.1生成矩阵和校验矩阵线性分组码的一致生成矩阵与一致校验矩阵之间有着非常密切的关系，这种关系非常重要。下面说明它们的关系：由于生成矩阵G的每一行都是一个码字，而或者816.3.1生成矩阵和校验矩阵更进一步：结论：(n,k)线性分组码的一致生成矩阵G与一致校验矩阵H之间可方便地相互转换。或者826.3.1生成矩阵和校验矩阵例6.1(6,3)线性分组码，其生成矩阵是836.3.1生成矩阵和校验矩阵求：(1)计算码集，列出信息组与码字的映射关系。(2)将该码系统化处理后，计算系统码码集并列出映射关系。(3)计算系统码的校验矩阵H。若收码r=[100110],检验它是否码字？(4)根据系统码生成矩阵画出编码器电原理图。846.3.1生成矩阵和校验矩阵解(1)由得

令得信息码字系统码字000000000000000001 011101 001011010 110001 010110011 101100 011101100 111010 100111101 100111 101100110 001011 110001111010110 111010856.3.1生成矩阵和校验矩阵(2)对G作行运算，得系统化后的生成矩阵Gs

866.3.1生成矩阵和校验矩阵(3)876.3.1生成矩阵和校验矩阵(4)m0m1m2c0c1c2输入输出886.3.2线性分组码的纠错能力

N重码矢可与N维矢量空间XN中的一个点对应，全体码字所对应的点构成矢量空间里的一个子集。发码一定在这个子集里，传输无误时的收码也一定位于该子集。当出现差错时，接收的N重矢量有两种可能：一种是对应到子集外空间某一点；另一种对应到该子集，却对应到该子集的另一点上。

896.3.2线性分组码的纠错能力定理6.1任何最小距离dmin的线性分组码，其检错能力为（dmin-1）,纠错能力t为定理6.2线性分组码的最小距离等于码集中非零码字的最小重量

dmin=min{w(Ci

)} CiC

及Ci

0906.3.2线性分组码的纠错能力

定理6.3(n,k)线性分组码最小距离等于dmin的充要条件是：校验矩阵H中有（dmin-1)列线性无关。

定理6.4(n,k)线性分组码的最小距离必定小于等于(n-k+1)916.3.2线性分组码的纠错能力例：(7，4)线性码

926.3.2线性分组码的纠错能力各列都不相同，任意2列之和不等于0，2列线性无关；任意2列之和一定等于矩阵中某一列，任意3列线性相关。所以该码的最小距离为3，小于n-k+1=4。

(n,k)线性码最小距离dmin的上边界是n-k+1。如果我们设计的(n,k)线性码的dmin达到了n-k+1，就是达到了设计性能的极点。因此，dmin=n-k+1的码称为极大最小距离码

(MDC–MaximizedminimumDistanceCode)。936.3.3伴随式与标准阵列译码

定义差错图案E

二进制码中模2加与模2减是等同的，因此有E=R+C

及R=C+E

1.伴随式S的定义因为CHT=0(码字和校验矩阵的正交性)所以RHT=(C+E)HT=CHT+EHT=EHT946.3.3伴随式与标准阵列译码

1、如果收码无误：必有R=C即E=0，则EHT=0RHT=0。

2、如果收码有误：即E

0，则RHT

=EHT0。在HT固定的前提下，RHT仅仅与差错图案E有关，而与发送码C无关。定义伴随式S

S=(sn-k-1,…,s1,s0)=RHT=EHT

956.3.3伴随式与标准阵列译码

2.伴随式S的意义从物理意义上看，伴随式S并不反映发送的码字是什么，而只是反映信道对码字造成怎样的干扰。

差错图案E是n重矢量，共有2n个可能的组合，而伴随式S是(n-k)重矢量，只有2n-k个可能的组合，因此不同的差错图案可能有相同的伴随式。

接收端收到R后，因为已知HT，可求出S=RHT

；如果能知道对应的E，则通过C=R+E而求得C。966.3.3伴随式与标准阵列译码

3.差错图案E的求解可以通过解线性方程求解E：

976.3.3伴随式与标准阵列译码得到线性方程组：

sn-k-1=en-1h(n-k-1)(n-1)+…+e1h(n-k-1)1+e0h(n-k-1)0

s1=en-1h1(n-1)+…+e1h11+e0h10

s0=en-1h0(n-1)+…+e1h01+e0h00986.3.3伴随式与标准阵列译码上述方程组中有n个未知数en-1,…e1,e0

，却只有n-k个方程，可知方程组有多解。在有理数或实数域中，少一个方程就可能导致无限多个解，而在二元域中，少一个方程导致两个解，少两个方程四个解，以此类推，少n-(n-k)=k个方程导致每个未知数有2k个解。到底取哪一个作为附加在收码R上的差错图案E的估值呢？

996.3.3伴随式与标准阵列译码概率译码：把所有2k个解的重量(差错图案E中1的个数)作比较，选择其中最轻者作为E的估值。该方法概念上很简单但计算效率不高。依据：若BSC信道的差错概率是p，则长度n的码中错误概率：1006.3.3伴随式与标准阵列译码0个错1个错2个错…n个错

(1-p)n

p(1-p)n-1

p2(1-p)n-2

pn

>>>>>>…>>由于p<<1，出错越少的情况，发生概率越大，E的重量越轻，所以该译码方法实际上体现了最小距离译码准则，即最大似然译码。依据：若BSC信道的差错概率是p，则长度n的码中错误概率：1016.3.3伴随式与标准阵列译码

方法：(1)按最可能出现的2r个差错图案E，计算相应的伴随式S，并构造伴随式一差错图案表[(S,E)]。(2)对接收向量R计算伴随式S。(3)查[(S,E)]表得E。(4)纠错计算C=R-E。1026.3.3伴随式与标准阵列译码例：设某（7,3）线性分组码的一致校验矩阵为：发送端发送的码字为（注：接收端译码器并不知道发送码字）。试讨论下面三种接收情况下的判错情形：1036.3.3伴随式与标准阵列译码①接收端接收的码字为②接收端接收的码字为③接收端接收的码字为解:①当接收端接收的码字为时，故译码器判为没错。1046.3.3伴随式与标准阵列译码②当接收端接收的码字为时，又由其H阵知该(7,3)码为能纠1个错误的码型，且ST正好等于H阵中的第二列，因此可判定第二位有错。1056.3.3伴随式与标准阵列译码③当接收端接收的码字为时，译码器判为有错。又由于此时的伴随式ST与H中任一列均不同，故一定出现了两位或两位以上的错误，译码器无法判定错误究竟出现在哪些位上。1066.3.3伴随式与标准阵列译码伴随式计算电路(以上例中的(7,3)码为例)设接收字为1076.3.3伴随式与标准阵列译码码字输入移位寄存器组半加器1086.3.3伴随式与标准阵列译码伴随式计算电路组合逻辑电路纠错译码电路…………输入（信道输出）译码输出1096.3.3伴随式与标准阵列译码4.标准阵列译码表上述的概率译码，如每接收一个码R就要解一次线性方程，那就太麻烦了。好在伴随式S的数目是有限的2n-k个，如果n-k不太大，我们可以预先把不同S下的方程组解出来，把各种情况下的最大概率译码输出列成一个码表。这样，在实时译码时就不必再去解方程，而只要象查字典那样查一下码表，这样构造的表格叫做标准阵列译码表。1106.3.3伴随式与标准阵列译码表中所列码字是接收到的码字R；将没有任何差错时的收码R放在第一行，收码等于发码R=C(CCi,i=0,1,…2k-1),差错图案为全零E0=(0,0…0)，伴随式为全零S0=(0,0…0)。由于有2k个码字，码表有2k列。

在第2到第n+1的n行中差错图案的所有重量为1(共n个)。1116.3.3伴随式与标准阵列译码如果(1+n)<2n-k，再在下面行写出全部带有2个差错的图案(共个)。如果总行数(1+n+)仍然小于2n-k，再列出带有3个差错的图案，以此类推，直到放满2n-k行，每行一个Ej,对应一个不同的伴随式Sj。这样，表的行数2n-k正好等于伴随式的数目。1126.3.3伴随式与标准阵列译码S0E0S1E1

SjEj

E0+C0=0+0=0E0+C1=C1E0+Ci=CiE1+C0=E1

E1+CiEj+C0=EjEj+C1Ej+Ci

E1+C1

1136.3.3伴随式与标准阵列译码译码表中有2n-k行，每行是一个陪集，每陪集的第一个元素(位于第一列)叫陪集首。同一陪集（同一行）中的所有元素对应共同的一个伴随式。第一行陪集的陪集首是全零伴随式S0所对应的全零差错图案E0(无差错)，而第j行陪集的陪集首是伴随式Sj所对应的重量最小的差错图案Ej(C0=0,Rj=Ej)。1146.3.3伴随式与标准阵列译码译码表中有2k列，每列是一个子集，每子集的第一个元素(位于第一行)叫子集头。同一子集（同一列）中的所有元素对应同一个码字，第一列子集的子集头是全零码字C0，而第i列子集的子集头是码字Ci(E0=0,Ri=Ci)。1156.3.3伴随式与标准阵列译码例6.3一个(5,2)系统线性码的生成矩阵是G=设收码R=(10101)，构造标准阵列译码表，译出发码的估值解：(1)构造标准阵列译码表。分别以信息组m=(00)、(01)、(10)、(11)及已知的G求得4个许用码字为C1=(00000)、C2=(10111)、C3=(01101)、C4=(11010)。1166.3.3伴随式与标准阵列译码求出校验矩阵：1176.3.3伴随式与标准阵列译码列出方程组：伴随式有2n-k=23=8种组合，差错图案中代表无差错的有一种，代表一个差错的图案有种，代表两个差错的图案有种。只需挑选其中的两个，挑选方法可有若干种，不是唯一的。1186.3.3伴随式与标准阵列译码先将Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的线性方程组，解得对应的Sj分别是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴随式中，(011)所对应的差错图案是2k个即(00011)、(10100)、(01110)、(11001),其中(00011)和(10100)并列重量最轻，任选其中一个如(00011)。同样可得伴随式(110)所对应的最轻差错图案之一是(00110)。1196.3.3伴随式与标准阵列译码S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=001101000101011111001206.3.3伴随式与标准阵列译码将接收码R＝10101译码可选以下三种方法之一译码：(1)直接搜索码表，查得(10101)所在列的子集头是(10111)，因此译码输出取为(10111)。

(2)先求伴随式RHT=(10101)

HT=(010)=S4，确定S4所在行，再沿着行对码表作一维搜索找到(10101),最后顺着所在列向上找出码字(10111)。1216.3.3伴随式与标准阵列译码

(3)先求出伴随式RHT=(010)=S4并确定S4所对应的陪集首（差错图案）E4=(00010)，再将陪集首与收码相加得到码字C=R+E4=(10101)+(00010)=(10111)。上述三种方法由上而下，查表的时间下降而所需计算量增大，实际使用时可针对不同情况选用。1226.3.3伴随式与标准阵列译码对上例作进一步分析，还可以看到，该(5,2)码的dmin=3,纠错能力是t=INT[(3-1)/2]=1。因此，译码阵列中只有前6行具有唯一性、可靠性，真正体现了最大似然译码准则，而第7、8行的差错图案(00011)和(00110)中包含两个“1”，已超出了t=1的纠错能力，译码已不可靠。1236.3.3伴随式与标准阵列译码比如，当收码R＝(10100)时，根据码表译出的码字是(10111)，与收码R的汉明距离是2，然而收码R与全零码字(00000)的汉明距离也是2，为什么不能译成(00000)呢？事实上，码表的第7、8行本身就不是唯一的。注意在码表计算过程中，伴随式(011)所对应的4个差错图案中有两个并列重量最轻，如果当时选的不是(00011)而是(10100)，那么码表第7行就不是现在这样了。1246.3.4完备码(Perfectcode)任何一个二元(n,k)线性分组码都有2n-k个伴随式，假如该码的纠错能力是t，则对于任何一个重量小于等于t的差错图案，都应有一个伴随式与之对应，也就是说，伴随式的数目满足条件上式称作汉明限，任何一个纠t码都应满足上述条件。1256.3.4完备码(Perfectcode)某二元(n,k)线性分组码能使等式

成立，即该码的伴随式数目不多不少恰好和不大于t个差错的图案数目相等，相当于在标准译码阵列中能将所有重量不大于t的差错图案选作陪集首，而没有一个陪集首的重量大于t，这时的校验位得到最充分的利用。这样的二元(n,k)线性分组码称为完备码。

1266.3.4完备码(Perfectcode)1.汉明码(HammingCode)

汉明码不是指一个码，而是代表一类码。汉明码的纠错能力t=1，既有二进制的，也有非二进制的。二进制时，汉明码码长n和信息位k服从以下规律：(n,k)=(2m-1,2m-1-m)

其中m=n-k，是正整数。当m＝3、4、5、6、7、8…时，有汉明码(7,4)、(15,11)、(31,26)、(63,57)、(127,120)……。1276.3.4完备码(Perfectcode)汉明码是完备码，因为它满足上述等式。1286.3.4完备码(Perfectcode)汉明码的校验矩阵H具有特殊的性质，能使构造方法简化。一个(n,k)码的校验矩阵有n-k行和n列，二进制时n-k个码元所能组成的列矢量总数是2n-k-1,恰好和校验矩阵的列数n=2m-1相等。只要排列所有列，通过列置换将矩阵H转换成系统形式，就可以进一步得到相应的生成矩阵G。1296.3.4完备码(Perfectcode)例6.4构造一个m=3的二元(7，4)汉明码。解：先利用汉明码的特性构造一个(7，4)汉明码的校验矩阵H，再通过列置换将它变为系统形式：

0001111列置换1110100 H= 0110011 0111010=[PT

I3] 1010101 1101001再得生成矩阵G为

1000101 G=[I4

P]=0100111 0010110 0001011 1306.3.4完备码(Perfectcode)

2.高莱（Golay）码是二进制（23，12）线性码，其最小距离dmin＝7，纠错能力t=3。是完备码，因为满足等式

223-12=2048=在(23,12)码上添加一位奇偶位即得二进制线性（24，12）扩展高莱码，其最小距离dmin＝8。1316.3.5循环码

1.循环码的定义定义1：如将一个码系的全部码字分成若干组，则每组的所有码字可由其中任一码字的循环移位得到。如(7,3)循环码分成两个组

(0000000)

(0010111)(0101110)(1011100)(0111001)(1110010)(1100101)(1001011)1326.3.5循环码又如：(7,4)循环码分成四个组

(0000000)

(1111111)

(1000101)(0001011)(0010110)(0101100)(1011000)(0110001)(1100010)

(1001110)(0011101)(0111010)(1110100)(1101001)(1010011)(0100111)1336.3.5循环码

定义2:一个(n,k)线性分组码C，若它一个码矢的每一循环移位都是C的一个码字，则C是一个循环码。

循环码是一种线性码，因此线性码的一切特性均适合于循环码；但它的特殊性是其循环性，码字集合或者说码组中任意一个码字的循环移位得到的序列仍是该码字集合中的码字，即它对循环操作满足封闭性。1346.3.5循环码2.循环码的多项式描述一般(n,k)线性分组码的k个基底之间不存在规则的联系，因此需用k个基底组成生成矩阵来表示一个码的特征。而循环码的k个基底可以是同一个基底循环k次得到，因此用一个基底就足以表示一个码的特征。既然只有一个基底，就无需矩阵，只要用多项式作为数学工具就足够了。1356.3.5循环码3.循环码的多项式定义把码字C＝[cn-1cn-2

…c1c0]与一个不大于n-1次的码多项式C(x)对应起来。

码多项式C(x)定义为：

C(x)=cn-1xn-1+cn-2xn-2

+…+c1x+c0

对于二进制码，ci{0,1},i=0,…，n-1。1366.3.5循环码循环移一位：(cn-1cn-2

…c1c0)(cn-2

…c1c0cn-1)循环移一位：C0(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0

C1(x)=

cn-2xn-1+cn-3xn-2+…+c0x+cn-1比较循环移位的前后，可用如下的多项式运算来表达循环移位

移1位：

C1(x)=xC0(x) mod(xn+1)

移2位：

C2(x)=xC1(x)=x2C0(x) mod(xn+1)

移n-1位：Cn-1(x)=xCn-2(x)=xn-1C0(x) mod(xn+1)1376.3.5循环码4.码字的组成根据码空间封闭性，码字的线性组合仍是码字。C(x)=a0C0(x)+a1xC0(x)+a2x2C0(x)+…+an-1xn-1C0(x)=(a0+a1x

+a2x2+…+an-1xn-1)C0(x)=A(x)C0(x) mod(xn

+1) 其中C0(x)是一个码多项式，而A(x)是次数不大于n-1的任意多项式。对于二进制码，ai{0,1},i=0,…，n-1。1386.3.5循环码5.生成多项式C(x)=m(x)g(x)码多项式信息多项式生成多项式

生成多项式不是唯一的；

g(x)＝x

n-k

+gn-k-1x

n-k-1+…+g2x2+g1x+1

是(n-k)次的首一码多项式，即(n-k)次项的系数为1。g(x)一定是(xn+1)的因子。1396.3.5循环码

几个关于生成多项式的定理

定理1：在(n,k)循环码中，生成多项式g(x)是唯一的(n-k)次多项式，且次数是最低的。定理2：在(n,k)循环码中，每个码多项式C(x)都是生成多项式g(x)的倍式，而每个g(x)倍式的次数小于或等于(n-1)的多项式必为(n,k)循环码的码多项式。1406.3.5循环码

定理3：(n,k)循环码的生成多项式g(x)是xn+1的因式，即xn+1=h(x)g(x)定理4：若g(x)是一个(n-k)次多项式，且为xn+1的因式，则g(x)生成唯一一个(n-k)循环码码系。以上几个定理说明：构建一个(n,k)循环码时，只要分解多项式xn+1的因式，从中取出(n-k)次因式作生成多项式即可。1416.3.5循环码6.校验多项式多项式xn+1可因式分解为xn+1＝g(x)h(x)的形式；如果g(x)代表(n,k)循环码的生成多项式，则h(x)代表该循环码的一致校验多项式，其阶次为k。h(x)的校验作用表现在：任何码多项式C(x)与h(x)的模xn+1乘积一定等于0，而非码字与h(x)的乘积必不为0。

C(x)h(x)=m(x)g(x)h(x)=m(x)(xn+1)=0mod(xn+1)1426.3.5循环码例6.5研究一个长度n=7的循环码的构成方法对(x7+1)作分解，找出n-k次因式。

x7+1＝(x+1)(x3+x2+1)(x3+x+1)，

n-k因式g(x)对偶式h(x) 循环码

1(x+1) (x3+x2+1)(x3+x+1) (7,6)3(x3+x2+1)(x+1)(x3+x+1) (7,4)3(x3+x+1)(x+1)(x3+x2+1) (7,4)4(x+1)(x3+x2+1)(x3+x+1) (7,3)4(x+1)(x3+x+1)(x3+x2+1) (7,3)6(x3+x2+1)(x3+x+1)

(x+1) (7,1)1436.3.5循环码构成(7,3)循环码： 选g(x)=(x+1)(x3+x+1)=(x4+x3+x2+1)，则C(x)=m(x)g(x)=(m2x2+m1x+m0)(x4+x3+x2+1)。当输入信息m=(011)时，m(x)=(x+1)，C(x)=(x+

1)(x4＋x3＋x2＋1)=x5+x2+x1+

1， 对应码矢C=(0100111)。1446.3.5循环码信息矢量m(m2m1m0)码矢C(c6c5c4c3c2c1c0)000001010011100101110111000000000111010111010010011111101001101001100111010100111456.3.5循环码6.系统循环码码字的前k位原封不动照搬信息位而后面(n-k)位为校验位：C(x)=xn-km(x)+r(x)产生系统循环码的方法：将信息多项式m(x)预乘xn-k，即右移(n-k)位；将xn-km(x)除以g(x)，得余式r(x)；得系统循环码的码多项式：C(x)=xn-km(x)+r(x)。1466.3.5循环码例6.6(7,3)循环码生成多项式是g(x)=x4+x3+x2+1，产生系统循环码。解：先以输入信息m=(011)即m(x)=(x+1)为例，①.xn-km(x)=x4(x+1)=x5+x4

②.(x5+x4)除以(x4+x3+x2+

1)，得余式(x3+x)③.C(x)=xn-km(x)

+r(x)＝(x5+x4)+(x3+x),