差错控制编码第二次课

差错控制编码第二次课第一页，共五十一页，2022年，8月28日回顾奇偶监督码在接收端解码时，实际上就是在计算若S＝0，认为无错若S＝1，认为有错S只有两种取值，只能代表有、无错两种信息，不能指出错码位置。监督关系式校正子第二页，共五十一页，2022年，8月28日在（n,k）码中，为能纠正一位错误要求在（n,k）码中，k=4。为能纠正一位错码，则r至少应为多少？第三页，共五十一页，2022年，8月28日举例说明如何构造监督关系式：上例中，若取r=3，则n=k+r=7。(7,4)线性分组码（a6a5a4a3a2a1a0)校正子与错码位置的对应关系如表规定(也可以另外规定)。第四页，共五十一页，2022年，8月28日S1S2S3错码位置S1S2S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错第五页，共五十一页，2022年，8月28日由表可见，当一错码位置在a2,a4，a5或a6时校正子S1为1；否则S1为0即构成如下关系第六页，共五十一页，2022年，8月28日由此解出给定信息位后，可直接按上式算出监督位监督方程第七页，共五十一页，2022年，8月28日信息位监督位信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111第八页，共五十一页，2022年，8月28日2、监督矩阵H和生成矩阵G

改写为第九页，共五十一页，2022年，8月28日(模2)简记为

或第十页，共五十一页，2022年，8月28日称为监督矩阵H矩阵的各个行是线性无关的行数=监督位数，列数=码字长度典型阵r行n列第十一页，共五十一页，2022年，8月28日第十二页，共五十一页，2022年，8月28日转置得K行r列第十三页，共五十一页，2022年，8月28日Q=PT，在Q矩阵的左边在加上一个k×k的单位矩阵，就形成了一个新矩阵G：

典型形式生成矩阵K行n列称为生成矩阵生成矩阵G的每一行都是一个码组第十四页，共五十一页，2022年，8月28日G为典型生成矩阵，则得到的码为系统码否则得到的码为非系统码第十五页，共五十一页，2022年，8月28日例【1】已知线性（6，3）码的生成矩阵为

求（1）信息码组为101对应的编码码组（2）所有许用码组、各码组的码重、最小码距和该码的差错控制能力。

第十六页，共五十一页，2022年，8月28日第十七页，共五十一页，2022年，8月28日第十八页，共五十一页，2022年，8月28日例2已知（7，4）码的生成矩阵为：列出所有许用码组并求监督矩阵第十九页，共五十一页，2022年，8月28日例3课后习题9-61、写出监督方程2、由监督方程求出所有许用码组3、求生成矩阵4、最小码距？只用于检错，能检出几位错码？只用于纠错？同时用于检错和纠错？第二十页，共五十一页，2022年，8月28日若发送码组为表示该位接收码元无错；表示该位接收码元有错。3、译码接收码组为二者之差为E称为错误图样第二十一页，共五十一页，2022年，8月28日

接收端译码时计算错误图样与校正子之间有确定的关系无错时，S等于零有错，S不等于零。校正子(伴随式)第二十二页，共五十一页，2022年，8月28日纠错-----------只纠一位错误时第二十三页，共五十一页，2022年，8月28日例4

设验证3个接收码组是否发生差错？若在某码组中有错码，错码的校正子是什么？然后再指出发生错码的码字中，哪位有错？且有3个接收码组第二十四页，共五十一页，2022年，8月28日解：1）若无错，则错误图样为0，S为0

B1无错B2错B3错2）∵S2=H第1列∴E=[100000]第1位错同理S3=H第3列∴E=[001000]第3位错第二十五页，共五十一页，2022年，8月28日例5、已知一（7，4），监督码元和信息码元之间的关系为：求（1）信息码字I=[0011]时的编码码组（2）如果接收的码字B=[1000101]，确定收到的码组是否有错，并纠正。第二十六页，共五十一页，2022年，8月28日4、汉明码（1）码长满足（2）最小码距d0=3（3）编码效率第二十七页，共五十一页，2022年，8月28日§9.4线性分组码

我们把建立在代数学基础上的编码称为代数码。在代数码中，常见的是线性码。线性码中信息位和监督位是由一些线性代数方程联系着的，或者说，线性码是按一组线性方程构成的。

本节将以汉明(Hamming)码为例引入线性分组码的一般原理。第二十八页，共五十一页，2022年，8月28日回顾奇偶监督码在接收端解码时，实际上就是在计算若S＝0，认为无错；若S＝1，认为有错。上式称为监督关系式，S称为校正子。S只有两种取值，只能代表有、无错两种信息，不能指出错码位置。如果监督位增加一位，则增加一个监督关系式。两个校正子的可能值有4种组合：00，01，10，11，故能表示4种不同状态。第二十九页，共五十一页，2022年，8月28日

若用其一种表示无错，则其余3种就可能用来指示一位错码的3种不同位置。同理r个监督关系式能指示一位错码的(2r-1)个可能位置。一般地，若码长为n，信息位数为k，则监督位数r=n-k。如果希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置，则要求

2r-1≥n，或者2r≥r+k+1第三十页，共五十一页，2022年，8月28日举例说明如何构造监督关系式：设(n，k)分组码中k=4。为了纠正一位错码，要求监督位数r≥3。若取r=3，则n=k+r=7。校正子与错码位置的对应关系如表9—4规定(也可以另外规定)。S1S2S3错码位置S1S2S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错第三十一页，共五十一页，2022年，8月28日由表可见，当一错码在a2,a4，a5或a6时校正子S1为1；否则S1为0.a2,a4，a5和a6构成偶数监督关系。即构成如下关系:

同理在发送端编码时，信息位a6a5a4a3的值决定于输入信号，因此它们是随机的。监督值a2a1ao应根据信息位的取值按监督关系来确定．即监督位应使上三式中的值为零(表示编成的码组中应无错码)，由此得到方程组第三十二页，共五十一页，2022年，8月28日由此解出给定信息位后，可直接按上式算出监督位，其结果如表9—5所列。第三十三页，共五十一页，2022年，8月28日信息位监督位信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111第三十四页，共五十一页，2022年，8月28日

接收端收到每个码组后，先按监督方程计算出S1、S2、S3，再按表9—4判断错码情况。例：接收0000011，可得：

S1S2S3=011。由表9—4可知在a3位有错码。

(7，4)汉明码：最小码距d0=3纠一个错码或检测两个错码。编码效率k/n=(2r-1-r)／(2r-1)=I-r／n。当n很大时，则编码效率接近1。第三十五页，共五十一页，2022年，8月28日线性分组码的—般原理。线性分组码是指信息位和监督位满足一组线性方程的编码。改写为第三十六页，共五十一页，2022年，8月28日(模2)简记为或第三十七页，共五十一页，2022年，8月28日称为监督矩阵H矩阵的各个行是线性无关的行数=监督位数，列数=码字长度典型阵第三十八页，共五十一页，2022年，8月28日第三十九页，共五十一页，2022年，8月28日转置得其中：矩阵P第四十页，共五十一页，2022年，8月28日称为典型生成矩阵第四十一页，共五十一页，2022年，8月28日生成矩阵G的每一行都是一个码组。例如，（参照前页矩阵G）。利用生成矩阵，码字再由得，H和G互为正交关系第四十二页，共五十一页，2022年，8月28日译码,若发送码组为接收码组为二者之差为其中E称为错误图样。表示该位接收码元无错；表示该位接收码元有错。第四十三页，共五十一页，2022年，8月28日

接收端译码时计算当接收码组无错时．S等于零有错但不超过检错能力时，S不等于零。在错码超过检错能力时，B变为另一许用码组，仍能成立S等于零。这样的错码是不可检测的。S称为校正子(伴随式)。S只与E有关，而与A无关，意味着S与E有的线性变换关系，能与E一一对应，可指示错码位置。第四十四页，共五十一页，2022年，8月28日

线性码重要性质之一，是它具有封闭性。若：A1和A2是线性码中的两个许用码组，则：(A1+A2)仍为其中的一个码组。由封闭性，两个码组之间的距离必是另一码组的重量。故码的最小距离即是码的最小重量(除全“0”码组外)。线性码又称群码，这是由于线性码的各许用码组构成代数学中的群。第四十五页，共五十一页，2022年，8月28日9.3.4线性分组码的译码

码字Ci

接收字R

Ci的估值干扰

1.差错图案

线性分组码C

的任一码字Ci=(ci1,ci

2,…,cin)经信道传输后，接收到字

R

=(r

1,r2,…,rn)；令

E=R-Ci=

(r

1-

ci1,r2-ci2,…,rn-cin);

这里称

E为差错图案。根据模2运算的性质，E=R+Ci

E=0则R是码C的码字；否则，R不是码C

的码字。对于二元(n,k)码，差错图案E的分量中“1”的个数即为接收码字R差错的个数。差错图案出现t个差错的图案数量为Cnt

。信道译码器第四十六页，共五十一页，2022年，8月28日2.伴随式根据Ci

H

T=01×(n-k)及R=Ci+E，

RH

T

=

(Ci+E)H

T=Ci

H

T+E

H

T=E

H

T

令S=RH

T

或S=E

H

T;这里S=(s1,s2,…,sn-k)

这里称S

为伴随式。伴随式S仅与接收字R或差错图案E有关，与码字Ci

无关。由于伴随式S是n-k维矢量，故不同S的个数只有2n-k个；而接收字R或差错图案E有2n个，因此，不同的接收字R或差错图案E

有相同的伴随式S.

第四十七页，共五十一页，2022年，8月28日例(5,2)线性分组码

1°生成矩阵G2°

校验矩阵H3°编码码字:00000011011011111010dmin=34°差错图案E出现0

个差错的1个:00000

出现1

个差错的5个:0000100010001000100010000出现2

个差错的10个:0001100110011001100000101010101010001001

10010

10001第四十八页，共五十一页，2022年，8月28日5°伴随式S=RHT=

EHT

00000→00000001→00100011→011

00010→010

00110→110

00100→10001100→00101000→10111000→010

10000→11100101→101

01010→11110100→01101001→100

10010→101

10001→110ESESES第四十九页，共五十一页，2022年，8月28日3.线性分组码的译码原理生成矩阵G或校验矩阵H确定后，就可以解决编码问题。码字经过信道传输后，接收端获得的只有R，而Ci未知的，因此E也是未知的.如何根据H和R进行译码，

1°如