信源编码：相关信源的编码,信道编码.ppt

信道编码 例如 假设要传送A B两个消息编码一 消息A 0 消息B 1 若产生错码 0 错成 1 或 1 错成 0 收端无法发现 该编码无检错纠错能力 此时的编码没有冗余 编码二 消息A 00 消息B 11 若一位产生错码 变成 01 或 10 因 01 10 为禁用码组 收端可发现有错 但无法确定错码位置 不能纠正 增加一位冗余后具有检出一位错码的能力 编码三 消息A 000 消息B 111 传输中产生一位或是两位错码 都将变成禁用码组 具有检出两位错码的能力在产生一位错码情况下 收端可根据 大数 法则进行正确判决 能够纠正这一位错码 该编码具有纠正一位错码的能力在产生两位错码情况下 只具有检错能力这表明增加两位冗余码元后码具有检出两位错码及纠正一位错码的能力 上述编码方法被称为重复码 记为 n 1 编码方法 把每个信息比特u重复n遍形成一个码组c u u u 译码方法 若译码器收到的一个n个比特码组y yn 1 yn 2 y0 判决码组y中比特 1 和 0 的个数 1 若比特 1 的个数多则判决发送的 1 码 2 若比特 0 的个数多则判决发送的 0 码仍然出错的概率 其中p为信道误码率 n表示码组长度 1表示信息码元的个数 信源编码 信道编码 发送滤波器 接收滤波器 信道译码 信源解码 调制器 解调器 信源 信道 信宿 信道编码的相关概念 码重 码距等简单的信道编码汉明码循环码卷积码 原因 在数字信号的传输过程中 实际信道不理想 存在噪声和干扰 导致接收端的误判 产生差错控制差错的方法 1 合理的设计基带信号 2 选择调制 解调方式 3 均衡技术 4 增大发送功率在此基础之上再采用信道编码技术控制差错 信道编码的目的 添加冗余位 信道编码 1 保持信息的位数不变的情况下 采用增加码长的方法降低误码率2 基本思想 通过对信息码元序列作某种变换 使原来彼此相互独立 没有关联的信息码元序列 经过这种变换后 产生某种规律性或相关性 在接收端可根据这种规律性来检查 或者纠正传输序列中的差错3 实现 发送端按照某种规则在信息序列上附加监督码元 接收端则按照同一规则检查两者间关系 信源编码 是指将信源中多余的信息除去 即降低冗余度 以提高传输的效率 即有效性编码1 去除冗余2 提高传输速率信道编码 为了对抗信道中的噪音和衰减 通过增加冗余 来提高抗干扰能力以及纠错能力 即可靠性编码1 添加冗余2 降低差错率 牺牲通信的有效性 信息传输速率 来提高可靠性因此信道编码又可称为差错控制编码 按照差错的类型可将信道分为 1 独立随机差错信道差错随机出现 且相互独立 主要有高斯白噪声引起2 突发差错信道信道传输的不理想 存在比较大的脉冲干扰导致差错成串出现 信道中差错的种类 差错控制方式 检错重发 能够发现错误的码 判决信号 发 收 检错重发 ARQ 接收端按一定规则对收到的码组进行有无错误的判别 若发现有错 则通知发送端重发 直到正确收到为止具体实现时 通常有3种形式 2 发送端 接收端 1 3 3 1 2 4 ACK ACK NAK 发现错误 a 停止等待重发 Ti Tw 1 如果未发现错误 则发回ACK信号给发送端 发送端收到ACK信号再发下一个码组2 若检测到错误 则发回NAK信号 发送端收到NAK信号后重发前一码组 并再次等候ACK信号或NAK信号 发送端 接收端 5 6 7 8 9 5 6 7 8 9 发现错误 NAK 从码组2开始重发 b 返回重发 1 不停地送出一个个连续码组 不再等候收端返回的ACK信号 收到到NAK则开始重发2 N的大小取决于信号传递及处理所带来的延时 发送端 接收端 9 9 发现错误 NAK 重发码组2 c 选择重发 与返回重发不同的是 发端并不重发错误码组后的所有码组 而只重发有错的那个码组 能够纠正错误的码 发 收 前向纠错 FEC 发送端将信息序列编码成能够纠正错误的码 接收端根据编码规则进行检查 如果有错自动纠正 特点如下 不需要反馈信道 特别适合只能提供单向信道场合自动纠错 不要求检错重发 延时小 实时性好纠错码必须与信道的错误特性密切配合若纠错较多 则编 译码设备复杂 传输效率低 差错控制方式 前向纠错 能够发现和纠正错误的码 发 收 混合纠错检错 HEC 判决信号 FEC与ARQ的结合发端发出同时具有检错和纠错能力的码 收端收到后 检查错误情况 如果错误在纠错能力之内 则自动纠正 若超出纠错能力 但在检错能力之内 则经反向信道要求重发 差错控制方式 混合纠错检错 信道编码的几个基本概念 1 码重 码字中非零位的数目定义为该码组的重量 即所含 1 的个数简称码重 记为Wc 如 10011 码组的码重为32 码距 两个码组中对应码位上具有不同二进制码元的位数被定义为两码组的距离 称为汉明 Hamming 距离 简称码距 记为d ci cj 如两码组 10011 与 11010 间码距为23 编码效率 指一个码组中信息位所占比重 用 表示 k n其中k为信息码元的数目 n为码长 值越大表明信息位所占的比重越大 码组传输信息的有效性越高 若某信源产生两个符号A与B 假设分别用两个长度为4的码组 已被信道编码 进行表示 A 0110 B 1100 码距d 2 此时只有这两个码组是许用码组 其他4位二进制比特位的组合均为禁用码组 不能代表任何消息 1 假设这种信道编码方式具有检错能力 下面分析码距与检错能力的关系1 消息A经过传输后发生一位错误后的情况可能为 A 0110 1110 0010 0100 0111 2 消息A经过传输后发生二位错误后的情况可能为 A 0110 1010 0000 0101 1100 1111 0011 A码组的误码集合中存在许用码组B 可知该编码方法不能检查二位以上的错误因此编码的检错能力与码距有关 最小码距与检 纠错能力关系 有上述分析可知 假设一个码能检测e个独立错误 则要求其最小码距dmin e 1反之 若码的最小距离为dmin 则最多能检测dmin 1个错码 若某信源产生两个符号A与B 假设分别用两个长度为4的码组 已被信道编码 进行表示 A 0110 B 1000 码距d 31 假设这种信道编码方式具有纠错能力 下面分析码距与纠错能力的关系1 若信道中只可能发生一位或两位错误 则消息A与消息B经过传输后发生一位错误后的情况分别可能为 A 0110 1110 0010 0100 0111 B 1000 0000 1100 1010 1001 若该种编码方法可以纠正t 1个错误 即d 2t 1 对于上面两个误码集合是没有交集的 因此可以完全的纠错 即可以分别将误码集合中的码字纠正为A或B 2 若信道中最多可以发生两位以内错误 消息A与消息B经过传输后发生一位或两位错误后的情况分别可能为 A 0110 1110 0010 0100 0111 1010 0000 0101 1100 1111 0011 B 1000 0000 1100 1010 1001 0100 1110 1011 1010 1001 1101 每个误码集合中前4个码组为误码一位的码组 后6个位误码两位的码组若该种编码方法可以纠正t 2个错误 即d 2t 1 观察发现两个误码集合存在交集 交集中的码组用相应的颜色标出 两个集合中黑色字体的码组都可以被正确的纠正 但对于其他颜色的码组 比如1110 它在两个集合中都存在 此时接收端不知道该纠正为A还是B 因此当d 2t 1时不能完全正确的进行纠错 由上述分析可知 一个码能纠正t个错码 则要求其最小码距dmin 2t 1反之 若码的最小距离为dmin 则最多能纠正 dmin 1 2个错码 一个码能纠正t个错码 同时能检测e个错码 则要求其最小码距dmin e t 1 e t 纠正t个错码 同时能检测e个错码 称为纠检结合 错码数较少时执行纠错方式 错码数较多时执行检错方式 有限域的简单知识 所谓有限域是指包含有限个元素的集合 按照所规定的运算规则运算后的结果仍为集合中的元素编码理论中有限域为 0 1 二元集合 记为GF 2 GF 2 的加法与乘法 1 加法 相同为0 相异为1 2 乘法 除了1 1 1 其他均为0二元扩展域 记为GF 2n 由GF 2 中的元素构成的长为n的序列的集合 若1 加法2 乘法 二 线性分组码 线性分组码的数学定义 信道编码可表示为由编码前的信息码元空间Uk到编码后的码字空间Cn的一个映射f 即 f Uk Cn其中 n k 若f进一步满足线性关系 则称f为线性编码映射 若f为一一对应映射 则称f为唯一可译线性编码 由f编写的码c cn 1cn 2 c0 称为线性分组码 u un 1un 2 u0 为编码前的信息分组 其中k为信息位数 n为码长 其编码效率为 k n 数学定义的解释 1 线性 是指码组中码元之间的约束关系为线性 2 分组 是在编码时将每k个信息位分为一组进行独立处理 3 将其变换成长度为n n k 的二进制码组 一般称为 n k 线性分组码线性分组码的特征 1 加法封闭性 码组集合中任意两个码组相加仍为集合中的一个许用码组 2 全零序列是线性分组码中的一个码字 3 码组集合中码组之间的最小码距等于某非零码字的最小码重 偶监督偶校验码发送端编码 将一位监督码元附加在信息码元后 使得码组中 1 码元个数为偶数 偶监督 接收端译码校验 1 计数接收码组中 1 码元个数是否为偶数 即计算S an 1 an 2 a02 S 0认为没错 S 1认为有错3 上式称为监督方程 监督关系式 其中S称为校正子 校验子 伴随式 4 S只能判断有错无错 而不能纠错 汉明码的构造 假设有1个信息码组由4位二进制位组成 在其后添加3位二进制位作为监督码元 最后所组成的码组表示为 c u6u5u4u3c2c1c0 并且令 1 c2监督u6u5u4 即2 c1监督u6u5u3 即3 c0监督u6u4u3 即接收端译码校验 得到监督方程 对于上式 若无错误发生 三个校验子均为0 假设传输过程中有且仅有一位发生错误 1 若c0发生错误 观察监督方程 则三个校验子S2S1S0的组合为001 2 若c1发生错误 S2S1S0 010 3 若c2发生错误 S2S1S0 100 4 若u3发生错误 S2S1S0 011 5 若u4发生错误 S2S1S0 101 6 若u5发生错误 S2S1S0 110 7 若u6发生错误 S2S1S0 111 因此依据监督关系式就可计算出所有4位二进制信息位u6u5u4u3的监督位c2c1c0 这一过程即为 7 4 线性码的构造过程 其码组空间为 表中所示为 7 4 线性码的码组空间 监督矩阵的推导 将监督关系式进行变换观察发现上式即为一个线性方程组 因此可用矩阵方程来表示 对于上面的矩阵方程 令 则矩阵方程可化简为 H CT OT或C HT O那么H称为线性码监督矩阵 r n阶的矩阵 由r 监督位个数 个线性独立方程组的系数组成 每一行代表了监督位与信息位间的监督关系 观察矩阵H 把具有 P Ir 形式的H矩阵称为典型形式的监督矩阵 其中P矩阵为r k阶矩阵 Ir矩阵为r r阶单位方阵H矩阵的各行应线性无关 矩阵若能写成典型形式 则其各行一定线性无关 生成矩阵的推导 对监督关系式进行移项变换 移动红色部分 观察上面的矩阵方程 其中系数矩阵与监督矩阵H中的P矩阵一样 对此矩阵方程两边做转置变换 其中Q PT 为k r阶矩阵 U矩阵表示信息位由上面的矩阵方程可知 只要用信息位与矩阵Q相乘就可得到监督位 然后拼接在信息位之后就是一个 n k 线性分组码集合中的一个码字 虽然通过Q矩阵可以产生线性分组码 但需要分为两步 如果对Q矩阵做变换 在Q矩阵的左边加上一个k k阶单位阵 即 则一个 n k 线性分组码可以通过下面的矩阵方程产生 矩阵G则被称为线性分组码的生成矩阵 对于生成矩阵G 1 k n阶矩阵 2 编码方法完全由生成矩阵G确定 3 把具有 Ik Q 形式的G矩阵称为典型形式的生成矩阵 其中Ik为k k阶单位方阵 Q为k r阶矩阵 4 由典型生成矩阵产生的分组码一定是系统码 5 若某生成矩阵G 不具有典型形式 则产生的线性分组码为非系统码 若将G 进行线性初等矩阵变换 使其具有典型形式 则产生的码组与不变换产生的码组有同样的纠检能力 即系统码与非系统码的纠检能力相同 6 H P Ir QT Ir G Ik Q Ik PT 7 生成矩阵G的各行线性无关 若k位的信息码元出现在线性分组码的前k位 则称此线性分组码为系统码 否则为非系统码 对于监督矩阵H 1 H矩阵r n阶的矩阵2 H矩阵中每行和其码组集合中的任一码字的内积为0 3 任意一个 n k 线性分组码的H矩阵行线性无关 4 一个 n k d 线性分组码 若要至多纠正t个错误 则其充要条件是H矩阵中任何一个2t列线性无关 由于最小距离d 2t 1 所以也相当于要求H矩阵中任意 d 1 列线性无关 生成矩阵G与监督矩阵H的关系 因为信息位不会全零 因此 再由 H P Ir G Ik Q 代入上式 得 上式中矩阵的下标为其阶数 例 设 7 4 线性码的生成矩阵G为 当信息位为0001时 试求其后的监督位 例 试求上例的监督矩阵H解 根据生成矩阵和监督矩阵的关系 G Ik Q H P Ir 可得监督矩阵H为 对偶码 定义 对于线性分组码 1 将 n k 码的监督矩阵H作为 n n k 码的生成矩阵G 2 将 n k 码的生成矩阵G作为 n n k 码的监督矩阵H 这样的 n k 码与 n n k 码互为对偶码 编码过程 观察 7 4 码的监督关系式 可设计出相应的编码电路 译码纠 检过程 错误矩阵 错误图样E 设发送码组为c 接收码组为y 则对于二元有限域 上式中的减法等价于加法 即 对于二元有限域的加法的具有确定两个码组中不同比特位的特性 例如 假设长度为n的码组A和B分别为 假设这两个码组的第k位不同 其他位相同 根据加法规则 因此接收端可以利用这种