信息论与编码 第5章.ppt.ppt

第5章 数据纠错 引言 信息传输是信息处理的一个重要环节，其目的是让其他人获得所需的信息 信息传输中面临的错误 如何避免和修复传输中的错误 处理方法 烽火台 离散信道模型 单向离散信道(One-way Discrete Channel)，一般简称为信道(Channel) 离散无记忆信道(Discrete Memoryless Channel, DMC) 信道转移矩阵 简单信道 无噪信道(Noiseless Channel) 输出隔离有噪信道(Noisy Channel with Nonoverlapping Outputs) 噪声 无意义的噪声 影响正确性的噪声 信道中传输的信息量 互信息 二元无噪信道(Binary Noiseless Channel) 信道转移矩阵为单位矩阵 二元对称信道( BSC) 对称 一般化:对称信道(Symmetric Channel) 其它信道 Z信道(Z Channel) 二元删除信道(Binary Erasure Channel, BEC)和自动重传请求(Automatic Repeat reQuest, ARQ) 二元打字机犯的错误，也正是数字信道中可能出现的一些典型错误 它们指示设计者更好地避免错误，从而保证有效的信息传输 信道扩展 并联技术 等价于扩展(Extension) 译码准则 最大似然译码(Maximum Likelihood Decoding) 最大后验概率译码(Maximum a Posteriori Decoding) 译码错误概率 (Decoding Error Probability) 最小错误概率译码(Minimum Error Probability Decoding) 一般是最大后验概率译码 等概率分布情况下就是最大似然译码 错误概率估计 Fano不等式(Fano Inequality) 错误概率下界 分组码 冗余(Redundancy) 重复码(Repetition Code) 前向纠错(Forward Error Correction, FEC) 码率(Rate) 差错控制编码(Error Control Coding) 码字距离 距离空间的三个公理 Hamming距离满足距离公理 线性分组码(Linear Block Code) 最小距离译码(Minimum Distance Decoding) 码簿的最小距离 该值越大，意味着出现错误后恢复的机会也越大 码簿的设计思路 纠错能力 差错模式(Error Pattern) 重量(Weight) 检测所有错误 纠正所有错误 Hamming码 奇偶校验矩阵(Parity-Check Matrix) (7,4)Hamming码 (7,4)Hamming码的码簿 至少能纠正1位错误 纠错实例 为 * *