线性分组编码.

Presentation on theme: "线性分组编码."— Presentation transcript:

1 线性分组编码

2 内容提要 线性分组码概述 校正子 最小距离 检测和纠错能力 标准阵 BSC上的漏检误码率 SPC，重复码，对偶码

3 线性分组码概述 假设信源输出的信息比特是一串二进制0和1 分组码将其分割为固定长度为k的消息分组（message block）
每个分组记作u，故共有2k个不同的消息分组 编码规则按照一定的规则将输入u映射为二进制n维向量v，n>k，v是u的码字或码向量，有2k种不同的码字，这些码字的集合叫做一个分组码 v和u之间是一一对应的 当n和k很大时，编码器要存储这种对应关系代价很高，除非这种对应关系有规律利用（线性？）

4 线性分组码，linear block codes
定义：（n,k）分组码，当且仅当其全部码字构成域GF(2)上所有n维向量组成的向量空间的一个k维子空间时被称为 (n,k)线性码 一个二进制分组码是线性的充要条件是任意两个码字的模2和仍是该分组码中的一个码字（模2和运算封闭） 一个(n,k)线性码C是所有二进制n为向量构成的向量空间Vn的一个k维子空间，故可在Vn中找到k个独立的码字g1,g2,…,gk-1做为基，用来表示C中任意一个码字

5 线性分组码 用这k个基为行向量构成矩阵Gkxn (1) 设 是带编码的信息序列，则对应的码字为：
G的行生成或张成（span）线性码C，故G称为生成矩阵。线性分组码C的任何k个基都可以获得一个生成矩阵G，故编码器只需要存储一组基就可以依据输入的信息序列得到码字 用这k个基为行向量构成矩阵Gkxn (1) 设 是带编码的信息序列，则对应的码字为：

6 (7,4)线性分组码例子 u=( )是带编码的信息序列，其对应码字为：

7 具有系统结构的线性分组码 下图显示分组码的系统结构，包括冗余校验部分和消息部分 消息部分包括k个未经改变的原始消息
冗余校验部分包括n-k个奇偶校验位，这些位是信息位的线性和 称为线性系统分组码

8 码字v的左边就是待编码信息序列u的线性和
线性系统分组码 (2) 一个线性系统分组码可由上述kxn的矩阵G来描述，若记k阶单位阵为Ik，则有G=[P Ik]，则 的码字为： ，v的分量： 码字v的左边就是待编码信息序列u的线性和 码字v的右边就是待编码信息序列u

9 奇偶校验矩阵 对任何由k个线性独立的行向量组成的kxn矩阵G，都存在一个有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的对偶码，dual code 一个线性码的奇偶校验矩阵是其对偶码的生成矩阵

10 奇偶校验矩阵 若(n,k)线性码的生成矩阵公式(2)所示，则其奇偶校验矩阵为公式(3) (3)
令hi表示H的任意一行向量，可以证明公式(2)中的行向量gj与hi的内积为0，即 也就是

11 小结 对任何一个(n,k)线性码C，存在一个生成矩阵Gkxn，其行空间为码C 存在一个矩阵H(n-k)xn使得当 是，n维向量v是C中的码字

12 校正子与差错检测 考虑一个(n,k)线性码C，其生成矩阵Gkxn，奇偶校验矩阵H，令 表示要通过有噪声信道传输的码字， 表示信道输出端接收到得码字，由于噪声的存在，v和r可能不一样。 向量和 是一个n维向量，e被称为差错向量或错误模式，它直接指出了接收向量r不同于传输码字v的位置，e中分量1表示信道噪声引起的传输错误

13 接收端的处理 接收端接收到r，但是不知道e，也不知道v 译码器必须先确定r是否包含传输差错 若检测出错误，则采取措施FEC或ARQ

14 校正子 syndrome 接收到r之后，译码器计算校正子s： (4) 当且仅当r是码字时，s=0；当且仅当r不是码字时， ；
故当 时，r不是码字，检测出存在错误；s=0时，认为r就是传输码字v 也有可能发生s=0时，传输发生错误，此时错误模式e和某个非零码字相同，此时r是两个码字的和，依然是个码字；这类错误称为漏检错误模式，译码器产生译码差错

15 校正子 依据公式(3)(4)可以得到： 从上述式子看出，校正子s就是接收到的消息位 重新计算校验位和接收到的校验位 的向量和

16 校正子 上式子给出了校正子s和错误模式e的关系，若H的表示如公式(3)所示系统形式，则有校正子为错误模式的线性组合：

17 小结 找到错误模式e，利用v=r+e就可将v视为实际传输的码字，但是错误模式e不容易找到，需要在2k个错误模式（待证明）中找到唯一正确的错误模式

18 (7,4)线性分组码能纠正7位范围内任意单个差错，即若传输过程中一个码字最多只有一位被噪声改变，则接收端能确定真正的错误模式并纠错
例子: (7,4)线性分组码 H如右，设v=( ), r=( ) 接收到r后，计算校正子s=r ·HT=(111) 接下来确定差错向量e，由s=e ·HT，三个线性方程，7个变量ei，共有24个解作为错误模式e，选择具有最少非零分量（即最有可能）的错误模式e=( )，从而得到v=r+e=( ) (7,4)线性分组码能纠正7位范围内任意单个差错，即若传输过程中一个码字最多只有一位被噪声改变，则接收端能确定真正的错误模式并纠错

19 分组码的最小距离 刻画分组码的重要参数，最小距离，决定了码检测随机错误和纠正随机错误的能力
设v是二进制n维向量，则v的汉明重量或重量就是值为1的分量的个数，用w(v)表示 若v1和v2是两个二进制n维向量，其汉明距离或距离就是两个不同位数的个数，记作d(v1,v2) 汉明距离满足三角不等式，即 汉明距离满足 给定分组码C，可计算任意两个不同码字之间的汉明距离，这些距离中的最小值称为码C的最小距离dmin

20 分组码的最小距离 另一种描述： 故有结论1：线性分组码的最小距离就是其非零码的最小重量

21 分组码的最小距离 (n,k)线性码C，其奇偶校验矩阵H，对任意重量为l的码字，存在H的l个列向量，满足这l个列向量的和为0；反之，若存在H的l个列向量其和为0，则存在重量为l的码字。 证明：记H=[h0,h1,…,hn-1], v=(v0,v1,…,vn-1)的重量为l， 中有l项非零，其和为0。定理前半部分得证，后半部分略。 不可能有重量为2的码字？？ 若H中少于d个列向量的和不等于0，则码的最小重量至少为d H中列向量相加之和为0所需要的最小列向量个数就是码的最小重量

22 分组码的检错能力 设错误模式e的重量，即接收码字和传输码字的距离为d(r,v)=l
分组码C的最小距离为dmin，C中任意两个不同码字至少有dmin处不同 当l<dmin时，我们说这种错误能检测出来，即之多dmin-1个差错可以检测出来 对于等于或多于dmin个错误的错误模式，无法检测，故称最小距离为dmin的分组码错误检测能力是dmin -1

23 分组码的检错能力 事实上，(n,k)线性分组码除了2k个码字，其它的2n-2k个向量都是错误模式，都可被检测出来

24 分组码的检错能力 (n,k)线性码C，Ai表示C中重量为i的码字个数，A0,A1,…,An称为C的重量分布 求BSC的漏检率：
漏检的错误模式就是非零码字，码字中的分量1表示出错，概率为p

25 分组码的纠错能力 与之相反l>t时，存在其它码字较传输码字与接收向量更接近，纠错时会出错
(n,k)线性分组码C，最小距离为dmin，其随机差错纠正能力为 证明：设v和r分别是传输码字和接受向量，x为任意C中其它码字，有三角不等式成立： 设传输时发生l个错误，即d(v,r)=l,而 故得到 ,若 即任意码字和接收向量的距离大于t 上述证明表明当 时， ，即接收向量与任意码字的距离大于接收向量与传输向量的距离

26 分组码的检错和纠错能力 分组码的检错和纠错能力由码的最小距离决定 构造码时尽可能使得最小距离大
可将(n,k)线性分组码记为(n,k,dmin)

27 标准阵和校正子译码 (n,k)线性码C，任何码字通过有噪信道传输，接收向量r必然是GF(2)上2n个n维向量中一个
接收端的任何译码方法都是一种划分规则，该规则将2n个可能的接收向量划分为2k个互不相交的子集D1,D2,…,D2k,一个码字对应一个子集 若接收向量位于与传输码字对应的子集Di中，则可正确译码 如何构造这种一个子集对应且仅对应一个码字的子集划分方法？

28 同一行中任意两个向量之和是C的码字，因为：
标准阵的构造 将所有2k个码字排成一行，全零码排在第一个 从2n-2k个非码向量构成的集合E中取出一个e2置于全零码正下方，对任意一个码字v，将v+e2置于v的正下方，这样构造出第二行； 从E中删除第二行出现的向量，得到更新的E 重复步骤2、3，构造第3，4，…，行，直到集合E为空 同一行中任意两个向量之和是C的码字，因为：

29 标准阵的性质 标准阵中同一行任意两个n维向量互不相同，每个n维向量在标准阵中出现且仅出现一次 证明:反证法证明第一部分，若有
则 ，这不可能。第二部分证明（反证）：假设在l和m(l<m)行出现了同一个向量，即有 这表明向量em在l行就已经出现，并从E中删除，故不可能在m行做为第一个出现，与标准阵构造矛盾。

30 标准阵与陪集 标准阵有2n-k个互不相交的行，每行2k个元素，一行构成码C的一个陪集(coset)，每个陪集的第一个元素ei称为陪集首或陪集代表元 陪集中任何元素都可以为陪集首，陪集中元素不会改变，改变的只是次序 二进制n维向量构成的2n阶群G，一个(n,k)线性分组码是其2k阶子群C，子群C的所有陪集构成了G的一个划分，如标准阵

31 标准阵：例子(6,3)线性码 令Dj表示标准阵的第j列， vj是码字，ei是陪集首

32 标准阵 码字vj通过有噪信道传输，若信道引起的错误模式是陪集首，则接收向量r在Dj中，此时接收向量可被正确译码为vj
若错误模式没有在陪集首中出现，则译码有误 假设错误模式x在第l行而非陪集首，不妨设在第i>1列，则x=el+vi，接收向量为r=vj+x= el+(vi+vj)=el+vs，接收向量出现在Ds中，r被译码为vs，出现译码错误 故当且仅当错误模式是陪集首时译码是正确的，这些陪集首称为可纠正错误模式

33 每个(n,k)线性分组码有纠正2n-k个错误模式的能力
为使译码差错最小，对给定信道，选择最有可能出现的错误模式作为陪集首。 对于BSC，重量小的错误模式比重量大的错误模式更容易发生 若采用这种方式选择陪集首，则每个陪集中，陪集首的重量最小 在构造标准阵时，在E中选择陪集首时，选择E中重量最小的，故能保证每个陪集中陪集首重量最小 基于标准阵的译码就是最小距离译码，即最大似然译码

34 陪集首的重量分布 令 表示重量为i的陪集首的个数，则称 为陪集首的重量分布
若陪集首的重量分布已知，当且仅当错误模式不是陪集首时，会发生译码错误，故对转移概率为p的BSC信道，误码率为：

35 例子(6,3)线性分组码 陪集首的重量分布为（1 6 1 0 0 0），故 P(E)=1-(1-p)6-6p(1-p)5-p2(1-p)4
当p=10-2时，P(E)=1.37x10-3 线性码能检测出2n-2k中错误模式，但是仅能够纠正2n-k种错误模式，在n较大时，能纠正的错误比能检测到得错误少很多

36 (n,k,dmin)线性分组码C，所有重量不超过t的n维向量可用作码C的标准阵的陪集首。若所有重量不超过t的n维向量都被用作码C标准阵的陪集首，则至少有一个重量t+1的n维向量无法用于陪集首。其中
证明：令x和y表示重量不大于t的两个n维向量，有w(x+y)<=w(x)+w(y)<=2t<dmin,若x和y在同一陪集中（标准阵的同一行），则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在同一陪集中

37 同一陪集的2k个n维向量有相同的校正子，不同的陪集有不同的校正子
证明：标准阵第l行陪集，陪集首为el，则陪集中任意向量vi+el的校正子s=(vi+el)·HT=el·HT，这表明陪集中任何一个向量的校正子都等于陪集首的校正子。 若有el和ei是不同的两个陪集首，若el·HT和ei·HT相等，即校正子相同，则有el·HT+ei·HT=0,即(el+ei)·HT=0，说明el+ei是码字，矛盾。故两个不同的陪集中不可能有相同的校正子。

38 查表译码，校正子译码 校正子是n-k维向量，从标准阵中知道有2n-k个不同的校正子，陪集和校正子之间有一一对应关系。
或者说陪集首（可纠正错误模式）和校正子之间有一一对应关系。 故可构建一个由陪集首（可纠正错误模式）和校正子构成的简单译码表，在接收端存储或电路实现之。 接收端译码步骤： 计算r的校正子s= r·HT 确定于校正子s对应的陪集首el，并假定el就是错误模式 将接受码字确定为v’=el+r

39 例子: (7,4)线性码 若传输码字v=1001011,接收向量r=1001111 计算s= r·HT=011
查表得到陪集首为e5= 计算v’=r+e5= 译码正确 若v= ,r= ,出现两个错误，计算s=111，译码结果为 ，译码错误

40 可选择利用对偶码的重量分布计算码的重量分布
BSC上漏检误码率 (n,k)线性码C，Ai表示C中重量为i的码字个数，A0,A1,…,An称为C的重量分布 BSC的漏检率： 漏检的错误模式就是码字，码字中的分量1表示出错，概率为p 线性码C的重量分布与其对偶码Cd的重量分布之间存在的关系可以计算Pu(E)的计算 设B0,B1,…,Bn是其对偶码Cd的重量分布 分布的多项式表示为： （重量枚举式） 存在恒等式： (5) 可选择利用对偶码的重量分布计算码的重量分布

41 BSC上漏检误码率 将z=p/(1-p)带入码C的重量枚举式，有 即 (6)

42 由公式(5)(6)， (7) 公式(6)(7)总有一个计算比较简单，可做为选择，例如n-k比k小，则选择公式(7)

43 例子: (7,4)线性码 对偶码如右下所示 对偶码的枚举重量式为： B(z)=1+7z4，利用公式(7)可以得到漏检误码率为：
计算漏检误码率需要计算重量分布， n，k和n-k较大时一般不可能

44 漏检误码率的上界 计算确切的漏检误码率很难，算法是指数阶的
计算上界较容易，存在(n,k)线性分组码C，有Pu(E)<=2-(n-k)，证明略 这是一个上界的存在性定理，现有已知的大多数码，不满足上述上界，只有极少数特列被证明满足，很难构造出一个满足这个上界的码

45 单奇偶校验码 单奇偶校验码(SPC)：设u=(u1,u2,…,uk-1)表示信息序列，校验位p= u1+u2+…+uk-1，校验位和信息序列一起构成了(k+1,k)线性码，码字为：v=(p u1,u2,…,uk-1) 若消息的重量是奇数，则p=1，是偶数则p=0，故SPC的重量都是偶数，并且码的最小重量是2，系统形式的码生成矩阵G和H如下： 所有奇数重量的错误模式都是可检测的

46 重复码和自偶码 长度为n的重复码是(n,1)线性分组码，只有两种码字全零和全1，码的生成矩阵G=[111…1]
重复码和单奇偶校验码互为对偶码 若码C=Cd，则码C称为自偶码 码长为偶数 k=n/2，即R=0.5 生成矩阵G同时也是校验矩阵H，有GGT=0 可以证明满足条件GGT=0的(n,n/2)线性码C是自偶码，例如(24,12)格雷码

47 题目： 三种二维码：QR、DM和PDF417 要求： 纠错原理、能力的对比分析；给一份报告
任意选择一个，修改其中的纠错码设计，给出实验结果和分析 要求： 二维码的编解码源代码可以网上寻找，但是纠错码的修改部分，自己做。用任何自己认为更好的纠错码或者自己会实现纠错码都可以 给出你实现纠错码的选择理由以及纠错能力分析，实验测试结果（证明你写的纠错码的能力），注意说服力。 提交时间6月1日之前，研究生门户网站中本课程的链接（主页？）