1、第8章 信道编码第8章 信道编码8.1 信道编码的实际应用信道编码的实际应用8.2 信道编码的基础信道编码的基础8.3 几种常用的检错码几种常用的检错码8.4 线性分组码线性分组码8.5 循环码循环码8.6 卷积码卷积码8.7 本章本章 MATLAB仿真实例仿真实例本章小结本章小结习题习题第8章 信道编码8.1 信道编码的实际应用信道编码的实际应用1.数字电视系统中的信道编码数字电视系统中的信道编码 在数字电视系统中通常采用两次附加纠错码的前向纠错编码(FEC)。RS编码属于第一 个 FEC,188字节后附加16字节 RS码,构成(204,188)RS码,这也可以称为外编码。第 二个附加纠错码
2、的 FEC一般采用卷积编码,又称为内编码。外编码和内编码结合一起,称 为级联编码。级联编码后得到的数据流再按规定的调制方式对载频进行调制。第8章 信道编码2.GSM 系统中的信道编码系统中的信道编码 GSM 系统把20ms语音编码后的数据作为一帧,共260b,分成最重要的50b、重要 的132b和不重要的78b。在 GSM 系统中,对语音编码后的数据既进行检错编码又进行纠错编码。首先对最重要 的50b进行循环冗余编码(CRC),编码后为53b;再将该53b与次重要的132b一起进行 约束长度为 K=5、编码效率为=1/2的卷积编码,编码后为2(53+132+4)=378b;最 后再加上最不重要
3、的78b,形成信道编码后,一帧共456b。第8章 信道编码3.IS95系统中的信道编码系统中的信道编码 在IS95系统中,正向链路上是以不同的沃尔什(Walsh)函数来区分不同的物理信道的。在用沃尔什函数进行直接扩频调制之前,要对语音数据或信令数据进行编码效率=1/2、约 束长度为 K=9的信道编码。由于 CDMA 系统是受自身干扰的系统,各业务信道上的发射 功率受到严格的限制。除了上面介绍的应用,信道编码还可应用于其他的实际通信系统中,比如,可用于深 空通信与卫星通信、数据存储与数据传输、数字音频/视频输出、光纤通信等。第8章 信道编码8.2 信道编码的基础信道编码的基础8.2.1 差错类型
4、差错类型 若要进行差错控制编码,应首先了解差错产生的原因和差错种类。信息码元差错主要 可以分成两类:一类称为随机差错,另一类称为突发差错。第8章 信道编码1.随机差错随机差错 随机差错一般由白噪声引起,表现为随机地出现。其特点是前、后码元差错没有任何 关系,是相互独立的。产生这种差错的信道称为随机信道或无记忆信道。2.突发差错突发差错这种差错的特点是前、后差错具有相关性,表现为差错成串地出现,我们把第一个错 误与最后一个错误之间的长度称为突发长度,用b 表示。例如:若发送端传送的数字序列为00000000,由于干扰,接收端接收到的序列为 00101110,因此突发长度为b=5。第8章 信道编码
5、8.2.2 差错控制方式差错控制方式 常用的差 错 控 制 方 式 主 要 有 三 种:前 向 纠 错(FEC)、检 错 重 发(ARQ)和 混 合 纠 错(HEC),它们的结构如图8 1所示。图中有斜线的方框图表示在该端进行错误的检测。第8章 信道编码图8 1 差错控制方式第8章 信道编码检错重发方式的优点主要表现在:(1)只需要少量的冗余码,就可以得到极低的输出误码率。(2)使用的检错码基本上与信道的统计特性无关,有一定的自适应能力。(3)与 FEC相比,信道编、译码器的复杂性要低得多。同时它也存在某些不足,主要表现在:(1)需要反向信道,故不能用于单向传输系统,并且实现重发控制比较复杂。
6、(2)当信道干扰增大时,整个系统有可能处在重发循环当中,因而通信效率低,不大适 合于严格实时传输系统。第8章 信道编码混合纠错方式是前向纠错方式和检错重发方式的结合。在这种系统中,接收端不但具 有纠正错误的能力,而且对超出纠错能力的错误有检测能力。遇到后一种情况时,系统可 以通过反馈信道要求发送端重发一遍。混合纠错方式在实时性和译码复杂性方面是前向纠 错和检错重发方式的折中。在实际应用中,上述几种差错控制方式应根据具体情况合理选用。第8章 信道编码8.2.3 差错控制编码分类差错控制编码分类 在差错控制系统中,信道编码存在着多种实现方式,同时信道编码也有多种分类方法。(1)按照信道编码的功能分
7、类,它可以分为检错码和纠错码。(2)按照信息码元和监督码元之间的约束方式分类,它可以分为分组码和卷积码。(3)按照信息码元和监督码元之间的检验关系分类,它可以分为线性码和非线性码。第8章 信道编码(4)按照信息码元在编码后是否保持原来的形式分类,它可以分为系统码和非系统码。(5)按照纠正错误的类型分类,它可以分为纠正随机错误码和纠正突发错误码两种。前者主要用于发生零星独立错误的信道,而后者用于对付以突发错误为主的信道。(6)按照信道编码所采用的数学方法分类,它可以分为代数码、几何码和算术码。其中 代数码是目前发展最为完善的编码,线性码就是代数码的一个重要的分支第8章 信道编码除上述信道编码的分
8、类方法以外,它还可以分为二进制信道编码和多进制信道编码等 等。同时,随着数字通信系统的发展,可以将信道编码器和调制器统一起来综合设计,这就 是所谓的网格编码调制(TrellisCodedModulation,TCM)。第8章 信道编码8.2.4 差错控制编码原理差错控制编码原理 在二进制编码中,一位二进制编码可表示两种不同的状态,两位二进制编码可表示4 种不同的状态,三位二进制编码可表示8种不同的状态,n 位二进制编码可表示2n 种不同 的状态。在n 位二进制编码的2n 种不同的状态中,能表示有用信息的码组称为许用码组,不能表示有用信息的码组称为禁用码组。第8章 信道编码8.2.5 码重、码重
9、、码距及检错、码距及检错、纠错能力纠错能力 1.差错控制编码的相关度量差错控制编码的相关度量 码长:码字中码元的数目。码重:码字中非0数字的数目。对于二进制码来讲,码重 w 就是码元中1的数目。例 如码字10100,码长n=5,码重w=2。码距:两个等长码字之间对应码位上具有不同的二进制码元的个数,有时也称为这两 个码字的汉明距离。例如码字10100与11000之间的码距d=2。第8章 信道编码最小码距:在码字集合中,全体码字之间距离的最小数值。对于二进制码字而言,两个码字之间的模二相加,其不同的对应位必为1,相同的对应 位必为0。因此,两个码字之间模二相加得到的码重就是这两个码字之间的距离。
10、第8章 信道编码2.最小码距与检错、纠错能力的关系最小码距与检错、纠错能力的关系 纠错码的抗干扰能力完全取决于许用码字之间的距离,码字的最小距离越大,说明码 字间的最小差别越大,抗干扰能力就越强。因此,码字之间的最小距离是衡量该码字检错 和纠错能力的重要依据。最小码距是信道编码的一个重要的参数。在一般情况下,分组码 的最小汉明距离d0 与检错和纠错能力之间满足下列关系。第8章 信道编码(1)当码字用于检测错误时,如果要检测e个错误,则这个关系可以利用图82(a)加以说明。在图中,用 A 和B 分别表示两个码距为d0 的码字,若 A 发生e个错误,则 A 就变成以 A 为球心、e为半径的球面上的
11、码字,为了 能分辨出这些码字,它们必须距离其最近的码字B 有一位的差别,即A 和B 之间最小距 离为d0 e+1。第8章 信道编码图82 纠(检)错能力的几何解释第8章 信道编码(2)当码字用于纠正错误时,如果要纠正t个错误,则这个关系可以利用图82(b)予以说明。在图中,用A 和B 分别表示两个码距为d0 的码字,若A 发生t个错误,则A 就变成以A 为球心、t为半径的球面上的码字;B 发生t个 错误,则B 就变成以B 为球心、t为半径的球面上的码字。为了在出现t个错误之后,仍能 够分辨出A 和B 来,那么,A 和B 之间距离应大于2t,最小距离也应当使两球体表面相距 为1,即满足不等式(8
12、2)。第8章 信道编码(3)若码字用于纠t个错误,同时检e个错误时(et),则这个关系可以利用图82(c)予以说明。在图中,用 A 和B 分别表示两个码距为d0 的码字,当码字出现t个或小于t个错误时,系统按照纠错方式工作;当码字出现大于t 个而小于e个错误时,系统按照检错方式工作;若 A 发生t个错误,B 发生e个错误时,既要纠 A 的错,又要检B 的错,则 A 和B 之间距离应大于t+e,也就是满足式(83)。第8章 信道编码3.编码效率编码效率 通常,在信道编码过程中,监督位越多纠错能力就越强,但编码效率就越低。若码字中 信息位数为k,监督位数为r,码长n=k+r,则编码效率可以用下式表
13、示:第8章 信道编码8.3 几种常用的检错码几种常用的检错码8.3.1 奇偶监督码奇偶监督码 奇偶监督码是奇监督码和偶监督码的统称,是一种最基本的检错码。它是由n-1位信 息元和1位监督元组成的,可以表示成(n,n-1)。如果是奇监督码,在附加上一个监督元 以后,码长为n 的码字中“1”的个数为奇数个;如果是偶监督码,在附加上一个监督元以 后,码长为n 的码字中“1”的个数为偶数个。第8章 信道编码第8章 信道编码第8章 信道编码3(a)就是码长为5的偶监督码编码器。从图中可以看到,长度为4的信息码,串行送入 四级移位寄存器,同时经模二运算得到监督元,存入输出缓冲器末级,编码完成就可以串 行输
14、出码字。接收端的检错电路如图83(b)所示,当一个接收码字B 完全进入5级移位寄存器内,开关S立即接通,从而得到检错信号 M=b4+b3+b2+b1+b0。如果接收码字B 无错,即 B=A,则 M=0;如果接收码字B 有单个(或奇数个)错误,则 M=1。第8章 信道编码图83 奇偶监督码的硬件实现第8章 信道编码8.3.2 二维奇偶监督码二维奇偶监督码 二维奇偶监督码又称水平垂直一致监督码或行列监督码,有时还称为方阵码。它对水 平(行)方向的码元和垂直(列)方向的码元实施奇偶监督。图84中,“”表示信息位,“”表示监督位。这种码有可能检测到偶数个错码。当 某一行(或某一列)出现偶数个错码时,该
15、行的监督位虽然不能被用于检测这偶数个错误,但只要所在列(或行)不同时出现偶数个错码,这个错码仍可以被发现。二位奇偶监督码不 能检测的错误是差错数正好为4的倍数,且差错位于构成矩形的四个角上,如图84中“”所示的位置。第8章 信道编码图84 二维奇偶监督码的结构第8章 信道编码8.3.3 恒比码恒比码 恒比码又称等重码,这种码的码字中1和0的位数保持恒定比例。由于每个码字的长 度是相同的,若1、0恒比,则码字必等重。若码长为n,码重为w,则此码的码字个数为 Cnw,禁用码字数为2n-Cnw。该码的检错 能力较强,除去“1”错成“0”和“0”错成“1”成对出现的差错之外,能发现几乎其他任何形式 的
16、错码。第8章 信道编码目前,我国电传通信中普遍采用3 2码,该码共有 C35=10个许用码字,用来传送10 个阿拉伯数字,如表82所示。这种码又称为5中取3恒比码。因为每个汉字是以四位十 进制数来表示的,所以提高十进制数字传输的可靠性,就等于提高汉字传输的可靠性。实 践证明,采用这种码后,我国汉字电报的差错率大为降低。第8章 信道编码第8章 信道编码8.3.4 群计数码群计数码 在群计数码中,信息码元经分组之后,计算每个信息码组中“1”的数目,然后这个数目 用二进制数表示,并作为监督码元附加在信息码元的后面一起传输。例如,信息码字为11100110,其中有5个“1”,用二进制数表示为“101”
17、,故群计数码码字为11100110101。这种码属于非线性分组系统码,检错能力很强,除了“1”错成“0”和“0”错成“1”成对 出现的差错之外,能检测出所有形式的错误。第8章 信道编码8.4 线线 性性 分分 组组 码码8.4.1 基本概念基本概念 分组码是一组固定长度的码组,可表示为(n,k),通常它用于前向纠错。在分组码中,监督位被加到信息位之后,形成新的码。在编码时,k 个信息位被编为n 位码组长度,而 n-k个监督位的作用就是实现检错与纠错。当分组码的信息码元与监督码元之间的关系为 线性关系时,这种分组码就称为线性分组码。第8章 信道编码线性分组码是建立在代数群论基础之上的,各许用码的
18、集合构成了代数学中的群,它 们的主要性质如下:(1)任意两个许用码之和(对于二进制码这个和的含义是模二和)仍为许用码,也就是 说,线性分组码具有封闭性。(2)码组间的最小码距等于非零码的最小码重。第8章 信道编码第8章 信道编码同理,由r 个监督方程式计算得到的校正子有r 位,可以用来指示2r-1种误码图样。对于一位误码来说,就可以指示2r-1个误码位置。对于码组长度为n、信息码元为k 位、监督码元为r=n-k 位的分组码(常记作(n,k)码),如果希望用r 个监督位构造出r 个监 督关系式来指示一位错码的n 种可能,则要求:第8章 信道编码设分组码(n,k)中,k=4,传输时仅有1位码元出现
19、误码,接收端需要纠正此位错误。由式(88)可 以 看 到,要 求 r3,若 取 r=3,则 n=k+r=7。因 此,可 以 用 a6a5a4a3a2a1a0 表示这7个码元,用S1、S2、S3 表示三个监督关系式的输出,通过计算即能够得到校正子,并且假设S3、S2、S1 三位校正子与误码位置的关系如表83所示。第8章 信道编码第8章 信道编码第8章 信道编码第8章 信道编码第8章 信道编码8.4.2 监督矩阵监督矩阵 式(8 10)所述(7,4)码的三个监督方程式可以重新改写为如下形式:第8章 信道编码上式可以记作:第8章 信道编码将上面的结论推广到一般的情况,(n,k)线性分组码的监督矩阵
20、H 由r=n-k 行、n列组成,可以表示为式中,P 为rk 阶矩阵,Ir 为rr 阶单位矩阵,具有这种特性的 H 矩阵称为典型监督矩 阵。典型监督矩阵各行一定是线性无关的。如果监督矩阵不是典型矩阵形式,可将其通过 初等变换转换为典型矩阵。第8章 信道编码8.4.3 生成矩阵生成矩阵 若信息码元已知,通过监督矩阵可以求得监督码元,由式(811),有第8章 信道编码第8章 信道编码由式(820)表示的生成矩阵形式称为典型生成矩阵,利用式(821)产生的分组码必 为系统码,也就是信息码元保持不变,监督码元附加在其后。第8章 信道编码8.4.4 校验子校验子 在发送端,信息码元 M 利用式(821)实
21、现信道编码,产生线性分组码A,在传输过程 中有可能出现误码,设接收到的码组为B,则收、发码组之差为其中,第8章 信道编码基于这样的原则,接收端利用接收到的码组B 计算校正子:因此,校正子仅与E 有关,而与发送的码字A 无关。仅当E 不为0时,即有误差时,S 不为0,否则S 等于0,任何一个错误图样都有其相应的校正子,而校正子ST 与 H 矩阵中 数值相同的一列正是错误图样E 中“1”的位置。所以译码器可以用校正子S 来检错和纠错。对于上述(7,4)码,校正子S 与错误图样的对应关系可由式(823)求得,其计算结果 见表85。第8章 信道编码第8章 信道编码8.4.5 汉明码汉明码 汉明码是一种
22、能够纠正单个错误的线性分组码。它有以下特点:(1)最小码距dmin=3,可以纠正一位错误。(2)码长n 与监督元个数r 之间满足关系式:n=2-1。如果要产生一个系统汉明码,可以将矩阵 H 转换成典型形式的监督矩阵,进一步利用Q=PT 的关系,得到相应的生成矩阵G。通常二进制汉明码可以表示为第8章 信道编码图85中给出(7,4)系统汉明码的编码器和译码器电路。第8章 信道编码图85(7,4)汉明码的编译码器第8章 信道编码8.5 循循 环环 码码循环码是线性分组码的一个重要子集,是目前研究的最成熟的一类码。它有许多特殊 的代数性质,这些性质有助于按所要求的纠错能力系统地构造这类码,且易于实现;
23、同时 循环码的性能也较好,具有较强的检错和纠错能力。第8章 信道编码8.5.1 循环码的特点循环码的特点 循环码最大的特点就是码字的循环特性。所谓循环特性,是指循环码中任一许用码组 经过循环移位后,所得到的码组仍然是许用码组。若an-1 an-2 a1 a0为一循环 码组,则an-2 an-3 a0 an-1、an-3 an-4 an-1 an-2、还是许用码组。也就是说,不论是左移还是右移,也不论移多少位,仍然是许用的循环码组。表8 6给出 了一种(7,3)循环码的全部码字。由此表可以直观地看出这种码的循环特性。例如,表86 中的第2码字向右移一位,即得到第5码字;第6码字组向右移一位,即得
24、到第3码字。第8章 信道编码第8章 信道编码对应表86中码字的循环关系,可以用图86来表示。图86(7,3)循环码循环左移状态转移图第8章 信道编码第8章 信道编码第8章 信道编码第8章 信道编码第8章 信道编码8.5.2 循环码的生成多项式和生成矩阵循环码的生成多项式和生成矩阵 在循环码中,次数最低的码多项式(全0码字除外)称为生成多项式,用g(x)表示。可 以证明,生成多项式g(x)具有以下特性:(1)g(x)是一个常数项为1的r=n-k 次多项式;(2)g(x)是xn+1的一个因式;(3)该循环码中,其他码多项式都是g(x)的倍式。第8章 信道编码1.生成矩阵生成矩阵 为了保证构成的生成
25、矩阵G 的各行线性不相关,通常用g(x)来构造生成矩阵,这时,生成矩阵G(x)可以表示为其中,第8章 信道编码第8章 信道编码2.生成多项式生成多项式 在上面的例子中,是利用表86给出的(7,3)循环码的所有码字,构造它的生成多项 式和生成矩阵的。但在实际循环码设计过程中,通常只给出码长和信息位数,这就需要设 计生成多项式和生成矩阵,这时可以利用g(x)所具有基本特性进行设计。第8章 信道编码第8章 信道编码8.5.3 循环码的编、循环码的编、译码方法译码方法 1.编码过程编码过程 在编码时,首先需要根据给定循环码的参数确定生成多项式g(x),也就是从xn+1的 因子中选一个(n-k)次多项式
26、作为g(x);然后,利用循环码的编码特点,即所有循环码多 项式A(x)都可以被g(x)整除,来确定循环码的相关码字。第8章 信道编码第8章 信道编码(3)系统循环码。编码输出系统循环码多项式A(x)为第8章 信道编码例例81 对于(7,3)循环码,若选用g(x)=x4+x2+x+1,请对信息码元110进行 循环编码。解:信息码元110对应的信息码多项式为第8章 信道编码第8章 信道编码图87(7,3)循环码编码器第8章 信道编码顺便指出,由于数字信号处理器(DSP)和大规模可编程逻辑器件(CPLD 和 FPGA)的 广泛应用,目前已多采用这些先进器件和相应的软件来实现上述编码。第8章 信道编码
27、第8章 信道编码2.译码过程译码过程 对于接收端译码的要求通常有两个:检错与纠错。以检错为目的译码十分简单,通过 判断接收到的码组多项式B(x)是否能被生成多项式g(x)整除作为依据。当传输中未发生 错误时,也就是接收的码组与发送的码组相同,即A(x)=B(x),则接收的码组B(x)必能 被g(x)整除;若传输中发生了错误,则A(x)B(x),B(x)不能被g(x)整除。因此,可 以根据余项是否为零来判断码组中有无错码。需要指出的是,有错码的接收码组也有可能被g(x)整除,这时的错码就不能被检出 了。这种错误称为不可检错误,不可检错误中的错码数必将超过这种编码的检错能力。第8章 信道编码在接收
28、端为纠错而采用的译码方法自然比检错要复杂许多,因此,对纠错码的研究大 都集中在译码算法上。我们知道,校正子与错误图样之间存在某种对应关系。如同其他线 性分组码,循环码的译码可以分三步进行:(1)由接收到的码多项式B(x)计算校正子(伴随式)多项式S(x);(2)由校正子S(x)确定错误图样E(x);(3)将错误图样E(x)与B(x)相加,纠正错误。第8章 信道编码基于错误图样识别的译码器称为梅吉特译码器,它的原理图如图88所示。错误图样 识别器是一个具有(n-k)个输入端的逻辑电路,原则上可以采用查表的方法,根据校正子 找到错误图样,利用循环码的上述特性可以简化识别电路。梅吉特译码器特别适合于
29、纠正 2个以下的随机独立错误。第8章 信道编码图88 梅吉特译码器原理第8章 信道编码8.5.4 BCH码码 BCH 码是1959年发展起来的一种循环码。该码的生成多项式g(x)与码的最小距离有 直接的关系。利用这种关系,可以根据纠错能力的要求来选择g(x),确定码的构造,编出 所需的码。该码纠错能力较强,编码较方便,译码也比较容易实现,是线性分组码中应用最 为广泛的一类码,尤其是在卫星通信中。如在ISV 的 TDMA 系统中,用(127,112)的 BCH 码。BCH 码有严密的代数结构,也是目前研究最为透彻的一类码。第8章 信道编码首先引入本原多项式的概念。若一个n 次多项式f(x)满足下
30、列条件:(1)f(x)为既约多项式(即不能分解因式的多项式);(2)f(x)可整除(xp+1),p=2n-1;(3)f(x)除不尽(xp+1),qp,则称f(x)为本原多项式。第8章 信道编码第8章 信道编码第8章 信道编码第8章 信道编码8.6 卷卷 积积 码码8.6.1 基本概念基本概念 在一个二进制分组码(n,k)当中,包含k 个信息位,码组长度为n,每个码组的(n-k)个校验位仅与本码组的k 个信息位有关,而与其他码组无关。为了达到一定的纠错能力 和编码效率(=k/n),分组码的码组长度n 通常都比较大。编、译码时,必须把整个信息 码组存储起来,由此产生的延时随着n 的增加而线性增加。
31、第8章 信道编码卷积码的纠错能力随着 N 的增加而增大,在编码器复杂程度相同的情况下,卷积码的 性能优于分组码。另一点不同的是:分组码有严格的代数结构,但卷积码至今尚未找到如 此严密的数学手段,把纠错性能与码的结构十分有规律地联系起来,目前大都采用计算机 来搜索性能优越的卷积码。第8章 信道编码8.6.2 编码原理编码原理 下面通过一个例子来简要说明卷积码的编码工作原理。正如前面已经指出的那样,卷 积码编码器在一段时间内输出的n 位码,不仅与本段时间内的k 位信息位有关,而且还与 前面m 段规定时间内的信息位有关。图89就是一个卷积码的编码器,该卷积码的n=2,k=1,m=2,因此,它的约束长
32、度nN=n(m+1)=23=6。第8章 信道编码图89(2,1,2)卷集码编码器第8章 信道编码在图89 中,D0 与 D1 为 移 位 寄 存 器,它 们 的 起 始 状 态 均 为 零。Cj1、Cj2 与 mj、mj-1、mj-2之间的关系如下:第8章 信道编码假如输入的信息序列为11010,为了使信息全部通过移位寄存器,还必须在信息位后 面加3个零。表811列出了对信息进行卷积编码时的状态。第8章 信道编码8.6.3 卷积码的图解表示卷积码的图解表示 描述卷积码的方法有多种,其中比较有代表性的有两类,即图解表示法和解析表示法。由于解析表示法较为抽象难懂,通常采用图解表示法来描述卷积码,而
33、常用的图解表示法 包括码树图、网格图和状态图。第8章 信道编码1.码树图码树图 由式(844)可以看出,编码器的输出与当前输入的码元 mj 和先前输入的两个码元 mj-2mj-1取值有关,我们将编码器中寄存器内所存储的、先前输入的信息码元的可能取值 称为编码器的状态。对应图89的编码器,mj-2mj-1可能的取值有4种:00、01、10和11,我们分别用a、b、c和d 表示。根据图89,可以得到当前时刻寄存器值、下一时刻寄存器值、输入、输出 的关系,如表812所示。第8章 信道编码第8章 信道编码第8章 信道编码图810(2,1,2)卷积码的码树第8章 信道编码2.网格图网格图 在码树中,从同
34、一个状态节点出发的分支都相同,因此可以将状态相同的节点合并在 一起,这样就得到了卷积码的另外一种更为紧凑的图形表示方法,即网格图。在网格图中,将码树中的上分支(对应于输入码元“0”的情况)用实线表示,下支路(对应于输入码元“1”的情况)用虚线表示,并将编码输出标在每条支路的上方。网格图的 每一行节点分别代表a、b、c、d 四种状态。(2,1,2)卷积码编码器的网格图如图811 所示。第8章 信道编码与码树一样,任何可能更多的输入码元序列都对应着网格图上的一条路径。例如,若 初始状态为a,输入序列为1101,对应的编码输出序列为11010100,如图811中粗线 所示。第8章 信道编码图811(
35、2,1,2)卷积码的网格图第8章 信道编码3.状态图状态图 卷积码的状态图表示给出了编码器当前状态与下一个状态之间的相互关系,如图812 所示。图中,虚线表示输入码元为“1”的路径,实线表示输入码元为“0”的路径,路径上的数 字表示编码输出。第8章 信道编码图812(2,1,2)卷积码状态转移图第8章 信道编码8.6.4 维特比译码维特比译码卷积码的译码可分为代数译码和概率译码两大类。代数译码利用生成矩阵和监督矩阵 来译码,最主要的方法是大数逻辑译码。概率译码中比较实用的有两种:维持比译码和序 列译码。第8章 信道编码当发送信息序列为11010时,为了使全部信息位能通过编码器,在发送信息序列后
36、面 加上了3个零,从而使输入编码器的信息序列变为11010000,得到如表8 10所示的计算 结果。这时编码器输出的序列为1101010010110000,那么移位寄存器的状态转移路线为 abdcbcaa,信息全部离开编码器,因此,最后回到状态a。假设在接收端接收到的序列有差错,变成0101011010010001。现对照图811的网格 图来说明 VB算法译码步骤和方法。第8章 信道编码由于该卷积码的编码约束长度为6,故先选前3段接收序列010101作为标准,与到达 第3级的4个节点的8条路径进行对照,逐步算出每条路径与作为标准的接收序列010101 之间的累计码距。由图813所示的网格图,可
37、以得到:第8章 信道编码(1)达到第3级的情况:到达节点a 的2条路径是000000与111011,它们与010101之间的码距分别是3和4;到达节点b 的2条路径是000011与111000,它们与010101之间的码距分别是3和4;到达节点c的2条路径是001110与110101,它们与010101之间的码距分别是4和1;到达节点d 的2条路径是001101与110110,它们与010101之间的码距分别是2和3。第8章 信道编码每个节 点 保 留 1 条 码 距 较 小 的 路 径 作 为 幸 存 路 径,它 们 分 别 是 000000、000011、110101和001101。这些路
38、径如图8 13中所示的到达第3级节点a、b、c和d 的4条路径,累计码距分别用括号内的数字标出。第8章 信道编码图813 维特比译码格图第8章 信道编码(2)到达第4级的情况:节点a 的2条路径是00000000和11010111;节点b 的2条路径是00000011和11010100;节点a 的2条路径是00001110和00110101;节点a 的2条路径是00110110和11011010。将它们与接收序列01010110对比求出累计码距,每个节点仅留下一条码距小的路径 作为幸存路径,它们分别是11010111、11010100、00001110和00110110。第8章 信道编码逐步推
39、进筛选幸存路径,到第7级时,只要选出到达节点a 和c的2条路径即可,应为 到达终点第8级a,只可能从第7级的节点a 或c出发。最后得到了到达终点a 的1条幸存 路径,即为译码路径,如图813中粗线所示。根据这条路径,对照图811可知,解码结 果为11010000,与发送信息序列一致。从解码过程中可以看出,维特比译码算法的存储量仅为2m+1,对于 mt),则d0t+e+1。常用的几种简单的检错码:奇偶监督码、二维奇偶监督码、恒比码、群计数码等。奇偶 监督码是一种有效地检测单个错误的方法,其编、译码方法简单,编码效率高。二维奇偶监 督码又称水平垂直一致监督码或行列监督码,有时还称为方阵码。它对水平
40、(行)方向的码 元和垂直(列)方向的码元实施奇偶监督。恒比码又称等重码,是目前国际电报通信系统中 常用的差错控制编码方式。第8章 信道编码分组码是一组固定长度的码组,可表示为(n,k),通常它用于前向纠错。在分组码中,监督位被加到信息位之后,形成新的码。在编码时,k 个信息位被编为n 位码组长度,而 n-k个监督位的作用就是实现检错与纠错。当分组码的信息码元与监督码元之间的关系为 线性关系时,这种分组码就称为线性分组码。信息位和监督位之间的关系可以用监督矩阵 H 和生成矩阵G 来表示。利用生成矩阵G 可以产生整个线性分组码的码字,即A=MG;利用监督矩阵 H 处理接收到的码字B,得到的校正子S
41、 能够实现差错控制。其中,汉明码 是一种能够纠正单个错误的线性分组码,其最小码距为3,码长n 与监督元个数r 之间满足 关系式:n=2r-1。第8章 信道编码循环码是线性分组码的一个重要子集,是目前研究的最成熟的一类码。它有许多特殊 的代数性质,这些性质有助于按所要求的纠错能力系统地构造这类码,且易于实现;同时 循环码的性能也较好,具有较强的检错和纠错能力。在循环码中,次数最低的码多项式(全 0码字除外)称为生成多项式,用g(x)表示。利用g(x)能够确定其生成矩阵和监督矩阵,同时也可以直接进行编码操作。BCH 码是循环码中的一个重要子类,它具有纠正多个随机 错误的能力,而且具有严密的代数结构
42、,是目前研究的较为透彻的一类码。第8章 信道编码与分组码不同,卷积码中编码后的n 个码元不仅与当前段的k 个信息有关,而且也与 前面m 段的信息有关。换句话说,各子码内的监督码元不仅对本子码有监督作用,而且对 前面m 个子码内的信息元也有监督作用。因此常用(n,k,m)表示卷积码。描述卷积码的 方法有多种,通常采用图解表示法来描述卷积码,而常用的图解表示法包括码树图、网格 图和状态图。卷积码的译码方法可分为代数译码和概率译码,本章介绍了概率译码的代表 性方法维特比译码。第8章 信道编码习题习题81 已知信息码组m1、m2、m3为000、001、010、011、100、101、110、111,试
43、写出 奇数监督码组和偶数监督码组。82 已 知 8 个 码 组 为 000000、001110、010101、011011、100011、101101、110110、111000。(1)求以上码组的最小距离;(2)将以上码组用于检错,能检测几位错码?若用于纠错,能纠正几位错码?(3)如果将以上码组同时用于检错与纠错,问纠错、检错能力如何?第8章 信道编码83 已知两码组为0000和1111。若用于检错,能检出几位错码?若用于纠错,能纠 正几位错码?若同时用于检错与纠错,问各能纠、检几位错码?第8章 信道编码第8章 信道编码第8章 信道编码8 8 已知(3,1,4)卷积码编码器的输出与m1、m2、m3 和m4 的关系为试画出码树、网格图和状态图。当输入编码器的信息序列为 10110 时,求它的输出码序列。第8章 信道编码89 一卷积编码器如题图所示,每次移入编码器一个消息码元。(1)试求出这个卷积码的约束长度和编码效率;(2)设寄存器的初始内容为零,试求与输入消息码组110101对应的输出卷积码码组。第8章 信道编码810 已知(2,1,2)卷积码编码器的输出与m1、m2和m3 的关系为当接收码序列为1000100000 时,试用维特比译码方法求译码序列 M
