信息论与编码原理_第8章_线性分组码

1、第1页2021-10-28Department of Electronics and Information, NCUT Song Peng第2页2021-10-28Department of Electronics and Information, NCUT Song Peng8.1 一般概念一般概念8.2 一致监督方程和一致一致监督方程和一致监督矩阵监督矩阵8.3 线性分组码的线性分组码的生成矩阵生成矩阵8.4 线性分组码的编码线性分组码的编码8.5 线性分组码的线性分组码的最小距离最小距离、检错和纠错能力、检错和纠错能力8.6 线性分组码的线性分组码的译码译码8.7 线性分组码的性能线性

2、分组码的性能8.8 汉明码汉明码8.9 由已知码构造新码的方法由已知码构造新码的方法8.10 GSM 的信道编码总体方案的信道编码总体方案8.11 线性分组码的码限线性分组码的码限第3页2021-10-28Department of Electronics and Information, NCUT Song Peng(1) 线性分组码的编码：线性分组码的编码：编码过程分为两步：编码过程分为两步：把信息序列按一定长度分成把信息序列按一定长度分成若干若干信息码组信息码组, 每组由每组由 k 位位组成组成;编码器按照预定的编码器按照预定的线性规则线性规则（可由线性方程组规定），（可由线性方程组规定

3、），把信息码组变换成把信息码组变换成 n 重（重（nk）码字，其中）码字，其中 (nk) 个附个附加码元是由信息码元的加码元是由信息码元的线性运算线性运算产生的。产生的。(2) 线性分组码的码字数：线性分组码的码字数：信息码组长信息码组长 k 位位，有，有 2k 个不同个不同的信息码组，有的信息码组，有 2k 个码字与它们一一对应。个码字与它们一一对应。第4页2021-10-28Department of Electronics and Information, NCUT Song Peng(3) 术语术语线性分组码：线性分组码：通过预定的线性运算将长为通过预定的线性运算将长为 k 位的信息码

4、位的信息码组变换成组变换成 n 重的码字重的码字 (nk)。由。由 2k 个信息码组所编成的个信息码组所编成的 2k个码字集合，称为个码字集合，称为线性分组码线性分组码。码矢：码矢：一个一个 n 重的码字可以用矢量来表示：重的码字可以用矢量来表示：C C=(cn1,cn1,c1,c0 )(n,k) 线性码：线性码：信息位长为信息位长为 k，码长为，码长为 n 的线性码。的线性码。编码效率编码效率/编码速率编码速率/码率码率/传信率：传信率：R=k /n。它说明了信。它说明了信道的利用效率，道的利用效率，R 是衡量码性能的一个重要参数。是衡量码性能的一个重要参数。第5页2021-10-28Dep

5、artment of Electronics and Information, NCUT Song Peng(1) 一致监督方程一致监督方程(2) 举举 例例(3) 一致监督矩阵一致监督矩阵(4) 一致监督矩阵特性一致监督矩阵特性第6页2021-10-28Department of Electronics and Information, NCUT Song Peng(1) 一致监督方程一致监督方程构成码字的方法：构成码字的方法：编码是给已知信息码组按预定规则添加监督码元，编码是给已知信息码组按预定规则添加监督码元，构成码字。构成码字。在在 k 个信息码元之后附加个信息码元之后附加 r(r=n

6、k) 个监督码元，使每个监督元是其个监督码元，使每个监督元是其中某些信息元的模中某些信息元的模 2 和。和。举例：举例：k=3, r=4，构成，构成 (7,3) 线性分组码。设码字为：线性分组码。设码字为：(c6,c5,c4,c3,c2,c1,c0)c6,c5,c4为信息元，为信息元，c3,c2,c1,c0为监督元，每个码元取为监督元，每个码元取“0”或或“1”监督元按下面方程组计算：监督元按下面方程组计算：) 1 . 2 . 7(4505614562463 ccccccccccccc第7页2021-10-28Department of Electronics and Information,

7、 NCUT Song Peng(1) 一致监督方程一致监督方程一致监督方程一致监督方程/一致校验方程：确定信息元得到监督元一致校验方程：确定信息元得到监督元规则的一组方程称为监督方程规则的一组方程称为监督方程/校验方程。由于校验方程。由于所有码所有码字都按同一规则确定，字都按同一规则确定，又称为一致监督方程又称为一致监督方程/一致校验一致校验方程。方程。为什么叫线性分组码？为什么叫线性分组码？由于一致监督方程是由于一致监督方程是线性线性的，即的，即监督元和信息元之间是线性运算关系，所以由线性监督监督元和信息元之间是线性运算关系，所以由线性监督方程所确定的分组码是方程所确定的分组码是线性分组码。

8、线性分组码。第8页2021-10-28Department of Electronics and Information, NCUT Song Peng(2) 举例举例信息码组信息码组 (101)，即，即c6=1, c5=0, c4=1代入代入 (7.2.1) 得：得： c3=0, c2=0, c1=1, c0=1由信息码组由信息码组 (101) 编出的码字为编出的码字为 (1010011)。其它。其它 7 个码字如表个码字如表8.2.1。 00000000000000000000451562456346ccccccccccccc) 1 . 2 . 8(4505614562463 cccccc

9、ccccccc第9页2021-10-28Department of Electronics and Information, NCUT Song Peng(3) 一致监督矩阵一致监督矩阵为了运算方便，将式为了运算方便，将式(7.2.1)监监督方程写成矩阵形式，得：督方程写成矩阵形式，得：)2 . 2 . 8(000010001100100011001011100011010123456 ccccccc )3 . 2 . 8(100011001000110010111000110100000123456 HH0 0C Cccccccc令令将式将式(8.2.2)可写成：可写成： HH C CT=0

10、 0T 或或 C C HHT=0 0 C CT、HHT、0 0T 分别表示分别表示 C C、HH、0 0 的转置矩阵。的转置矩阵。第10页2021-10-28Department of Electronics and Information, NCUT Song Peng )4 . 2 . 8(1000010000100001110011111101434)37(434I IP PHHI IP P ,所所以以(3) 一致监督矩阵一致监督矩阵系数矩阵系数矩阵 H H 的后四列组成一个的后四列组成一个 (44) 阶单位子阵，用阶单位子阵，用 I I4 表示，表示，H H 的其余部分用的其余部分用

11、P P 表示：表示：第11页2021-10-28Department of Electronics and Information, NCUT Song Peng(3) 一致监督矩阵一致监督矩阵推广到一般情况：推广到一般情况：对对 (n,k) 线性分组码，每个码字中的线性分组码，每个码字中的 r(r=nk) 个监督元与信息元之间的关系可由下面的线个监督元与信息元之间的关系可由下面的线性方程组确定：性方程组确定：)5 . 2 . 8(000022110222212101212111 chchchchchchchchchrnnrnrnnnnnn第12页2021-10-28Department of

12、 Electronics and Information, NCUT Song Peng(3) 一致监督矩阵一致监督矩阵令上式的系数矩阵为令上式的系数矩阵为 HH，码字行阵列为，码字行阵列为 C C ： 0211cccnnn C C)6 . 2 . 8(212222111211 rnrrnnnrhhhhhhhhhHH矩矩阵阵，简简称称监监督督矩矩阵阵。线线性性分分组组码码的的一一致致监监督督为为称称或或可可写写成成：式式),()7 . 2 . 8()()()()5 . 2 . 7(1111knrTnrnTrTnnrHH0 0HHC C0 0C CHH 第13页2021-10-28Departm

13、ent of Electronics and Information, NCUT Song Peng(4) 一致监督矩阵特性一致监督矩阵特性对对 H H 各行实行初等变换，将后面各行实行初等变换，将后面 r 列列化为化为单位子阵单位子阵，得到下面矩阵，行变换所得方程组与原方程组同解。得到下面矩阵，行变换所得方程组与原方程组同解。监督矩阵监督矩阵 H H 的标准形式的标准形式：后面后面 r 列列是一是一单位子阵单位子阵的监的监督矩阵督矩阵 HH。)8 . 2 . 8(100010001212222111211 rnrrkknrpppppppppHH第14页2021-10-28Department

14、 of Electronics and Information, NCUT Song Peng(4) 一致监督矩阵特性一致监督矩阵特性 H H 标准形式的特性标准形式的特性q H H 阵的每一行都代表一个监督方程，它表示与该行中阵的每一行都代表一个监督方程，它表示与该行中“1”相对应的码相对应的码元的模元的模 2 和为和为 0。 q H H 的标准形式表明了相应的监督元是由哪些信息元决定的。例如的标准形式表明了相应的监督元是由哪些信息元决定的。例如 (7,3) 码的码的 H H 阵的第一行为阵的第一行为 (1011000)，说明第一个监督元等于第一个和第三，说明第一个监督元等于第一个和第三个信

15、息元的模个信息元的模 2 和，依此类推。和，依此类推。 q H H 阵的阵的 r 行代表了行代表了 r 个监督方程，个监督方程，由由 H H 所确定的码字有所确定的码字有 r 个监督元。个监督元。q 为了得到确定的码，为了得到确定的码，r 个监督方程（或个监督方程（或 H H 阵的阵的 r 行）必须是行）必须是线性独立线性独立的，这要求的，这要求 H H 阵的秩为阵的秩为 r。q 若把若把 H H 阵化成标准形式，只要检查单位子阵的秩，就能方便地确定阵化成标准形式，只要检查单位子阵的秩，就能方便地确定 H H 阵本身的秩。阵本身的秩。第15页2021-10-28Department of El

16、ectronics and Information, NCUT Song Peng (1) 线性码的封闭性线性码的封闭性 (2) 线性分组码的生成矩阵线性分组码的生成矩阵(3) 生成矩阵与一致监督矩阵的关系生成矩阵与一致监督矩阵的关系 (4) 对偶码对偶码第16页2021-10-28Department of Electronics and Information, NCUT Song Peng(1) 线性码的封闭性线性码的封闭性 线性码的封闭性：线性码的封闭性：线性码任意两个码字之和仍是一个码字。线性码任意两个码字之和仍是一个码字。 定理定理7.3.1：设二元线性分组码设二元线性分组码 C

17、CI (C CI 表示码字集合表示码字集合) 是由监督矩阵是由监督矩阵H H 所定义的，若所定义的，若 U U 和和 V V 为其中的任意两个码字，则为其中的任意两个码字，则 U U +V V 也是也是 C CI 中的中的一个码字一个码字. 证明证明：由于由于 U U 和和 V V 是码是码 C CI 中的两个码字，故有：中的两个码字，故有：HU HU T=0 0T HV HV T=0 0T ，那么，那么 HH(UU+V V)T=HH(U U T+V V T)=HU HU T+HV HV T=0 0T 即即 UU+V V 满足监督方程，所以满足监督方程，所以 UU+V V 一定是一个码字。一定

18、是一个码字。 一个长为一个长为 n 的二元序列可以看作是的二元序列可以看作是 GFGF(2) (二元域二元域) 上的上的 n 维线性维线性空间中的一点。所有空间中的一点。所有 2n 个矢量集合构成了个矢量集合构成了GFGF(2)上的上的 n 维线性空间维线性空间 V Vn。把线性码放入线性空间中进行研究，将使许多问题简化而比较。把线性码放入线性空间中进行研究，将使许多问题简化而比较容易解决。容易解决。(n,k) 线性码是线性码是 n 维线性空间维线性空间 V Vn 中的一个中的一个 k 维子空间维子空间 V Vk。第17页2021-10-28Department of Electronics

19、and Information, NCUT Song Peng(2) 线性分组码的生成矩阵线性分组码的生成矩阵生成矩阵的来由生成矩阵的来由：在由在由 (n,k) 线性码构成的线性空间线性码构成的线性空间 V Vn 的的 k 维子维子空间中，一定存在空间中，一定存在 k 个线性独立的码字：个线性独立的码字：g g1,g g2, g gk。码。码 C CI 中其中其它任何码字它任何码字 C C 都可以表为这都可以表为这 k 个码字的一种线性组合，即：个码字的一种线性组合，即：。写写成成矩矩阵阵形形式式得得：）（1, 1 , 0),2(1 . 3 . 802211 kiGFmmmmikkkg gg

20、gg gC C 阶阶矩矩阵阵。是是一一个个待待编编码码的的信信息息组组nkmmmnkkk GGmm021 )2 . 3 . 8(,1210211nkkkkknmmm GGmmg gg gg gC C第18页2021-10-28Department of Electronics and Information, NCUT Song Peng(2) 线性分组码的生成矩阵线性分组码的生成矩阵生成矩阵定义生成矩阵定义：由于矩阵由于矩阵 G G 生成了生成了 (n,k) 线性码，称矩线性码，称矩阵阵 G G 为为 (n,k) 线性码的生成矩阵。线性码的生成矩阵。)3 . 3 . 8(2122221112

21、1121 knkknnknkgggggggggg gg gg gGG第19页2021-10-28Department of Electronics and Information, NCUT Song Peng(2) 线性分组码的生成矩阵线性分组码的生成矩阵 生成矩阵生成矩阵G G 的特性的特性q G G 中每一行中每一行 g gi=(gi1,gi2, gin ) 都是一个码字；都是一个码字；q 对每一个信息组对每一个信息组 mm，由矩阵，由矩阵 G G 都可以求得都可以求得 (n,k) 线线性码对应的码字。性码对应的码字。q (n,k) 线性码的每一个码字都是生成矩阵线性码的每一个码字都是生

22、成矩阵 G G 的行矢量的行矢量的线性组合，所以它的的线性组合，所以它的 2k 个码字构成了由个码字构成了由 G G 的行张成的行张成的的 n 维空间的一个维空间的一个 k 维子空间维子空间 V Vk。第20页2021-10-28Department of Electronics and Information, NCUT Song Peng )4 . 3 . 8(100010001)(21)(22221)(11211rkkknkkkknknnkqqqqqqqqq QQI IGG(2) 线性分组码的生成矩阵线性分组码的生成矩阵 线性线性系统系统分组码分组码q 线性系统分组码的构成线性系统分组码

23、的构成：通过行初等变换，将通过行初等变换，将 G G 化为前化为前 k 列是列是单位子阵的标准形式。单位子阵的标准形式。)5 . 3 . 8(, 2 , 1, 2 , 1),(),(02211)(0210211 knjqmqmqmckimc,mmmccckjjkjkjknikinnkkknnn得：得：将上式代入将上式代入GGC C第21页2021-10-28Department of Electronics and Information, NCUT Song Peng(2) 线性分组码的生成矩阵线性分组码的生成矩阵 线性线性系统系统分组码分组码q 线性系统分组码定义线性系统分组码定义：用标准

24、生成矩阵用标准生成矩阵 GGkn 编成的码字，前面编成的码字，前面 k 位为信息位，后面位为信息位，后面 r=nk 位为校验位，这种信息位在前校验位位为校验位，这种信息位在前校验位在后的线性分组码称为线性系统分组码。在后的线性分组码称为线性系统分组码。q 当生成矩阵当生成矩阵 G G 确定之后，确定之后，(n,k) 线性码也就完全被确定了，只要线性码也就完全被确定了，只要找到码的生成矩阵，编码问题也同样被解决了。找到码的生成矩阵，编码问题也同样被解决了。第22页2021-10-28Department of Electronics and Information, NCUT Song Peng

25、 )1010011(11010000110100111001010100010101)1010(11010000110100111001010100017441714174 GGmmC CmmGG，则则：若若(2) 线性分组码的生成矩阵线性分组码的生成矩阵举例举例：(7,4) 线性码的生成矩阵为：线性码的生成矩阵为：第23页2021-10-28Department of Electronics and Information, NCUT Song Peng(3) 生成矩阵与一致监督矩阵的关系生成矩阵与一致监督矩阵的关系由于生成矩阵由于生成矩阵 G G 的每一行都是一个码字，所以的每一行都是一个

26、码字，所以 G G 的每行都满足：的每行都满足：HHrn(C C1n)T=(0 01r)T，则有：，则有：HHrn(GGkn)T=(0 0kr)T 或或 GGkn(HHrn)T=0 0kr。rkrSrkkSIPHQIGrkrkTkrrTkrrkkTrkrrkkTSS0QPIPQIIPQIHG)()(krTrkTkrrk P PQQP PQQ)()(或或所所以以， )6 . 3 . 7()( rTrkSrkkSI IQQHHQQI IGG第24页2021-10-28Department of Electronics and Information, NCUT Song Peng(3) 生成矩阵与

27、一致监督矩阵的关系生成矩阵与一致监督矩阵的关系由于生成矩阵由于生成矩阵 G G 的每一行都是一个码字，所以的每一行都是一个码字，所以 G G 的每行都满足：的每行都满足：HHrn(C C1n)T=(0 01r)T，则有：，则有：HHrn(GGkn)T=(0 0kr)T 或或 GGkn(HHrn)T=0 0kr。rkrSrkkSIPHQIGrkrkTkrrTkrrkkTrkrrkkTSS0QPIPQIIPQIHG)()(krTrkTkrrk P PQQP PQQ)()(或或所所以以， )6 . 3 . 7()( rTrkSrkkSI IQQHHQQI IGG第25页2021-10-28Depar

28、tment of Electronics and Information, NCUT Song Peng 1101000011010011100101010001100101101011100010111)4,7()4,7(GGHH阵阵：可可直直接接写写出出它它的的生生成成矩矩(3) 生成矩阵与一致监督矩阵的关系生成矩阵与一致监督矩阵的关系举例举例： 已知已知 (7,4) 线性系统码的监督矩阵为：线性系统码的监督矩阵为：QQT第26页2021-10-28Department of Electronics and Information, NCUT Song Peng(4) 对偶码对偶码 对偶码

29、对偶码：对一个对一个 (n,k) 线性码线性码C CI，由于，由于 HHrn(GGkn)T=(0 0kr)T，如果以如果以G G 作监督矩阵，而以作监督矩阵，而以 H H 作生成矩阵，可构造另一个码作生成矩阵，可构造另一个码 C CId，C CId是一个是一个 (n,nk) 线性码，称码线性码，称码 C CId 为原码的对偶码为原码的对偶码. 例如例如： (7,4) 线性码的对偶码是线性码的对偶码是 (7,3) 码：码：q (7,3) 码的生成矩阵码的生成矩阵 GG(7,3) 是是 (7,4) 码监督矩阵码监督矩阵 HH(7,4) 1011100111001001110011001011010

30、11100010111)4,7()3,7(化化成成标标准准形形式式HHGG第27页2021-10-28Department of Electronics and Information, NCUT Song Peng 4505614562463)3, 7(1000110010001100101110001101cccccccccccccTT得得：由由0 0HHC CHH (n,k) 线性码的编码线性码的编码：根据线性码的监督矩阵或生成矩根据线性码的监督矩阵或生成矩阵阵将长为将长为 k 的信息组变换成长为的信息组变换成长为 n(nk) 的码字。的码字。 利用监督矩阵构造利用监督矩阵构造 (7,3

31、) 线性分组码的编码电路线性分组码的编码电路q 设码字为：设码字为：C C=(c6c5c4c3c2c1c0)q 码的监督矩阵为：码的监督矩阵为：第28页2021-10-28Department of Electronics and Information, NCUT Song Peng 利用监督矩阵构造利用监督矩阵构造 (7,3) 线性分组码的编码电路：线性分组码的编码电路：q 根据上面方程组可直接画出根据上面方程组可直接画出 (7,3) 码的并行编码电路和串行编码码的并行编码电路和串行编码电路电路:第29页2021-10-28Department of Electronics and Inf

32、ormation, NCUT Song Peng第30页2021-10-28Department of Electronics and Information, NCUT Song Peng(1) 汉明距离、汉明重量和汉明球汉明距离、汉明重量和汉明球 汉明距离汉明距离（距离）：在（距离）：在 (n,k) 线性码中，两个码字线性码中，两个码字 UU、V V 之间对应之间对应码元位上符号取值不同的个数，称为码字码元位上符号取值不同的个数，称为码字 UU、V V 之间的汉明距离。之间的汉明距离。q 线性分组码的一个码字对应于线性分组码的一个码字对应于 n 维线性空间中的一点，码字间维线性空间中的一点

33、，码字间的距离即为空间中两的距离即为空间中两对应点的距离。因此，码字间的距离满足一对应点的距离。因此，码字间的距离满足一般距离公理：般距离公理： 10)(),(niiivudV VUU 三三角角不不等等式式对对称称性性非非负负性性),(),(),(),(),(0),(WWUUWWV VV VUUUUV VV VUUV VUUdddddd第31页2021-10-28Department of Electronics and Information, NCUT Song Peng(1) 汉明距离、汉明重量和汉明球汉明距离、汉明重量和汉明球 最小距离最小距离 dmin：在在 (n,k) 线性码的码字

34、线性码的码字集合中集合中，任意两，任意两个码字间距离最小值，叫做码的最小距离。若个码字间距离最小值，叫做码的最小距离。若 C C(i) 和和 C C(j) 是任意两个码字，则码的最小距离表示为：是任意两个码字，则码的最小距离表示为：q 码的最小距离是衡量码的抗干扰能力（检、纠错能力）码的最小距离是衡量码的抗干扰能力（检、纠错能力）的重要参数。的重要参数。 12 , 1 , 0,),(min)()(min kjijijiddC CC C第32页2021-10-28Department of Electronics and Information, NCUT Song Peng(1) 汉明距离、汉

35、明重量和汉明球汉明距离、汉明重量和汉明球汉明球汉明球：以码字以码字 C C 为中心，半径为为中心，半径为 t 的汉明球是与的汉明球是与 C C 的汉明距离的汉明距离t 的向量全体的向量全体 S SC C(t) ：。 tdt ),()(R RC CR RS SC C第33页2021-10-28Department of Electronics and Information, NCUT Song Peng(1) 汉明距离、汉明重量和汉明球汉明距离、汉明重量和汉明球汉明球汉明球：第34页2021-10-28Department of Electronics and Information, NCU

36、T Song Peng(1) 汉明距离、汉明重量和汉明球汉明距离、汉明重量和汉明球汉明重量汉明重量（码字重量）（码字重量）W：码字中非码字中非 0 码元符号的个数，码元符号的个数，称为该码字的汉明重量。称为该码字的汉明重量。q在二元线性码中，码字重量就是码字中含在二元线性码中，码字重量就是码字中含“1”的个的个数。数。最小重量最小重量 Wmin ：线性分组码线性分组码 C CI 中，非中，非 0 0 码字重量最小码字重量最小值，叫做码值，叫做码 C CI 的最小重量：的最小重量：Wmin =minW(V V),V VC CI ,V V0 0第35页2021-10-28Department of

37、 Electronics and Information, NCUT Song Peng(1) 汉明距离、汉明重量和汉明球汉明距离、汉明重量和汉明球 最小距离最小距离 与最小重量与最小重量 的关系的关系：线性分组码的最小距离等于它线性分组码的最小距离等于它的最小重量。的最小重量。证明证明： 设线性码设线性码 C CI，且，且 UUC CI, V VC CI 又设又设 UUV V=Z Z 由线性码的封闭性知，由线性码的封闭性知，Z ZC CI 因此，因此，d(UU,V V)=W(Z Z) 由此可推知，线性分组码的最小距离必等于非由此可推知，线性分组码的最小距离必等于非 0 0 码字的最小重量。码

38、字的最小重量。第36页2021-10-28Department of Electronics and Information, NCUT Song Peng(2) 最小距离与检、纠错能力最小距离与检、纠错能力检错能力检错能力：如果一个线性码能检出长度如果一个线性码能检出长度l 个码元的任何个码元的任何错误图样，称码的错误图样，称码的检错能力为检错能力为 l。纠错能力纠错能力：如果线性码能纠正长度如果线性码能纠正长度t 个码元的任意错误个码元的任意错误图样，称码的图样，称码的纠错能力为纠错能力为 t。最小距离与检纠错能力的关系最小距离与检纠错能力的关系：线性码的最小距离越大，线性码的最小距离越大

39、，意味着任意码字间的差别越大，则码的检、纠错能力越意味着任意码字间的差别越大，则码的检、纠错能力越强。强。第37页2021-10-28Department of Electronics and Information, NCUT Song Peng(2) 最小距离与检、纠错能力最小距离与检、纠错能力最小距离与纠错能力最小距离与纠错能力：(n,k) 线性码能纠线性码能纠 t 个错误的充要条件是码个错误的充要条件是码的最小距离为：的最小距离为：dmin2t+1 (8.5.1)证明证明：设发送的码字为设发送的码字为 V V；接收的码字为；接收的码字为 R R；U U 为任意其它码字为任意其它码字则矢

40、量则矢量V V、R R、U U 间满足距离的三角不等式：间满足距离的三角不等式： d(R R,V V)+d(R R,UU)d(UU,V V) (8.5.2)设信道干扰使码字中码元发生错误的实际个数为设信道干扰使码字中码元发生错误的实际个数为 t ，且，且 t t d(R R,V V)t t (8.5.3)第38页2021-10-28Department of Electronics and Information, NCUT Song Peng(2) 最小距离与检、纠错能力最小距离与检、纠错能力最小距离与纠错能力：最小距离与纠错能力：(n,k) 线性码能纠线性码能纠 t 个错误的充要条件是码的

41、个错误的充要条件是码的最小距离为：最小距离为：dmin2t+1 (8.5.1)证明证明：由于由于 d(UU,V V)dmin=2t+1，代入式，代入式 (7.5.2) 得：得： d(R R,UU) d(UU,V V)d(R R,V V)= 2t+1t t (8.5.4) 含义含义：如果接收字如果接收字 R R 中错误个数中错误个数 t t，接收字，接收字 R R 和发送字和发送字 V V 间距间距离离t ，而与其它任何码字间距离都大于，而与其它任何码字间距离都大于 t，按最小距离译码把，按最小距离译码把 R R 译译为为 V V。此时译码正确，码字中的错误被纠正。此时译码正确，码字中的错误被纠

42、正。几何意义几何意义：第39页2021-10-28Department of Electronics and Information, NCUT Song Peng(2) 最小距离与检、纠错能力最小距离与检、纠错能力最小距离与检错能力最小距离与检错能力：(n,k) 线性码能够发现线性码能够发现 l 个错误的充要条件个错误的充要条件是码的最小距离为：是码的最小距离为：dminl+1 (8.5.5)证明证明：设发送的码字为设发送的码字为 V V；接收的码字为；接收的码字为 R R；U U 为任意其它码字为任意其它码字则矢量则矢量V V、R R、U U 间满足距离的三角不等式：间满足距离的三角不等式

43、： d(R R,V V)+d(R R,UU)d(UU,V V) (8.5.2)设信道干扰使码字中码元发生错误的实际个数为设信道干扰使码字中码元发生错误的实际个数为 l ，且，且 l l d(R R,V V)l l (8.5.6)第40页2021-10-28Department of Electronics and Information, NCUT Song Peng(2) 最小距离与检、纠错能力最小距离与检、纠错能力最小距离与检错能力最小距离与检错能力：(n,k) 线性码能够发现线性码能够发现 l 个错误的充要条件个错误的充要条件是码的最小距离为：是码的最小距离为：dminl+1 (8.5.

44、5)证明证明：由于由于 d(UU,V V)dmin=l+1，代入式，代入式(7.5.2)得：得：d(R R,UU) d(UU,V V)d(R R,V V)=l+1l 0 (8.5.7) 含义含义：由于接收字由于接收字 R R 与其它任何码字与其它任何码字 UU 的距离都大于的距离都大于0，说明接，说明接收字收字 R R 不会因发生不会因发生 l 个错误变为其它码字，因而必能发现错误。个错误变为其它码字，因而必能发现错误。第41页2021-10-28Department of Electronics and Information, NCUT Song Peng(2) 最小距离与检、纠错能力最小

45、距离与检、纠错能力最小距离与检错能力最小距离与检错能力： 几何意义几何意义：第42页2021-10-28Department of Electronics and Information, NCUT Song Peng(2) 最小距离与检、纠错能力最小距离与检、纠错能力最小距离与检、纠错能力最小距离与检、纠错能力：(n,k) 线性码能纠线性码能纠 t 个错误，并能发现个错误，并能发现 l 个错误个错误 (lt) 的充要条件是码的最小距离为：的充要条件是码的最小距离为：Dmin t+l+1 (8.5.8)证明证明：因为因为dmin2t+1，根据，根据最小距离与纠错能力最小距离与纠错能力定理，该码

46、可纠定理，该码可纠 t 个错误。个错误。因为因为dminl+1，根据，根据最小距离与检错能力最小距离与检错能力定理定理, 该码有检该码有检 l 个错误的个错误的能力。能力。纠错和检错不会发生混淆纠错和检错不会发生混淆：设发送码字为设发送码字为 V V，接收字为，接收字为 R R，实际错，实际错误数为误数为 l ，且，且 t t (8.5.9) 不会把不会把 R R 误纠为误纠为 UU。第43页2021-10-28Department of Electronics and Information, NCUT Song Peng(2) 最小距离与检、纠错能力最小距离与检、纠错能力最小距离与检、纠错

47、能力：最小距离与检、纠错能力： 几何意义：几何意义：第44页2021-10-28Department of Electronics and Information, NCUT Song Peng(2) 最小距离与检、纠错能力最小距离与检、纠错能力当当 (n,k) 线性码的最小距离线性码的最小距离dmin给定后，可按实际需给定后，可按实际需要灵活安排纠错的数目。要灵活安排纠错的数目。例如例如：对对 dmin=8 的码，可的码，可用来纠用来纠 3 检检 4 错，或纠错，或纠 2检检 5 错，或纠错，或纠 1 检检 6错，错，或者只用于检或者只用于检 7 个错误。个错误。第45页2021-10-28

48、Department of Electronics and Information, NCUT Song Peng(3) 线性码的最小距离与监督矩阵的关系线性码的最小距离与监督矩阵的关系定理定理8.5.1：设设 H H 为为 (n,k) 线性码的一致监督矩阵，若线性码的一致监督矩阵，若 H H 中任意中任意 S 列线性无关，而列线性无关，而 H H 中存在中存在 (S+1) 列线性相关，列线性相关，则码的最小距离为则码的最小距离为 (S+1)。定理定理8.5.2：若码的最小距离为若码的最小距离为 (S+1)，则该码的监督矩，则该码的监督矩阵的任意阵的任意 S 列线性无关，而必存在有相关的列线性

49、无关，而必存在有相关的 (S+1)列。列。定理定理8.5.3：在二元线性码的监督矩阵在二元线性码的监督矩阵 H H 中，如果任一中，如果任一列都不是全列都不是全“0”，且任两列都不相等，则该码能纠一个，且任两列都不相等，则该码能纠一个错误。（错误。（S=2，dmin=3）第46页2021-10-28Department of Electronics and Information, NCUT Song Peng8.6.1 伴随式和错误检测伴随式和错误检测8.6.2 纠错译码纠错译码第47页2021-10-28Department of Electronics and Information,

50、NCUT Song Peng(1) 如何译码？如何译码？(2) 伴随式伴随式(3) 伴随式的计算伴随式的计算(4) 伴随式的特性伴随式的特性(5) 举例举例(6) 伴随式计算电路伴随式计算电路8.6线性分组码的译码第48页2021-10-28Department of Electronics and Information, NCUT Song Peng(1) 如何译码？如何译码？ 用监督矩阵编码，也用监督矩阵编码，也用监督矩阵译码：用监督矩阵译码：接收到一个字接收到一个字 R R 后，校验后，校验 HH R R T=0 0T 是否成立：是否成立：若关系成立，则认为若关系成立，则认为 R R

51、是一个码字；是一个码字；否则判为码字在传输中发生了错误；否则判为码字在传输中发生了错误；HH R R T 的值是否为的值是否为 0 0 是校验码字出错与否的依据。是校验码字出错与否的依据。(2) 伴随式伴随式/监督子监督子/校验子：校验子：S S=R R H H T 或或 S S T=HH R R T8.6线性分组码的译码第49页2021-10-28Department of Electronics and Information, NCUT Song Peng(3) 伴随式的计算伴随式的计算 发送码字：发送码字：C C=(cn1,cn2,c0) 信道错误图样：信道错误图样：E E=(en1,

52、en2,e0) q ei=0，表示第，表示第 i 位无错；位无错；q ei=1，表示第，表示第 i 位有错。位有错。i=n1,n2,0 接收字：接收字：R R=(rn1,rn2,r0)=C C+E E=(cn1+en1,cn2+en2,c0 +e0) 求接收字的伴随式（接收字用监督矩阵进行检验）求接收字的伴随式（接收字用监督矩阵进行检验） S S T=HH R R T=HH (C C+E E )T=HH C C T+HH E E T (8.6.1) H H C C T=0 0T，所以，所以 S S T=HH E E T 设设 HH=(h h1,h h2,h hn)，（，（h hi 表示表示 H

53、 H 的列）。代入式的列）。代入式(8.6.1)得：得：S S T=h h1 en1+ h h2 en2+ + h hn e08.6线性分组码的译码第50页2021-10-28Department of Electronics and Information, NCUT Song Peng(4) 伴随式的特性伴随式的特性 伴随式仅与错误图样有关，而与发送的具体码字无关，伴随式仅与错误图样有关，而与发送的具体码字无关，即即伴随式仅由错误图样决定；伴随式仅由错误图样决定； 伴随式是错误的判别式：伴随式是错误的判别式：q 若若 S S=0 0，则判为没有出错，接收字是一个码字；，则判为没有出错，接收

54、字是一个码字；q 若若 S S0 0，则判为有错。，则判为有错。 不同的错误图样具有不同的伴随式，它们是一一对应的。不同的错误图样具有不同的伴随式，它们是一一对应的。对二元码，伴随式是对二元码，伴随式是 H H 阵中与错误码元对应列之和。阵中与错误码元对应列之和。8.6线性分组码的译码第51页2021-10-28Department of Electronics and Information, NCUT Song Peng(5) 举举 例：例：(7,3) 码接收字码接收字 R R 的伴随式计算的伴随式计算 若接收字中没有错误：若接收字中没有错误：q 设发送码字设发送码字 C C=101001

55、1，接收码字，接收码字 R R1010011，R R 与与 C C 相同：相同：q 但接收端译码器并不知道就是发送的码字但接收端译码器并不知道就是发送的码字q 根据接收字根据接收字R R 计算伴随式：计算伴随式：S S T= HR HR T =0 0Tq 因此，译码器判接收字无错因此，译码器判接收字无错 1000110010001100101110001101H8.6线性分组码的译码第52页2021-10-28Department of Electronics and Information, NCUT Song Peng(5) 举举 例：例：(7,3) 码接收矢量码接收矢量 R R 的伴随式

56、计算的伴随式计算 若接收字中有若接收字中有 1 位错误：位错误：q 发送码字发送码字C C=1010011，接收码字，接收码字R R=1110011，伴随式为：，伴随式为：q (7,3) 码是纠单个错误的码，且码是纠单个错误的码，且S S T 等于等于HH 的第二列，因此判定接的第二列，因此判定接收字收字R R 的第二位是错的。的第二位是错的。q 由于接收字由于接收字R R 中错误码元数与码的纠错能力相符，所以译码正确。中错误码元数与码的纠错能力相符，所以译码正确。 111011001111000110010001100101110001101TTR RHHS S译译码码器器判判为为有有错错由

57、由于于0 0S S T8.6线性分组码的译码第53页2021-10-28Department of Electronics and Information, NCUT Song Peng(5) 举举 例：例：(7,3) 码接收矢量码接收矢量 R R 的伴随式计算的伴随式计算 当码元错误多于当码元错误多于 1 个时：个时：q 发送码字发送码字C C=1010011，接收码字，接收码字R R=0011011，伴随式为：，伴随式为：q 由于由于S S T 是第一列和第四列之和，不等于是第一列和第四列之和，不等于0 0；q 但但S S T 与与 HH 阵中任何一列都不相同无法判定错误出在哪些位上，阵中

58、任何一列都不相同无法判定错误出在哪些位上，只是发现有错。只是发现有错。 011011011001000110010001100101110001101TTR RHHS S8.6线性分组码的译码第54页2021-10-28Department of Electronics and Information, NCUT Song Peng(6) 伴随式计算电路伴随式计算电路伴随式的计算可用电路来实现。伴随式的计算可用电路来实现。(7,3) 码为例：接收字码为例：接收字 R R =(r6r5r4r3r2r1r0)，伴随式：，伴随式： 0123045156345634601234561000110010

59、001100101110001101ssssrrrrrrrrrrrrrrrrrrrrTTR RHHS S8.6线性分组码的译码第55页2021-10-28Department of Electronics and Information, NCUT Song Peng(6) 伴随式计算电路伴随式计算电路伴随式计算电路：伴随式计算电路：8.6线性分组码的译码第56页2021-10-28Department of Electronics and Information, NCUT Song Peng(1) 最佳译码准则（最大似然译码）最佳译码准则（最大似然译码）(2) 查表译码法查表译码法(3)

60、标准阵列标准阵列(4) 举例举例(5) 结论结论8.6线性分组码的译码第57页2021-10-28Department of Electronics and Information, NCUT Song Peng(1) 最佳译码准则（最大似然译码）最佳译码准则（最大似然译码） 通信是一个统计过程，纠、检错能力最终要反映到差错通信是一个统计过程，纠、检错能力最终要反映到差错概率上。概率上。 对于对于 FEC 方式，采用纠错码后的码字差错概率为方式，采用纠错码后的码字差错概率为 pwe：q p(C C)：发送码字发送码字C C 的的先验概率先验概率q p(C C/R R)：后验概率后验概率)()(