第九章：纠错编码 第九章：纠错编码 第九章：纠错编码 第九章：纠错编码 1. 概述 一：基本概念 一：基本概念 2. 纠错工作方式 3. 纠错码分类 二：线性分组码 二：线性分组码 三：汉明码 三：汉明码 四：循环码 四：循环码 1. 概述（续1） 1. 概述 1. 概述（续1） 1. 概述 减小接收端码元错误概率的措施 香农第二定理证明，当R C 时 P →0 的码存在。 E 选择合适的调制、解调方法 增加信号的发送功率 证明过程采用的是随机编码的方法： 采用差错控制编码 随机编码所得的码集很大，通过搜索得到好码的方法在实际 上很难实现； 纠错编码是提高传输可靠性的最主要的措施之一。 即使找到了好码，这种码的码字也没有规律，不便于译码。 实用的信道编码方法还需要通过各种数学工具来构 造，使码具有好的结构性以便于译码。 1. 概述（续2 ） 2. 纠错工作方式 1. 概述（续2 ） 2. 纠错工作方式 纠错编码的基本思路： (1) 反馈重传(ARQ) 根据一定的规律在待发送的信息码元中人为的加 入一些冗余码元，这些冗余码元与信息码元之间以某 (2) 前向纠错(FEC) 种确定的规则相互关联（约束）。 (3) 混合纠错 在接收端按照既定的规则检验信息码元与监督码 元之间的关系。如果传输过程出错，则信息码元与监 督码元之间的关系将受到破坏，从而可以发现错误乃 至纠正错误。 1 2. 纠错工作方式（续1） 2. 纠错工作方式（续1） 2. 纠错工作方式（续2 ） 2. 纠错工作方式（续2 ） (1) 反馈重传(ARQ) (2) 前向纠错(FEC) m C ˆ 检错 信道 Y 检错 m 编码 译码 m 纠错 C Y ˆ 信道 纠错 m 编码 译码 反馈 发送端经编码后发出能够发现错误的码，接收端收到后经 发送端发出的是具有纠错能力的纠错码，接收端根据译 检验，如果发现传输中有错误，则通过反馈系统把这一判断结 码规则进行译码。当误码个数在码的纠错能力范围内时，译 果反馈回发端，然后发送端把前面发出的信息重新传送一次， 码器可以自动纠正错误。 直到接收端认为正确地收到信息为止。 2. 纠错工作方式（续3 ） 2. 纠错工作方式（续4 ） 2. 纠错工作方式（续3 ） 2. 纠错工作方式（续4 ） 特点： (3) 混合纠错 1）前向纠错方式不需要反馈信道，特别适合于只能 对发送端进行适当的编码。当错误不严重，在码的 提供单向信道的场合。 纠错能力范围之内时，采用自动纠错；当产生的差错超 2）由于能自动纠错，不要求检错重发，因而延时小， 出码的纠错能力范围时，通过反馈系统要求发端重发。 实时性好。 3）随着纠错能力的增强，译码设备也变得复杂。 3. 纠错码分类 3. 纠错码分类（续1） 3. 纠错码分类 3. 纠错码分类（续1） (1) 按功能分： (3) 按信息码元与监督码元之间的约束方式不同分： 检错码：仅能检测误码 分组码：本码组的监督码元仅和本码组的信息元相关。 纠错码：可纠正误码 卷积码：本码组的监督码元不仅和本码组的信息元相 纠删码：兼纠错和检错能力 关，而且与前面码组的信息码元有关。 (2) 按信息码元与监督码元之间的检验关系分： (4) 按信息码元在编码后是否保持原形式不变： 线性码：满足线性关系 系统码：信息码元与监督码元在分组内有确定位置， 非线性码：不存在线性关系 编码后的信息码元保持不变； 非系统码：信息位打乱，与编码前不同。 2 3. 纠错码分类（续2 ） 3. 纠错码分类（续2 ） 第九章：纠错编码 第九章：纠错编码 (5)按纠正差错的类型可分为： 一：基本概念 1. 线性码的优点 纠随机错误码 2. 校验矩阵与生成矩阵 差错的出现互不相关，彼此独立 二：线. 检纠错能力 纠突发错误码 4. 校验矩阵与最小距离的关系 错误之间存在相关性 三：汉明码 5. 伴随式 纠随机和突发错误码 四：循环码 1. 线. 线. 线. 线） k 分组码的表示方法： 对二进制(n, k)线性分组码，合法码字数为2 ，可用编 信息码组由 k 个信息码元组成，共有 2k 个不同 码空间的序列数为2n个。 的信息码组； k n 任一种2 信息集合到二进制序列集合(2 ) 的映射都是 k 附加 r 个校验码元，每个校验码元是该信息码 一种(n, k)码。因此总共可能的编码方案有 C 2 n 种。 2 组的某些信息码元模2和； 译码运算量：如果直接用最大似然序列译码，对一般 编码器输出长度为n r =+k 的码字； 性的编码而言，正比于n* 2k 。BG大游娱乐平台几乎是不可能译码。 码字的数目共有 2k ； 这2k 个码字的集合称为 (n,k) 分组码； 1. 线. 校验矩阵与生成矩阵 1. 线. 校验矩阵与生成矩阵 发现或构造好码是信道编码研究的主要问题： (1) 校验矩阵 编码方案太多，以至全局搜索是不可能的。BG大游娱乐平台 以(7,3) 线性分组码为例。码字表示为 现实的做法是对编码方案加以一定的约束，在一个子集中 寻找局部最优。 C [c ,c ,c ,c ,c ,c ,c ] 1 2 3 4 5 6 7 这种约束即要能包含尽可能好的码，又要便于分析，便于 c , c ,c c , c ,c , c 译码。 其中 为信息元， 为校验元。 1 2 3 4 5 6 7 线性分组码是最简单、实用一类码，比如汉明码、循 环码、BCH码、RS码等。 3 2. 校验矩阵与生成矩阵（续1） 2. 校验矩阵与生成矩阵（续2 ） 2. 校验矩阵与生成矩阵（续1） 2. 校验矩阵与生成矩阵（续2 ） 校验元可由下面方程组计算得到： 用矩阵表示为： c ⎡ ⎤ 1 ⎢ ⎥ + + c c c c 0 2 c c =+c ⎧ ⎧4 1 3 1 3 4 1 0 1 1 0 0 0 ⎢ ⎥ 0 ⎡ ⎤ ⎡ ⎤ ⎪ c ⎪ ⎢ ⎥ + + + ⎢ ⎥ 3 ⎢ ⎥ c c =+c +c c c c c 0 1 1 1 0 1 0 0 0 ⎪5 1 2 3 ⎪1 2 3 5 ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎨ ⇒ ⎨ c4 1 1 0 0 0 1 0 ⎢ ⎥ 0 c c =+c c +c +c 0 ⎢ ⎥ ⎢ ⎥ 6 1 2 ⎪1 2 6 ⎢ ⎥ ⎪ ⎢ ⎥c5 ⎢ ⎥ 0 1 1 0 0 0 1 ⎢ ⎥ 0 ⎪ ⎪ ⎣ ⎦ ⎣ ⎦ c c c c c =+c + + 0 c ⎩7 2 3 ⎩2 3 7 6 ⎢ ⎥ ⎢ ⎥ c 7 ⎣ ⎦ 2. 校验矩阵与生成矩阵（续3 ） 2. 校验矩阵与生成矩阵（续4 ） 2. 校验矩阵与生成矩阵（续3 ） 2. 校验矩阵与生成矩阵（续4 ） 令 ⎡1 0 1 1 0 0 0⎤ H 被称为校验矩阵。 ⎢ ⎥ H ⎢1 1 1 0 1 0 0⎥ 对（n,k ) 线性分组码，校验矩阵为(n −k ) ×n 维矩 ⎢1 1 0 0 0 1 0⎥ ⎢ ⎥ 阵。 ⎣0 1 1 0 0 0 1⎦ 对于系统码，校验矩阵可以表示为 C [c ,c ,c ,c ,c ,c ,c ] 1 2 3 4 5 6 7 H = [Q I ] 0 [0,0,0,0] 其中 为(n −k ) ×k维矩阵， 为(n −k ) ×(n −k )维单 Q I 则 HC T 0 T ⇔ CH T 0 位矩阵。 2. 校验矩阵与生成矩阵（续5 ） 2. 校验矩阵与生成矩阵（续6 ） 2. 校验矩阵与生成矩阵（续5 ） 2. 校验矩阵与生成矩阵（续6 ） (2) 生成矩阵 令 m [c ,c ,c ] 1 2 3 ⎧c1 c1 由校验方程，得到 ⎪ ⎡1 0 0 1 1 1 0⎤ ⎪⎪c2 c2 G ⎢⎢0 1 0 0 1 1 1⎥⎥ [I P ] c c ⎪ 3 3 ⎢⎣0 0 1 1 1 0 1⎥⎦ ⎨c4 c1 =+c3 ⎪ =+ + ⇒ C mG c c c c ⎪ 5 1 2 3 ⎪c6 c1 =+c2 ⎪ ⎩c7 c2 =+c3 4 2. 校验矩阵与生成矩阵（续7 ） 2. 校验矩阵与生成矩阵（续8 ） 2. 校验矩阵与生成矩阵（续7 ） 2. 校验矩阵与生成矩阵（续8 ） G 被称为生成矩阵。 把生成矩阵的每一行用一个行向量 G ,i 1,2,L, k 来表 i 对（n,k ) 线性分组码，生成矩阵为 k ×n 维矩阵。 示，则生成矩阵可以表示为 G ⎡ ⎤ 1 对于系统码，生成矩阵可以表示为 ⎢ ⎥ G 2 G ⎢ ⎥ G [I P] ⎢ ⎥M ⎢ ⎥ G k ⎣ ⎦ 其中 为k ×(n −k )维矩阵， 为 k ×k 维单位矩阵。 P I 令 m [m ,m ,L,m ] ，则 1 2 k k C mG ∑m G i i i 1 2. 校验矩阵与生成矩阵（续9 ） 2. 校验矩阵与生成矩阵（续9 ） 2. 校验矩阵与生成矩阵（续9 ） 2. 校验矩阵与生成矩阵（续9 ） 生成矩阵的每一行都是一个码字： 问题： 当信息码组m [m ,m ,L,m ] 中仅有一个非零 （1）非标准形式的生成矩阵，如何化成标准形式？ 1 2 k 元素时，得到的码字即为生成矩阵的某一行。 （2 ）若校验位在前，信息位在后，标准形式的校验矩 阵或生成矩阵，可以表示成什么样的分块矩阵？ （3 ）给定一种线性分组的全部码字，已知该码是系统 码，如何确定信息位在前还是在后？ 2. 校验矩阵与生成矩阵（续10） 2. 校验矩阵与生成矩阵（续11） 2. 校验矩阵与生成矩阵（续10） 2. 校验矩阵与生成矩阵（续11） (3) 校验矩阵和生成矩阵的关系 线性分组码的封闭性：线性分组码中任意两个码字之 和仍然是该码的码字。 由于生成矩阵G的每一行都是一个码字，所以G 的每 行都满足 HG T 0 T，则有 C C 证明：设 和 分别是码 C 中的两个码字，因此有 i 1 2 HG T 0 HC1T 0 T ⎫⎪ T T T T H C C HC HC 0 对于标准形式的校验矩阵和监督矩阵，有 T T ⎬⇒ ( 1 + 2 ) 1 =+ 2 HC2 0 ⎭⎪ HGT [Q I ][I P ]T Q +P T 0 即C +C 满足监督方程，所以是码 中的一个码字。 1 2 C ⇒ Q P T 5 3. 线性分组码的检纠错能力 3. 线性分组码的检纠错能力 3. 线性分组码的检纠错能力 3. 线性分组码的检纠错能力 * p y x ( j ) 定理9.3.1 对于一个二进制对称信道，若输入为k个等可 令 λ ( ) 能的n长码字，则最大后验概率译码准则应为最小汉明 p y j xi * * ( ) * d x ,y ( ) j n−d x ,y ( ) ( ) j d x ,y −d x ,y ( ) j i j 距离译码。 λ p ( ) 1−p ⎛⎜ p ⎞⎟ d x ,y ( ) i j n−d x ,y ⎜ ⎟ 证明： ( ) i j 1−p p 1−p ⎝ ⎠ * ( ) 最大后验概率译码准则 p (x y j )≥p xi y j ∀i p p 0.5 ⇒ 1 ( * ) ( ) 1−p 输入等概 p y j x ≥p y j xi * 当 ( * ) ( ) 时， * d x ,y ≤d x , y ( ) ( ) λ≥1 p y x ≥p (y x ) 最小汉明距离译码 d (x ,y )≤d x , y ∀i j i j j j i j i j d x ,y n−d (x ,y ) ( ) ( )( ) p y x p 1−p 3. 线性分组码的检纠错能力 3. 线性分组码的检纠错能力 3. 线性分组码的检纠错能力 3. 线性分组码的检纠错能力 定理9.3.2 线性分组码的最小汉明距离等于非零码字的 定理9.3.3 设d 为线性分组码的最小汉明距离， min 最小重量。 1)该码具备纠正 u 个错误的充分必要条件是 说明： dmin 2u +1 1. 线. 码字的重量定义为非零码元的个数 Ci 1 C j 3. 两个码字的汉明距离等于这两个码字 u u 相加所得新码字的重量。 d min 3. 线性分组码的检纠错能力（续1） 3. 线性分组码的检纠错能力（续2 ） 3. 线性分组码的检纠错能力（续1） 3. 线性分组码的检纠错能力（续2 ） 2)该码具备检测 l 个错误的充分必要条件是 3)该码具备纠正 t 个错误，同时可以发现 l(l t) 个错 误的充分必要条件是 d l =+1 min d t +l +1 min l Ci 1 Ci 1 C j t l d d min min 6 4. 校验矩阵与最小距离的关系 5. 线. 校验矩阵与最小距离的关系 5. 线性分组码的伴随式 定理9.3.4 对于线性分组码，设其校验矩阵为 H 。 设发送码字为C，接收到的码元序列为Y，令 H t T T T 若 中的任意 列线列线性相关， S YH 或 S HY 则该码的最小汉明距离为 t +1； 1) S 0 ，说明Y 是一个码字; 反之，若码的最小汉明距离为 t +1 ，则校验矩阵 2) ，说明Y 不是码字，传输过程产生了误码。 S ≠0 t t +1 的任意 列线性无关，而 列线性相关。 令 Y = C + E n T 提示：通过公式 HC 0 ⇔ c H 0 ⇒ T T T T T ∑ i i S YH = (C + E )H = CH + EH = EH i 1 5. 线. 线. 线 ） 令 E = [e , e ,L, e ] 结论： 1 2 n 1) 当传输过程没有错误时，即 E = 0,0, L,0 ， T H = [H ,H ,L,H ] H [ ] （其中 表示 的列向量） S 0 1 2 n i H 2)当发生一位错误时， T 是校验矩阵的某一列。 则 S e ⎡ ⎤ 1 3)当发生多个错误时，S T 为校验矩阵对应列的模2和。 ⎢ ⎥ n e T T 2 S = HE [H ,H ,L,H ]⎢ ⎥ ∑e H 1 2 n ⎢ ⎥M i 1 i i ⎢ ⎥ e n ⎣ ⎦ 5. 线. 线. 线. 线性分组码的伴随式 伴随式：n-k维向量。 译码过程总结： – 确定校验矩阵H； 伴随式数目与可纠正错误数目的关系： S T HY T u – 对于接收到的码符号序列，求伴随式： 2n−k ≥ Ci 等号成立则为完备码 ∑ n – 判断出错码元位置； i 0 – 纠错； 7 5. 线. 线. 线. 线)线性分组码的校验矩阵为 （1）接收码字Y=(1010011)， 1 ⎡ ⎤ ⎢ ⎥ 0 ⎡1 0 1 1 0 0 0⎤ 1 0 1 1 0 0 0 ⎢ ⎥ 0 ⎡ ⎤ ⎡ ⎤ 1 ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ 1 1 1 0 1 0 0 T T 1 1 1 0 1 0 0 ⎢ ⎥ 0 H ⎢ ⎥ S = HY ⎢ ⎥0 ⎢ ⎥ 1 1 0 0 0 1 0 ⎢ ⎥ 0 ⎢1 1 0 0 0 1 0⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥0 ⎢ ⎥ 0 1 1 0 0 0 1 ⎢ ⎥ 0 ⎣0 1 1 0 0 0 1⎦ ⎣ ⎦ 1 ⎣ ⎦ ⎢ ⎥ ⎢ ⎥ 1 ⎣ ⎦ ⇒ 传输过程中没有误码， ˆ C =Y 5. 线. 线 ）接收码字Y=(0011011)， 0 1 ⎡ ⎤ ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ 1 0 ⎢ ⎥ 1 0 1 1 0 0 0 ⎢ ⎥ 0 1 0 1 1 0 0 0 0 ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ 1 1 ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ T T 1 1 1 0 1 0 0 ⎢ ⎥ 1 T T 1 1 1 0 1 0 0 ⎢ ⎥ 1 S = HY ⎢ ⎥ 0 ⎢ ⎥ S = HY ⎢ ⎥ 1 ⎢ ⎥ ⎢ ⎥ 1 1 0 0 0 1 0 ⎢ ⎥ 1 1 1 0 0 0 1 0 1 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ 0 ⎢ ⎥ 0 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 ⎢ ⎥ 0 ⎣ ⎦⎢
2、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。
3、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
4、VIP文档为合作方或网友上传，每下载1次， 网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
距离下一个“iPhone时刻”还有多远：2025年中国AI眼镜行业研究报告.pdf
2026《高考数学一轮复习微专题106讲》含答案43.从教材到压轴：n维向量的概念与应用.docx
原创力文档创建于2008年，本站为文档C2C交易模式，即用户上传的文档直接分享给其他用户（可下载、阅读），本站只是中间服务平台，本站所有文档下载所得的收益归上传人所有。原创力文档是网络服务平台方，若您的权利被侵害，请发链接和相关诉求至 电线) ，上传者
