信息论与编码技术 第7章信道纠错编码 苗付友 mfy@ustc.edu.cn 2019年12月
苗付友 mfy@ustc.edu.cn 2019年12月
7.3线性分组码 7.3.1一般概念 7.3.2一致监督方程和一致监督矩阵 7.33线性分组码的生成矩阵 7.34线性分组码的编码 7.3.5线性分组码的最距离、检错和纠错能力 7.3.6线性分组码的译码 7.3.7线性分组码的性能 7.38汉明码 7.3.9由已知码构造新码的方法 7.3.10GSM的信道编码总体方案 7.3.11线性分组码的码限 ash mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 3/
mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 3/ 7.3.1 一般概念 7.3.2 一致监督方程和一致监督矩阵 7.3.3 线性分组码的生成矩阵 7.3.4 线性分组码的编码 7.3.5 线性分组码的最小距离、检错和纠错能力 7.3.6 线性分组码的译码 7.3.7 线性分组码的性能 7.3.8 汉明码 7.3.9 由已知码构造新码的方法 7.3.10 GSM 的信道编码总体方案 7.3.11 线性分组码的码限
7.3.1一般概念 (1)线性分组码的编码:编码过程分为两步 把信息序列按一定长度分成若千信息码组,每组由k 位组成; 〉编码器按照预定的线性规则(可由线性方程组规定), 把信息码组变换成门重(m>K)码字,其中(n-k) 个附加码元是由信息码元的线性运算产生的。 (2)线性分组码的码字数:信息码组长k位,有2k个 不同的信息码组,有2k个码字与它们一—对应。 erence 0(0 ash mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码
mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 4/ (1) 线性分组码的编码：编码过程分为两步： 把信息序列按一定长度分成若干信息码组, 每组由 k 位组成; 编码器按照预定的线性规则（可由线性方程组规定）， 把信息码组变换成 n 重（n>k）码字，其中 (n－k) 个附加码元是由信息码元的线性运算产生的。 (2) 线性分组码的码字数：信息码组长 k 位，有 2k 个 不同的信息码组，有 2k 个码字与它们一一对应
7.3.1一般概念 (3)术语 〉线性分组码:通过预定的线性运算将长为k位的信息 码组变换成刀重的码字(m>A)。由2k个信息码组所 编成的2个码字集合,称为线性分组码 码字:一个门重的码字可以用矢量来表示: n-1,Cn-1y.yCl, C0 (n,k)线性码:信息位长为k,码长为门的线性码。 〉编码效率/编码速率/码率/传信率:R=k/。它说明 了信道的利用效率,R是衡量码性能的一个重要参数。 ash 返回目录 mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 5/
mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 5/ (3) 术语 线性分组码：通过预定的线性运算将长为 k 位的信息 码组变换成 n 重的码字 (n>k)。由 2k 个信息码组所 编成的 2k个码字集合，称为线性分组码。 码字：一个 n 重的码字可以用矢量来表示： C=(cn－1 ,cn－1 ,…,c1 ,c0 ) (n,k) 线性码：信息位长为 k，码长为 n 的线性码。 编码效率/编码速率/码率/传信率：R=k /n。它说明 了信道的利用效率，R 是衡量码性能的一个重要参数。 返回目录
732致监督方程和一致监督鄉 (1)一致监督方程 (2)举例 (3)一致监督矩阵 (4)一致监督矩阵特性 ash mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码
mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 6/ (1) 一致监督方程 (2) 举 例 (3) 一致监督矩阵 (4) 一致监督矩阵特性
7.3.2-致监督方程和一致监督 (1)一致监督方程 构成码字的方法:编码是给已知信息码组按预定规则添加监督码元 构成码字。 在k个信息码元之后附加r(′=n一k)个监督码元,使每个监督元是 其中某些信息元的模2和。 举例:k=3,=4,构成(7,3)线性分组码。设码字为: (c6,C5,C4,C3,C2,C1,C) c6c3c.为信息元,c3C2cC1c为监督元,每个码元取“0”或“1” 监督元按下面方程组计算:(c3=c6+c cs +c (721) Mol c=c t ash +c mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码
mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 7/ (1) 一致监督方程 构成码字的方法：编码是给已知信息码组按预定规则添加监督码元， 构成码字。 在 k 个信息码元之后附加 r(r=n－k) 个监督码元，使每个监督元是 其中某些信息元的模 2 和。 举例：k=3, r=4，构成 (7,3) 线性分组码。设码字为： (c6 ,c5 ,c4 ,c3 ,c2 ,c1 ,c0 ) c6 ,c5 ,c4为信息元，c3 ,c2 ,c1 ,c0为监督元，每个码元取“0”或“1” 监督元按下面方程组计算： (7.2.1) 0 5 4 1 6 5 2 6 5 4 3 6 4 = + = + = + + = + c c c c c c c c c c c c c
732致监督方程和一致监督鄉 (1)一致监督方程 一致监督方程/一致校验方程:确定信息元得到监 督元规则的一组方程称为监督方程/校验方程。由 于所有码字都按同一规则确定,又称为一致监督 方程/一致校验方程。 为什么叫线性分组码?由于一致监督方程是线性 的,即监督元和信息元之间是线性运算关系,所 以由线性监督方程所确定的分组码是线性分组码。 0(0 ash mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 8/
mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 8/ (1) 一致监督方程 一致监督方程/一致校验方程：确定信息元得到监 督元规则的一组方程称为监督方程/校验方程。由 于所有码字都按同一规则确定，又称为一致监督 方程/一致校验方程。 为什么叫线性分组码？由于一致监督方程是线性 的，即监督元和信息元之间是线性运算关系，所 以由线性监督方程所确定的分组码是线性分组码
732致监督方程和一致监督鄉 (2)举例 信息码组(101),即c6=1,G=0,C4=1 代入(7.2.1)得:c3=0,C2=0,c1=1,c0=1 由信息码组(101)编出的码字为(1010011)。其它7个 码字如表82.1。 表821(7,3)分组码编码表 信息组对应码字 000 0000000 C=C6+cs tC (72.1 001 0011101 c6+c5 010 0100111 Co =c 011 0111010 C+0+c4+c3+0+0+0=0 100 1001110 C6+C5+C4+0+c2+0+0=0 101 1010011 C+Cs+0+0+0+c1+0=0 110 1101001 111 1110100 0+cs+c4+0+0+0+co=0 mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 9/
mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 9/ (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。 + + + + + + = + + + + + + = + + + + + + = + + + + + + = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 4 0 6 5 1 6 5 4 2 6 4 3 c c c c c c c c c c c c c 表 8.2.1 (7,3)分组码编码表 信息组 对应码字 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 1 0 0 (7.2.1) 0 5 4 1 6 5 2 6 5 4 3 6 4 = + = + = + + = + c c c c c c c c c c c c c
732致监督方程和一致监督鄉 (3)一致监督矩阵 为了运算方便,将式(72.1) 011000 监督方程写成矩阵形式,得: 10100 00010 (722) 令C 田将式822)可写成 0100 H·c=0或c·H=0 H 00010 (72.3 C、、07分别表示c, 1000 0的转置矩阵。 ash mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 10/
mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 10/ (3) 一致监督矩阵 为了运算方便，将式(7.2.1) 监督方程写成矩阵形式，得： (7.2.2) 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 1 0 1 1 0 0 0 0 1 2 3 4 5 6 = c c c c c c c (7.2.3) 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 6 5 4 3 2 1 0 = = = H 0 令 C c c c c c c c 将式(8.2.2)可写成： H ·CT=0T 或 C ·HT=0 CT 、HT 、0T 分别表示 C、H、 0 的转置矩阵
732致监督方程和一致监督鄉 (3)一致监督矩阵 系数矩阵H的后四列组成一个(4×4)阶单位子阵,用 表示,H的其余部分用P表示 4×3 所以Hn3=[P4 (82.4) 0(0 ash mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 11/
mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 11/ (3) 一致监督矩阵 系数矩阵 H 的后四列组成一个 (4×4) 阶单位子阵，用 I4 表示，H 的其余部分用 P 表示： (8.2.4) 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 1 (7 3) 4 3 4 4 3 4 H P I P I = = = 所 以