《信息理论与编码-第六章-信道编码备课讲稿》由会员分享，可在线阅读，更多相关《信息理论与编码-第六章-信道编码备课讲稿（154页珍藏版）》请在金锄头文库上搜索。
1、第1章 概述 第2章 信源熵 第3章 信道容量 第4章 信息率失真函数 第5章 信源编码 第6章 信道编码 第7章 密码体制的安全性测度 6 1信道编码的概念 6 2线形分组码 6 3循环码 6 4卷积码 信道编码是以信息在信道上的正确传输为目标的编码 可分为两个层次上的问题 如何正确接收载有信息的信号 线路编码如何避免少量差错信号对信息内容的影响 纠错编码 广义信道编码 特定信道上传输信息而进行的传输信号或信号格式的设计与实现 描述编码用于对特定数据信号的描述约束编码用于对特定信号特性的约束扩频编码用于扩展信号频谱为近似白噪声谱并满足某些相关特性纠错编码用于检测与纠正信号传输过程中因噪声干扰
2、导致的差错 1 2 3 4 6 1 1 信道编码的作用和分类 6 1 3编码信道 6 1 3 检错和纠错原理 6 1 4 检错和纠错方式和能力 消息 编码信道模型 n 1 当码字C和接受向量R均由二元序列表时 称编码信道为二进制信道C c0 c1 cn 1 如果对于任意的n都有 P r c p ri ci 则称此二进制信道为无记忆二进制信道 p 0 1 p 1 0 p0则称此信道为无记忆二进制对称信道BSC i 0 BSC输入输出关系等效为 差错图案 随机序列或 第位上的一个随机错误 长的突发错误 第至第位之间有很多错误 对于一个BSC信道总有转移概率1 2 比特传输中发生差错数目越少 概率越
3、大 即 从而总认为发生差错的图案是差错数目较少的图案 二元软判决信道 用多个比特 理想情况下为实数 表示每一个无记忆编码信道的二元符号输出 信道干扰z为零均值正态分布的随机变量 噪声干扰功率为均方差 z的概率分布为 对于BPSK调制 二元输入符号为二元符号取值为 1或 1 6 1 1 信道编码的作用和分类 6 1 2 编码信道 6 1 3检错和纠错原理 6 1 4 检错和纠错方式和能力 检纠错是根据信道输出序列自身判断是否可能是发送的 或纠正导致不等于的错误 冗余编码 码字的长度一定大于消息的长度 编码码率 每个码字的序列符号 或码元 平均传送的消息比特数 偶 或奇 校验方法 实现检纠错目的的
4、一个基本方法 一个偶校验位是对消息使得如下校验方程成立的二进制符号 即 一个偶校验码码字 一个码率为的偶校验码 所有可能的的全体 校验方程为1表明一定有奇数个差错 校验方程为0表明可能有偶数个差错 m0 m1 m2 mk 1 p 0 mod2 称c m0 m1 m2 mk 1 p 为一个偶校验字确定校验位P的编码方程为 P m0 m1 mk 1 编码可以产生多个奇偶校验位 即一个校验位可以由消息位的部分或全部按某种校验方程产生 例如对阵列消息进行垂直与水平校验以及总校验的码字和其码率分别为 重复消息位 实现检纠错目的第二个基本方法 一个重复码是一个码率为的码 仅有两个码字和 传送1比特 消息
5、重复码可以检测出任意小于个差错的错误图案 纠正任意小于个差错的错误图案 纠1位差错的3重复码 等重码或定比码 实现检纠错的第三个方法 设计码字重量恒为常数 即 例如一种用于表示0至9数字的5中取3等重码如表 6 1 1 所示 其码率为 5中取3等重码 5中取3等重码可以检测出全部奇数位差错 对某些码字的传输则可以检测出部分偶数位差错 6 1 1 信道编码的作用和分类 6 1 2 编码信道 6 1 3 检错和纠错原理 6 1 4检错和纠错方式和能力 纠错码的应用方式 前向纠错方式 FEC 自动请求重发 ARQ 方式 混合纠错 HEC 方式以及信息反馈 IRQ方式 FEC与ARQ纠错应用方式 常用
6、汉明距离来描述检纠差错的数目 对于两n长向量u v汉明距离为 最小汉明距离 最小码距d 任意两码字之间的汉明距离的最小值 定理对一个最小距离为纠错码 如下三个结论仅有其中任意一个结论成立 1 可以检测出任意小于等于个差错 2 可以纠正任意小于等于个差错 3 可以检测出任意小于等于l同时纠正小于等于t个差错 其中l和t满足 最小码距与检纠错能力 差错概率 通信作为一个统计过程时 纠检错能力的统计特性 FEC方式纠错码的码字差错概率 发送码字的先验概率 码字数 对于充分随机的消息源 对BSC信道 最大化等价于最小化 最小差错概率译码等价为使接收向量与输出码字距离最小的最小距离译码 即 信息比特信噪
7、比 传输一个比特信息所需的最小信噪比 比特差错概率 又称误码率 与信噪比的关系如下图所示 采用纠错码后 达到同样比特差错概率实际需要的信噪比减小量称为编码增益 编码增益 6 2线性码 6 2 1线性分组码的描述 6 2 2线性分组码的译码 6 2 3码例与码的重构 6 2 1线性分组码的描述 6 2 2线性分组码的译码 6 2 3码例与码的重构 一个 n k 线形分组码C是称为码字c的n维向量的集合C c c mG 其中m为任意的k维向量并称为消息向量 G是k行n行列秩为k n k 的矩阵并称为生成矩阵 对于二元编码 和是二元向量 是一个二元矩阵 向量与矩阵 矩阵与矩阵之间的基本运算是模二加和
8、模二乘运算 表6 2 1模二加 乘法表 例6 2 13重复码是一个 3 1 线性分组码 例6 2 2 4 3 偶校验码是一个 4 3 线性分组码 当生成矩阵给定时线性分组码有如下性质 1 零向量一定是一个码字 称为零码字 2 任意两码字的和仍是一个码字 3 任意码字是的行向量的线性组合 4 线性分组码的最小距离等于最小非零码字重量 由偶校验码的检错概念 可以通过计算接收向量的所有校验方程值是否为0来判断传输是否可能有错 那么必有一个矩阵满足 显然的每一列或的每一行确定了一个可能的分组码的校验方程 的线性不相关行数最少要等于该码的所有可能的校验方程数 称这样的矩阵为线性分组码的一致校验矩阵 由的
9、每一行都是一个码字有 由现行空间的理论 当H的行秩为r时 H作为一个 n k 线性分组码的生成矩阵所生成的码是与G对应空间正交的r维线性子空间 称为 n k 线性分组码的对偶码或对偶空间 并且有如下的维数关系成立 T 定理 任何满足下式的n维向量a均是一 n k 线形分组码的码字aH 其中满足公式的H矩阵形式不唯一 但一个码的对偶码是惟一的 T 系统码 生成矩阵具有如下形式 在码字集合不变的情况下 任何一个线性分组码都可以一对一的去对应一个系统码 对于系统码相应的一致校验矩阵 注意与仍然满足 以线性分组码的一致校验矩阵为生成产生的线性分组码称为原线性分组码的对偶码 例6 2 3一个 5 3 线
10、性分组码的 其中到的行初等变换过程为 表示第i行 5 3 线性分组码码例 由一致校验矩阵可以比较容易确定线性分组码的最小码距 定理线性分组码的最小码距为 当且仅当其一致校验矩阵H中任意列线性无关 某列线性相关 该定理实际给出了计算线性分组码最小码距的一种方法 6 2 1线性分组码的描述 6 2 2线性分组码的译码 6 2 3码例与码的重构 译码的概念 检错译码 译码器输出为当前接收向量r和r是否有差错的标志s 即 纠错译码的译码成功状态 译码器能够在达到译码码字差错概率最小条件下输出一个确切的码字 即 纠错译码的译码成功状态 译码器能够在达到译码码字差错概率最小条件下输出一个确切的码字 即 纠
11、错译码的译码失败状态 译码器不能输出一个确切的码字 通常此时的输出y与检错译码输出相同 定义 n k 线形分组码的伴随式是一个r r n k 维向量s 则传输中一定有错误发生 则传输中要么无差错发生 要么差错图案恰好为一个码字 定理可纠t错的q元线性分组码满足 伴随式纠错译码的通用译码方法 1 按最可能出现的个差错图案 计算相应的伴随式 并构造伴随式 差错图案表 2 对接收向量计算伴随式 3 查表得 4 纠错计算 6 2 1线性分组码的描述 6 2 2线性分组码的译码 6 2 3码例与码的重构 常见的线形分组码有重复码 汉明码 里德 穆勒码 戈雷码 1 汉明码 二元Hamming码是一种的完备
12、码 满足 其中列向量为全部可能的非零元组 Hamming码的对偶码是一个线性分组码 称为最大长度码 由于所有非零码字的重量均为 又称为等距码或单形 simplex 码 例6 2 4一个二元 7 4 Hamming码的系统码形式的矩阵和校验矩阵分别为 等价的编码方程为 伴随式计算方程 2 Hadamard码 Hadamard码是由Hadamard矩阵派生出的一种纠错码 阶实Hadamard矩阵由元素为 1 1的矩阵递归定义为 例如 Hadamard矩阵为正交矩阵 即中的任意不同两行 列 的点积为0 即 超正交矩阵 Hadamard矩阵中的第1列 全 1列 去掉后由于任两行的点积为 1 将Hada
13、mard矩阵元素 1 1映射为0 1 则Hadamard矩阵映射后的行向量为一个二元向量 以这些二元向量的部份或全体就构成标准0 1二元意义上的分组码 并称为Hadamard码 具体的Hadamard码的选择构成有正交码 双正交码和超正交码三种形式 A 正交码 以的全部行向量的0 1映射向量为码字 B 双正交码 以和 的全部行向量的0 1映射向量为码字 C 超正交码 以的全部行向量的0 1映射向量为码字 可以证明正交码 双正交码和超正交码均是线性分组码 例6 2 5 7 3 超正交码的超正交矩阵和生成矩阵G分别为 3 里德 穆勒 Reed Muller 阶码是一种线性分组码 满足 例6 2 6
14、的阶RM码的各个子矩阵有 码的对偶码仍是一个Reed Muller码 为码 4 戈雷码二元戈雷码是一种就纠3个错的完备线形分组码 满足 n 23k 12 由于 因此某种二元 23 12 码一定可以纠正任意小于等于3个差错 所以 6 3循环码 6 3 1循环码的多项式描述 6 3 2循环码的生成矩阵 6 3 4多项式运算电路 6 3 3系统循环码 6 3 5循环码的编码电路 6 3 6循环码的伴随多项式与检测 6 3 7BCH码与RS码 6 3 1循环码的多项式描述 6 3 2循环码的生成矩阵 6 3 3系统循环码 6 3 4多项式运算电路 6 3 5循环码的编码电路 6 3 6循环码的伴随多项
15、式与检测 6 3 7BCH码与RS码 更好的设计和实现线性分组码的方法是引入特定的数学结构来界定某一类线性分组码 循环码即是采用循环移位特性界定的一类线性分组码 6 3 1循环码的多项式描述 定义如果一个线性分组码的任意一个码字c n元组 都是另外一个码字c 的循环移位 称此线性分组码为一个循环码 将循环码的码字用多项式c x 称为码多项式 简称码式 表示后 循环码集合表示C x 例6 3 2如下确定的CA是线性循环码 CB是非循环的线性分组码 CC是非线性的循环码 定理 n k 循环码C x 中存在唯一的一个非零的 首一的和最低次为r r n 的码多项式g x 满足 g x xr gr 1x
16、r 1 g1X g0g0 0r n k并且c x 是码式当且仅当c x 是g x 的倍式 定义由上述定理确定的码式g x 称为循环码 n k 的生成多项式 因此 n k 循环码的构造是如何构造生成多项式g x 循环码由生成多项式的倍式组成 定理 g x 是 n k 循环码的生成多项式 当且仅当g x 是xn 1的r n k次因式 6 3 1循环码的多项式描述 6 3 2循环码的生成矩阵 6 3 3系统循环码 6 3 4多项式运算电路 6 3 5循环码的编码电路 6 3 6循环码的伴随多项式与检测 6 3 7BCH码与RS码 6 3 2循环码的生成矩阵和校验矩阵 n k 循环码的生成矩阵为 n k 循环码的校验矩阵为 6 3 1循环码的多项式描述 6 3 2循环码的生成矩阵 6 3 3系统循环码 6 3 4多项式运算电路 6 3 5循环码的编码电路 6 3 6循环码的伴随多项式与检测 6 3 7BCH码与RS码 6 3 3系统循环码 循环码的系统码码式为 6 3 1循环码的多项式描述 6 3 2循环码的生成矩阵 6 3 3系统循环码 6 3 4多项式运算电路 6 3 5循环码的编码电路
