[信息与通信]第11章差错控制编码.ppt

通 信 原 理 电 子 教 案第11章 差错控制编码 11.1 概述一、编码问题的提出 由于数字信号在传输过程中必不可免的受到干扰的影响，使码元波形变坏，故传输到接收端后可能发生错判。 11.2 纠错编码的基本原理一. 基本思想 11.4 简单的实用编码 －－属于分组码一类。简单、实用。一. 奇偶监督码满足: 11.6 循环码 －－仍属于线性分组码特点: 编译码设备简单，检纠错能力强。11.6.1 循环码的原理具有线性分组码的所有性质之外，还具有循环性：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。 11.5 线性分组码 基本概念 代数码：建立在代数学基础上的编码。 线性码：按照一组线性方程构成的代数码。在线性码中信息位和监督位是由一些线性代数方程联系着的。 线性分组码：按照一组线性方程构成的分组码 。 定义：若分组码（n,k）,督元与信元的关系可用一线性方程组来描述，则该分组码（n,k）称为线性分组码。 定义：若分组码（n,k）,督元与信元的关系可用一线性方程组来描述，则该分组码（n,k）称为线性分组码。 一、汉明码 －－能纠一位错的线性分组码。 定义：是一种能纠正一位错码，且编码效率较高的线性分组码。 最小码距：d0=3 1. 构造原理 考察：定义一个监督方程（监督关系式、偶监督）： 由于一位校正子只有两种取值，故只能表示有错或无错，不能指出错码的位置。 推想：如果监督位增加一位（即变成两位），则可增加一个类似于上式的监督关系，即可获得两个校正子，于是可有 S1 S2 0 0 0 1 0 1 1 －－无错 可指示一个错码可能出现的位置，共有22-1=3 个位置。 再推广： S1 S2 ……Sr 0 0 ……. 0 0 0 ……. 1 ……………… 1 1 ….1 1 －－无错 2r-1 个错的 可能位置 －－可指示一个错码可能出现的2r-1个位置。 一般来说，若码长为n，信息位数为k，则监督位数r＝n－k。如果希望用r个监督位构造出r个监督关系式来指示1位错码的n种可能位置，则要求 2. 例: 构造k=4 的汉明码 （1）确定 r 由 2r ≥ k+r+1 得 r = 3，则 n= k+r=7 －－ ( 7,4 ) 分组码 （2）写出校正子的编码表 2r-1≥n，（n=k+r），则可指示（仅一位错时）任一错码的位置－－包括信元、督元。 或：2r≥k+r+1 （2）写出校正子的编码表 r = 3 共有3个校正子 S1 S2 S3 错码位置 S1 S2 S3 错码位置 0 0 1 a0 1 0 1 a4 0 1 0 a1 1 1 0 a5 1 0 0 a2 1 1 1 a6 0 1 1 a3 0 0 0 无错 （3） 由校正子编码表得监督方程组－－校正子和哪些码元构成偶监督关系 若 S1S2S3 = 000 时, 即无错－－得校验方程: 偶监督关系 校正子编码表不是唯一的。 得校验方程: 即实际上确定了督元和信元之间的关系: 校验方程 督～信关系 －－有了校正子编码表，督元不是随便选的！（表的编制不是唯一的） （4） 给定了信元a6a5a4a3,可由“督～信关系”确定督元－－全部( 7,4 ) 码组。 （4） 给定了信元a6a5a4a3,可确定督元－－全部( 7,4 ) 码组 二. 线性分组码－－一般性讨论 1. 线性方程组和监督方程－从校验方程入手 写成矩阵式: 1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 a6 a5 a4 a3 a2 a1 a0 校验方程 来自编码表 可见：H一旦确定，督元和信元之间的关系也就确定了。 若: 则称H为典型阵，一般，H总可以化为典型阵。 1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 a6 a5 a4 a3 a2 a1 a0 H矩阵的性质： 1) H的行数就是监督关系式的数目，它等于监督位的数目r。H的每行