信息论与编码理论-信道编码-线性分组码1

1、第六章 信道编码2021/12/311第六章 信道编码2021/12/3126.2.1 一般概念一般概念6.2.2 一致监督方程和一致监督矩阵一致监督方程和一致监督矩阵6.2.3 线性分组码的生成矩阵线性分组码的生成矩阵6.2.4 线性分组码的编码线性分组码的编码6.2.5 线性分组码的最小距离、检错和纠错能力线性分组码的最小距离、检错和纠错能力6.2.6 线性分组码的译码线性分组码的译码6.2.7 线性分组码的性能线性分组码的性能6.2.8 汉明码汉明码6.2.9 由已知码构造新码的方法由已知码构造新码的方法6.2.10 线性分组码的码限线性分组码的码限6.2 线性分组码线性分组码第六章 信

2、道编码2021/12/313l线性分组码的编码线性分组码的编码：线性分组码的编码过程分为两步：线性分组码的编码过程分为两步：l把信息序列按一定长度分成若干信息码组，每组由把信息序列按一定长度分成若干信息码组，每组由 k 位组成；位组成；l编码器按照预定的编码器按照预定的线性规则线性规则(可由线性方程组规定可由线性方程组规定)，把信息码，把信息码组变换成组变换成 n 重重 (nk) 码字，其中码字，其中 (nk) 个附加码元是由信息码个附加码元是由信息码元的元的线性运算线性运算产生的。产生的。l信息码组长信息码组长 k 位，有位，有 2k 个不同的信息码组，则有个不同的信息码组，则有 2k 个个

3、码字与它们一一对应。码字与它们一一对应。6.2.1 一般概念一般概念第六章 信道编码2021/12/314l名词解释名词解释l线性分组码线性分组码：通过预定的线性运算将长为：通过预定的线性运算将长为 k 位的信息码组变换位的信息码组变换成成 n 重的码字重的码字 (nk)。由。由 2k 个信息码组所编成的个信息码组所编成的 2k个码字集合，个码字集合，称为称为线性分组码线性分组码。l码矢码矢：一个：一个 n 重的码字可以用矢量来表示重的码字可以用矢量来表示C C=(Cn1,Cn2,C1,C0 ) 所以码字又称为码矢。所以码字又称为码矢。l(n,k) 线性码线性码：信息位长为：信息位长为 k，码

4、长为，码长为 n 的线性码。的线性码。l编码效率编码效率/编码速率编码速率/码率码率/传信率：传信率：R=k /n。它说明了信道的利。它说明了信道的利用效率，用效率，R是衡量码性能的一个重要参数是衡量码性能的一个重要参数。6.2.1 一般概念一般概念第六章 信道编码2021/12/315(1) 一致监督方程一致监督方程l编码就是给已知信息码组按预定规则添加监督码元，以构成码字。编码就是给已知信息码组按预定规则添加监督码元，以构成码字。l在在 k 个信息码元之后附加个信息码元之后附加 r(r=nk) 个监督码元，使每个监督元是个监督码元，使每个监督元是其中某些信息元的模其中某些信息元的模2和。和

5、。l举例：举例：k=3, r=4，构成，构成 (7,3) 线性分组码线性分组码。设码字为。设码字为l(C6,C5,C4,C3,C2,C1,C0)lC6,C5,C4为信息元，为信息元，C3,C2,C1,C0为监督元，每个码元取为监督元，每个码元取“0”或或“1”l监督元可按下面方程组计算监督元可按下面方程组计算6.2.2 一致监督方程和一致监督矩阵一致监督方程和一致监督矩阵) 1 . 2 . 6(4505614562463CCCCCCCCCCCCC第六章 信道编码2021/12/316l一致监督方程一致监督方程/一致校验方程：一致校验方程：确定由信息元得到监督元规确定由信息元得到监督元规则的一组

6、方程称为监督方程则的一组方程称为监督方程/校验方程。由于校验方程。由于所有码字都按同一规所有码字都按同一规则确定则确定，又称为一致监督方程，又称为一致监督方程/一致校验方程。一致校验方程。l由于一致监督方程是由于一致监督方程是线性线性的，即监督元和新信源之间是的，即监督元和新信源之间是线性运算关系，所以由线性监督方程所确定的分组码是线性运算关系，所以由线性监督方程所确定的分组码是线性分组码线性分组码。6.2.2 一致监督方程和一致监督矩阵一致监督方程和一致监督矩阵第六章 信道编码2021/12/317(2) 举例举例l信息码组信息码组 (101)，即，即C6=1, C5=0, C4=1l代入代

7、入 (6.2.1) 得：得： C3=0, C2=0, C1=1, C0=1l由信息码组由信息码组 (101) 编出的码字为编出的码字为 (1010011)。其它其它7个码字如表个码字如表6.2.1。6.2.2 一致监督方程和一致监督矩阵一致监督方程和一致监督矩阵) 1 . 2 . 6(4505614562463CCCCCCCCCCCCC00000000000000000000451562456346CCCCCCCCCCCCC第六章 信道编码2021/12/318(3) 一致监督矩阵一致监督矩阵l为了运算方便，将式为了运算方便，将式(6.2.1)监督方程写成监督方程写成矩阵形式，得矩阵形式，得l

8、式式(6.2.2)可写成可写成 H H C CT=0 0T或或 C C HHT=0 0 C CT、HHT、0 0T分别表分别表示示C C、HH、0 0的转置的转置矩阵。矩阵。)3 . 2 . 6(10001100100011001011100011010000)2 . 2 . 6(0000100011001000110010111000110101234560123456H0CCCCCCCCCCCCCCC令6.2.2 一致监督方程和一致监督矩阵一致监督方程和一致监督矩阵第六章 信道编码2021/12/319l系数矩阵系数矩阵 H H 的后四列组成一个的后四列组成一个 (44) 阶单位子阵，用阶

9、单位子阵，用 I I4 表示，表示，H H 的其余部分用的其余部分用 P P 表示表示)5 . 2 . 6(100001000010000111001111110143437434IPHIP),(所以6.2.2 一致监督方程和一致监督矩阵一致监督方程和一致监督矩阵第六章 信道编码2021/12/3110l推广到一般情况：对推广到一般情况：对 (n,k) 线性分组码，每个码字中的线性分组码，每个码字中的 r(r=nk) 个监督元与信息元之间的关系可由下面的线性个监督元与信息元之间的关系可由下面的线性方程组确定方程组确定6.2.2 一致监督方程和一致监督矩阵一致监督方程和一致监督矩阵)6 . 2

10、. 6(000022110222212101212111ChChChChChChChChChrnnrnrnnnnnn第六章 信道编码2021/12/3111l令上式的系数矩阵为令上式的系数矩阵为 HH，码字行阵列为，码字行阵列为 C C6.2.2 一致监督方程和一致监督矩阵一致监督方程和一致监督矩阵矩阵，简称监督矩阵。线性分组码的一致监督为称或可写成式),()8 . 2 . 6()6 . 2 . 6()7 . 2 . 6(11110211212222111211knCCChhhhhhhhhrTrnnTrTnnrnnnrnrrnnnrH0HC0CHCH第六章 信道编码2021/12/3112(4

11、) 一致监督矩阵特性一致监督矩阵特性l对对H H 各行实行初等变换，将后面各行实行初等变换，将后面 r 列化为单位子阵，于是得到下列化为单位子阵，于是得到下面矩阵，行变换所得方程组与原方程组同解。面矩阵，行变换所得方程组与原方程组同解。l监督矩阵监督矩阵H H 的标准形式的标准形式：后面：后面 r 列是一单位子阵的监督矩阵列是一单位子阵的监督矩阵HH。lH H 阵的每一行都代表一个监督方程，它表示与该行中阵的每一行都代表一个监督方程，它表示与该行中“1”相对应的相对应的码元的模码元的模2和为和为0。6.2.2 一致监督方程和一致监督矩阵一致监督方程和一致监督矩阵)9 . 2 . 6(10001

12、0001212222111211rnrrkknrpppppppppH第六章 信道编码2021/12/3113lH H 的标准形式还说明了相应的监督元是由哪些信息元的标准形式还说明了相应的监督元是由哪些信息元决定的。例如决定的。例如 (7,3) 码的码的H H 阵的第一行为阵的第一行为 (1011000)，说明此码的第一个监督元等于第一个和第三个信息元说明此码的第一个监督元等于第一个和第三个信息元的模的模2和，依此类推。和，依此类推。 lH H 阵的阵的 r 行代表了行代表了 r 个监督方程，也表示个监督方程，也表示由由H H 所确定所确定的码字有的码字有 r 个监督元个监督元。l为了得到确定的

13、码，为了得到确定的码，r 个监督方程（或个监督方程（或H H 阵的阵的r 行）必行）必须是须是线性独立线性独立的，这要求的，这要求H H 阵的秩为阵的秩为 r。l若把若把H H 阵化成标准形式，只要检查单位子阵的秩，就阵化成标准形式，只要检查单位子阵的秩，就能方便地确定能方便地确定H H 阵本身的秩。阵本身的秩。6.2.2 一致监督方程和一致监督矩阵一致监督方程和一致监督矩阵第六章 信道编码2021/12/3114(1) 线性码的封闭性线性码的封闭性l线性码的封闭性线性码的封闭性：线性码任意两个码字之和仍是一个码字。：线性码任意两个码字之和仍是一个码字。l定理定理6.2.1：设二元线性分组码：

14、设二元线性分组码 C CI (C CI表示码字集合表示码字集合) 是由监督矩阵是由监督矩阵HH所定义的，若所定义的，若 U U 和和 V V 为其中的任意两个码字，则为其中的任意两个码字，则 UU+V V 也是也是 C CI中的一个码字。中的一个码字。l证明证明：由于由于 U U 和和 V V 是码是码 C CI 中的两个码字，故有中的两个码字，故有HUHUT=0 0T，HVHVT=0 0T 那么那么 HH(UU+V V)T=HH(UUT+V VT)=HUHUT+HVHVT=0 0T 即即 UU+V V 满足监督方程，所以满足监督方程，所以 UU+V V 一定是一个码字。一定是一个码字。l一个

15、长为一个长为 n 的二元序列可以看作是的二元序列可以看作是GFGF(2)(二元域二元域)上的上的 n 维线维线性空间中的一点。长为性空间中的一点。长为 n 的所有的所有 2n 个矢量集合构成了个矢量集合构成了GFGF(2)上的上的 n 维线性空间维线性空间V Vn。把线性码放入线性空间中进行研究，。把线性码放入线性空间中进行研究，将使许多问题简化而比较容易解决。将使许多问题简化而比较容易解决。l(n,k) 线性码是线性码是 n 维线性空间维线性空间V Vn中的一个中的一个 k 维子空间维子空间 V Vk。6.2.3 线性分组码的生成矩阵线性分组码的生成矩阵第六章 信道编码2021/12/311

16、5(2) 线性分组码的生成矩阵线性分组码的生成矩阵l在由在由 (n,k) 线性码构成的线性空间线性码构成的线性空间 V Vn 的的 k 维子空间中，维子空间中，一定存在一定存在 k 个线性独立的码字：个线性独立的码字：g g1,g g2, g gk。码。码 C CI 中中其它任何码字其它任何码字C C都可以表示为这都可以表示为这 k 个码字的一种线性组个码字的一种线性组合，即合，即6.2.3 线性分组码的生成矩阵线性分组码的生成矩阵阶矩阵。是一个是待编码的信息组。写成矩阵形式得）（nkmmmmmmkimmmmkknkkkkknikkkGmGmgggCGFgggC021121021102211)

17、11. 2 . 6(1, 1 , 0),2(10. 2 . 6第六章 信道编码2021/12/3116lGG中每一行中每一行 g gi=(gi1,gi2, gin ) 都是一个码字；都是一个码字；l对每一个信息组对每一个信息组mm，由矩阵，由矩阵GG都可以求得都可以求得 (n,k) 线性码对应的码字。线性码对应的码字。l生成矩阵生成矩阵：由于矩阵：由于矩阵 G G 生成了生成了 (n,k) 线性码，称矩阵线性码，称矩阵 G G 为为 (n,k) 线性码的生成矩阵。线性码的生成矩阵。l(n,k) 线性码的每一个码字都是生成矩阵线性码的每一个码字都是生成矩阵 G G 的行矢量的线性组合，的行矢量的

18、线性组合，所以它的所以它的 2k 个码字构成了由个码字构成了由 G G 的行张成的的行张成的 n 维空间的一个维空间的一个 k 维维子空间子空间 V Vk。6.2.3 线性分组码的生成矩阵线性分组码的生成矩阵11112122122212ggG(6.2.11)gnnk nkkkknggggggggg第六章 信道编码2021/12/3117l线性系统分组码线性系统分组码 通过行初等变换，将通过行初等变换，将 G G 化为前化为前 k 列是单位子阵的列是单位子阵的标准标准形式形式 6.2.3 线性分组码的生成矩阵线性分组码的生成矩阵)13. 2 . 6(, 2 , 1, 2 , 1),(),()12

19、. 2 . 6(10001000102211)(0210211)(21)(22221)(11211knjqmqmqmCkimC,mmmCCCqqqqqqqqqkjjkjkjknikinnkkknnnrkkknkkkknknnk得将上式代入GCQIG第六章 信道编码2021/12/3118l线性系统分组码线性系统分组码：用标准生成矩阵：用标准生成矩阵 GGkn 编成的码字，前面编成的码字，前面 k 位为信息数字，后面位为信息数字，后面 r=nk 位为校验字，这种信息数字在前位为校验字，这种信息数字在前校验数字在后的线性分组码称为线性系统分组码。校验数字在后的线性分组码称为线性系统分组码。l当生成

20、矩阵当生成矩阵 G G 确定之后，确定之后，(n,k) 线性码也就完全被确定了，只线性码也就完全被确定了，只要找到码的生成矩阵，编码问题也同样被解决了。要找到码的生成矩阵，编码问题也同样被解决了。6.2.3 线性分组码的生成矩阵线性分组码的生成矩阵第六章 信道编码2021/12/3119(3) 举例举例 (7,4) 线性码的生成矩阵为线性码的生成矩阵为6.2.3 线性分组码的生成矩阵线性分组码的生成矩阵)1010011(11010000110100111001010100010101)1010(11010000110100111001010100017441714174GmCmG，则若第六章

21、信道编码2021/12/3120(4) 生成矩阵与一致监督矩阵的关系生成矩阵与一致监督矩阵的关系l由于生成矩阵由于生成矩阵GG的每一行都是一个码字，所以的每一行都是一个码字，所以G G 的每行都满足的每行都满足HHrnC CTn1=0 0Tr1，则有，则有HHrnGGTnk=0 0Trk 或或 GGknHHTnr=0 0krl线性系统码的监督矩阵线性系统码的监督矩阵 H H 和生成矩阵和生成矩阵 G G 之间可以直接互换之间可以直接互换。6.2.3 线性分组码的生成矩阵线性分组码的生成矩阵)14. 2 . 6()()()()()(rTrkSrkkSkrTrkTkrrkrkrkTkrrTkrrk

22、kTrkrrkkTSSrkrSrkkSIQHQIGPQPQ0QPIPQIIPQIHGIPHQIG或所以，第六章 信道编码2021/12/3121l举例举例 已知已知(7,4)线性系统码的监督矩阵为线性系统码的监督矩阵为6.2.3 线性分组码的生成矩阵线性分组码的生成矩阵1101000011010011100101010001100101101011100010111)4,7()4,7(GH阵可直接写出它的生成矩第六章 信道编码2021/12/3122(5) 对偶码对偶码l对偶码对偶码：对一个对一个(n,k)线性码线性码 C CI，由于，由于HHrnGGTnk=0 0Trk，如果以，如果以G G

23、 作监督矩阵，而以作监督矩阵，而以H H 作生成矩阵，可构造另一个码作生成矩阵，可构造另一个码C CId，码，码C CId是一个是一个(n,nk)线性码，称码线性码，称码C CId为原码的对偶码。为原码的对偶码。l例如例如： (7,4)线性码的对偶码是线性码的对偶码是(7,3)码：码：l(7,3)码的监督矩阵码的监督矩阵HH(7,3)是是(7,4)码生成矩阵码生成矩阵GG(7,4) 6.2.3 线性分组码的生成矩阵线性分组码的生成矩阵10001100100011001011100011011101000011010011100101010001)4,7()3 ,7(化成标准形式GH第六章 信道

24、编码2021/12/3123l(7,3) 码的生成矩阵码的生成矩阵 GG(7,3) 是是 (7,4) 码监督矩阵码监督矩阵 HH(7,4) 6.2.3 线性分组码的生成矩阵线性分组码的生成矩阵101110011100100111001100101101011100010111)4,7()3 ,7(化成标准形式HG第六章 信道编码2021/12/3124l(n,k) 线性码的编码就是根据线性码的线性码的编码就是根据线性码的监督矩阵监督矩阵或或生成生成矩阵矩阵将长为将长为 k 的信息组变换成长为的信息组变换成长为 n(nk) 的码字的码字。l利用监督矩阵构造利用监督矩阵构造 (7,3) 线性分组码

25、的编码电路：线性分组码的编码电路：l设码字矢量为设码字矢量为C C=(C6 C5C4C3C2C1C0)l码的监督矩阵为码的监督矩阵为6.2.4 线性分组码的编码线性分组码的编码4505614562463)3 ,7(1000110010001100101110001101CCCCCCCCCCCCCTT得由0HCH第六章 信道编码2021/12/3125l根据方程组可直接画出根据方程组可直接画出 (7,3) 码的并行编码电路和串行编码电码的并行编码电路和串行编码电路，如图路，如图6.2.2。6.2.4 线性分组码的编码线性分组码的编码第六章 信道编码2021/12/3126(1) 汉明距离、汉明重

26、量和汉明球汉明距离、汉明重量和汉明球l汉明距离汉明距离/距离：在距离：在 (n,k)线性码中，两个码字线性码中，两个码字 UU、V V 之间对应之间对应码元位上符号取值不同的个数，称为码字码元位上符号取值不同的个数，称为码字 UU、V V 之间的汉明距离。之间的汉明距离。l例如例如：(7,3) 码的两个码字码的两个码字 UU=0011101,V V=0100111，它们之间，它们之间第第2、3、4和和6位不同。因此，码字位不同。因此，码字 U U 和和 V V 的距离为的距离为4。l线性分组码的一个码字对应于线性分组码的一个码字对应于 n 维线性空间中的一点，码字维线性空间中的一点，码字间的距

27、离即为空间中两间的距离即为空间中两对应点的距离。因此，码字间的距离对应点的距离。因此，码字间的距离满足一般距离公理：满足一般距离公理：10)(),(niiivudVU6.2.5 线性分组码的最小距离、检错和纠错能力线性分组码的最小距离、检错和纠错能力三角不等式对称性非负性),(),(),(),(),(0),(WUWVVUUVVUVUdddddd第六章 信道编码2021/12/3127l.l最小距离最小距离/dmin：在：在 (n,k) 线性码的码字线性码的码字集合中集合中，任意两个码字，任意两个码字间距离最小值，叫做码的最小距离。若间距离最小值，叫做码的最小距离。若C C(i)和和C C(j)

28、 是任意两个是任意两个码字，则码的最小距离表示为码字，则码的最小距离表示为l码的最小距离是衡量码的抗干扰能力（检、纠错能力）的重码的最小距离是衡量码的抗干扰能力（检、纠错能力）的重要参数。码的最小距离越大，码的抗干扰能力就越强。要参数。码的最小距离越大，码的抗干扰能力就越强。l汉明球汉明球：以码字：以码字C C为中心，半径为为中心，半径为 t 的汉明球是与的汉明球是与 C C 的汉明距的汉明距离离 t 的向量全体的向量全体 S SC C(t) 任意两个汉明球不相交最大程度取决于任意两个码字之间的最小任意两个汉明球不相交最大程度取决于任意两个码字之间的最小汉明距离汉明距离dmin。12 , 1

29、, 0,),(min)()(minkjijijiddCC6.2.5 线性分组码的最小距离、检错和纠错能力线性分组码的最小距离、检错和纠错能力tdt),()(RCRSC第六章 信道编码2021/12/3128 6.2.5 线性分组码的最小距离、检错和纠错能力线性分组码的最小距离、检错和纠错能力第六章 信道编码2021/12/3129l汉明重量汉明重量/码字重量码字重量/W：码字中非：码字中非0码元符号的个数，称为该码码元符号的个数，称为该码字的汉明重量。字的汉明重量。l在二元线性码中，码字重量就是码字中含在二元线性码中，码字重量就是码字中含“1”的个数。的个数。l最小重量最小重量/Wmin ：线

30、性分组码：线性分组码C CI中，非中，非0 0码字重量最小值，叫码字重量最小值，叫做码做码C CI的最小重量：的最小重量：Wmin =minW(V V),V VC CI ,V V0 0l最小距离与最小重量的关系最小距离与最小重量的关系：线性分组码的最小距离等于线性分组码的最小距离等于它的最小重量。它的最小重量。 证明证明：设线性码设线性码C CI，且，且UUC CI, V VC CI，又设，又设UUV V= Z Z ，由，由线性码的封闭性知，线性码的封闭性知，Z ZC CI 。因此，。因此，d(UU,V V)=W(Z Z)，由此可推知，由此可推知，线性分组码的最小距离必等于非线性分组码的最小距

31、离必等于非0 0码字的最小重量。码字的最小重量。6.2.5 线性分组码的最小距离、检错和纠错能力线性分组码的最小距离、检错和纠错能力第六章 信道编码2021/12/3130(2) 最小距离与检、纠错能力最小距离与检、纠错能力l一般地说，线性码的最小距离越大，意味着任意码字一般地说，线性码的最小距离越大，意味着任意码字间的差别越大，则码的检、纠错能力越强。间的差别越大，则码的检、纠错能力越强。l检错能力检错能力：如果一个线性码能检出长度：如果一个线性码能检出长度l 个码元的个码元的任任何错误图样何错误图样，称码的，称码的检错能力为检错能力为 l。l纠错能力纠错能力：如果线性码能纠正长度：如果线性

32、码能纠正长度t 个码元的个码元的任意错任意错误图样误图样，称码的，称码的纠错能力为纠错能力为 t。6.2.5 线性分组码的最小距离、检错和纠错能力线性分组码的最小距离、检错和纠错能力第六章 信道编码2021/12/3131l最小距离与纠错能力最小距离与纠错能力：(n,k) 线性码能纠线性码能纠 t 个错误的充要条件个错误的充要条件是码的最小距离为是码的最小距离为 简述简述： 设：发送的码字为设：发送的码字为V V；接收的码字为；接收的码字为R R；UU为任意其它码字；为任意其它码字； 则：矢量则：矢量V V、R R、UU间满足距离的三角不等式，间满足距离的三角不等式， d(R R,V V)+d

33、(R R,UU)d(UU,V V) (6.2.16) 设：信道干扰使码字中码元发生错误的实际个数为设：信道干扰使码字中码元发生错误的实际个数为 t，且，且t t d(R R,V V)t t (6.2.17) 由于由于d(UU,V V)dmin=2t+1，代入式，代入式(6.2.16)得得 d(R R,UU) d(UU,V V)d(R R,V V)= 2t+1tt (6.2.18)6.2.5 线性分组码的最小距离、检错和纠错能力线性分组码的最小距离、检错和纠错能力47 . 4)15. 2 . 6(2112minmin的最大整数，例表示取实数其中或XXdttd第六章 信道编码2021/12/313

34、2 上式表明上式表明：如果接收字：如果接收字 R R 中错误个数中错误个数 tt，那么接收字，那么接收字 R R 和发和发送字送字 V V 间距离间距离t ，而与其它任何码字间距离都大于，而与其它任何码字间距离都大于 t，按最小距，按最小距离译码把离译码把R R译为译为V V。此时译码正确，码字中的错误被纠正。此时译码正确，码字中的错误被纠正。 几何意义几何意义：6.2.5 线性分组码的最小距离、检错和纠错能力线性分组码的最小距离、检错和纠错能力第六章 信道编码2021/12/3133l最小距离与检错能力最小距离与检错能力：(n,k) 线性码能够发现线性码能够发现 l 个错误的充要个错误的充要

35、条件是码的最小距离为条件是码的最小距离为 dmin=l+1 或或 l=dmin1 (6.2.19) 简述简述： 设：发送的码字为设：发送的码字为 V V；接收的码字为；接收的码字为 R R；U U 为任意其它码字；为任意其它码字； 则：矢量则：矢量V V、R R、UU间满足距离的三角不等式，间满足距离的三角不等式， d(R R,V V)+d(R R,UU)d(UU,V V) (6.2.20) 设：信道干扰使码字中码元发生错误的实际个数为设：信道干扰使码字中码元发生错误的实际个数为 l，且，且l l d(R R,V V)l l (6.2.21) 由于由于d(UU,V V)dmin=l+1，代入式

36、，代入式(6.2.20)得得 d(R R,UU) d(UU,V V)d(R R,V V)=l+1l0 (6.2.22)6.2.5 线性分组码的最小距离、检错和纠错能力线性分组码的最小距离、检错和纠错能力第六章 信道编码2021/12/3134 上式表明上式表明：由于接收字：由于接收字 R R 与其它任何码字与其它任何码字 U U 的距离都大于的距离都大于0，则说明接收字则说明接收字 R R 不会因发生不会因发生 l 个错误变为其它码字，因而必能发个错误变为其它码字，因而必能发现错误。现错误。 几何意义几何意义：6.2.5 线性分组码的最小距离、检错和纠错能力线性分组码的最小距离、检错和纠错能力

37、第六章 信道编码2021/12/3135l最小距离与检、纠错能力最小距离与检、纠错能力：(n,k) 线性码能纠线性码能纠 t 个错误，并个错误，并能发现能发现 l 个错误个错误 (lt) 的充要条件是码的最小距离为的充要条件是码的最小距离为 dmin=t+l+1 或或 t+l=dmin1 (6.2.23) 简述简述：因为：因为dmin2t+1，根据，根据最小距离与纠错能力最小距离与纠错能力定理，该码可定理，该码可纠纠 t 个错误。个错误。 因为因为dminl+1，根据，根据最小距离与检错能力最小距离与检错能力定理，该码有检定理，该码有检 l 个个错误的能力。错误的能力。 纠错和检错不会发生混淆

38、：设发送码字为纠错和检错不会发生混淆：设发送码字为 V V，接收字为，接收字为 R R，实际错误数为实际错误数为 l，且，且 tt+1t (6.2.24) 因而不会把因而不会把 R R 误纠为误纠为 UU。6.2.5 线性分组码的最小距离、检错和纠错能力线性分组码的最小距离、检错和纠错能力第六章 信道编码2021/12/3136 几何意义几何意义：6.2.5 线性分组码的最小距离、检错和纠错能力线性分组码的最小距离、检错和纠错能力第六章 信道编码2021/12/31376.2.5 线性分组码的最小距离、检错和纠错能力线性分组码的最小距离、检错和纠错能力第六章 信道编码2021/12/3138l

39、当当 (n,k) 线性码的最小距离线性码的最小距离 dmin 给定后，可按实际需要给定后，可按实际需要灵活安排纠错的数目。例如，对灵活安排纠错的数目。例如，对 dmin=8 的码，可用来的码，可用来纠纠3检检4错，或纠错，或纠2检检5错，或纠错，或纠1检检6错，或者只用于检错，或者只用于检7个错误。个错误。6.2.5 线性分组码的最小距离、检错和纠错能力线性分组码的最小距离、检错和纠错能力第六章 信道编码2021/12/3139(3) 线性码的最小距离与监督矩阵的关系线性码的最小距离与监督矩阵的关系l定理定理6.2.2：设：设 H H 为为 (n,k) 线性码的一致监督矩阵，若线性码的一致监督

40、矩阵，若 H H 中任意中任意 S 列线性无关，而列线性无关，而 H H 中存在中存在 (S+1) 列线性相列线性相关，则码的最小距离为关，则码的最小距离为 (S+1)。（矩阵矩阵 H H 的秩为的秩为S）l定理定理6.2.3：若码的最小距离为：若码的最小距离为 (S+1)，则该码的监督矩，则该码的监督矩阵的任意阵的任意 S 列线性无关，而必存在有相关的列线性无关，而必存在有相关的 (S+1)列。列。l定理定理6.2.4：在二元线性码的监督矩阵：在二元线性码的监督矩阵 H H 中，如果任一中，如果任一列都不是全列都不是全“0”，且任两列都不相等，则该码能纠一个，且任两列都不相等，则该码能纠一个

41、错误。错误。6.2.5 线性分组码的最小距离、检错和纠错能力线性分组码的最小距离、检错和纠错能力第六章 信道编码2021/12/3140(1) 伴随式和错误检测伴随式和错误检测 用监督矩阵编码，也用监督矩阵编码，也用监督矩阵译码用监督矩阵译码：接收到一个接收：接收到一个接收字字 R R 后，校验后，校验 HH R RT=0 0T 是否成立：是否成立：l若关系成立，则认为若关系成立，则认为 R R 是一个码字；是一个码字；l否则判为码字在传输中发生了错误；否则判为码字在传输中发生了错误；lHH R RT的值是否为的值是否为0 0是校验码字出错与否的依据。是校验码字出错与否的依据。 伴随式伴随式/

42、监督子监督子/校验子校验子：S S=R R HHT或或S ST=HH R RT。 如何纠错？如何纠错？l设发送码矢设发送码矢 C C=(Cn1,Cn2,C0)l信道错误图样为信道错误图样为 E E=(En1,En2,E0) ，l其中其中Ei=0，表示第，表示第i位无错；位无错；lEi=1，表示第，表示第i位有错。位有错。i=n1,n2,0。6.2.6 线性分组码的译码线性分组码的译码第六章 信道编码2021/12/3141l接收字接收字 R R 为为R R=(Rn1,Rn2,R0)=C C+E E =(Cn1+En1,Cn2+En2,C0 +E0)l求接收字的伴随式（接收字用监督矩阵进行检验）

43、求接收字的伴随式（接收字用监督矩阵进行检验） S ST=HH R RT=HH (C C+E E)T=HH C CT+HH E ET (6.2.25)l由于由于HH C CT=0 0T，所以，所以 S ST=HH E ETl设设HH=(h h1,h h2,h hn)，其中，其中h hi表示表示HH的列。代入式的列。代入式(6.2.25)得到得到6.2.6 线性分组码的译码线性分组码的译码02211EEEnnnThhhS第六章 信道编码2021/12/3142 总结总结l伴随式仅与错误图样有关，而与发送的具体码字无关，即伴伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定；随式仅由错误图样决定；l伴随式是错误的判别式：伴随式是错误的判别式：l若若S S=0 0，则判为没有出错，接收字是一个码字；，则判为没有出错，接收字是一个码字；l若若S S0 0，则判为有错。，则判为有错。l不同的错误图样具有不同的伴随式，它们是一一对应的。不同的错误图样具有不同的伴随式，它们是一一对应的。对对