编码技术引言 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 结合分组码和多级调制信号
差错控制编码的思想 向传输信息序列中添加合理设计的冗余信息 冗余信息通过向传输信息序列中添加额外的符号,为保证数据率,需要扩展信道带宽,适合于功率受限通信系统的差错控制 扩展信道信号集,将传输信息序列映射到信号序列时采用更多的信号集,不需要扩展信道带宽而获得编码增益,适合于带宽受限通信系统的差错控制