第7章_信道编码技术(改1)

1、第1页2022-1-26Department of Electronics and Information, NCUT Song Peng Song Peng7.1 线性分组码线性分组码7.2 卷积码卷积码7.3 TCM码与级联码码与级联码7.4 Turbo码和码和LDPC码码第2页2022-1-26(1) 线性分组码的编码：线性分组码的编码：编码过程分为两步：编码过程分为两步：把信息序列按一定长度分成若干信息码组把信息序列按一定长度分成若干信息码组, 每组由每组由 k 位组位组成成;编码器按照预定的线性规则（由线性方程组规定），把编码器按照预定的线性规则（由线性方程组规定），把信息码组变换成

2、信息码组变换成 n 重（重（nk）码字，其中）码字，其中 (nk) 个附加个附加码元是由信息码元的线性运算产生的。码元是由信息码元的线性运算产生的。(2) 线性分组码的码字数：线性分组码的码字数：信息码组长信息码组长 k 位，有位，有 2k 个不同的个不同的信息码组，有信息码组，有 2k 个码字与它们一一对应。个码字与它们一一对应。第3页2022-1-26(3) 术语术语线性分组码：线性分组码：通过预定的线性运算将长为通过预定的线性运算将长为 k 位的信息码位的信息码组变换成组变换成 n 重的码字重的码字 (nk)。由。由 2k 个信息码组所编成的个信息码组所编成的 2k个码字集合，称为线性分

3、组码。个码字集合，称为线性分组码。码矢：码矢：一个一个 n 重的码字可以用矢量来表示：重的码字可以用矢量来表示：C C=(cn1,cn1,c1,c0 )(n,k) 线性码：线性码：信息位长为信息位长为 k，码字长为，码字长为 n 的线性码。的线性码。编码效率编码效率/编码速率编码速率/码率码率/传信率：传信率：R=k /n。 它说明了信道的利用效率，它说明了信道的利用效率，R 是衡量码性能的一个重是衡量码性能的一个重要参数。要参数。第4页2022-1-26(1) 校验方程校验方程构成码字的方法：构成码字的方法：编码是给已知信息码组按预定规则添加监督码元，构成编码是给已知信息码组按预定规则添加监

4、督码元，构成码字。码字。在在 k 个信息码元之后附加个信息码元之后附加 r(r=nk) 个校验（监督）码元，使每个校验元个校验（监督）码元，使每个校验元是其中某些信息元的模是其中某些信息元的模 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 ccccccccccccc1. 线性

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

6、组码是线性分组码。1. 线性分组码的校验矩阵线性分组码的校验矩阵7.1线性分组码第6页2022-1-26(2) 举例举例信息码组信息码组 (101)，即，即c6=1, c5=0, c4=1得：得： c3=0, c2=0, c1=1, c0=1由信息码组由信息码组 (101) 编出的码字为编出的码字为 (1010011)。其它。其它 7 个码字如表。个码字如表。 00000000000000000000451562456346ccccccccccccc) 1 . 2 . 8 (4505614562463 ccccccccccccc1. 线性分组码的校验矩阵线性分组码的校验矩阵7.1线性分组码第7

7、页2022-1-26(3) 一致监督矩阵一致监督矩阵为了运算方便，将监督方程为了运算方便，将监督方程写成矩阵形式，得：写成矩阵形式，得：) 2 . 2 . 8 (000010001100100011001011100011010123456 cccccccHH C CT=0 0T 或或 C C HHT=0 0 C CT、HHT、0 0T 分别表示分别表示 C C、HH、0 0 的转置矩阵。的转置矩阵。1. 线性分组码的校验矩阵线性分组码的校验矩阵 00000000000000000000451562456346ccccccccccccc ) 3 . 2 . 8 (100011001000110

8、010111000110100000123456 HH0 0C Cccccccc令令7.1线性分组码第8页2022-1-26(3) 一致监督矩阵一致监督矩阵系数矩阵系数矩阵 H H 的后四列组成一个的后四列组成一个 (44) 阶单位子阵，用阶单位子阵，用 I I4 表示，表示，H H 的其余部分用的其余部分用 P P 表示：表示：推广到一般情况：推广到一般情况：对对 (n,k) 线性分组码，每个码字中的线性分组码，每个码字中的 r(r=nk) 个个监督元与信息元之间的关系由下面的线性方程组确定：监督元与信息元之间的关系由下面的线性方程组确定：1. 线性分组码的校验矩阵线性分组码的校验矩阵 )4

9、.2.8(1000010000100001110011111101434)37(434I IP PHHI IP P ,所所以以 )4.2.8(1000010000100001110011111101434)37(434I IP PHHI IP P ,所所以以) 5 . 2 . 8(000022110222212101212111 chchchchchchchchchrnnrnrnnnnnn7.1线性分组码 )3 . 2 . 8(100011001000110010111000110100000123456 HH0 0C Cccccccc令令第9页2022-1-26(3) 一致监督矩阵一致监督矩

10、阵令上式的系数矩阵为令上式的系数矩阵为 HH，码字行阵列为，码字行阵列为 C C ： 0211cccnnn C C) 6 . 2 . 8 (212222111211 rnrrnnnrhhhhhhhhhHH矩矩阵阵，简简称称监监督督矩矩阵阵。线线性性分分组组码码的的一一致致监监督督为为称称或或可可写写成成：式式),()7.2.8()()()()5.2.7(1111knrTnrnTrTnnrHH0 0HHC C0 0C CHH 矩矩阵阵，简简称称监监督督矩矩阵阵。线线性性分分组组码码的的一一致致监监督督为为称称或或可可写写成成：式式),()7.2.8()()()()5.2.7(1111knrTnr

11、nTrTnnrHH0 0HHC C0 0C CHH 1. 线性分组码的校验矩阵线性分组码的校验矩阵7.1线性分组码) 5 . 2 . 8 (000022110222212101212111 chchchchchchchchchrnnrnrnnnnnn第10页2022-1-26(4) 一致监督矩阵特性一致监督矩阵特性对对 H H 各行实行初等变换，将后面各行实行初等变换，将后面 r 列化为单位子阵，得列化为单位子阵，得到下面矩阵，行变换所得方程组与原方程组同解。到下面矩阵，行变换所得方程组与原方程组同解。监督矩阵监督矩阵 H H 的标准形式：的标准形式：后面后面 r 列是一单位子阵的监督列是一单

12、位子阵的监督矩阵矩阵 HH。)8 . 2 . 8(100010001212222111211 rnrrkknrpppppppppHH1. 线性分组码的校验矩阵线性分组码的校验矩阵7.1线性分组码第11页2022-1-26(4) 一致监督矩阵特性一致监督矩阵特性q H H 阵的每一行都代表一个监督方程，它表示与该行中阵的每一行都代表一个监督方程，它表示与该行中“1”相对应相对应的码元的模的码元的模 2 和为和为 0。 q H H 的标准形式表明相应的监督元是由哪些信息元决定。例如的标准形式表明相应的监督元是由哪些信息元决定。例如 (7,3) 码的码的 H H 阵的第一行为阵的第一行为 (1011

13、000)，说明第一个监督元等于第一个和，说明第一个监督元等于第一个和第三个信息元的模第三个信息元的模 2 和，依此类推。和，依此类推。 q H H 阵的阵的 r 行代表了行代表了 r 个监督方程，由个监督方程，由 H H 所确定的码字有所确定的码字有 r 个监个监督元。督元。q 为了得到确定的码，为了得到确定的码，r 个监督方程（或个监督方程（或 H H 阵的阵的 r 行）必须是线性行）必须是线性独立的，即要求独立的，即要求 H H 阵的秩为阵的秩为 r。q 若把若把 H H 阵化成标准形式，只要检查单位子阵的秩，就能方便地阵化成标准形式，只要检查单位子阵的秩，就能方便地确定确定 H H 阵本

14、身的秩。阵本身的秩。1. 线性分组码的校验矩阵线性分组码的校验矩阵7.1线性分组码 )3 . 2 . 8(100011001000110010111000110100000123456 HH0 0C Cccccccc令令第12页2022-1-26(1) 线性码的封闭性线性码的封闭性 线性码的封闭性：线性码的封闭性：线性码任意两个码字之和仍是一个码字。线性码任意两个码字之和仍是一个码字。 定理：定理：设二元线性分组码设二元线性分组码 C CI (C CI 表示码字集合表示码字集合) 是由监督矩阵是由监督矩阵H H 定义，若定义，若 U U 和和 V V 为其中的任意两个码字，则为其中的任意两个码

15、字，则 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 一定是一个码字。一定是一个码字。 一个长为一个长为 n 的二元序列可以看作是的二元序列可以看作是 GFGF(2) (二元域二元域) 上的上的 n 维线性空间中的一维线性空间中的一点。所有点

16、。所有 2n 个矢量集合构成了个矢量集合构成了GFGF(2)上的上的 n 维线性空间维线性空间 V Vn。把线性码放入线性。把线性码放入线性空间中进行研究，可使许多问题简化而比较容易解决。空间中进行研究，可使许多问题简化而比较容易解决。(n,k) 线性码是线性码是 n 维线性空间维线性空间 V Vn 中的一个中的一个 k 维子空间维子空间 V Vk。7.1线性分组码第13页2022-1-26(2) 线性分组码的生成矩阵线性分组码的生成矩阵生成矩阵的来由：生成矩阵的来由：在由在由 (n,k) 线性码构成的线性空间线性码构成的线性空间 V Vn 的的 k 维子空维子空间中，一定存在间中，一定存在

17、k 个线性独立的码字：个线性独立的码字：g g1,g g2, g gk。码。码 C CI 中其它中其它任何码字任何码字 C C 都可以表示为这都可以表示为这 k 个码字的一种线性组合，即：个码字的一种线性组合，即：。写写成成矩矩阵阵形形式式得得：）（1, 1 , 0),2(1 . 3 . 802211 kiGFmmmmikkkg gg gg gC C 阶阶矩矩阵阵。是是一一个个待待编编码码的的信信息息组组nkmmmnkkk GGmm021 ) 2 . 3 . 8 (,1210211nkkkkknmmm GGmmg gg gg gC C7.1线性分组码第14页2022-1-26(2) 线性分组码

18、的生成矩阵线性分组码的生成矩阵生成矩阵定义：生成矩阵定义：由于矩阵由于矩阵 G G 生成了生成了 (n,k) 线性码，称矩阵线性码，称矩阵 G G 为为 (n,k) 线性码的生成矩阵。线性码的生成矩阵。) 3 . 3 . 8 (21222211121121 knkknnknkgggggggggg gg gg gGG 生成矩阵生成矩阵G G 的特性的特性q G G 中每一行中每一行 g gi=(gi1,gi2, gin ) 都是一个码字；都是一个码字；q 对每一个信息组对每一个信息组 mm，由矩阵，由矩阵 G G 都可以求得都可以求得 (n,k) 线性码对应的码线性码对应的码字。字。q (n,k

19、) 线性码的每一个码字都是生成矩阵线性码的每一个码字都是生成矩阵 G G 的行矢量的线性组合，的行矢量的线性组合，所以它的所以它的 2k 个码字构成了由个码字构成了由 G G 的行张成的的行张成的 n 维空间的一个维空间的一个 k 维子维子空间空间 V Vk。7.1线性分组码111212122212nnkkknggggggggg第15页2022-1-26 ) 4 . 3 . 8 (100010001)(21)( 22221)( 11211rkkknkkkknknnkqqqqqqqqq QQI IGG(2) 线性分组码的生成矩阵线性分组码的生成矩阵 线性系统分组码线性系统分组码q 线性系统分组码

20、的构成：线性系统分组码的构成：通过行初等变换，将通过行初等变换，将 G G 化为前化为前 k 列是列是单位子阵的标准形式。单位子阵的标准形式。)5 . 3 . 8(, 2 , 1, 2 , 1),(),(02211)(0210211 knjqmqmqmckimc,mmmccckjjkjkjknikinnkkknnn得得：将将上上式式代代入入GGC C7.1线性分组码第16页2022-1-26(2) 线性分组码的生成矩阵线性分组码的生成矩阵 线性系统分组码线性系统分组码q 线性系统分组码定义：线性系统分组码定义：用标准生成矩阵用标准生成矩阵 GGkn 编成的编成的码字，前面码字，前面 k 位为信

21、息位，后面位为信息位，后面 r=nk 位为校验位，这位为校验位，这种信息位在前校验位在后的线性分组码称为线性系统分种信息位在前校验位在后的线性分组码称为线性系统分组码。组码。q 当生成矩阵当生成矩阵 G G 确定之后，确定之后，(n,k) 线性码就完全被确定，线性码就完全被确定，只要找到码的生成矩阵，编码问题也同样被解决。只要找到码的生成矩阵，编码问题也同样被解决。7.1线性分组码第17页2022-1-26 )1010011(11010000110100111001010100010101)1010(11010000110100111001010100017441714174 GGmmC Cm

22、mGG，则则：若若(2) 线性分组码的生成矩阵线性分组码的生成矩阵举例：举例：(7,4) 线性码的生成矩阵为：线性码的生成矩阵为： )1010011(11010000110100111001010100010101)1010(11010000110100111001010100017441714174 GGmmC CmmGG，则则：若若 )1010011(11010000110100111001010100010101)1010(11010000110100111001010100017441714174 GGmmC CmmGG，则则：若若7.1线性分组码第18页2022-1-26(3) 生成

23、矩阵与一致监督矩阵的关系生成矩阵与一致监督矩阵的关系由于生成矩阵由于生成矩阵 G G 的每一行都是一个码字，所以的每一行都是一个码字，所以 G G 的每行都满足：的每行都满足：HHrn(C C1n)T=(0 01r)T，则有：，则有：HHrn(GGkn)T=(0 0kr)T 或或 GGkn(HHrn)T=0 0kr线性系统码的监督矩阵线性系统码的监督矩阵 H H 和生成矩阵和生成矩阵 G G 之间可以直接互换。之间可以直接互换。rkrSrkkSIPHQIGrkrkTkrrTkrrkkTrkrrkkTSS0QPIPQIIPQIHG)()(krTrkTkrrk P PQQP PQQ)()(或或所所

24、以以， ) 6 . 3 . 7 ()( rTrkSrkkSI IQQHHQQI IGG7.1线性分组码第19页2022-1-26 1101000011010011100101010001100101101011100010111)4,7()4,7(GGHH阵阵：可可直直接接写写出出它它的的生生成成矩矩(3) 生成矩阵与一致监督矩阵的关系生成矩阵与一致监督矩阵的关系举例：举例： 已知已知 (7,4) 线性系统码的监督矩阵为：线性系统码的监督矩阵为：QQT 1101000011010011100101010001100101101011100010111)4,7()4,7(GGHH阵阵：可可直直接

25、接写写出出它它的的生生成成矩矩 1101000011010011100101010001100101101011100010111)4,7()4,7(GGHH阵阵：可可直直接接写写出出它它的的生生成成矩矩7.1线性分组码第20页2022-1-26(4) 对偶码对偶码 对偶码：对偶码：对一个对一个 (n,k) 线性码线性码C CI，由于，由于 HHrn(GGkn)T=(0 0kr)T，如果以如果以G G 作监督矩阵，而以作监督矩阵，而以 H H 作生成矩阵，可构造另一个码作生成矩阵，可构造另一个码 C CId，C CId是一个是一个 (n,nk) 线性码，称码线性码，称码 C CId 为原码的对

26、偶码为原码的对偶码。 例如例如： (7,4) 线性码的对偶码是线性码的对偶码是 (7,3) 码：码：q (7,3) 码的生成矩阵码的生成矩阵 GG(7,3) 是是 (7,4) 码监督矩阵码监督矩阵 HH(7,4) 101110011100100111001100101101011100010111)4,7()3,7(化化成成标标准准形形式式HHGG7.1线性分组码第21页2022-1-26 4505614562463) 3 , 7 (1000110010001100101110001101cccccccccccccTT得得：由由0 0HHC CHH (n,k) 线性码的编码：线性码的编码：根据

27、线性码的监督矩阵或生成矩阵，根据线性码的监督矩阵或生成矩阵，将长为将长为 k 的信息组变换成长为的信息组变换成长为 n(nk) 的码字。的码字。 利用监督矩阵构造利用监督矩阵构造 (7,3) 线性分组码的编码电路线性分组码的编码电路q 设码字为：设码字为：C C=(c6c5c4c3c2c1c0)q 码的监督矩阵为：码的监督矩阵为： 4505614562463) 3 , 7 (1000110010001100101110001101cccccccccccccTT得得：由由0 0HHC CHH7.1线性分组码的编码第22页2022-1-26 利用监督矩阵构造利用监督矩阵构造 (7,3) 线性分组码

28、的编码电路：线性分组码的编码电路：q 根据上面方程组可直接画出根据上面方程组可直接画出 (7,3) 码的并行编码电路和串行编码电码的并行编码电路和串行编码电路路:7.1线性分组码的编码3642654165054c c cc c c cc c cc c c 第23页2022-1-26 利用监督矩阵构造利用监督矩阵构造 (7,4) 线性分组码的编码电路：线性分组码的编码电路：q 根据上面方程组可直接画出根据上面方程组可直接画出 (7,4) 码的并行编码电路和串行编码码的并行编码电路和串行编码电路电路:7.1线性分组码的编码第24页2022-1-26(1) 汉明距离、汉明重量和汉明球汉明距离、汉明重

29、量和汉明球 汉明距离汉明距离（距离）：在（距离）：在 (n,k) 线性码中，两个码字线性码中，两个码字 UU、V V 之间对应之间对应码元位上符号取值不同的个数，称为码字码元位上符号取值不同的个数，称为码字 UU、V V 之间的汉明距离。之间的汉明距离。q 线性分组码的一个码字对应于线性分组码的一个码字对应于 n 维线性空间中的一点，码字间的维线性空间中的一点，码字间的距离即为空间中两距离即为空间中两对应点的距离。因此，码字间的距离满足一般距对应点的距离。因此，码字间的距离满足一般距离公理：离公理： 10)(),(niiivudV VUU 三三角角不不等等式式对对称称性性非非负负性性),(),

30、(),(),(),(0),(WWUUWWV VV VUUUUV VV VUUV VUUdddddd7.1线性分组码第25页2022-1-26(1) 汉明距离、汉明重量和汉明球汉明距离、汉明重量和汉明球 最小距离最小距离 dmin：在在 (n,k) 线性码的码字集合中，任意两个码字间距线性码的码字集合中，任意两个码字间距离的最小值，叫做码的最小距离。若离的最小值，叫做码的最小距离。若 C C(i) 和和 C C(j) 是任意两个码字，则是任意两个码字，则码的最小距离表示为：码的最小距离表示为：q 码的最小距离是衡量码抗干扰能力（检、纠错能力）的重要参数。码的最小距离是衡量码抗干扰能力（检、纠错能

31、力）的重要参数。码的最小距离越大，码抗干扰能力就越强。码的最小距离越大，码抗干扰能力就越强。 12 , 1 ,0,),(min)()(min kjijijiddC CC C汉明球：汉明球：以码字以码字 C C 为中心，半径为为中心，半径为 t 的汉明球是与的汉明球是与 C C 的汉明距离的汉明距离t 的向量全体的向量全体 S SC C(t) ：q任意两个汉明球不相交最大程度取决于任意两个码字之间的最任意两个汉明球不相交最大程度取决于任意两个码字之间的最小汉明距离小汉明距离 dmin。 tdt ),()(R RC CR RS SC C7.1线性分组码第26页2022-1-26(1) 汉明距离、汉

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

33、距离、汉明重量和汉明球 最小距离最小距离 与最小重量与最小重量 的关系：的关系：线性分组码的最小距离等于它的最线性分组码的最小距离等于它的最小重量。小重量。 检错能力：检错能力：如果一个线性码能检出长度如果一个线性码能检出长度l 个码元的任何错误图样，个码元的任何错误图样，称码的检错能力为称码的检错能力为 l。 纠错能力：纠错能力：如果线性码能纠正长度如果线性码能纠正长度t 个码元的任意错误图样，称个码元的任意错误图样，称码的纠错能力为码的纠错能力为 t。 最小距离与检纠错能力的关系：最小距离与检纠错能力的关系：线性码的最小距离越大，意味着线性码的最小距离越大，意味着任意码字间的差别越大，则码

34、的检、纠错能力越强。任意码字间的差别越大，则码的检、纠错能力越强。7.1线性分组码第28页2022-1-26(2) 最小距离与检、纠错能力最小距离与检、纠错能力最小距离与纠错能力：最小距离与纠错能力：(n,k) 线性码能纠线性码能纠 t 个错误的充要条件是码的个错误的充要条件是码的最小距离为：最小距离为： dmin2t+1 最小距离与检错能力：最小距离与检错能力：(n,k) 线性码能够发现线性码能够发现 l 个错误的充要条件是个错误的充要条件是码的最小距离为：码的最小距离为：dminl+1最小距离与检错能力：最小距离与检错能力： 几何意义：几何意义：7.1线性分组码第29页2022-1-26(

35、2) 最小距离与检、纠错能力最小距离与检、纠错能力最小距离与检、纠错能力：最小距离与检、纠错能力：(n,k) 线性码能纠线性码能纠 t 个错误，并能发现个错误，并能发现 l 个个错误错误 (lt) 的充要条件是码的最小距离为：的充要条件是码的最小距离为： dmin t+l+1 最小距离与检、纠错能力：最小距离与检、纠错能力： 几何意义：几何意义：7.1线性分组码第30页2022-1-26(2) 最小距离与检、纠错能力最小距离与检、纠错能力当当 (n,k) 线性码的最小距离线性码的最小距离 dmin 给定后，可按实际需要给定后，可按实际需要灵活安排纠错的数目。灵活安排纠错的数目。： dmin t

36、+l+1例如：例如：对对 dmin=8 的码，可的码，可用来纠用来纠 3 检检 4 错，或纠错，或纠 2检检 5 错，或纠错，或纠 1 检检 6错，或者错，或者只用于检只用于检 7 个错误。个错误。7.1线性分组码第31页2022-1-26(3) 线性码的最小距离与监督矩阵的关系线性码的最小距离与监督矩阵的关系定理定理1：设设 H H 为为 (n,k) 线性码的一致监督矩阵，若线性码的一致监督矩阵，若 H H 中中任意任意 S 列线性无关，而列线性无关，而 H H 中存在中存在 (S+1) 列线性相关，则列线性相关，则码的最小距离为码的最小距离为 (S+1)。定理定理2：若码的最小距离为若码的

37、最小距离为 (S+1)，则该码监督矩阵的任，则该码监督矩阵的任意意 S 列线性无关，而必存在有相关的列线性无关，而必存在有相关的 (S+1)列。列。定理定理3：在二元线性码的监督矩阵在二元线性码的监督矩阵 H H 中，如果任一列都中，如果任一列都不是全不是全“0”，且任两列都不相等，则该码能纠一个错误。，且任两列都不相等，则该码能纠一个错误。（S=2，dmin=3）7.1线性分组码第32页2022-1-26(1) 如何译码？如何译码？ 用监督矩阵编码，也用监督矩阵译码：接收到一个码用监督矩阵编码，也用监督矩阵译码：接收到一个码字字 R R 后，校验后，校验 HH R R T=0 0T 是否成立

38、：是否成立：若关系成立，则认为若关系成立，则认为 R R 是一个码字；是一个码字；否则，判码字在传输中发生了错误；否则，判码字在传输中发生了错误；HH R R T 的值是否为的值是否为 0 0 是校验码字出错与否的依据。是校验码字出错与否的依据。(2) 伴随式伴随式/监督子监督子/校验子：校验子：S S=R R H H T 或或 S S T=HH R R T1. 伴随式和错误检测伴随式和错误检测7.1线性分组码第33页2022-1-26(3) 伴随式的计算伴随式的计算 发送码字：发送码字：C C=(cn1,cn2,c0) 信道错误图样：信道错误图样：E E=(en1,en2,e0) q ei=

39、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 H H C C T=0 0T，所以，所以 S S T=HH E E T 设设 HH=(h h1,h h2,h hn)，（，（h hi 表示表示 H H 的列）。代入上式得：的列）。代入上式

40、得：S S T=h h1 en1+ h h2 en2+ + h hn e07.1线性分组码的译码第34页2022-1-26(4) 伴随式的特性伴随式的特性 伴随式仅与错误图样有关，而与发送的具体码字无关，伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定；即伴随式仅由错误图样决定； 伴随式是错误的判别式：伴随式是错误的判别式：q 若若 S S=0 0，则判为没有出错，接收字是一个码字；，则判为没有出错，接收字是一个码字；q 若若 S S0 0，则判为有错。，则判为有错。 不同的错误图样具有不同的伴随式，它们是一一对应的。不同的错误图样具有不同的伴随式，它们是一一对应的。对

41、二元码，伴随式是对二元码，伴随式是 H H 阵中与错误码元对应列之和。阵中与错误码元对应列之和。7.1线性分组码的译码S T=h1 en1+ h2 en2+ + hn e0第35页2022-1-26(5) 举举 例：例：(7,3) 码接收字码接收字 R R 的伴随式计算的伴随式计算 若接收字中没有错误：若接收字中没有错误：q 设发送码字设发送码字 C C=1010011，接收码字，接收码字 R R1010011，R R 与与 C C 相同：相同：q 但接收端译码器并不知道就是发送的码字；但接收端译码器并不知道就是发送的码字；q 根据接收字根据接收字R R 计算伴随式：计算伴随式：S S T=

42、HR HR T =0 0Tq 因此，译码器判接收字无错。因此，译码器判接收字无错。 1000110010001100101110001101H7.1线性分组码的译码第36页2022-1-26(5) 举举 例：例：(7,3) 码接收矢量码接收矢量 R R 的伴随式计算的伴随式计算 若接收字中有若接收字中有 1 位错误：位错误：q 发送码字发送码字C C=1010011，接收码字，接收码字R R=1110011，伴随式为：，伴随式为：q (7,3) 码是纠单个错误的码，且码是纠单个错误的码，且S S T 等于等于HH 的第二列，因此判定接收的第二列，因此判定接收字字R R 的第二位是错的。的第二位

43、是错的。q 由于接收字由于接收字R R 中错误码元数与码的纠错能力相符，所以译码正确。中错误码元数与码的纠错能力相符，所以译码正确。 111011001111000110010001100101110001101TTR RHHS S译译码码器器判判为为有有错错由由于于0 0S S T7.1线性分组码的译码第37页2022-1-26(5) 举举 例：例：(7,3) 码接收矢量码接收矢量 R R 的伴随式计算的伴随式计算 当码元错误多于当码元错误多于 1 个时：个时：q 发送码字发送码字C C=1010011，接收码字，接收码字R R=0011011，伴随式为：，伴随式为：q 由于由于S S T

44、是第一列和第四列之和，不等于是第一列和第四列之和，不等于0 0；q 但但S S T 与与 HH 阵中任何一列都不相同无法判定错误出在哪些位上，阵中任何一列都不相同无法判定错误出在哪些位上，只是发现有错。只是发现有错。 011011011001000110010001100101110001101TTR RHHS S7.1线性分组码的译码第38页2022-1-26(6) 伴随式计算电路伴随式计算电路伴随式的计算可用电路来实现。伴随式的计算可用电路来实现。(7,3) 码为例：接收字码为例：接收字 R R =(r6r5r4r3r2r1r0)，伴随式：，伴随式： 0123045156345634601

45、234561000110010001100101110001101ssssrrrrrrrrrrrrrrrrrrrrTTR RHHS S7.1线性分组码的译码第39页2022-1-26(6) 伴随式计算电路伴随式计算电路7.1线性分组码的译码64336543265115400TrrrsrrrrsrrrsrrrsS第40页2022-1-26(1) 最佳译码准则（最大似然译码）最佳译码准则（最大似然译码） 通信是一个统计过程，纠、检错能力最终要反映到差错概率上。通信是一个统计过程，纠、检错能力最终要反映到差错概率上。 对于对于 FEC 方式，采用纠错码后的码字差错概率为方式，采用纠错码后的码字差错概

46、率为 pwe：q p(C C)：发送码字发送码字C C 的先验概率的先验概率q p(C C/R R)：后验概率后验概率)()(RCCC/pppwe2. 纠错译码纠错译码若码字数为若码字数为 2k，对充分随机的消息源有，对充分随机的消息源有 p(C C)=1/ 2k，所以最小化的，所以最小化的 pwe等价为最小化等价为最小化 p(C C C C/R R )，又等价为最大化：，又等价为最大化：p(C C =C C/R R)；对于对于 BSC 信道：信道：最大化的最大化的 p(C C =C C/R R ) 等价于最大化的等价于最大化的 p(R R /C C) ，最大化的最大化的 p(R R /C C

47、) 又等价于最小化又等价于最小化 d(R R,C C)，所以使差错概率最小的，所以使差错概率最小的译码是使接收向量译码是使接收向量 R R 与输出码字与输出码字 C C 距离最小的译码。距离最小的译码。) ,(),(min: CRCRCCddii7.1线性分组码的译码第41页2022-1-26(2) 查表译码法查表译码法 按最小距离译码，对有按最小距离译码，对有 2k 个码字的个码字的 (n,k) 线性码，为了找到与接线性码，为了找到与接收字收字 R R 有最小距离的码字，需将有最小距离的码字，需将 R R 分别和分别和 2k 个码字比较，求出最小个码字比较，求出最小距离。其中利用距离。其中利

48、用“标准阵列标准阵列”译码是最典型的方法。译码是最典型的方法。(3) 标准阵列标准阵列 码字参数：码字参数：发送码字：取自于发送码字：取自于 2k 个码字集合个码字集合 C C； 接收码字：可以是接收码字：可以是 2n 个个 n 重中任一个矢量。重中任一个矢量。 译码方法译码方法把把 2n 个个 n 重矢量划分为重矢量划分为 2k 个互不相交的子集个互不相交的子集 ，使得在，使得在每个子集中仅含一个码字；每个子集中仅含一个码字；根据码字与子集间一一对应的关系，若接收矢量根据码字与子集间一一对应的关系，若接收矢量 R Rl 落在子集落在子集 D Dl 中，中，就把就把 R Rl 译为子集译为子集

49、 D Dl 含有的码字含有的码字 C Cl；当接收矢量当接收矢量 R R 与实际发送码字在同一子集中时，译码就是正确的。与实际发送码字在同一子集中时，译码就是正确的。k221,DDD7.1线性分组码的译码2. 纠错译码纠错译码第42页2022-1-26(3) 标准阵列标准阵列 标准阵列构造方法标准阵列构造方法先将先将 2k 个码字排成一行，作为标准阵列的第一行，并将全个码字排成一行，作为标准阵列的第一行，并将全 0 码字码字 C C1=(000) 放在最左面的位置上；放在最左面的位置上；然后在剩下的然后在剩下的 (2n2k) 个个 n 重中选取一个重量最轻的重中选取一个重量最轻的 n 重重 E

50、 E2 放在放在全全 0 码字码字 C C1 下面，再将下面，再将 E E2 分别和码字分别和码字 相加，放在相加，放在对应码字下面构成阵列第二行；对应码字下面构成阵列第二行；在第二次剩下的在第二次剩下的 n 重中，选取重量最轻的重中，选取重量最轻的 n 重重 E E3，放在，放在 E E2 下面，下面，并将并将 E E3 分别加到第一行各码字上，得到第三行；分别加到第一行各码字上，得到第三行；，继续这样做下去，直到全部，继续这样做下去，直到全部 n 重用完为止。得到下表所示给定重用完为止。得到下表所示给定 (n,k) 线性码的标准阵列。线性码的标准阵列。k232,CCC7.1线性分组码的译码

51、2. 纠错译码纠错译码第43页2022-1-26(3) 标准阵列标准阵列 标准阵列构造方法标准阵列构造方法7.1线性分组码的译码2. 纠错译码纠错译码第44页2022-1-26(3) 标准阵列标准阵列 标准阵列的特性标准阵列的特性定理定理1：在标准阵列的同一行中没有相同的矢量，而且在标准阵列的同一行中没有相同的矢量，而且 2n 个个 n 重中重中任一个任一个 n 重在阵列中出现一次且仅出现一次。重在阵列中出现一次且仅出现一次。定理定理2（线性码纠错极限定理）：二元线性码纠错极限定理）：二元 (n,k) 线性码能纠线性码能纠 2nk 个错误个错误图样。这图样。这 2nk 个可纠的错误图样，包括个

52、可纠的错误图样，包括 0 0 矢量在内，即把无错的矢量在内，即把无错的情况也看成一个可纠的错误图样。情况也看成一个可纠的错误图样。陪集：陪集：标准阵列的每一行叫做码的一个陪集。标准阵列的每一行叫做码的一个陪集。陪集首：陪集首：每个陪集的第一个元素叫做陪集首。每个陪集的第一个元素叫做陪集首。(n,k) 线性码的标准阵列有线性码的标准阵列有 2k 列（和码字数量相等），列（和码字数量相等），2n/2k= 2nk 行，且任何两列和两行都没有相同的元素。行，且任何两列和两行都没有相同的元素。7.1线性分组码的译码2. 纠错译码纠错译码第45页2022-1-26(3) 标准阵列标准阵列 标准阵列的特性标

53、准阵列的特性线性码纠错能力与监督元数目的关系：线性码纠错能力与监督元数目的关系：一个可纠一个可纠 t 个错误的线性码必个错误的线性码必须满足：须满足：上式中等式成立时的线性码称为完备码。即：上式中等式成立时的线性码称为完备码。即：对于完备码，由码的纠错能力所确定的伴随式数恰好等于可纠的错误对于完备码，由码的纠错能力所确定的伴随式数恰好等于可纠的错误图样数，所以完备码的图样数，所以完备码的 (nk) 个监督码元得到了充分的利用。个监督码元得到了充分的利用。 tiknintnnn02112 tiknin027.1线性分组码的译码2. 纠错译码纠错译码第46页2022-1-26(3) 标准阵列标准阵

54、列 标准阵列的特性标准阵列的特性完备译码：完备译码：(n,k) 线性码的所有线性码的所有 2nk 个伴随式，在译码过程中都用个伴随式，在译码过程中都用来纠正所有小于等于来纠正所有小于等于 个随机错误，以及部分大于个随机错误，以及部分大于 t 的的错误图样。错误图样。限定距离译码：限定距离译码：任一个任一个 (n,k) 线性码，能纠正线性码，能纠正 个随机个随机错误，如果在译码时仅纠正错误，如果在译码时仅纠正 t t 个错误，而当错误个数大于个错误，而当错误个数大于 t 时，时，译码器不进行纠错而仅指出发生了错误。译码器不进行纠错而仅指出发生了错误。 21dt 21dt7.1线性分组码的译码2.

55、 纠错译码纠错译码第47页2022-1-26(3) 标准阵列标准阵列 标准阵列的特性标准阵列的特性 从多维矢量空间的角度看完备码从多维矢量空间的角度看完备码q 假定围绕每一个码字假定围绕每一个码字 C Ci 放置一个半径为放置一个半径为 t 的球，每个球内包含的球，每个球内包含了与该码字汉明距离小于等于了与该码字汉明距离小于等于 t 的所有接收码字的所有接收码字 R R 的集合；的集合；q 在半径为在半径为 的球内的接收码字数是：的球内的接收码字数是：q 因为有因为有 2k 个可能发送的码字，也就有个可能发送的码字，也就有 2k 个不相重叠的半径为个不相重叠的半径为 t 的球。包含在的球。包含

56、在 2k 个球中的码字总数不会超过个球中的码字总数不会超过 2n 个可能的接收码字。个可能的接收码字。 tiin0 21dt7.1线性分组码的译码2. 纠错译码纠错译码第48页2022-1-26(3) 标准阵列标准阵列 标准阵列的特性标准阵列的特性 从多维矢量空间的角度看完备码从多维矢量空间的角度看完备码q 于是一个纠于是一个纠 t 个差错的码必然满足不等式：个差错的码必然满足不等式：q 如果上式中等号成立，表示所有的接收码字都落在如果上式中等号成立，表示所有的接收码字都落在 2k 个球内，而个球内，而球外没有一个码，这就是完备码。球外没有一个码，这就是完备码。 tikntinkinin002

57、22：即即7.1线性分组码的译码2. 纠错译码纠错译码第49页2022-1-26(3) 标准阵列标准阵列 标准阵列的特性标准阵列的特性 从多维矢量空间的角度看完备码从多维矢量空间的角度看完备码q 完备码特性：完备码特性：围绕围绕 2k 个码字，个码字，汉明距离为汉明距离为 t=INT(dmin1)/2 的的所有球都是不相交的，每一个接所有球都是不相交的，每一个接收码字都落在这些球中之一，因收码字都落在这些球中之一，因此接收码与发送码的距离至多为此接收码与发送码的距离至多为 t，这时所有重量这时所有重量 t 的错误图样都能的错误图样都能用最佳（最小距离）译码器得到用最佳（最小距离）译码器得到纠正

58、，而所有重量纠正，而所有重量t+1 的错误图的错误图样都不能纠正。样都不能纠正。7.1线性分组码的译码2. 纠错译码纠错译码第50页2022-1-26(3) 标准阵列标准阵列 标准阵列的特性标准阵列的特性 从多维矢量空间的角度看完备码从多维矢量空间的角度看完备码q 举例：举例：对纠一个错误的对纠一个错误的 (7,4) 汉明码：汉明码：(7,4) 汉明码是一个完备码。汉明码是一个完备码。 所有汉明码都是完备码：所有汉明码都是完备码：（满足（满足2nk = 2r=n+1）。）。 112,811, 82nnknkn所所以以：7.1线性分组码的译码2. 纠错译码纠错译码第51页2022-1-26(3)

59、 标准阵列标准阵列 标准阵列的特性标准阵列的特性 标准阵列译码标准阵列译码 = 最小距离译码最小距离译码 = 最佳译码最佳译码q 陪集首是可纠正的错误图样，为了使译码错误概率最小，应选取陪集首是可纠正的错误图样，为了使译码错误概率最小，应选取出现概率最大的错误图样作陪集首；出现概率最大的错误图样作陪集首；q 重量较轻的错误图样出现概率较大，所以在构造标准阵列时是选重量较轻的错误图样出现概率较大，所以在构造标准阵列时是选取重量最轻的取重量最轻的 n 重作陪集首；重作陪集首；q 当错误图样为陪集首时（可纠的错误图样），接收矢量与原发送当错误图样为陪集首时（可纠的错误图样），接收矢量与原发送码字间的

60、距离（等于陪集首）最小；码字间的距离（等于陪集首）最小；q 因此，选择重量最轻的元素作陪集首，按标准阵列译码就是按最因此，选择重量最轻的元素作陪集首，按标准阵列译码就是按最小距离译码；小距离译码；q 所以标准阵列译码法也是最佳译码法。所以标准阵列译码法也是最佳译码法。7.1线性分组码的译码2. 纠错译码纠错译码第52页2022-1-26(3) 标准阵列标准阵列 标准阵列的特性标准阵列的特性定理定理3：在标准阵列中，一个陪集的所有在标准阵列中，一个陪集的所有 2k 个个 n 重有相同的伴随式，重有相同的伴随式，不同的陪集伴随式互不相同。不同的陪集伴随式互不相同。证明证明：设设 H H 为给定为给