编码技术引言 2009年秋.

Slides:



Advertisements
Similar presentations
2.5 函数的微分 一、问题的提出 二、微分的定义 三、可微的条件 四、微分的几何意义 五、微分的求法 六、小结.
Advertisements

第二章 导数与微分. 二、 微分的几何意义 三、微分在近似计算中的应用 一、 微分的定义 2.3 微 分.
阻塞操作. 在 linux 里,一个等待队列由一个 wait_queue_head_t 类型的结构来描述 等待队列的初始化: static wait_queue_head_t testqueue; init_waitqueue_head(&testqueue);
信号与系统 第三章 傅里叶变换 东北大学 2017/2/27.
通信原理 第7章数字带通传输系统.
REED-SOLOMON CODES.
计算机网络课程总结 一、计算机网络基础 计算机网络定义和功能、基本组成 OSI/RM参考模型(各层的功能,相关概念, 模型中数据传输 等)
通信原理.
1.2 信号的描述和分类.
信息论 复习.
第 9 章 差错控制编码 9.1 概述 9.2 常用的几种简单分组码 9.3 线性分组码 9.4 循环码 9.5 卷积码
第九章 信道编码 9.1 引言 9.2 信道编码的基本原理 9.3 线性分组码 9.4 循环码 9. 5 卷积码.
第三章 函数逼近 — 最佳平方逼近.
§5.1 幅度调制(线性调制)的原理 一般模型 边带滤波器.
常用逻辑用语复习课 李娟.
本节内容简介: 音频信号压缩编码 信道编码的必要性、目的及编码框图 纠错原理 数字信号的调制与解调.
Class Profile 36 credit hours.
2-7、函数的微分 教学要求 教学要点.
C++中的声音处理 在传统Turbo C环境中,如果想用C语言控制电脑发声,可以用Sound函数。在VC6.6环境中如果想控制电脑发声则采用Beep函数。原型为: Beep(频率,持续时间) , 单位毫秒 暂停程序执行使用Sleep函数 Sleep(持续时间), 单位毫秒 引用这两个函数时,必须包含头文件
第5章 §5.3 定积分的积分法 换元积分法 不定积分 分部积分法 换元积分法 定积分 分部积分法.
第三章 信源编码(一)离散信源无失真编码.
第一章:高斯信道的信号检测 1.1 问题描述 1.2 Bayes检测 1.3 二元实高斯信号检测
现代通信原理 吉林大学远程教育学院.
计算机数学基础 主讲老师: 邓辉文.
§2 求导法则 2.1 求导数的四则运算法则 下面分三部分加以证明, 并同时给出相应的推论和例题 .
第一章 函数 函数 — 研究对象—第一章 分析基础 极限 — 研究方法—第二章 连续 — 研究桥梁—第二章.
时序逻辑电路实验 一、 实验目的 1.熟悉集成计数器的功能和使用方法; 2.利用集成计数器设计任意进制计数器。 二、实验原理
实验六 积分器、微分器.
多媒体技术 中南大学信息科学与工程学院 黄东军.
第3章 信息与信息系统 陈恭和.
第一章 函数与极限.
本节内容 字符编码 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
C语言程序设计 主讲教师:陆幼利.
简单介绍 用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)
学习目标 1、什么是字符集 2、字符集四个级别 3、如何选择字符集.
晶体管及其小信号放大 -单管共射电路的频率特性.
概 率 统 计 主讲教师 叶宏 山东大学数学院.
5.2 常用统计分布 一、常见分布 二、概率分布的分位数 三、小结.
晶体管及其小信号放大 -单管共射电路的频率特性.
WPT MRC. WPT MRC 由题目引出的几个问题 1.做MRC-WPT的多了,与其他文章的区别是什么? 2.Charging Control的手段是什么? 3.Power Reigon是什么东西?
卷积码.
复习.
<编程达人入门课程> 本节内容 内存的使用 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群: ,
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
定理21.9(可满足性定理)设A是P(Y)的协调子集,则存在P(Y)的解释域U和项解释,使得赋值函数v(A){1}。
第16讲 相似矩阵与方阵的对角化 主要内容: 1.相似矩阵 2. 方阵的对角化.
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
无线通信系统 信源:消息信号(调制信号) 振荡器:高频载波(正弦) 三要素: 振幅 AM 频率 FM 相位 PM 超外差接收 已调信号.
1.设A和B是集合,证明:A=B当且仅当A∩B=A∪B
第一部分:概率 产生随机样本:对分布采样 均匀分布 其他分布 伪随机数 很多统计软件包中都有此工具 如在Matlab中:rand
卷积码的概率译码.
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
正弦、余弦函数的性质 华容一中 伍立华 2017年2月24日.
第五章 信道编码定理.
第五章 信道编码定理.
§2 方阵的特征值与特征向量.
《通信系统实验与设计》 Matlab编程题目.
§7.3 离散时间系统的数学 模型—差分方程 线性时不变离散系统 由微分方程导出差分方程 由系统框图写差分方程 差分方程的特点.
欢迎大家来到我们的课堂 §3.1.1两角差的余弦公式 广州市西关外国语学校 高一(5)班 教师:王琦.
陈振国 杨鸿文 郭文彬 编著 北京邮电大学出版社
基于列存储的RDF数据管理 朱敏
第四节 向量的乘积 一、两向量的数量积 二、两向量的向量积.
第三章 从概率分布函数的抽样 (Sampling from Probability Distribution Functions)
第四章:信道及其容量 §4.1 信道分类 §4.2 离散无记忆信道 §4.5 信道的组合 §4.6 时间离散的无记忆连续信道
第十七讲 密码执行(1).
第十二讲 密码执行(上).
Viterbi译码 问题:根据接收序列求解最可能的发送序列 例: 收到序列是: 求最可能的发送序列
最小生成树 最优二叉树.
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
9.6.2 互补对称放大电路 1. 无输出变压器(OTL)的互补对称放大电路 +UCC
Presentation transcript:

编码技术引言 2009年秋

1、引言 传输/存储系统框图 术语 学习内容

用于可靠数据传输(存储)的编码 典型的数据传输(存储)系统框图

简化框图

术语 信源,information source 信息序列,information sequence,u 信道编码器,channel encoder 编码序列(码字),encoded sequence (codeword),v 信道,channel 接受序列,received sequence,r 信道译码器,channel decoder 估计信息序列,estimated information sequence, 信宿,destination

课程学习内容 设计和实现信道编码器,以抵抗传输或存储码字面临的噪声; 设计和实现使译码错误率最小的信道译码器; 设计和实现信道编码器/译码器的目标: 噪声环境下,信息尽可能快地传输; 信息在信道译码器的输出端可靠地重现; 降低编码器/译码器的实现代价。

2、码的类型 分组码,block codes 卷积码,convolution codes

分组码 block codes 把信息序列分组,每组包括k bits的信息符号,一个分组就是一个消息(message) u表示一个分组而非整个信息序列,u的可能取值有2k个,即2k种不同的消息 编码器把u独立地变成n维离散的符号向量 v是n维符号组,称为码字,codeword,而非整个序列 编码器的输入端u有2k个取值,对应到编码器输出端n维向量 也有2k个取值,这n维的2k个取值(码字)构成的集合就叫做(n,k)分组码 比值 称之为码率(code rate),信道上传输的每个符号所包含的信息符号数

(n,k)分组码 对二进制而言, ,或 当 时,可认为对每个消息增加了 个冗余比特来构成码字,这些冗余具有抗噪声能力 对二进制而言, ,或 当 时,可认为对每个消息增加了 个冗余比特来构成码字,这些冗余具有抗噪声能力 若固定码率,即 保持不变,可通过增大n和k来增加冗余比特数 冗余比特如何选择?主要问题

(7,4)分组码的例子

卷积码 convolution codes 编码器 输入: k bits的信息序列u 输出: n维编码序列v u和v表示分组序列,而非单个分组 每个编码分组不仅取决于当前单位时间的k bits的信息序列 u(消息组),而且与前m个消息组相关 m称为编码器的存储级数(memory order) 编码器的所有可能输出构成的集合称为“码” 比值 称之为码率(code rate) 二进制卷积码,通过固定n和k,也就固定了R,增加m可以增加冗余,从而增加抗噪声能力

调制与编码 调制 AWGN 解调 离散无记忆信道 有记忆信道 硬判决和软判决 符号传输速率,数据传输速率

调制 编码器的每个输出符号,调制器必须选择一个适于传播,持续时间为T的波形 二进制码,调制器产生两个信号中的一个,对应于编码“1”的s1(t)和对应于“0”的信号s2(t) 对于宽带信号,信号的最优选择是

调制:BPSK 二进制相移键控 载波信号频率f0是1/T的整数倍,Es是信号能量 二进制相移键控:载波 的相位随着编码器的输出而变化取0或π 二进制相移键控:载波 的相位随着编码器的输出而变化取0或π 例子:下图是码字v=(1101000)对应的BPSK调制波形

加性高斯白噪声 AWGN Additive White Gaussian Noise,AWGN 假设传输的信号为s(t) ( ),则接受信号为 ,其中 是一个高斯随机过程,其单边功率谱密度(power spectral density, PSD)为N0

解调 每个时间间隔T,解调器产生一个对应于接受信号 的输出 该输出可以是一个实数或预先选定的离散符号集(Q个)中的一个元素,取决于解调器的设计 最优解调器通常包含一个匹配滤波器或相干检测器,后面再有一个采样开关,每个T秒对输出信号采样 带相干检测的BPSK调制,其采样输出是实数:

M进制相移键控 用M=2l个信道信号来传输信息,首先将二进制编码器的输出序列以l比特为一个字节分段,每个字节称为一个符号,共有M个符号 每个符号映射到信道传输信号集S中的一种信号,每种信号都是周期为T的脉冲波形 M进制相移键控,信号集M个正玄信号组成,这些信号具有相同的能量和周期,它们的相位是等间隔的

离散无记忆信道 若给定时间间隔内检测器的输出仅和该间隔内传输的信号相关,而与任何以前的传输信号无关,则称信道是无记忆的 此时,一般将M进制调制器,物理信道,Q进制解调器合称为离散无记忆信道(discrete memoryless channel,DMC) DMC可用一组转移概率来完全描述: 其中i表示调制器的输入符号,j表示解调器的输出符号, 是发送i,输出j的概率

硬判决和软判决 当解调器的输出采用二进制量化,即Q=2时,译码器只有二进制的输入;此时称解调器采用硬判决,特点:实现简单 二进制输入,Q 进制输出的DMC 二进制对称信道BSC

更多的软判决信息 假设调制器的输入信号是有限离散字符集X中的符号,其中 ,解调器的输出未经量化,此时存在一个离散输入,连续输出的信道 信道的输出是一个随机变量,可以取实数轴上任意点,假设信道仅受均值为0,单边功率谱密度为N0的AWGN影响,则信道的输出是一个均值为0,方差为 的高斯随机变量 信道可以由一组M个条件概率密度哈数来刻画:

更多的软判决信息(续) 对于M=2, ,若采用BPSK,则

有记忆的信道 在给定时间间隔内检测器的输出不仅和当期间隔内的信道信号相关,也和以前传输的信号相关,则称为有记忆信道 衰落信道是典型的有记忆信道

符号传输速率,波特率 每T秒传输一个编码符号,所以符号传输速率(波特率)为1/T 若码率为 ,则k个bits的信息对应于n个bits的传输符号,故信息传输率(数据率)为 b/s 通信中,除了噪声造成信号变形,带宽受限也会造成信号失真,一般应保证带宽(bandwidth)至少为1/2THz

最大似然译码 基本概念 最大似然译码 最大似然译码例子:BSC

假设基础 译码器对接受序列r产生对信息序列u的一个估计值 u和v之间存在一一对应关系,故也可认为对v求一个估计值

误码率和最优译码规则 误码率 最优译码规则:使得P(E)最小,对所有r使得 最小,等价于 最大 译码器的条件误码率(conditional error probability of the decoder)定义: 译码器的误码率(error probability of the decoder): P(r)表示接受序列为r的概率 最优译码规则:使得P(E)最小,对所有r使得 最小,等价于 最大

最大似然译码 对给定r,选择 为码字v,使得 最大 若所有的信息序列(码字)等概率出现 ,即对任意的v,P(v)都一样 ,则上式就变成使得 ,对离散无记忆信道成立ri和vi表示接受序列r和编码序列v的第i个符号,这就是最大似然译码(MLP),等价于

最大似然译码理解 所谓MLD,就是得到估计值 ,根据r来选择合适的 ,使得 最大 MLD是P(v)等概率的情形下最优,但当码字不是等概率出现时MLD不一定是最优,现实中接收端常不能知道码字的概率,MLD是可行的最优选择

最大似然译码例子:BSC BSC,二进制对称信道,r是一个二进制序列,由于噪声的影响,可能某些比特不同于发送码字v 当 时, ;当 时, 当 时, ;当 时, 令 表示r和v之间的汉明距离,若码字长度为n,则 若p<1/2,则log(p/(1-p))<0,对任何码字v,nlog(1-p)是常数,故要使logP(r|v)最大,就是要使d(r,v)最小

噪声信道编码定理,香农 每个信道都有一个容量C,对任意满足R<C的速率R,都存在满足传输速率为R的码,用最大似然译码可以达到任意小的误码率P(E) 对任意R<C,存在着分组长度n足够大的分组码使得 ,任何固定的R<C,通过增加n,可以获得任意低的误码率 同时存在存储级数m足够大的卷积码,使得 注:Eb(R)和Ec(R)是关于R的正函数

噪声信道编码定理 是全体码集合上的平均误码率 指出了存在性,但是没有给出任何构造的方法 固定速率R<C,为获得很低的误码率,需要较长的分组长度,这使得码字集合的大小2k=2nR很大 MLD需要对每个接收序列r,计算使得logp(r|v)最大的码字v,这导致计算次数随n的增加而指数增加,卷积码关于m和计算次数也有类似的结论

面临的要解决的主要问题 构造好的长码,用最大似然译码时,它的性能满足 或 构造好的长码,用最大似然译码时,它的性能满足 或 如何实现易实现的编译码方法,使得其实际性能接近最大似然译码所能达到的性能

错误类型 随机错误 突发错误 随机和突发错误

随机错误信道 无记忆信道,噪声对每个传输符号的影响彼此独立 接受序列中的传输错误随机出现,故无记忆信道又称为随机错误信道,random-error channel 典型随机错误信道:深空信道,部分卫星信道 为纠正随机错误的码称为随机错误纠正码,random-error correcting codes

突发错误信道 “好”的状态s1,传输错误不常出现, ,“坏”的状态s2,传输错误的可能性非常大 为纠正突发错误的码称为突发错误纠正码

混合信道 既有随机错误也有突发错误的信道,称为混合信道 为纠正这类错误的码叫做突发和随机错误纠正码字

差错控制策略 前向纠错 自动请求重传 FEC和ARQ的比较

前向纠错 FEC 传输严格地从发送端到接收端一个方向进行,称之为单向通信系统 单向系统的差错控制策略必须采用前向纠错(forword error crrection,FEC),即纠错码在接收端自动地纠正检查出的错误 主要的差错控制策略,如深空通信系统,数字存储系统

自动请求重传 ARQ 传输系统是双向的 双向通信系统差错控制策略采用错误检测和重传,即自动请求重传(automatic repeat request,ARQ),当接收端检测到错误时,就向发送端发出要求重传该消息的请求,直到消息被正确接收为止 典型例子:数据通信网,卫星通信系统

自动请求重传 等待式ARQ,每传送一个码字必须保证其被正确接收,确保接收端得反馈,否则等待重传 连续式ARQ,发送端连续发送码字,连续接收确认消息,如果接收到否定回答消息,则从被否定的码字开始重传后续码字(退N步ARQ,go-back-N),也可以选择性地传输否定的码字(selective repeat) 连续式ARQ比等待式ARQ效率高,但是复杂,实现代价高

FEC和ARQ的比较 检错对译码设备的要求远比纠错简单 ARQ是自适应系统,错了才重传

性能的衡量 一般用译码错误的概率,误码率 error probability 信噪比,SNR 相对于具有相同传输速率非编码系统的编码增益 coding gain 香浓限

误码率 误码率定义:译码器输出的码字有错误的概率 也可称为误字率(word-error rate, WER)或误分组率(block-error rate, BLER) 误比特率(bit-error rate, BER),译码器输出的信息比特错误概率 编码通信系统设计要求:WER和BER尽可能低

概念 在码率R=k/n的编码通信系统中,为传输每个信息比特需要的符号数目为1/R 若传输每个符号需要能量Es,则每个信息比特对应的能量Eb为Eb=Es/R 一个编码通信系统的误码率常用单位信息比特的能量Eb与信道噪声的单边功率谱密度N0的比值形式来表示

信噪比,SNR Signal-to Noise Ratio,SNR 例如:码字长为n=23bits,信息比特长为k=12bits,冗余11bits,码率R=12/23=0.5217 若采用相干检测,BPSK调制,信道为单边功率谱密度为N0的AWGN信道 Eb/N0表示接收端输入处单位信息比特能量和噪声功率谱密度的比值,SNR,单位为分贝dB

编码增益 为获得一个特定的误码率,如WER或BER,编码系统所需要的SNR比非编码系统小,这个少了的值称为编码增益 如图,当BER=10-5时,硬判决和软判决分别获得了2.15dB和4dB的编码增益,代价是译码复杂性 当SNR较小时,编码增益变成负数,这对任何编码系统都是存在的,即存在SNR的编码阈值,此时编码无效甚至更差

渐进编码增益,asymptotic CG ACG,高SNR下的编码增益 具有最小距离dmin的(n,k)码采用软判决MLD时相对于非编码BPSK的ACG为: 对采用硬判决,有ACG为: 软判决比硬判决大约多3dB的增益,但实际上因SNR达不到3dB,一般在2-2.5dB

香农限 为差错控制而设计编码通信系统时,希望尽可能为了特定的误码率而所需的SNR尽可能小 上述描述等价竟可能最大化编码系统对非编码系统(相同调制信号)的编码增益 依据香农有噪声信道编码定理,可推导出一个一个码率为R的编码系统达到无误或任意小误码率所必须的最小SNR理论极限,称为香农限(Shannon limit) 可用香农限作为标尺来衡量编码增益 通过合适设计具有足够长度的码字,并采用有效地软判决MLD或近MLD算法,香农限可以被逼近

编码调制 信道带宽的展宽 编码调制 分类

信道带宽的展宽 为获得编码增益,将编码技术和二进制调制技术结合,导致信道带宽的展宽,即为了保持信息比特的传输速率和非编码系统一样,需要更宽的信道带宽(1/R) 因此编码增益的代价就是信道带宽的展宽 若带宽受限,如语音电话、地面微波和一些卫星通信,此时很少为差错控制而增加冗余比特 多级调制(M>2)能提高带宽利用率,故将编码和调制结合起来,就可以不用扩展带宽,这成为编码调制(coded modulation),例如:网格编码调制

编码调制 对信息符号编码,然后映射到扩展的调制信号集(相对于非编码调制信号集)上,扩展信号集提供了差错控制的冗余,同时不增加信号速率,也就不增加带宽 每个传输信号表示的信息比特数称为频谱效率(spectral efficiency),如非编码的QPSK(4-PSK)有4个信号,每个信号表示2比特,编码的8-PSK,2个信息比特,1个冗余比特,频谱效率也是2,它们具有相同的带宽,编码增益约为3dB(MLD软判决)

编码调制分类 网格编码调制,TCM 结合卷积码(网格码)和多级调制信号 分组编码调制,BCM 结合分组码和多级调制信号

差错控制编码的思想 向传输信息序列中添加合理设计的冗余信息 冗余信息通过向传输信息序列中添加额外的符号,为保证数据率,需要扩展信道带宽,适合于功率受限通信系统的差错控制 扩展信道信号集,将传输信息序列映射到信号序列时采用更多的信号集,不需要扩展信道带宽而获得编码增益,适合于带宽受限通信系统的差错控制