第五章 差错控制与信道编码--数据通信原理.ppt

第五章差错控制与信道编码 结束放映 学习目录 学习要求 内容简介 主讲教师 刘兴顺 内容简介 差错控制就是通过某种方法 发现并纠正数据传输中出现的错误 差错控制技术是提高数据传输可靠性的重要手段之一 现代数据通信中使用的差错控制方式大都是基于信道编码技术来实现的 本章对差错控制的基本概念以及常用的信道编码方案作了比较详细的理论述 返回 结束 学习要求 1 理解差错控制的基本概念及其原理等 2 掌握信道编码的基本原理 3 了解常用检错码的特性 4 掌握线性分组码的一般特性 5 掌握汉明码以及循环码的编译码及其实现原理 6 了解卷积码的基本概念 返回 结束 学习目录 返回 5 1概述5 2常用的简单信道编码5 3线性分组码5 4卷积码 结束 5 1概述 差错控制是数据通信系统中提高传输可靠性 降低系统传输误码率的有效措施 本节将介绍差错控制和信道编码的基本原理 差错控制的实现方式等内容 5 1 1差错控制5 1 2信道编码5 1 3基于信道编码的差错控制方式 本节内容提要 5 1 1差错控制 差错控制 通过某种方法 发现并纠正传输中出现的错误 香农信道编码定理 在具有确定信道容量的有扰信道中 若以低于信道容量的速率传输数据 则存在某种编码方案 可以使传输的误码率足够小 基于信道编码的差错控制 在发送端根据一定的规则 在数据序列中按照一定的规则附加一些监督信息 接收端根据监督信息进行检错或者纠错 5 1 1差错控制 随机错误 主要由起伏噪声引起 错误码元分布比较分散且彼此统计独立 突发错误 主要由脉冲噪声引起 错误码元分布集中且彼此具有某种相关性 错误图样 差错分析 E中 0 表示正确 1 表示错误 随机错误错误图样 5 1 1差错控制 突发错误错误图样 5 1 2信道编码 在不采用信道编码的时候 进入信道的数据码元相互独立 一旦发生错误 将无法发现 例如气象台向电视台传输气象信息 不可靠数据传输系统 5 1 2信道编码 将信息序列按照k位码元的长度分成若干个信息码组M 再将信息码组输入到信道编码器 信道编码器按照一定的算法 产生一个新的n位码字A输出 n k 收端根据A中的相关性判断接收是否正确 并将其恢复成M 编码效率为k n 即所谓编码效率是指信道编码后码字中信息码元的数目与码字总码元数目之比 信道编码的基本思想 5 1 2信道编码 信道编码的冗余 信息码组M由k个二进制码元 即比特 组成 所以就有2k个M A长度为n n位长度的码字共有2n个 信道编码实质是通过一定的规则 从2n个长度为n的码字中选择了其中的2k个 每个被选中的码字称为许用码字 未被选中的2n 2k个n长的码字称为禁用码字 反映冗余大小 5 1 2信道编码 对本节开始时的例子采用 2 1 重复码 11 晴 00 雨许用码组为 11 和 00 禁用码组为 01 和 10 此时接收端可以发现单个错误 但不能纠正错误也不能发现2位错误 如下图所示 实例分析I 5 1 2信道编码 对本节开始时的例子采用 3 1 重复码 111 晴 000 雨许用码组为 111和000禁用码组为 001 010 011 100 101 110将这种编码用来检错时 可以发现两位以内的错误将这种编码用来纠错 可以纠正一位错误 如下图所示 实例分析II 5 1 2信道编码 如此译码的原因是信道中错一位的概率远远大于错多位的概率 例如要把该 3 1 重复码在有一条误码率为10 5的信道传输 则 错一位的概率为 P1 C31Pe 1 Pe 2 3 10 5 错二位的概率为 P2 C32Pe2 1 Pe 3 10 10 错三位的概率为 P3 Pe3 10 15 这种译码方法称为极大似然译码法 其基本原理为 构造一个极大似然函数L 从2k个许用码组中找到一个码字Ci 当R Ci时 函数L可以取得最大值 则认为C Ci 5 1 2信道编码 线性码和非线性码 若f 是线性函数称为线性码 若f 是非线性函数则称为非线性编码 信道编码的分类 信道编码器函数关系式为 分组码和卷积码 分组码 每个信息码组M通过运算产生对应的A 记作 n k 卷积码 每个A是由m m 2k 个M联合运算得到 记作 n k m 5 1 2信道编码 系统码和非系统码 检错码 纠错码和纠检错码 若A中的前k位或者后k位就是信息码组M 则称这种编码为系统码 否则称为非系统码 5 1 2信道编码 几个概念 码长 码字的码元数目 例如 n k 分组码的码长为n 码重 指码字中 1 的数目 记作W A 例如W 110110 4 码距 汉明距 两个等长码对应位不同的数目 记作d A B 例如A 110110 B 101011 则d A B 4 码距与码重的关系 d A B W A B 5 1 2信道编码 最小码距 最小汉明距 一个 n k 分组码的纠检错能力由其最小码距决定 当最小码距d0 e 1时 能够发现e个错误码元 当最小码距d0 2t 1时 能够纠正t个错误码元 当最小码距d0 t e 1时 能够纠正t个错误码元 同时发现e个错误码元 e t n k 分组码总共有2k个码字 记作Ai i 0 1 2k 1 则这些码字两两之间都有一个码距 定义该 n k 分组码的最小码距为 5 1 3基于信道编码的差错控制方式 反馈纠错 ARQ 方式 原理 采用检错码 接收端发现错误后 给发送端一个反馈信号 要求重新发送 直到正确为止 特点 编码效率比较高 对信道的适应能力强 重发导致信道的有效利用率较低 通信的实时性较差 应用 数据通信系统 5 1 3基于信道编码的差错控制方式 前向纠错 FEC 方式 原理 采用纠错码 收端发现错误后自动纠正 特点 无需重发 实时性好 编码效率较低 译码设备比较复杂 若错误超出纠错码纠错能力 只好将其抛弃 应用 移动通信系统 5 1 3基于信道编码的差错控制方式 混合纠错 HEC 方式 原理 采用纠检错码 是ARQ和FEC方式的折衷方案 特点 集合了ARQ和FEC的优点 在保证系统较高的有效性的同时 大幅度提高了整个系统的可靠性 应用 移动通信系统 数据传输系统 5 2常用的简单信道编码 本节内容提要 检错码在ARQ系统中使用 其生成方式简单 易于实现 检错效果较好 因此得到广泛的应用 本节将介绍奇偶校验码 行列监督码 恒比码 正反码的编译码规则 特性以及应用情况 5 2 1奇偶监督码5 2 2行列监督码5 2 3恒比码5 2 4重复码5 2 5正反码 5 2 1奇偶监督码 奇偶监督码 码重为奇数或偶数的 n n 1 系统分组码 ITU T建议 同步数据传输使用偶监督 异步数据传输使用奇监督 监督关系 假设将 n n 1 的奇偶监督码的码字记作 an 1 an 2 a1 a0 其中a0为监督码元 其余为信息码元 则各码元满足 5 2 2行列监督码 行列监督码 对水平方向 共L行 和垂直方向 共M列 同时进行奇偶监督的码 记作 LM L M 1 LM 66 50 行列监督码的一个码字 该码具有很强的纠检错能力 常用于短波散射信道等信道干扰比较严重的通信中 5 2 3恒比码 恒比码 该码的特点是码字中1 0数目恒定 亦即1 0数目之比恒定 目前我国电传通信中普遍采用3 2码 又称5中取3码 如下所示 国际上通用的ARQ电报通信系统中 采用7中取3码 5 2 4重复码 3 1 重复码两个码字为000和111 其最小码距为3 n 1 重复码也只有全0码和全1码两个码字 其最小码距为n 却有2n 2个禁用码组 随着码长的增大 其冗余也变得很大 该码随码长增加 具有很强的纠检错能力 但其编码效率的急剧下降 重复码并不是一种优秀的编码方案 仅用于速率很低的数据通信系统中 重复码 重复码只有一位信息码元 监督码元是信息码元的重复 所以仅有两个码字 5 2 5正反码 正反码 该码型多用于10单位码的前向纠错设备中 可以纠正一位错误 发现全部两个以下的错误 以及大部分两个以上的错误 其本质就是五单位码的重复 编码规则 信息码组中1的数目为奇数时 监督码是信息码的重复即正码 信息码组中1的数目为偶数时 监督码是信息码的反码 译码方法 首先将收到的码字重的信息位和监督位按对应位作模2运算 得到一个5位码组 若该码字中有奇数个1 则将其作为校验码组 若有偶数个1 则取其反码作为校验码组 然后 按照下表进行纠检错译码 5 2 5正反码 正反码错误判决表 5 3线性分组码 本节内容提要 本节将对线性分组码的特点 编译码规则以及应用情况作介绍 主要包括以下四方面内容 5 3 1基本概念5 3 2线性分组码编码5 3 3汉明码5 3 4循环码 5 3 1基本概念 1 有限域 定义了加法 和乘法 两种运算的有限集合 q个元素的有限域又称为伽罗瓦域 记作GF q 对域的逆元操作又演绎出了减法 和除法运算 域具有封闭特性 域中总包含惟一的加法恒等元 0 和乘法恒等元 1 5 3 1基本概念 域中任意元素存在惟一的加法逆元域中任意非零元都存在惟一的乘法逆元于是减法和除法运算可定义为 域中元素满足交换律 结合律和分配律运算规则 5 3 1基本概念 GF q 中定义的是模q的加法和乘法 例如GF 2 的运算表如表所示 加法运算表 乘法运算表 5 3 1基本概念 2 矢量空间 所有n维矢量组成的集合就构成了n维矢量空间Vn 矢量对矢量的加法构成一个加法交换群 即满足封闭性 结合律和交换律 有恒等元和逆元 满足分配律 满足结合律 矢量空间的性质 8PSK调制时给出的信号点矢量图 就是定义在GF 2 上的3维矢量空间V3 V3 000 001 010 011 100 101 110 111 5 3 1基本概念 集合S中存在全零矢量 0 0 0 即零元 集合S中任何两个矢量和仍在该集合中 即满足封闭性 子空间 如果n维矢量空间Vn的一个子集S 满足以下条件 则称其为Vn的一个子空间 矢量与码字的关系 一个码长为n的码字可以看成是一个有n个元素的矢量 所有2n个n长码字就构成了定义在GF 2 上的n维矢量空间Vn 对于一个 n k 线性分组码 其编码过程是从GF 2 上的n维矢量空间Vn中 寻找其中遵循某种编码规则的一个子空间 而这个字空间中的所有码字正好构成了一个加法交换群 所以线性分组码又称为群码 5 3 1基本概念 3 线性分组码性质 封闭性 具有零元 即具有全零码 记作A0 具有负元 若Ai Aj A0则称其互为码元 n k 中Ai是它本身的负元 满足结合率和交换率 5 3 2线性分组码编码 1 生成距阵 矢量的线性无关 若Vn中k个矢量A1 A2 Ak 当且仅当 i 1 2 k时下式成立 空间的基 在任意一个矢量空间或者子空间中 至少存在一组线性无关的矢量 可以张成这个空间 这一组矢量称为该空间的基 基中矢量的数目称为空间的维数 5 3 2线性分组码编码 实例分析 v1 1000 v2 0100 v3 0010 v4 0001 线性无关的 作为基 张成一个4维矢量空间V4 5 3 2线性分组码编码 生成矩阵 矩阵G的每行矢量是基中的矢量 故称之为生成矩阵 有其可以得到矢量空间中的全部矢量 上例中选取的基得到的生成矩阵恰好是4阶单位矩阵 实际上线性无关的行矢量都可以作为生成矩阵的行矢量 2 编码原理 线性分组码标记 n k 线性分组码 其码字通常记作 A an 1an 2 a0 1 n 信息码组M记作 M mk 1mk 2 m1m0 1 k 5 3 2线性分组码编码 生成矩阵G记作 编码过程 5 3 2线性分组码编码 实例 假设一个 6 3 分组生成矩阵为 编码过程为 5 3 2线性分组码编码 该 6 3 码是非系统码 信息元m2 m0 m1分别出现在码字A的第1 3 5位 而2 4 6位是编码器产生的监督码元其码表为 5 3 2线性分组码编码 生成矩阵典型化 实例分析 3 系统码编码原理 编码过程 5 3 2线性分组码编码 6 3 系统分组码表 监督元与信息元之间的一般关系 5 3 2线性分组码编码 注意到系统码中前k位即信息元 将其写成线性方程组的形式 监督关系 5 3 2线性分组码编码 监督矩阵 监督关系一般表达 或 生成矩阵典型阵一般形式 5 3 2线性分组码编码 n k 分组码码字可表示为 n k 码的一般编码过程 A an 1an 2 an kar 1 a1a0 mk 1mk 2 m0ar 1 a1a0 对上式两边同时进行矩阵转置得 5 3 2线性分组码编码 也即 此时的系数矩阵 即监督矩阵为 5 3 2线性分组码编码 生成矩阵和监督距阵的关系 n k 码的一般编码过程 根据需要选定一监督关系确定H阵 求由H距阵和 阵的关系确定G阵 由A M G生成所有码字 5 3 2线性分组码编码 伴随式S和错误图样E的关系 伴随式 二者并不是一一对应的关系 因为错误图样有2n种表现形式 而伴随式仅有2r种表现形式 注意r n k n 且其中S 0说明传输无错 这在该 n k 分组码用于检错时已足够 但发生了错误却不能检出是完全有可能的 例如封闭性错误 4 伴随式与检错原理 5 3 2线性分组码编码 6 3 分组码的监督矩阵为 实例分析 伴随式 5 3 2线性分组码编码 6 3 分组码伴随式计算电路 5 3 3汉明码 将监督矩阵记成列矢量的形式 H h0h1 hn 2hn 1 则 汉明码定义 伴随式和错误图样的关系 单个错误时的伴随式恰好与H的一个列矢量对应 只要H的各个列矢量不为0矢量 且各不相同 则可以纠正单个错误 5 3 3汉明码 汉明码的另一种描述方式 对于任何的整数 必存在一个 n k 汉明码 码长n和监督元数目r n k满足n 2r 1 汉明码特点 可以纠正一位传输错误 且d0 3 码长和监督员的关系 n 2r 1 实例分析 7 4 汉明码 首先其监督矩阵 此时监督矩阵为H3 7 3位二进制码元的组合有8种 000 001 010 011 100 101 110 111 其中不全为零的7个正好可用作监督矩阵的列 可得到监督矩阵 5 3 3汉明码 任意调换监督矩阵各列位置并不影响码的纠错能力 将其转化成典型阵的形式 并由其可以得到生成矩阵G 由A MG得到其所有的码字 如下表所示 5 3 3汉明码 假设发送端的码字是A15 1111111 传输过程中第4位a3出现了错误 即接收的码字是B 1110111 此时对应的伴随式为 5 3 3汉明码 下表给出了该 7 4 汉明码单个错误的错误图样与其对应的伴随式 可以发现伴随式正是监督矩阵的每一列 且该列的位置恰好是码元出错的位置 由于S不时全零 可判断传输出错 而ST 011 T 是监督矩阵H的第4列 这正是错误码元发生的位置 因此可以得到错误图样为E 0001000 进而按B E即可纠错 5 3 3汉明码 完备性定义 汉明码完备码性 5 3 4循环码 一个 7 3 系统循环码码表如下所示 1 基本概念 一类具有循环移位特性的线性分组码 即其中的一个码字经过循环移位后仍然是该分组码的码字 定义 5 3 4循环码 例如A4 0111001 对应的码多项式为 码多项式 n k 循环码中 为了便于描述与计算 经常使用n 1次码多项式来表示码字 码字A an 1an 2 a1a0 它对应的码多项式为 A4向左循环移1位得A7 1110010 这相当于将A4 x 乘以x 即 5 3 4循环码 对于 7 3 循环码的码多项式 其最高次数不能超过6 解决该问题的办法是对上式作模x7 1运算 A7向左循环移1位得A6 1100101 但若将A7 x 乘以x得到多项式为 其计算过程如下 5 3 4循环码 2 生成多项式和生成矩阵 n k 循环码中的r n k次码多项式 其次数最低 0元除外 其它所有的码多项式都能被g x 整除 并且g x 是xn 1的一个因式 生成多项式g x 例如本节前面给出的 7 3 循环码 其生成多项式为 5 3 4循环码 若g x 含有 x 1 因式 对应的 n k 系统循环码 能够检出所有奇数个错误 n k 系统循环码检错能力与g x 的关系 若g x 含有常数项1因式 且不能整除xe 1 则对应的 n k 系统循环码 能够检出所有的两位错误 若g x 含有常数项1因式 对应的 n k 系统循环码 能够检出所有突发长度r的突发错误 并且对突发长度等于r 1的突发错误的漏检率为2 r 1 对突发长度大于r 1的突发错误的漏检率为2 r 5 3 4循环码 CRC 12 标准生成多项式 CRC 16 CRC CCITT CRC 32 5 3 4循环码 g x xg x x2g x xk 1g x 是 n k 循环码的k个线性无关的码字 所以可得其上乘距阵G 用码多项式表示G的各行 生成矩阵G 若信息码组M mk 1mk 2 m0 则 5 3 4循环码 上式同时提供了循环码的一种编码方法 但由其得到的循环码是非系统码 因为此时生成矩阵不是典型阵 例如本节前面给出的 7 3 循环码 将该矩阵典型化之后 再按照A MG编码才能得到表本节前面给出的系统 7 3 循环码 实际应用中 系统循环码的编译码通常是由g x 经过简单的代数运算来实现 5 3 4循环码 系统 n k 循环码码字 编码原理 用码多项式来表示为 3 编码 A an 1an 2 an kar 1 a1a0 mk 1mk 2 m0ar 1 a1a0 5 3 4循环码 式中M x 是信息码组码多项式 所以只需要确定r x 已知循环码的所有码字都能够被g x 整除 r x 可由下式确定 n k 循环码的生成多项式为 编码器 其中r n k 则该 n k 系统循环码的编码电路如下图所示 5 3 4循环码 r级线性移位寄存器的初始状态为全零 所有开关均向下连通 在寄存器时钟的控制下进行k次移位 输出M x 的系数 即信息码组 同时实现除法电路的功能 编码器工作过程 5 3 4循环码 所有开关向下连通 输入下一组信息重复上述过程 实例分析 所有开关均倒向上方连通 在寄存器时钟的控制下再经过r n k次移位 将监督元输出到信道 本节前面给出的 7 3 循环码生成多项式 g x x4 x2 x 1由其可得编码电路如下图所示 5 3 4循环码 假设M 110 编码器工作过程如下表所示 5 3 4循环码 现在检验上表编码结果 因为M 110 所以 即所得的码字为A 1100101 5 3 4循环码 系统循环码的每一个码字都能够被生成多项式g x 整除 检错译码原理 发送端发送的码字为 3 译码 接收的码字为 错误图样 伴随式 5 3 4循环码 可以证明 若S等于0判定传输无错 否则判定传输出错 检错译码原理图 5 3 4循环码 寄存器置零 开关S向下连通 在寄存器时钟的控制下经n次移位后将接收码字B输入 此时寄存器中存储的即伴随式 n k 循环码伴随式计算电路 其工作过程如下 将开关向上打开 经r n k次移位读出伴随式 5 3 4循环码 纠错译码原理 确定循环码的纠错能力 根据 模g x 计算伴随式 若S x 则判定传输出错 根据 模g x 找到伴随式对应的错误图样 由A x B x E x 纠错 5 4卷积码 本节内容提要 卷积码是一类非线性有记忆编码 本节将简要介绍卷积码的编译码原理 5 4 1