第16讲――线性分组码代数基础

线性分组码代数基础,第十八讲,一个离散有噪声信道的容量为C，当信息速率RC时，总可以找到一种编码方法及译码准则，使信道输出端的平均错误译码概率达到任意小；当RC时，则不可能找到一种编码方法及译码准则，使信道输出端的平均错误译码概率达到任意小。,信道编码定理,卷积码(convolutionalcode),分组码(blockcodecode),分组码的各个码段之间是彼此独立的，而卷积码却不同，它不能将数据流划分成为独立的块，前后码段间相互约束，并且这种依赖关系一直递推下去。,常见的分组码包括：HammingCode,CyclicCode,BCHCode,Reed-SolommonCode等，我们将主要讨论分组码中最重要的一类线性分组码。,分组码基本概念,如果原始信源序列共有M=2L个，对其进行q元等长码的信道编码，码长为N，信道码的所有码字有qN个。编码器将在这qN个可用码字中选择M个码字分别代表原始信源中的M个序列，这M个码字称为“许用码字”，而另外的qN-M个码字称为“禁用码字”。,为了实现纠错编码，一定有。这M个许用码字也称为一个码组，或称为码。,R=L/N称为编码效率。,分组码基本概念,例题,码字中非零码元的个数称为的汉明重量（简称重量），记为W()。对于在二元码字集合中，码字的汉明重量即为码字中“1”的个数。,在一个码组（码字集合）中，任意两个等长码字之间对应位不相同的位数，即如果有d个相对应的码元不同，则称d为这两个码字的汉明距离。,分组码基本概念,d=0表明为全同码，d=N表明为全异码。它用来定量的描述码字之间的“相似”程度。,例题,若X为一个长度为N的二元码组，令和为码组X中的两个不同码字，,=(a0,a1,aN-1)ai0,1,=(b0,b1,bN-1)bi0,1,则与的汉明距离为：,利用码字重量的概念，汉明距离还可以表示为：,d(,)=W(),分组码基本概念,在一个码字集合中，任何两个码字之间的汉明距离组成一个元素集合D(,),这个集合中的最小值称为这个码的最小汉明距离，简称最小码距，记为dmin。,dmin=mind(,),X,分组码基本概念,例题,d(c1,c2)=3,d(c1,c3)=4,d(c1,c4)=2,d(c2,c3)=3,d(c2,c4)=3,d(c3,c4)=2,dmin=2,在一个码字集合中，任何两个码字之间的汉明距离组成一个元素集合D(,),这个集合中的最小值称为这个码的最小汉明距离，简称最小码距，记为dmin。,dmin=mind(,),X,它是衡量码的性能的重要参数，dmin小，说明其中有些码字受到干扰后容易变成另外一个码字，译码时就会出错。因此选择码字时，尽量使码的最小汉明距离大一些为好。,分组码基本概念,0:雪1:雨,00雪,10,01,11,00,11雨,能发现一个错误,禁用码组,最小码距为2，具有检出1位错码的能力,但不能予以纠正。,最小距离与纠检错能力,若10,01，收端无法发现错误,000雪,010,001,111,000,111雨,雪,最小码距为3，在只有1位错码的情况下,可以判决哪位是错码并予以纠正,可以检出2位或2位以下的错码。,100,011,101,110,雨,最小距离与纠检错能力,分组码的最小码距为dmin，则,发现l个错误，则要求dminl+1;,纠正t个错误，则要求dmin2t+1;,纠正t个错误，同时发现l（lt）个错误，则dmint+l+1;,最小距离与纠检错能力,分组码能够发现l个错误的充要条件是码的最小距离为dminl+1,最小距离与纠检错能力,最小距离与纠检错能力,分组码能够纠正t个错误的充要条件是码的最小距离为dmin2t+1,分组码能纠t个错误，并能发现l个错误(lt)的充要条件是码的最小距离为dmint+l+1,最小距离与纠检错能力,最小距离与纠检错能力,分组码的最小码距为dmin，则,发现l个错误，则要求dminl+1;,纠正t个错误，则要求dmin2t+1;,纠正t个错误，同时发现l（lt）个错误，则dmint+l+1;,【例如】,dmin=1：,dmin=2：,dmin=3：,dmin=4：,最小距离与纠检错能力,无纠检错能力,检1位错,纠1位错（或检两位错）,纠1位，同时检2位（或纠1位，或检3位）,【例】重复码,重复码是一种最简单的纠错码。在实际系统重有较广泛的应用。例如将0编为000，1编为111。,它的最小码距为3，可以纠1个错，或者检2个错;,编码效率相当于k=1,n=3，=k/n=1/3。,例题,【定义】,如果一个元素集合G，在其中定义一种运算“*”，若满足下列条件则称为一个群。若a,b,c,e,a-1G，,1）封闭性，c=a*b,2）结合律，a*(b*c)=(a*b)*c,3）单位元，a*e=a,4）逆元，a*a-1=e,如果还满足交换律，a*b=b*a,则称为交换群。,群(Group),有限元素的群称为有限群，群中元素的个数称为阶（m阶有限群）。,【例1】：G=0,1为一个模2加法群，因为0+0=0,0+1=1，1+0=1,1+1=0，由此可知：0是单位元，本身是逆元，满足结合律，交换律和封闭性，因而为一个加法交换群。,【例2】：当p为一个素数，则集合G=1,2,p-1在模p乘法下为一个群。如p=5,G=1,2,3,4为一个乘法群，,【定义】,如果集合G在某种运算*下为一个群，集合H为G中的一个非空子集。若H在运算*下也满足封闭性，结合律，单位元和逆元，则称H为G的一个子群。,【例】偶数集合H:2n为整数加法群的一个子群。,【定理】,如果集合G在运算*下为一个群，H为一个子群，则G中的所有元素都可以由子群H中的元素表示。,子群,【例】集合G=0,1,2,8在模9加法下构成一个群，而H=0,3,6是它的一个子群，对此划分陪集？,【例】整数加法群，而H=0,3,6是它的一个子群,分元陪集划分方法,将子群H中的元素放在表的第一行，且单位元放在首位，称为陪集首。,将H中没有的，但G中的元素1作为陪集首，放在表的第二行的首位，将陪集首分别与第一行的元素做运算，组成的二个陪集。,将第一行，第二行中没有的，但在群中有的元素2作为第三个陪集的陪集首，构成第三个陪集。,这样下去，直至G中的所有元素都由子群H中的元素表示出来。,陪集要么不相交，要么相等,陪集首可以任意选择,陪集数目群元素数目/子群元素数目,注：,【域的定义】,如果一个元素集合F，在其中定义加法和乘法两种运算，若满足下列条件则称为一个域(Feild)。,1）在加法下为一个交换群，即满足封闭性，交换律，结合律，单位元为0，逆元。,2）在乘法下为一个交换群，满足非零元素封闭性，交换律，结合律，单位元为1，逆元。,3）在加法、乘法下满足分配律。,域(Field),【有限域定义】,域中元素个数m称为阶，有限个元素的域称为有限域或伽罗华域（GF-GaloisField），记为GF(m)。,例如：集合0,1在模二加法和乘法下构成一个二元有限域GF(2)。一个域中最少包含加法单位元和乘法单位元两个元素，否则不能构成域。,【素域定义】,如果p为一个素数，则正整数集合0,1,2,p-1，在模p加法和乘法下构成阶数为p的域，称为素域，记为GF(p)。,【例】GF(7)为一个素域，其运算如下：,令V是一个矢量集合，在其上定义加法运算。令F是一个域，在域中的元素和V中的元素之间定义乘法运算.如果集合V满足下列条件，称其为域F上的矢量空间（线性空间）。,1）V是加法交换群；,2）F中的任意元素a和V中的元素vi的乘积aviV；,3）满足分配律：a,bF;vi,vjV;,a(vi+vj)=avi+avj;(a+b)vi=avi+bvi;,4）满足结合律：(ab)vi=a(bvi)1vi=vi1F;,域上的矢量空间,【例如】实数域上的n重数组全体组成一个线性空间。,【例如】【GF(2)上矢量空间】,域GF(2)上的n重数组全体组成一个线性空间。GF(2)上共有2n个n重，令Vn表示这2n个n重的集合，Vn是GF(2)上的一个矢量空间。,【例】n=5,GF(2)上的5重矢量空间V5由32个矢量组成，即(00000),(00001),(11111)。这个空间中任意两个矢量之和仍然是这个空间中的矢量。GF(2)中的元素0,1乘以空间中的任意矢量仍然是这个空间中的矢量。,如果V是F上的矢量空间，V的一个子集S也是F上的一个矢量空间，则称S为V的一个子空间。,由定义，判断子空间只需要检验：集合是否构成交换群；数乘是否封闭两个条件即可。,【例】：V5上的子集，(00000),(00111),(11010),(11101),为一个子空间。,子空间,令v1,v2,vk是F上矢量空间V中的k个矢量，令a1,a2ak是F中的k个标量，则a1v1+a2v2+akvk称为v1,v2,vk的线性组合。,若除非a1=a2=ak=0,否则a1v1+a2v2+akvk0，则称v1,v2,vk是线性无关的；,若a1,a2ak不都为0，而可使a1v1+a2v2+akvk=0，则称v1,v2,vk是线性相关的。,【例】(010)(100)(110)线性相关，因为1*(010)+1*(100)+1*(110)=(000)，而(010)(100)(010)线性无关。,线性组合,【定理】,如v1,v2,vk是F上矢量空间V中的k个矢量，则v1,v2,vk的所有线性组合构成V的一个子空间。,矢量空间的基底与维数,【例】：V5中选取,0v1+0v2+0v3=(00000).0v1+0v2+1v3=(11011).,这8个矢量构成一个V5的3维子空间,0v1+1v2+0v3=(01001).0v1+1v2+1v3=(10010).,1v1+0v2+0v3=(10110).1v1+0v2+1v3=(01101).,1v1+1v2+0v3=(11111).1v1+1v2+1v3=(00100).,进行所有线性组合,v1=(10110),v2=(01001),v3=(11011),（注意这里三个矢量相互独立），若线性相关呢？,【矢量空间的基底与维数】,如果一个矢量空间或子空间中的所有矢量，都是由其中的一组矢量v1,v2,vk的线性组合得到，则称这组矢量张成这个矢量空间的子空间。如果这组矢量是线性无关的，则称这组矢量是这个矢量空间的基底。基底中矢量的个数称为矢量空间的维数。,矢量空间的基底与维数,【例1】：GF(2)上的V3的所有8个矢量都可以由(001),(010),(100)这三个矢量的线性组合构成，而且它们是线性无关的，因此它们是GF(2)上的三维矢量空间V3的基底。(001),(010),(101)同样也能张成V3，而(010)(100)(110)则不能。,【例2】：对于GF(2)上的所有n-重组成的矢量空间Vn，其基底为(1000),(0100),(0001)。这类基底称为自然基底。,一个矢量空间的基底可以有多个，但基底中矢量的个数，即矢量空间的维数是一定的。,【矢量正交】,如果两个矢量v=(v1,v2,vn)，u=(u1,u2,un)的内积vu=v1u1+v2u2+vnun=0，则称这两个矢量正交。,【零化空间】,如果S1和S2为矢量空间V中的两个子空间，且S1中的每个矢量都与S2中的每个矢量正交，则称S1S2互为零化空间（对偶空间），或称这两个子空间互为正交。,【零化空间维数定理】,Vn为GF(2)上的n维矢量空间，S1,S2为Vn中两个相互正交的子空间，如果S1是k维子空间，则S2必是一个n-k维子空间。,零化空间,【例】：V5中，,v1=(10110),v2=(01001),v3=(11011)为,0v1+0v2+0v3=(00000).0v1+0v2+1v3=(11011).,这8个矢量构成一个V5的3维子空间S3，（由三个相互独立的矢量张成的子空间）。,0v1+1v2+0v3=(01001).0v1+1v2+1v3=(10010).,1v1+0v2+0v3=(10110).1v1+0v2+1v3=(01101).,1v1+1v2+0v3=(11111).1v1+1v2+1v3=(00100).,线性无关的，其线性组合为：,与这8个矢量都正交的矢量由下面4个矢量组成(00000),(10010),(01001),(11011),而它们是由v1=(10010),v2=(01001)张成的。这4个矢量构成一个V5的2维子空间S2，可见满足零化空间维数关系的定理。,mn矩阵M的行（列）空间是以矩阵M的行作为矢量所张成的空间，它是m(n)维矢量空间中的一个子空间。,行空间,在编码理论中，用矩阵表示矢量和矢量空间是方便的,【行空间定义】,行（列）空间的维数等于行（列）空间中线性无关的最大行数，也等于矩阵的行（列）秩。,初等行变换,1）任何两行交换位置；2）任何行乘以非零域元素；3）一行乘以非零域元素