,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三讲,线性码与线性分组码,编码与译码,对 二进制(,n,k),码，信息数量（或合法码字数）为2,k,，可用编码空间的点数为2,n,个。,任一种2,k,信息集合到二进制序列集合(2,n,)的映射都是一种,(,n,k),码。因此总共可能的编码方案有 种。如，共有10,29,种(100,50)码。,译码运算量：如果直接用最大似然序列译码，对一般性的编码而言，正比于n,*,2,k,，对,(100,50)码，则为10,17,。几乎是不可能译码的。,为什么要引入线性码,发现或构造好码是信道编码研究的主要问题,编码方案太多，以至全局搜索是不可能的,现实的做法是对编码方案加以一定的约束，在一个子集中寻找局部最优,这种约束即要能包含尽可能好的码，又要便于分析，便于译码,目前对线性系统的研究远比非线性系统充分,线性码的定义,码字集中的元之间的任意线性组合仍是合法码字，即对线性组合运算封闭的码字集，称为线性码,因此，为了构成线性空间，必须首先定义运算,群,定义了一种运算的集合,群,运算封闭,有恒等元,有逆元,满足结合律,交换群,满足交换律的群,环,定义了两种运算的集合,按第一种运算（不妨称为加法）构成交换群,第二种运算（不妨称为乘法）满足以下条件,封闭性,结合律,与加法间满足分配律,域,一种特殊的环,乘法有恒等元（称为1元），且除了加法的恒等元（称为0元）以外有逆的环,除0元外，对乘法构成交换群,无限域和有限域,有理数、实数和复数都是无限域,信道编码中用到的是有限域，,GF(,q,),两者在空间意义上有很强的可类比性,子群与陪集,就给定群,G,所定义的（加法）运算封闭的非空子集,H,，,称,H,为,G,的子群,G,中任一元,g,与,H,相加得到的子集称为,H,的陪集,举例,陪集不相交,陪集首,商集,整数群的子群,m,的所有倍数,剩余类,线性空间、,线性码与线性分组码,利用线性空间中的子空间作为许用码字的编码称线性码,当线性空间为有限维空间时即为线性分组码,GF(,q,),上的,n,维线性空间,V,n,中的一个,k,维子空间,V,n,k,称为(,n,k,),线性分组码,线性分组码的特点,全零序列是许用码字,与任一码字的距离谱都相同,只须考虑重量谱,自由距就是最小码重量,平均差错概率就是当发全零序列时的条件差错概率：,P,e,=,x1,P(,x,1,)P(e|,x,1,)=P(e|,全零,),码的球半径和覆盖半径,码空间中以许用码字为中心半径相等的互不相交的球，其最大半径称为码的球半径,s,(,C,)，,对自由距为,d,的码，球半径为,s,(,C,)=,(,d,-1)/2,可以覆盖整个码空间的以许用码字为中心半径相等的球，其最小半径称为码的覆盖半径,t,(,C,)，,显然球半径不大于覆盖半径,当相等时称为完备码，在,k,和,d,相不变的码中,n,最小,当给定编码参数,n,和,k,时，覆盖半径越小码距就可以越大,线性码的矢量与矩阵表示,(,n,k,),线性分组码是,GF(q),上的,n,维线性空间中,k,个线性无关的向量,c,1,c,2,c,k,张成的,对码空间中任一个码字,C,0,可表示为,将所有矢量写成行向量的形式：,c,0,=,d,*,G,生成矩阵,校验矩阵,若,C,是,n,维线性空间,的一个,k,维子空间，则必存在一个,的,n-k,维子空间,H,，,它与,C,互为零空间。即,C,H,，,或,C,H,=,。,中任一矢量,r,是许用码字的充要条件是,校验矩阵,对偶码,用校验矩阵,H,中行矢量张成的子空间是一个(,n,n-k,),线性分组码，它与码,C,互为对偶码,自由距与校验矩阵,校验矩阵的秩为,d,f,-1,例：,纠一个错的码设计,自由距至少为3,校验矩阵的秩至少为2，即任两个列矢量不同,当冗余位数,m,固定时，最多的非零列矢量个数为,2,m,-1,最高效率为(2,m,-1，2,m,-1-,m,，3),码，,称为汉明码，是完备码,汉明码的对偶码为2(2,m,-1，,m,，2,m,-1,),码，,等价于,m,序列，又称极长码，如果用BPSK，并看成,2,m,进制调制时，是一种自相关性最好的调制方式,我们能得到多大的自由距？,在大部分情况下，自由距是码设计的首选目标,它代表了渐近性能,大部分分组译码算法的译码能力也限于自由距,普洛特金限（,Plotkin,）,自由距小于平均距：,d,nq,k,-1,(,q,-1)/(,q,k,-1),或,k,/,n,1-2,d,/,n,汉明限，球包限：,k,/,n,1-,H,2,(,d,/2,n,),沃尔沙莫夫-吉尔伯特（,V-G）,限，,H,阵的秩与距离的关系：,k,/,n,1-,H,2,(,d,/,n,),其中,H,2,(,x,)=-,x,log,2,x,(1-,x,)log,2,(1-,x,),最大的自由距存在区间,线性分组码译码的基本方法,码,C,作为一个子群，它的每一个陪集在码,C,的正交空间,H,中的投影是一个点，而不同的陪集投影不同。,每一个陪集有一个最小码重，作为陪集首，代表最可能的错误图案。,这就引出了伴随式译码：,s,=,rH,T,，,将,s,与最可能的,e,建一张表，即可通过查表法实现译码。,小结：引入线性码的好处,简化了分析：距离谱变成了重量谱,简化了译码：,随机分组码译码需要2,k,次长为,n,的距离计算及比较,线性分组码译码需要,n-k,次长为,n,的矢量内积和一张大小为2,n-k,宽度为,n,的表,说明约束起了作用，但还不够，需要进一步引入其它约束,