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

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

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

3、编成的 2k个码字集合，称为线性分组码。个码字集合，称为线性分组码。 码矢：码矢：一个一个 n 重的码字可以用矢量来表示：重的码字可以用矢量来表示： C C=(cn 1,cn1,c1,c0 ) (n,k) 线性码：线性码：信息位长为信息位长为 k，码字长为，码字长为 n 的线性码。的线性码。 编码效率编码效率/编码速率编码速率/码率码率/传信率：传信率：R=k /n。 它说明了信道的利用效率，它说明了信道的利用效率，R 是衡量码性能的一个重是衡量码性能的一个重 要参数。要参数。 第4页2021-7-12 (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

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

6、和信息元之间是线性运算关系，所 以由线性监督方程所确定的分组码是线性分组码。以由线性监督方程所确定的分组码是线性分组码。 1. 线性分组码的校验矩阵线性分组码的校验矩阵 7.1 线 性 分 组 码 第6页2021-7-12 (2) 举例举例 信息码组信息码组 (101)，即，即c6=1, c5=0, c4=1 得：得： c3=0, c2=0, c1=1, c0=1 由信息码组由信息码组 (101) 编出的码字为编出的码字为 (1010011)。其它。其它 7 个码字如表。个码字如表。 00000 00000 0000 00000 045 156 2456 346 ccc ccc cccc cc

7、c ) 1 . 2 . 8 ( 450 561 4562 463 ccc ccc cccc ccc 1. 线性分组码的校验矩阵线性分组码的校验矩阵 7.1 线 性 分 组 码 第7页2021-7-12 (3) 一致监督矩阵一致监督矩阵 为了运算方便，将监督方程为了运算方便，将监督方程 写成矩阵形式，得：写成矩阵形式，得： ) 2 . 2 . 8 ( 0 0 0 0 1000110 0100011 0010111 0001101 0 1 2 3 4 5 6 c c c c c c c HH C CT=0 0T 或或 C C HHT=0 0 C CT、HHT、0 0T 分别表示分别表示 C C、H

8、H、0 0 的转置矩阵。的转置矩阵。 1. 线性分组码的校验矩阵线性分组码的校验矩阵 00000 00000 0000 00000 045 156 2456 346 ccc ccc cccc ccc ) 3 . 2 . 8 ( 1000110 0100011 0010111 0001101 0000 0123456 HH 0 0 C Cccccccc令令 7.1 线 性 分 组 码 第8页2021-7-12 (3) 一致监督矩阵一致监督矩阵 系数矩阵系数矩阵 H H 的后四列组成一个的后四列组成一个 (44) 阶单位子阵，用阶单位子阵，用 I I4 表示，表示，H H 的其余部分用的其余部分用

9、 P P 表示：表示： 推广到一般情况：推广到一般情况：对对 (n,k) 线性分组码，每个码字中的线性分组码，每个码字中的 r(r=nk) 个个 监督元与信息元之间的关系由下面的线性方程组确定：监督元与信息元之间的关系由下面的线性方程组确定： 1. 线性分组码的校验矩阵线性分组码的校验矩阵 )4.2.8( 1000 0100 0010 0001 110 011 111 101 434)37( 434 I IP PHH I IP P , 所所以以 )4.2.8( 1000 0100 0010 0001 110 011 111 101 434)37( 434 I IP PHH I IP P , 所

10、所以以 ) 5 . 2 . 8( 0 0 0 02211 02222121 01212111 chchch chchch chchch rnnrnr nnn nnn 7.1 线 性 分 组 码 )3 . 2 . 8( 1000110 0100011 0010111 0001101 0000 0123456 HH 0 0 C Cccccccc令令 第9页2021-7-12 (3) 一致监督矩阵一致监督矩阵 令上式的系数矩阵为令上式的系数矩阵为 HH，码字行阵列为，码字行阵列为 C C ： 0211 ccc nnn C C ) 6 . 2 . 8 ( 21 22221 11211 rnrr n n

11、 nr hhh hhh hhh HH 矩矩阵阵，简简称称监监督督矩矩阵阵。线线性性分分组组码码的的一一致致监监督督为为称称 或或可可写写成成：式式 ),( )7.2.8()()()()5.2.7( 1111 kn r T nrn T r T nnr HH 0 0HHC C0 0C CHH 矩矩阵阵，简简称称监监督督矩矩阵阵。线线性性分分组组码码的的一一致致监监督督为为称称 或或可可写写成成：式式 ),( )7.2.8()()()()5.2.7( 1111 kn r T nrn T r T nnr HH 0 0HHC C0 0C CHH 1. 线性分组码的校验矩阵线性分组码的校验矩阵 7.1 线

12、 性 分 组 码 ) 5 . 2 . 8 ( 0 0 0 02211 02222121 01212111 chchch chchch chchch rnnrnr nnn nnn 第10页2021-7-12 (4) 一致监督矩阵特性一致监督矩阵特性 对对 H H 各行实行初等变换，将后面各行实行初等变换，将后面 r 列化为单位子阵，得列化为单位子阵，得 到下面矩阵，行变换所得方程组与原方程组同解。到下面矩阵，行变换所得方程组与原方程组同解。 监督矩阵监督矩阵 H H 的标准形式：的标准形式：后面后面 r 列是一单位子阵的监督列是一单位子阵的监督 矩阵矩阵 HH。 )8 . 2 . 8( 100

13、010 001 21 22221 11211 rnrr k k nr ppp ppp ppp HH 1. 线性分组码的校验矩阵线性分组码的校验矩阵 7.1 线 性 分 组 码 第11页2021-7-12 (4) 一致监督矩阵特性一致监督矩阵特性 q H H 阵的每一行都代表一个监督方程，它表示与该行中阵的每一行都代表一个监督方程，它表示与该行中“1”相对应相对应 的码元的模的码元的模 2 和为和为 0。 q H H 的标准形式表明相应的监督元是由哪些信息元决定。例如的标准形式表明相应的监督元是由哪些信息元决定。例如 (7,3) 码的码的 H H 阵的第一行为阵的第一行为 (1011000)，说

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

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

16、任意两个码字，则为其中的任意两个码字，则 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 维线性空

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

18、Vn 的的 k 维子空维子空 间中，一定存在间中，一定存在 k 个线性独立的码字：个线性独立的码字：g g1,g g2, g gk。码。码 C CI 中其它中其它 任何码字任何码字 C C 都可以表示为这都可以表示为这 k 个码字的一种线性组合，即：个码字的一种线性组合，即： 。写写成成矩矩阵阵形形式式得得： ）（ 1, 1 , 0),2( 1 . 3 . 8 02211 kiGFm mmm i kkk g gg gg gC C 阶阶矩矩阵阵。是是一一个个 待待编编码码的的信信息息组组 nk mmm nk kk GG mm 021 ) 2 . 3 . 8 (, 1 2 1 0211nkk k

19、kkn mmm GGmm g g g g g g C C 7.1 线 性 分 组 码 第14页2021-7-12 (2) 线性分组码的生成矩阵线性分组码的生成矩阵 生成矩阵定义：生成矩阵定义：由于矩阵由于矩阵 G G 生成了生成了 (n,k) 线性码，称矩阵线性码，称矩阵 G G 为为 (n,k) 线性码的生成矩阵。线性码的生成矩阵。 ) 3 . 3 . 8 ( 21 22221 11211 2 1 knkk n n k nk ggg ggg ggg g g g g g g GG 生成矩阵生成矩阵G G 的特性的特性 q G G 中每一行中每一行 g gi=(gi1,gi2, gin ) 都是

20、一个码字；都是一个码字； q 对每一个信息组对每一个信息组 mm，由矩阵，由矩阵 G G 都可以求得都可以求得 (n,k) 线性码对应的码线性码对应的码 字。字。 q (n,k) 线性码的每一个码字都是生成矩阵线性码的每一个码字都是生成矩阵 G G 的行矢量的线性组合，的行矢量的线性组合， 所以它的所以它的 2k 个码字构成了由个码字构成了由 G G 的行张成的的行张成的 n 维空间的一个维空间的一个 k 维子维子 空间空间 V Vk。 7.1 线 性 分 组 码 11121 21222 12 n n kkkn ggg ggg ggg 第15页2021-7-12 ) 4 . 3 . 8 ( 1

21、00 010 001 )(21 )( 22221 )( 11211 rk k knkkk kn kn nk qqq qqq qqq QQI IGG (2) 线性分组码的生成矩阵线性分组码的生成矩阵 线性系统分组码线性系统分组码 q 线性系统分组码的构成：线性系统分组码的构成：通过行初等变换，将通过行初等变换，将 G G 化为前化为前 k 列是列是 单位子阵的标准形式。单位子阵的标准形式。 )5 . 3 . 8( , 2 , 1 , 2 , 1 ),(),( 02211)( 0210211 knjqmqmqmc kimc ,mmmccc kjjkjkjkn ikin nkkknnn 得得：将将上

22、上式式代代入入GGC C 7.1 线 性 分 组 码 第16页2021-7-12 (2) 线性分组码的生成矩阵线性分组码的生成矩阵 线性系统分组码线性系统分组码 q 线性系统分组码定义：线性系统分组码定义：用标准生成矩阵用标准生成矩阵 GGk n 编成的 编成的 码字，前面码字，前面 k 位为信息位，后面位为信息位，后面 r=nk 位为校验位，这位为校验位，这 种信息位在前校验位在后的线性分组码称为线性系统分种信息位在前校验位在后的线性分组码称为线性系统分 组码。组码。 q 当生成矩阵当生成矩阵 G G 确定之后，确定之后，(n,k) 线性码就完全被确定，线性码就完全被确定， 只要找到码的生成

23、矩阵，编码问题也同样被解决。只要找到码的生成矩阵，编码问题也同样被解决。 7.1 线 性 分 组 码 第17页2021-7-12 )1010011( 1101000 0110100 1110010 1010001 0101 )1010( 1101000 0110100 1110010 1010001 744171 41 74 GGmmC C mm GG ，则则：若若 (2) 线性分组码的生成矩阵线性分组码的生成矩阵 举例：举例：(7,4) 线性码的生成矩阵为：线性码的生成矩阵为： )1010011( 1101000 0110100 1110010 1010001 0101 )1010( 110

24、1000 0110100 1110010 1010001 744171 41 74 GGmmC C mm GG ，则则：若若 )1010011( 1101000 0110100 1110010 1010001 0101 )1010( 1101000 0110100 1110010 1010001 744171 41 74 GGmmC C mm GG ，则则：若若 7.1 线 性 分 组 码 第18页2021-7-12 (3) 生成矩阵与一致监督矩阵的关系生成矩阵与一致监督矩阵的关系 由于生成矩阵由于生成矩阵 G G 的每一行都是一个码字，所以的每一行都是一个码字，所以 G G 的每行都满足：的

25、每行都满足： HHr n(C C1n)T=(0 01r)T，则有： ，则有：HHr n(G Gk n)T=(0 0kr)T 或 或 GGk n(H Hr n)T=0 0kr 线性系统码的监督矩阵线性系统码的监督矩阵 H H 和生成矩阵和生成矩阵 G G 之间可以直接互换。之间可以直接互换。 rkrSrkkS IPHQIG rkrk T kr r T kr rkk T rkrrkk T SS 0QP I P QIIPQIHG)( )( kr T rk T krrk P PQQ P PQQ )( )( 或或 所所以以， ) 6 . 3 . 7 ( )( r T rkS rkkS I IQQHH Q

26、QI IGG 7.1 线 性 分 组 码 第19页2021-7-12 1101000 0110100 1110010 1010001 1001011 0101110 0010111 )4,7( )4,7( GG HH 阵阵：可可直直接接写写出出它它的的生生成成矩矩 (3) 生成矩阵与一致监督矩阵的关系生成矩阵与一致监督矩阵的关系 举例：举例： 已知已知 (7,4) 线性系统码的监督矩阵为：线性系统码的监督矩阵为： Q QT 1101000 0110100 1110010 1010001 1001011 0101110 0010111 )4,7( )4,7( GG HH 阵阵：可可直直接接写写出

27、出它它的的生生成成矩矩 1101000 0110100 1110010 1010001 1001011 0101110 0010111 )4,7( )4,7( GG HH 阵阵：可可直直接接写写出出它它的的生生成成矩矩 7.1 线 性 分 组 码 第20页2021-7-12 (4) 对偶码对偶码 对偶码：对偶码：对一个对一个 (n,k) 线性码线性码C CI，由于，由于 HHr n(G Gk n)T=(0 0kr)T， ， 如果以如果以G G 作监督矩阵，而以作监督矩阵，而以 H H 作生成矩阵，可构造另一个码作生成矩阵，可构造另一个码 C CId，C CId是一个是一个 (n,nk) 线性码

28、，称码线性码，称码 C CId 为原码的对偶码为原码的对偶码。 例如例如： (7,4) 线性码的对偶码是线性码的对偶码是 (7,3) 码：码： q (7,3) 码的生成矩阵码的生成矩阵 GG(7,3) 是是 (7,4) 码监督矩阵码监督矩阵 HH(7,4) 1011100 1110010 0111001 1001011 0101110 0010111 )4,7()3,7( 化化成成标标准准形形式式 HHGG 7.1 线 性 分 组 码 第21页2021-7-12 450 561 4562 463 ) 3 , 7 ( 1000110 0100011 0010111 0001101 ccc ccc

29、 cccc ccc TT 得得：由由0 0HHC C HH (n,k) 线性码的编码：线性码的编码：根据线性码的监督矩阵或生成矩阵，根据线性码的监督矩阵或生成矩阵， 将长为将长为 k 的信息组变换成长为的信息组变换成长为 n(nk) 的码字。的码字。 利用监督矩阵构造利用监督矩阵构造 (7,3) 线性分组码的编码电路线性分组码的编码电路 q 设码字为：设码字为：C C=(c6c5c4c3c2c1c0) q 码的监督矩阵为：码的监督矩阵为： 450 561 4562 463 ) 3 , 7 ( 1000110 0100011 0010111 0001101 ccc ccc cccc ccc TT

30、 得得：由由0 0HHC C HH 7.1 线 性 分 组 码 的 编 码 第22页2021-7-12 利用监督矩阵构造利用监督矩阵构造 (7,3) 线性分组码的编码电路：线性分组码的编码电路： q 根据上面方程组可直接画出根据上面方程组可直接画出 (7,3) 码的并行编码电路和串行编码电码的并行编码电路和串行编码电 路路: 7.1 线 性 分 组 码 的 编 码 364 2654 165 054 c c c c c c c c c c c c c 第23页2021-7-12 利用监督矩阵构造利用监督矩阵构造 (7,4) 线性分组码的编码电路：线性分组码的编码电路： q 根据上面方程组可直接画

31、出根据上面方程组可直接画出 (7,4) 码的并行编码电路和串行编码码的并行编码电路和串行编码 电路电路: 7.1 线 性 分 组 码 的 编 码 第24页2021-7-12 (1) 汉明距离、汉明重量和汉明球汉明距离、汉明重量和汉明球 汉明距离汉明距离（距离）：在（距离）：在 (n,k) 线性码中，两个码字线性码中，两个码字 UU、V V 之间对应之间对应 码元位上符号取值不同的个数，称为码字码元位上符号取值不同的个数，称为码字 UU、V V 之间的汉明距离。之间的汉明距离。 q 线性分组码的一个码字对应于线性分组码的一个码字对应于 n 维线性空间中的一点，码字间的维线性空间中的一点，码字间的

32、 距离即为空间中两距离即为空间中两对应点的距离。因此，码字间的距离满足一般距对应点的距离。因此，码字间的距离满足一般距 离公理：离公理： 1 0 )(),( n i ii vudV VUU 三三角角不不等等式式 对对称称性性 非非负负性性 ),(),(),( ),(),( 0),( WWUUWWV VV VUU UUV VV VUU V VUU ddd dd d 7.1 线 性 分 组 码 第25页2021-7-12 (1) 汉明距离、汉明重量和汉明球汉明距离、汉明重量和汉明球 最小距离最小距离 dmin：在在 (n,k) 线性码的码字集合中，任意两个码字间距线性码的码字集合中，任意两个码字间

33、距 离的最小值，叫做码的最小距离。若离的最小值，叫做码的最小距离。若 C C(i) 和和 C C(j) 是任意两个码字，则是任意两个码字，则 码的最小距离表示为：码的最小距离表示为： q 码的最小距离是衡量码抗干扰能力（检、纠错能力）的重要参数。码的最小距离是衡量码抗干扰能力（检、纠错能力）的重要参数。 码的最小距离越大，码抗干扰能力就越强。码的最小距离越大，码抗干扰能力就越强。 12 , 1 ,0,),(min )()( min kji ji jiddC CC C 汉明球：汉明球：以码字以码字 C C 为中心，半径为为中心，半径为 t 的汉明球是与的汉明球是与 C C 的汉明距离的汉明距离

34、t 的向量全体的向量全体 S SC C(t) ： q任意两个汉明球不相交最大程度取决于任意两个码字之间的最任意两个汉明球不相交最大程度取决于任意两个码字之间的最 小汉明距离小汉明距离 dmin。 td t ),( )( R RC CR RS S C C 7.1 线 性 分 组 码 第26页2021-7-12 (1) 汉明距离、汉明重量和汉明球汉明距离、汉明重量和汉明球 汉明球：汉明球： 汉明重量（码字重量）汉明重量（码字重量）W：码字中非码字中非 0 码元符号的个数，称为该码码元符号的个数，称为该码 字的汉明重量。字的汉明重量。 q在二元线性码中，码字重量就是码字中含在二元线性码中，码字重量就

35、是码字中含“1”的个数。的个数。 最小重量最小重量 Wmin ：线性分组码线性分组码 C CI 中，非中，非 0 0 码字重量最小值，叫做码码字重量最小值，叫做码 C CI 的最小重量：的最小重量： Wmin =minW(V V),V VC CI ,V V0 0 7.1 线 性 分 组 码 第27页2021-7-12 (1) 汉明距离、汉明重量和汉明球汉明距离、汉明重量和汉明球 最小距离最小距离 与最小重量与最小重量 的关系：的关系：线性分组码的最小距离等于它的最线性分组码的最小距离等于它的最 小重量。小重量。 检错能力：检错能力：如果一个线性码能检出长度如果一个线性码能检出长度l 个码元的任

36、何错误图样，个码元的任何错误图样， 称码的检错能力为称码的检错能力为 l。 纠错能力：纠错能力：如果线性码能纠正长度如果线性码能纠正长度t 个码元的任意错误图样，称个码元的任意错误图样，称 码的纠错能力为码的纠错能力为 t。 最小距离与检纠错能力的关系：最小距离与检纠错能力的关系：线性码的最小距离越大，意味着线性码的最小距离越大，意味着 任意码字间的差别越大，则码的检、纠错能力越强。任意码字间的差别越大，则码的检、纠错能力越强。 7.1 线 性 分 组 码 第28页2021-7-12 (2) 最小距离与检、纠错能力最小距离与检、纠错能力 最小距离与纠错能力：最小距离与纠错能力：(n,k) 线性

37、码能纠线性码能纠 t 个错误的充要条件是码的个错误的充要条件是码的 最小距离为：最小距离为： dmin2t+1 最小距离与检错能力：最小距离与检错能力：(n,k) 线性码能够发现线性码能够发现 l 个错误的充要条件是个错误的充要条件是 码的最小距离为：码的最小距离为：dminl+1 最小距离与检错能力：最小距离与检错能力： 几何意义：几何意义： 7.1 线 性 分 组 码 第29页2021-7-12 (2) 最小距离与检、纠错能力最小距离与检、纠错能力 最小距离与检、纠错能力：最小距离与检、纠错能力：(n,k) 线性码能纠线性码能纠 t 个错误，并能发现个错误，并能发现 l 个个 错误错误 (

38、lt) 的充要条件是码的最小距离为：的充要条件是码的最小距离为： dmin t+l+1 最小距离与检、纠错能力：最小距离与检、纠错能力： 几何意义：几何意义： 7.1 线 性 分 组 码 第30页2021-7-12 (2) 最小距离与检、纠错能力最小距离与检、纠错能力 当当 (n,k) 线性码的最小距离线性码的最小距离 dmin 给定后，可按实际需要给定后，可按实际需要 灵活安排纠错的数目。灵活安排纠错的数目。 ： dmin t+l+1 例如：例如：对对 dmin=8 的码，可的码，可 用来纠用来纠 3 检检 4 错，或纠错，或纠 2检检 5 错，或纠错，或纠 1 检检 6错，或者错，或者 只

39、用于检只用于检 7 个错误。个错误。 7.1 线 性 分 组 码 第31页2021-7-12 (3) 线性码的最小距离与监督矩阵的关系线性码的最小距离与监督矩阵的关系 定理定理1：设设 H H 为为 (n,k) 线性码的一致监督矩阵，若线性码的一致监督矩阵，若 H H 中中 任意任意 S 列线性无关，而列线性无关，而 H H 中存在中存在 (S+1) 列线性相关，则列线性相关，则 码的最小距离为码的最小距离为 (S+1)。 定理定理2：若码的最小距离为若码的最小距离为 (S+1)，则该码监督矩阵的任，则该码监督矩阵的任 意意 S 列线性无关，而必存在有相关的列线性无关，而必存在有相关的 (S+

40、1)列。列。 定理定理3：在二元线性码的监督矩阵在二元线性码的监督矩阵 H H 中，如果任一列都中，如果任一列都 不是全不是全“0”，且任两列都不相等，则该码能纠一个错误。，且任两列都不相等，则该码能纠一个错误。 （S=2，dmin=3） 7.1 线 性 分 组 码 第32页2021-7-12 (1) 如何译码？如何译码？ 用监督矩阵编码，也用监督矩阵译码：接收到一个码用监督矩阵编码，也用监督矩阵译码：接收到一个码 字字 R R 后，校验后，校验 HH R R T=0 0T 是否成立：是否成立： 若关系成立，则认为若关系成立，则认为 R R 是一个码字；是一个码字； 否则，判码字在传输中发生了

41、错误；否则，判码字在传输中发生了错误； HH R R T 的值是否为的值是否为 0 0 是校验码字出错与否的依据。是校验码字出错与否的依据。 (2) 伴随式伴随式/监督子监督子/校验子：校验子：S S=R R H H T 或或 S S T=HH R R T 1. 伴随式和错误检测伴随式和错误检测 7.1 线 性 分 组 码 第33页2021-7-12 (3) 伴随式的计算伴随式的计算 发送码字：发送码字：C C=(cn 1,cn2,c0) 信道错误图样：信道错误图样：E E=(en 1,en2,e0) q ei=0，表示第，表示第 i 位无错；位无错； q ei=1，表示第，表示第 i 位有错

42、。位有错。i=n1,n2,0 接收字：接收字：R R=(rn 1,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 的列）。代入上式得：的列）。代入上式得： S S T=h h1 en 1+ h h2 en2+ + h hn e0

43、 7.1 线 性 分 组 码 的 译 码 第34页2021-7-12 (4) 伴随式的特性伴随式的特性 伴随式仅与错误图样有关，而与发送的具体码字无关，伴随式仅与错误图样有关，而与发送的具体码字无关， 即伴随式仅由错误图样决定；即伴随式仅由错误图样决定； 伴随式是错误的判别式：伴随式是错误的判别式： q 若若 S S=0 0，则判为没有出错，接收字是一个码字；，则判为没有出错，接收字是一个码字； q 若若 S S0 0，则判为有错。，则判为有错。 不同的错误图样具有不同的伴随式，它们是一一对应的。不同的错误图样具有不同的伴随式，它们是一一对应的。 对二元码，伴随式是对二元码，伴随式是 H H

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

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

46、的第二位是错的。的第二位是错的。 q 由于接收字由于接收字R R 中错误码元数与码的纠错能力相符，所以译码正确。中错误码元数与码的纠错能力相符，所以译码正确。 1 1 1 0 1 1 0 0 1 1 1 1000110 0100011 0010111 0001101 TT R RHHS S 译译码码器器判判为为有有错错 由由于于0 0S S T 7.1 线 性 分 组 码 的 译 码 第37页2021-7-12 (5) 举举 例：例：(7,3) 码接收矢量码接收矢量 R R 的伴随式计算的伴随式计算 当码元错误多于当码元错误多于 1 个时：个时： q 发送码字发送码字C C=1010011，接

47、收码字，接收码字R R=0011011，伴随式为：，伴随式为： q 由于由于S S T 是第一列和第四列之和，不等于是第一列和第四列之和，不等于0 0； q 但但S S T 与与 HH 阵中任何一列都不相同无法判定错误出在哪些位上，阵中任何一列都不相同无法判定错误出在哪些位上， 只是发现有错。只是发现有错。 0 1 1 0 1 1 0 1 1 0 0 1000110 0100011 0010111 0001101 TT R RHHS S 7.1 线 性 分 组 码 的 译 码 第38页2021-7-12 (6) 伴随式计算电路伴随式计算电路 伴随式的计算可用电路来实现。伴随式的计算可用电路来实

48、现。 (7,3) 码为例：接收字码为例：接收字 R R =(r6r5r4r3r2r1r0)，伴随式：，伴随式： 0 1 2 3 045 156 3456 346 0 1 2 3 4 5 6 1000110 0100011 0010111 0001101 s s s s rrr rrr rrrr rrr r r r r r r r TT R RHHS S 7.1 线 性 分 组 码 的 译 码 第39页2021-7-12 (6) 伴随式计算电路伴随式计算电路 7.1 线 性 分 组 码 的 译 码 6433 65432 6511 5400 T rrrs rrrrs rrrs rrrs S 第40

49、页2021-7-12 (1) 最佳译码准则（最大似然译码）最佳译码准则（最大似然译码） 通信是一个统计过程，纠、检错能力最终要反映到差错概率上。通信是一个统计过程，纠、检错能力最终要反映到差错概率上。 对于对于 FEC 方式，采用纠错码后的码字差错概率为方式，采用纠错码后的码字差错概率为 pwe： q p(C C)：发送码字发送码字C C 的先验概率的先验概率 q p(C C/R R)：后验概率后验概率 )()(RCCC/pppwe 2. 纠错译码纠错译码 若码字数为若码字数为 2k，对充分随机的消息源有，对充分随机的消息源有 p(C C)=1/ 2k，所以最小化的，所以最小化的 pwe等价为

50、最小化等价为最小化 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) 又等价于最小化又等价于最小化 d(R R,C C)，所以使差错概率最小的，所以使差错概率最小的 译码是使接收向量译码是使接收向量 R R 与输出码字与输出码字 C C 距离最小的译码。距离最小的译码。 ) ,(),(min: CRCRC C dd i i 7.1 线 性 分 组 码 的 译 码 第

51、41页2021-7-12 (2) 查表译码法查表译码法 按最小距离译码，对有按最小距离译码，对有 2k 个码字的个码字的 (n,k) 线性码，为了找到与接线性码，为了找到与接 收字收字 R R 有最小距离的码字，需将有最小距离的码字，需将 R R 分别和分别和 2k 个码字比较，求出最小个码字比较，求出最小 距离。其中利用距离。其中利用“标准阵列标准阵列”译码是最典型的方法。译码是最典型的方法。 (3) 标准阵列标准阵列 码字参数：码字参数：发送码字：取自于发送码字：取自于 2k 个码字集合个码字集合 C C； 接收码字：可以是接收码字：可以是 2n 个个 n 重中任一个矢量。重中任一个矢量。

52、 译码方法译码方法 把把 2n 个个 n 重矢量划分为重矢量划分为 2k 个互不相交的子集个互不相交的子集 ，使得在，使得在 每个子集中仅含一个码字；每个子集中仅含一个码字； 根据码字与子集间一一对应的关系，若接收矢量根据码字与子集间一一对应的关系，若接收矢量 R Rl 落在子集落在子集 D Dl 中，中， 就把就把 R Rl 译为子集译为子集 D Dl 含有的码字含有的码字 C Cl； 当接收矢量当接收矢量 R R 与实际发送码字在同一子集中时，译码就是正确的。与实际发送码字在同一子集中时，译码就是正确的。 k 2 21 ,DDD 7.1 线 性 分 组 码 的 译 码 2. 纠错译码纠错译

53、码 第42页2021-7-12 (3) 标准阵列标准阵列 标准阵列构造方法标准阵列构造方法 先将先将 2k 个码字排成一行，作为标准阵列的第一行，并将全个码字排成一行，作为标准阵列的第一行，并将全 0 码字码字 C C1=(000) 放在最左面的位置上；放在最左面的位置上； 然后在剩下的然后在剩下的 (2n2k) 个个 n 重中选取一个重量最轻的重中选取一个重量最轻的 n 重重 E E2 放在放在 全全 0 码字码字 C C1 下面，再将下面，再将 E E2 分别和码字分别和码字 相加，放在相加，放在 对应码字下面构成阵列第二行；对应码字下面构成阵列第二行； 在第二次剩下的在第二次剩下的 n

54、重中，选取重量最轻的重中，选取重量最轻的 n 重重 E E3，放在，放在 E E2 下面，下面， 并将并将 E E3 分别加到第一行各码字上，得到第三行；分别加到第一行各码字上，得到第三行； ，继续这样做下去，直到全部，继续这样做下去，直到全部 n 重用完为止。得到下表所示给定重用完为止。得到下表所示给定 (n,k) 线性码的标准阵列。线性码的标准阵列。 k 2 32 ,CCC 7.1 线 性 分 组 码 的 译 码 2. 纠错译码纠错译码 第43页2021-7-12 (3) 标准阵列标准阵列 标准阵列构造方法标准阵列构造方法 7.1 线 性 分 组 码 的 译 码 2. 纠错译码纠错译码 第

55、44页2021-7-12 (3) 标准阵列标准阵列 标准阵列的特性标准阵列的特性 定理定理1：在标准阵列的同一行中没有相同的矢量，而且在标准阵列的同一行中没有相同的矢量，而且 2n 个个 n 重中重中 任一个任一个 n 重在阵列中出现一次且仅出现一次。重在阵列中出现一次且仅出现一次。 定理定理2（线性码纠错极限定理）：二元线性码纠错极限定理）：二元 (n,k) 线性码能纠线性码能纠 2n k 个错误 个错误 图样。这图样。这 2n k 个可纠的错误图样，包括 个可纠的错误图样，包括 0 0 矢量在内，即把无错的矢量在内，即把无错的 情况也看成一个可纠的错误图样。情况也看成一个可纠的错误图样。

56、陪集：陪集：标准阵列的每一行叫做码的一个陪集。标准阵列的每一行叫做码的一个陪集。 陪集首：陪集首：每个陪集的第一个元素叫做陪集首。每个陪集的第一个元素叫做陪集首。 (n,k) 线性码的标准阵列有线性码的标准阵列有 2k 列（和码字数量相等），列（和码字数量相等），2n/2k= 2n k 行，且任何两列和两行都没有相同的元素。行，且任何两列和两行都没有相同的元素。 7.1 线 性 分 组 码 的 译 码 2. 纠错译码纠错译码 第45页2021-7-12 (3) 标准阵列标准阵列 标准阵列的特性标准阵列的特性 线性码纠错能力与监督元数目的关系：线性码纠错能力与监督元数目的关系：一个可纠一个可纠

57、t 个错误的线性码必个错误的线性码必 须满足：须满足： 上式中等式成立时的线性码称为完备码。即：上式中等式成立时的线性码称为完备码。即： 对于完备码，由码的纠错能力所确定的伴随式数恰好等于可纠的错误对于完备码，由码的纠错能力所确定的伴随式数恰好等于可纠的错误 图样数，所以完备码的图样数，所以完备码的 (nk) 个监督码元得到了充分的利用。个监督码元得到了充分的利用。 t i kn i n t nnn 0 21 12 t i kn i n 0 2 7.1 线 性 分 组 码 的 译 码 2. 纠错译码纠错译码 第46页2021-7-12 (3) 标准阵列标准阵列 标准阵列的特性标准阵列的特性 完

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

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

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