1、2019/4/20,1,通 信 原 理 电 子 教 案 第9章 差错控制编码,西 北 工 业 大 学 (2012.5),2019/4/20,2,9.1 引言 一、编码问题的提出 由于数字信号在传输过程中必不可免的受到干扰的影响,使码元波形变坏,故传输到接收端后可能发生错判。,信道,译码,检/纠错编码,若还不行,则需差错控制编码。 目的:在数字通信系统中,为了提高数字通信的可靠性而采取的编码称为信道编码。差错可控 之前:为了提高数字信号传输的有效性而采取的编码称为信源编码。如:PCM 二、方法/模型,2019/4/20,3,研究问题:,9.1 引言 9.2 差错控制编码的基本概念 9.3 常用的简单检错码 9.4 线性分组码 9.5 循环码 9.6 检测和纠正突发错误的分组码交织码 9.7 卷积码 9.8 网格编码调制(TCM),2019/4/20,4,1. 随机性差错:差错是随机的且相互之间独立单个错。通常由高斯白噪声引起。 突发性差错:错误之间有相关性-成串错 。由脉冲性干扰引起,在短暂的时间内出现连续的差错,而这些短暂时间之后却又存在较长的无误码区间。,9.2.1 差错类型,9.2
2、 纠错编码的基本概念,3. 混合性差错:既存在随机差错又有突发性差错。,以上两种错误性质不同,可分别处理。,2019/4/20,5,可以用来检测一位错误,可纠正一位错误或检测两位错误,A B,采用1位二进制码,0 1,9.2.2 差错控制的基本方法,在信息序列之后附加一些监督码元,这些多余的码元与信息码元之间以某种确定的规则相互关联,接收端按照既定的规则检验出关联关系,如这种规则受到破坏,将会发现错误,乃至纠正错误。,例:,2019/4/20,6,检错与纠错能力与最小码距 d0 的关系,(c) 为了同时检测e个错误,纠正t个错误d0 et1,et,(b) 为了纠正t个错误 d0 2t1,(a) 为了检测e个错误, d0 e1,码距:两个码组对应位上不同的数目。 码重:码组中“1”的数目。,结论:最小码距决定检错和纠错能力。,2019/4/20,7,9.2.3 差错控制方式,比较:译码复杂性、实时性和占用传输链路(单向还是双向)。,接收端所识别到的错误超过了自身的纠错能力时,就请求发送端重发。,2019/4/20,8,9.2.4 差错控制编码的效用,假设在随机信道中发“0”和发“1”的概
3、率相同,在码长为n的码组中恰好发生 r 个错误的概率为:( p为误码率 ),当码长 n7 ,误码率 时 ,则有:,结论:采用差错控制编码,即使仅能纠正(或检测)12个错误,就能使误码率下降几个数量级。,(9.2-4),2019/4/20,9,9.2.5 纠错码的分类,1. 分组码与卷积码 分组码:将信息码分组,为每组信息码后面附加若干位监督码元,且 监督码元仅监督本码组中的信息位。,卷积码:将信息序列分组,后面附加监督位,但监督位不但与本码组的信息位有关,还与前面码组的信息位有关,或者说监督位不仅监督本码组的信息位还监督其它码组的信息位。,2. 系统码与非系统码,系统码: 就是信息位在前,监督位在后的码字。 非系统码:信息位与监督位之间无特定的位置关系。,编码效率:k/n,( n,k)码,2019/4/20,10,9.3 常用的简单纠错码,9.3.1 奇偶校验,构成:n-1位信息位、1位监督位。n位编码构成以下约束关系,接收端计算校正子(偶监督),检错能力:所有奇数个错误。一半!应用非常广泛。 编码效率:,2019/4/20,11,9.3.2 纵向奇偶校验(LRC)用于检测突发错误,1
4、1100111 11011101 00111001 10101001,11100111 11011101 00111001 10101001,纵向排列,原始数据,11100111 11011101 00111001 10101001 10101010,接收方检验是否满足LRC,交织编码: 针对突发性错误,n位的LRC可以检测一个n位突发错误。,2019/4/20,12,信 息 码 元 0 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 1 0 1 1 0 0 0 0 监督码元 0 0 1 1 1 0 0 0 0 1 0,监督码元 1 0 0 1 0 1 1,9.3.3 水平垂直奇偶校验(二维),它能发现某一行或某一列上所有奇数个错误以及长度不大于行数(或列数)的突发错误。 可检某些偶数个错误。 具有一定的纠错能力。,2019/4/20,13,9.3.4 群计数码,功能:发现所有奇数个错误,以及
5、一些偶数个错误,除“0”变“1”,和“1”变“0”成对出现。,规则:信息码元分组后计算“1”的个数,然后将这个数目的二进制码元表示作为监督码元附加在信息码元之后。,2019/4/20,14,9.3.5 等重码(恒比码),功能:检测所有奇数个错误,以及一些偶数个错误,除“0”变“1”,和“1”变“0”成对出现。,等重码是从特定码长的码组中,选取固定个数的“1”作为码组的许用码组,这种码de码重相同,或“1”与“0”之比保持恒定。,例:我国电传汉字电码,每个汉字用4位阿拉伯数字表示,每个阿拉伯数字又用5位二进制符号表示,其中3个“1”,码重为3。,2019/4/20,15,9.4 线性分组码,定义:信息位和监督位之间的关系由线性方程组约束的分组码称作线性分组码。 特征:督元由信元的线性组合而产生。,奇偶校验码就是一种效率很高的线性分组码。,这里S称为校正子:若S0,表示无错,S1表示有错。 因仅用了1位监督位a0 ,所计算的1个校正子只能表示有错与无错。 若监督位增加到2位,就可增加一个监督方程式,便可获得2个校正子S1、 S2,于是:,2019/4/20,16,推广:,显然:要求 2r-
6、1n(n=k+r),则可指示(仅一位错时) 任一错码的位置包括信元、督元。 或: 2rk+r+1,对于二进制编码,知道了错误的位置,就可以实现纠错了。,2019/4/20,17,一般说来对于(n,k)码。要想指出一位错码的所有可能位置,则要求:,对于纠正t 个错误,需满足:,(纠正1个错误),2019/4/20,18,9.4.1 线性分组码的构成,例:构造k4的汉明码(能纠一位错的线性分组码)。 (1)确定 r 由,得 r3 ,取r3,则n7。 (7,4)码!,(2)写出校正子的编码表,2019/4/20,19,因此接收端计算下面3个校验关系,可确定误码的位置:,校正子表不是唯一的!,这里的“+”代表模2和,(2)写出校正子的编码表-r = 3 共有3个校正子,2019/4/20,20,发送端构成偶校验方程,可得督-信方程(线性组合),表9-5 16个许用码组!,信息位 监督位 信息位 监督位 0 0 0 0 0 0 0 1 0 0 0 111 0 0 0 1 0 1 1 1 0 0 1 100 0 0 1 0 1 0 1 1 0 1 0 010 0 0 1 1 1 1 0 1 0 1
7、 1 001 0 1 0 0 1 1 0 1 1 0 0 001 0 1 0 1 1 0 1 1 1 0 1 010 0 1 1 0 0 1 1 1 1 1 0 100 0 1 1 1 0 0 0 1 1 1 1 111,(3)生成全部许用码组,2019/4/20,21,9.4.2 线性分组码的监督矩阵和生成矩阵,1. 监督矩阵从校验方程入手,记为,或有,2019/4/20,22,其中:,-监督矩阵,-码组的行矩阵,-零矩阵,可见:H一旦确定,督元和信元之间的关系也就确定了。 若:,-则称H为典型阵。,由线性代数理论:典型阵各行一定是线性无关的; 非典型阵可通过矩阵的初等变换化为典型阵。,2019/4/20,23,2. 生成矩阵,矩阵形式:,从督信方程入手 由,2019/4/20,24,写成行阵形式:,其中 Q = PT。上式表明:信息位给定后,就产生了监督位!,进一步,令生成矩阵 G = Ik Q 则,码组行阵 A = a6a5a4a3 G,Q能生成督元 G才生成线性分组码 如何装配:信元督元?,2019/4/20,25,例:生成矩阵,讨论: 由信息位与生成矩阵G相乘可得到全部码字A
8、。 具有 Ik Q 形式的生成矩阵称为典型生成阵。 由典型生成矩阵得出的码组为系统码。,码组行阵:,督元由相应的信息位决定!,2019/4/20,26,一般形式: A = an-1an-2ar G,3. G 和 H 的关系 由 Q = PT 或 P = QT 则 : H = P Ir G = Ik Q 综上:线性分组码的编码,就是根据其监督阵H或生成阵G将长为k的信息码编成长为n的码组。,2019/4/20,27,4. 线性分组码的性质 (1)封闭性 设: A1、A2 分别为一线性分组码的任意两个许用码组。 则:A1+A2 仍为该线性分组码的许用码组。 证:由假设知 A1HT=0、A2HT=0 所以 A1HT+A2HT=(A1+A2)HT0 即A1+A2也是一个码组。 结论:线性码组中任意两个码字之和,仍为该线性码组之码字。 (2)线性分组码的最小距离等于非零码的最小重量。即 : d0=Wmin(除全0码组) 证:由封闭性得,两个码组之间的距离(之差),必是另一码组的重量。故最小码距即是码的最小重量!,2019/4/20,28,9.4.3 线性分组码的伴随式译码,设:发送码组为A,接收
9、码组为R。 则: R-AE(模2) 为错误行阵或错误图样。,对于前面(7,4)码的例子,一位错误图样为: (1000000) , (0100000), (0010000),(0001000), (0000100),(0000001), (0000001),计算校正子或伴随式:,结论:校正子S仅与错误图案有关,与发送码组无关。,2019/4/20,29,伴随式与纠错: 结论:校正子S只与E有关,若接收码字R中第i 位有错,那么导出的伴随式恰好同于监督矩阵H的第i 列。 例:对于前面(7,4)码例子,一位错误图样为: (1000000) , (0100000), (0010000),(0001000), (0000100),(0000001), (0000001),分别计算当错误图样为上面七种形式之一时的伴随式值。,2019/4/20,30,结论:利用伴随式不仅可以判决接收码字中是否有错,而且可以指出差错的位置。,2019/4/20,31,例:若接收的码组为1001101,请指出错误位置并译码。,解:计算伴随式,最后一位有错,译码得:1001100。,2019/4/20,32,9.5.1 循环码的概念 定义:是一种具有循环移位特性的线性分组码。 特点:编译码设备简单;检纠错能力强。,9.5 循环码,构成原理: 具有线性分组码的所有性质之外,还具有循环性:循环码中任一许用码组经过循环移位后,所得到的码组仍然是许用码组。,2019/4/20,3
《差错控制编码_4课件》由会员F****n分享,可在线阅读,更多相关《差错控制编码_4课件》请在金锄头文库上搜索。