第三章 线性分组码PPT.ppt

第三章 线性分组码 要求掌握的内容 线性分组码的定义及性质 码的一致校验矩阵和生成矩阵 码的伴随式、标准阵列及译码 汉明码及译码 第一节 线性分组码基本概念 线性分组码定义 生成矩阵 校验矩阵 对偶码、系统码和缩短码 编码与译码 对 二进制(n, k)码，信息数量（或合法码字数）为2k，可用编码空间的点数为2n个。 任一种2k信息集合到二进制序列集合(2n)的映射都是一种(n, k)码。因此总共可能的编码方案有 种。如，共有1029种(100,50)码。 译码运算量：如果直接用最大似然序列译码，对一般性的编码而言，正比于n* 2k ，对(100,50)码，则为1017。几乎是不可能译码的。 为什么要引入线性码 发现或构造好码是信道编码研究的主要问题 编码方案太多，以至全局有哪些信誉好的足球投注网站是不可能的 现实的做法是对编码方案加以一定的约束，在一个子集中寻找局部最优 这种约束即要能包含尽可能好的码，又要便于分析，便于译码 目前对线性系统的研究远比非线性系统充分 一、线性分组码基本概念(P52-54) 码的最小距离 在大部分情况下，码的最小距离是码设计的首选目标 它代表了渐近性能 大部分分组译码算法的译码能力也限于最小距离 线性分组码的特点 全零序列是许用码字 与任一码字的距离谱都相同 只须考虑重量谱 自由距就是最小码重量 平均差错概率就是当发全零序列时的条件差错概率：Pe=?x1P(x1)P(e|x1)= P(e|全零) 三、码的生成矩阵(P56) 注： 生成矩阵G中的每一行都是一个码字 任意k个线性独立的码字都可以作为生成矩阵 给定一个[n,k,d]线性分组码，其生成矩阵可有多个 四、码的校验矩阵(P54) ——从线性方程组的角度描述分组码 五、几个概念(P57-58) ——对偶码、系统码和缩短码 第二节 线性分组码的译码 伴随式 汉明码 标准阵列 一、伴随式(P59) Singleton限 (n, k, d)线性分组码的最大可能的最小距离小于等于n-k+1, 即d≤n-k+1 若系统码的最小距离d=n-k+1，则此码为极大最小距离可分码，简称MDS码 二、汉明码 参数 码长： n=2m-1 信息位长度：k=2m-1-m 最小汉明距离：d=3 校验矩阵有 m行，2m-1列，取互不相同的m重构成 GF(2)上的[7,4,3]汉明码，001,010,011,100, 101,110,111,000。校验矩阵为： 三、标准阵列译码(p63) 线性分组码的基本译码步骤 Step1: 由接收到的序列R，计算伴随式S=RHT； Step2: 若S=0，正确接收；若S不为零，寻找错误图样； Step3: 由错误图样解出码字C=R-E。 标准阵列 根据许用码字将禁用码字进行分类， 分类的依据是错误图样。 两个概念 完备译码:[n,k,d]线性分组码的所有2n-k个伴随式在译码过程中都用来纠正所有小于等于t=(d-1)/2个随机错误以及部分大于t的错误图样。 限定距离译码：译码时不能达到码的纠错能力 第三节 由已知码构造新码的方法 扩展码 删余码 增广码(增信删余码) 增余删信码 延长码 一、扩展码 二、删余码 在原码基础上删去一个校验元。 三、增广码 在原码基础上，增加一个信息元，删去一个校验元 [n,k+1,d] 四、增余删信码 删去一个信息元，增加一个校验元 五、延长码 对增广码再添加一个全校验位。[n+1,k+1] 用多个已知码构造新码 直和: [n, k1+k2, d≤min{d1, d2}] 笛卡尔积：[n1+n2, k1+k2, min{d1,d2}] 链接: [n1+n2, k2, d≥min{d1, d2}] [C1, C1+C2]构造: [2n, k1+k2, min{2d1,d2}] 直积：[n1n2, k1k2, d1d2] 第四节 线性码的纠错能力(p79) 码的重量分布(p73) 普洛特金限(P限) 汉明限 V-G限 一、码重量分布 码的性能不仅由码的最小汉明距离决定，还可由码的重量分布有关 马克威伦(MacWilliams)恒等式 线性分组码的不可检错误概率 线性码是同距离分布码 若码字等概发送 平均不可检 错误概率 译码错误与译码失败概率 teD译码器正确译码的概率 译码错误概率 译码失败概率 误码率 普洛特金（P）限 GF(q)上(n,M,d)分组码的最小距离d为： 三、汉明限(H限、球包限) 长为n纠t个错误的q进制分组码的码字数M为： 四、V-G限 若码的校验元数目n-k满足 当n??时，由P限可推出： 最大的最小距离存在区间 C1 C2 …Ci … … …