第六章--差错控制编码...ppt

第六章差错控制编码,6.1差错控制编码基本概念6.2有噪信道编码香农第二定理6.3差错控制方式和纠错码分类6.4线性分组码6.5循环码6.6卷积码6.7Turbo码,6.1差错控制编码基本概念,一、基本概念编码纠错技术是正确读出数字的技术，其主要目的是提高系统的可靠性，而编码理论则是其理论的基础。检错码：在收端，通过检测预先约定的约束关系而发现错误。纠错码：不但能判断是否有错，而且还能指出是哪些位有错，并通过译码器直接纠错得到正确码字。,二、纠错码技术实用化状况,1、卫星通信系统系统特点：根据安装天线的尺寸、发送功率限制，采用低C/N比（白噪声性）的信道；错误种类：随机错误实用纠错码例：双重纠错自正交卷积码、（120，112）缩短BCH码,卷积码、软判决维特比译码,2、宇宙通信系统系统特点：超远距离通信（微弱电波），采用低C/N比（白噪性）的信道；传输速率数Mbit/s（遥测用数据CCSDS建议）；地面局也可以采用大规模纠错设备。错误种类：随机错误实用纠错码例：卷积码（内部码）（255，233）里德索洛蒙码（ReedSolomonCode）（外部码）的双重码3、移动通信系统系统特点：有多径衰落等干扰，是低质量信道；为了使移动体装有设备，纠错设备需要简单。错误种类：突发错误实用纠错码例：(43，31)BCH码,4、卫星广播系统系统特点：有降雨衰落影响，但没有重像干扰，信道质量比较高；作为家庭用，纠错设备规格有限制。错误种类：随机错误实用纠错码例：(63，56)BCH码5、文字广播系统系统特点：由于重影干扰、脉冲噪声等，是低质量信道；作为家庭用，纠错设备的规格有限制。,错误种类：突发错误实用纠错码例：（272，190）缩短差集合循环码、多数表决逻辑译码。6、计算机半导体存储设备系统特点：可靠性要求高；需要高速读写数据错误种类：随机错误实用纠错码例：单一纠错、双重检错码（以汉明码为基础构成,7、计算机磁记录设备系统特点：可靠性要求高（误码率10-1210-13）；与传媒相关的错误多；错误种类：随机错误（字节错误）实用纠错码例：法牙码（FarCode）8、音频光盘设备系统特点：听觉所需的误码率较高（107指令）；超高密度，与媒体相关的错误。错误种类：随机错误突发错误实用纠错码例：双重编码里德索洛蒙码交叉码和循环码,9、视频磁记录设备系统特点：超宽带、高密度记录，与媒体、磁头相关的错误多；听觉所需的误码率较高。错误种类：随机错误突发错误实用纠错码例：里德索洛蒙积码,三、最简单的编码方法,例：码长3的重复码在直接传送1比特数据时，同一内容可以重复发送3次。对0发送(000)，对1发送(111)，即发送比特串。假设比特串的第2个产生错误，接收到(010)。由于这个是不可能的比特串，所以就知道发生了错误（检错）。在这种情况下要纠正第2比特的错误（纠错）。纠错是通过把可能接收的比特串判断为“好似(或好像)”来进行的。,四、为检、纠错要做的工作一般信道中发生的错误可分为随机错误和突发错误，相应的信道称为随机信道和突发信道。随机错误与突发错误并存的信道，称为组合信道或复合信道。作为检错与纠错用的抗干扰码，必须针对这几类信道，设计能纠正随机错误或纠正突发错误的码，或者设计既能纠正随机错误又能纠正突发错误的码。,五、编码理论中的通信系统模型设计一种编码，希望在抗干扰能力一定的条件下，编码效率越高、编码设备越简单越好。,6.2有噪信道编码香农第二定理,一、信道编码概念信道编码是为了保证信息传输的可靠性，使信源与信道特性相匹配，且传输中的差错为任意小，提高传输质量而设计的一种编码。信道编码是在信息码中增加一定数量的多余码元，在编码效率一定的条件下，提高检纠错能力，使码字具有一定的抗干扰能力，故又称为抗干扰编码。,定义编码效率为：RK/n其中K位信息，经编码得到长为n（nK）的码字，增加了nKr位多余码元。因此，信道编码以降低信息传输效率为代价，来增加码字的抗干扰能力。例：反复传送可以提高通信的可靠性。,二、有噪信道编码定理（香农第二定理）已知某离散无记忆平稳信道的信道容量为C，只要待传送的信息率RC，总可以在输入符号集中找到M（2nR）个码字组成的一组码（一种码长为n的编码）和相应的译码规则，当码长n足够长时，译码错误概率PE，为任意正数；反之，当RC时，译码错误概率任意小的码不存在，而当n时，PE1。,三、译码错误概率和译码规则问题：当码长n为有限值时，译码错误概率情况怎样？可靠性函数：表示在n为有限值时，差错概率的上界；同时也表示n时，PE0的速率。可靠性函数可帮助我们选择信息率R和编码长度n。注意：错误概率不仅与信道的统计特性有关，也与译码规则有关。最佳判断法则是最大似然译码法则,设：信道输入符号集为Aa1,a2,ai,ar信道输出符号集为Bb1,b2,bj,bs译码就是收到bj后，判断发送的是哪一个ai制定译码规则就是设计一个函数F(bj)，即：F(bj)ai若使正确译码概率最大，则：P(bj/a*)P(bj/ai)，其中aia*，a*A即输入符号最像是a*，故判断为a*是合理的，称为最大似然译码准则。,当输入符号是别的ai时，也有可能收到同样的bj，造成差错，条件错误概率为P(e/bj)，e表示除了F(bj)a*以外的所有输入符号的集合。则经过译码后的平均错误概率PE为：PEEP(e/bj)费诺不等式说明了PE与信道疑义度H(X/Y)关系：H(X/Y)H(PE)PElog(r1)无论采用什么译码规则，费诺不等式都是成立的,收到Y后产生错误概率PE的不确定性,错误发生后，判断是哪个输入符号发送而造成的错误的最大不确定性,四、连续信道编码定理对于限带高斯白噪声加性信道，噪声功率为Pn，带宽为W，信号平均功率受限为Ps，则：当总可以找到一种信道编码，使错误概率任意小；当RC时，使错误概率任意小的编码不存在。香农信道容量公式给出了达到无错误通信的传输速率的理论极限，但如何达到或接近这个香农极限，却并未给出具体方案。,小结,香农信道容量公式把信道的统计参量（容量C）和实际物理量（W，T，Ps/Pn）联系起来，它表明一个信道可靠传输的最大信息量完全由W，T，Ps/Pn所确定。所以，对一定的信息传输率来说，W，T，Ps/Pn之间可以相互转换，若时间一定，可以通过带宽和信噪比的互换而保持信息传输率不变。,6.3差错控制方式和纠错码分类,一、差错控制方式1、重传反馈方式(ARQ)：必须有反馈信道优点：编译码设备简单，误码率低，适应性强特点：适合点对点通信，控制电路复杂，实时性差,2、前向纠错方式(FEC)：发送能够被纠错的码，接收时可纠错。优点：无需反馈信道，能进行一对多的同播通信，译码实时性较好，控制电路比ARQ的简单。缺点：译码设备较复杂，对信道的适应性较差，编码效率低。特别适用于军用通信，随着大规模集成电路发展，译码设备也可变为简单，在实际中广泛应用。,3、混合纠错方式（HEC）：发送的码不仅可检错，且有一定纠错能力。可克服FEC和ARQ方式的缺点，在实际中应用更广泛。4、狭义信息反馈系统（IRQ）：接收端把收到的消息原封不动地通过反馈信道送回发送端，与原发送消息比较，从而发现错误并再次传送，达到正确接收消息的目的。,二、纠错码的分类1、按码的规律性：正交码，检、纠错码正交码：规律性在于码组间的正交性检、纠错码：规律性在于编码后码字中K位信息和nk位校验元之间建立了一定的函数关系。2、按对信息元处理方法不同：分组码，卷积码分组码：k个信息元按一定规律产生r个校验元，输出长为nkr的码字，此码字集称为（n，k）分组码，每个码字的n位码元仅与本组k位信息有关，与其它码组无关。其中，n为码长，k为信息位，k/n为码速率,卷积码：以k0个码元分为一段，输出长为n0的码段（n0k0），该码段的n0k0个校验元不仅与本组的信息元有关，而且也与其前m段的信息元有关。3、按校验元与信息之间的关系：线性码，非线性码4、按纠正错误的类型：纠随机错误码，纠突发错误码，纠同步错误码，既纠随机错误又纠突发错误码,5、按码字中的信息位是否发生变化：系统码，非系统码6、按每个码元取值：二进制码，q进制码7、按对每个信息元保护能力是否相等：等保护纠错码，不等保护纠错码,纠错码分类,6.4线性分组码,一、线性分组码的生成例：任给一个由k3位信息组成的信息组：m（m2，m1，m0），所生成的（6，3）线性分组码的码字由下列关系确定：ci3mi，i0，1，2c2m2+m1，c1m2m0，c0m1m0显然，可生成8个码字，前k3位是原信息组，后nk3位是由关系式确定的校验元，也称系统码（也称可分码）,定义：信息组以不变的形式，在码字的任意k位中出现的码称为系统码，否则称为非系统码。如：将码字生成的关系式用向量与矩阵乘积表示：C（m2,m1,m0）（m2,m1,m0）G这里G称为该（6，3）码的生成矩阵，有了生成矩阵就很容易把8个信息组变换成（6，3）码的8个码字,100110010101001011,对任意给定的信息组，由m生成的码字：CmG其中：m（mn-1，mn-2，mn-k）n，k分组码的2k个码字组成了一个k维子空间，码字可由k个独立矢量所组成的基底生成，设基底为：写成矩阵形式：,n，k码中的任何码字，都可由基底的线性组合生成即：若n，k码为系统码，且前k位是原来的信息组，则G矩阵左边k列必组成一个kk阶单位方阵Ik，因此系统码的生成矩阵通常为：式中，P是k(nk)阶矩阵，G的k行是线性无关的，这是标准型生成矩阵，只有G是标准型，才生成系统码。,结论,码的生成矩阵G为kn阶矩阵，可以不止一种形式，但都生成相同的矢量空间，即生成同一个n，k码，G中的每一行及其线性组合均为n，k码的一个码字。,二、分组码的几个参数1、码率：R=k/n表示（n,k）分组码中，信息位在码字中所占的比重。2、汉明距离：用d(a,b)表示a与b相应分量不相等的个数，则d为向量a与b的汉明距离，简称距离。3、码长为n的码字c中不为0的码元个数称为该码字的重量，记为W（c）。4、最小汉明距离dmin：任两个码字之间距离的最小值。纠错码的基本任务就是构造出R一定、dmin尽可能大的码字，或dmin一定、R尽可能高地码字。,三、最小距离译码将译码器的输入R与C的码字逐个进行比较，与哪个码字差别最小，就将其译成哪个码字，称为最小距离译码。四、分组码的检、纠错能力1、检测e个随机错误，则要求码的最小距离dmine+12、纠正t个随机错误，则要求dmin2t+13、纠正t个随机错误，同时检测e(t)个错误，则要求dmint+e+1,例：发生t个错误的概率远大于发生t+1个错误的概率：,一个数字通信系统的误码率为P104，因而收到一个7位码元的码字有一位码元发生错误的概率为：P(1)C17104（1104）67104其中C17表示7中取1的组合，同理：P(2)C27P2（1P）52.1107P(3)C37P3（1P）43.51011P(4)C47P4（1P）33.51015P(5)C57P5（1P）22.11019P(6)C67P6（1P）71024P(7)C77P71028,不发生错误，其概率为P(0)(1P)70.9993以上结果归纳：P(0)P(1)P(2)P(7)结论：发生t个错误的概率远大于发生t+1个错误的概率。因此：当收到一个R，若它不属于码集C，可将R与C中qk个码字作比较，当R与Cj的距离最小时，则发送Cj收到R的条件概率最大，由此可将R判决为Cj,实现最小距离译码的直观方法，就是将收到的码字与码集合中所有可能的码字进行比较，取距离最小的码字为译码结果。但当码长较长时，计算量太大，无法实现。其他还有陪集译码和伴随式译码方式。但陪集译码器的复杂性随n指数增长，很不实用。,四、伴随式纠错码,伴随式纠错码是用校验矩阵纠错的译码方法：设发送C时，收端收到R，错误图样：ERC（en1，en2，e1，e0）译码时，从R中得出C的估值，或解出错误图样从而得到，并使译码错误概率最小，或使尽可能是C，每个码字都满足校验方程HCT=0或CHT=0因此可用校验方程检验R：RHT（CE）HTCHTEHTEHT若E0，则RHT0，收到的R就是C,若E0，则RHT0，故它仅与错误图样有关，与发送的码字无关。令SRHTEHT或STHRTHET称S为R的伴随式（或校正子）伴随式完全由E决定，它充分地反映了信道干扰情况，译码器的主要任务就是如何从S求得E，从而译出发送的码字C，所以：收到R时，首先计算伴随式SRHT若S0，则接收的R无错S0，则接收的R一定有错,例：（7，3）码，发送码字C（1110100），R（0010100），E（1100000）时：所得伴随式S是H矩阵第一列与第二列之和,E（0010000）时：S是H矩阵的第三列（1个错）,E（0010100），则：S是H矩阵第三列与第五列之和（2个错）,结论,1）如果ST0，则判R无错，此时CR；2）如果ST0，且ST与H矩阵的第i列相同，就判R的第i位有错；3）如果ST0，且ST与H矩阵的哪列都不相同，则只判R有错，但不指出究竟是哪些位有错，即只发现错误而不纠错。,6.5循环码,一、基本概念定义：设C是一个（n，k）线性分组码，如果C中任意一个码字每次循环移位后得到的n维向量仍是C中的一个码字，那么就称C为循环码。,例：7，4汉明码的H阵为：交换H阵各列，并不影响码的纠错能力，交换各列后的H阵：显然，第二行是第一行循环右移一位得到，第三行是第二行循环右移一位。由此编出的16个码字为：1000110，0100011，1010001，1101000，0110100，0011010，0001101，1001011，1100101，1110010，0111001，1011100，0101110，0010111，1111111，0000000。,二、循环码的多项式描述在（n，k）循环码中，任一个码字C1（cn-1,cn-2,c0）可用多项式表示为：f1(x)cn-1xn-1cn-2xn-2c0C1循环移位一次得到C2（cn-2,cn-3,c0,cn-1）C2对应的多项式：f2(x)cn-2xn-1c0 xcn-1同理：再循环得到C3对应的码多项式：f3(x)cn-3xn-1c0 x2cn-1xcn-2,比较以上各多项式可知：用x乘以f1(x)再取模（xn1）得到f2(x)，用x乘以f2(x)，或用x2乘以f1(x)再取模（xn1）得到f3(x)，推广到一般情况：任何一个码字C1循环移位i次得到Ci1，对应多项式：fi+1(x)cn-1-ixn-1cn-2-ixn-2cn-i这相当于用xi乘以f1(x)，然后取模xn1即：xif1(x)fi+1(x)mod(xn1)上式表示：fi+1(x)是xn1除多项式xif1(x)的余式,三、循环码的纠突发错误能力,突发错误与随机错误的区别：E1（0.010.010.），E2（0.01110110.）错误图样E1对应的传输错误为随机错误错误图样E2对应的传输错误为突发错误定义：突发错误图样中，从第一个非0码元到最后一个非0码元总的码元位数称为突发长度，一般用b表示。,一个（n，k）分组码，如果能纠正任一个码字中长度不大于b的所有突发错误图样，则称该码的纠突发错误能力为b。一个（n，k）分组码若要发现所有长度不大于b的突发错误，则任何长度不大于b的突发错误图样不是一个码字。一个（n，k）分组码要发现所有长度不大于b的突发错误的必要条件是其校验元位数rnk满足：nkb，即校验元位数至少是b。但这不是充分条件，即若满足nkb，检错能力不一定达到b。,一个（n，k）分组码要能纠所有长度不大于b的突发错误，则任何长度不大于2b的突发错误图样不能作为一个码字。一个（n，k）分组码要纠所有长度不大于b的突发错误，则码至少要有2b个校验元，即nk2b，此式为赖格尔限，简称R限。这是每个能纠不多于b的突发错误码所必须满足的必要条件。如果纠突发能力达到（nk）/2，则称它为最佳纠突发错误码，简称R最佳码。,6.6卷积码,一、基本概念卷积码与分组码的区别：本组的码元不仅与本组的k0个信息元有关，而且还与以前若干时刻输入至编码器的信息元有关。译码时，不仅从此时刻收到的n0个码元中提取译码信息，而且还利用以后若干时刻收到的码组提取有关译码信息。卷积码各码组之间不再是相互独立。,卷积码的编码器可以看作是一个由k0各输入端和n0个输出端组成的时序网络。设第i时刻输入编码器的k0个信息为：mi（mi(1)，mi(2)，mi(ko)）相应输出是由n0个码元组成的子码：ci（ci(1)，ci(2)，ci(no)）,若输入的信息序列：m（m0,m1,m2,）则输出由子码c0,c1,c2,组成，均为半无限序列。所以，卷积码的码序列（或码字）：C（c0,c1,c2,），这是一个无限维向量卷积码具有线性相加特性定义：如果n0位长的子码中，前k0位是原输入的信息元，则称该卷积码为系统码，否则称为非系统码。,如下图二进制卷积码编码器：第i时刻输入信息元mi，此时刻的子码：ci（mi，pi,1，pi,2）,pi,1，pi,2为校验元且满足：ci(1)mici(2)pi,1mimi-1ci(3)pi,2mimi-2,下一个时间单位输入的信息元为mi+1，则对应的校验元：ci1(2)pi1,1mi1mici1(3)pi1,2mi1mi-1第二个子码ci1（mi+1，ci1(2)，ci1(3)）如此每时刻送入编码器1个（可为k0个）信息元，编码器就送出相应的3个（可为n0个）码元组成一个子码ci送入信道。这n0个码元组成的子码ci称为卷积码的一个码段或子组。,二、描述卷积码的主要术语,输入帧：每个时刻同时输入编码器信息组中的比特数（信息元个数），用k0表示。输出帧：每个时刻同时从编码器输出的比特数（输出一个子码中码元的个数），用n0表示。储存阶数（编码储存）：表示输入信息组在编码器中需存储的单位时间，即产生输出比特的过程中移位寄存器的最大级数，用m表示。编码约束度：表示编码过程中相互约束的子码个数，用Nm1表示。,编码约束长度：表示编码过程中相互约束的码元数目，用NANn0表示。参数m，N，k0，n0反映了编码器的复杂程度，所以卷积码一般用（n0，k0，m）或（n0N，k0N）表示，k0和n0比分组码的k和n通常要小。比值Rk0/n0为卷积码的码率，是衡量卷积码传输信息有效性的一个重要参数。,三、卷积码的特点,1、当前码分组输出不仅与当前信息分组输入有关，还与前面m个信息分组有关；2、还没有完善的数学工具有效地分析其结构和性能，必须借助计算机搜索来寻找好码；3、卷积吗是渐进好码，相同码率、相同译码复杂性条件下，卷积吗的性能要好于分组码；4、卷积吗仍是线性码，满足线性叠加关系。,四、卷积码的状态图编码器寄存器中任一时刻的存数称为编码器的一个状态，以si表示，每个状态都对应一个不同的输入组。如图为（2，1，2）卷积码编码器状态图。编码器由两级移存器组成，其存数只有4种可能，即4个状态。,实线表示0输入、虚线表示1输入时的状态转移,例：信息组M（1100），M(D)1D，则，输出的码序列：C(D)M(D)G(D)(1+D)1+D+D2,1+D2(11)+(10)D+(01)D2+(11)D3相应地C（11，01，01，11）状态图中编码器的状态变化为：s0s1s3s2s0从s0开始再回到s0，所得码序列称为结尾码字。这要求输完信息序列后，还应再输入mk0个全0信息元，使编码器回到全0状态。,五、卷积码的距离度量衡量卷积码的纠错性能可用其距离特性描述，但其纠错能力与它采用的译码方法有关，不同的译码方法有不同的距离度量。定义（汉明距离）：整个码树上不同子集的码字之间的距离最小值，为（n0,k0,m）卷积码的最小汉明距离d。定义（最小汉明距离）：不同初始截短码字子集之间距离的最小值，为（n0,k0,m）卷积码的最小汉明距离dmin。,六、卷积码的译码,代数译码：译码方法具有一定的代数结构，译码简单，便于实施。概率译码：纠错能力强，但算法复杂。较著名的有序列译码和维特比译码。概率译码方法不仅基于码的代数结构基础上，而且还利用了信道的统计特性，因而能充分发挥卷积码的特点，使译码错误概率达到很小。,1、维特比（Viterbi，VB）译码算法VB译码算法是一种最大似然译码算法。用栅格图或篱笆图可表示编码器状态转移与时间的关系：,例：输入编码器的信息序列：M（1011100）则编码器输出的码序列：C（11100001100111）它相应于篱笆图中红线表示的一条路径。编码器送出码序列C，经信道传输后，送入译码器的序列RCE，译码器根据R，按最大似然译码准则力图找出编码器在篱笆图上所走过的路径。,卷积码的译码过程就是译码器计算、寻找最大似然函数的过程。通过计算似然函数，相当于每一步都是寻找与R有最小汉明距离的路径，直接译出码字。,2、维特比译码算法的步骤(1)从某一时间单位jm开始，对进入每一状态的所有长为j段分支的部分路径，计算部分路径度量。对每一状态，挑选并存贮一条有最大度量的部分路径及其部分度量值，称此部分路径为留选(幸存)路径。(2)j增加l，把此时刻进入每一状态的所有分支度量，和同这些分支相连的前一时刻的留选路径的度量相加，得到了此时刻进入每一状态的留选路径，加以存贮并删去其它所有路径，因此留选路径延长了一个分支。,(3)若jL+m，则重复以上各步，否则停止，译码器得到了有最大路径度量的路径。由此可知，在篱笆图上用VB译码算法得到的路径一定是一条最大似然路径，因而这种译码方法是最佳的。,例：编码器如图，输入信息序列：M（1011100）输出码序列：C（11，10，00，01，10，01，11）通过BSC送入译码器的序列：R（10，10，00，01，11，01，11）求利用VB译码算法时，译码器输出的估值信息序列,解：VB译码器译R的过程：,进入相同状态时，由于d大，红色路径被删除即信息估值100、001、110、111被删除,虽然d相同，均为3任选一条舍去，信息估值0111删除即绿色路径被舍去,11,7.第7时刻接收子码R611,能用以上有限状态组成的篱笆图描述其编、译码过程的码称为网格码或篱笆码，也称Trellis码，是码树的一个大类。,最后幸存一条最大似然路径,译码输出：11,10,00,01,10,01,11而接收的R：10,10,00,01,11,01,11,3、VB译码算法的特点,1）（n0,k0,m）卷积码编码器共有2kom个状态，则译码器必有2kom个存储器，存储2kom个幸存路径（或信息序列）以及每一单个路径与Rj的距离。译码器的复杂性随k0m指数增加，一般选择m10。2）信息序列存储器存储的信息长度为k0L，L很大时，译码器的存储量也随之增大，难以实用。,6.7Turbo码,Turbo码，又称并行级联卷积码（PCCC），它巧妙地将卷积码和随机交织器结合在一起，实现了随机编码；同时采用软输出迭代译码来逼近最大似然译码。这是1993年发展