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

第1页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng信息论与编码原理（第八章）──────────────线性分组码第2页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng第8章线性分组码8.1一般概念8.2一致监督方程和一致监督矩阵8.3线性分组码的生成矩阵8.4线性分组码的编码8.5线性分组码的最小距离、检错和纠错能力8.6线性分组码的译码8.7线性分组码的性能8.8汉明码8.9由已知码构造新码的方法8.10GSM的信道编码总体方案8.11线性分组码的码限第3页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng8.1一般概念(1)线性分组码的编码：编码过程分为两步：把信息序列按一定长度分成若干信息码组,每组由k位组成;编码器按照预定的线性规则（可由线性方程组规定），把信息码组变换成n重（nk）码字，其中(n－k)个附加码元是由信息码元的线性运算产生的。(2)线性分组码的码字数：信息码组长k位，有2k个不同的信息码组，有2k个码字与它们一一对应。第4页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng8.1一般概念(3)术语线性分组码：通过预定的线性运算将长为k位的信息码组变换成n重的码字(nk)。由2k个信息码组所编成的2k个码字集合，称为线性分组码。码矢：一个n重的码字可以用矢量来表示：C=(cn－1,cn－1,…,c1,c0)(n,k)线性码：信息位长为k，码长为n的线性码。编码效率/编码速率/码率/传信率：R=k/n。它说明了信道的利用效率，R是衡量码性能的一个重要参数。返回目录第5页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng8.2一致监督方程和一致监督矩阵(1)一致监督方程(2)举例(3)一致监督矩阵(4)一致监督矩阵特性第6页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng8.2一致监督方程和一致监督矩阵(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”监督元按下面方程组计算：)1.2.7(4505614562463ccccccccccccc第7页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng8.2一致监督方程和一致监督矩阵(1)一致监督方程一致监督方程/一致校验方程：确定信息元得到监督元规则的一组方程称为监督方程/校验方程。由于所有码字都按同一规则确定，又称为一致监督方程/一致校验方程。为什么叫线性分组码？由于一致监督方程是线性的，即监督元和信息元之间是线性运算关系，所以由线性监督方程所确定的分组码是线性分组码。返回目录第8页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng8.2一致监督方程和一致监督矩阵(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表8.2.1(7,3)分组码编码表信息组对应码字00000000000010011101010010011101101110101001001110101101001111011010011111110100)1.2.8(4505614562463ccccccccccccc返回目录第9页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng8.2一致监督方程和一致监督矩阵(3)一致监督矩阵为了运算方便，将式(7.2.1)监督方程写成矩阵形式，得：)2.2.8(000010001100100011001011100011010123456ccccccc)3.2.8(100011001000110010111000110100000123456H0Cccccccc令将式(8.2.2)可写成：H·CT=0T或C·HT=0CT、HT、0T分别表示C、H、0的转置矩阵。第10页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng)4.2.8(1000010000100001110011111101434)37(434IPHIP,所以8.2一致监督方程和一致监督矩阵(3)一致监督矩阵系数矩阵H的后四列组成一个(4×4)阶单位子阵，用I4表示，H的其余部分用P表示：第11页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng8.2一致监督方程和一致监督矩阵(3)一致监督矩阵推广到一般情况：对(n,k)线性分组码，每个码字中的r(r=n－k)个监督元与信息元之间的关系可由下面的线性方程组确定：)5.2.8(000022110222212101212111chchchchchchchchchrnnrnrnnnnnn返回第12页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng8.2一致监督方程和一致监督矩阵(3)一致监督矩阵令上式的系数矩阵为H，码字行阵列为C：返回目录0211cccnnnC)6.2.8(212222111211rnrrnnnrhhhhhhhhhH矩阵，简称监督矩阵。线性分组码的一致监督为称或可写成：式),()7.2.8()()()()5.2.7(1111knrTnrnTrTnnrH0HC0CH第13页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng(4)一致监督矩阵特性对H各行实行初等变换，将后面r列化为单位子阵，得到下面矩阵，行变换所得方程组与原方程组同解。监督矩阵H的标准形式：后面r列是一单位子阵的监督矩阵H。)8.2.8(100010001212222111211rnrrkknrpppppppppH8.2一致监督方程和一致监督矩阵第14页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng(4)一致监督矩阵特性H标准形式的特性H阵的每一行都代表一个监督方程，它表示与该行中“1”相对应的码元的模2和为0。H的标准形式表明了相应的监督元是由哪些信息元决定的。例如(7,3)码的H阵的第一行为(1011000)，说明第一个监督元等于第一个和第三个信息元的模2和，依此类推。H阵的r行代表了r个监督方程，由H所确定的码字有r个监督元。为了得到确定的码，r个监督方程（或H阵的r行）必须是线性独立的，这要求H阵的秩为r。若把H阵化成标准形式，只要检查单位子阵的秩，就能方便地确定H阵本身的秩。8.2一致监督方程和一致监督矩阵参见方程返回目录第15页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng8.3线性分组码的生成矩阵(1)线性码的封闭性(2)线性分组码的生成矩阵(3)生成矩阵与一致监督矩阵的关系(4)对偶码第16页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng(1)线性码的封闭性线性码的封闭性：线性码任意两个码字之和仍是一个码字。定理7.3.1：设二元线性分组码CI(CI表示码字集合)是由监督矩阵H所定义的，若U和V为其中的任意两个码字，则U+V也是CI中的一个码字.[证明]：由于U和V是码CI中的两个码字，故有：HUT=0THVT=0T，那么H(U+V)T=H(UT+VT)=HUT+HVT=0T即U+V满足监督方程，所以U+V一定是一个码字。一个长为n的二元序列可以看作是GF(2)(二元域)上的n维线性空间中的一点。所有2n个矢量集合构成了GF(2)上的n维线性空间Vn。把线性码放入线性空间中进行研究，将使许多问题简化而比较容易解决。(n,k)线性码是n维线性空间Vn中的一个k维子空间Vk。8.3线性分组码的生成矩阵返回目录第17页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng(2)线性分组码的生成矩阵生成矩阵的来由：在由(n,k)线性码构成的线性空间Vn的k维子空间中，一定存在k个线性独立的码字：g1,g2,…,gk。码CI中其它任何码字C都可以表为这k个码字的一种线性组合，即：8.3线性分组码的生成矩阵。写成矩阵形式得：）（1,,1,0),2(1.3.802211kiGFmmmmikkkgggC阶矩阵。──是一个──待编码的信息组nkmmmnkkkGm021)2.3.8(,1210211nkkkkknmmmGmgggC第18页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng(2)线性分组码的生成矩阵生成矩阵定义：由于矩阵G生成了(n,k)线性码，称矩阵G为(n,k)线性码的生成矩阵。8.3线性分组码的生成矩阵)3.3.8(21222211121121knkknnknkggggggggggggG第19页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng(2)线性分组码的生成矩阵生成矩阵G的特性G中每一行gi=(gi1,gi2,…,gin)都是一个码字；对每一个信息组m，由矩阵G都可以求得(n,k)线性码对应的码字。(n,k)线性码的每一个码字都是生成矩阵G的行矢量的线性组合，所以它的2k个码字构成了由G的行张成的n维空间的一个k维子空间Vk。8.3线性分组码的生成矩阵第20页2020/1/7DepartmentofElectronicsandInformation,NCUTSongPeng)4.3.8(100010001)(21)(22221)(11211rkkknkkkknknnkqqqqqqqqqQIG(2)线性分组码的生成矩阵线性系统分组码