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

线性分组码代数基础第十八讲信源信源编码信道信源译码信宿噪声信道编码信道译码一个离散有噪声信道的容量为C，当信息速率R≤C时，总可以找到一种编码方法及译码准则，使信道输出端的平均错误译码概率达到任意小；当RC时，则不可能找到一种编码方法及译码准则，使信道输出端的平均错误译码概率达到任意小。信道编码定理Review卷积码(convolutionalcode)分组码(blockcodecode)分组码的各个码段之间是彼此独立的，而卷积码却不同，它不能将数据流划分成为独立的块，前后码段间相互约束，并且这种依赖关系一直递推下去。常见的分组码包括：HammingCode,CyclicCode,BCHCode,Reed-SolommonCode等，我们将主要讨论分组码中最重要的一类——线性分组码。分组码基本概念如果原始信源序列共有M=2L个，对其进行q元等长码的信道编码，码长为N，信道码的所有码字有qN个。编码器将在这qN个可用码字中选择M个码字分别代表原始信源中的M个序列，这M个码字称为“许用码字”，而另外的qN-M个码字称为“禁用码字”。为了实现纠错编码，一定有。这M个许用码字也称为一个码组，或称为码。MqNR=L/N称为编码效率。分组码基本概念0001101110101=c110010=c201110=c311111=c4消息序列码字例题码字α中非零码元的个数称为α的汉明重量（简称重量），记为W(α)。对于在二元码字集合中，码字的汉明重量即为码字中“1”的个数。在一个码组（码字集合）中，任意两个等长码字之间对应位不相同的位数，即如果有d个相对应的码元不同，则称d为这两个码字的汉明距离。分组码基本概念d=0表明为全同码，d=N表明为全异码。它用来定量的描述码字之间的“相似”程度。0001101110101=c110010=c201110=c311111=c4消息序列码字例题若X为一个长度为N的二元码组，令α和β为码组X中的两个不同码字，α=(a0,a1,……aN-1)ai∈{0,1}β=(b0,b1,……bN-1)bi∈{0,1}则α与β的汉明距离为：10),(NiiibadNd0利用码字重量的概念，汉明距离还可以表示为：d(α,β)=W(α⊕β)分组码基本概念在一个码字集合中，任何两个码字之间的汉明距离组成一个元素集合D(α,β),这个集合中的最小值称为这个码的最小汉明距离，简称最小码距，记为dmin。dmin=min{d(α,β)α,β∈Xα≠β}分组码基本概念0001101110101=c110010=c201110=c311111=c4消息序列码字例题d(c1,c2)=3d(c1,c3)=4d(c1,c4)=2d(c2,c3)=3d(c2,c4)=3d(c3,c4)=2dmin=2在一个码字集合中，任何两个码字之间的汉明距离组成一个元素集合D(α,β),这个集合中的最小值称为这个码的最小汉明距离，简称最小码距，记为dmin。dmin=min{d(α,β)α,β∈Xα≠β}它是衡量码的性能的重要参数，dmin小，说明其中有些码字受到干扰后容易变成另外一个码字，译码时就会出错。因此选择码字时，尽量使码的最小汉明距离大一些为好。分组码基本概念0:雪1:雨图6.1.4BSC转移概率1－pb00111－pbpbpb00雪1001110011雨能发现一个错误禁用码组最小码距为2，具有检出1位错码的能力,但不能予以纠正。最小距离与纠检错能力若1→0,0→1，收端无法发现错误000雪010001111000111雨雪最小码距为3，在只有1位错码的情况下,可以判决哪位是错码并予以纠正,可以检出2位或2位以下的错码。100011101110雨最小距离与纠检错能力分组码的最小码距为dmin，则发现l个错误，则要求dmin≥l+1;纠正t个错误，则要求dmin≥2t+1;纠正t个错误，同时发现l（lt）个错误，则dmin≥t+l+1;最小距离与纠检错能力lVUdmin图6.2.4dmin=4,码距和检错能力关系示意图分组码能够发现l个错误的充要条件是码的最小距离为dmin≥l+1最小距离与纠检错能力tVUdmin图6.2.3dmin=5,码距和纠错能力关系示意图最小距离与纠检错能力分组码能够纠正t个错误的充要条件是码的最小距离为dmin≥2t+1分组码能纠t个错误，并能发现l个错误(lt)的充要条件是码的最小距离为dmin≥t+l+1ldmin图6.2.5dmin=5,t=1,l=3时码距和检错能力关系示意图tVU最小距离与纠检错能力dminldmintdmintl图6.2.6最小码距与检纠错能力最小距离与纠检错能力分组码的最小码距为dmin，则发现l个错误，则要求dmin≥l+1;纠正t个错误，则要求dmin≥2t+1;纠正t个错误，同时发现l（lt）个错误，则dmin≥t+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-1∈G，1）封闭性，c=a*b2）结合律，a*(b*c)=(a*b)*c3）单位元，a*e=a4）逆元，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}为一个乘法群，*123411234224133314244321【定义】如果集合G在某种运算*下为一个群，集合H为G中的一个非空子集。若H在运算*下也满足封闭性，结合律，单位元和逆元，则称H为G的一个子群。【例】偶数集合H:{2n}为整数加法群的一个子群。【定理】如果集合G在运算*下为一个群，H为一个子群，则G中的所有元素都可以由子群H中的元素表示。子群【例】集合G={0,1,2,…8}在模9加法下构成一个群，而H={0,3,6}是它的一个子群，对此划分陪集？H036H+1147H+2258陪集103-36-6…陪集21+0=11+3=4-27-5…陪集32+0=22+3=5-18-4…【例】整数加法群，而H={0,±3,±6}是它的一个子群分元陪集划分方法将子群H中的元素放在表的第一行，且单位元放在首位，称为陪集首。将H中没有的，但G中的元素1作为陪集首，放在表的第二行的首位，将陪集首分别与第一行的元素做运算，组成的二个陪集。将第一行，第二行中没有的，但在群中有的元素2作为第三个陪集的陪集首，构成第三个陪集。这样下去，直至G中的所有元素都由子群H中的元素表示出来。H036H+1147H+2258陪集103-36-6…陪集21+0=11+3=4-27-5…陪集32+0=22+3=5-18-4…陪集要么不相交，要么相等陪集首可以任意选择陪集数目＝群元素数目/子群元素数目注：【域的定义】如果一个元素集合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)为一个素域，其运算如下：模7加法+012345600123456112345602234560133456012445601235560123466012345模7乘法.012345600000000101234562024613530362514404152635053164260654321令V是一个矢量集合，在其上定义加法运算。令F是一个域，在域中的元素和V中的元素之间定义乘法运算.如果集合V满足下列条件，称其为域F上的矢量空间（线性空间）。1）V是加法交换群；2）F中的任意元素a和V中的元素vi的乘积avi∈V；3）满足分配律：a,b∈F;vi,vj∈V;a∙(vi+vj)=a∙vi+a∙vj;(a+b)∙vi=a∙vi+b∙vi;4）满足结合律：(a∙b)∙vi=a∙(b∙vi)1∙vi=vi1∈F;域上的矢量空间【例如】实数域上的n重数组全体组成一个线性空间。Ri1-n10a:)a,a,(a【例如】【GF(2)上矢量空间】域GF(2)上的n重数组全体组成一个线性空间。GF(2)上共有2n个n重，令Vn表示这2n个n重的集合，Vn是GF(2)上的一个矢量空间。1,0a:)a,a,(ai1-n10【例】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,a2…ak是F中的k个标量，则a1v1+a2v2+…+akvk称为v1,v2,…vk的线性组合。若除非a1=a2=…=ak=0,否则a1v1+a2v2+…+akvk≠0，则称v1,v2,…vk是线性无关的；若a1,a2…ak不都为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中选取0∙v1+0∙v2+0∙v3=(00000).0∙v1+0∙v2+1∙v3=(11011).这8个矢量构成一个V5的3维子空间0∙v1+1∙v2+0∙v3=(01001).0∙v1+1∙v2+1∙v3=(10010).1∙v1+0∙v2+0∙v3=(10110).1∙v1+0∙v2+1∙v3=(01101).1∙v1+1∙v2+0∙v3=(11111).1∙v1+1∙v2+1∙v3=(00100).进行所有线性组合v1=(10110),v2=(01001),v3=(11011)（注意这里三个矢量相互独立），若线性相关呢？【矢量空间的基底与维数】如果一个矢量空间或子空间中的所有矢量，都是由其中的一组矢量v1,v2,…vk的线性组合得到，则称这组矢量张成这个矢量空间的子空间。如果这组矢量是线性无关的，则称这组矢量是这个矢量空间的基底。基底中矢量的个数称为矢量空间的维数。矢量空间的基底与维