信息论第九讲-代数基础与线性分组码课件

[群的定义]：如果一个元素集合G，在其中定义一种运算“*”，并满足下列条件则称为一个群(Group)。a,b,c,e,a-1∈G。自闭性，c=a*b结合律，a*(b*c)=(a*b)*c单位元（恒元），a*e=e*a=a逆元，a*a-1=a-1*a=e如果还满足交换律，a*b=b*a,则称为交换群。5.4代数基础5.4.1群(Group)7/20/20231[定理1]：群G中的单位元是唯一的。[定理2]：群G中任一元素的逆元是唯一的。[有限群]：群中元素的个数称为元素的阶，有限元素的群称为有限群。（m阶有限群）[模运算]：G={0，1}为一个模2加法群，0+0=0，0+1=1，1+0=1，1+1=00是单位元，元素本身是逆元，满足结合律，交换律和自闭性，为一个加法交换群。当p为一个素数，则集合G={1,2,…p-1}在模p乘法下为一个群。7/20/20232例如：p=5为一个素数,G={1,2,3,4}为一个乘法群，*123411234224133314244321全体实数集合为一个普通加法的交换群；全体非零实数集合为一个普通乘法的交换群；7/20/20233[子群]：如果集合G在某种运算*下为一个群，集合H为G中的一个非空子集。若H在运算*下也满足自闭性，结合律，单位元和逆元，则称H为G的一个子群。偶数集合H:{2n}为整数加法群的一个子群。[定理]：如果集合G在运算*下为一个群，H为一个子群，则G中的所有元素都可以由子群H中的元素表示。[单位元]：如果H为G的一个子群，则G中唯一的单位元一定在子群H中。7/20/20234[分元陪集]：利用子群和陪集，可以用子群H的元素表示所有G中的元素。例：设G是整数集合，在普通加法+下为一个交换群，而H为G的一个子群，它由整数m的倍数构成，那么，所有正整数均可用H中的元素表示，且划分为子群H的若干个陪集。H:{nm};n=0,±1,±2,…。例如m=3,则子群H的元素为：H:{0,±3,±6,±9,±12,±15,±18,…}利用分元陪集的方法，用H的元素表示G中的所有元素。7/20/20235将子群H中的元素放在表的第一行，且单位元0放在首位，称为陪集首。将H中没有的，但G中的元素1作为陪集首，放在表的第二行的首位，将陪集首分别与第一行的元素做加法运算，组成的二个陪集。将第一行，第二行中没有的，但在群中有的元素2作为第二个陪集的陪集首，构成第三个陪集。这样，利用分元陪集的方法，可以构成所有G中的元素。陪集103-36-69-9…陪集21+0=11+3=4-27-510-8…陪集32+0=22+3=5-18-411-7…7/20/202365.4.2域(Field)[域的定义]：如果一个元素集合F，在其中定义加法和乘法两种运算，并满足下列条件则称为一个域(Feild)。a,b,c,d,e,a-1∈F。在加法下为一个交换群，即满足自闭性，交换律，结合律，单位元为0，逆元。在乘法下也为一个交换群，即满足非零元素自闭性，交换律，结合律，单位元，逆元。在加法乘法下满足分配律。[有限域]：域中的元素个数m称为域的阶，有限个元素的域称为有限域或叫作伽罗华域，记为GF(m)，GF-GaloisField，7/20/20237[循环群]：如果一个群中存在一个元素，其各次幂可以构成整个群的所有元素，这种群称为循环群。[定理]：有限域GF(q)的非零元素构成一个循环群。设a是GF(q)中的一个非零元素，由于GF(q)的非零元素在乘法下为自闭的，所以a，a2，a3，…也必然是GF(q)中的非零元素，又因为GF(q)为有限元素，所以必然有一个最小的正整数n，使an=1。这个正整数n称为元素a的阶。令a为有限域GF(q)的非零元素，则aq-1=1。令a为有限域GF(q)的非零元素，且n为a的阶，则q-1一定能被n除尽。7/20/20238[本原元]：如果有限域GF(q)中，非零元素a的阶n=q-1，就称a为GF(q)的本原元素。本原元素的各次幂构成有限域FG(q)的所有元素。每个有限域都有其本原元素。例如：素数q=7，模7运算下构成有限域GF(7)，域中元素为{0,1,2,3,4,5,6}，其非零元素集合为{1,2,3,4,5,6}，考虑其中的非零元素a=3，可知：31=3，32=3·3=2，33=32·3=6，34=33·3=4，35=5，36=1

，（3的阶=6）可以看到3的各次幂构成了GF(7)中所有非零元素，所以3的阶n=q-1=6，3为GF(7)的一个本原元。7/20/20239如果取a=4，可知：41=4，42=2，43=1(4的阶=3），44=434=4，45=4243=2，46=4343=1(4q-1=46=1)即元素4的阶为n=3，并且3可以除尽q-1=6。如果取a=5，可知：51=5，52=25=4，53=5251=20=654=535=30=2，55=5154=10=3，56=5254=8=1(2q-1=26=1)即元素5的阶为n=6=q-1，即5也为GF(7)的本原元。可以验证：如果取a=6，可知：61=6，62=36=1(6的阶=2）

，63=6，64=1，65=6，66==1(6q-1=66=1)如果取a=2，可知：21=2，22=4，23=8=1(2的阶=3），24=232=2，25=2223=4，26=2323=1(2q-1=26=1)7/20/2023105.4.3域上多项式[域上多项式]：如果多项式f(x)=f0+f1x+f2x2+…+fnxn的系数取自二元有限域GF(2)，则称f(x)为域FG(2)上的多项式。fi=0或fi=1;[域上多项式计算]：加法：如果f(x)=f0+f1x+f2x2+…+fnxn;g(x)=g0+g1x+g2x2+…+gnxn

则：f(x)+g(x)=(f0+g0)+(f1+g1)x+(f2+g2)x2+…+(fn+gn)xn7/20/202311乘法：如果f(x)=f0+f1x+f2x2+…+fnxn;g(x)=g0+g1x+g2x2+…+gmxm

则：f(x)g(x)=c(x)=c0+c1x+c2x2+…+cn+mxn+m;c0=f0g0c1=f0g1+f1g0……cn+m=fngm7/20/202312除法：如果f(x)=1+x+x4+x5+x6;g(x)=1+x+x3;则f(x)/g(x)的结果可以写作：

其中：q(x)=x3+x2为商式;r(x)=x2+x+1为余式;利用展转相除法（欧几里得除法）可以计算多项式除法。7/20/202313

x3+x+1x6+x5+x4+x+1

x5+x3+x+1

x2+x+1x3+x2x6+x4+x3

x5+x3+x2如果r(x)=0，即f(x)能被g(x)除尽，则称g(x)为f(x)的因式；f(x)为g(x)的倍式。7/20/202314[多项式的模运算]：如果GF(2)上多项式，F(x),N(x),Q(x),R(x)满足：则称在模N(x)条件下，F(x)=R(x)。7/20/202315[不可约多项式]：如果f(x)为GF(2)上的m次多项式，它不能被任何次数小于m，大于0的多项式除尽，则称其为GF(2)上的不可约多项式，既约多项式。f(x)=x3+x+1;f(x)=x4+x+1;均为不可约多项式。GF(2)上的多项式若有偶数项，则一定可被x+1除尽。对于任意m≥1,都存在m次不可约多项式。GF(2)上的任意m次不可约多项式，一定能除尽xn+1，其中n=2m-1。例如：x3+x+1,可以除尽x7+1。7/20/202316

x3+x+1x7+1

x5+x4+1

x4+x3+x2+1x4+x2+x+1x7+x5+x4

x5+x3+x2

x4+x2+x

x3+x+1

x3+x+1

07/20/202317[本原多项式]：如果n=2m-1，f(x)为GF(2)上的m次不可约多项式，且f(x)可除尽xn+1，则称f(x)为本原多项式。不可约多项式不一定是本原多项式，本原多项式一定为不可约的。m次本原多项式是不唯一的。[性质]：对于GF(2)上的多项式f(x)，有[f(x)]2=f(x2)。7/20/2023185.4.4GF(2)上的矢量空间[域上矢量空间]：令[V]是一个矢量集合，在其上定义一个加法运算。令F是一个域，在域中的元素和[V]中的元素之间定义了一个乘法运算。如果集合[V]满足下例条件，称其为域F上的矢量空间（线性空间）。[V]是加法可交换群；F中的任意元素a和[V]中的元素Vi的乘积，aVi是[V]中的元素；满足分配律：a,b∈F;Vi,Vj∈[V];a∙(Vi+Vj)=a∙Vi+a∙Vj;(a+b)∙Vi=a∙Vi+b∙Vi;满足结合律：(a∙b)∙Vi=a∙(b∙Vi);F中的单位元为1，1∙Vi=Vi。[V]中的单位元为[0]矢量。7/20/202319[域上矢量空间的性质]：0为F上的零元，则0∙Vi=[0];c为F上的任意标量，则c∙[0]=0;c为F上的任意标量和[V]中的任意矢量Vi，(-c)∙Vi=c∙(-Vi)=-(c∙Vi);[GF(2)上的矢量空间]：一个有n个分量的序列；(a0,a1,…an-1)其中每个分量是二元域上的元素(ai=0,1)，这个序列称为GF(2)上的n-重。GF(2)上共有2n个n-重。令[Vn]表示这2n个n-重的集合，则可以证明[Vn]是GF(2)上的一个矢量空间。7/20/202320例如：n=5,GF(2)上的5-重矢量空间[V5]由32个矢量组成。(00000),(00001),…(11111)。这个空间中任意两个矢量之和仍然是这个空间中的矢量。GF(2)中的元素0，1乘上空间中的任意矢量仍然是这个空间中的矢量。7/20/202321[V的子空间]：如果[V]是F上的矢量空间，[V]的一个子集也是F上的一个矢量空间，则称[S]为[V]的一个子空间。例如：[V5]上的子集，{(00000),(00111),(11010),(11101)}为一个子空间。7/20/202322[线性组合]：令V1,V2,…Vk是F上矢量空间[V]中的k个矢量。令a1,a2…ak是F中的k个标量。则:a1V1+a2V2+…+akVk称为他们的线性组合。如果：除非a1=a2=…=ak=0,否则a1V1+a2V2+…+akVk≠0；则称V1,V2,…Vk是线性独立的。如果：a1,a2…ak是不都为0，而可以使a1V1+a2V2+…+akVk=0；则称V1,V2,…Vk是线性相关的。7/20/202323[定理]：子空间的构成如V1,V2,…Vk是F上矢量空间V中的k个矢量，则V1,V2,…Vk的所有线性组合构成[V]的一个子空间。7/20/202324[矢量空间的基底与维数]：如果一个矢量空间或子空间中的所有矢量，都是由其中的一组矢量V1,V2,…Vk的线性组合得到，则称这组矢量张成这个矢量空间或子空间。如果这组矢量是线性无关的，则称这组矢量是这个矢量空间的基底。基底中矢量的个数称为矢量空间的维数。7/20/202325例如：GF(2)上的三维矢量空间[V3]的所有8个矢量都可以由(001),(010),(100)这三个矢量的线性组合构成，而且它们是线性无关的，因此它们是[V3]的基底。可以看出：对于GF(2)上的所有n-重组成的矢量空间[Vn]，其基底为{(100…0),(010…0),…(000…1)}。这类基底称为自然基底。一个矢量空间的基底可以有多个，但基底中矢量的个数，即矢量空间的维数是一定的。7/20/202326[内积与矢量正交]：如果两个矢量V=(v1,v2,…vn)，U=(u1,u2,…un)的内积（点积）V∙U=(v1u1+v2u2+…+vnun)=0，则称这两个矢量正交。[零化空间]：如果[S1]和[S2]为矢量空间[V]中的两个子空间，且[S1]中的每个矢量都与[S2]中的每个矢量正交。则称[S1]，[S2]互为零化空间（对偶空间），或称这两个子空间互为正交。7/20/202327[零化空间维数定理]；[Vn]为GF(2)上的n维矢量空间，[S1],[S2]为[Vn]中两个相互正交的子空间，如果[S1]是k维子空间，则[S2]必是一个n-k维子空间。7/20/202328第六章线性分组码6.1汉明码(HammingCode)汉明码是一种基本的线性分组码。6.1.1线性分组码的定义分组码是一种代数编码，它的基本关系一个码字包括独立的信息元和监督元，其监督元与信息元之间是一种代数关系，如果这种代数关系为线性的则称为线性分组码。7/20/202329[m]为编码器的输入，称为信息码元（信息位），它由k位码元组成。[C]为编码器的输出，称为码字矢量，它由n位码元组成，其中有k位信息元，r=n-k位监督元.7/20/202330对于二元编码来说，k位信息码元共有2k个不同组合，根据编码器为一一对应关系，输出的码字矢量也应当有2k种码字。对于长度为n的二元序列来(n-重)说，共有2n个可能的码字矢量，编码器只是在这2n个可能码矢中选择2k个码字，被选中的2k个n-重称为许用码字，其余的2n-2k个码字称为禁用码字，称这2k个码字矢量的集合为(n,k)分组码。7/20/202331[线性分组码定义]：长度为n，有2k个码字的分组码，当且仅当这2k个码字是GF(2)上n维矢量空间（所有n重）的一个k维子空间时，称为(n,k)线性分组码，简称(n,k)码。二元分组码为线性分组码的充要条件为两个码字的模二加也是一个码字。由于k维子空间是在模2加法下运算的，构成了一个加法交换群（阿贝尔群），所以线性分组码也称为群码。7/20/202332线性分组码的一个重要参数为码率(Coderate)：R=k/n;它实际上也就是编码效率或传输效率。如果(n,k)码位信息位没有变化，与信息码元排列相同，并且与监督位分开，称为系统码，否则称为非系统码。7/20/202333编码的数学定义：分组码-BlockCodes:

设A=(a1,a2,…aq)为一个有限集合作为一个码表。Cn=(cn-1,cn-2,……c1,c0)为一个n维矢量空间。而Cn中的一个非空子空间C为一个q元分组码。码率-CodeRate:

如果C∈Cn，包含有M个码字矢量，则记为(n,M)code，q元(n,M)分组码的码率为：7/20/2023346.1.2基本监督矩阵(Paritycheckmatrix)线性分组码可以用GF(2)上的矢量空间的矩阵和GF(2)上多项式来描述，对于汉明码这一类分组码用矩阵（矢量）描述更为方便。7/20/202335[汉明码定义]：对于任意正整数r≥3，存在有下列参数的线性分组码，码长：n=2r-1信息位：k=2r-1-r=n-r监督位：r=n-k最小码距：dmin=3这种码称为狭义汉明码，也称为完备汉明码。7/20/202336这种码的码字矢量为：[C]={cn-1,cn-2,……c1,c0}如果对于系统码，其前k位为信息位，后r位监督位。信息位=[mk-1,mk-2,……,m0]=[cn-1,cn-2,……,cn-k]监督位=[cn-k-1,……c1,c0]7/20/202337由于线性分组码的监督元与信息元之间的线性关系，可以用二元域上的线性方程组描述。记为：cn-k-1=h1,n-1cn-1+h1,n-2cn-2+……+h1,n-kcn-kcn-k-2=h2,n-1cn-1+h2,n-2cn-2+……+h2,n-kcn-k…c0=hr,n-1cn-1+hr,n-2cn-2+……+hr,n-kcn-k

在二元域上，hij:{0,1}7/20/202338整理这个方程组可得：记为：[H][C]T=[0][C]T为[C]的转置，称矩阵[H]为分组码的基本监督矩阵（一致校验矩阵，一致监督矩阵）。

7/20/202339[P]为r×k矩阵，[Ir]为r×r单位阵。可见系统码的基本监督矩阵为：[H]=[PIr]7/20/202340[举例]：(7,4)系统汉明码，n=7,k=4,r=3[C]=[c6,c5,c4,c3,c2,c1,c0]；其中[c6,c5,c4,c3]为信息位，[c2,c1,c0]为监督位。011110010110101101001[H]=P矩阵I矩阵7/20/202341由[H][C]T=[0]可知：监督方程为：c2=c5+c4+c3c1=c6+c4+c3c0=c6+c5+c3根据这个方程组可以进行编码。例如信息码元m=[1011]，则有c2=c5+c4+c3=0+1+1=0c1=c6+c4+c3=1+1+1=1c0=c6+c5+c3=1+0+1=0则汉明码字[C]=[1011010]。7/20/2023426.1.3生成矩阵(Generatormatrix)（1）[生成矩阵的基本形式]：由上面(7,4)汉明码的例子；可以将基本监督方程扩展写为：c6=c6c5=c5c4=c4c3=c3c2=c5+c4+c3c1=c6+c4+c3c0=c6+c5+c37/20/202343用矩阵表示：可以写为：[C]=[m3,m2,m1,m0].[G]

[汉明码字]=[信息码字][生成矩阵][G]称为(7,4)汉明码的生成矩阵。7/20/202344例如：[m]=[1100],[C]=[1100][G]=[1100110]可以看出：(n,k)码的生成矩阵的基本形式为：同样，利用生成矩阵的编码关系为[C]=[m][G]7/20/202345而系统(n,k)码的生成矩阵的基本形式应当为系统码的生成矩阵也称为典型生成矩阵，其基本形式为；[G]=[Ik,Q]，[Q]为k×r矩阵，[Ik]为k×k单位阵。7/20/202346（2）[系统码基本监督矩阵与典型生成矩阵的关系]：从生成矩阵与码字矢量的关系可以看出：[G]矩阵的每一行都是一个码字矢量，分别对应信息码字[10…0],[010…0]…[00…01]的分组码的码字。由于每一行都是码字，把每一行作为一个码字矢量，都应当满足监督矩阵所规定的监督关系，即应当有：[H][G]T=[0]，同时有：[G][H]T=[0]称[H]与[G]为正交矩阵，由[PIr][IkQ]T=[0][P+QT]=[0][P]=[Q]T[Q]=[P]T

P矩阵与Q矩阵互为转置矩阵。7/20/202347（3）[生成矩阵的一般性质]：根据线性分组码的定义，(n,k)线性分组码[C]是二元n重矢量空间中的一个k维子空间，因此，在码字[C]的集合中（2k个码字的码组中），可以找到k个线性独立的码字，g1,g2,…gk;使[C]中的所有码字都是这k个码字的线性组合。7/20/202348[定理]：子空间的构成定理如V1,V2,…Vk是F上矢量空间V中的k个矢量，则V1,V2,…Vk的所有线性组合构成[V]的一个子空间。7/20/202349[矢量空间的基底与维数]：如果一个矢量空间或子空间中的所有矢量，都是由其中的一组矢量V1,V2,…Vk的线性组合得到，则称这组矢量张成这个矢量空间或子空间。如果这组矢量是线性无关的，则称这组矢量是这个矢量空间的基底。基底中矢量的个数称为矢量空间的维数。7/20/202350例如：GF(2)上的三维矢量空间[V3]的所有8个矢量都可以由(001),(010),(100)这三个矢量的线性组合构成，而且它们是线性无关的，因此它们是[V3]的基底。可以看出：对于GF(2)上的所有n-重组成的矢量空间[Vn]，其基底为{(100…0),(010…0),…(000…1)}。这类基底称为自然基底。一个矢量空间的基底可以有多个，但基底中矢量的个数，即矢量空间的维数是一定的。［(101),(110),(111)］也是一个基底。7/20/202351g1=[g1,n-1,g1,n-2,……,g1,0]g2=[g2,n-1,g2,n-2,……,g2,0]…gk=[gk,n-1,gk,n-2,……,gk,0][C]=mn-1g1+mn-2g2+……+mn-kgk其中系数就是信息码字矢量的元素：[mn-1,mn-2……mn-k]=[mk-1,mk-2……m0]7/20/202352根据线性矢量空间的知识，这k个码字矢量就可以张成（生成）这个k维子空间，将这k个矢量组成的矩阵就是(n,k)分组码的生成矩阵。所以生成矩阵是一个k行n列的矩阵。确定(n,k)码的生成矩阵的问题就是确定n-重矢量空间中k维子空间的k个线性无关的码字矢量的问题。也就是寻找子空间基底的问题。(n,k)码的n-重矢量空间中的一个k维子空间的基底可以有多个，因此可以有不同的生成矩阵[G]，但都产生相同的码组。7/20/202353（4）[非系统汉明码]：可以证明非系统汉明码的一致监督矩阵可以用一种简单方法得到。例如：(7,4)非系统汉明码的[H]为

0001111[H]=0110011

1010101其每一例都是二进制数的1，2，3。利用[H][C]T=[0]的基本关系，可以得到非系统形式的汉明码。通过[H]矩阵的列换位，可以将[H]变为系统码的形式。7/20/2023546.1.4校验子与译码(SyndromeMatrixandDecoding)（1）错误图样设发送码字为：[C]=(cn-1,cn-2,……,c0)；由于信道干扰产生差错，反映到接收码字上可以用一个二元矢量[E]表示，这个矢量称为错误图样(errorpatterns)，[E]=(en-1,en-2,……,e0)其中：ei=1表明相应位有错，ei=0表明相应位无错。7/20/202355（2）接收码字矢量这时接收码字可以表示为，

[R]=[C]+[E]=(cn-1+en-1,cn-2+en-2,……c0+e0)译码器的作用就是从接收码字[R]中得到发送码字的估计值，或者说从接收码字中确定错误图样[E]，然后由[C]’=[R]-[E]得到发送码字的估计值，如果估计正确则译码正确，否则译码错误。7/20/202356(3)校验子定义[S]为校验子（伴随式）：[S]=[R][H]T=[C][H]T+[E][H]T=[E][H]T

或[S]T=[H][R]T=[H][C]T+[H][E]T=[H][E]T(本教材的表示方法)[S]=[sr,sr-1,……s1]=[sn-k,sn-k-1,……s1]可以看出：如果校验子矢量[S]≠0，接收码字一定有错误，如果校验子矢量[S]=0，译码器认为接收码字无错误。7/20/202357举例:

(7,4)汉明码的基本监督矩阵[H]为已知，

0111100[H]=1011010

1101001由其得到的汉明码字如下表：000000000000100010010110001000011110011001100001000111101010101010100110011001101110100100100010110011001100111010101010111101110000001100110010111011110010111011010111111111117/20/202358假如接收码字为[R]=[0100101]可以看到：[S]T=[H][R]T=[0]这时表明无差错；如果接收码字有一位差错，[R]=[0110101]；即错误图样[E]=[0010000]；接收码字的第三位错。这时校验子矢量为：7/20/202359可见这时校验子[S]T不为0，译码器认为有错，且正好等于[H]的第三列，表明接收码字的第三位码元错了。这时判断发送码字位[0100101]，译码正确。如果接收码字由两位差错，[R]=[0111101]；即错误图样[E]=[0011000]；接收码字的第三、四位错。这时校验子矢量为：7/20/202360可见这时，校验子矢量不为0，但是如果这时接收机按原来的译码方法，将认为第7位出错。但如果接收机设计为检错系统，当校验子不为0，就认为有错。因为(7,4)汉明码的最小码距为3，其纠错检错能力是正确的。7/20/202361注意：这里告诉我们一个问题，纠错码的选用要小心，要根据信道条件来确定，如果信道较差，而使用的纠错码能力不够，可能使译码错