第一章 纠错码概述.ppt

1、第一章 纠错码概述,陆以勤,在一切哲学那里，体系都是暂时的东西，但包含在体系中的真正有价值的方法却可以长久地启发人心智、发人深思。,我们所能有的最美好的经验是奥秘的经验，谁要是体验不到它，谁要是不再有好奇心，也不再有惊讶的感觉，他就无异于行尸走肉。,一、什么叫纠错码,通信系统模型,信源,信源 编码,信道 编码,+,信道 译码,信源 译码,信宿,u,m,c,噪声,e(t),r(t)= s(t)+e(t), m, u,压缩编码,检纠错 编码,信道：消息的传递途径，可以物理信道，也可以是一些处理过程，如CD复制，硬盘，物流等,调制,s(t),解调,r=c+e,AWGN (additive white

2、 Gaussian noise),信源信道联合编码 密码编码,编码调制 (conded modulation),对于无线信道，还有调制和解调,信道模型,ask和apk为信道衰落因子， nsk和npk为两个独立分布的高斯噪声。 对于高斯白噪声信道， ask和apk都为1。,AWGN (additive white Gaussian noise),2.纠错的两种方式： ARQ： Automatic Repeat Quest,自动重发请求，前提：检错 FEC：Forward error correct：前向纠错,ARQ：重传反馈（p5) Automatic Repeat Quest,Data Fra

3、me n,Ack n,Data Frame n+1,Ack n+1,Waiting time,Waiting time,Error Control,Stop and Wait ARQ,Slide Windows ARQ,Send one frame at a time,Send several frames at a time,Go-back n,Selective-reject,Stop-and-Wait ARQ: Damaged Frame,Flash,Stop-and-Wait ARQ: Lost Frame,Stop-and-Wait ARQ: Lost ACK,Slide Windo

4、ws,Sliding Window Example,Go-back n: 回退n帧协议： damaged frame,Flash,Go-back n: 回退n帧协议：lost frame,Go-back n: 回退n帧协议：lost ACK,Selective Reject: 选择拒绝,2.6 HDLC p.340, 226页,11.6,Flag,Address,Control,Information,Flag,FCS,1 8,01111110,2/4 bytes,1-n bytes,1/2 bytes,0,最后1byte 的第8位为1表示地址结束,0,N(S),P/F,01111110,0,

5、1,N(R),1,5,2,3,4,6,7,8,I: Information frame 信息帧,1,S,P/F,N(R),0,1,M,P/F,M,1,S: Supervisory frame监督帧,U: Unnumbered frame 无编号帧,8 bits Control 字段,0,N(S),P/F,N(R),1,5,2,3,4,6,7,8,9,13,10,11,12,14,15,16,1,0 0 0 0,P/F,N(R),0,I:信息帧,S:监督帧,S,16 bits Control 字段,N(S) :发送顺序号 N(R) ：接收顺序号 S: 监督功能位 M: 无编号功能位 P/F: 轮

6、询/终止位,S: 00: 接收就绪RR 10：接收未就绪RNR,01：拒绝, 从顺序号N开始重传REJ 11：选择拒绝，重传顺序号为N的1帧SREJ,确认 应答,非确认 应答,RNR可用于流量控制，告诉对方停发信息帧 REJ可用于差错控制，告诉对方重新发送信息帧,监督帧,在多终端线路的场合用来区分各个终端，对于点到点，用来区分命令和响应,帧类别,位位置,命 令,响 应,b1 b8,b1 b8,方向,DCE =DTE,DTE =DCE,0 0 0 0 0 0 1 1,0 0 0 0 0 0 0 1,0 0 0 0 0 0 0 1,0 0 0 0 0 0 1 1,地址域,扩充方式 （U帧仍为1字节

7、）,Flash,Piggyback：捎带确认(法),A technique used to return acknowledgement information across a full-duplex (two-way simultaneous) data link without the use of special (acknowledgement) message. The acknowledgement information relating to the flow of message in one direction is embedded (piggybacked) into

8、 normal data-carrying message flowing in the reverse direction. 经全双工(双向同时)数据链路,不用专门(确认)报文返回确认信息所用的技术。与一个方向的报文流有关的确认信息钳在反方向正常携带数据的报文流中。,3.纠错码的原理,附加一些消息对原信息的性质加以说明。 从几何学上看，是通过空间变换把一些紧密排列的点重新分布，使之有一定距离。如：银行卡号，偶校验码,（0,0),（1,0),（1,1),（0,1),（0,0,0),（1,0,0),（1,1,0),（0,1,0),(0,0) (0,0,1) (0,1) (0,1,0) (1,0)

9、 (1,0,0) (1,1) (1,1,1),（0,1,1),（0,0,1),（1,0,1),（1,1,1),4.纠错码的三个例子,1.奇偶校验码问题：1. 奇偶校验码能否纠错？(答案）2. 提高方式：CRC(Cyclic Redundancy Check)循环冗余校验码，是一种缩短循环码，广泛用于帧校验，习惯上把校验位称作CRC校验码 条形码的检错 2.重复码（见p10,例1.1)00100 000 000 111 000 0003.线性分组码,线性分组码（1）,c = (m1m2mkp1p2pr) 二进制 m1m2mk：信息位，p1p2pr：校验位，n=k+r: 码长，记为（n,k) 假设

10、检验位与信息位是线性关系，即： p1= h11m1+h12m2+h1kmk p2= h21m1+h22m2+h2kmk 。 pr= hr1m1+hr2m2+hrkmk,h11m1+h12m2+h1kmk- p1 =0 h21m1+h22m2+h2kmk- p2 =0 。 hr1m1+hr2m2+hrkmk- pr =0,c HT=0,h11h12h1k-1 0 00 h21h22h2k 0 -1 00 hr1hr2hrk 0 0 0-1,H=,校验矩阵 (n-k) n 矩阵,h1h2hn,=,r维列矢量,线性分组码（2）,假设噪声只有1位，发生在第i位，即 e=(00010),第i位,c HT

11、=0 r HT=(c+e) HT= c HT+e HT=e HT=s (校正子）,s=r HT=e HT=(00010) HT,=(00010),h1 h2 hn,=hi,纠错决策：s=0,可认为收到的是一个码字（不一定没有错）s0,而且错误只有1位，则校正子等于校验矩阵第几列，则错误发生在第几位。 前提：为了使H各列能互相区分，对于2元码，2r n =k+r, 例如，如果取下限（意味着？），即 2（n-k) -1= n, 则为汉明码（p62)。,汉明码,汉明码的最简单的构造方法是：校验矩阵的各列依次取12（n-k)-1，如（7，4）汉明码：,1 1 1 1 0 0 0 1 1 0 0 1 1

12、 0 1 0 1 0 1 0 1,汉明码的编码,例1：7,4,3 循环汉明码，g(x)=x3+x+1,H=,1110100 0111010 1101001,纠错码的数学知识可以帮组构造简单的编码电路,汉明码的译码电路,例1：7,4,3 循环汉明码，g(x)=x3+x+1,H=,1110100 0111010 1101001,要构造简单的译码电路，必需纠错码的数学知识,5.纠错码的分类,1.按信息元处理方法：分组码：校验元仅与本组信息元有关卷积码：校验元不仅与本组信息元有关，而且与前m组有关 2.按检验元与信息元之间的关系：线性码，非线性码 3.按错误类型：纠突发错误码，纠随机错误码可利用交织技

13、术把突发错误转化为随机错4.按码字之间的关系：循环码：全部码字可用循环移位获得非循环码：不能通过循环移位获得全部码字 5.按码元取值：二进制码（缺省）,q进制码（q=pm,p为素数,m为正整数） 6.按码元的纠错能力：等保护码，不等保护码 交叉分类见图1-11,a11a12a1k a21a22a2k ar1ar2ark,存入 顺序,发送 顺序,Turbo码：卷积码交织码 LDPC：线性分组码,循环码的数学概念,g(x) (0 0 0 1 1 0 1) xg(x) (0 0 1 1 0 1 0) x2g(x) (0 1 1 0 1 0 0) x3g(x) (1 1 0 1 0 0 0) x4g(

14、x) (1 0 1 0 0 0 1) x5g(x) (0 1 0 0 0 1 1) x6g(x) (1 0 0 0 1 1 0) (x+1)g(x) (0 0 1 0 1 1 1) x(x+1)g(x) (0 1 0 1 1 1 0) x2(x+1)g(x) (1 0 1 1 1 0 0) x3(x+1)g(x) (0 1 1 1 0 0 1) x4(x+1)g(x) (1 1 1 0 0 1 0) x5(x+1)g(x) (1 1 0 0 1 0 1) x6(x+1)g(x) (1 0 0 1 0 1 1) (x3+x+1)g(x) (1 1 1 1 1 1 1) 0*g(x) (0 0 0

15、 0 0 0 0),二、纠错码的背景知识,1.判决,x=1:硬判决 x=?:不判决 x=p(1),p(0):软判决,所以，信道的输入是二进制，但输出不一定是二进制, 如果输出是二进制,则叫二进制信道,如果输出是q进制,则为q进制信道,2.信道模型(1),(1)二进制信道,01,01,p00,p11,p10,p01,P=,p00 p01 p10 p11,转移矩阵,01,01,1- pe,1- pe,pe,pe,2.信道模型(2),(a) 2进制对称信道(BSC, binary symmetric channel),(b) 2进制非对称信道(BAC , binary asymmetric chan

16、nel),01,01,1,1- p1,p1,01,01,1,1- p0,p0,Z信道,2.信道模型(3),(c) 2进制删除信道(BEC, binary erasure channel),01,0x1,pe,pe,q,q,1- pe-q,1- pe-q,pe=0的BEC称为二进制纯删除信道,x:未知或待定信号，称为删除符号（p2),2.信道模型(4),01,01 q-1,p0,0,p1,q-1,p1,0,p0,1,P=,p0,0 p0,1p0,q-1 p1,0 p1,1p1,q-1,(2)q进制信道,p0,q-1,p1.1,p(0/0) p(1/0)p(q-1/0) p(0/1) p(1/1)

17、p(q-1/1),=,p(i/0)=p(q-1-i /1), i=0,1,q-1 的q进制信道叫离散无记忆信道(DMC，discrete memoryless channel) 二进制对称信道BSC是q=2的DMC,3.汉明距离与重量,汉明重量: 码字x的非零位数, 记为w(x)。 (2) 汉明距离: 等长码字x、y的汉明距离d(x,y)=w(x+y)。 (3) 最小汉明距离: 一组码字中任一对码字汉明距离的最小值。,4.译码准则(1),C= c1, c2, . c2k 码字集合 R= r1, r2, . r2n 接收字集合 译码就是从接收字ri 估计发送的码字为译码器错误译码概率,译码的原则

18、就是保证PE为最小,与译码方法无关,所以译码的准则就是,对于收到的ri,使 最小,4.译码准则(2),(3)最大后验概率译码(MAP, maximum a posteriori) 收到的ri , 在c1, c2, . c2k 选择 作为ci的估值, 使 最大.,(4)最大似然率(Most-Likelihood-Decision ，or maximum likelihood decoder, MLD) 收到的ri , 在c1, c2, . c2k 选择 作为ci的估值, 使 最大.,(2)最小距离译码准则 (minimum distance deconder) 收到的ri , 在c1, c2,

19、. c2k 选择作 为ci的估值, 使d(ri - )最小.,d（ri, )= d(ri- ), d（ri, )越小， 越大。,所以最小距离译码与最大后验概率译码是一致的。,4.译码准则(3),对于DMC（离散无记忆信道），最大似然率译码与最小距离译码也是一致的。 下以BSC（二进制对称信道）为例。,01,01,q=1- p,p,p,q=1- p,5.纠错码的应用,(1)几乎所有的以HDLC衍伸的协议。(X.25,FR,Ethernet,ISDN,ATM,都带有CRC.) (2)加密和保护文本。 (3)码率R=1/2，约束度k=7的卷积码是商用卫星通信的编码标准。 (4)美国航天局（NSAS)

20、和欧洲航空局（ESA)深空通信编码标准。,RS外编码器,卷积内编码器,信道,RS外译码器,卷积内译码器,255，223，33 8元RS码,码率R=1/2，约束度k=7的串联级联码,(5)IBM3850海量磁带机采用（15，13）BCH码（16元BCH码），IBM3370磁盘机采用RS码。 （6）GSM采用R=1/2,k=5的卷积码，IS-94和IS-136采用R=1/2,k=6的卷积码，IS-95在上行线路采用R=1/2,k=9的卷积码，下行线路采用R=1/3,k=9的卷积码。 （7）Turbo码和用户检测被认为3G的关键技术。 （8）LDPC (low density parity chec

21、k，低密度奇偶校验码)被认为是B3G(beyond 3G)移动系统的编码方案； （9）数字广播(DRM,DAB,DVB) （10）IEEE802.16 (WiMax),各种高速数据广播系统特性摘要,新欧洲卫星广播系统DVB-S52：LDPC和BCH码组成的连接码,常用的CRC国际标准,CRC(Cyclic Redundancy Check)循环冗余校验码 是一种缩短循环码，广泛用于帧校验，习惯上把校验位称作CRC校验码,HDLC(high-level data link control),Flag,Address,Control,Information,Flag,FCS,01111110,2/

22、4 bytes,1-n bytes,1/2 bytes,01111110,HDLC的子集 LAPB：平衡式链路访问规程，Link access procedure,balanced LAPD (Q.921) ：D信道链路访问规程，Link access procedure for D channel LAPM：调制解调器链路访问规程，link access procedure for modems LAPF (Q.922) : link access procedure for frame model bearer services 帧方式承载业务的数据链路访问规程, 以LAPD为基础并作延伸

23、LAPF分两部分：DL-CORE: 数据链路核心协议，支持帧中继承载业务DL-CONTROL: 数据链路控制协议,X.25 Layers,Network,Packet layer protocol(PLP),Data link,Link access procedure, balanced (LAPB),Physical,EIA-232, V-serials, X.21 others,Flag,Address,Control,Information,Flag,FCS,Header,User payload & headers from upper layers,PLP Packet （包层）,

24、1 Frame（帧层）,Link control field(a subset of HDLC) (sequence numbers, ACKs, NAKs, flow control, link address),Network interface control field (sequence numbers, ACKs, NAKs, flow control, logical channel number),LAPF (Q.922),Flag,Address,Control,Information,Flag,FCS,01111110,2/4 bytes,2-n bytes,1/2 byt

25、es,01111110,DLCI,C/R,EA,DLCI,FECN,BECN,DE,EA,6 bits,4 bits,1 bit,1 bit,1 bit,1 bit,1 bit,1 bit,LAPF Control Field,Flag,Address,Control,Information,Flag,FCS,与HDLC相同,Flag,Address,Information,FCS,Flag,DLCI,C/R,EA,DLCI,FECN,BECN,DE,EA,FCS:frame check sequence DLCI:data link connection identifier C/R: co

26、mmand/response, unused in FR EA: extended address FECN:forward explicit congestion notification BECN:backward explicit congestion notification DE:discard eligibility,6 bit,4 bit,1 bit,1 bit,1 bit,1 bit,1 bit,1 bit,1 byte,1 byte,24 byte,2 byte,=8189 bytes in standards, Normally =1600bytes,A ether net

27、 packet =1500bytes,No Control Field,FR: LAPF-CORE,ISDN Layers,Users choice,End-to-end user signaling,X.25 and other,Call cotrol Q.931,LAPB and others,LAPD (Q.921),BRI (I.430) & PRI (I.431),Physical,Data link,Network,User defined,B channel,D channel,Protocol discriminator,0 0 0 0,Length of call refer

28、ence value,Call reference value,0,Message type,Other information elements(as required),Bits,8 7 6 5 4 3 2 1,Octets,1,2,3,etc,Information (ISDN layer 3),FCS,Flag,Control,Address,Flag,SAPI,TE1,E A,C R,E A,Link control field sequence no. ACKs, NAKs, flow control, link addresses SAPs in the terminal,Pre

29、amble,SFD,Destination address(DA),Source address (SA),Length/typeof PDU,Data,CRC,7 bytes,1 byte,6 bytes,6 bytes,2 bytes,4 bytes,DSAP,SSAP,Control,Information,Cyclic redundancy check,Preamble:同步前导，101010 SFD: 帧定界符10101011,MAC,PAD,PDU of Ethernet,SDH/SONET (Physical layer)、T3,ATM,SAR,AAL: ATM adaptati

30、on layer SAR: segmentation and reassembly CS: convergence sublayer,CS,AAL1,SAR,CS,AAL2,SAR,CS,AAL3/4,SAR,CS,AAL5,ATM Layers,PAD: added when necessary to fill out the final cell(s) in a segmentpacket,AAL1,AAL2,AAL3/4,AAL5,ATM Layer,Segment From AAL layer (48 bytes),Header (5tyes),0 GFC,VCI,VPI,4 VPI

31、7,VCI,VCI,4 PT 6,CLP,HEC,Payload Data(48bytes),UNI Cell,VPI,4 VCI 7,0 VPI,VCI,VCI,4 PT 6,CLP,HEC,Payload Data(48bytes),NNI Cell,GFC: Generic flow control PT:Payload type VPI: Virtual path identifier CLP: Cell loss priority VCI: Virtual channel identifier HEC: Header error control,TCP,可靠的流传输端口到端口协议，传

32、输前必须先建立虚电路，通过差错检测和重传被破坏的帧保证可靠传输。IP和UDP 把每次传输的数据看作孤立的单元，相互之间没有联系，TCP把长的数据划分位为更小的单元，封装成段，在接收段，通过序列号对段重新排序。,UDP,UDP (user diagram protocol), 仅提供端到端传输所必须的基本功能，为上层PDU增加端口地址、校验和差错控制以及长度信息。不提供任何顺序或重新排序的功能。UDP仅提供一个校验和，对一个特定的数据段，并不包含ID或序列号，因此，它可以发现一个错误，由ICMP通知发送者有一个用户数据报被损坏和丢弃，但它们都没有能力指出是哪一个包丢了。,SCTP,Stream

33、Control Transmission Protocol (SCTP) is a new reliable, message-oriented transport layer protocol. SCTP, however, is mostly designed for Internet applications that have recently been introduced. These new applications need a more sophisticated service than TCP can provide.,IP协议,仅有头校验，内容校验放在TCP层,进度,第

34、一章 纠错码的基本概念 3学时 （第1周） 第二章 代数初步 3学时 （第2周） 第三章 线性分码组 6学时 （第34周） 第四章 多项式环与有限域 6学时 （第56周） 第五章 循环码 7学时 （第78周） 第六章 循环码的译码 6学时 （第910） 第七章 BCH码与Goppa码 3学时（第11周） 第十章 卷积码基础 6学时 （第12、13周） 第十二章 卷积码的译码 3学时 （第14周） 第十三章 Turbo码 3学时 （第15周） 第十四章 LDPC码 （补充） 3学时 （第16周） 复习 3学时 （第17周）,课本： 1.王新梅，肖国镇，纠错码原理与方法（修订版），西安电子科技大学出版社，2002。参考书 1.Shu Lin，Daniel J.Costello,Jr,Error Control Coding （2rd Edition) 差错控制编码(第2版），机械工业出版社，2007公共邮箱：, 密码：ee2000,可以纠错的检验阵列,行检验位,列检验位,e,返回,