信息论 基础理论与应用第三版(傅祖芸)-第9章-讲义

第9章信道的纠错编码差错控制的基本形式纠错码分类及其基本概念线性分组码*循环码*卷积码香农定理指出，只要信息传输率小于信道容量，通过适当的编译码方法，就能以任意小的错误概率传输信息。但从实际工程看，并没有指出具体的编译码方法。这正是信道纠错编码要解决的问题。2021/6/271

香农第二定理指出，在信道中以信息传输率R小于信道容量条件下，使差错概率尽可能小的信道编译码原则是：编码原则：

在n次扩展信道输入符号序列中选取M个作为码字构成一组码C，并尽量使选取的M个码字中两两不相同码字的汉明距离尽可能地大；译码原则：当收到符号序列后，翻译成与之汉明距离最近的码字（最大似然准则）。几十年来，基于香农编码定理和以上编译码原则，科技工作者们开发了很多具有纠错能力的信道编码，如线性分组码、循环码、BCH码、卷积码、TCM码、Tuobo码等，在通信系统中得到了广泛应用。2021/6/2729.1差错控制的基本形式

现代数字通信系统中，利用检错和纠错的编码技术，使得信道编译码具备一定的差错控制能力。主要方式有：1、前向纠错(FEC)方式：

发送端信道编码器将信息码组编成具有一定纠错能力的码。接收端信道译码器对接收码字译码，若传输中产生的差错数目在码的纠错能力之内，译码器对差错进行定位并加以纠正。发送端接收端可检错纠错的码FEC检错、纠错2021/6/273FEC特点单向控制，不需要反馈信道；时延小，实时性好。为适应较差信道，冗余码元多，编码效率低，译码设备复杂。有一定的纠错范围限制。

适用于容错能力强的语音、图像传输；不适合容错能力弱的数据通信网。2、反馈重发(ARQ)方式（检错重发方式）：发送端发送的是能够发现（检测）错误的码；

接收端收到信道传输来的码后，译码器依据该码编码规则，判决出当前码字传输是否出错，并把判决结果（应答信号）反馈至发送端。发送端把接收端认为有错的信息重新发出，直到接收端认为正确为止。2021/6/274发送端接收端可检错的码ARQ应答信号检错、不纠错ARQ特点需要双向控制和反馈信道。系统的控制设备和存储设备复杂，但编译码设备较简单。接收端检错能力、系统纠错能力强，可大大降低系统误码率。具有自适应性。但若重发频繁，将使效率降低，甚至系统阻塞，使得连续性和实时性变差。

在短波、有线干扰情况复杂的信道，在计算机网络、分组交换网、卫星通信、移动通信中广泛应用。2021/6/2753、混合纠错(HEC)方式：前向纠错FEC+反馈重发ARQ

发送端发送的是兼有检错和纠错能力的码；接收端收到码字后，首先检测错误情况。当差错在码的纠错能力范围内，就自动纠错；当差错很多已经超出了纠错能力，但能够检测到错误，接收端就通过反馈信道，请求重发。发送端接收端可检错和纠错的码HEC应答信号检错、纠错HEC的特点总体性能介于FEC和ARQ之间，误码率低，但需要反馈信道。实时性和连续性好。设备不太复杂，应用广泛。2021/6/2764、信息反馈(IRQ)方式(回程校验方式):

接收端收到信道传输来的码后，全部由反馈信道发回发送端；发送端将发送的码与反馈回的码进行比较，发现错误后，把出错的码再次重发，直到接收端认为正确为止。发送端接收端消息（不编码）IRQ消息不检错、纠错IRQ特点：需要双向控制，需要反馈信道。系统的控制设备和存储设备相对复杂。无需编译码设备，接收端不具备检、纠错能力强，整体系统纠错能力强，可大大降低整个系统误码率。具有自适应性，但若重发频繁，将使传输效率降低，甚至系统阻塞，使得连续性和实时性变差。2021/6/2775、检错删除：

接收端发现错码后，立即将其删除。适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处。6、差错隐藏：在某些应用领域，如音乐、语音、图像、视频等领域，有差错或损失的部分数据对人的主观感受影响不大，此时，可根据已接收的数据采用内插或外推的技术，得到满足应用的输出数据。2021/6/2789.2纠错码分类1、纠错码的分类：按纠正错误的类型分类：纠随机差错码：无记忆信道中，噪声随机独立地影响每个码元，造成了随机差错；纠突发差错码：有记忆信道中，突发噪声可造成突发性的成群差错（如太阳黑子、雷电等引起）。纠混合差错码按应用目的分类：检错码——只能检测错误是否存在。纠错码——能够检测错误，并能够自动纠正错误。纠删码——能够纠正删除（丢失）了的信息。2021/6/279按码元取值分类：二元纠错码——目前最常用模式多元纠错码按码的结构中对信息序列的处理方式分类：分组码（n,k）——将信息序列每k位分组，再增加入r=n-k个冗余码元（校验元），校验元只由本组k个信息元按照一定规律产生，与其他信息组无关。卷积码（n,k0,L）——将信息序列每k0位分组，编码器输出该段的r=n-k0个与本组和前L组信息元相关的校验元，得到n长的码字。2021/6/2710按码的数学结构中校验元与信息元关系分类：线性码——线性关系，如线性方程组非线性码——非线性关系按码的是否具有循环性分类：循环码——分组码中任一码字的码元经过循环移位后，仍是本码中的码字。非循环码——至少有一个码字经循环移位后，不再是本码中的码字。按构造码的数学理论分类：代数码——近世代数，比较完善，如线性分组码。几何码——投影几何学算术码——数论，高等算术组合码——排列组合，数论2021/6/2711

实际的码可能同时分别具备以上某些特征，比如：某一纠错码可以同时是线性码、分组码、循环码、纠随机差错码、二元码、代数码等。2021/6/27129.3纠错码的概念及其纠错能力信息序列码字序列接收序列译码后信息序列噪声源E错误图样2021/6/2713

对编码器的输入信息序列，每k个信息符号分成信息组：

m=（mk-1,mk-2,…,m0），mi为信息元（i=0,1,…k-1）。（在q元数字通信系统中，共有种信息组。）码字：

为了纠错，编码器按一定规则增加产生r个多余符号，形成长度为n=k+r的序列：

C=(cn-1,cn-2,…,c0),ci为码元（i=0,1,…n-1）

校验元：增加的r=n-k位码元。

n：码长；k：信息组长度；r：校验元的位长。1、信息元、校验元、码字：2021/6/2714码C中的码字个数（k为信息位数）：（n,k）分组码：编码器输出为个码字组成的序列；许用码字：种码符号序列中，取出个作为分组码的码字。禁用码字：其余种码符号序列。卷积码（n,k0,L）:编码器输出的校验元不仅由本组信息元有关，也与其前面若干段的信息组所确定。k个信息位r个监督位an-1an-2...arar-1an-2...a0t码长n=k+r分组码的结构2021/6/27152、码字的汉明重量：汉明距离D(C1,C2)：对应位置上不同码元的个数。码的最小距离：dmin,d(C)汉明重量（汉明势）：码字中非零码元的个数W(C)。对2元码，汉明重量为码字中的“1”的个数。因此，二元码字的汉明重量和汉明距离为：模2加，若对应位不同则为1；相同则为0。其重量即为不相同的总位数，也就是两个码字的汉明距离。2021/6/27163、错误图样：码字序列通过信道传输送入译码器之前，由于信道的噪声干扰，使得接收序列中某些码元发生差错，可用错误图样（差错图样）定量描述：

E=(en-1en-2…e1e0)=C－R

二元数字通信系统中，码元传输错误图样：

E=(en-1en-2…e1e0),ei={0,1},i=0,1,…,n-1

若ei=0，第i位码元无差错；若ei=1，第i位码元发生差错；

2021/6/2717差错关系：接收序列=许用码字+错误图样

R=(rn-1rn-2…r1r0),ri={0,1},i=0,1,…,n-1

接收序列长度=码字长度=错误图样长度=n差错类型：随机差错是相互独立的、不相关，存在这种差错的信道是无记忆信道或随机信道；突发差错指成串出现的错误,错误与错误间有相关性,一个差错往往要影响到后面一串码元。2021/6/2718例

发送码字C=010110111,接收序列R=001110011,错误图样E=C+R=011000100

若为随机差错，错误码元为：2，3，7，错误数量=W(E)=3；若为突发差错，错误码元串长度为：6；出错范围：从错误图样E中的第一个1到最后一个1，其错误串中的0表示该位码元未发生错误。

2021/6/2719BSC（二元无记忆对称信道）的错误图样的出现概率设p为错误概率(<<1),则n次无记忆扩展信道中，随机差错的某错误图样E的出现概率为：

0位差错（全对）：W(E0)=0，1位随机差错：W(E1)=1,2位随机差错：W(E2)=2,……e位随机差错：W(Ee)=e,……n位差错（全错）W(En)=n,差错图样数概率2021/6/2720错误图样的总数：

发生多位错误的概率小于较少位数随机错误的概率。因此，无记忆信道中，一般优先纠正较少位数的随机错误，如1-2位，此时的误码率就可下降几个数量级。错误图样出现的概率关系（p<<1）：2021/6/27214、分组码的纠错能力与码最小距离的关系

一般地，分组码的码间最小距离dmin越大，意味着任意码字间的差别越大，则码的检、纠错能力越强。检错能力：如果一个分组码能检出总位数≤e个码元的任何错误图样，称码的检错能力为e。纠错能力：如果分组码能纠正总位数≤t个码元的任意错误图样，称码的纠错能力为t。2021/6/2722例重复码（3，1）为：（000，111），最小码间距为3。两个码字在传输后发生1位错误的接收序列形成两个互不相交的子集，按照最小距离译码准则，就能纠正1位随机错误。若发生2-3位错误，则接收序列进入另一个子集内，无法纠正。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a12021/6/2723定理：对于一个（n,k）分组码C，最小距离为dmin，则：⑴若能检测（发现）e个随机错误，则要求dmin≥e+1;

或：可检测出任意小于等于e=dmin－1个随机差错；

⑵若能纠正t个随机错误，则要求dmin≥2t+1;

或：可纠正任意小于等于t=INT[(dmin-1)/2]个随机差错；

⑶若能纠正t个随机错误，同时能检测e≥t个随机错误，则要求：dmin≥t+e+1。2021/6/2724

设V,U为距离最小的两个许用码字。若某码字传输发生错误，按最小距离准则译码，为了检测R=U+E：须dmin≥e+1，否则，会发生码字译码混淆，如R+E=V。eVUdmin

dmin=4,码距和检错能力关系示意图2021/6/2725tVUdmin图

dmin=5,码距和纠错能力关系示意图

设V,U为距离最小的两个许用码字。若某码字传输发生错误，按最小距离准则译码.

若R=V+E，W（E）=t，则若dmin<2t+1,则可能译码为U。错误！

当dmin≥2t+1，D（R，V）<D（R，U）译码为V。正确！2021/6/2726

设V,U为距离最小的两个许用码字。自接收序列中码字分别发生t位错误和e位错误，要检错、纠错，需要使得大球和小球不相交。故：须dmin≥e+t+1，否则，译码时引起码字译码混淆。edmin图

dmin=5,t=1,e=3码距和纠检错能力关系示意图tVUet2021/6/27275、分组码的码率二元无记忆信道中，（n，k）分组码个数为：也就是说，信道输入的消息数目为M。信道输入的信息流可以认为是去除了信源剩余度的的无记忆等概分布的信息流，则信道信息传输率（码率）：表示了信息位在分组码码字中所占比重，反映了每个码元符号携带的信息量。是衡量其有效性的重要参数。2021/6/27289.4线性分组码概念：

分组码中的信息元和校验元是用线性方程联系起来的一类差错控制码。线性分组码的编码过程：把信息序列按一定长度分成若干长度为k位的信息码组；编码器按照预定的线性规则(可由线性方程组规定)，把信息码组变换成n长(n>k)码字，其中(n－k)个附加码元是由信息码元的线性运算产生的。对于二元码，信息码组长k位，有2k个不同的信息码组，则有2k个码字与它们一一对应。2021/6/27292、一致监督（校验）方程编码方法：已知信息码组k位信息位，按预定规则生成r个监督（校验）码元，与信息位一起构成码字。要求：每个监督元是其中某些信息元的运算结果。（以下仅讨论二元码）例：k=3,r=4，构成(7,3)线性分组码。设码字为(C6,C5,C4,C3,C2,C1,C0)其中，C6,C5,C4为信息元，C3,C2,C1,C0为监督元，码元取0或1。监督元可按下面方程组计算2021/6/2730一致监督（校验）方程

由确定信息元得到监督元规则的一组方程。由于所有码字都按同一规则确定，又称为一致监督（校验）方程。线性分组码

若一致监督方程是线性的，监督元和信息元之间是线性运算关系，所以由监督方程所确定的分组码是线性分组码。前例2021/6/27313、一致监督（校验）矩阵为了运算方便，可将监督方程写成矩阵形式。前例：2021/6/2732推广：一般情况，对(n,k)线性分组码，每个码字中的r(r=n－k)个监督元与信息元之间的关系可由如下r*n阶线性方程组确定：则：令：2021/6/2733若用hi(i=n-1,n-2,…,1,0)表示H矩阵中的列矢量，则H可写为：H矩阵的每一行元素是线性方程组中一个方程的系数，由它来唯一确定每一个校验元。因此，H中每一行必须是线性无关的，且必定有：r=n－k

行。2021/6/27344、生成矩阵

根据（n,k）线性分组码的一致监督方程出发，将信息组信息位与生成的码字之间的生成关系用矩阵来表示，就可得到生成矩阵。例前例中，2021/6/2735生成矩阵G1其各行为码字，互不相关。其他码字为此三个码字的线性组合方式生成。2021/6/2736推广：对一般(n,k)线性分组码，设有一组k个线性独立的码字，由此一组线性独立的码字以行向量构成的矩阵，称为线性分组码的生成矩阵G（k*n阶）：满足：2021/6/2737G中每一行及其线性组合都是许用码字，故有：

线性分组码的所有码字都可由其生成矩阵或一致校验矩阵求得。当已知G、H中的一个，就可求另一个。系统码：信息元以不变形式出现在码字的任意k位上。标准生成矩阵：生成矩阵能把信息元保留在各码字的最左边k位上。2021/6/2738

因此，标准系统生成矩阵G应满足如下形式：其与H矩阵之间的转换关系：若非标准系统码，则G与H之间元素需要由方程组确定。2021/6/2739(略)生成矩阵之间的关系对于二元（n,k）分组码，在2k个码字中，k个独立码字组不止一个。对于同一码，选择不同的独立码字组构成生成矩阵G也不相同。但经过若干次初等变换，可变成等价的标准生成矩阵。例一个二元（7，3）码,生成矩阵为：生成的码字为：2021/6/2740码字集合完全相同。但生成矩阵G1、G2选取了不同的独立码字构成。生成矩阵可以经过初等行变换得到其标准生成矩阵。比较：生成矩阵G2产生的码（非系统码）比较：生成矩阵G1产生的码（系统码）2021/6/27412行+3行==〉2行1行+2行==〉3行标准生成矩阵2021/6/27425、线性分组码性质与纠错能力1）（n,k）线性分组码由生成矩阵G或校验矩阵H确定。它们满足：2）封闭性。（n,k）码中任意两个码字之和仍为许用码字，即：2021/6/27433）含有零码字。

n位长的零矢量为（n,k）线性分组码的许用码字。（因为满足）4）所有许用码字可由其中k个独立码字（基底）线性组合而成。在个许用码字中，k个独立许用码字不止一组。它们可构成生成矩阵G。5）码的最小距离等于非零码字的最小重量。即：因为：2021/6/2744定理设（n,k）线性分组码C的校验矩阵为H，则码的最小距离为d的充要条件为：H中任意d-1个列向量线性无关，且有d个列向量线性相关。（提供了构造最小距离为d的线性分组码的思路。）任何3列相加均非0，而最少的相关列数为4：如：从右向左第0，1，2，5之和为0，相关。故，码最小距离为：4由此可知：当所有列向量相同，而排列位置不同的H矩阵所对应的分组码，具有相同的最小距离，则它们在纠错能力和码率上等价。对于分组码来说，由于可以进行初等变换进行等价变换，系统码和非系统码的纠错能力是相同的，而系统码的编译码比非系统码简单，且G、H矩阵可方便互求，因此，一般只需讨论系统码。例2021/6/27456、线性分组码的纠错与伴随式：①接收到一个序列R后，校验H

RT=0T

是否成立：若关系成立，则认为R是一个码字；否则判为码字在传输中发生了错误；②伴随式（/监督子/校验子）：

S=R

HT

或

ST=H

RT③如何纠错？设发送码矢C=(cn－1,cn－2,…,c0)信道错误图样为E=(en－1,en－2,…,e0)，其中ei=0，表示第i位无错；ei=1，表示第i位有错。

i=n－1,n－2,…,0。2021/6/2746接收序列R：R=(rn－1,rn－2,…,r0)=C+E=(cn－1+en－1,cn－2+en－2,…,c0+e0)接收序列的伴随式（接收字用监督矩阵进行检验）

ST=H

RT=H

(C+E)T=H

CT+H

ET

由于H

CT=0T，所以

ST=H

ET

或

S=E

HT即：分析：2021/6/2747对于2元码，ei=[0，1]，伴随式是H矩阵中对应若干列向量之和。（1位错，多位错）例：已知(7,3)码的一致校验矩阵。①设发送码矢C=1010011。若传输时没有差错，E0=（0000000），则接收码字R＝1010011=C，R与C相同：

S0=E0

HT=

（0000）没有错误；

若传输时差错图样为E00=C=1010011，则R＝0000000，S00=E00

HT=

（0000），无法发现此错误；2021/6/2748②若发送码矢C1=0100111，C2=1101001，错误图样E1=（1000000），接收码字R1＝1100111，R2＝0101001；伴随式

S1=R1

HT=E1

HT

=

（1110），

S2=R2

HT=E2

HT

=

（1110），可见：S1=S2≠0；不为0，译码器判断有错误；第1位错误，刚好对应于H矩阵的第1列向量；伴随式与发送码字无关，只与错误图样有关。2021/6/2749

当错误图样E3=（0010000），可得：S3=E3

HT=（1101），刚好为H矩阵的第3列向量。依此类推：当发生1位错误时，当i位错误发生在第i位，其伴随式正好是H矩阵中的第i列向量。③若传送时发送2位码元错误，设E=（1010000）=E1+E3

，伴随式S

=E

HT=（E1+E3）

HT=

E1

HT+E3

HT=

（0011），

可见：

S不同于H中的任何一列，说明发生了不止一位错误；可能是第1、第3位错误；但若错误图样E=（0100100）或（0000011），其伴随式仍为（0011），译码器无法判断错误的位置，故无法纠正2位的随机差错。2021/6/2750④若错误图样E=（0110100），可得：S=EHT=（1110）=S1

，刚好为H矩阵的第1列向量。由此：此（7，3）码可发现3位随机错误，但当发生1位错误时，无法纠正；或者相反。H矩阵：任意小于等于3列线性无关，而最少4列就线性相关，故其最小码距dmin=4,故可纠正1位错误的同时检测出2位错误，或检测3位错误。2021/6/2751本章习题

9-1

9-3

9-4

2021/6/27527、标准阵列译码传输中错误图样E不同时，有可能对应相同的伴随式。当信道译码器接收到接收序列R后，由下式求解E：

S

=R

HT=

E

HT

但是，此式中对应的错误图样可以有2k个解。一般采用最大似然准则译码（输入码元等概分布），其译码错误概率最小，正确译码概率最大。在BSC信道中，重量最小的E*，其发生的概率最大，则：P(C+E*|C)=P(E*)>P(C+E|C),E≠E*

因此，用伴随式译码时就采用最大似然准则（最小距离译码准则），选取重量最轻的E作为译码的错误图样。2021/6/2753

实际译码中，根据

R

HT=

S

=E

HT找出重量最轻的E的译码方法及其繁琐。一般采用标准阵列译码方法。标准阵列译码方法：发送码字：取自由2k个码字构成的集合{C}；接收序列：可以是2n个n长序列中任一个矢量；把2n个n长序列划分为2k个互不相交的子集，并按照最大似然译码准则，使得在每个子集对应一个许用码字；根据码字和子集间一一对应关系，若接收矢量R落在子集Dl中，就把Rl译为子集Dl对应的码字Cl。因此当接收序列R与实际发送码字在同一子集中时，译码就是正确的。2021/6/2754标准阵列表的构造：先将2k个许用码字排成一行，作为标准阵列的第一行，并将全0码矢C0=(00…0)放在最左面的位置上；然后在剩下的(2n－2k)

个n长序列中选取一个重量最轻的重E1放在全0码矢C0下面，即第2行首位；再将E1分别和所有许用码字相加：Ci+E1，放在对应码字下构成阵列第二行；在第二次剩下的n长序列中，选取重量最轻的n重E2，放在E1下面，并将E2分别加到第一行各许用码字上Ci+E2

，得到第三行；…，继续这样做下去，直到全部n重用完为止。得到(n,k)线性码的标准阵列。2021/6/2755标准阵列表结构伴随式陪集首（表中每一行称为陪集）2021/6/2756标准阵列表的特点：表中每一行称为陪集，该行的首位元素Ei在为陪集首，各行元素都不同；如果把错误图样作为陪集首，则同一个陪集中所有的元素都队应相同的伴随式；表中各列以同一组许用码字为基础，将2n个接收序列划分成不相交的子集合D0,D1,D2,…,D2k-1.每个子集合Dj对应同一个许用码字Cj，它是每列子集的子集首。2021/6/2757标准阵列的译码：列子集Dj各元素是同一许用码字Cj在信道中发生若干错误得到。同列中各元素对应的是不同的错误图样。而列子集Dj各元素是与许用码字Cj距离最近的，与许用码字的距离等于错误图样Ej在的重量W(Ej).由建表过程中，选取的陪集首都是重量为最轻的错误图样，所以，这样的列子集Dj的划分是满足最大似然准则的（最小距离准则）.2021/6/2758标准阵列的译码方式：方式1：在表中查询接收序列R，并把R所在列的子集首Cj作为R的译码。方式2：先求出伴随式S,找出S所在的行中的R，以R所在列的子集首Cj作为R的译码。表较大时，两种方式的搜索时间差别也较大。2021/6/2759例

设（5，2）系统线性码的生成矩阵为构造该码的标准阵列译码表。信息组为（00）（01）（10）（11），由C=mG

可求出相应码字。同时，可得到校验矩阵（用于计算伴随式）：伴随式个数：(2n－2k)=8，标准阵列表应有8行。按照重量选择错误图样，并计算其对应伴随式，填入表中。2021/6/2760重量为2的错误图样的选择：1、根据前面6行填满后，选择未出现的重量为2的二元序列；2、根据尚未出现的伴随式，计算出对应的错误图样，并选用之。2021/6/2761若接收序列R=（10101）,可采用两种译码方式：1、搜索全部码表，在（5，2）位置，查询到R，则其所在列子集首为码字C1,则将此R译码为C1=10111；2、根据尚未出现的伴随式，计算出对应的错误图样。

RHT=S=010=S4在S4所在行查找R，则其所在列子集首为码字C1,则将此R译码为C1=10111。由阵列译码表知，此（5，2）码能够纠正所有的1位错误，以及两个2位发生图样。2021/6/2762简化译码表：问题：利用标准阵列译码，需要将标准阵列的2n个接收序列R存入存储器，译码器复杂度随着n增大而成指数增大，限制了其适用性。简化译码表：只构造表的第0、第1列：即Si与Ei对照表，译码器只需要存储2n-k个长度为（n-k）的向量Si与2n-k个长度为n的错误图样Ei。大大减少了存储量，简化了译码器。译码方式：先由R计算伴随式S=RHT,然后在简化表中查找出S对应的错误图样E，最后计算：C=R+E，C作为译码输出。2021/6/2763建立译码表的注意点：在构造译码表时，当不等式（r为错误图样重量）成立时，在第1列中顺序存入重量为0，1，2，…，r的错误图样Ei,由EHT=S求出S，放入表的第0列。当第1列剩余位置少于个时，才需要由S解方程EHT=S,求出E，从中挑选重量为（r+1）的错误图样填入第一列剩余位置。2021/6/2764线性码可纠正的错误图样若发送码矢为Cj，信道干扰的错误图样是陪集首，则接收矢量R必在Dj中；若错误图样不是陪集首，则接收矢量R不在Dj中，则译成其它码字，造成错误译码；当且仅当错误图样为陪集首时，译码才是正确的。可纠正的错误图样：这2n－k个陪