第一章-绪论-纯中文)-2013-2014-10要点.ppt

主讲人 束锋 纠错编码技术 主要内容 绪论 应用 基本原理 发展简史 与信息论基础编码的数学基础 代数引论线性分组码卷积码先进的编码技术简介 TurboCode LPDC Polarcode Furtaincode 参考书 差错控制编码 英文名为 ErrorControlCoding 第2版 ShuLinandD J Costello 机械工业出版社 2007 6 第一章绪论 1 1引言1 2码类型1 3调制编码1 4最大似然译码 MLD Maximumlikelihooddecoding 1 5错误类型1 6差错控制策略1 7性能衡量1 8编码调制1 9熵 互信息量 信道容量与编码 引言 主要用于 信息传输和信息存储 过程中信息出错 检测或纠正错误 信息传输 无线通信 移动通信 无线网络 无线局域网 WLAN 有线网络 有线电视 信息存储 光盘光驱 硬盘和硬盘驱动系统 典型信息传输和数据存储框图 信源编码器 信道编码器 调制器 写入单元 信道 存储价质 信源 信源解码器 信道解码器 解调器 读出单元 信宿 发射机 接收机 框图功能模块介绍 一 发射机 信源 是人或计算机 输出是连续的声音 或离散的信息 信源编码器 将信源输出转化为二进制01信息序列 对应连续波形 就是A D转换 模数转换 采样量化 理想信源编码两个原则 编码输出比特数最小化 Huffman编码 可完全重构连续波形 属于信息论范畴 框图功能模块介绍 二 信道编码 二进制信息序列u变换成离散的编码序列v 称之为码字 V可为二进制或非二进制 对抗信道噪声 Why 模拟信号无对抗噪声能力 数字或幅度离散信号可以 信道编码和信源编码区别 前者在信息中引入冗余性 纠正错误 后者压缩信源输出波形中冗余性 是否相同冗余性 调制器 将信道编码器每个输出的符号转变为适合信道传输的波形 举例 广播信道 信道 波形进入信道后会收到噪声干扰 比如电话线 干扰 开关脉冲噪声 热噪声和其他线串音 框图功能模块介绍 三 信道 光盘 灰尘 划痕和表面缺陷 接收机 解调器 demodulator 处理收到T秒波形 产生离散或连续的输出r 信道译码 将r转化为二进制输出序列u hat 此为估计信息序列 寻找使译码的误码率最小的信道译码器 信源译码器 将估计的信息序列u hat变换为信源输出估计 恢复发射机信源编码输出 第一章绪论 1 1引言1 2码类型1 3调制编码1 4最大似然译码 MLD Maximumlikelihooddecoding 1 5错误类型1 6差错控制策略1 7性能衡量1 8编码调制1 9熵 互信息量 信道容量与编码 两种不同类型信道编码 分组码 Blockcodes 将信息流或序列分成多块或组 假定每组由k个比特 符号 组成 可用u u 0 u 1 u k 1 称为一个消息 message 总共有2 k不同信息 如果是M进制呢 编码器会将每个消息转化为n维离散符号向量 v v 0 v 1 v k 1 称之为码字 codeword 一共多少码字 此 个码字集合称之为 n k 分组码 比值k n R为码率 coderate 0000100010010011 0000 1000 1001 0011 0000000 1101000 0111001 0100011 信息流 分组后信息 编码后码字 R 1 k n 每个消息附加n k比特有规律的冗余信息 可对抗信道噪声 7 4 分组码例子 第二种类型码 卷积码 同分组码一样 同样分组 不像分组码 每个编码分组不仅取决于当前时刻对应的k比特消息 而且与前m个信息组有关 此时编码器有存储级数为m 可通过时序逻辑电路实现 移位寄存器 异或门 u v 第二种类型码 卷积码 移位寄存器 异或门 u v 求输入比特流为 1101000 时编码输出 请同学们0011001 计算卷积码输出 什么是异或门 11 10 10 00 01 11 00 00 00 第一章绪论 1 1引言1 2码类型1 3调制编码1 4最大似然译码 MLD Maximumlikelihooddecoding 1 5错误类型1 6差错控制策略1 7性能衡量1 8编码调制1 9熵 互信息量 信道容量与编码 调制与编码 对于二进制通信系统中信道编码器每输出一个符号 调制器必须选中一个适合信道传输 持续时间为T秒的波形 比如 1 对应于s1 t 0 对应于s0 t Es为功率还是能量 为什么 二进制相移健控调制 BPSK Binaryphaseshiftkeying 实际上存在成形滤波器 作用 系统模型 各种通信系统中噪声一般近似为加性白高斯噪声 白噪声 如果发射的信号为s t 则接收信号为 r t a t s t n t 式中n t 高斯随机过程 单边带功率谱密度为N0 a t 是信道衰落因子 对于加性白高斯信道 AWGN AdditivewhiteGaussiannoise 其是常数 对于市区信道 信号带宽较窄时 多条路径合成复高斯分布 其包络是瑞利分布或赖斯分布 慢变化随机过程 相位是均匀分布 解调器 在每T秒间隔上 解调的器产生一个相应于接收的输出 最优检测器 匹配滤波器 想干检测器 输出实数 需要 什么是匹配滤波器 多进制调制器 对于多 M 进制通信系统 先将二进制信道编码器输出的输出序列按l比特为组进行分段 M 2 l 存在M个波形 例如MPSK 适用于信道编码的离散信道模型 给定当前T秒内检测器只与该间隔内传输的信号有关 与以前传输符号无关 称该信道为无记忆信道 memoryless 前面AWGN信道属于此信道 将M进制调制器 信道和Q进制的解调器输出合成一个大的信道 可建模为离散的无记忆信道 DMC Discretememorylesschannel 适用于信道编码的离散信道模型 数字信源 编码器 译码器 数字信宿 调制器 加性白色高斯噪声信道 匹配滤波检测器 Q电平量化器 离散记忆信道 解调器 几种典型的离散信道模型 BSPK在AWGN等价于BSC 非编码的二进制的误比特率为 当采用二进制编码 调制器也是二进制 如果解调器的输出是二进制量化Q 2 此时译码器只有二进制输入 解调器采用硬判决 hard decision 译码器为硬判决译码 hard decisiondecoding 如果Q 2 软判决 softdecision 软判决译码 softdecisiondecoding 离散信道模型和条件概率 如图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 因此数据速率受带宽限制2W 编码系统信道速率 2log2MRW 非编码系统为2log2MW 考虑到成形滤波器 实际的信息速率为 频谱效率 Bandwidthefficiency 第一章绪论 1 1引言1 2码类型1 3调制编码1 4最大似然译码 MLD Maximumlikelihooddecoding 1 5错误类型1 6差错控制策略1 7性能衡量1 8编码调制1 9熵 互信息量 信道容量与编码 MLD 上图在AWGN信道中采用输出有限量化的编码系统 对于分组码 u表示一个k比特消息 编码输出代表v代表n个符号码字 解调器输出r代表Q进制的n维向量 译码器的输出u hat代表k比特消息估值 u和v有一一对应关系 译码器主要任务 根据接收序列r估计发射信息序列u 数字信源 信道编码 离散信道 数字信宿 信道译码 u v r u hat MLD 假定接收为r 则译码器条件错误概率为 译码器错误概率为 P r 为接收序列为r的条件概率 其独立于译码规则 最优的译码规则应该对于每个r使P E r 最小 也就是最大化P v hat v r why MLD P v 1 2 k 对于无记忆信道 由于logx是 MLD 最小距离 BSC信道 解调器输出二进制r 由于信道噪声影响 发生的码字v可能不等于r n位置某些位不同 两者距离 等价于码字发生错误个数 Why 码字长度为n的分组码 MLD 最小距离 BSC信道 p 0 5 MLD等价于最小化d r v Why 有噪声信道编码定理 C E Shannon于1948年在他的著名论文 Amathematicaltheoryofcommunication 给出AWGN信道的可靠的信息传输能力 他证明 每个信道都存在一个信道容量C 最大信息速率 只要需要传输的信息速率R低于C 则存在速率为R的码 用MLD可到任意小的错误概率P E 对于任意R C 存在分组码 存在分组长度n足够大的分组码使 同时存在存储级数m足够大的卷积码 n k保持不变 第一章绪论 1 1引言1 2码类型1 3调制编码1 4最大似然译码 MLD Maximumlikelihooddecoding 1 5错误类型1 6差错控制策略1 7性能衡量1 8编码调制1 9熵 互信息量 信道容量与编码 错误类型一 随机错误 随机错误信道 random errorchannels 在无记忆信道上 例如AWGN 噪声对每个传输符号影响是独立的 以图1 6a的BSC为例 每个传输比特被错误接收的概率为p 被正确接收概率 与其他比特无关 典型的随机错误信道 深空通信信道 卫星通信信道 一些视距传输信道 纠随机错误码 为纠正随机错误的而设计的码 错误类型二 突发错误 突发错误信道 random errorchannels 在有记忆信道 各次传输信道噪声不是独立 或信道增益a t 是慢变化的 比如步行到高大建筑物后面 信道处于深度衰落 RayleighFading 瑞利衰落 Deepfading 有记忆信道简化模型 两个状态 好状态 传输错误概率大 和坏状态 传输错误概率大 第一章绪论 1 1引言1 2码类型1 3调制编码1 4最大似然译码 MLD Maximumlikelihooddecoding 1 5错误类型1 6差错控制策略1 7性能衡量1 8编码调制1 9熵 互信息量 信道容量与编码 单向传输系统 前向纠错 FEC 如第6页的通信系统框图是单向系统 信息传输方向严格按照从发射机向接收机 该系统差错控制策略必须采用前向纠错 Forwarderrorcorrection FEC 接收机利用纠错码纠错码自动纠正和检测错误 典型例子如下 深空通信 数字存储系统 数字调幅广播 DRM 数字陆地电视 DVB T 数字有线电视 DVB C 2G 3G 双向传输系统 自动请求重传 ARQ 有些情况下 系统是双向 信息沿两个方向传输 发射机可作为接收机 发送机 接收机 信道 反馈 双向系统的差错控制策略同时采用检测错误和重传 称为自动请求重传 ARQ Automaticrepeatrequest ARQ系统中接收机检测出错误 就向发送端发出要求重传该消息的要求 直到消息被正确接收 ARQ有两种 等待式和连续ARQs 传送 等待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 另外一种可选方案 发送端仅传输那些有否定应答的码字 称为选择重传ARQ SelectiverepeatARQ ARQ FEC 连续ARQ比等待式效率高 比如卫星通信 速率高延时大 一般采用连续ARQ 无线通信网络Layers 应用层压缩和错误隐藏技术 传输层端到端差错恢复 重传 流量控制 网络层邻居发现 路由 资源配置 接入层信道接入 功率控制 纠错 重传 物理层调制 编码 MIMO功率控制 抗衰落 MIMO 第一章绪论 1 1引言1 2码类型1 3调制编码1 4最大似然译码 MLD Maximumlikelihooddecoding 1 5错误类型1 6差错控制策略1 7性能衡量1 8编码调制1 9熵 互信息量 信道容量与编码 译码错误概率和编码增益 codinggain 码字错误概率 worderrorate WER 或分组错误概率 Blockerrorrate BLER 和比特错误概率 biterrorrate BER 比特信噪比 Eb No Es RNo PsTs RNo Ps Pn R SNR R其中SNR Ps Pn 编码阈值 Eb No低于此值 编码将毫无效果 译码后效果更糟糕 左图给出Golay码 23 12 最大似然硬判决译码和软判决译码的误码率曲线 图中包括未编码系统BER作为参考 由图可知 当Eb No大于某个阈值时 无论采用硬判决还是软判决 在相同Eb No 编码比不编码要好 差错控制码设计目标 信道编码和译码的最终目标是总是希望获得特定BER 所需Eb No最小化 根据香农有噪声编码定理可推导出一个码率为R的编码通信系统达到无误码传输时所需最小Eb No的理论极限 下界 这个理论极限为香农限 Shannonlimit 上图绘出码率R 0 5 存储级数为m 6的卷积码在采用软判决MLD时BER曲线 当BER 10 5 该码EbNo 4 15dB 同未编码的BER相比有5 35dB编码增益 同香农限比还差3 962dB 上图绘出LDPC 65520 61425 逼近MLD的译码算法BER性能 该码码率为R 15 16 0 9375 这个码率下的香农限为3 91dB 从上图我们发现 BER为10 5 我们发现该码所需SNR与比香农限高0 5dB 第一章绪论 1 1引言1 2码类型1 3调制编码1 4最大似然译码 MLD Maximumlikelihooddecoding 1 5错误类型1 6差错控制策略1 7性能衡量1 8编码调制1 9熵 互信息量 信道容量与编码 参考书 T M CoverandJ A Thomas 信息论基础 ElementsofInformationTheory 清华大学出版社第一作者 StanfordUniversity 52 熵 Entropy 式中h X 成为微分熵 熵与微分熵之间区别 对应离散的随机变量X 对于连续的随机变量 53 熵计算的例子 对于离散的随机变量 P X 0 a P X 1 1 a 对于连续的随机变量 N m 2 54 相对熵和Jensen不等式 请证明 现在我们用它来推导相对熵的性质 相对熵 Jensen不等式 f x 是一个凸函数 X是一个随机变量 55 Jensen不等式的证明 证明 函数f x 在区间 a b 上是一个凸函数 Jensen s不等式 f x 是一个凸函数 X是一个随机变量 56 高斯分布熵最大定理 g x f x 有相同的协方差 定理的证明 57 互信息量与维恩图 I X Y H X H Y 维恩图 58 互信息量 MutalInformation 信道容量 一个通信信道中能够以任意小的错误率传递信息时可达的速率上限 数据压缩与传输 冗余 59 信道容量 ChannelCapacity 信道容量 一个通信信道中能够以任意小的错误率传递信息时可达的速率上限 数据压缩与传输 冗余 60 白高斯噪声信道容量 X AWGN Y Y h X NN是加性高斯白噪声 h是恒定的通道增益 SNR h2E X2 E N2 克劳德 香农 ClaudeElwoodShannon 1916 2001 1916年4月30日诞生于美国密西根州的Petoskey 在Gaylord小镇长大 当时镇里只有三千居民 父亲是该镇的法官 他们父子的姓名完全相同 都是ClaudeElwoodShannon 母亲是镇里的中学校长 姓名是MabelWolfShannon 他生长在一个有良好教育的环境 不过父母给他的科学影响好像还不如祖父的影响大 香农的祖父是一位农场主兼发明家 发明过洗衣机和许多农业机械 这对香农的影响比较直接 此外 香农的家庭与大发明家爱迪生 ThomasAlvaEdison 1847 1931 还有远亲关系 2001年2月24日 香农在马萨诸塞州Medfod辞世 享年85岁 贝尔实验室和MIT发表的讣告都尊崇香农为信息论及数字通信时代的奠基人 1948年香农在BellSystemTechnicalJournal 贝尔系统技术杂志 上发表了 AMathematicalTheoryofCommunication 克劳德 香农在公众中并不特别知名 但他是使我们的世界能进行即时通信的少数科学家和思想家之一 他是美国科学院院士 美国工程院院士 英国皇家学会会员 美国哲学学会会员 他获得过许多荣誉和奖励 例如1949年Morris奖 1955年Ballantine奖 1962年Kelly奖 1966年的国家科学奖章 IEEE的荣誉奖章 1978年Jaquard奖 1983年Fritz奖 1985年基础科学京都奖 他接受的荣誉学位不胜枚举 不再赘述 今天 我们怀念香农 要熟悉他的两大贡献 一是信息理论 信息熵的概念 另一是符号逻辑和开关理论 63 香农信道容量公式 1948 两部分 当传输速率RC 任何方式的编码都无法实现可靠的信息传输 64 频谱效率 65 最大频谱效率 最大频谱效率 66 香农限 香农界 为可靠的传输需要的最小能量 香农极限 带宽无限的情况下 67 香农界与香农限图解 Furtherinsight TwobasicresourcesoftheAWGNchannelarethereceivedpowerPandtheband widthW Tothisend akeyobservationisthatthefunction isconcave HighandLowSNRregions Increasingthepowersuffersfromalawofdiminishingmarginalreturns whentheSNRislow thecapacityincreaseslinearlywiththereceivedpowerP every3dBincreasein or doubling thepowerdoublesthecapacity WhentheSNRishigh thecapacityincreaseslogarithmicallywithP every3dBincreaseinthepoweronlyyieldsonlyoneadditionalbitperdimension BandwidthLimited PowerLimited Whenthebandwidthissmall theSNRperdegreeoffreedomishigh andthenthecapacityisinsensitivetosmallchangesinSNR IncreasingWyieldsarapidincreaseincapacitybecausetheincreaseindegreesoffreedommorethancompensatesforthedecreaseinSNR Thesystemisinthebandwidth limitedregime WhenthebandwidthislargesuchthattheSNRperDoFissmall thecapacityisproportionaltothetotalreceivedpoweracrosstheentireband Itisinsensitivetothebandwidth andincreasingthebandwidthhasasmallimpactoncapacity Ontheotherhand thecapacityisnowlinearinthereceivedpowerandincreasingpowerhasasignificanteffect Thisisthepower limitedregime FixPandIncreasingW W infinitegivenPisconstraint Minimumenergyperbit Theminimumrequiredenergyperbitisdefinedas Tominimizetheabove weshouldoperateinmostpower efficientregime P 0 thustheminimumrequiredenergyperbitis Toachievethis theSNRperDoFgoestozero Thepricetopayfortheenergyefficiencyisdelay ifthebandwidthWisfixed thecommunicationrate inbits s goestozero Thisisessentiallymimicstheinfinitebandwidthregimebyspreadingthetotalenergyoveralongtimeinterval insteadofspreadingthetotalpoweroveralargebandwidth Intheinfinitebandwidthregime however ithaslongbeenknownthatorthogonalcodes3achievethecapacity or equivalently achievetheminimumEb N0of 1 59dB HadamardsequencesusedinIS 95system Alternativeproof Geometrically repetitioncodesputsallthecodewordsinjustonedimension Figureprovidesanillustration here allthecodewordsareonthesameline andrepetitioncodingpackspointsinefficientlyinthehighdimensionalsignalspace Alternativeproof Spherepacking N dimensionalreceivedvectory x w withhighprob liewithinay sphereofradiussqrt N P Sigma 2 P y N P sigma 2 P x NP P n N simga 2 intermsofthelawoflargenumbers Figureprovidesanillustration here allthecodewordsareonthesameline andrepetitioncodingpackspointsinefficientlyinthehighdimensionalsignalspace Alternativeproof Spherepacking Reliablecommunicationoccursaslongasthenoisespheresaroundthecodewordsdonotoverlap Themaximumnumberofcodewordsthatcanbepackedwithnon overlapping noisespheresistheratioofthevolumeofthey spheretothevolumeofanoisesphere Thisimpliesthatthemaximumnumberofbitspersymbolthatcanbereliablycommunicatedis Summary ReliableRateofCommunicationandCapacity ReliablecommunicationatrateRbits symbolmeansthatonecandesigncodesatthatratewitharbitrarilysmallerrorprobability