纠错编码技术

1、纠错编码技术 主要内容 绪论: 应用，基本原理，发展简史，与信息 论基础 编码的数学基础：代数引论 线性分组码 卷积码 先进的编码技术简介： Turbo Code, LPDC, Polar code, Furtain code 参考书 差错控制编码（英文名为：Error Control Coding），第2版，Shu Lin and D. J. Costello, 机械工业出版社， 2007.6； 如何在噪声信道上实现可靠通信？ 为什么需要纠错编码（信道编码）？ 常见的噪声信道1-模拟电话线 （ADSL） 调制解调器电话线调制解调器 一根电话受到其他电话线干扰，硬件电路导致 信号失真，线路会产

2、生加性热噪声 常见的噪声信道2-深空通信 伽利略号 飞船 无线电波地球 伽利略号 飞船发射信号到达地球是非常微弱的信号，受到地面 和太空干扰源的背景辐射 常见的噪声信道3-细胞复制 父/母细胞 子细胞 子细胞 DNA会产生突变， 变异（恶劣环境产生的辐 射，污染） 常见的噪声信道4-计算机磁盘驱 动器 内存/硬盘/光盘磁盘驱动器内存/硬盘/光盘 磁盘驱动器通过将一小块磁介质校准到两个方向(1或0） ，磁介质小材料可能改变磁化方向，或者一个短时脉冲干 扰会导致数据读取电路读出错误值，磁盘运输或保存过程 中会出现磨损、损坏或灰尘 信道非理想和噪声会导致传输发 生过程错误！ 0 1 0 1 1-p

3、1-p p p BSC P(y=0/x=0)=1-f, P(y=1/x=1)=1-f, P(y=0/x=1)=f, P(y=1/x=0)=f, Solutions 第一章 绪论 1.1 引言 1.2 码类型 1.3 调制编码 1.4 最大似然译码(MLD, Maximum likelihood decoding) 1.5 错误类型 1.6 差错控制策略 1.7 性能衡量 1.8 编码调制 1.9 熵、互信息量、信道容量与编码 引言 主要用于：信息传输和信息存储，过程中信 息出错，检测或纠正错误。 信息传输： 无线通信-移动通信，无线网络（无线局域 网（WLAN）,有线网络（有线电视，.） 信息

4、存储：光盘光驱，硬盘和硬盘驱动系统 典型信息传输和数据存储框图 发射机 接收机 框图功能模块介绍（一） 发射机：发射机： 信源：是人或计算机，输出是连续的声音， 视频，或离散的信息。 信源编码器：将信源输出转化为二进制01 信息序列， 对应连续波形，就是A/D转换（模数转换）， 采样量化。理想信源编码两个原则：编码 输出比特数最小化（Huffman编码）；可完 全重构连续波形。属于信息论范畴 框图功能模块介绍（二） 信道编码：二进制信息序列u变换成离散的编 码序列v，称之为码字。V可为二进制或非二 进制，对抗信道噪声（Why？模拟信号无对 抗噪声能力？数字或幅度离散信号可以？）。 信道编码和信

5、源编码区别：前者在信息中引 入冗余性，纠正错误；后者压缩信源输出波 形中冗余性。是否相同冗余性？ 调制器：将信道编码器每个输出的符号转变 为适合信道传输的波形。举例：广播 信道：信道： 信道：波形进入信道后会收到噪声干扰，比 如电话线，干扰-开关脉冲噪声，热噪声和其 他线串音， 框图功能模块介绍（三） 信道：光盘，灰尘，划痕和表面缺陷。 接收机：接收机： 解调器(demodulator):处理收到T秒波形，产 生离散或连续的输出r； 信道译码：将r转化为二进制输出序列uhat, 此为估计信息序列。寻找使译码的误码率 最小的信道译码器； 信源译码器：将估计的信息序列uhat变换 为信源输出估计，

6、恢复发射机信源编码输 出 第一章 绪论 1.1 引言 1.2 码类型 1.3 调制编码 1.4 最大似然译码(MLD, Maximum likelihood decoding) 1.5 错误类型 1.6 差错控制策略 1.7 性能衡量 1.8 编码调制 1.9 熵、互信息量、信道容量与编码 两种不同类型信道编码 分组码（Block codes）：将信息流或序列 分成多块或组，假定每组由k个比特（符号） 组成。可用u=u_0,u_1,u_(k-1), 称为一个 消息（message）,总共有2k不同信息，如 果是M进制呢？ 编码器会将每个消息转化 为n维离散符号向量，v=v_0,v_1,v_(n

7、-1), 称之为码字(codeword), 一共多少码字？此？ 个码字集合称之为（n,k) 分组码，比值 k/n=R为码率（code rate） 10011 0000100010010011 信息流 分组后 信息 编码后 码字 R1， kn,每个消息附加n-k比特有规律的冗余信息，可对抗信道噪声 (7,4)分组码例子 Message CodewordMessage Codeword 00000001 10001001 01000101 11001101 00100011 10101011 01100111 11101111 第二种类型码 卷积码：同分组码一样，同样分组，不像分 组码，每个编码分

8、组不仅取决于当前时刻对 应的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, Maximum likelihood decoding) 1.5 错误类型 1.6 差错控制策略 1.7 性能衡量 1.8 编码调制 1.9 熵、

9、互信息量、信道容量与编码 调制与编码 对于二进制通信系统中信道编码器每输 出一个符号，调制器必须选中一个适合 信道传输,持续时间为T秒的波形， 比如 “1”对应于s1(t), “0”对应于s0(t), 00 100 2 ( )cos(20),0 22 ( )cos(2)cos(2),0 s ss E s tf ttT T EE s tf tf ttT TT Es为功率还是能量？为什么？ 二进制相移健控调制（BPSK，Binary phase shift keying ）, 实际上存在成形滤波器？作用？频谱线性搬移到射频段！频谱线性搬移到射频段！ 系统模型 各种通信系统中噪声一般近似为加性白高斯

10、噪声(白噪声？)如果发 射的信号为s(t), 则接收信号为 r(t)=a(t) s(t)+n(t) 式中n(t)高斯随机过程，单边带功率谱密度为N0. a(t)是信道衰落因子，对于加性白高斯信道（AWGN： Additive white Gaussian noise），其是常数；对于市区信道，信号带宽较窄时，多条路径合成复高斯分布， 其包络是瑞利分布或赖斯分布（慢变化随机过程），相位是均匀分布。 解调器 在每T秒间隔上，解调的器产生一个相应 于接收 的输出： 0 ( )cos2 T s c E yr tf t dt T 最优检测器，匹配滤波器，想干检测器，输 出实数，需要 什么是匹 配滤波器

11、？ 多进制调制器 对于多(M)进制通信系统，先将二 进制信 道编码器输出的输出序列按l比特 为组进行 分段，M=2l, 存在M个波形, 例如 MPSK： 0 2 ( )cos(2),0,1,2, s ii E s tf ttT iM T s1 s2 s3 s4 s1s2 s1 s2 s3 s4 s5 s6 s7 s8 a) BPSK b) QPSK c) 8-PSK 45 BPSK、QPSK和8-PSK 的信号星座图 适用于信道编码的离散信道模型 给定当前T秒内检测器只与该间隔内传输 的信号有关，与以前传输符号无关，称 该信道为无记忆信道 (memoryless). 前面AWGN信道属于此信道

12、， 将M进制调制器，信道和Q进制的解调器 输出合成一个大的信道，可建模为离散 的无记忆信道(DMC: Discrete memoryless channel) 适用于信道编码的离散信道模 型 uv r u ( )s t ( )r t ( )n t 离散记忆信道 解调器 几种典型的离散信道模型 1 - p 1 - p p p 00 11 (a) 0 0 1 1 Q - 1 P(0|0) P(1|0) P(1|1) P(Q 1|0) P(Q 1|1) (c) 11 0 0 1 p q 1 p q p p q q (b) 可擦除 传输概率示意图:(a)二进制对称信道（BSC）；（b）二进制对称可 擦

13、除信道；（c）二进制输入，Q进制输出离散无记忆信道 BSPK在AWGN等价于BSC 非编码的二进制的误比特 率为 2 2 0 /2 0 /2 ( 2/) 1 ( ),0 2 1 ( ),0 2 s x x pQEN Q xex Q xex 其中 当采用二进制编码，调制器也是二进制，如果解调器的输出是二进制量化Q=2， 此时译码器只有二进制输入 ，解调器采用硬判决(hard-decision),译码器为硬判决译码(hard-decision decoding); 如果Q2, 软判决 (soft decision), 软判决译码(soft decision decoding) 离散信道模型和条件概

14、率 如图1-7所示，编码器输出（调制器输入） 为离散的星座图符号，解调器输出是未 经量化的随机向量y属于-到+，此处 调制器，信道和解调器合成了一个离散 输入连续输出离散信道。如果信道噪声 是AWGN，0均值和方差为No/2, 该信道可 用M个调件概率密来刻画。对于M=2， 2 0 0 () 1 (0/1)exp s yE p x x NN 符号传输速率和信息传输速率 如果每T秒传输一个符号，则符号传输速 率为1/T符号/秒(Symbol/s)，波特率; 对于 于编码系统，如果信道编码码率为R，信 息传输速率为log2MR/T, M=2, 为R/T；为 了减少符号间干扰W至少为0.5/THz,

15、 因此 数据速率受带宽限制2W，编码系统信道 速 率 = 2 l o g 2 M R W ， 非 编 码 系 统 为 2log2MW，考虑到成形滤波器，实际的信 息速率为 2 2log ,0.2 1 RWM a a 频谱效率？ 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信道中采用输出有限量化的编码系统，对于分组

16、码，u表示一个k比特消息，编码输出代表v代表n个 符号码字，解调器输出r代表Q进制的n维向量，译码器的输出uhat代表k比特消息估值，u和v有一一对应关系； 译码器主要任务：根据接收序列r估计发射信息序列u ! 数字信源信道编码 离散信道 数字信宿信道译码 u v r uhat MLD 假定接收为r，则译码器条件错误 概率为： ( / )(/ )P E rP vv r 译码器错误概率为： ( )(/ ) ( ) r P EP vv r P r P(r)为接收序列为r的条件概率，其独立于译码规则。最优的译码规则应该对于每个r使P(E/r) 最小，也就是最大化P(v_hat=v/r), why?

17、( / ) ( ) ( / ) ( ) P r v P v P v r P r MLD P(v)=1/2k max ( / )max ( / ) vv P v rP r v 对于无记忆信道 ( / )( /) ii i P r vP r v 由于logx是？ log ( / )( /) ii i P r vP r v MLD=最小距离（BSC信道） 解调器输出二进制r，由于信道噪声影响， 发生的码字v可能不等于r，n位置某些位 不同， ,(/); ,(/)(1) iiii iiii rvP rvp rvP rvp (,)d rv 两者距离，等价于码字发生错误个数， Why？ 码字长度为n的分

18、组码 ( , )( , ) ( / )(1) d r vn d r v P r vpp MLD=最小距离（BSC信道） ( ( / )( , )log( , )log(1) ( , )log(/(1)log(1) log P r vd r vpnd r vp d r vppnp p0.5, MLD等价于最小化d(r,v), Why? 有噪声信道编码定理 C. E. Shannon 于1948年在他的著名论文“A mathematical theory of communication”给出 AWGN信道的可靠的信息传输能力，他证明： 每个信道都存在一个信道容量C（最大信息速率），只要需要传输的

19、信息速率R低于C，则 存在速率为R的码，用MLD可到任意小的错误概率P(E) 对于任意RC, 存在分组码，存在分组长度n足够大的分组码使 ( ) ( )2 b nER P E 同时存在存储级数m足够大的卷积码(n,k保持不变) ( ) ( )2 c mnER P E 第一章 绪论 1.1 引言 1.2 码类型 1.3 调制编码 1.4 最大似然译码(MLD, Maximum likelihood decoding) 1.5 错误类型 1.6 差错控制策略 1.7 性能衡量 1.8 编码调制 1.9 熵、互信息量、信道容量与编码 错误类型一：随机错误 随机错误信道（random-error ch

20、annels）: 在无记忆信道上，例如AWGN， 噪声对每 个传输符号影响是独立的，以图1-6a的 BSC为例，每个传输比特被错误接收的概 率为p，被正确接收概率？与其他比特无 关。 典型的随机错误信道:深空通信信道，卫星通信信 道，一些视距传输信道。 纠随机错误码: 为纠正随机错误的而设计的码。 错误类型二：突发错误 突发错误信道（random-error channels）: 在有记忆信道，各次传输信道噪声不是 独立，或信道增益a(t)是慢变化的（比如 步行到高大建筑物后面，信道处于深度 衰落） Rayleigh Fading (瑞利衰 落) Deep fading 有记忆信道简化模型：两

21、个状态：好状态 （传输错误概率大）和坏状态（传输错误 概率大）。 第一章 绪论 1.1 引言 1.2 码类型 1.3 调制编码 1.4 最大似然译码(MLD, Maximum likelihood decoding) 1.5 错误类型 1.6 差错控制策略 1.7 性能衡量 1.8 编码调制 1.9 熵、互信息量、信道容量与编码 单向传输系统：前向纠错(FEC) 如第6页的通信系统框图是单向系统，信息 传输方向严格按照从发射机向接收机。该 系统差错控制策略必须采用前向纠错 (Forward error correction, FEC), 接收机利用 纠错码纠错码自动纠正和检测错误。典型 例子如

22、下：深空通信，数字存储系统，数 字调幅广播（DRM），数字陆地电视(DVB- T), 数字有线电视(DVB-C), 2G,3G. 双向传输系统：自动请求重传(ARQ) 有些情况下，系统是双向，信息沿两个 方向传输，发射机可作为接收机。 发送机接收机 信道 反馈 双向系统的差错控制策略同时采用检测错误和重传，称为自动请求重传(ARQ: Automatic repeat request)，ARQ系统中接收机检测出错误，就向发送端发出要求重传该消息的要求，直到消 息被正确接收。ARQ有两种：等待式和连续ARQs。 传送 等待ARQ（Stop-and-wait） 码字1码字2 码字1码字1译码 失败

23、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); 另外一种可选方案，发送端仅传输 那些有否定应答的码

24、字，称为选择重传 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 差错控制

25、策略 1.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作为

26、参考。由图可知 ，当Eb/No大于某个阈值时，无 论采用硬判决还是软判决，在相 同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 上图绘出LD

27、PC（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, Maximum likelihood decoding) 1.5 错误类型 1.6 差错控制策略 1.7 性能衡量 1.8 编码调制 1.9 熵、互信息量、信道容量与编码 参考书 T. M. Cover and J. A . Thomas. 信息论基础 （Elements of In

28、formation Theory），清华 大学出版社 第一作者：Stanford University 59 熵(Entropy) SX ii i XPXPXH)(log)()( S xfxfXh)(log)()( xdxxfxf xxfxxfxxf xxfxxfppXH iii iiii log)(log)( log)()(log)( )(log)(log)( 式中 h(X) 成为微分熵. 熵与微分熵之间区别： 对应离散的随机变量X 对于连续的随机变量 60 熵计算的例 子 1)1log()1 (log)(aaaaXH 2 2 2 2 2 2 2 2 2log 2 1 2 1 2log 2

29、1 )()( 2 1 2log)( )( 2 )( 2log)( )(log)()( e dxxfmxdxxf dxxf mx dxxf dxxfxfXh SS SS S 对于离散的随机变量, P(X=0)=a,P(X=1)=1-a 对于连续的随机变量，N(m,2) 61 相对熵和Jensen不等式 Sx xq xp xpqpD )( )( log)()/( )(EXfXfE 0)(log )( )( )(log )( )( log)()/( xq xp xq xp xp xq xpqpD 请证明。现在我们用它来推导相对熵的性质： 相对熵, Jensen不等式, f(x) 是一个凸函数， X

30、是一个随机变量 62 Jensen不等式的证明 )(EXfXfE 12 1212 0 1 11 , , , , ()()() () Forx xa b fxxf xf x 证明: 函数f(x)在区间（a，b） 上是一个凸函数 Jensens 不等式: f(x)是一个凸函数，X是一个随机变量 X1 x x2 63 高斯分布熵最大定理 )()( )log()( )log()( )log()log( )/log()|(0 ghfh dxggfh dxgffh dxgff dxgffgfD 2 2 2 222 2 )( exp 2 1 )( )()()()( mx xg dxxgmxdxxfmx g(

31、x), f(x)有相同的协方差 定理的证明 64 互信息量与维恩 图 )/()()/()( )()(|),( )()( ),( log),(),( XYHYHYXHXH yfxfyxfD dxdy yfxf yxf yxfYXI I(X,Y) H(X) H(Y) 维恩图 65 互信息量（Mutal Information） ),(max )( YXIC xp 信道容量=一个通信信道中能够以任意小的错误率传递信息时可达的速率上限 (数据压缩与传输：冗余) 66 信道容量（Channel Capacity） ),(max )( YXIC xp 信道容量=一个通信信道中能够以任意小的错误率传递信息时

32、可达的速率上限 (数据压缩与传输：冗余) 67 白高斯噪声信道容量 ntransmisioper P Ph PPYXI ENEXh ENEXhNhXNhXEYYE NHYH XNHYH XYHYH XYHYHYXI N X NY 2 222 222 1log 2 1 2log 2 1 2log 2 1 ),( )()( )()( )/X()( )/()( )/()(),( XAWGNY Y=h*X+N N是加性高斯白噪声， h是恒定的 通道增益 SNR=h2E(X2)/E(N2) 克劳德香农(Claude Elwood Shannon，1916-2001)1916年4 月30日诞生于美国密西根

33、州的Petoskey。在Gaylord小镇长大 ，当时镇里只有三千居民。父亲是该镇的法官，他们父子的 姓名完全相同，都是Claude Elwood Shannon。母亲是镇里的 中学校长，姓名是Mabel Wolf Shannon。他生长在一个有良 好教育的环境，不过父母给他的科学影响好像还不如祖父的 影响大。香农的祖父是一位农场主兼发明家，发明过洗衣机 和许多农业机械，这对香农的影响比较直接。此外，香农的 家庭与大发明家爱迪生(Thomas Alva Edison，1847-1931)还 有远亲关系。 2001年2月24日，香农在马萨诸塞州Medfod辞世，享年85岁。贝尔实 验室和MIT发

34、表的讣告都尊崇 香农为信息论及数字通信时代的奠基人 。 1948年香农在Bell System Technical Journal（贝尔系统技术杂志）上发表了A Mathematical Theory of Communication 。 克劳德香农在公众中并不特别知名，但他是使我们的世界能进行即时通信的少数科学家和思想 家之一。他是美国科学院院士、美国工程院院士、英国皇家学会会员、美国哲学学会会员。他获 得过许多荣誉和奖励。例如1949年Morris奖、1955年Ballantine奖、1962年Kelly奖、1966年的国 家科学奖章、IEEE的荣誉奖章、1978年Jaquard奖、198

35、3年Fritz奖、1985年基础科学京都奖。他 接受的荣誉学位不胜枚举，不再赘述。 今天，我们怀念香农，要熟悉他的两大贡献：一是信息理论、信息熵的概念；另一是符号逻 辑和开关理论。 70 香农信道容量公式香农信道容量公式 （1948） 两部分: 当传输速率RC, 任何方式的编码都无法实现可靠的信息传输 )sec/)(1 (log2ondbit P P BC N S 71 频谱效率频谱效率 )M(bit/s/Hzlog n k 2 1a 2 b R (bit / s / Hz) B 传输速率 信道带宽 72 最大频谱效率最大频谱效率 最大频谱效率: BNP CEER T kE T E P N bbb bs S 0 )1 (log)1 (log 0 max2 0 2max N E N E B R bbb )1 (log2 max Hzsbits P P B C N S 73 香农限香农限 max0 12 max N Eb dB N Eb 59.