错误检测和校正-2.pptVIP

MMT YANGZHOUDAXUE 物理科学与技术学院 第十一讲 错误检测和校正 第1节理论基础 错误的检测和校正是通过编码来实现的 检错编码的目的是通过解码能够发现数据在传输过程中出现了错误纠错编码不仅能够检测到错误还能够纠正过来 因为错误是在信道传输中产生 所以纠错或检错编码属于 通信 信道编码 而压缩编码属于信源编码 香农定理指出 当信息传输速率 R 低于信道容量时 通过编译码 就能够使错误概率为任意小 信道容量指信道传输信息的最大能力或传输信息的最大值 单位bit s 香农给出高斯白噪声信道的信道容量 C 公式 W 信道带宽PS 信号功率N0 噪声功率密度 香农第二定理没有明确指出编译码方法 纠 检 错码类型 本讲只介绍几种简单的线性分组码和交织码的概念 分组码的表示 分组码将k个码元 一般为二进制数 组成一个信息组 例如k 3 则有000 001 111八种信息组 编码器根据信息组按某种规律产生r个码元 校验元 形成一个长n k r的码字 成为 n k 分组码 n表示码长 k表示信息位的数目 例1 重复码规则 k 1 如果信息码字为1 则发送111 如果信息码子为0 则发送000 这是一个 3 1 分组码 例2 一个 4 2 分组码 c3 c2 c1 c0 信息码字 c3 c2 可能为00 01 10 11 校验码字定义为c1 c2 c0 c3 c2 则码字可能为 0000 0111 1001 1110 例1和例2中的发送码字为合法码字 如果接受端收到非法码字则说明发生错误 例3 奇偶校验码规则 在k个信息源后加上1位校验元 使得n k 1个码元中0 1 的个数为奇 偶 数个 例如一个 4 3 码 使0的个数为偶数个 则 Messagescodewords00000000010011010010101101101001001101101011011001111111 检错和纠错重复码可以检出错两位和错一位的情况 可以纠正错一位的情况 重复码译码规则 00000010010001111000101111011奇偶校验码仅是检错码 且只能检出错奇数位的情况 信道出错的类型 噪声对传输码元的影响独立 即每一个差错的出现与否与其前后是否有差错无关 这样的信道称为无记忆信道 因为和前后无关 出现错误的机会可以用独立的概率来表示 Pe 如果仅考虑0和1 又有1错误的变成0和0错误的变成1的概率相等 则这样的信道称为BSC BinarySymmetricChannel 二进制对称信道 表示为下图 若信道的错误不是独立出现 而是成串的出现 则称为有记忆信道 可以采取交织编码技术解决 实际的信道两种错误都可能发生 差错控制系统分类 一 前向纠错 FEC 方式FEC ForwardErrorControl 方式是发端发送能够纠错的码 收端通过译码器纠正这些错误 例如重复码 但不能保证百分之百纠错 二 重传反馈 ARQ 方式ARQ AutomaticRepeatRequest 方式是发端发送能够检错的码 收端发现有错误时 给发端发送一个出错信号要求重发 例如奇偶校验码 也不能保证百分之百检错 三 混合纠错 HEC 方式HEC HybirdErrorControl 方式是上述两种方式的结合 发送端发送的码即能检错 又能纠错 译码器如果发现错误可以纠正就自动纠正 如果错误不能纠正 则通知发端重发 CRC 奇偶校验码和重复码都不属于这类编码 第2节CRC CyclicRedundancyCode 检错编码 基本思想 1 除法被除数x 除数y 商z 余数C 有 x yz cx c yz所以 x c肯定可以被y整除 2 二进制数的模2加减法定义 0 0 0 1 0 1 0 1 1 1 1 00 0 0 1 0 1 0 1 1 1 1 1 0可以看到模2加法和减法是一样的 由模2加减法可以定义模2的乘除法 编码 设待编码的数据为k位 例110101101 k 9 设除数为r 1位 例10011 r 4 则余数最多为r位 令 被除数 待编码的数 2r 1101011010000 n k r位模2除法 则 1101011010000 10011 110000101 1111有 1101011010000 1111 10011 1100001011101011011111 10011 1100001011101011011111就是CRC编码的结果 最后的1111就是CRC校验码 解码 看收到的数据能否被10011整除 如果可以 认为没有出错 如果不能 通知发端重发 上面的例子是一个 13 9 检错码 第3节混合纠错码举例 一个 7 3 码 校验位生成规则 合法码字 合法码字生成规则 G为生成矩阵 H为校验矩阵 当校验结果为0 则认为没有错 否则有错 证明 观察校验矩阵H H的每一列都不一样任意两列的和都不等于H的其它列第1列加第2列等于第4列加第7列第4 5 6列的和等于第1列第1 4 5 6列的和等于0 出错假设 E可能有0000001到1111111共127种情况 E称为出错图样 校验 有1位错 S不为0 一定有错 且根据S的具体值知道哪一位出错 有2位错 S不为0 一定有错 但不知哪2位出错 因为任意两列的和都不等于H的其它列 所以不会误认为1位错 有3位错 S不为0 一定有错 会误认为第1位错 从而误纠错 有4位错 S为0 误认为没有错 上例编码的检纠错能力 1 能够检出1位2位3位错 2 能够纠正1位错 3 能够对2位错不误纠正 4 对3位错会误纠 5 对4位错会误检 S等于H中和错误图样相对应的列之和 可以从H得出编码的纠错能力 该码可以用于HCE方式 在实际应用中 比特差错经常成串发生 而信道编码仅在检测和校正单个差错和不太长的差错串时才最有效 为了纠正这些成串发生的比特差错 交织技术对已编码的信号按一定规则重新排列 解交织后突发性错误在位置上被分散 使其类似于独立发生的随机错误 交织编码和纠错编码连用 一般来说 在发端先对数据进行纠错编码 然后再进行交积处理 第4节交织编码技术 交织的原理图 光盘用到的编码技术 CRC码RS码 也是一个 n k 线性分组码 但是它有纠正 n k 2个错误的能力 CIRC码 RS编码和交织技术相结合形成CIRC码 用在CD ROM中 RSPC码 基本思想用两次RS编码对数据矩阵的行