编码技术引言 2009年秋.

Presentation on theme: "编码技术引言 2009年秋."— Presentation transcript:

1 编码技术引言 2009年秋

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

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

4 简化框图

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

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

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

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

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

10 (7,4)分组码的例子

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

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

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

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

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

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

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

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

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

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

21 更多的软判决信息（续） 对于M=2， ，若采用BPSK，则

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

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

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

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

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

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

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

29 最大似然译码例子：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)最小

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

52 编码调制分类 网格编码调制，TCM 结合卷积码（网格码）和多级调制信号 分组编码调制，BCM 结合分组码和多级调制信号

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