复制成功
  • 图案背景
  • 纯色背景
  •   |  注册
  • /
  • 批注本地保存成功,开通会员云端永久保存 去开通
  • 信息论与编码技术(第2版)CHAP6简明教程PPT课件

    下载积分:10

    内容提示: 第六章第六章 信信 道道 编编 码码 • 在通信系统中, 要提高信息传输的有效性, 我们将信源的输出经过信源编码用较少的符号来表达信源消息, 这些符号剩余度很小, 效率很高, 但对噪声干扰的抵抗能力很弱。• 信息传输要通过各种物理信道, 由于干扰、 设备故障等影响, 被传送的信源符号可能会发生失真, 使有用信息遭受损坏接收信号造成误判这种在接收端错误地确定所接损坏, 接收信号造成误判。 这种在接收端错误地确定所接收的信号叫做差错。• 为了提高信息传输的准确性, 使其具有较好的抵抗信道中噪声干扰的能力, 在通信系统中需要采用专门的检、 纠错误方法, 即...

    亚博足球app下载格式:PPT| 浏览次数:9| 上传日期:2015-06-17 19:19:45| 亚博足球app下载星级:
    第六章第六章 信信 道道 编编 码码 • 在通信系统中, 要提高信息传输的有效性, 我们将信源的输出经过信源编码用较少的符号来表达信源消息, 这些符号剩余度很小, 效率很高, 但对噪声干扰的抵抗能力很弱。• 信息传输要通过各种物理信道, 由于干扰、 设备故障等影响, 被传送的信源符号可能会发生失真, 使有用信息遭受损坏接收信号造成误判这种在接收端错误地确定所接损坏, 接收信号造成误判。 这种在接收端错误地确定所接收的信号叫做差错。• 为了提高信息传输的准确性, 使其具有较好的抵抗信道中噪声干扰的能力, 在通信系统中需要采用专门的检、 纠错误方法, 即差错控制。 • 差错控制的任务是发现所产生的错误、 并指出发生错误的信号或者校正错误, 差错控制是采用可靠、 有效的信道编码方法来实现的。• 信道编码器要对信源编码输出的符号进行变换, 使其尽量少受噪声干扰的影响, 减少传输差错, 提高通信可靠性。少受噪声干扰的影响减少传输• 本章要讨论的问题是在符号受到噪声干扰的影响后, 如何从接收到的信号中恢复出原送入信道的信号、 确定差错概率是多少等等。• 本章首先讨论信道编码的基本概念和分类, 在此基础上再讨论两类主要的信道编、 译码方法, 即线性分组码与卷积码。错提高信可靠性 6. 1 信道编码的概念• 进行信道编码是为了提高信号传输的可靠性, 改善通信系统的传输质量, 研究信道编码的目标是寻找具体构造编码的理论与方法。• 在理论上, 香农第二定理已指出, 只要实际信息传输率(信道容量), 则无差错的信道编、 译码方法是存在的。• 从原理上看, 构造信道码的基本思路是根据一定的规律在待发送的信息码元中人为地加入一定的多余码元(称为监督码), 以引入最小的多余度为代价来换取最好的抗干扰性能。RC 6.1.1 信道编码的分类• 由于实际信道存在噪声和干扰, 使发送的码字与信道传输后所接收到的码字之间存在差错。 在一般情况下, 信道中噪声或干扰越大, 码字产生差错的概率也就越大。• 有些实际信道既有独立随机差错也有突发性成串的差错,这种信道称混合差错信道, 实际的移动信道属于此类信道。• 对不同的信道需要设计不同类型的信道编码方案, 按照信道特性进行划分, 信道编码可分为: 以纠独立随机差错为主的信道编码、 以纠突发差错为主的信道编码和纠混合差错的信道编码。• 从功能上看, 信道编码可分为检错(可以发现错误)码与纠错(不仅能发现而且能自动纠正)码两类, 纠错码一定能检错, 检错码不一定能纠错, 平常所说的纠错码是两者的统称。 根据信息码元与监督码元之间的关系, 纠错码分为线性码和非线性码。 线性码——信息码元与监督码元之间呈线性关系, 它们的关系可用一组线性代数方程联系起来。 非线性码——信息码元与监督校元之间不存在线性关系。按照对信息码元处理的方法的不同按照对信息码元处理的方法的不同, 纠错码分为分组码和卷积码。 分组码----把信息序列以每 个码元分组, 然后把每组 个信息元按一定规律产生 个多余的监督码元, 输出序列每组长为, 则每一码字的个信息位有关, 与别的码字的信息位无关, 通常记分组码为。(,)nk纠错码分为分组码和个校验元只与本码字的kkr()nkrrk 其中分组码又可分循环码和非循环码: 对循环码而言, 其码书的特点是, 若将其全部码字分成若干组, 则每组中任一码字中码元循环移位后仍是这组的码字; 对非循环码来说, 任一码字中的码元循环移位后不一定再是该码书中的码字。 卷积码----把信息序列以每 (通常较小)个码元分段, 编码器输出该段的监督码元关, 而且还与其前面L段的信息码元有关, 故记卷积码为。按照每个码元的取值来分, 可有二元码和多元码。 由于目前的传输或存储系统大都采用二进制的数字系统, 所以一般提到的纠错码都是指二元码。不但与本段的个信息元有0kn0()rk0k0( ,n k L, ) 综上所述, 纠错码分类如图6.1.1所示。图6.1.1 纠错码的分类 6.1.2 与纠错编码有关的基本概念在通信系统的接收端, 若接收到的消息序列符号序列不一样, 例如有两位不同, 即出现两个错误, 这种错误是由信道中的噪声干扰所引起的。为了说明如何描述这种错误及相应编码方法的性质为了说明如何描述这种错误及相应编码方法的性质, 我们先介绍一些基本概念。(1)码长、 码重和码距码字中码元的个数称为码字的长度, 简称码长, 用码字中非“0”码元的个数称为码字的汉明重量(简称码重,记作 )。 对二进制码来说, 码重 就是码字中所含码元“1”的数目, 例如码字“110000”, 其码长和发送的码,与, 而中我们RC(110000)R(100001)CRC表示。, 码重nWW6n 2W  • 两个等长码字之间对应码元不相同的数目称为这两个码组的汉明距离(简称码距)。 例如码字“110000”与“100001”,它们的汉明距离。• 在某一码书中, 任意两个码字之间汉明距离的最小值称为该码的最小距离, 即:d为该码的最小距离, 即:mind2D C例如: 码组的最小码距。• 从避免码字受干扰而出错的角度出发, 总是希望码字间有尽可能大的距离, 因为最小码距代表着一个码组中最不利的情况, 从安全出发, 应使用最小码距来分析码的检错、纠错能力。 因此, 最小码距是衡量该码纠错能力的依据,是非常重要的一个参数。minmin(,) ,C CijijijdD C CCCC  {0111100, 1011011, 1101001}Cmin3d (2) 错误图样• 在二元无记忆序列来描述。 设发送码字为次扩展信道中, 差错的形式也可以用二元()nCcc c, 接收码字为, 两者的差别:N2 12 1r r()nRr2 1e e()nEeCR称为错误图样。• 如错误图样中的第 位为“1”( ), 则表明传输过程中第i位发生了错误。• 例如:, 而中的第“2”位和第“6”位出现了错误。, 则, 可知接收的消息序列1ie i(110000)R(100001)C(010001)E C RR (3) 重复码和奇偶校验码前面已述信道编码的任务是构造出以最小多余度的代价换取最大抗干扰性的“好“码。 下面, 从直观概念出发,说明多余度与抗干扰性能的关系, 介绍两种极端情况:一是高可靠性, 低有效性的重复码; 二是高有效性, 低是高可靠性, 低有效性的重复码; 二是高有效性, 低可靠性的奇偶校验码。1)重复码构成重复码的方法是当发送某个信源符号 时, 不是只发一个, 而是连续重发多个, 连续重发的个数越多, 重复码的抗干扰能力就越强, 当然效率也越低。ia • 不重复时为(1, 1)重复码, 如图6.1.2所示: 图6.1.2 发送码元不重复对这种情况可得结论: 不重复, 方法简单, 但没有任何抗干扰能力, 既不能发现, 更不能纠正错误。• 重复一次时为(2, 1)重复码, 如图6.1.3所示: 图6.1.3 发送码元重复一次 对这种情况可得结论: 重发一次, 效率降低一倍, 可以换取在传输过程中允许产生一个错误(收端能发现它), 但不能纠正这个错误。• 重复二次时为(3, 1)重复码, 如图6.1.4所示:图6.1.4 发送码元重复二次(3, 1)重复码用“000”来代表信息“0”, 用“111”来代表信息“1”, 码本中共有两个码字。 显然, 所增加的两位码元并不会增加信息, 是多余的, 因而使信息传输率降低。 此外, 除了传送信息的“000”和“111”两种组合之外, 还有六种组合{001, 010, 011,100, 101, 110}没有利用。 当信道上信噪比足够大时,我们可以认为码字中产生的错误一般不多于一个码元, 那么如果接收到“001”“010”么, 如果接收到001 、010 、实际传输的是“000”; 同样, 如接收到“011”、 “101”、“110”, 则可判定为“111”。 因此多余码元使我们可检出一个错, 并且还可纠正这个错误, 这样就提高了信息传输的可靠性。对这种情况可得结论: 重发二次, 效率降低二倍, 但换取了可纠正一个差错或发现两个差错的性能改善。“100”100 , 我们就可判定我们就可判定 2) 奇偶检验码奇偶校验是一种最基本的校验方法。 构成奇偶检验码的方法是在每 个二进制信息位后加上一个奇(偶)监督位(或称校验位), 使码长, 同时使码中“1”的个数恒为奇数(或偶数)如图6 1 5所示在奇偶校验码中(或偶数), 如图6.1.5所示。 在奇偶校验码中, 监督位, 它是一种码重 为奇数(或偶数)的系统分组码。W监督位k1nk 11图6.1.5 奇偶校验码r  奇偶校验又可以分为奇校验和偶校验。 其规则如下:• 奇校验----如果信息码元中“1”值的个数为奇数个, 则校验码元值为“0”; 如果信息码元中“1”值的个数为偶数个,则校验码元值为“1”。 即所有信息码元与校验码元的模二和等于“1”。• 偶校验----如果信息码元中“1”值的个数为偶数个, 则校验码元值为“0”; 如果信息码元中“1”值的个数为奇数个,则校验码元值为“1”。即所有信息码元与校验码元的模二和等于“0”。根据奇偶校验的规则, 校验位值的确定方法如表6.1.1所示。 表6.1.1 奇偶校验规则表校验方式信息位中“1”值的个数校验位值奇数个0奇校验偶数个1偶校验偶数个0奇数个1 • 例如, 在七位信息码中, 字符A的代码为1000001, 其中有两位码元值为“1”。 若采用奇校验编码, 由于这个字符的七位代码中有偶数个“1”, 所以校验位的值应为“l”,其8位组合代码为: 10000011, 前7位是信息位, 最右边的1位是校验位。 同理, 若采用偶校验, 可得奇偶校验位的 位是校验位同若采用偶校验的值为“0”, 其8位组合代码为: 10000010。 这样在接收端对码字中“1”的个数进行检验, 如有不符, 就可断定发生了差错。• 在接收端进行校验时, 如采用奇校验编码, 当接收到的字符经检测其八位代码“l”的个数为奇个数时, 则被认为传输正确; 否则就被认为传输中出现差错。 然而, 如果在传输中有偶数位出现差错, 用此方法就检测不出来了。可得奇偶校验位 • 所以, 奇偶校验方式只能检测出位代码中出现的任意奇数个错误, 如果代码中错码数为偶数个, 则奇偶校验不能奏效。 由于奇偶校验码容易实现, 所以当信道干扰不太严重以及码长不很长时很有用, 特别是在计算机通信网的数据传送中经常应用这种检错码。传中常应用种检错码• 奇偶校验编码如果是在一维空间上进行, 则是简单的“水平奇偶校验” 或“垂直奇偶校验” 码, 如果是在二维空间上进行, 则是“水平垂直奇偶校验码” 。 • 垂直奇偶校验在垂直奇偶校验编码中, 先将整个要发送的信号序列划分成长度为的若干个组, 然后对每组按码元中“1”的个数为奇数或偶数的规律, 在其后附加上一位奇偶校验位加上一位奇偶校验位, 如表6.1.2所示。表6.1.2中将70个码元组成的信号序列划分成长度为7的10个组, 每组按顺序一列一列地排列起来,然后对垂直方向的码元进行奇偶校验(假设采用偶校验), 得到一行校验位, 附加在其他各行之后,然后按列的顺序进行传输。如表6 1 2所示 码元位分组123456789101100011100120110100011表6.1.2 垂直奇偶校验3000101110041000100000500011011016011100100070110101001偶校验位0111101010 • 在垂直奇偶校验编码和校验过程中, 用硬件方法或软件方法来实现上述连续的奇偶校验运算都非常容易, 而且在发送时可以边发送边产生校验位, 并插入发送, 在接收时边接收边进行校验后去掉校验位。• 垂直奇偶校验方法的编码效率为:垂直奇偶校验方法的编码效率为:• 这种奇偶校验方法能检测出每个分组中的所有奇数位的错,但检测不出偶数位的错。 对于突发性错误, 由于出错码元为奇数个或偶数个的概率各占一半, 因而对差错的漏检率接近于1/2。1kk  • 水平奇偶校验为了降低对突发错误的漏检率, 可以采用“水平奇偶校验” , 它是以分组为单位, 对一组中的相同位的码元进行奇偶校验。 在水平奇偶校验中, 把信号序列先以适当的长度划分成个组, 每组位码元, 并把每组按顺序一列一列地排列起来如表6 1 3所示排列起来, 如表6.1.3所示然后对水平方向的码元进行奇偶校验, 得到一列校验位,附加在其他各列之后, 最后按列的顺序进行传输。 表中的信号序列共分成10个组, 每组有7个码元。 传输时按列的顺序先传送第l组, 再传送第2组……, 最后传送第11列即校验位列(本例采用偶校验)。 因此, 在信道中传送的二进制信号序列为: 10010000100011……1101101。 码元位分组偶校验位12345678910110001110011201101000111表6.1.3 水平奇偶校验300010111000410001000000500011011011601110010000701101010011 • 水平奇偶校验的编码效率是:• 水平奇偶校验不但可以检测各组同一位上的奇数位错, 而且可以检测出突发长度小于或等于(每组的码元数)的所有突发性错误(突发性错误是指一连串的码元均出错)突发性错误(突发性错误是指一连串的码元均出错), 因为传输时按组的顺序发送, 发生长度小于或等于的突发性错误必然分布在不同行中, 每行最多只有一位出错, 所以可以检出差错。• 水平奇偶校验的漏检率比垂直奇偶校验码要低。 但是, 在实现水平奇偶校验时, 不论采用硬件方法还是软件方法,都不能在发送过程中边产生边插入奇偶校验位, 而必须等待要发送的完整数据信号序列到齐后, 才能确定校验位,也就是要使用一定的存储空间。 因此, 其编码和检测的实现都要复杂一些。因为1pp • 水平垂直奇偶校验同时进行水平奇偶校验和垂直奇偶校验就构成二维的“水平垂直奇偶校验码” , 如表6.1.4所示。其具体实现过程是: 先将整个欲发送的信号序列其具体实现过程是: 先将整个欲发送的信号序列划分成长度为的若干个组; 然后对每个组按码元中“1”的个数为奇或偶数的规律, 在其后附加上一位奇偶校验位(表中采用偶校验); 再对每个字符的相同位按“1”的个数为奇或偶数的规律, 增加一个校验位(表中采用偶校验)。 码元位分组偶校验位12345678910110001110011201101000111表6.1.4 水平垂直奇偶校验300010111000410001000000500011011011601110010000701101010011偶校验位01111010100 • 水平垂直奇偶校验的编码效率为:• 这种方法能检测出所有3位或3位以下的错误, 因为在这种情况下, 至少会在某一行或某一列上出现一位错, 这时错误就能被检测到; 还能检测出奇数位错、 突发长度小于或等于的突发性错以及很大一部分偶数位错。 一些试验测量表明, 这种方式的编码可使误码率降至原始误码率的百分之一到万分之一。 另外, 水平垂直奇偶校验不仅可检错,还可用来纠正部分差错。• 上述奇偶校验码中, 水平奇偶校验码、 垂直奇偶校验码是单纯检错码, 而水平垂直奇偶校验码则还具有有限的纠错能力, 但多数情况下只用于检错。 11k pkp 6.1.3 检错与纠错原理• 检错、 纠错的目的是要根据信道接收端接收到的信息序列来判断是否就是发送的序列, 如果有错则尽可能纠正其中的错误。• 要纠正传输差错, 首先必须检测出错误。 而要检测出错误,常用的方法是将发送端要传送的信息序列(常为二进制序常用的方法是将发送端要传送的信息序列(常为二进制序列)中截取出长度相等的码元进行分组, 每组长度为k, 组成k位码元信息序列, 并根据某种编码算法以一定的规则在每个信息组的后面产生 个冗余码元, 由冗余码元和信息码元一起形成“位编码序列” , 即信号码字位的码字比信息码长(有码是冗余编码, 如图6.1.6所示。RR,个码元), 因而纠错编MrnCnnkr 图6.1.6 纠错编码• 译码就是利用校验关系进行检错、 纠错的, 在接收端收到的位码字中, 信息码元与冗余码元之间也应符合上述编码规则, 并根据这一规则进行检验, 从而确定是否有错误。这就是差错控制的基本思想。• 我们把这种将信息码元分组, 为每组码附加若干校验码的编码称为分组码。 在分组码中, 校验码元仅校验本码组中的信息码元。• 分组码一般用符号表示, 其中 是每组二进制信息码元的数目, 是编码组的长度(简称码长), 即编码组的总位数,为每码组中的校验码元(或称监督位)数目。nkr( , )n kkn • 通常, 将分组码规定为具有如图6.1.7所示的结构。 图中前面 位( )为信息位, 后面附加 个( )校验位。k1,,nraar10,,raa图6.1.7 分组码的结构• 实现检纠错常用的基本方法除了前面介绍的和奇偶校验方法外, 还有等重码(或定比码)方法:• 奇偶校验方法。 增加偶(或奇)校验位使得对消息序列言校验方程成立, 当校验位数增加时, 可以检测到差错图重复码方法而样的种类数也增加, 但同时码率减小。nM •重复码方法。 重复消息位使之可以检测出任意小于 个差错的错误图样。• 等重码方法。 设计码字中的非“0”符号个数(若是二进制码则为“1”的个数)恒为常数, 使码书 由全体重量恒等的长矢量组成。 表6 1 5所示为一种用于表示数字“0”到“9”长矢量组成。 表6.1.5所示为的五中取三等重码(所有码字的码重都等于“3”)的例子。表6.1.5 五中取三等重码nnCn种用于表示数字0 到9• 显然五中取三等重码可以检测出全部奇数位差错, 对某些码字的传输则可以检测出部分偶数位差错。123456789001011110011011011010001111010111100011101001101101 • 对于纠错码, 其抗干扰能力完全取决于码书C中许用码字之间的距离。 码的最小距离越大, 则码字间的最小差别越大, 抗干扰能力就越强, 即受较强的干扰仍不会造成许用码字之间的混淆。• 差错控制编码是用增加码元数, 利用“冗余” 来提高抗干扰能力的, 即是以降低信息传输速率为代价来减少错误的,或者说是用削弱有效性来增强可靠性的。 6.1.4 检错与纠错方式和能力(1) 检错与纠错方式•自动请求重发方式----用于检错的纠错码在译码器输出端给出当前码字传输是否可能出错的指示, 当有错时按某种协议通过一个反向信道请求发送端重传已发送的全部或部分码字, 这种纠错码的应用方式称为自动请求重发方式(ARQ, Automatic-Repeat-reQuest)。方式(•前向纠错方式----用于纠错的纠错码在译码器输出端总要输出一个码字或是否出错的标志, 这种纠错码的应用方式称为前向纠错方式(FEC, Forward-error control)。•另外用于检错与纠错的方式还有混合纠错(HEC, Hybrid Error Correction)。•图6.1.8所示为上述几种检错与纠错方式示意图, 图中有斜线的方框表示在该端检出错误。p) 图6.1.8 差错控制的工作方式• ARQ方式: 发送端用编码器对发送数据进行差错编码, 通过正向信道送到接收端, 而接收端经译码器处理后只是检测有无差错, 不作自动纠正。 如检测到差错, 则利用反向信道反馈信号, 请求发送端重发有错的数据单元, 直到接收端检测不到差错为止。 • FEC方式: 发送端用编码器对发送数据进行差错编码, 在接收端用译码器对接收到的数据进行译码后检测有无差错,通过按预定规则的运算, 如检测到差错, 则确定差错的具体位置和性质, 自动加以纠正, 故称为“前向纠错” 。• HEC方式: 是检错重发和前向纠错两种方式的混合。 发送端用编码器对发送数据进行便于检错和纠错的编码端用编码器对发送数据进行便于检错和纠错的编码, 通过正向信道送到接收端, 接收端对少量的接收差错进行自动前向纠正, 而对超出纠正能力的差错则通过反馈重发方式加以纠正, 所以是一种纠检结合的混合方式。(2) 检错与纠错能力一个纠错码的每个码字都可以形成一个汉明球, 因此要能够纠正所有不多于 位的差错, 纠错码的所有汉明球均应不相交, 判定纠错码的检、 纠错能力可根据任意两个汉明球不相交的要求, 由码的最小距离通过来决定。tmind • 定理6.1.1 若纠错码的最小距离为论的任何一个结论独立成立:① 若要发现个独立差错, 则要求最小码距② 若要纠正个独立差错, 则要求最小码距③ 若要求发现个同时又纠正个独立差错③ 若要求发现个同时又纠正个独立差错, 则;, 那么如下三个结;;则mind1min ed12min td• 这里说的“同时” 是指在译码过程中, 若错误个数≤ , 则能纠正; 若错误个数> , 但≤ , 则能检测错误, 但不能纠正。 或者说能检测个错误, 其中 个错误可以纠正。 其直观的关系如图6.1.9所示。这些min1()detet tte ()etett (a) 纠错能力的几何说明(b) 检错能力的几何说明(c) 区分纠错和检错的示意图(d) 检错、 纠错能力与最小码距的关系图6.1.9 最小码距与检错、 纠错能力 • 图6.1.9(c)中, 粗线球面(圆)是纠正 个错误的球面, 细线球面(圆)代表检出 个错误的球面。 当接收码字 中不包含错误或错误, 将落在粗线球内或球上, 因而可把 纠正为原发送的码字, 当接收码字 包含不会落在任何码字的纠错球内, 但此时代表纠错范围的粗不会落在任何码字的纠错球内, 但此时代表纠错范围的粗线球面与另一码字的代表检错范围的细线球面没有相交或个而t个错误时,teRtRReR相切, 于是可将纠错和检错区分开来。• 当码的最小码距为3或4时, 可以纠正所有1位错。当码的最小码距为5时, 可以纠正所有2位错。当码的最小码距为时, 可以纠正所有位错。12n  • 定理6.1.1说明, 码的最小距离能力越强。 但是, 随着多余码元的增多, 信息传输速率会降低得越多。越大, 码的纠(检)错误的mindkk• 通常用码效率, 简称码率, 它是衡量码性能的又一个重要参数。码率越高, 信息传输率就越高, 但此时纠错能力要降低,若时就没有纠错能力了。 可见, 码率与纠错能力之间1 来表示码字中信息码元所占的比例, 称为编是有矛盾的。n  6. 2 线性分组码• 线性分组码是纠错码中非常重要的一类码, 虽然对于同样码长的非线性码来说线性码可用码字较少, 但由于线性码的编码和译码容易实现, 而且是讨论其他各类码的基础,至今仍是广泛应用的一类码。 6.2.1 线性分组码的基本概念• 定义6.2.1 对信源编码器输出的分组长度为, 相应的码字表示为:k进制序列进行分组, 设其中: 每个码元有个D有个。 信道编码(纠错编码)的目的是将信息码字变换, 使其成为以下形式:(nCc都是 进制的, 显然这样的码字共信道编码(纠错编码)的目的是将信息码字进行进行D21(,,,)kMm mm(1)imi k DkMM其中:我们称全体码字 的集合为的变换为线性变换, 则称全体码字 的集合为组码, 常用线性分组码 来表示全体码字 的集合。( , )n kC,为进制数, 显然这样的码字共有 个。元分组码。 若由DC到 之间元线性分CD2 1c c)nk(1)icin DnDCMCD • 例6.2.1 设将信源编码器输出的二进制序列进行分组, 分组长度为, 相应的码字表示为:制的, 即。 这样的码字共有两个, 即“1”和“0”。 现, 这里 是二进将 进行变换, 变换规则为:12k D 1()Mm1mM• 因此, 形成的纠错码具有以下形式:由于 只取“0”或“l”, 所以的全“0”或全“l”序列。 即经过上述变换, 得到了。n的全体码字只有两个: 长为重复码。12111ncmcmcm2 1c c111() ()nCcmmm1mC( ,1)n • 例6.2.2 设信源编码器输出的信息序列为中: 是二进制数。 信道编码器输出的码字为其中: 也是二进制数。 若从 到则为:nkcm, 其(nc,的变换规M21()kMmm m(1)i mik 2 1c c)C(1,)icin nk C• 由于从 到 的变换是一种线性变换, 所以全体 的集合构成了—种线性分组码。( ,1)n n 3221112kcmcmcmmmMCC • 由本例可以看出, 变换后码字集合中每一个码字的所有码元之和为:• 因为假设了码为二进制码, 上述码元的和是模2和。 因此,变换后将每一个码字的码元全部加起来变换后将每一个码字的码元全部加起来, 它的模2和为“0”, 即每一个码字中“1”的个数为偶数个, 所以这种码为偶校验码。它的模2和为12311211()nkcccccmmmcc • 例6.2.3 分组码, 按以下的规则(校验方程)可得到四个校验元:cm43cm(7,3)4321 c c c c736251cmcm• 式中:由此可得到码字的对应关系列于表6.2.1中。 由校验方程看到, 信息码是三个信息码元, 方程中的加运算均为模2加。分组码的八个码字。 八个信源序列与八个元与校验码元满足线性关系, 因此该码是线性码。13321232121 mcmmmcmmcmm321 m m m(7,3)(7,3) 表6.2.1 例6.2.3编出的线性码的码字与信息码元的对应关系(7,3)321 mmm7654321 ccccccc信息码元码字0 0 00 0 0 0 0 0 00 0 10 0 1 1 1 0 10 1 00 1 0 0 1 1 10 1 10 1 1 1 0 1 01 0 01 0 0 1 1 1 01 0 11 0 1 0 0 1 11 1 01 1 0 1 0 0 11 1 11 1 1 0 1 0 0 • 对于线性分组码有一个非常重要的结论: 一个线性分组码中非零码字的最小重量等于该码的最小距离[证明] 设有任意两个码字有。 而 的码重等于。。 根据线性分组码的性质,的码距(D C C。 即:( , )n kmind jC CiC +=ijlC CCCl C ijC C,)ij 而是C中任意两个非全零码字, 所以:[证毕]由例6.2.3 线性码的八个码字可见, 除全零码字外, 其余七个码字最小重量, 所以该4W线性码的最小距离。()()(,)lijijW CW CCD C C  jC Ci minminmin()()lijWCWCCd(7,3)min(7,3)min4d 6.2.2 生成矩阵和一致校验矩阵从矢量空间的角度, 形形色色的编码方法实质上是采用了不同的基底选择方法及矢量映射规则而形成的。 基底的选择与映射规则均可用矩阵来表示, 因此在线性分组码的讨论中就有了生成矩阵和一致校验矩阵的概念。(1) 生成矩阵在讨论生成矩阵之前我们再看例6 2 3的在讨论生成矩阵之前, 我们再看例6.2.3的码。 该码所满足的校验方程可写成矩阵形式:线性分组线性分组(7 3)(7,3)式中称线性分组码的生成矩阵。7362514313321232121 cmcmcmcmmcmmmcmmcmm76 54 32 13211001110 01001110011101c c c c c c cm m m CMG • 定义6.2.2 若信息组以不变的形式, 在码字的任意 位中出现, 则该码称为系统码。 否则, 称为非系统码。目前常用的有两种形式的系统码:种是把信息组排在码字• 一种是把信息组排在码字式(6.2.2)就是这种形式, 若非特别说明, 我们后面所说的的最左边 位的最左边 位:k(( ,))kk,系统码均指这种形式。• 另一种是把信息组安置在码字的最右边 位:。21,,ncc c1,,nn k cc21( ,,,)ncc ck1,,kcc • 能够产生系统码的生成矩阵为典型矩阵(或称标准阵), 典型矩阵的最大优势是便于检查生成矩阵 的各行是否是线性无关。 如果 不具有标准型, 虽能产生线性码, 但码字不具备系统码的结构, 因而存在难以区分码字中信息码元和监督码元的缺点。 由于系统码的编码与译码较非系统码和监督码元的缺点由于系统码的编码与译码较非系统码简单, 而且对分组码来说, 系统码与非系统码的抗干扰能力是等价的, 故若无特别声明, 我们仅讨论系统码。 如果生成矩阵 为非标准型的, 可经过行初等变换变成标准型。GGG (2) 一致校验矩阵从前面的讨论我们知道, 编码问题就是在给定的从已知的 个信息码元求得一般可写成:下如何个校验码元。mindk()r n k 或式(6.2.3)表明,方程的解, 故 是码书 中的一个码字, 由成了码书 ; 反之, 若某码元序列满足由中各码元是满足由矩阵 所确定的个线性C的全体就构所确定的 个线性方程, 则该码元序列一定是码书 中的一个码字。0TTHC0TCHCHCCCHrC • 因此,就迎刃而解; 或者说, 要解决编码问题, 只要找到由于码的所有码字均按所确定的规则求出, 故称为其一致校验矩阵。• 综上所述我们将 矩阵的特点归纳如下H• 综上所述, 我们将 矩阵的特点归纳如下:H一定, 便可由信息码元求出校验码元, 编码问题即可。HH( , )n kH①矩阵的每一行代表一个线性方程的系数, 它对应求一个校验码元的线性方程。矩阵每一列代表此码元与哪几个校验方程有关。③ 由该 矩阵得到的分组码的每一码字 都必须满足由矩阵的行所确定的线性方程, 即式(6.2.3)或式H②(6.2.4)。HHH( , )n kC ④码需有 个校验码元, 故需有 个独立的线性方程。因此,矩阵必须有 行, 且各行之间线性无关, 即矩阵的秩为 。⑤ 由于生成矩阵 中的每一行及其线性组合都是GTHG一个码字, 故有:⑥ 由例6.2.3不难看出,码的矩阵。 通常, 系统型码中的个码字故有或或( , )n krrrHrH( , )n k00TT00TTGHGH 矩阵右边为一个四阶单位线性分组码的矩阵右边 列组成一个单位矩阵 , 故有:r k式中型矩阵(或标准矩阵), 同样, 采用典型矩阵形式的 矩阵更易于检查各行是否线性无关。是一个阶矩阵。 我们称这种形式的矩阵为典HrTHG (7,3)H( , )n kHrrIrHQ I QH ⑦ 由式(6.2.5)易得:由此关系可知THG 0TkTTTrkrIQ IIPQ IQPPTT或这说明,二列, ……, 因此,反之亦然。的第一行就是 的第一列,矩阵一旦确定, 则H的第二行就是 的第矩阵也就确定,QPTPQPQPQG (3) 线性分组码的编码线性分组码的编码就是根据一致校验矩阵 或生成矩阵 将长度为 的信息码元变换成长度为 的码字。 这里以线性分组码为例来说明构造编码电路的方法。(7,3) 线性分组码为例来说明构造编码电路的方法。• 例6.2.4 设二元码字为校验矩阵 为:H10110( , )n kHGkn, 码的一致由得:(7,3)7 6 5 4 3 2 1c c cc cc c321 4 3 2 1() ()Cmmmc cc c001110 1 0 000110100110 001H0TTHC 按照该线性方程组, 可直接画出码电路和串行编码电路, 如图6.2.1所示。线性分组码的并行编4753765276165ccccccccccccc(7,3)(a) 并行编码电路图6.2.1 线性分组码编码电路原理图(b) 串行编码电路 (4) 对偶码和缩短码我们已经讨论了一致校验矩阵 , 如果把码的生成矩阵, 将( , )n r线性分组码的生成矩阵 与其对应的码的一致校验矩阵看成是码的生成矩阵看成是码的致校验矩阵一致校验矩阵, 则称这两种码互为对偶码。• 例6.2.6 求例6.2.3所述显然,码的对偶码应是码的矩阵就是即可按式(6.2.1)得到示。则称这两种码互为对偶码( , )n kGH( , )n k( , )n k( , )n r码的对偶码。码, 由对偶码的定义得,码的矩阵, 将其化成标准形式后码的对偶码码, 如表6.2.2所(7,4)(7,3)(7,3)(7,4)(7,4)G(7,3)H(7,3) 表6.2.2 例6.2.3线性码的对偶码(7,4)(7,3)10110001000101111010001001111100010001011001100010001011GH4321 mmmm7654321 ccccccc4321 mmmm7654321 ccccccc信息码元码字信息码元码字0 0 0 00 0 0 0 0 0 01 0 0 01 0 0 0 1 0 10 0 0 10 0 0 1 0 1 11 0 0 11 0 0 1 1 1 00 0 1 00 0 1 0 1 1 01 0 1 01 0 1 0 0 1 10 0 1 10 0 1 1 1 0 11 0 1 11 0 1 1 0 0 00 1 0 00 1 0 0 1 1 11 1 0 01 1 0 0 0 1 00 1 0 10 1 0 1 1 0 01 1 0 11 1 0 1 0 0 10 1 1 00 1 1 0 0 0 11 1 1 01 1 1 0 1 0 00 1 1 10 1 1 1 0 1 01 1 1 11 1 1 1 1 1 1 在有些情况下, 如果对某一给定长度的信息码元找不到合适码长的码, 则可将某一• 例如, 在线性分组码的码字集合中将最左边一位为“0”的消息和对应的码字选出来, 并把消息中最左边的“0”去掉则可构成线性分组码(6 2)掉, 则可构成线性分组码, 这种码称为缩短码。 如表6.2.3所示。表6.2.3 例6.2.3线性码的缩短码码缩短以满足要求。这种码称为缩短码如表( , )n k(7,3)(6,2)21 mm654321 cccccc信息码元码字0 00 0 0 0 0 00 10 1 1 1 0 11 01 0 0 1 1 11 11 1 1 0 1 0 6.2.3 线性分组码的译码• 只要找到 矩阵或 矩阵, 便解决了编码问题。 经编码后发送的码字, 由于信道干扰可能出错, 接收方怎样发现或纠正错误呢, 这就是译码要解决的问题。• 定义6.2.3 设码的一致校验矩阵为接收序时的接收序列, 则称:为接收序列 的伴随式或校正子。伴随式 是一致校验矩阵 的线性组合, 如果错误图样中有一些分量不为“0”, 则在 中正好就是 中不为“0”的那几列组合而成。 由于 是 维的列向量, 所以伴随式 也是一个 维向量。r,是发送码字为称GH( , )n kHRCTTSRHEHRSHSEihrS • 由上面的分析, 可得如下结论:① 从式(6.2.7)可知伴随式 仅与错误图样 有关, 它充分反映了信道受干扰的情况, 而与发送的是什么码字无关。② 伴随式是是否有错的判别式, 若若, 则判有错。0③ 不同的错误图样具有不同的伴随式, 它们是一一对应的,对二元码来说, 伴随式即为列之和。注意, 如果错误图样 本身就是一个码字, 即么计算伴随式 得到的结果必为“” , 此时的错误不能发现, 也无法纠正, 因而这样的错误图样称为不可检错误图样。, 则判没有出错;SE0SS矩阵中与错误图样对应的各H码, 那E( . )n kES • 例6.2.7 计算例6.2.3所述时的伴随式。码接收解:码的一致校验矩阵为:(7,3)123(1010011),(1110011),(0011011)RRR(7,3)101100011111100110000当接收时, 接收端译码器根据接收序列计算的伴随式为:(7,3)11000100110001H101011000011110100001100010000110001011TTSHR     因此, 译码器判别接收序列无错, 传输中没有发生错误。当接收时, 接收端译码器根据接收序列计算的伴随式为: 111011000011111110011000011 0   由于发生。因此可判定接收序列列中错误个数与码的纠错能力相符, 所以可正确译码, 即发送码字应为。, 所以译码器判别接收序列有错, 传输中有错误码是纠正单个错误的码, 观察 即为的第二位发生了错误。 由于接收序的第二行,1100010100110001111TTSHR0S(7,3)SH2 R(1010011) • 当接收伴随式时, 接收端译码器根据接收序列计算的为:3(0011011)RS001011000011110100111100010100TTSHR   0 •, 但与的任何一列都不相同, 无法判别错误发生在哪些位上, 此时只能发现有错。• 伴随式的计算可用电路来实现, 如前所述的码, 设接收序列, 则伴随式为:0110001110SH(7,3)7 6 5 4 3 2 1r r r r rr r()R • 根据上式, 可画出示。码的伴随式计算电路, 如图6.2.3所7675445765334762236511211011000111010011000100110001TTrrrrrsrrrrrsrSHRrrrsrrrrsrr  (7,3)图6.2.3 码的伴随式计算电路 6.2.4 线性分组码的纠错能力• 由前面的介绍可知, 线性分组码的纠错能力 和码字的最小距离有关, 一般 是在设计通信系统时提出的, 那么寻找满足纠正 个错误码元的码字就是编码技术的任务,为此我们还需进一步研究• 线性分组码码字的结构是由生成矩阵(或一致校验矩阵)决线性分组码码字的结构是由生成矩阵(或定的, 若巳知矩阵, 该码的结构也就知道了, 实际上所谓校验就是利用矩阵去鉴别接收矢量 的结构。 那么从研究码的纠错能力角度来看 与• 定理6.2.1 线性分组码最小码距等于矩阵中任何列线性无关。和码字结构的关系。tmindttmind致校验矩阵)决有什么关系呢?d的充要条件是HHRmindH( , )n kminHmin1d • 定理6.1.2是构造任何类型线性分组码的基础, 由定理可得出以下三个结论:① 为了构造最小距离(可检测纠正个错误)的线性分组码, 其充要条件是要求 矩阵中任意列线性无关。例如, 要构造最小距离为3的码, 则要求 矩阵中任意2列例如, 要构造最小距离为3的码, 则要求 矩阵中任意2列线性无关。 对于二元码, 即要求 矩阵满足无相同的列和无全“0”的列, 就可纠正所有单个错误。② 因为交换 矩阵的各列不会影响码的最小距离, 因此所有列向量相同但排列位置不同的纠错能力和码率是等价的。③ 任一线性分组码的最小距离(或最小重量) 均满足。个错误)或(可min1de emin21dttHmin1dHH矩阵所对应的分组码, 其HHHmindmin1dnk  • 满足的这种码, 是编码理论中人们感兴趣的一个课题。• 根据定理6.2.1, 我们可以由码的纠错、 检错能力。码的纠错、 检错能力。• 在巳知信息位 的条件下, 如何去确定监督位(即确定码长), 才能满足对纠错能力 的要求? 对此有下述的线性分组码称为极大最小距离码。 在同样之下, 由于最大, 因此纠错能力更强, 所以设计矩阵的列的相关性直接知道min1dnk , n kmindH的位数结论:• 若 是必须有不少于 个校验位, 并且使 满足:r二元码, 当巳知 时, 要使 能纠正 个错, 则krkrnktC( , )n kCt121triniC  • 式中的码, 这种码的校验元得到了最充分的利用。 式(6.2.9)又称为 中 取的组合。 满足ni时的码称为完备为汉明不等式。inC121triniC  6.2.5 汉明码•汉明码是汉明(Hamming)于1950年提出的能纠正一位错的特殊的线性分组码。 汉明码有许多很好的性质, 是一种完备码, 它可以用一种简洁有效的方法进行译码。 由于它的编、 译码较简单, 且较容易实现, 因此被广泛采用, 尤其是在计算机存储与运算系统中被广泛应用。(1) 汉明码的参数(1) 汉明码的参数对于任意正整数, 存在具有下列参数的二进制汉明码:•码长:•信息位数:•监督位数:•最小码距:3d3m 21mn 21mkmrnkm min • 给定 后, 即可构造出具体的立—致校验矩阵长 , 行数等于 。 例如4)线性码。 其 矩阵正是用的。 如:的如汉明码, 这可以从建矩阵的列数就是码, 可算出个非零三维列向量构成217入手。 我们知道,3m H, 因而是(7,m( , )n kHHnr7,4nkr • 此时,纠一位差错来说, 其伴随式的值就等于对应的矢量, 即错误位置。 所以这种形式的于纠错, 但这是非系统的(7, 4)汉明码的一致校验矩阵。如果要得到系统码, 可调整各列次序来实现:矩阵的列所对应的十进制数正好是“1”“7”, 对于矩阵的列矩阵构成的码很便101010111001101111000) 4 , 7 (HHHH • 有了, 就可得到系统码的校验位, 其相应的生成矩阵为:011101000 1110101101001H0H010001010100111001011000000010011G• 设码字, , 根据 (或))及关系式, 有:(7, 4)汉明码的编码电路原理图如图6.2.4所示。7 6 5 4 3 2 1c c c c c c c(C0H0G0TTHC376526541764cccccccccccc • 汉明码的译码, 可以采用计算伴随式, 然后确定错误图样并加以纠正的方法。 图6.2.5所示为(7, 4)汉明码的译码电路原理图。意• 需要注意的是(7, 4)汉明码的矩阵并非只有以上两种。 原则上讲,汉明码的一致校验矩阵有 列 行, 它的由除了全“0”以外的 位码组构成, 每个码组只在某列中出现一次,矩阵中各列的次序是可任意改变。• 另外, 对照完备码的定义可知, 汉明码实际上是备码。阵有种列的完( , )n knrnrH1t  图6.2.5 (7, 4)汉明译码器电路原理图 6. 3 循环码• 循环码是一种特殊的线性分组码, 属于线性分组码的一个重要子类, 也是目前研究最为透彻的一类码, 大多数有实用价值的纠错码都是循环码。循环码与一般的线性分组码相比具有以下优点:循环码的编码及译码易于用简单的具有反馈连接循环码的编码及译码易于用简单的具有反馈连接的移位寄存器来实现。• 定义6.3.1 设有线性分组码 , 如果它的任意一个码字的每一次循环移位仍然是 中的一个码字, 则称为循环码。 也即, 如果环码 的一个码字, 那么码字时, 则所有这些具有循环特性的码字的全体便构成了循环码。C是循C等也都是 的( , )n kCCC12 1c c()n nc cCC12 1c c c(),nnCc • 例如在例6.2.3中的6.3.1所示。• 由表可以看到, 在右边的码字栏内, 任意一个码字将其循环移位后, 其结果仍然是该栏内的一个码字。• 例如将第二行的码字循环右移一位后可得到第五行的码字• 例如将第二行的码字循环右移一位后可得到第五行的码字,第五行的码字循环右移一位后得到第三行的码字等。 实际上右移和左移具有同样的效果。循环码的主要特点是:• ① 理论成熟: 可利用成熟的代数结构深入探讨其性质;• ② 实现简单: 可利用循环移位特性在工程上进行编、 译码;线性分组码就是循环码, 该码如表(7,3) 321 mmm7654321 ccccccc信息码元码字0 0 00 0 0 0 0 0 00 0 10 0 1 1 1 0 10 1 00 1 0 0 1 1 10 1 10 1 1 1 0 1 01 0 01 0 0 1 1 1 01 0 11 0 1 0 0 1 11 1 01 1 01 1 0 1 0 0 11 1 0 1 0 0 1③ 循环码的描述方式有很多, 但在工程上最有用的是采用多项式的描述方法。由于循环码的以上特点, 可以将其用多项式来表示, 从而可以借助代数的工具对循环码进行分析, 这也是循环码能被广泛应用的原因之一。1 1 11 1 1 0 1 0 0 6.3.1 循环码的多项式描述• 设有循环码字项式惟一确定, 其相应的多项式可表示为:, 则可以用一个次数不超过的多•(6.3.1)即码字 与码多项式C即码字 与码多项式C一一对应。对应。2 1c c()nCc1n 121( )nnC xc xc xc( )( )C x由循环码的特性可知, 若字, 则项式为:是循环码 的一个码C也是该循环码的一个码字, 它的码多(6.3.2)比较式(6.3.1)和式(6.3.2), 得:12 1c c()n nc cC(1)12 1c c c()nnCc(1)111( )xnnnCcxc xc 该式说明, 码字循环一次的码多项式乘 后再除以所得的余式, 即:(1)( )C是原码多项式由此可以推知,由此可以推知,的 次循环移位的 次循环移位是原码多项式是原码多项式乘乘1(1)11( )( )x111nnnnnnnncxc xcxC xCccxxx( )mod(xC x1)nxx (1)( )Cx( )C xx1nx ( )( )C xi( )( )( )iCx( )( )C x后再除以所得的余式, 即:(6.3.3)式(6.3.3)揭示了线性码中码多项式与码字循环移位之间的关系, 它对循环码的研究起着重要的作用。ix1nx ( )( )( )mod(x C x1)iinCxx ( , )n k • 例如前面所述经循环移位后, 得到其他6个码字; 也可由相应的码多项式乘以后, 再模多项式。 这个移位过程及相应的多项式运算如表6 3 2所示。多项式。 这个移位过程及相应的多项式运算如表6.3.2所示。循环码可由任一个码字(如“0011101”)得到其他6个非零码(7,3)4321xxx(1,2,,6)ix i71x  4321xxx4327543(1)mod(1)x xxxxxxxx循环次数码字码多项式0 0 0 0 0 0 000 0 1 1 1 0 110 1 1 1 0 1 0表6.3.2 循环码的循环移位243276542(1)mod(1)xxxxxxxxx34327653(1)mod(1)1x xxxxxxx4432764(1) mod(1)1xxxxxxxx5432752(1) mod(1)1x xxxxxxx64327632(1)mod(1)x xxxxxxxx21 1 1 0 1 0 031 1 0 1 0 0 141 0 1 0 0 1 150 1 0 0 1 1 161 0 0 1 1 1 0 6.3.2 循环码的生成矩阵• 根据循环码的循环特性, 可由一个码字的循环移位得到其他非“0”码字。 在循环码的码多项式中, 每一个能整除的次首一多项式(其最高次项系数为“l”)都是该码的生成多项式, 记为。 将k的生成多项式, 记为。 将到 个码多项式:、、 …、是相互独立的, 可作为码生成矩阵的 行, 于是得到环码的生成矩阵:2( )xg x经过经过次循环移位, 共得k次循环移位, 共得。 这 个码多项式显然k( , )n k1nx ()nk( )g x( )g x(1)k ( )g x( )g( )( )gxg x1( )g x( )gkx循(6.3.4)kk( , )n k( )G x1( )g x( )( )( )kkxG xxg xg x • 码的生成矩阵一旦确定, 码也就确定了。 这说明码可由它的一个次首一多项式说由生成了循环码, 因此称即:循环来确定, 所以可以为码的生成多项式,( )g x(6 3 5)(6.3.5)( , )n k( , )n k( )g x( )g x( , )n k( )( )g xn k如果某一个码具有生成多项式, 则该码一定是循环码。• 码的生成多项式具有如下性质:① 在循环码中,次码多项式是最低次的码多项式。② 在循环码中,是惟一的③ 在循环码中, 每个码多项式次多项式。都是的倍式。④ 任意循环码的生成多项式一定整除。10n kn kgxg xg( , )n k( , )n k( , )n k( )g x()nk( , )n k( )C x( )g x( , )n k( )g x1nx  ...

    关注我们

  • 新浪微博
  • 关注微信公众号

  • 打印亚博足球app下载
  • 复制文本
  • 下载信息论与编码技术(第2版)CHAP6简明教程PPT课件.XDF
  • 您选择了以下内容