第16讲――线性分组码代数基础_第1页
第16讲――线性分组码代数基础_第2页
第16讲――线性分组码代数基础_第3页
第16讲――线性分组码代数基础_第4页
第16讲――线性分组码代数基础_第5页
已阅读5页,还剩37页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

线性分组码代数基础,第十八讲,一个离散有噪声信道的容量为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)一行乘以非零域元素

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论