[数学]信息论与编码理论2012-ch5 信道编码-概念

Todaydoesnotwalk,willhavetoruntomorrow

信道编码定理

1948年,信息论的奠基人C.E.Shannon在他的开创性论文“通信的数学理论”中,提出了著名的有噪信道编码定理。

他指出：对任何信道,只要信息传输速率R不大于信道容量C,就一定存在这样的编码方法：在采用最大似然译码时,其误码率可以任意小。

信道编码

信道编码定理

该定理在理论上给出了对给定信道通过编码所能达到的编码增益的上限,并指出了为达到理论极限应采用的译码方法。

在信道编码定理中,香农提出了实现最佳编码的三个基本条件：(1)采用随机编译码方式;(2)编码长度Ｌ→∞,即分组的码组长度无限;(3)译码采用最佳的最大似然译码算法。

信道编码

信道编码定理

在满足这三个条件的前提下,香农认为在有噪信道中可以实现无差错传输。在这一编码定理的理论引导下,人们开始了对设计出信道好码的探索与研究。信道编码定理为人们探索信道的最佳编码方案提供了理论依据,但并没有指明如何获得好码。

后来出现了多种信道编码方案,如RS码、卷积码、级联码等。每一编码方案的提出,性能虽有所提高,但距香农极限还有很大距离。1993年出现的Turbo码,由于其很好地应用了编码定理中的随机性编译码条件和最佳译码算法,而获得了几乎接近香农理论极限的译码性能,立即在通信界引起了研究Turbo码的热潮。

信道编码

信道编码的历史

50年代至60年代初，主要研究各种有效的编、译码方法，奠定了线性分组码的理论基础；提出了BCH编码、译码方法以及卷积码的序列译码；给出了纠错码的基本码限；还出版了纠错码的第一本专著

60年代至70年代初，这是纠错码发展过程中最为活跃的时期。提出了如门限译码、迭代译码、软判决译码和卷积码的Viterbi译码等有效的编译码方法；同时注意到了纠错码实用化的问题，讨论了如码重量分布、译码错误概率和不可检错误概率的计算、信道的模型化等与实用化有关的各种问题

信道编码

信道编码的历史

70年代以来，纠错码在实际应用中得到了更大的发展。大规模集成电路和微机的迅速发展，为纠错码的实用打下了坚实的物质基础。

70年代末、80年代初（20世纪），G.Ungerboeck把编码与调制相结合提出了网格编码调制（TCM,trellis-codedmodulation）技术是编码理论的又一重要里程碑。

继TCM之后，1993年C.Berrou，A.Glavieux和P.Thitimajshima发现的Turbo码是又一重大突破.

信道编码

信道编码定理指出：在编码速率小于信道容量的条件下，通过编码可以使译码错误概率任意小，从而达到可靠通信。给出的结果只说明存在一种编码方式。其误码率随着码长n的增长趋于任意小。证明是非构造性的，它没有告诉我们如何构造实际上可实现的、具有上述性能的这类码的方法。

信道编码/纠错编码/差错控制：就是为解决这一问题而产生的学科，它的目的是寻找在实际上易于实现且能达到可靠通信的编译码方法。

6.1信道编码的概念

6.2线性分组码

6.3循环码

6.4卷积码

6.5信道编码总结

第六章信道编码

6.1.1信道编码在数字通信系统中的地位和作用

6.1.2信道编码的基本思想和分类

6.1.3检错与纠错原理

6.1.4差错控制的基本方式和能力

6.1信道编码的概念

(1)数字通信系统工作原理

数字通信系统模型

信源：可以是人或机器（例如计算机、传感器）；

信源编码器：将信源输出变换成信息序列；

调制器：把输入的消息序列变换为适合于在实际信道中传输/存储的信号波形；

6.1.1信道编码在数字通信系统中的地位和作用

传输信道/存储媒介

有线：实际的传输信道可能是光缆、电缆等有线信道；

无线：高频无线线路、卫星中继等无线信道；

存储媒介：媒介可以是磁带、磁盘、光盘等；

无论何种传输媒介，都受到不同性质的干扰：

有线信道中的脉冲干扰；

无线信道中的噪声和衰落；

存储媒介的缺损也被看做是脉冲干扰。

解调器：其输入信号一般是受到干扰的混合波形，解调器的任务就是从有用信号和干扰的混合波形中恢复有用的信号，这个过程与调制器的过程相反。由于干扰的作用，解调器的输出信号不可避免地包含着差错，差错的多少不应超过系统所规定的数值。

6.1.1信道编码在数字通信系统中的地位和作用

信源译码器：把解调器输出的序列变换成为信源输出的估值。

图6.1.1所示的数字通信系统并没有信道编码和信道译码的环节。为了明确信道编码在数字通信系统中的地位和作用，介绍数字通信系统的主要技术指标。

6.1.1信道编码在数字通信系统中的地位和作用

(2)通信系统的主要技术指标

传输速率

码元：携带数据信息的信号单元。

码元传输速率/波特率/调制速率：每秒钟通过信道传输的码元数。单位是波特(Bd)。

比特率/比特传输速率：每秒钟通过信道传输的信息量。单位是比特/秒(bit/s)。

这两种传输速率的定义不同，它们都是衡量系统传输能力的主要指标。

二进制：每个码元的信息含量为1比特，二进制的波特率与比特率在数值上是相等的。

M进制：每一个码元的信息含量为log2M。如果码元传输速率为rs波特，相应的比特率rb为

rb=rslog2M(bit/s)

6.1.1信道编码在数字通信系统中的地位和作用

差错率：差错率是衡量传输质量的重要指标之一，它有以下几种不同的定义。

码元差错率：指在传输的码元总数中发生差错的码元数所占的比例（平均值），简称误码率。

比特差错率/比特误码率：指在传输的比特总数中发生差错的比特数所占的比例（平均值）。在二进制传输系统中，码元差错率就是比特差错率。

码组差错率：指在传输的码组总数中发生差错的码组数所占的比例（平均值）。

根据不同的应用场合对差错率有不同的要求。

在电报传送时，允许的比特差错率约为10－4～10－5；

计算机数据传输，一般要求比特差错率小于10－8～10－9；

在遥控指令和武器系统的指令系统中，要求有更小的误比特率或码组差错率。

6.1.1信道编码在数字通信系统中的地位和作用

可靠性

可靠性是衡量传输系统质量的一项重要指标，工程中经常用平均无故障间隔时间来衡量。

在数字通信系统中信息传输/存储所遇到的最主要的问题是在传输过程中出现差错的问题，也就是传输可靠性的问题。

在传输过程中产生不同差错的主要原因：

不同的传输系统有不同的性能；

在传输过程中干扰不同。

不同的用户或不同的传输系统对差错率的要求不同。

有两种途径降低误码率以满足系统要求：

降低信道(调制解调器/传输媒介)本身引起的误码率；

采用信道编码，在数字通信系统中增加差错控制设备。

6.1.1 信道编码在数字通信系统中的地位和作用

降低信道引起误码率的主要方法

选择合适的传输线路：如有线线路中，电缆线路优于明线线路，光缆优于电缆；

改进传输线路的传输特性或增加发送信号功率：如进行相位均衡和幅度均衡以改进线路的群延时特性和幅频特性，增加中继放大器。在无线信道中，可以增加发射机功率、利用高增益天线、低噪声放大器等方法改善信道；

选用潜在抗干扰性较强的调制解调方案。

6.1.1 信道编码在数字通信系统中的地位和作用

(3) 采用信道编码的数字通信系统

在某些情况下，信道的改善可能较困难或者不经济，这就要求采用信道编码，以便满足系统差错率的技术指标要求。

信道编码为系统设计者提供了一个降低系统差错率的措施。采用信道编码后的数字通信系统可用图6.1.2所示。

6.1.1 信道编码在数字通信系统中的地位和作用

(1) 编码信道：是研究纠错编码和译码的一种模型。如图6.1.3所示。

编码信道

无线通信中的发射机、天线、自由空间、接收机等的全体；

有线通信中的如调制解调器、电缆等的全体；

Internet 网的多个路由器、节点、电缆、底层协议等的全体；

计算机的存储器（如磁盘等）的全体。

6.1.2 信道编码的基本思想和分类

二进制信道：当码字 C 和接收向量 R 均由二元序列/向量表示时，称编码信道为二进制信道。

C=(C0,C1,…,Cn-1),Ci∈{0,1}

R=(R0,R1,…,Rn-1),Ri∈{0,1}

描述二进制信道输入输出关系或噪声干扰程度的是转移概率p(R/C)。

无记忆二进制信道：对任意的n都有

则称为无记忆二进制信道。

无记忆二进制对称信道/BSC/硬判决信道：无记忆二进制信道的转移概率又满足 p(0/1)=p(1/0)=pb，称为无记忆二进制对称信道。如图6.1.4所示。

6.1.2 信道编码的基本思想和分类

只要噪声是白噪声，大多数二进制传输信道的模型都可以等效为一个BSC信道。

二进制编码信道模型：

R =C+E (mod 2)

E：随机变量；

差错图案：随机序列(Ei)；

称E=(E0,E1,…,En-1)中Ei=1为第i位上的一个随机错误；

第i至第j位之间有很多错误时，称为一个j－i+1长的突发错误。

二进制软判决信道：无记忆编码信道的每一个二元符号输出可以用多个比特表示，理想情况下为实数，此时的无记忆二进制信道称为二进制软判决信道。

6.1.2 信道编码的基本思想和分类

硬判决和软判决译码

在差错控制编码方面的第一个量化的飞跃在于系统工程师意识到将解调和译码分离会带来损失。差错控制编码理论的提出，最初是为了补偿由解调器引进的差错。在这个思想指引下，解调器首先判断调制器的输入会是什么，再将判决的结果输入到译码器；然后使用已知的码字结构去判断编码器输入端的码字。这个过程称之为“硬”判决译码；它并不是一个最佳的方法，因为对于每次硬判决，解调器都要丢失一些可能会用到的信息，而且我们知道，不应该在和这个信息有关的所有判决执行之前，将信息过早地丢弃。

6.1.2 信道编码的基本思想和分类

硬判决和软判决译码

采用将编码和调制结合的方法，解调器就不会将一些错误传递到译码器。解调器只是对各种符号进行暂时的估计，通常被称作“软”判决，这样就可以不丢失一些对于译码器来说有用的信息。“最佳”的译码器可以采用ＭＡＰ（最大后验概率）算法，将比特差错率（ＢＥＲ）最小化。软判决译码相对于硬判决译码，通常在性能上具有一定程度的改善。经常引用的数字是，如果采用软判决，信号的ＳＮＲ会相对于硬判决具有２ｄＢ的优势。

在进行硬判决译码时，采用码字间汉明距离最大化准则；而对于软判决译码，则是几何距离（欧式距离）最大化准则。因此，软判决译码时我们常说针对“信号空间”进行译码。

6.1.2 信道编码的基本思想和分类

(2) 信道编码的基本思想

信道编码的对象：是信源编码器输出的信息序列m。通常是二元符号1、0组成的序列。

信道编码的基本思想

按一定规则给数字序列m增加一些多余的码元，使不具有规律性的信息序列 m 变换为具有某种规律性的数码序列 C；

码序列中的信息序列码元与多余码元之间是相关的；

信道译码器利用这种预知的 编码规则译码。检验接收到的数字序列 R 是否符合既定的 规则，从而发现 R 中是否有错，或者纠正其中的差错；

根据相关性来检测/发现和纠正传输过程中产生的差错就是信道编码的基本思想。

6.1.2 信道编码的基本思想和分类

码元的组成及其它们之间的关系

信息码组：数字序列 m 总是以 k 个码元为一组传输，称这k 个码元的码组为信息码组。例如遥控系统中的每个指令字，计算机中的每个字节。

码组/码字：信道编码器按一定的规则对每个信息码组附加一些多余的码元，构成了 n 个码元的码组。

码组的 n 个码元之间是相关的，附加的 (n－k) 个多余码元为何种符号序列与待编码的信息码组有关。

监督码元/监督元：附加的 (n－k) 个码元称为该码组的监督码元或监督元。

6.1.2 信道编码的基本思想和分类

可靠性与带宽、速度的关系

从信息传输的角度，监督元不载有任何信息，所以是多余的。这种多余度使码字具有一定的纠错和检错能力，提高了传输的可靠性，降低了误码率；

如果要求信息传输速度不变，在附加了监督元后必须减小码组中每个码元符号的持续时间，对二进制码，就是要减小脉冲宽；若编码前每个码脉冲的归一化宽度为1，则编码后的归一化宽度为 k/n (k

如果保持码元持续时间不变，必须降低信息传输速率。这时，以信息传输速度的多余度或称时间上的多余度换取了传输的可靠性。

6.1.2 信道编码的基本思想和分类

(3) 信道编码的分类

广义的信道编码是为特定信道传输而进行的传输信号设计与实现，常用的信道编码有：

描述编码：用于对特定信号的描述，如 NRZ 码、ASCⅡ码等；

约束编码：用于对特定信号特性的约束，如用于减少直流分量的 HDB-3码，用于同步检测的 Barker 码；

扩频编码：用于扩展信号频谱为近似白噪声谱并满足某些相关特性，如 m 序列等；

纠错编码：用于检测与纠正信号传输过程中因噪声干扰导致的差错，纠错编码又可分为几类。

6.1.2 信道编码的基本思想和分类

纠错编码的分类

分组码：编码的规则仅局限于本码组之内，本码组的监督元仅和本码组的信息元相关。

信息码组由 k 个二进制码元组成，共有 2k 个不同的信息码组；

附加n－k个码元，每个监督元取值与该信息码组的k个码元有关；

编码器输出长度 n；

码字的数目共有 2k ；

这2k 个码字的集合称为 (n,k) 分组码；

分组码的每个码字只取决于相应的信息码组，编码器是无记忆的，可用组合逻辑实现。

卷积码：本码组的监督元不仅和本码组的信息元相关，而且还与本码组相邻的前 n－1 个码组的信息元相关。

6.1.2 信道编码的基本思想和分类

是否可用线性方程组来表示

线性码：编码规则可以用线性方程表示；

非线性码：编码规则不能用线性方程表示；

按码字的结构分

系统码：前 k 个码元与信息码组一致；

非系统码：没有系统码的特性。

按纠正差错的类型可分为纠正随机错误的码和纠正突发错误的码；

按码字中每个码元的取值可分为二进制码和多进制码。

6.1.2 信道编码的基本思想和分类

(1) 检错与纠错的目的和性质

目的：从信道的输出信号序列 R 是否是可能发送的 C，或纠正导致 R 不等于 C 的错误。

性质：纠错编码是冗余编码。例如BSC信道，消息m和码字C都是二进制序列/向量。

编码效率：R=k/n。

6.1.3 检错与纠错原理

(2) 偶（或奇）校验方法

一个奇偶校验位

p 为偶校验位

m0+m1+m2+…+mk－1+p=0 (mod 2)

则 C =(m0,m1,m2,…,mk－1,p) 为一个偶校验码字。

C 中一定有偶数个“1”

所有可能的 C 的全体称为一个码率为 k/(k+1) 的(k+1,k) 偶校验码；

确定校验位 p 的编码方程为 p= m0+m1+m2+…+mk－1

当差错图案 E 中有奇数个“1”，即 R 中有奇数个位有错时，可以通过校验方程是否为0判断有无可能传输差错。

校验方程为1表明一定有奇数个差错，校验方程为0表明可能有偶数个差错。

6.1.3 检错与纠错原理

多个奇偶校验位

一个校验位可以由信息位的部分或全部按校验方程产生；

例如 C 是一个对阵列消息进行垂直与水平校验以及总校验的码字；

其码率为

6.1.3 检错与纠错原理

当校验位数增加时，可以检测到差错图案种类数也增加，同时码率减小。

(3) 重复消息位方法

n重复码：码率为 1/n，仅有两个码字 C0和 C1，传送1比特(k=1)消息；

C0=(00…0)，C1=(11…1)

n重复码可以检测出任意小于 n/2 个差错的错误图案

BSC信道：pb≤1/2，n比特传输中发生差错数目越少，概率越大 (1－pb)n> pb(1－pb)n －1>… > pbt(1－pb)n －t>… > pbn

总认为发生差错的图案是差错数目较少的图案，当接收到重复码的接收序列 R 中“1”的个数少于一半时，认为发送的是C0，否则认为是 C1。图6.1.7所示纠1个任意差错的3重复码。

6.1.3 检错与纠错原理

6.1.3 检错与纠错原理

(4) 等重码/定比码

设计码字中的非0符号个数恒为常数，即 C 由全体重量恒等于 m 的 n 重向量组成（等重码） /非0符号与0符号的比例是固定的（定比码）

等重码可以检测出全部奇数位差错，对某些码字的传输则可以检测出部分偶数位差错。

定比码有很好的检错能力，由于监督位数多，因此其效率比奇偶校验码低。但它的应用很广，因为它们的大部分设备都可以与不编码的五单位和其单位电报系统通用。如5/3,7/3定比码。

6.1.3 检错与纠错原理

1、差错控制的理论基础

1)香农第二定理

2)近世代数

6.1.4 差错控制的基本方式和能力

2、差错控制的途径

信道编码定理公式

纠错编码的基本理论

利用冗余度

噪声均化

6.1.4 差错控制的基本方式和能力

前向纠错(FEC)：发送端的信道编码器将信息码组编成具有一定纠错能力的码。接收端信道译码器对接收码字进行译码，若传输中产生的差错数目在码的纠错能力之内时，译码器对差错进行定位并加以纠正。

自动请求重发(ARQ)：用于检测的纠错码在译码器输出端只给出当前码字传输是否可能出错的指示，当有错时按某种协议通过一个反向信道请求发送端重传已发送的码字全部或部分。

混合纠错(HEC)：是FEC与ARQ方式的结合。发端发送同时具有自动纠错和检测能力的码组，收端收到码组后，检查差错情况，如果差错在码的纠错能力以内，则自动进行纠正。如果信道干扰很严重，错误很多，超过了码的纠错能力，但能检测出来，则经反馈信道请求发端重发这组数据。

6.1.4 差错控制的基本方式和能力

3、差错控制系统

信息反馈(IRQ)：也称回程校验方式。收端把收到的数据，原封不动地通过反馈信道送回到发端，发端比较发的数据与反馈来的数据，从而发现错误，并且把错误的消息再次传送，直到发端没有发现错误为止。

6.1.4 差错控制的基本方式和能力

3、差错控制系统

1) FEC:

6.1.4 差错控制的基本方式和能力

2) ARQ:

3、差错控制系统

6.1.4 差错控制的基本方式和能力

停止-等待式ARQ

连续式ARQ

选择式ARQ

3、差错控制系统

2) ARQ:

6.1.4 差错控制的基本方式和能力

3、差错控制系统

2) ARQ:

6.1.4 差错控制的基本方式和能力

ACK1

NAK2

ACK2

W-ARQ方式的原理为：发送端发送码字后，等待接收端反馈回该码字的判决信号。如果码字接收正确，则继续发下一个码字；如果码字接收错误，则重传该码字，指导该码字正确接收为止。

3、差错控制系统

2) ARQ:

6.1.4 差错控制的基本方式和能力

NAK1

GBN-ARQ方式的原理为：发送端发送一串码字后，如果接收端反馈回第n个码字接收错误的信号，那么接收端删除第n个码字及后续接收的所有码字，发送端将重传第n个码字及后续的所有码字。

3、差错控制系统

2) ARQ:

6.1.4 差错控制的基本方式和能力

NAK1

NAK4

10

11

10

12

SR-ARQ方式的原理为：SR-ARQ在GBN-ARQ的基础进行改进，如果发送端从接收端反馈信号中发现某个码字接收错误，则发送端只重传该码字，接收端只删除错误码字，而保留正确接收的码字。

3) HEC:

4、IRQ:

3、差错控制系统

6.1.4 差错控制的基本方式和能力

3、差错控制系统

设计差错控制系统时需考虑以下因素：

1、满足用户对错误概率的要求

2、有尽可能高的信息传输率

3、有尽可能简单的编译码算法，且易于实现

4、可接受的成本

6.1.4 差错控制的基本方式和能力

译码过程

由图6.1.2可见：译码器接收到一个接收码字 R 后，按编码规则对 R 进行译码后输出信息码组的估值 m’；

信息码组与码字 C 之间是有固定规则的，这相当于信道译码器能给出码字 C 的估值 C’。当C’≠C时就出现了译码错误。因为只有当 C’=C 时，m’=m。

6.1.4 差错控制的基本方式和能力

4、最大似然译码

最大后验概率译码准则

当译码器收到某一个接收码字R后，根据最大后验概率p(C/R)进行译码判决，一定使译码错误概率最小。

根据贝叶斯原理

似然函数：p(R/C)

6.1.4 差错控制的基本方式和能力

设每个码字长为 n，若接收码字 R 与码字 C 的距离为 d(R,C)，则条件概率 p(R│C) 可表示为

最大化 p(R│C) 等价于最小化 d(R,C)，所以使差错概率最小的译码是使接收向量 R 与输出码字 C’ 距离最小的译码。

6.1.4 差错控制的基本方式和能力

编码增益

实际的通信系统，信号的传送需要一定的信噪比 Eb/N0，它直接影响信道转移概率的大小，误码率 pbe与信噪比 Eb/N0 的关系如图6.1.9所示，当采用纠错码之后，达到同样的误码率需要的信噪比减小量称为编码增益。

6.1.4 差错控制的基本方式和能力

Any Questions！