编码chapter1

1、第一章 纠错码概述 陆以勤在一切哲学那里，体系都是暂时的东西，但包含在体系在一切哲学那里，体系都是暂时的东西，但包含在体系中的真正有价值的方法却可以长久地启发人心智、发人中的真正有价值的方法却可以长久地启发人心智、发人深思。深思。 我们所能有的最美好的经验是奥秘的经验，谁要是体验我们所能有的最美好的经验是奥秘的经验，谁要是体验不到它，谁要是不再有好奇心，也不再有惊讶的感觉，不到它，谁要是不再有好奇心，也不再有惊讶的感觉，他就无异于行尸走肉。他就无异于行尸走肉。一、什么叫纠错码通信系统模型信源信源编码信道编码+信道 译码信源译码信宿umc噪声e(t)r(t)=s(t)+e(t) mu压缩编码压缩

2、编码检纠错检纠错编码编码信道：消息的传递途径，可以物信道：消息的传递途径，可以物理信道，也可以是一些处理过程，理信道，也可以是一些处理过程，如如CD复制，硬盘，物流等复制，硬盘，物流等调制s(t)解调r=c+eAWGN (additive white Gaussian noise) 信源信道联合编码信源信道联合编码密码编码密码编码编码调制编码调制(conded modulation)对于无线信道，还有调制和解调信道模型ask和apk为信道衰落因子， nsk和npk为两个独立分布的高斯噪声。对于高斯白噪声信道， ask和apk都为1。AWGN (additive white Gaussian n

3、oise) 2.纠错的两种方式：ARQ： Automatic Repeat Quest,Automatic Repeat Quest,自动重发请求，前提：检错FEC：Forward error correct：前向纠错ARQ：重传反馈（：重传反馈（p5) Automatic Repeat QuestAutomatic Repeat QuestData Frame nAck nData Frame n+1Ack n+1Waiting timeWaiting timeError ControlStop and Wait ARQSlide Windows ARQSend one frame at a

4、 timeSend several frames at a timeGo-back nSelective-rejectStop-and-Wait ARQ: Stop-and-Wait ARQ: Damaged FrameFlashStop-and-Wait ARQ: LostStop-and-Wait ARQ: Lost FrameStop-and-Wait ARQ: Lost ACKStop-and-Wait ARQ: Lost ACKSlide WindowsSlide WindowsSliding Window ExampleGo-back n: 回退n帧协议： damaged fram

5、eFlashGo-back n: Go-back n: 回退回退n n帧协议：帧协议：lost framelost frameGo-back n: Go-back n: 回退回退n n帧协议：帧协议：lost ACKlost ACKSelective Reject: 选择拒绝2.6 HDLC p.340, 226 p.340, 226页页,11.6,11.6FlagAddressControlInformationFlagFCS1 8011111102/4 bytes1-n bytes1/2 bytes0最后最后1byte 的第的第8位位为为1表示地址结束表示地址结束0N(S)P/F01111

6、11001N(R)15234678I: Information frame信息帧信息帧1SP/FN(R)01MP/FM1S: Supervisory frame监督帧监督帧U: Unnumbered frame无编号帧无编号帧8 bits Control 字段字段0N(S)P/FN(R)152346789131011 121415 1610 0 0 0 P/FN(R)0I:信息帧信息帧S:监督帧监督帧S16 bits Control 字段字段N(S) :发送顺序号发送顺序号N(R) ：接收顺序号接收顺序号S: 监督功能位监督功能位M: 无编号功能位无编号功能位P/F: 轮询轮询/终止位终止位S

7、: 00: 接收就绪接收就绪RR 10：接收未就绪接收未就绪RNR01：拒绝：拒绝, 从顺序号从顺序号N开始重传开始重传REJ 11：选择拒绝，重传顺序号为选择拒绝，重传顺序号为N的的1帧帧SREJ确认确认应答应答非确认非确认应答应答RNR可用于流量控制，告诉对方停发信息帧可用于流量控制，告诉对方停发信息帧REJ可用于差错控制，告诉对方重新发送信息帧可用于差错控制，告诉对方重新发送信息帧监督帧监督帧在多终端线路的场合用来区在多终端线路的场合用来区分各个终端，对于点到点，分各个终端，对于点到点，用来区分命令和响应用来区分命令和响应帧类别帧类别位位置位位置命命 令令响响 应应b1 b8 b1 b8

8、 方向方向DCE =DTEDTE =DCE0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 10 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1地址域地址域扩充方式扩充方式（U帧仍为帧仍为1字节）字节）FlashPiggyback：捎带确认捎带确认(法法)A technique used to return acknowledgement information across a full-duplex (two-way simultaneous) data link without the use of special (acknowledgement) message

9、. The acknowledgement information relating to the flow of message in one direction is embedded (piggybacked) into normal data-carrying message flowing in the reverse direction.经全双工经全双工( (双向同时双向同时) )数据链路数据链路, ,不用专门不用专门( (确认确认) )报文返回报文返回确认信息所用的技术。与一个方向的报文流有关的确认确认信息所用的技术。与一个方向的报文流有关的确认信息钳在反方向正常携带数据的报文流

10、中。信息钳在反方向正常携带数据的报文流中。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) (1,0,0)(1,1) (1,1,1) （0,1,1)（0,0,1)（1,0,1)（1,1,1)4.纠错码的三个例子1.

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

12、h12m2+h1kmkp2= h21m1+h22m2+h2kmk。pr= hr1m1+hr2m2+hrkmkh11m1+h12m2+h1kmk- p p1 =0h21m1+h22m2+h2kmk- p p2 =0。hr1m1+hr2m2+hrkmk- p pr =0c HT=0h11h12h1k-1 0 00h21h22h2k 0 -1 00hr1hr2hrk 0 0 0-1H=校验矩阵(n-k) n 矩阵h h1h h2h hn=r维列矢量线性分组码（2）假设噪声只有1位，发生在第i位，即 e=(00010)第i位c HT=0r HT=(c+e) HT= c HT+e HT=e HT=s (

13、校正子）校正子）s=r HT=e HT=(00010) HT =(00010) h h1h h2h hn=hi纠错决策：s=0,可认为收到的是一个码字（不一定没有错） s 0,而且错误只有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 01 1 0 0 1 1 01 0 1 0 1 0 1汉明码的编码例1：7,4,3 循环

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

15、环移位获得全部码字5.按码元取值：二进制码（缺省）,q进制码（q=pm,p为素数,m为正整数）6.按码元的纠错能力：等保护码，不等保护码交叉分类见图1-11a11a12a1ka21a22a2kar1ar2ark存入顺序发送顺序Turbo码：卷积码交织码码：卷积码交织码 LDPC：线性分组码：线性分组码循环码的数学概念010001110001100001101 g(x)11010000011010011010010100010010111 (x+1)g(x) 0111001010111010111001110010110010110010110000000 0 g(x)1111111 (x3+x

16、+1)g(x)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(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

17、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 0 0 0 0)二、纠错码的背景知识1.判决x=1:硬判决x=?:不判决x=p(1),p(0):软判决所以，信道的输入是二进制，但输出不一定是二进制, 如果输出是二进制,则叫二进制信道,如果输出是q进制,则为q进制信道2.信道模型(1)(1)二进制信道0101p00p11p10p01P=p00 p01p10 p11转移矩阵01011- pe1- pepepe2.信道模型(2)(a) 2进制对称信道(BSC, binary symmetric

18、channel)(b) 2进制非对称信道(BAC , binary asymmetric channel)010111- p1p1010111- p0p0Z信道2.信道模型(3)(c) 2进制删除信道(BEC, binary erasure channel)010 x1pepeqq1- pe-q1- pe-qpe=0的BEC称为二进制纯删除信道x:未知或待定信号，称为删除符号（p2)2.信道模型(4)0101q-1p0,0p1,q-1p1,0p0,1P=p0,0 p0,1p0,q-1p1,0 p1,1p1,q-1(2)q进制信道p0,q-1p1.1p(0/0) p(1/0)p(q-1/0)p(

19、0/1) p(1/1)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的DMC3.汉明距离与重量汉明重量: 码字x的非零位数, 记为w(x)。(2) 汉明距离: 等长码字x、y的汉明距离d(x,y)=w(x+y)。(3) 最小汉明距离: 一组码字中任一对码字汉明距离的最小值。4.译码准则(1)()/ (21iiiiiErprccpPnic )/ (min)()/ (minmin2121iiiiiiiiiErccprprccpPnnC= c1,

20、 c2, . c2k 码字集合R= r1, r2, . r2n 接收字集合译码就是从接收字ri 估计发送的码字为(1) 译码器错误译码概率译码的原则就是保证PE为最小与译码方法无关所以译码的准则就是,对于收到的ri,使 最小)/ (iiirccp4.译码准则(2)/ (iiirccp(3)最大后验概率译码(MAP, maximum a posteriori) 收到的ri , 在c1, c2, . c2k 选择 作为ci的估值, 使 最大.ic (4)最大似然率(Most-Likelihood-Decision ，or maximum likelihood decoder, MLD)收到的ri

21、, 在c1, c2, . c2k 选择 作为ci的估值, 使 最大.ic )/(iicrp (2)最小距离译码准则 (minimum distance deconder)收到的ri , 在c1, c2, . c2k 选择作 为ci的估值, 使d(ri - )最小.ic ic d（ri, )= d(ri- ), d（ri, )越小， 越大。 ic ic ic )/ (iiirccp所以最小距离译码与最大后验概率译码是一致的。4.译码准则(3)对于DMC（离散无记忆信道），最大似然率译码与最小距离译码也是一致的。下以BSC（二进制对称信道）为例。0101q=1- pppq=1- p增加而单调减少。

22、随着所以一般则令iiiddniiiiinjjijiiinijiiiinijiiiidcrppqpqcrppqcrddcrcrpcccccrrrrrii)/(,)/(,1),()/()/(). ().(10,2,1 ,2,1 ,5.纠错码的应用(1)几乎所有的以HDLC衍伸的协议。(X.25,FR,Ethernet,ISDN,ATM,都带有CRC.)(2)加密和保护文本。(3)码率R=1/2，约束度k=7的卷积码是商用卫星通信的编码标准。(4)美国航天局（NSAS)和欧洲航空局（ESA)深空通信编码标准。RS外编码器卷积内编码器信道RS外译码器卷积内译码器255，223，33 8元元RS码码码率

23、码率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 check，低密度奇偶校验码)被认为是B3G(beyond 3G)移动系统的编码方案；（9）数字广播(DRM,DAB,DVB)（10）

24、IEEE802.16 (WiMax)各种高速数据广播系统特性摘要 DARC（1993年）年）日本日本 NHK HSDS （1992年）年）美国美国 SeikoFMHDS（1997年）年）北京广播学北京广播学院院副载波频率副载波频率76kHZ66.5kHZ70kHZ占用频宽占用频宽6095kHZ61-76kHZ60.9-79.1kHZ信道速率信道速率16Kbps19Kbps17.5/28Kbps调制方式调制方式L-MSKAM+PSKQPSK纠错码纠错码(272,190)乘乘积码积码(12,8)汉明码汉明码(48,32)R-S码码交织交织交织交织卷积交织卷积交织检错码检错码14BIT CRC 16

25、BIT CRC16BIT CRC频偏频偏3-7.5KHZ3.5-7.5KHZ4-7.5KHZ新欧洲卫星广播系统新欧洲卫星广播系统DVB-S52：LDPC和和BCH码组成的连接码码组成的连接码常用的CRC国际标准CRC(Cyclic Redundancy Check)循环冗余校验码是一种缩短循环码，广泛用于帧校验，习惯上把校验位称作CRC校验码HDLC(high-level data link control)HDLC(high-level data link control)FlagAddressControlInformationFlagFCS011111102/4 bytes1-n byt

26、es1/2 bytes01111110HDLC的子集LAPB：平衡式链路访问规程，平衡式链路访问规程，Link access procedure,balancedLAPD (Q.921) ：D信道链路访问规程，信道链路访问规程，Link access procedure for D channelLAPM：调制解调器链路访问规程，调制解调器链路访问规程，link access procedure for modemsLAPF (Q.922) : link access procedure for frame model bearer services 帧帧方式承载业务的数据链路访问规程方式承载

27、业务的数据链路访问规程, 以以LAPD为基础并作延伸为基础并作延伸LAPF分两部分：分两部分： DL-CORE: 数据链路核心协议，支持帧中继承载业务数据链路核心协议，支持帧中继承载业务 DL-CONTROL: 数据链路控制协议数据链路控制协议 X.25 LayersNetworkPacket layer protocol (PLP)Data linkLink access procedure, balanced (LAPB)PhysicalEIA-232, V-serials, X.21othersFlag Address ControlInformationFlagFCSHeaderUse

28、r payload & headers from upper layersPLP Packet （包层）包层）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)LAPF (Q.922)FlagAddres

29、sControlInformationFlagFCS011111102/4 bytes2-n bytes1/2 bytes01111110DLCIC/R EADLCIFECN BECNDE EA6 bits4 bits1 bit 1 bit1 bit 1 bit 1 bit1 bitLAPF Control FieldFlagAddressControlInformationFlagFCS与与HDLC相同相同FlagAddress InformationFCSFlagDLCIC/R EADLCIFECN BECNDE EAFCS:frame check sequenceDLCI:data li

30、nk connection identifierC/R: command/response, unused in FREA: extended addressFECN:forward explicit congestion notificationBECN:backward explicit congestion notificationDE:discard eligibility6 bit4 bit1 bit 1 bit1 bit 1 bit 1 bit1 bit1 byte1 byte24 byte2 byte=8189 bytes in standards,Normally=1600by

31、tesA ether net packet=1500bytesNo Control FieldFR: LAPF-COREISDN LayersUsers choiceEnd-to-enduser signalingX.25 and otherCall cotrolQ.931LAPB and othersLAPD (Q.921)BRI (I.430) & PRI (I.431)PhysicalData linkNetworkUser definedB channelD channelProtocol discriminator0 0 0 0Length of call reference

32、 valueCall reference value0 Message typeOther information elements(as required)Bits8 7 6 5 4 3 2 1 Octets123etcInformation(ISDN layer 3)FCSFlagControlAddressFlagSAPITE1EACREALink control fieldsequence no.ACKs, NAKs, flow control,link addressesSAPs in the terminalPreambleSFDDestinationaddress(DA)Sour

33、ceaddress (SA)Length/type of PDUDataCRC7 bytes1 byte6 bytes6 bytes2 bytes4 bytesDSAPSSAPControlInformationCyclic redundancy checkPreamble:同步前导，同步前导，101010SFD: 帧定界符帧定界符10101011MACPADPDU of EthernetSDH/SONET (Physical layer)、T3ATM SARAAL: ATM adaptation layer SAR: segmentation and reassemblyCS: conver

34、gence sublayerCSAAL1 SARCSAAL2 SARCSAAL3/4 SARCSAAL5ATM LayersPAD: added when necessary to fill out the final cell(s) in a segment packetAAL1AAL2AAL3/4AAL5ATM LayerSegment From AAL layer (48 bytes)Header (5tyes)0 GFCVCIVPI4 VPI 7VCIVCI4 PT 6 CLPHECPayloadData(48bytes)UNI CellVPI4 VCI 70 VPIVCIVCI4 PT 6 CLPHECPayloadData(48bytes)NNI CellGFC: Generic flow