通信原理第7章信道编码和差错控制

第7章信道编码和差错控制7.1概述7.2纠错编码的基本原理7.3纠错编码系统的性能7.4奇偶监督码7.5线性分组码7.6循环码●信源编码与信道编码●信源编码(有效性编码)●去除冗余●提高数字信号的有效性●模拟信号数字化●信道编码(可靠性编码)●添加冗余●降低差错率：牺牲通信的有效性（信息传输速率）来提高可靠性●差错控制：包括信道编码在内的一切纠正错误手段●差错控制技术的种类●检错重发●能发现错码，但是不能确定错码的位置●通信系统需要有双向信道●前向纠错(FEC)：利用加入的差错控制码元，不但能够发现错码，还能纠正错码●反馈校验●将收到的码元转发回发送端，将它和原发送码元比较●缺点：需要双向信道，传输效率也较低●检错删除●在接收端发现错码后，立即将其删除●适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处7.1概述发送端接收端信源信道编码调制信道压缩编码解调信宿保密解码信道解码压缩解码保密编码噪声信源编码信源解码●自动要求重发(ARQ)系统●停止等待ARQ系统●拉后ARQ系统7.1概述接收数据ACKACKNAKACKACKNAKACK1233455t发送数据12334556t有错码组有错码组214365798接收数据有错码组有错码组91011101112576ACK1NAK5NAK9ACK55769521436798发送数据1011101112重发码组重发码组●自动要求重发(ARQ)系统●选择重发ARQ系统7.1概述选择重发ARQ系统9接收数据有错码组有错码组21436575981011131412发送数据995852143671011131412重发码组重发码组NAK9ACK1NAK5ACK5ACK9●ARQ和前向纠错比较●优点●监督码元较少，即码率较高●检错的计算复杂度较低●能适应不同特性的信道●缺点●需要双向信道●不适用于一点到多点的通信系统或广播系统●传输效率降低，可能因反复重发而造成事实上的通信中断●产生错码的原因●乘性干扰引起的码间串扰●加性干扰引起的信噪比降低●信道分类：按照加性干扰造成错码的统计特性不同划分●随机信道：错码随机出现，例如由白噪声引起的错码●突发信道：错码相对集中出现，例如由脉冲干扰引起的错码●混合信道●编码序列的参数●n－编码序列中总码元数量k－编码序列中信息码元数量r－编码序列中差错控制码元数量（差错控制码元，以后称为监督码元或监督位）k/n－码率(n-k)/k=r/k－冗余度7.1概述7.2纠错编码的基本原理●差错控制编码●理论依据：香农信道编码定理对于一给定的有干扰信道，若其信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值●基本思想通过对信息码元序列作某种变换,使原来彼此相互独立,没有关联的信息码元序列,经过这种变换后,产生某种规律性或相关性,使在接收端可根据这种规律性来检查,以至纠正传输序列中的差错●实现：发送端按照某种规则在信息序列上附加监督码元，接收端则按照同一规则检查两者间关系7.2纠错编码的基本原理●差错控制编码●简单例子●假如要传送A、B两个消息，消息A----“0”；消息B----“1”若传输中产生错码（“0”错成“1”或“1”错成“0”）收端无法发现，该编码无检错纠错能力●消息A----“00”；消息B----“11”若传输中产生一位错码，则变成“01”或“10”，收端判决为有错（因“01”“10”为禁用码组），但无法确定错码位置，不能纠正，该编码具有检出一位错码的能力。这表明增加一位冗余码元后码具有检出一位错码的能力●消息A----“000”；消息B----“111”传输中产生一位即使两位错码，都将变成禁用码组，收端判决传输有错。该编码具有检出两位错码的能力。在产生一位错码情况下，收端可进行正确判决，能够纠正这一位错码。该编码具有纠正一位错码的能力。这表明增加两位冗余码元后码具有检出两位错码及纠正一位错码的能力。●可见，纠错编码之所以具有检错和纠错能力，确实是因为在信息码元外添加了冗余码元（监督码元）。一般说来，添加的冗余越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。7.2纠错编码的基本原理●差错控制能力与编码效率●设：有一种由3个二进制码元构成的编码，它共有23=8种不同的可能码组：000–晴001–云010–阴011–雨100–雪101–霜110–雾111–雹这时，若一个码组中发生错码，则将收到错误信息●若在此8种码组中仅允许使用4种来传送天气，例如：令000–晴011–云101–阴110–雨为许用码组，其他4种不允许使用，称为禁用码组这时，接收端有可能发现（检测到）码组中的一个错码。这种编码只能检测错码，不能纠正错码●若规定只许用两个码组：例如000–晴111–雨就能检测两个以下错码，或纠正一个错码●分组码概念●分组码＝信息位＋监督位分组码符号：(n,k)其中，n－码组总长度k－信息码元数目r=n–k－监督码元数目右表中的码组为(3,2)码●分组码的一般结构：信息位监督位晴000云011阴101雨110k个信息位r个监督位an-1an-2...arar-1an-2...a0t码长n=k+r7.2纠错编码的基本原理●码重码字中非零码元的数目●码距两个码字中对应码位上具有不同二进制码元的位数定义两码字的距离，称为汉明（Hamming）距离,简称码距●最小码距在一个码中，任意两个码字间距离的最小值，即码字集合中任意两元素间的最小距离，记为d0●码距的几何意义：以n=3的编码为例一般而言，码距是n维空间中单位正多面体顶点之间的汉明距离7.2纠错编码的基本原理(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1●最小码距与检、纠错能力关系●一个码能检测e个错码，则要求其最小码距d0≥e+1反之，若码的最小距离为d0，则最多能检测d0-1个错码●一个码能纠正t个错码，则要求其最小码距d0≥2t+1反之，若码的最小距离为d0，则最多能纠正(d0-1)/2个错码7.2纠错编码的基本原理0123BA汉明距离ed0码距等于3的两个码组BtA汉明距离012345td0码距等于5的两个码组●最小码距与检、纠错能力关系●一个码能纠正t个错码，同时能检测e个错码，则要求其最小码距d0≥e+t+1(et)7.2纠错编码的基本原理●误码率性能和带宽的关系采用编码降低误码率所付出的代价是带宽的增大10-610-510-410-310-210-1编码后Eb/n0(dB)编码和误码率关系PeCDEAB2PSK7.3纠错编码系统的性能●功率和带宽的关系采用编码以节省功率，并保持误码率不变，付出的代价也是带宽增大。10-610-510-410-310-210-1编码后Eb/n0(dB)编码和误码率关系PeCDEAB2PSK7.3纠错编码系统的性能●传输速率和带宽的关系对于给定的传输系统，其传输速率和Eb/n0的关系：式中，RB－码元速率。提高传输速率，采用编码以保持误码率不变；付出的代价仍是带宽增大BsssbRnPTnPnTPnE0000)/1(10-610-510-410-310-210-1编码后Eb/n0(dB)编码和误码率关系PeCDEAB2PSK7.3纠错编码系统的性能●编码增益定义：在保持误码率恒定条件下，采用纠错编码所节省的信噪比Eb/n0称为编码增益：式中，(Eb/n0)u－未编码时的信噪比(dB)(Eb/n0)c－编码后所需的信噪比(dB))(//00dBnEnEGcbubdB7.3纠错编码系统的性能10-610-510-410-310-210-1编码后Eb/n0(dB)编码和误码率关系PeCDEAB2PSK●一维奇偶监督码●在信息码元后附加一位监督位，使得码组中“1”的个数为偶数或奇数,按照奇偶数分为奇数监督码和偶数监督码两类●(n,n-1)分组码，码率为(n-1)/n（或k/(k+1))●奇数监督码中，此监督位使码组中“1”的个数为奇数：式中，a0为监督位，其他位为信息位●偶数监督码中，此监督位使码组中“1”的个数为偶数：式中，a0为监督位，其他位为信息位●检错能力－能够检测奇数个错码●应用：以随机错误为主的计算机通信系统，难于对付突发错误,计算机内部的数据传送，就是采用这种码7.4奇偶监督码1021aaann0021aaann信息位监督位晴000云011阴101雨110●二维奇偶监督码●有可能检测偶数个错码，但当偶数个错误刚好分布在矩阵的四个顶点时，则检测不出●适合检测突发错码●能够纠正部分错码7.4奇偶监督码信息码元监督码元1110000000111010011010100001110110001000010011001110111监督码元01101010011●基本概念●代数码－利用代数关系式产生监督位的编码●线性分组码－代数码的一种，其督位和信息位的关系由线性代数方程决定●汉明码－一种能够纠正一个错码的线性分组码●汉明码●发送端编码：将一位监督码元附加在信息码元后，使得码元中“1”码元个数为偶数●接收端译码：●计数接收码组中“1”码元个数是否为偶数，即计算：S=an-1+an-2+…+a0…………………………………………………（1）●S=0认为没错，S=1认为有错●（1）式称为监督方程/监督关系式，S称为校正子/校验子/伴随式7.5线性分组码●汉明码●监督位增加到2位：有两个监督方程，两个伴随式；两个伴随式组合有四种（00表示无错，01、10、11表示一位错码的三种可能位置）●监督位增加到r位：可指示一位错码的（2r-1）个可能位置●一般说来，对于（n，k)分组码，若希望用r=n-k个监督位构造出的r个监督关系式来指示一位错码的n种可能位置，则要求：2r-1≥n即2r≥k+r+1……………………………………………（2）●举例：构造一（n，k)分组码，k=4并能纠正一位错码●欲纠正一位错码，由（2）式知r≥3，取r=3，则n=k+r=7●设7位码元为：a6a5……a0；三个伴随式：S1、S2、S3；则可规定S1S2S3的八种组合与一位错码的对应关系如下（也可规定为另一种对应关系）：7.5线性分组码S1S2S3错码位置S1S2S3错码位置000无错011a3001a0101a4010a1110a5100a2111a67.5线性分组码●汉明码●举例：构造一（n，k)分组码，k=4并能纠正一位错码从上表可见：●当一位错码发生在a2、a4、a5或a6上时，S1为1；否则为0。即a2、a4、a5和a6构成偶监督关系：S1=a2+a4+a5+a6同理，a1、a3、a5和a6构成偶监督关系：S2=a1+a3+a5+a6a0、a3、a4和a6构成偶监督关系：S3=a0+a3+a4+a67.5线性分组码●汉明码●发端编码原则信息码元a6、a5、a4、a3来源于待编码的信息序列；监督码元a2、a1、a0的取值应根据信息码元按监督关系式来决定，即使上面三式中的S1、S2、S3均为0：a2+a4+a5+a6=0a1+a3+a5+a6=0……………………………………（3）a0+a3+a4+a6=0a2=a4+a5+a6a1=a3+a5+a6………………………………………（4）a0=a3+a4+a6于是，给定信息位后，根据上式算出各监督位，于是该编码的所有码组如下表：●汉明码的编码效率较高，其编码效率：该汉明码的码率较高：k/n=4/7≈57%。与相同码长、能纠正一位错码的其他分组码相比，该码效率最高，且实现简单。信息位监督位信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111nrrnkrr