线性分组编码.ppt

《线性分组编码.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

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

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

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

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