线性分组编码

1、线性分组编码2009年秋内容提要n线性分组码概述n校正子n最小距离n检测和纠错能力n标准阵nBSC上的漏检误码率nSPC，重复码，对偶码线性分组码概述n假设信源输出的信息比特是一串二进制0和1n分组码将其分割为固定长度为k的消息分组（message block）n每个分组记作u，故共有2k个不同的消息分组n编码规则按照一定的规则将输入u映射为二进制n维向量v，nk，v是u的码字或码向量，有2k种不同的码字，这些码字的集合叫做一个分组码nv和u之间是一一对应的n当n和k很大时，编码器要存储这种对应关系代价很高，除非这种对应关系有规律利用（线性？）线性分组码，linear block codesn

2、定义：（n,k）分组码，当且仅当其全部码字构成域GF(2)上所有n维向量组成的向量空间的一个k维子空间时被称为 (n,k)线性码n一个二进制分组码是线性的充要条件是任意两个码字的模2和仍是该分组码中的一个码字（模2和运算封闭）n一个(n,k)线性码C是所有二进制n为向量构成的向量空间Vn的一个k维子空间，故可在Vn中找到k个独立的码字g1,g2,gk-1做为基，用来表示C中任意一个码字线性分组码n用这k个基为行向量构成矩阵Gkxnn (1)n设 是带编码的信息序列，则对应的码字为： G的行生成或张成（span）线性码C，故G称为生成矩阵。线性分组码C的任何k个基都可以获得一个生成矩阵G，故编码

3、器只需要存储一组基就可以依据输入的信息序列得到码字(7,4)线性分组码例子nu=(1 1 0 1)是带编码的信息序列，其对应码字为：具有系统结构的线性分组码n下图显示分组码的系统结构，包括冗余校验部分和消息部分n消息部分包括k个未经改变的原始消息n冗余校验部分包括n-k个奇偶校验位，这些位是信息位的线性和n称为线性系统分组码线性系统分组码 (2)n一个线性系统分组码可由上述kxn的矩阵G来描述，若记k阶单位阵为Ik，则有G=P Ik，则 的码字为： ，v的分量：码字v的右边就是待编码信息序列u码字v的左边就是待编码信息序列u的线性和奇偶校验矩阵n对任何由k个线性独立的行向量组成的kxn矩阵G，

4、都存在一个有n-k个线性独立的行向量组成的(n-k)xn矩阵H，使得G的行空间的任意向量与H的行向量正交，且任何与H正交的向量都在G的行空间内。故：q一个n维向量v是G生成的码C中的一个码字，当且仅当 q码C称为H的零空间，H称为码的奇偶校验矩阵q矩阵H的行向量有2n-k中组合方式，构成(n,n-k)线性码Cd，这个码是G的零空间qCd是C的对偶码，dual codeq一个线性码的奇偶校验矩阵是其对偶码的生成矩阵 奇偶校验矩阵n若(n,k)线性码的生成矩阵公式(2)所示，则其奇偶校验矩阵为公式(3) (3)n令hi表示H的任意一行向量，可以证明公式(2)中的行向量gj与hi的内积为0，即 也就

5、是小结n对任何一个(n,k)线性码C，存在一个生成矩阵Gkxn，其行空间为码Cn存在一个矩阵H(n-k)xn使得当 是，n维向量v是C中的码字校正子与差错检测n考虑一个(n,k)线性码C，其生成矩阵Gkxn，奇偶校验矩阵H，令 表示要通过有噪声信道传输的码字， 表示信道输出端接收到得码字，由于噪声的存在，v和r可能不一样。n向量和 是一个n维向量，e被称为差错向量或错误模式，它直接指出了接收向量r不同于传输码字v的位置，e中分量1表示信道噪声引起的传输错误接收端的处理n n接收端接收到r，但是不知道e，也不知道vn译码器必须先确定r是否包含传输差错n若检测出错误，则采取措施FEC或ARQ校正子

6、 syndromen接收到r之后，译码器计算校正子s： (4)n当且仅当r是码字时，s=0；当且仅当r不是码字时， ；n故当 时，r不是码字，检测出存在错误；s=0时，认为r就是传输码字vn也有可能发生s=0时，传输发生错误，此时错误模式e和某个非零码字相同，此时r是两个码字的和，依然是个码字；这类错误称为漏检错误模式，译码器产生译码差错校正子n依据公式(3)(4)可以得到：n从上述式子看出，校正子s就是接收到的消息位 重新计算校验位和接收到的校验位 的向量和校正子n上式子给出了校正子s和错误模式e的关系，若H的表示如公式(3)所示系统形式，则有校正子为错误模式的线性组合：小结n找到错误模式e

7、，利用v=r+e就可将v视为实际传输的码字，但是错误模式e不容易找到，需要在2k个错误模式（待证明）中找到唯一正确的错误模式例子: (7,4)线性分组码nH如右，设v=(1001011), r=(1001001)n接收到r后，计算校正子s=r HT=(111)n接下来确定差错向量e，由s=e HT，三个线性方程，7个变量ei，共有24个解作为错误模式e，选择具有最少非零分量（即最有可能）的错误模式e=(0000010)，从而得到v=r+e=(1001011)(7,4)线性分组码能纠正7位范围内任意单个差错，即若传输过程中一个码字最多只有一位被噪声改变，则接收端能确定真正的错误模式并纠错分组码的

8、最小距离n刻画分组码的重要参数，最小距离，决定了码检测随机错误和纠正随机错误的能力n设v是二进制n维向量，则v的汉明重量或重量就是值为1的分量的个数，用w(v)表示n若v1和v2是两个二进制n维向量，其汉明距离或距离就是两个不同位数的个数，记作d(v1,v2)n汉明距离满足三角不等式，即n汉明距离满足n给定分组码C，可计算任意两个不同码字之间的汉明距离，这些距离中的最小值称为码C的最小距离dminn另一种描述：n故有结论1：线性分组码的最小距离就是其非零码的最小重量分组码的最小距离分组码的最小距离n(n,k)线性码C，其奇偶校验矩阵H，对任意重量为l的码字，存在H的l个列向量，满足这l个列向量

9、的和为0；反之，若存在H的l个列向量其和为0，则存在重量为l的码字。n证明：记H=h0,h1,hn-1, v=(v0,v1,vn-1)的重量为l， 中有l项非零，其和为0。定理前半部分得证，后半部分略。n不可能有重量为2的码字？n若H中少于d个列向量的和不等于0，则码的最小重量至少为dnH中列向量相加之和为0所需要的最小列向量个数就是码的最小重量分组码的检错能力n设错误模式e的重量，即接收码字和传输码字的距离为d(r,v)=ln分组码C的最小距离为dmin，C中任意两个不同码字至少有dmin处不同n当lt时，存在其它码字较传输码字与接收向量更接近，纠错时会出错分组码的检错和纠错能力n分组码的检

10、错和纠错能力由码的最小距离决定n构造码时尽可能使得最小距离大n可将(n,k)线性分组码记为(n,k,dmin)标准阵和校正子译码n(n,k)线性码C，任何码字通过有噪信道传输，接收向量r必然是GF(2)上2n个n维向量中一个n接收端的任何译码方法都是一种划分规则，该规则将2n个可能的接收向量划分为2k个互不相交的子集D1,D2,D2k,一个码字对应一个子集n若接收向量位于与传输码字对应的子集Di中，则可正确译码n如何构造这种一个子集对应且仅对应一个码字的子集划分方法？标准阵的构造1. 将所有2k个码字排成一行，全零码排在第一个2. 从2n-2k个非码向量构成的集合E中取出一个e2置于全零码正下

11、方，对任意一个码字v，将v+e2置于v的正下方，这样构造出第二行；3. 从E中删除第二行出现的向量，得到更新的E4. 重复步骤2、3，构造第3，4，行，直到集合E为空同一行中任意两个向量之和是C的码字，因为：标准阵的性质n标准阵中同一行任意两个n维向量互不相同，每个n维向量在标准阵中出现且仅出现一次n证明:反证法证明第一部分，若有 则 ，这不可能。第二部分证明（反证）：假设在l和m(l1列，则x=el+vi，接收向量为r=vj+x= el+(vi+vj)=el+vs，接收向量出现在Ds中，r被译码为vs，出现译码错误n故当且仅当错误模式是陪集首时译码是正确的，这些陪集首称为可纠正错误模式每个(

12、n,k)线性分组码有纠正2n-k个错误模式的能力n为使译码差错最小，对给定信道，选择最有可能出现的错误模式作为陪集首。n对于BSC，重量小的错误模式比重量大的错误模式更容易发生n若采用这种方式选择陪集首，则每个陪集中，陪集首的重量最小n在构造标准阵时，在E中选择陪集首时，选择E中重量最小的，故能保证每个陪集中陪集首重量最小n基于标准阵的译码就是最小距离译码，即最大似然译码陪集首的重量分布n令 表示重量为i的陪集首的个数，则称 为陪集首的重量分布n若陪集首的重量分布已知，当且仅当错误模式不是陪集首时，会发生译码错误，故对转移概率为p的BSC信道，误码率为：例子(6,3)线性分组码n陪集首的重量分

13、布为（1 6 1 0 0 0），故nP(E)=1-(1-p)6-6p(1-p)5-p2(1-p)4n当p=10-2时，P(E)=1.37x10-3n线性码能检测出2n-2k中错误模式，但是仅能够纠正2n-k种错误模式，在n较大时，能纠正的错误比能检测到得错误少很多n(n,k,dmin)线性分组码C，所有重量不超过t的n维向量可用作码C的标准阵的陪集首。若所有重量不超过t的n维向量都被用作码C标准阵的陪集首，则至少有一个重量t+1的n维向量无法用于陪集首。其中n证明：令x和y表示重量不大于t的两个n维向量，有w(x+y)=w(x)+w(y)=2tdmin,若x和y在同一陪集中（标准阵的同一行），

14、则x+y就是码字，其重量小于dmin，矛盾，故x和y不在同一陪集中。因此重量不大于t的n维向量均可做陪集首。设v是具有dmin的码字，则存在x和y，满足x+y=v及w(x)+w(y)=w(v)=dmin,若w(y)=t+1，则w(x)=t或t+1，取x为陪集首，则y就不能作为陪集首了，因为x和y在同一陪集中同一陪集的2k个n维向量有相同的校正子，不同的陪集有不同的校正子n证明：标准阵第l行陪集，陪集首为el，则陪集中任意向量vi+el的校正子s=(vi+el)HT=elHT，这表明陪集中任何一个向量的校正子都等于陪集首的校正子。 若有el和ei是不同的两个陪集首，若elHT和eiHT相等，即校

15、正子相同，则有elHT+eiHT=0,即(el+ei)HT=0，说明el+ei是码字，矛盾。故两个不同的陪集中不可能有相同的校正子。查表译码，校正子译码n校正子是n-k维向量，从标准阵中知道有2n-k个不同的校正子，陪集和校正子之间有一一对应关系。n或者说陪集首（可纠正错误模式）和校正子之间有一一对应关系。n故可构建一个由陪集首（可纠正错误模式）和校正子构成的简单译码表，在接收端存储或电路实现之。n接收端译码步骤：1.计算r的校正子s= rHT2.确定于校正子s对应的陪集首el，并假定el就是错误模式3.将接受码字确定为v=el+rn适用于n-k较小例子: (7,4)线性码n若传输码字v=10

16、01011,接收向量r=1001111n计算s= rHT=011n查表得到陪集首为e5=0000100n计算v=r+e5=1001011n译码正确n若v=0000000,r=1000100,出现两个错误，计算s=111，译码结果为0000010，译码错误BSC上漏检误码率n(n,k)线性码C，Ai表示C中重量为i的码字个数，A0,A1,An称为C的重量分布nBSC的漏检率： 漏检的错误模式就是码字，码字中的分量1表示出错，概率为pn线性码C的重量分布与其对偶码Cd的重量分布之间存在的关系可以计算Pu(E)的计算n设B0,B1,Bn是其对偶码Cd的重量分布n分布的多项式表示为： （重量枚举式）n

17、存在恒等式： (5)可选择利用对偶码的重量分布计算码的重量分布BSC上漏检误码率n n将z=p/(1-p)带入码C的重量枚举式，有n即 (6)n由公式(5)(6)， (7)n公式(6)(7)总有一个计算比较简单，可做为选择，例如n-k比k小，则选择公式(7)例子: (7,4)线性码n对偶码如右下所示n对偶码的枚举重量式为： B(z)=1+7z4，利用公式(7)可以得到漏检误码率为：n计算漏检误码率需要计算重量分布， n，k和n-k较大时一般不可能漏检误码率的上界n计算确切的漏检误码率很难，算法是指数阶的n计算上界较容易，存在(n,k)线性分组码C，有Pu(E)=2-(n-k)，证明略n这是一个上界的存在性定理，现有已知的大多数码，不满足上述上界，只有极少数特列被证明满足，很难构造出一个满足这个上界的码单奇偶校验码n单奇偶校验码(SPC)：设u=(u1,u2,uk-1)表示信息序列，校验位p= u1+u2+uk-1，校验位和信息序列一起构成了(k+1,