第四章-多项式与有限域

第一章纠错码概述 陆以勤 在一切哲学那里 体系都是暂时的东西 但包含在体系中的真正有价值的方法却可以长久地启发人心智 发人深思 我们所能有的最美好的经验是奥秘的经验 谁要是体验不到它 谁要是不再有好奇心 也不再有惊讶的感觉 他就无异于行尸走肉 一 什么叫纠错码 通信系统模型 信源 信源编码 信道编码 信道译码 信源译码 信宿 u m c 噪声 e t r t s t e t m u 压缩编码 检纠错编码 信道 消息的传递途径 可以物理信道 也可以是一些处理过程 如CD复制 硬盘 物流等 调制 s t 解调 r c e AWGN additivewhiteGaussiannoise 信源信道联合编码密码编码 编码调制 condedmodulation 对于无线信道 还有调制和解调 信道模型 ask和apk为信道衰落因子 nsk和npk为两个独立分布的高斯噪声 对于高斯白噪声信道 ask和apk都为1 AWGN additivewhiteGaussiannoise 2 纠错的两种方式 ARQ AutomaticRepeatQuest 自动重发请求 前提 检错FEC Forwarderrorcorrect 前向纠错 ARQ 重传反馈 p5 AutomaticRepeatQuest DataFramen Ackn DataFramen 1 Ackn 1 Waitingtime Waitingtime ErrorControl StopandWaitARQ SlideWindowsARQ Sendoneframeatatime Sendseveralframesatatime Go backn Selective reject Stop and WaitARQ DamagedFrame Flash Stop and WaitARQ LostFrame Stop and WaitARQ LostACK SlideWindows SlidingWindowExample Go backn 回退n帧协议 damagedframe Flash Go backn 回退n帧协议 lostframe Go backn 回退n帧协议 lostACK SelectiveReject 选择拒绝 2 6HDLCp 340 226页 11 6 Flag Address Control Information Flag FCS 18 01111110 2 4bytes 1 nbytes 1 2bytes 0 最后1byte的第8位为1表示地址结束 0 N S P F 01111110 0 1 N R 1 5 2 3 4 6 7 8 I Informationframe信息帧 1 S P F N R 0 1 M P F M 1 S Supervisoryframe监督帧 U Unnumberedframe无编号帧 8bitsControl字段 0 N S P F N R 1 5 2 3 4 6 7 8 9 13 10 11 12 14 15 16 1 0000 P F N R 0 I 信息帧 S 监督帧 S 16bitsControl字段 N S 发送顺序号N R 接收顺序号S 监督功能位M 无编号功能位P F 轮询 终止位 S 00 接收就绪RR10 接收未就绪RNR 01 拒绝 从顺序号N开始重传REJ11 选择拒绝 重传顺序号为N的1帧SREJ 确认应答 非确认应答 RNR可用于流量控制 告诉对方停发信息帧REJ可用于差错控制 告诉对方重新发送信息帧 监督帧 在多终端线路的场合用来区分各个终端 对于点到点 用来区分命令和响应 帧类别 位位置 命令 响应 b1b8 b1b8 方向 DCE DTE DTE DCE 00000011 00000001 00000001 00000011 地址域 扩充方式 U帧仍为1字节 Flash Piggyback 捎带确认 法 Atechniqueusedtoreturnacknowledgementinformationacrossafull duplex two waysimultaneous datalinkwithouttheuseofspecial acknowledgement message Theacknowledgementinformationrelatingtotheflowofmessageinonedirectionisembedded piggybacked intonormaldata carryingmessageflowinginthereversedirection 经全双工 双向同时 数据链路 不用专门 确认 报文返回确认信息所用的技术 与一个方向的报文流有关的确认信息钳在反方向正常携带数据的报文流中 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 奇偶校验码问题 1 奇偶校验码能否纠错 答案 2 提高方式 CRC CyclicRedundancyCheck 循环冗余校验码 是一种缩短循环码 广泛用于帧校验 习惯上把校验位称作CRC校验码条形码的检错2 重复码 见p10 例1 1 001000000001110000003 线性分组码 线性分组码 1 c m1m2 mkp1p2 pr 二进制m1m2 mk 信息位 p1p2 pr 校验位 n k r 码长 记为 n k 假设检验位与信息位是线性关系 即 p1 h11m1 h12m2 h1kmkp2 h21m1 h22m2 h2kmk pr hr1m1 hr2m2 hrkmk h11m1 h12m2 h1kmk p1 0h21m1 h22m2 h2kmk p2 0 hr1m1 hr2m2 hrkmk pr 0 cHT 0 h11h12 h1k 100 0h21h22 h2k0 10 0 hr1hr2 hrk000 1 H 校验矩阵 n k n矩阵 h1h2 hn r维列矢量 线性分组码 2 假设噪声只有1位 发生在第i位 即e 00 01 0 第i位 cHT 0rHT c e HT cHT eHT eHT s 校正子 s rHT eHT 00 01 0 HT 00 01 0 h1h2 hn hi 纠错决策 s 0 可认为收到的是一个码字 不一定没有错 s 0 而且错误只有1位 则校正子等于校验矩阵第几列 则错误发生在第几位 前提 为了使H各列能互相区分 对于2元码 2r n k r 例如 如果取下限 意味着 即2 n k 1 n 则为汉明码 p62 汉明码 汉明码的最简单的构造方法是 校验矩阵的各列依次取1 2 n k 1 如 7 4 汉明码 111100011001101010101 汉明码的编码 例1 7 4 3 循环汉明码 g x x3 x 1 H 111010001110101101001 纠错码的数学知识可以帮组构造简单的编码电路 汉明码的译码电路 例1 7 4 3 循环汉明码 g x x3 x 1 H 111010001110101101001 要构造简单的译码电路 必需纠错码的数学知识 5 纠错码的分类 1 按信息元处理方法 分组码 校验元仅与本组信息元有关卷积码 校验元不仅与本组信息元有关 而且与前m组有关2 按检验元与信息元之间的关系 线性码 非线性码3 按错误类型 纠突发错误码 纠随机错误码可利用交织技术把突发错误转化为随机错4 按码字之间的关系 循环码 全部码字可用循环移位获得非循环码 不能通过循环移位获得全部码字5 按码元取值 二进制码 缺省 q进制码 q pm p为素数 m为正整数 6 按码元的纠错能力 等保护码 不等保护码交叉分类见图1 11 a11a12 a1ka21a22 a2k ar1ar2 ark 存入顺序 发送顺序 Turbo码 卷积码 交织码LDPC 线性分组码 循环码的数学概念 g x 0001101 xg x 0011010 x2g x 0110100 x3g x 1101000 x4g x 1010001 x5g x 0100011 x6g x 1000110 x 1 g x 0010111 x x 1 g x 0101110 x2 x 1 g x 1011100 x3 x 1 g x 0111001 x4 x 1 g x 1110010 x5 x 1 g x 1100101 x6 x 1 g x 1001011 x3 x 1 g x 1111111 0 g x 0000000 二 纠错码的背景知识 1 判决 x 1 硬判决x 不判决x p 1 p 0 软判决 所以 信道的输入是二进制 但输出不一定是二进制 如果输出是二进制 则叫二进制信道 如果输出是q进制 则为q进制信道 2 信道模型 1 1 二进制信道 01 01 p00 p11 p10 p01 P p00p01p10p11 转移矩阵 01 01 1 pe 1 pe pe pe 2 信道模型 2 a 2进制对称信道 BSC binarysymmetricchannel b 2进制非对称信道 BAC binaryasymmetricchannel 01 01 1 1 p1 p1 01 01 1 1 p0 p0 Z信道 2 信道模型 3 c 2进制删除信道 BEC binaryerasurechannel 01 0 x1 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 0p0 1 p0 q 1p1 0p1 1 p1 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 p q 1 1 p i 0 p q 1 i 1 i 0 1 q 1的q进制信道叫离散无记忆信道 DMC discretememorylesschannel 二进制对称信道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估计发送的码字为译码器错误译码概率 译码的原则就是保证PE为最小 与译码方法无关 所以译码的准则就是 对于收到的ri 使最小 4 译码准则 2 3 最大后验概率译码 MAP maximumaposteriori 收到的ri 在c1 c2 c2k选择作为ci的估值 使最大 4 最大似然率 Most Likelihood Decision ormaximumlikelihooddecoder MLD 收到的ri 在c1 c2 c2k选择作为ci的估值 使最大 2 最小距离译码准则 minimumdistancedeconder 收到的ri 在c1 c2 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 和欧洲航空局 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 lowdensityparitycheck 低密度奇偶校验码 被认为是B3G beyond3G 移动系统的编码方案 9 数字广播 DRM DAB DVB 10 IEEE802 16 WiMax 各种高速数据广播系统特性摘要 新欧洲卫星广播系统DVB S52 LDPC和BCH码组成的连接码 常用的CRC国际标准 CRC CyclicRedundancyCheck 循环冗余校验码是一种缩短循环码 广泛用于帧校验 习惯上把校验位称作CRC校验码 HDLC high leveldatalinkcontrol Flag Address Control Information Flag FCS 01111110 2 4bytes 1 nbytes 1 2bytes 01111110 HDLC的子集LAPB 平衡式链路访问规程 Linkaccessprocedure balancedLAPD Q 921 D信道链路访问规程 LinkaccessprocedureforDchannelLAPM 调制解调器链路访问规程 linkaccessprocedureformodemsLAPF Q 922 linkaccessprocedureforframemodelbearerservices帧方式承载业务的数据链路访问规程 以LAPD为基础并作延伸LAPF分两部分 DL CORE 数据链路核心协议 支持帧中继承载业务DL CONTROL 数据链路控制协议 X 25Layers Network Packetlayerprotocol PLP Datalink Linkaccessprocedure balanced LAPB Physical EIA 232 V serials X 21others Flag Address Control Information Flag FCS Header Userpayload headersfromupperlayers PLPPacket 包层 1Frame 帧层 Linkcontrolfield asubsetofHDLC sequencenumbers ACKs NAKs flowcontrol linkaddress Networkinterfacecontrolfield sequencenumbers ACKs NAKs flowcontrol logicalchannelnumber LAPF Q 922 Flag Address Control Information Flag FCS 01111110 2 4bytes 2 nbytes 1 2bytes 01111110 DLCI C R EA DLCI FECN BECN DE EA 6bits 4bits 1bit 1bit 1bit 1bit 1bit 1bit LAPFControlField Flag Address Control Information Flag FCS 与HDLC相同 Flag Address Information FCS Flag DLCI C R EA DLCI FECN BECN DE EA FCS framechecksequenceDLCI datalinkconnectionidentifierC R command response unusedinFREA extendedaddressFECN forwardexplicitcongestionnotificationBECN backwardexplicitcongestionnotificationDE discardeligibility 6bit 4bit 1bit 1bit 1bit 1bit 1bit 1bit 1byte 1byte 2 4byte 2byte 8189bytesinstandards Normally 1600bytes Aethernetpacket 1500bytes NoControlField FR LAPF CORE ISDNLayers User schoice End to endusersignaling X 25andother CallcotrolQ 931 LAPBandothers LAPD Q 921 BRI I 430 PRI I 431 Physical Datalink Network Userdefined Bchannel Dchannel Protocoldiscriminator 0000 Lengthofcallreferencevalue Callreferencevalue 0 Messagetype Otherinformationelements asrequired Bits 87654321 Octets 1 2 3 etc Information ISDNlayer3 FCS Flag Control Address Flag SAPI TE1 EA CR EA Linkcontrolfieldsequenceno ACKs NAKs flowcontrol linkaddressesSAPsintheterminal Preamble SFD Destinationaddress DA Sourceaddress SA Length typeofPDU Data CRC 7bytes 1byte 6bytes 6bytes 2bytes 4bytes DSAP SSAP Control Information Cyclicredundancycheck Preamble 同步前导 1010 10SFD 帧定界符10101011 MAC PAD PDUofEthernet SDH SONET Physicallayer T3 ATM SAR AAL ATMadaptationlayerSAR segmentationandreassemblyCS convergencesublayer CS AAL1 SAR CS AAL2 SAR CS AAL3 4 SAR CS AAL5 ATMLayers PAD addedwhennecessarytofilloutthefinalcell s inasegmentpacket AAL1 AAL2 AAL3 4 AAL5 ATMLayer SegmentFromAALlayer 48bytes Header 5tyes 0GFC VCI VPI 4VPI7 VCI VCI 4PT6 CLP HEC PayloadData 48bytes UNICell VPI 4VCI7 0VPI VCI VCI 4PT6 CLP HEC PayloadData 48bytes NNICell GFC GenericflowcontrolPT PayloadtypeVPI VirtualpathidentifierCLP CelllosspriorityVCI VirtualchannelidentifierHEC Headererrorcontrol TCP 可靠的流传输端口到端口协议 传输前必须先建立虚电路 通过差错检测和重传被破坏的帧保