通信原理 第11章 差错控制编码.doc

通信原理 第11章差错控制编码 信道编码的目的和方法 差错控制 信道分类从差错控制角度看 随机信道错码的出现是随机的 突发信道错码是成串集中出现的 混合信道既存在随机错码又存在突发错码 差错控制技术的种类 举例 <a name=baidusnap0></a>明天</B>1400～1600开会 明天</B>1000～1600开会 明天</B>下午1400～1600开会 明天</B>下午1000～1600开会 明天</B>下午1400～1600开两小时会 明天</B>下午1000～1600开两小时会 基本概念 差错控制编码纠错编码 监督码元在发送端在信息码元序列中增加一些差错控制码元它们称为监督码元 多余度就是指增加的监督码元多少例如若编码序列中平均每两个信息码元就添加一个监督码元则这种编码的多余度为13 编码效率 码率 设编码序列中信息码元数量为k总码元数量为n则比值kn 就是码率 冗余度监督码元数 n-k 和信息码元数 k 之比 差错控制以降低信息传输速率为代价换取提高传输可靠性 停止等待ARQ系统 系统是工作在半双工状态时间没有得到充分利用传输效率较低 拉后ARQ系统 需要对发送的数据组和答复进行编号以便识别需要双工信道 选择重发ARQ系统 只重发出错的数据组进一步提高了传输效率 ARQ的主要优点和前向纠错方法相比 监督码元较少即能使误码率降到很低即码率较高 检错的计算复杂度较低 检错用的编码方法和加性干扰的统计特性基本无关能适应不同特性的信道 ARQ的主要缺点 需要双向信道来重发不能用于单向信道也不能用于一点到多点的通信系统 因为重发而使ARQ系统的传输效率降低 在信道干扰严重时可能发生因不断反复重发而造成事实上的通信中断 在要求实时通信的场合例如电话通信往往不允许使用ARQ法 ARQ系统的原理方框图 分组码举例 设有一种由3位二进制数字构成的码组若全部用来表示天气则可以表示8种不同天气 例如000晴001云 010阴011雨 100雪101霜 110雾111雹 其中任一码组在传输中发生错码将变成另一个信息码组接收端无法发现错误 若只准许使用4种来传送天气 000＝晴 011＝云 101＝阴 110＝雨 检错和纠错 上面这种编码只能检测错码不能纠正错码要能够纠正错误还要增加多余度 若规定许用码组只有两个000晴111雨其他都是禁用码组则能够检测两个以下错码或能够纠正一个错码 分组码＝信息码＋监督码 分组码的符号 n k n － 码组的总位数又称为码组的长度码长 k － 码组中信息码元的数目 n – k ＝ r － 码组中的监督码元数目或称监督位数目 总的码组数2n个许用码组2k个禁用码组2r个 编码的任务从总码组中选出许用码组 译码的任务用相应的规则判断校正码组 分组码的码重和码距 码重把码组中1的个数目称为码组的重量 码距把两个码组中对应位上数字不同的位数称为码组的距离码距又称汉明距离 000＝晴011＝云101＝阴110＝雨 4个码组之间任意两个的距离均为2 最小码距d0 各个码组之间距离的最小值 上面的编码的最小码距d0 2 每个码组的3个码元的值 a2 a1 a0 就是此立方体各顶点的坐标 码距各顶点之间沿立方体各边行走的几何距离 n维空间中单位正多面体顶点间的汉明距离 码距和检纠错能力的关系 为检测e个错码要求最小码距 d0 e 1 为了纠正t个错码要求最小码距d0 2t 1 为纠正t个错码同时检测e个错码要求最小码距 113 纠错编码的性能 偶数监督码监督位只有1位它使码组中1的数目为偶数 式中a0为监督位其他位为信息位 奇数监督码 特点 能够检测奇数个错码无法检测偶数个错码 适合检随机差错连续多个突发性误码不能检知 没有纠错能力 二维奇偶监督码的性能 有可能检测偶数个错码 由于方阵码只对构成矩形四角的错码无法检测故其检错能力较强使Pe下降至原来的1％～001％ 适于检测突发错码 二维奇偶监督码不仅可用来检错还可以用来纠正一些错码 例如仅在一行中有奇数个错码时 在恒比码中每个码组均含有相同数目的1或01的数目与0的数目之比保持恒定 这种码在检测时只要计算接收码组中1的数目是否对就知道有无错码 恒比码的主要优点是简单和适于用来传输电传机或其他键盘设备产生的字母和符号对于信源来的二进制随机数字序列这种码就不适合使用了 正反码的编码 监督位数目与信息位数目相同监督码元与信息码元相同或者相反则由信息码中1的个数而定 其编码规则为 当信息位中有奇数个1时监督位是信息位的简单重复 当信息位有偶数个1时监督位是信息位的反码 例如若信息位为11001则码组为1100111001 若信息位为10001则码组为1000101110 可纠错长度为10的正反码具有纠正1位错码的能力并能检测全部2位以下的错码和大部分2位以上的错码 基本概念 代数码利用代数关系式产生监督位的编码 线性码信息位和监督位是由一些线性代数方程联系着的 线性分组码按照一组线性方程构成的分组码 汉明码 能够纠正1位错码且编码效率较高的一种线性分组码 偶数监督码使用了一位监督位a0 接收端解码时计算 若S 0就认为无错码若S 1就认为有错码 监督关系式 校正子S 一个校正子检错两个校正子可纠错 校正子的4中组合 00011011能表示4种不同的信息若用其中1种组合表示无错则其余3种组合就有可能用来指示一个错码的3种不同位置 r个校正子能指示1位错码的 2r – 1 个可能位置 若码长为n信息位数为k则监督位数r＝n－k 用r个监督位构造出r个监督关系式来指示1位错码的n种可能位置则要求 设分组码 n k 中k 4为了纠正1位错码要求监督位数 r 3若取 r 3则n k r 7 用a6 a5 a0表示这7个码元用S1S2和S3表示3个监督关系式中的校正子 仅当一位错码的位置在a2 a4a5或a6时校正子S1为1否则S1为零a2 a4a5和a6四个码元构成偶数监督关系 同理 无错码监督位应使上3式中S1S2和S3的值为0 编码给定信息位后可以直接按上式算出监督位 解码 计算 查表判断错码情况 若接收码组为0000011计算可得S1 0S2 1S3 1查表可知在a3位有1错码 7 4 汉明码的最小码距d0 3能够纠正1个错码或检测2个错码 由于码率kn n - r n 1 – rn故当n很大和r很小时码率接近1汉明码是一种高效码 H矩阵监督矩阵 上面 7 4 汉明码的例子有 改写为 上式中已经将简写成 表示成矩阵形式 简记为 H AT 0T 或　　A HT 0 H AT 0T 或　　A HT 0 式中 A [a6 a5 a4 a3 a2 a1 a0] 0 [000] H称为监督矩阵 只要监督矩阵H给定编码时监督位和信息位的关系就完全确定了 H的行数就是监督关系式的数目r H的每行中1的位置表示相应码元之间存在的监督关系例如H的第一行1110100表示监督位a2是由a6 a5 a4之和决定的 H矩阵可以分成两部分 P为r k阶矩阵Ir为r r阶单位方阵 将具有[P Ir]形式的H矩阵称为典型阵 H矩阵的各行应该是线性无关的否则将得不到r个线性无关的监督关系式 写成矩阵形式 Q为一个k r阶矩阵Q PT 在信息位给定后用信息位的行矩阵乘矩阵Q就产生出监督位 将Q的左边加上1个k k阶单位方阵就构成1个矩阵G G称为生成矩阵因为由它可以产生整个码组 具有[IkQ]形式的生成矩阵称为典型生成矩阵 由典型生成矩阵得出的码组A中信息位的位置不变监督位附加于其后这种形式的码称为系统码 G矩阵的性质 G矩阵的各行是线性无关的 G的各行本身就是一个码组因此如果已有k个线性无关的码组则可以用其作为生成矩阵G并由它生成其余码组 错码矩阵和错误图样 发送的码组A 设接收码组B 发送码组和接收码组之差为 B – A E 模2 它就是传输中产生的错码行矩阵称为错误图样 B A E 例若发送码组A [1000111] 错码矩阵E [0000100] 则接收码组B [1000011] 校正子矩阵S 当接收码组有错时E 0将B当作A代入公式 A H T 0 后该式不一定成立 B