第8章线性分组码.ppt

《第8章线性分组码.ppt》由会员分享，可在线阅读，更多相关《第8章线性分组码.ppt（73页珍藏版）》请在第壹文秘上搜索。

1、第8章 线性分组码本章节教学内容、基本要求、重点与难点本章节教学内容、基本要求、重点与难点 1.1.教学内容：教学内容：线性分组码的概念。线性分组码的概念。一致监督方程、一致监督矩阵和线性分组码的生成矩阵。一致监督方程、一致监督矩阵和线性分组码的生成矩阵。线性分组码的最小距离、检错和纠错能力。线性分组码的最小距离、检错和纠错能力。线性分组码的编码方法与译码。线性分组码的编码方法与译码。线性分组码的性能分析。线性分组码的性能分析。汉明码。汉明码。2.2.教学基本要求：教学基本要求：掌握掌握线性分组码线性分组码的编码方法和的编码方法和译码方法译码方法。了解了解一致监督方程和一致监督矩阵的求法。一致

2、监督方程和一致监督矩阵的求法。理解理解最小距离与检错和纠错能力的关系。最小距离与检错和纠错能力的关系。了解汉明码的特点。了解汉明码的特点。3.3.重点与难点：重点与难点：监督矩阵和生成矩阵。监督矩阵和生成矩阵。线性分组码的最小距离、检错和纠错能力。线性分组码的最小距离、检错和纠错能力。译码的性能。译码的性能。线性分组码的编码线性分组码的编码过程分为两步：过程分为两步：p把信息序列按一定长度分成若干信息码组，每组由 k 位组成；p编码器按照预定的线性规则(可由线性方程组规定)，把信息码组变换成 n 重(nk)码字，其中(nk)个附加码元是由信息码元的线性运算产生的。信息码组长信息码组长 k 位，

3、有位，有 2k 个不同的信息码组，则应该有个不同的信息码组，则应该有 2k 个个码字与它们一一对应。码字与它们一一对应。概念概念线性分组码线性分组码：通过预定的线性运算将长为：通过预定的线性运算将长为 k 位的信息码组位的信息码组变换成变换成 n位的码字位的码字(nk)。由。由 2k 个信息码组所编成的个信息码组所编成的 2k个码个码字集合，称为字集合，称为线性分组码线性分组码。码矢码矢：一个：一个 n 重的码字可以用矢量来表示重的码字可以用矢量来表示C=(Cn1,Cn1,C1,C0)所以码字又称为码矢。(n,k)线性码线性码：信息位长为：信息位长为 k，码长为，码长为 n 的线性码。的线性码

4、。编码效率编码效率/编码速率编码速率/码率码率/传信率：传信率：R=k/n。它说明了信道的。它说明了信道的利用效率，利用效率，R是衡量编码性能的一个重要参数是衡量编码性能的一个重要参数。一致监督方程：一致监督方程：编码就是给已知信息码组按预定规则添加监督码元，以编码就是给已知信息码组按预定规则添加监督码元，以构成码字。构成码字。在在 k 个信息码元之后附加个信息码元之后附加 r(r=nk)个监督码元，使每个监督码元，使每个监督元是其中某些信息元的模个监督元是其中某些信息元的模2和。和。例例k=3,r=4构成构成(7,3)线性分组码。设码字为线性分组码。设码字为p(C6,C5,C4,C3,C2,

5、C1,C0)pC6,C5,C4为信息元，C3,C2,C1,C0为监督元，每个码元取“0”或“1”p监督元可按下面方程组计算一致监督方程和一致监督矩阵一致监督方程和一致监督矩阵4505614562463CCCCCCCCCCCCC一致监督方程一致监督方程/一致校验方程：确定信息元得到监督元规则一致校验方程：确定信息元得到监督元规则的一组方程称为监督方程的一组方程称为监督方程/校验方程。由于校验方程。由于所有码字都按同所有码字都按同一规则确定一规则确定，又称为一致监督方程，又称为一致监督方程/一致校验方程。一致校验方程。由于一致监督方程是线性的，即监督元和信息元之间是线由于一致监督方程是线性的，即监

6、督元和信息元之间是线性运算关系，所以由线性监督方程所确定的分组码是线性性运算关系，所以由线性监督方程所确定的分组码是线性分组码分组码。信息码组信息码组(101)，即，即C6=1,C5=0,C4=1由线性方程组得：由线性方程组得：C3=0,C2=0,C1=1,C0=1即信息码组即信息码组(101)编出的码字为编出的码字为 (1010011)。其它。其它7个码字如个码字如表。表。(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

7、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 4505614562463CCCCCCCCCCCCC00000000000000000000451562456346CCCCCCCCCCCCC一致监督矩阵：一致监督矩阵：将监督方程写成矩阵形将监督方程写成矩阵形式，得：式，得：HH C CT=0 0T或或 C C HHT=0 0 C CT、HHT、0 0T分别表示分别表示C C、HH、0 0的转置矩阵。的转置矩阵。1000110010001100101110001101H 00000C00001000110

8、01000110010111000110101234560123456CCCCCCCCCCCCCC令系数矩阵系数矩阵 H H 的后四列组成一个的后四列组成一个(44)阶单位子阵，用阶单位子阵，用 I I4 表示，表示，H H 的其余部分用的其余部分用 P P 表示表示43437434IPH1000010000100001I110011111101P),(所以推广到一般情况：对推广到一般情况：对(n,k)线性分组码，每个码字中的线性分组码，每个码字中的 r(r=nk)个监督元与信息元之间的关系可由下面的线性个监督元与信息元之间的关系可由下面的线性方程组确定方程组确定000022110222212

9、101212111ChChChChChChChChChrnnrnrnnnnnn令系数矩阵为令系数矩阵为 HH，码字行阵列为，码字行阵列为 C C一致监督方程和一致监督矩阵一致监督方程和一致监督矩阵矩阵。线性分组码的一致监督为称或则：),(H0HC0CHCH11110211212222111211knCCChhhhhhhhhrTrnnTrTnnrnnnrnrrnnnr一致监督矩阵特性一致监督矩阵特性:对对H H 各行实行初等变换，将后面各行实行初等变换，将后面 r 列化为单位子阵，于是列化为单位子阵，于是得到下面矩阵得到下面矩阵(行变换所得方程组与原方程组同解行变换所得方程组与原方程组同解)。监

10、督矩阵监督矩阵H H 的标准形式的标准形式：后面：后面 r 列是一单位子阵的监督矩列是一单位子阵的监督矩阵阵HH。H H 阵的每一行都代表一个监督方程，它表示与该行中阵的每一行都代表一个监督方程，它表示与该行中“1”相对应的码元的模相对应的码元的模2和为和为0。100010001H212222111211rnrrkknrpppppppppH H 的标准形式还说明了相应的监督元是由哪些信息元决定的标准形式还说明了相应的监督元是由哪些信息元决定的。例如的。例如(7,3)码的码的H H 阵的第一行为阵的第一行为(1011000)，说明此码的，说明此码的第一个监督元等于第一个和第三个信息元的模第一个监

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

12、意两个码字之和仍是一个码字。：线性码任意两个码字之和仍是一个码字。证明证明：若：若 U U 和和 V V 为线性码的任意两个码字，故有为线性码的任意两个码字，故有HUT=0T，HVT=0T那么 H(U+V)T=H(UT+VT)=HUT+HVT=0T即 U+V 满足监督方程，所以 U+V 一定是一个码字。一个长为一个长为 n 的二元序列可以看作是的二元序列可以看作是GFGF(2)(二元域二元域)上的上的 n 维维线性空间中的一点。长为线性空间中的一点。长为 n 的所有的所有 2n 个矢量集合构成了个矢量集合构成了GFGF(2)上的上的 n 维线性空间维线性空间V Vn。把线性码放入线性空间中进。

13、把线性码放入线性空间中进行研究，将使许多问题简化而比较容易解决。行研究，将使许多问题简化而比较容易解决。(n,k)线性码是线性码是 n 维线性空间维线性空间V Vn中的一个中的一个 k 维子空间维子空间 V Vk。线性分组码的生成矩阵线性分组码的生成矩阵线性分组码的生成矩阵线性分组码的生成矩阵:在由在由(n,k)线性码构成的线性空间线性码构成的线性空间 V Vn 的的 k 维子空间中，一维子空间中，一定存在定存在 k 个线性独立的码字：个线性独立的码字：g1,g2,gk,。码。码 C CI 中其它任中其它任何码字何码字C C都可表示为这都可表示为这 k 个码字的线性组合，即个码字的线性组合，即

14、阶矩阵。是一个是待编码的信息组。写成矩阵形式得其中：nkmmmmmmkimmmmkknkkkkknikkkGmGmgggC1,1,0),2(GFgggC021121021102211GG中每一行中每一行 gi=(gi1,gi2,gin)都是一个码字；都是一个码字；对每一个信息组对每一个信息组mm，由矩阵，由矩阵GG都可以求得都可以求得(n,k)线性码对应线性码对应的码字。的码字。生成矩阵生成矩阵：由于矩阵：由于矩阵 G G 生成了生成了(n,k)线性码，称矩阵线性码，称矩阵 G G 为为(n,k)线性码的生成矩阵。线性码的生成矩阵。(n,k)线性码的每一个码字都是生成矩阵线性码的每一个码字都是

15、生成矩阵 G G 的行矢量的线性的行矢量的线性组合，所以它的组合，所以它的 2k 个码字构成了由个码字构成了由 G G 的行张成的的行张成的 n 维空间维空间V Vn的一个的一个 k 维子空间维子空间 V Vk。knkknnknkggggggggg21222211121121gggG显然：线性系统分组码线性系统分组码:通过行初等变换，将通过行初等变换，将 G G 化为前化为前 k 列是单位子阵的列是单位子阵的标准形式标准形式 knjqmqmqmCkimC,mmmCCCqqqqqqqqqkjjkjkjknikinnkkknnnrkkknkkkknknnk,2,1,2,1G),(),(CQI100

16、010001G02211)(0210211)(21)(22221)(11211得将上式代入线性系统分组码线性系统分组码：用标准生成矩阵：用标准生成矩阵 GGkn 编成的码字，前面编成的码字，前面 k 位为信息数字，后面位为信息数字，后面 r=nk 位为校验字，这种信息数字位为校验字，这种信息数字在前校验数字在后的线性分组码称为线性系统分组码。在前校验数字在后的线性分组码称为线性系统分组码。当生成矩阵当生成矩阵 G G 确定之后，确定之后，(n,k)线性码也就完全被确定了，线性码也就完全被确定了，只要找到码的生成矩阵，编码问题也同样解决了。只要找到码的生成矩阵，编码问题也同样解决了。系统码的码字结构信息数字校验数字例例:(7,4)线性码的生成矩阵为线性码的生成矩阵为)1010011(11010000110100111001010100010101GmC)1010(m1101000011010011100101010001G7441714174，则若 rTrkSrkkSkrTrkTkrrkrkrkTkrrTkrrkkTrkrrkkTSSrkrSrkkSI)Q(HQIGP)Q()P(Q0Q)