《第一章绪论纯中文要点》由会员分享，可在线阅读，更多相关《第一章绪论纯中文要点（76页珍藏版）》请在金锄头文库上搜索。
1、主讲人：束锋纠错编码技术主要内容绪论: 应用，基本原理，发展简史，与信息论基础编码的数学基础：代数引论线性分组码卷积码先进的编码技术简介： Turbo Code, LPDC, Polar code, Furtain code参考书差错控制编码（英文名为：Error Control Coding），第2版，Shu Linand D. J. Costello, 机械工业出版社，2007.6；第一章绪论1.1 引言1.2 码类型1.3 调制编码1.4 最大似然译码(MLD, Maximum likelihood decoding)1.5 错误类型1.6 差错控制策略1.7 性能衡量1.8 编码调制1
2、.9 熵、互信息量、信道容量与编码引言主要用于：信息传输和信息存储，过程中信息出错，检测或纠正错误。信息传输： 无线通信-移动通信，无线网络（无线局域网（WLAN）,有线网络（有线电视，.）信息存储：光盘光驱，硬盘和硬盘驱动系统典型信息传输和数据存储框图信源编码器信源编码器信道编码器信道编码器调制器调制器（写入单元）（写入单元）信道信道( (存储价质存储价质) )信源信源信源解码器信源解码器信道解码器信道解码器解调器解调器（读出单元）（读出单元）信宿信宿发射机接收机框图功能模块介绍（一）发射机：发射机：信源：是人或计算机，输出是连续的声音，或离散的信息。信源编码器：将信源输出转化为二进制01信
3、息序列，对应连续波形，就是A/D转换（模数转换），采样量化。理想信源编码两个原则：编码输出比特数最小化（Huffman编码）；可完全重构连续波形。属于信息论范畴框图功能模块介绍（二）信道编码：二进制信息序列u变换成离散的编码序列v，称之为码字。V可为二进制或非二进制，对抗信道噪声（Why？模拟信号无对抗噪声能力？数字或幅度离散信号可以？）。信道编码和信源编码区别：前者在信息中引入冗余性，纠正错误；后者压缩信源输出波形中冗余性。是否相同冗余性？调制器：将信道编码器每个输出的符号转变为适合信道传输的波形。举例：广播信道：信道：信道：波形进入信道后会收到噪声干扰，比如电话线，干扰-开关脉冲噪声，热噪
4、声和其他线串音，框图功能模块介绍（三）信道：光盘，灰尘，划痕和表面缺陷。接收机：接收机：解调器(demodulator):处理收到T秒波形，产生离散或连续的输出r；信道译码：将r转化为二进制输出序列uhat, 此为估计信息序列。寻找使译码的误码率最小的信道译码器；信源译码器：将估计的信息序列uhat变换为信源输出估计，恢复发射机信源编码输出第一章绪论1.1 引言1.2 码类型1.3 调制编码1.4 最大似然译码(MLD, Maximum likelihood decoding)1.5 错误类型1.6 差错控制策略1.7 性能衡量1.8 编码调制1.9 熵、互信息量、信道容量与编码两种不同类型信
5、道编码分组码（Block codes）：将信息流或序列分成多块或组，假定每组由k个比特（符号）组成。可用u=u_0,u_1,u_(k-1), 称为一个消息（message）,总共有2k不同信息，如果是M进制呢？编码器会将每个消息转化为n维离散符号向量，v=v_0,v_1,v_(k-1), 称之为码字(codeword), 一共多少码字？此？个码字集合称之为（n,k) 分组码，比值k/n=R为码率（code rate）000010001001001100001000100100110000000110100001110010100011信息流分组后信息编码后码字R1，kn,每个消息附加n-k比特
6、有规律的冗余信息，可对抗信道噪声(7,4)分组码例子Message CodewordMessage Codeword00000000000000110100011000110100010010111001010001101000101110010111001011100110100011010010111001000110100011101000110101011100101101101000110011100101111110010111011111111111第二种类型码卷积码：同分组码一样，同样分组，不像分组码，每个编码分组不仅取决于当前时刻对应的k比特消息，而且与前m个信息组有关。此时
7、编码器有存储级数为m。可通过时序逻辑电路实现。移位寄存器异或门uv第二种类型码：卷积码：移位寄存器异或门uv求输入比特流为：1101000时编码输出？请同学们0011001, 计算卷积码输出？什么是异或门？11,10,10,00,01,11,00,00,00，第一章绪论1.1 引言1.2 码类型1.3 调制编码1.4 最大似然译码(MLD, Maximum likelihood decoding)1.5 错误类型1.6 差错控制策略1.7 性能衡量1.8 编码调制1.9 熵、互信息量、信道容量与编码调制与编码对于二进制通信系统中信道编码器每输出一个符号，调制器必须选中一个适合信道传输,持续时间
8、为T秒的波形，比如“1”对应于s1(t),“0”对应于s0(t), Es为功率还是能量？为什么？二进制相移健控调制（BPSK，Binary phase shift keying）, 实际上存在成形滤波器？作用？系统模型各种通信系统中噪声一般近似为加性白高斯噪声(白噪声？)如果发射的信号为s(t), 则接收信号为 r(t)=a(t) s(t)+n(t)式中n(t)高斯随机过程，单边带功率谱密度为N0.a(t)是信道衰落因子，对于加性白高斯信道（AWGN：Additive white Gaussian noise），其是常数；对于市区信道，信号带宽较窄时，多条路径合成复高斯分布，其包络是瑞利分布或
9、赖斯分布（慢变化随机过程），相位是均匀分布。解调器在每T秒间隔上，解调的器产生一个相应于接收 的输出： 最优检测器，匹配滤波器，想干检测器，输出实数，需要什么是匹配滤波器？多进制调制器对于多(M)进制通信系统，先将二进制信 道编码器输出的输出序列按l比特为组进行分段，M=2l, 存在M个波形, 例如MPSK：适用于信道编码的离散信道模型给定当前T秒内检测器只与该间隔内传输的信号有关，与以前传输符号无关，称该信道为无记忆信道 (memory less). 前面AWGN信道属于此信道，将M进制调制器，信道和Q进制的解调器输出合成一个大的信道，可建模为离散的无记忆信道(DMC: Discrete m
10、emoryless channel)适用于信道编码的离散信道模型数字数字信源信源编码器编码器译码器译码器数字数字信宿信宿调制器调制器加性白色高加性白色高斯噪声信道斯噪声信道匹配滤匹配滤波检测器波检测器Q Q电平电平量化器量化器离散记忆信道解调器几种典型的离散信道模型BSPK在AWGN等价于BSC非编码的二进制的误比特率为当采用二进制编码，调制器也是二进制，如果解调器的输出是二进制量化Q=2，此时译码器只有二进制输入，解调器采用硬判决(hard-decision),译码器为硬判决译码(hard-decision decoding); 如果Q2, 软判决(soft decision), 软判决译码
11、(soft decision decoding)离散信道模型和条件概率如图1-7所示，编码器输出（调制器输入）为离散的星座图符号，解调器输出是未经量化的随机向量y属于-到+，此处调制器，信道和解调器合成了一个离散输入连续输出离散信道。如果信道噪声是AWGN，0均值和方差为No/2, 该信道可用M个调件概率密来刻画。对于M=2，符号传输速率和信息传输速率如果每T秒传输一个符号，则符号传输速率为1/T符号/秒(Symbol/s)，波特率; 对于于编码系统，如果信道编码码率为R，信息传输速率为log2MR/T, M=2, 为R/T；为了减少符号间干扰W至少为0.5/THz, 因此数据速率受带宽限制2
12、W，编码系统信道速率=2log2MRW，非编码系统为2log2MW，考虑到成形滤波器，实际的信息速率为频谱效率？Bandwidth efficiency第一章绪论1.1 引言1.2 码类型1.3 调制编码1.4 最大似然译码(MLD, Maximum likelihood decoding)1.5 错误类型1.6 差错控制策略1.7 性能衡量1.8 编码调制1.9 熵、互信息量、信道容量与编码MLD 上图在AWGN信道中采用输出有限量化的编码系统，对于分组码，u表示一个k比特消息，编码输出代表v代表n个符号码字，解调器输出r代表Q进制的n维向量，译码器的输出uhat代表k比特消息估值，u和v有
13、一一对应关系；译码器主要任务：根据接收序列r估计发射信息序列u !数字信源信道编码离散信道数字信宿信道译码uvruhatMLD假定接收为r，则译码器条件错误概率为：译码器错误概率为：P(r)为接收序列为r的条件概率，其独立于译码规则。最优的译码规则应该对于每个r使P(E/r)最小，也就是最大化P(v_hat=v/r), why?MLDP(v)=1/2k对于无记忆信道由于logx是？MLD=最小距离（BSC信道）解调器输出二进制r，由于信道噪声影响，发生的码字v可能不等于r，n位置某些位不同，两者距离，等价于码字发生错误个数，Why？码字长度为n的分组码MLD=最小距离（BSC信道）p0.5,
14、MLD等价于最小化d(r,v), Why?有噪声信道编码定理C. E. Shannon 于1948年在他的著名论文“A mathematical theory of communication”给出AWGN信道的可靠的信息传输能力，他证明：每个信道都存在一个信道容量C（最大信息速率），只要需要传输的信息速率R低于C，则存在速率为R的码，用MLD可到任意小的错误概率P(E)对于任意RC,存在分组码，存在分组长度n足够大的分组码使同时存在存储级数m足够大的卷积码(n,k保持不变)第一章绪论1.1 引言1.2 码类型1.3 调制编码1.4 最大似然译码(MLD, Maximum likelihood
15、 decoding)1.5 错误类型1.6 差错控制策略1.7 性能衡量1.8 编码调制1.9 熵、互信息量、信道容量与编码错误类型一：随机错误随机错误信道（random-error channels）: 在无记忆信道上，例如AWGN，噪声对每个传输符号影响是独立的，以图1-6a的BSC为例，每个传输比特被错误接收的概率为p，被正确接收概率？与其他比特无关。典型的随机错误信道:深空通信信道，卫星通信信道，一些视距传输信道。纠随机错误码: 为纠正随机错误的而设计的码。错误类型二：突发错误突发错误信道（random-error channels）: 在有记忆信道，各次传输信道噪声不是独立，或信道增
16、益a(t)是慢变化的（比如步行到高大建筑物后面，信道处于深度衰落）Rayleigh Fading (瑞利衰落)Deep fading有记忆信道简化模型：两个状态：好状态（传输错误概率大）和坏状态（传输错误概率大）。第一章绪论1.1 引言1.2 码类型1.3 调制编码1.4 最大似然译码(MLD, Maximum likelihood decoding)1.5 错误类型1.6 差错控制策略1.7 性能衡量1.8 编码调制1.9 熵、互信息量、信道容量与编码单向传输系统：前向纠错(FEC)如第6页的通信系统框图是单向系统，信息传输方向严格按照从发射机向接收机。该系统差错控制策略必须采用前向纠错(F
17、orward error correction, FEC), 接收机利用纠错码纠错码自动纠正和检测错误。典型例子如下：深空通信，数字存储系统，数字调幅广播（DRM），数字陆地电视(DVB-T), 数字有线电视(DVB-C), 2G,3G.双向传输系统：自动请求重传(ARQ)有些情况下，系统是双向，信息沿两个方向传输，发射机可作为接收机。发送机接收机信道反馈双向系统的差错控制策略同时采用检测错误和重传，称为自动请求重传(ARQ:Automatic repeat request)，ARQ系统中接收机检测出错误，就向发送端发出要求重传该消息的要求，直到消息被正确接收。ARQ有两种：等待式和连续ARQ
18、s。传送等待ARQ（Stop-and-wait）码字1码字2码字1码字1译码失败NACK码字1码字1译码成功ACK码字2码字2译码失败NACK发送机接收机发送端发射一个码字到接收端，同时等待接收接收端返回一个确认信号(ACK)或否定应答(NACK, NAK),如果是ACK，表示成功，传送下个码字；如果Fail，重传前码字。连续ARQ两种类型：退N步ARQ、选择重传ARQ发生端连续将码字发生到接收端，同时通过Feedback信道接收应答信号，当接收到NAK时，发送端重传。有两种选择，第一，发送端回退到发生错误码字，并重传该码字和其后的N-1个码字，称为退N步ARQ(Go-back-N); 另外一
19、种可选方案，发送端仅传输那些有否定应答的码字，称为选择重传ARQ(Selective repeat ARQ).ARQ, FEC连续ARQ比等待式效率高，比如卫星通信，速率高延时大，一般采用连续ARQ；无线通信网络Layers应用层压缩和错误隐藏技术传输层端到端差错恢复,，重传， 流量控制网络层邻居发现，路由， 资源配置接入层信道接入, 功率控制, 纠错, 重传物理层调制， 编码， MIMO功率控制，抗衰落, MIMO第一章绪论1.1 引言1.2 码类型1.3 调制编码1.4 最大似然译码(MLD, Maximum likelihood decoding)1.5 错误类型1.6 差错控制策略1.
20、7 性能衡量1.8 编码调制1.9 熵、互信息量、信道容量与编码译码错误概率和编码增益(coding gain)码字错误概率(word erro rate, WER)或分组错误概率（Block error rate, BLER）和比特错误概率(bit error rate,BER);比特信噪比=Eb/No=Es/RNo=PsTs/RNo=Ps/Pn/R =SNR/R 其中SNR=Ps/Pn编码阈值：Eb/No低于此值，编码将毫无效果，译码后效果更糟糕！左图给出Golay码(23,12)最大似然硬判决译码和软判决译码的误码率曲线，图中包括未编码系统BER作为参考。由图可知，当Eb/No大于某个阈
21、值时，无论采用硬判决还是软判决，在相同Eb/No, 编码比不编码要好。差错控制码设计目标信道编码和译码的最终目标是总是希望获得特定BER，所需Eb/No最小化；根据香农有噪声编码定理可推导出一个码率为R的编码通信系统达到无误码传输时所需最小Eb/No的理论极限，下界，这个理论极限为香农限(Shannon limit).上图绘出码率R=0.5,存储级数为m=6的卷积码在采用软判决MLD时BER曲线，当BER=10-5, 该码EbNo=4.15dB, 同未编码的BER相比有5.35dB编码增益，同香农限比还差3.962dB上图绘出LDPC（65520,61425）逼近MLD的译码算法BER性能，该
22、码码率为R=15/16=0.9375, 这个码率下的香农限为3.91dB，从上图我们发现，BER为10-5,我们发现该码所需SNR与比香农限高0.5dB第一章绪论1.1 引言1.2 码类型1.3 调制编码1.4 最大似然译码(MLD, Maximum likelihood decoding)1.5 错误类型1.6 差错控制策略1.7 性能衡量1.8 编码调制1.9 熵、互信息量、信道容量与编码参考书T. M. Cover and J. A . Thomas. 信息论基础（Elements of Information Theory），清华大学出版社第一作者：Stanford Universit
23、y52 熵(Entropy)式中 h(X) 成为微分熵. 熵与微分熵之间区别：对应离散的随机变量X对于连续的随机变量53熵计算的例子对于离散的随机变量, P(X=0)=a,P(X=1)=1-a 对于连续的随机变量，N(m,2) 54 相对熵和Jensen不等式请证明。现在我们用它来推导相对熵的性质：相对熵, Jensen不等式, f(x) 是一个凸函数， X 是一个随机变量55Jensen不等式的证明证明: 函数f(x)在区间（a，b）上是一个凸函数Jensens 不等式: f(x)是一个凸函数，X是一个随机变量X1 x x256 高斯分布熵最大定理 g(x), f(x)有相同的协方差定理的证
24、明57 互信息量与维恩图I(X,Y)H(X)H(Y)维恩图58互信息量（Mutal Information）信道容量=一个通信信道中能够以任意小的错误率传递信息时可达的速率上限(数据压缩与传输：冗余)59信道容量（Channel Capacity）信道容量=一个通信信道中能够以任意小的错误率传递信息时可达的速率上限(数据压缩与传输：冗余)60白高斯噪声信道容量XAWGNY Y=h*X+NN是加性高斯白噪声， h是恒定的通道增益 SNR=h2E(X2)/E(N2)克劳德香农(Claude Elwood Shannon，1916-2001)1916年4月30日诞生于美国密西根州的Petoskey。
25、在Gaylord小镇长大，当时镇里只有三千居民。父亲是该镇的法官，他们父子的姓名完全相同，都是Claude Elwood Shannon。母亲是镇里的中学校长，姓名是Mabel Wolf Shannon。他生长在一个有良好教育的环境，不过父母给他的科学影响好像还不如祖父的影响大。香农的祖父是一位农场主兼发明家，发明过洗衣机和许多农业机械，这对香农的影响比较直接。此外，香农的家庭与大发明家爱迪生(Thomas Alva Edison，1847-1931)还有远亲关系。2001年2月24日，香农在马萨诸塞州Medfod辞世，享年85岁。贝尔实验室和MIT发表的讣告都尊崇香农为信息论及数字通信时代的
26、奠基人1948年香农在Bell System Technical Journal（贝尔系统技术杂志）上发表了A Mathematical Theory of Communication 。克劳德香农在公众中并不特别知名，但他是使我们的世界能进行即时通信的少数科学家和思想家之一。他是美国科学院院士、美国工程院院士、英国皇家学会会员、美国哲学学会会员。他获得过许多荣誉和奖励。例如1949年Morris奖、1955年Ballantine奖、1962年Kelly奖、1966年的国家科学奖章、IEEE的荣誉奖章、1978年Jaquard奖、1983年Fritz奖、1985年基础科学京都奖。他接受的荣誉学
27、位不胜枚举，不再赘述。今天，我们怀念香农，要熟悉他的两大贡献：一是信息理论、信息熵的概念；另一是符号逻辑和开关理论。63香农信道容量公式香农信道容量公式（1948）两部分:当传输速率RC, 任何方式的编码都无法实现可靠的信息传输64频谱效率频谱效率65最大频谱效率最大频谱效率 最大频谱效率:66香农限香农限 香农界(为可靠的传输需要的最小能量):香农极限(带宽无限的情况下)67香农界与香农限图解Further insightTwo basic resources of the AWGN channel are the received powerP and the band-width W.
28、To this end, a key observation is that the functionis concave.High and Low SNR regionsIncreasing the power suffers from a law of diminishing marginal returns: when the SNR is low, the capacity increases linearly with the received power P: every 3 dB increase in (or, doubling) the power doubles the c
29、apacityWhen the SNR is high, the capacity increases logarithmically with P: every 3 dB increase in the power only yields only one additional bit per dimensionBandwidth Limited & Power LimitedWhen the bandwidth is small, the SNR per degree of freedom is high, and then the capacity is insensitive to s
30、mall changes in SNR. Increasing W yields a rapid increase in capacity because the increase in degrees of freedom more than compensates for the decrease in SNR. The system is in the bandwidth-limited regime.When the bandwidth is large such that the SNR per DoF is small. the capacity is proportional t
31、o the total received power across the entire band. It is insensitive to the bandwidth, and increasing the bandwidth has a small impact on capacity. On the other hand, the capacity is now linear in the received power and increasing power has a significant effect. This is the power-limited regime.Fix
32、P and Increasing WW=infinite given P is constraint.Minimum energy per bitThe minimum required energy per bit is defined asTo minimize the above, we should operate in most power-efficient regime, P-0, thus the minimum required energy per bit is To achieve this, the SNR per DoF goes to zero. The price
33、 to pay for the energy efficiency is delay: if the bandwidth W is fixed, the communication rate (in bits/s) goes to zero. This is essentially mimics the infinite bandwidth regime by spreading the total energy over a long time interval, instead of spreading the total power over a large bandwidth. In
34、the infinite bandwidth regime, however, it has long been known that orthogonal codes 3 achieve the capacity (or, equivalently, achieve the minimum Eb/N0 of 1.59 dB): Hadamard sequences used in IS-95 system. 73应用YearRate CodeSNR Required for BER 10-51948SHANNON0dB1967(255,123) BCH 5.4dB1977Convolutio
35、nal Code4.5dB1993Iterative Turbo Code0.7dB2001Iterative LDPC Code0.0245dB74逼近香农限逼近香农限75信道编码发展简史Convolutional CodesBlock CodesPolar codeFountain code1, 什么是ARQ？其中英文全称，其同前向纠错区别在哪里？ARQ分为几类？请绘出ARQ传输系统简单框图和等待ARQ工作流程图。2, 什么是信道容量？请写出香农信道容量公式，并解释公式中每个参数，请从物理意义角度解释香农容量公式, 请写出香农两大贡献。3, 纠错码主要性能衡量指标有哪些？香农限如何定义？请阐述香农有噪声信道编码定理。第一章第一章 作业作业
