《信道编码-纠错码概述概要》由会员分享，可在线阅读，更多相关《信道编码-纠错码概述概要（54页珍藏版）》请在金锄头文库上搜索。
1、第一章 纠错码概述 陆以勤 在一切哲学那里，体系都是暂时的东西，但包含在体系 中的真正有价值的方法却可以长久地启发人心智、发人 深思。 我们所能有的最美好的经验是奥秘的经验，谁要是体验 不到它，谁要是不再有好奇心，也不再有惊讶的感觉， 他就无异于行尸走肉。 一、什么叫纠错码 通信系统模型 信 源 信源 编码 信道 编码 + 信道 译码 信源 译码 信 宿 umc 噪声 e(t) r(t)= s(t)+e(t) m u 压缩编码 检纠错 编码 信道：消息的传递途径，可以物 理信道，也可以是一些处理过程 ，如CD复制，硬盘，物流等 调 制 s(t) 解 调 r=c+e AWGN (additive
2、 white 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 D
3、ata Frame n Ack n Data Frame n+1 Ack n+1 Waiting time Waiting time Error Control Stop and Wait ARQSlide Windows ARQ Send one frame at a time Send several frames at a time Go-back nSelective-reject Stop-and-Wait ARQ: Damaged Frame Flash Stop-and-Wait ARQ: Lost Frame Stop-and-Wait ARQ: Lost ACK Slide
4、Windows 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 FlagAddressControlInformationFlagFCS 1 8 011111102/4 bytes1-n bytes1/2 bytes 0 最后1byte 的第8位 为1表示地址结束 0N(S)P/F 01111110 01 N(R
5、) 15234678 I: Information frame 信息帧 1SP/FN(R)0 1MP/FM1 S: Supervisory frame 监督帧 U: Unnumbered frame 无编号帧 8 bits Control 字段 0N(S)P/FN(R) 152346789131011 121415 16 10 0 0 0 P/FN(R)0 I:信息帧 S:监督帧S 16 bits Control 字段 N(S) :发送顺序号 N(R) ：接收顺序号 S: 监督功能位 M: 无编号功能位 P/F: 轮询/终止位 S: 00: 接收就绪RR 10：接收未就绪RNR 01：拒绝,
6、从顺序号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字节） Flash Piggyback：捎带确认(法) A technique
7、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 normal data-carrying message flowing
8、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) (1,0,0) (1,1) (1,1,1) （0,1,1) （0,0,1
9、) （1,0,1) （1,1,1) 4.纠错码的三个例子 1.奇偶校验码 问题：1. 奇偶校验码能否纠错？(答案） 2. 提高方式： s CRC(Cyclic Redundancy Check)循环冗余校验码，是一种缩 短循环码，广泛用于帧校验，习惯上把校验位称作CRC校验码 s 条形码的检错 2.重复码（见p10,例1.1) 00100 000 000 111 000 000 3.线性分组码 线性分组码（1） c = (m1m2mkp1p2pr) 二进制 m1m2mk：信息位，p1p2pr：校验位，n=k+r: 码长，记为（n,k) 假设检验位与信息位是线性关系，即： p1= h11m1+h
10、12m2+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=0 r HT=(c+e) HT= c HT+e HT
11、=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 0 1 0 1 0 1 0 1 汉明码的编
12、码 例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.按错误类型：纠突发错误码，纠随机错误码 可利用交织技术把突发错误转化为随机错 4.按码字之
13、间的关系： 循环码：全部码字可用循环移位获得 非循环码：不能通过循环移位获得全部码字 5.按码元取值：二进制码（缺省）,q进制码（q=pm,p为素数,m为正整数 ） 6.按码元的纠错能力：等保护码，不等保护码 交叉分类见图1-11 a11a12 a1k a21a22 a2k ar1ar2 ark 存入 顺序 发送 顺序 Turbo码：卷积码交织码 LDPC：线性分组码 循环码的数学概念 0100011 1000110 0001101 g(x) 1101000 0011010 0110100 1010001 0010111 (x+1)g(x) 0111001 0101110 1011100 11
14、10010 1100101 1001011 0000000 0 g(x) 1111111 (x3+x+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
15、 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 0 0 0 0) 二、纠错码的背景知识 1.判决 x=1:硬判决 x=?:不判决 x=p(1),p(0):软判决 所以，信道的输入是二进制，但输出不一定是二进制, 如果 输出是二进制,则叫二进制信道,如果输出是q进制,则为q进 制信道 2.信道模型(1) (1)二进制信道 0 1 0 1 p00 p11 p10 p01 P= p00 p01 p10 p11 转移矩阵 0 1 0 1 1- pe 1- pe pe pe 2.信道模型(2) (a) 2进制对称信道(BSC, binary symmetric channel) (b) 2进制非对称信道(BAC , binary asymmetric channel) 0 1 0 1 1 1- p1 p1 0 1 0 1 1 1- p0 p0 Z信道 2.信道模型(3) (c) 2进制删除信道(BEC, binary erasure channel) 0 1 0 x
