第7章-信道编码技术.ppt

1、第8章 信道编码技术,信号源,信源编码,信道编码,载波调制,载波解调,信源解码,显示装置,信道解码,数字声音,附加数据,传输通道,加性噪声 干扰、多径,数字声音,附加数据,通信系统的基本构成,信道,通信系统主要性能指标,通信系统性能指标涉及要素 有效性：传输信息的速度，传输一定信息所占资源（带宽和时间）； 可靠性：通信传输质量； 适应性：使用的环境条件； 经济性：系统的成本； 标准性； 维修性、工艺性、保密性。 从信息传输的角度看，有效性和可靠性是矛盾的主要方面。,通信系统主要性能指标,模拟通信系统的性能指标 有效性度量： 系统的频带利用率 可靠性指标： 接收端最终输出信噪比 数字通信系统的性

2、能指标 传输速率和频带利用率 传输速率可分为码元传输速率和信息传输速率两种。,通信系统主要性能指标,码元传输速率 (RB) 又叫符号速率，它表示单位时间(每秒)内 传输的码元(符号)的数目。其单位为波特，常 用B表示。简称波特率。 码元速率、数码率、传码率、波特率、波 形速率、调制速率。,例：某数字通信系统2s内传送3600个码元， 其码元速率为1800B。,通信系统主要性能指标,码元宽度或码元周期TB 相邻两个码元发送的时间间隔 TB=1/RB 信息传输速率(Rb) 又叫信息速率，它表示单位时间(每秒)内传送数据信息的比特数。其单位为比特/秒，记为bit/s，或bps。 信息传输速率与码元速

3、率的关系： 若采用N进制传输，则信息速率与码元速率之间的关系为: Rb=RBlog2N （b/s）,通信系统主要性能指标,频带利用率 单位频带的传输速率,例：某数字通信系统在3s内输出3600个码元， 采用4进制传输，则信息速率为2400bps.,通信系统主要性能指标,误码率 在传输过程中错误接收的码元数与传输的总码元数之比。,误信率（误比特率） 在传输过程中错误接收的比特数与传输的总比特数之比。,对于二进制数字通信系统，,信道,信道的定义： 以传输媒介为基础的信号通道 狭义信道的定义和分类： 仅指信号传输媒介的信道称为狭义信道； 分类： 无线信道 有线信道 广义信道 包含有关的“转换器” ，

4、如天线，调制器、解调器等。,信道,广义信道的分类 调制信道：从调制器的输出端到解调器的输入端 编码信道：从编码器的输出端到译码器的输入端,狭义信道 有线或无线传输媒介,调制信道,编码信道,信道,1、对称电缆（双绞线）,对称电缆结构图,有线信道,2、同轴电缆,同轴电缆结构图,信道,信道,3、光纤 光纤传输原理 全反射原理 多模光纤（MMF）和单模光纤（SMF） 光源 LED（Light Emitted Dioxide） 激光 光纤中的色散 限制了光纤的无中继传输距离,第三传输窗口,第二传输窗口,第一传输窗口,1300,1550,850,紫外吸收,红外吸收,瑞利散射,0.2,2.5,损 耗 (dB

5、/km),波长 (nm),光纤损耗谱特性,OH离子吸收峰,光纤带宽： 1300nm窗口约100nm， 1550nm窗口约100nm， 共200nm，约30THz,信道,信道,无线信道,电磁波传播特性 影响电磁波传播的因素 大气：电离层、雨雪、空气粒子等 地面：良导体、地面弯曲等 地波传播 电磁波波长与电离层距离地面的高度相比拟，形同波导； ELF、VLF、LF、MF主要使用的传播方式 ELF具有一定的海水穿透能力。,1969年，威斯康辛州建WTF台，十字型天线，各长22.5公里，300A；,1981年，密歇根州又建MTF台，天线各长45公里，150A；,1986年，WTF/MTF台正式投入使用

6、，共指挥161艘潜艇。,美国超长波对潜通信系统,威斯康辛州,密歇根州,信道,天波传播 HF使用的主要传播方式； 主要特点：电离层随机扰动、多径效应。,Multi hop,single hop,信道,视距传播 天线高度与传输距离之间的关系,平坦地面条件下，收发天线高度分别为50m，则视线距离为50km。,信道,对流层散射,无线光传输 红外光、紫外光、激光,信道,微波中继信道,信道,卫星中继信道,信道,陆地移动信道 1）传播衰减：移动信道中自由空间传播损耗,信道,2）反射波与散射波 移动信道的传播路径和平滑表面反射,信道,短波电离层反射信道,短波电离层反射信道是利用地面发射的无线电波在电离层，或电

7、离层与地面之间的一次反射或多次反射所形成的信道。 电离层离地面60600km。当频率范围为330MHz（波长为10100m）的短波（或称为高频）无线电波射入电离层时，由于折射现象会使电波发生反射，返回地面。,信道,电离层反射示意图,信道,多径形式示意图,信道,调制信道的主要特性 绝大部分信道是线性的，即满足叠加原理； 信号通过信道需要经过一定的延时； 信道对信号有损耗（固定或时变损耗）； 有一对或多对输入端，必然有一对或多对输出端； 即使没有信号输入，接收端仍有信号输出（噪声），通常称为加性噪声或加性干扰。,信道,信道对信号的影响：,1、乘性干扰k(t)的影响 2、加性干扰n(t)的影响,二对

8、端的调制信道模型：,把f()设想成一个信号与干扰相乘的形式,信道,乘性干扰k(t) 包含的因素：线性失真、非线性失真、时间延迟以及衰减等； 随时间变化的特性； 调制信道的分类 恒参信道：k(t)不随时间变化或变化极为缓慢；有线信道通常可以看成恒参信道。 随参信道：k(t)随时间t随机变化；移动无线信道为随参信道。,信道,信道模型 （1）加性噪声恒参信道,信道,（2）具有加性噪声的线性滤波信道,信道,（3）加性噪声线性时变滤波信道模型,信道,编码信道包括调制器、解调器和传输媒介 调制信道使调制信号发生波形变化 编码信道对信号的影响是数字序列的变换 与调制信道的关系 解调发生的差错 编码信道模型

9、采用数字信号的转移概率来描述,信道,信道,信道容量：是指信道中信息能够无差错传输的最大速率。 说明：本节讨论的是调制信道（或称波形信道，它是指从发射机调制器输出端到接收机解调器输入端之间的信道）的信道容量。,信道,香农公式 对于带宽有限，平均功率有限的高斯白噪声连续信道，设信道带宽为B (Hz)，信道输出信号功率为S (W)，输出加性高斯噪声功率为N (W)，则可以证明该信道的信道容量为,令加性高斯噪声的单边功率谱密度为 ，则,信道,例：已知黑白电视图像信号每帧有30万个像素，每个像素有8个亮度电平，各电平独立等概出现，图像每秒发送25帧，若要求接收图像信噪比达到30dB，求所需最小带宽。 解

10、：首先计算每个像素的信息量： 每帧图像的信息量为 每秒传输25帧所需传输速率,信道,信道容量必须不小于所要求的信息传输速率。代入信道容量公式得到 得到所需最小带宽,(1)增加尽可能少的数据率而可获得较强的检错和纠错能力，即编码效率高，抗干扰能力强 (2)对数字信号有良好的透明性，也即传输通道对于传输的数字信号内容没有任何限制 (3)传输信号的频谱特性与传输信道的通频带有最佳的匹配性；,8.1 信道编码概述,(4)编码信号内包含有正确的数据定时信息和帧同步信息，以便接收端准确地解码； (5)编码的数字信号具有适当的电平范围； (6)发生误码时，误码的扩散蔓延小。,8.1 信道编码概述,其中，最主

11、要的可概括为两点：其一，附加一些数据信息以实现最大的检错纠错能力，这就涉及到差错控制编码原理和特性。其二，数据流的频谱特性适应传输通道的通频带特性，以求信号能量经由通道传输时损失最小，因此有利于载波噪声比(载噪比，C/N)高，发生误码的可能性小。,8.1 信道编码概述,8.1 信道编码概述,随机信道是指数据流在其中传输时会受到随机噪声的干扰，使高低电平的码元在信道输出端产生电平失真，导致接收端解码时发生码元值的误判决，形成误码。,(1) 随机信道,信道模型,传输通道中常有一些瞬间出现的短脉冲干扰，它们引起的不是单个码元误码，而往往是一串码元内存在大量误码，前后码元的误码之间表现为有一定的相关性

12、。,(2) 突发信道,信道模型,实际的传输通道通常不是单纯的随机信道或突发信道，而是二者兼有，或者以某个信道属性为主。,(3) 混合信道,信道模型,ARQ 方式是：发送端发出能够发现错误的码(检错码)，接收端译码器收到后，判断在传输中有无错误产生，并通过反馈信道把检测结果告诉发送端。发送端把接收端认为有错的消息再次传送，直到接收端认为正确接收为止。 应用ARQ方式必须有一条从收端至发端的反馈信道。,(1) 反馈重发(ARQ，自动重发请求)方式,差错控制编码方式,FEC 方式是发送端发送有纠错能力的码（纠错码），接收端收到这些码后，通过纠错译码器自动地纠正传输中的错误。 优点是不需要反馈信道；能

13、进行一个用户对多个用户的同时通信，特别适合于移动通信；译码实时性较好，控制电路也比较简单。 缺点是译码设备较复杂；编码效率较低。,(2) 前向纠错(FEC)方式,差错控制编码方式,HEC 方式是上述两种方式的结合。发端发送的码既能检错、又有一定的纠错能力。收端译码时若发现错误个数在码的纠错能力以内，则自动进行纠错；若错误个数超过了码的纠错能力，但能检测出来，则通过反馈信道告知发方重发。这种方式在一定程度上避免了FEC方式译码设备复杂和ARQ方式信息连贯性差的缺点。,(3) 混合纠错(HEC)方式,差错控制编码方式,纠错码,随机误码纠错码,突发误码纠错码,分组码,卷积码,分组码,交织码,线性码,

14、非线性码,系统卷积码,非系统卷积码,比特交织码,字节交织码,循环码,非循环码,BCH码,RS码,奇偶校验码,汉明码,纠错码分类,纠错码分类,纠错码分类,信道编码的基本原理,香农的信道编码定理指出：对于一个给定的有扰信道，如果信道容量为C，只要发送端以低于C的信息速率R发送信息，则一定存在一种编码方法，使译码差错概率随着码长的增加，按指数规律下降到任意小的值。这就是说，通过信道编码可以使通信过程不发生差错，或者使差错控制在允许的数值之下。,信道编码的检错和纠错能力,信道编码的检错和纠错能力是通过信息量的冗余度来换取的。为了便于理解，先通过一个简单的例子来说明。例如，要传送A和B两个消息，可以用一

15、个二进制码元来表示一个消息，比如“0”码代表A， “1”码表示B。在这种情况下，若传输中产生错码，即“0”错成“1”，或“1”错成“0”，接收端将无法检测到差错，因此，这种编码没有检错和纠错能力。,如果用两个二进制码元来表示一个消息，有4种可能的码字，即“00”、 “01”、“10”和“11”。比如规定“00”表示消息A， “11”表示消息B。码字“01”或“10”不允许使用，称为禁用码字，对应地，用来表示消息的码字称为许用码字。如果在传输消息的过程中发生一位错码，则变成禁用码字“01”或“10”，译码器就可判决为有错。这表明在信息码元后面附加一位监督码元以后，当只发生一位错码时，码字具有检错

16、能力。但由于不能判决是哪一位发生了错码，所以没有纠错能力。,编码中的几个定义,纠错码按照检错纠错功能的不同分类，可分为检错码、纠错码和纠删码三种。 纠错码按照误码产生原因的不同，可分为纠随机误码的纠错码和纠突发误码的纠错码两种。前者应用于主要产生独立性随机误码的信道，后者应用于易产生突发性局部误码的信道。,纠错码分类,1.奇偶校验码,9.低密度校验码(LDPC),8.Turbo码,7.分组交织和卷积交织,2.线性分组码,3.循环码,4.BCH码,5.RS码,6.卷积码和维特比(Viterbi)译码,信道编码技术种类,编码定理,香农第二定理阐述了当信息传输率小于信道容量时，通过增加码长可以降低平

17、均错误概率，并且根据随机编码思想对定理进行了证明，但是并没有给出构造好码的具体方法，而随机编码面临编码和译码的困难。,主要编码技术,线性分组码：概念比较简单，但十分重要，特别是有关生成矩阵和校验矩阵的表示和相互之间的关系，以及校验矩阵与纠错能力之间的关系尤其重要。 卷积码，卷积码的码字之间具有相关性，可以利用这种相关性进行译码，从而取得好的效果。,线性分组码,(n，k）线性分组码为系统码的结构,线性分组码的编码,在介绍线性分组码的原理之前，首先我们来看一种简单而又常用的线性分组码奇偶监督码（也称为奇偶校验码），分为奇数监督码和偶数监督码。无论信息码元有多少，监督码元只有一位。在偶数监督码中，监

18、督码元的加入使得每个码字中“1”的数目为偶数；在奇数监督码中，监督码元的加入使得每个码字中“1”的数目为奇数。,线性分组码,将需要传输的信息分割为等长的信息组，然后将每组中的信息映射为长度固定码字； 码字是由长度固定的矢量集合构成； 组与组之间独立编码；,信息组1,信息组2,信息组n,码字1,码字2,码字n,二元码：码字的元素取自于具有q个符号的符 号集，当符号集只有两个元素0，1时， 称为二元码，每个码字的元素称为比特 ； 非二元码：码字元素取值于q（q2）个元素 的符号集；,线性分组码,（n,k）码 ：从 种可能码字选择 种作为编码使用的码字； 码率 : R=k/n; 码字的重量:码字所包

19、含的非0元素的个数 每个码字都有自己的重量，一个码字的所有重量集合构成该码的重量分布。 当所有M个码字具有相同重量时，该码称为等重量码。,线性分组码,举例,比如对于（7，4）码，R4/7; 对于其中的一个码字（1101011），其重量为5； 假设码字为 （0 0 0 0 0 0 0 ），（0 0 0 1 1 0 1 ）， （0 0 1 1 0 1 0 ），（0 0 1 0 1 1 1 ）， （0 1 1 0 1 0 0 ），（0 1 1 1 0 0 1 ）， （0 1 0 1 1 1 0 ），（0 1 0 0 1 1 1 ）， （1 1 0 1 0 0 0 ），（1 1 0 0 1 0 1 ）

20、， （1 1 1 0 0 1 0 ），（1 1 1 1 1 1 1 ）， （1 0 1 1 1 0 0 ），（1 0 1 0 0 0 1 ）， （1 0 0 0 1 1 0 ） ， （1 0 0 1 0 1 1） 重量分布为（0，3，3，4，3，4，4，4，3，4，4，7，4，3，3，4，）,8.1 线性分组码,有限域的运算,加法规则： 1.加法运算是闭的， 2.加法运算满足结合律 3.加法运算满足交换律 4.集合F包含一个称为0的元素，满足 5. 每个元素都有一个负元素，如果b是一个元素，其负元素记作b，两个元素减法运算定义为,8.1 线性分组码,乘法,乘法运算是闭的； 乘法运算满足结合律

21、乘法运算满足交换律 乘法对加法运算满足分配律 集合中的每个元素都有一个单位元素1，满足 除0之外，每个元素都有一个逆元，两个元素的除法运算定义为,8.1 线性分组码,线性分组码的码字都是由有限个元素的域构造的，这种域称为有限域，也称为伽罗华域(Galois Field); 每个域都至少有一个0元素和一个1元素 ； 最简单的域就是GF(2);,8.1 线性分组码,负元素每行、每列只有一个,逆元素每行、每列只有一个,负元素,逆元素,8.1 线性分组码,一般说来，有限域是由素数或者素数的幂构造的。 当是素数时，加法、乘法都是基于模q的算术运算。 如果q=pm ，可以将域扩展为GF(pm)，此时称 G

22、F(pm)为GF(p)的扩域，扩域元素的加法、乘法运算都是基于p模的。,8.1 线性分组码,分组码的基本特点,Dij:码字之间差异的一种测度是两个码字之间的汉明距离; 任何码字集合一定存在最小汉明距离； 分组码分为线性和非线性的； 设Ci,Cj是分组码中的两个码字，并令 表示 取值于符号集合的两个元素。当且仅当 也是一个码字时，称为线性码。 线性码必须包含全0码字; 等重量码是非线性的。,8.1 线性分组码,假设为全0码字,即 ，同时wi用表示第个码字的重量，于是得到第i个码字与第1个码字之间的汉明距离为 wi; 对于线性分组码而言，两个码字之差仍然是一个码字，所以两个码字之间的汉明距离就是另

23、外一个码字的重量；所以码字重量分布完全描述了码的距离特性，码的最小距离为,8.1 线性分组码,线性分组码的讨论经常使用线性代数的许多基本概念，特别是所有n重集合形成一个矢量空间; 从S空间中选取kn个线性独立的子集，并构造出所有矢量的线性组合的集合，所产生集合形成S的k维子空间Sc ; 任何k个线性独立的矢量集合构成空间Sc的一组基。 考虑中的矢量集合，它们与Sc的基中任何矢量都是正交的，这个矢量集合也是的一个子空间，称为的零空间 ； 如果的维数为k，零空间的维数应当为n-k。,8.1 线性分组码,对于二元分组码 矢量空间是由2k个二元值的n重构成的 ; 线性码（n,k）是2k个n重的集合，所

24、有码字构成二元域子空间 Sc; Sc中共有2k个码字， Sc的基底有k个码字，这就是说需要2k个线性独立的码字去构造种线性组合，从而产生整个码。 Sc的零空间是另一种线性码，它是由码长为n，信息比特数为n-k的2n-k个码字所组成。,8.1 线性分组码,k比特信息的矢量表示形式为,8.1.1 生成矩阵和校验矩阵,线性分组码的编码可以用下列方程表示,该方程组表示为矩阵形式为,其中称为该码的生成矩阵,任何码字都是G的行矢量,的线性组合,8.1.1 生成矩阵和校验矩阵,gj必须是(n,k)码的基底。 由于n维空间的基矢量不是唯一的，G也不是唯一的，G的秩就是子空间的维数k; (n,k)码的任何生成矩

25、阵都可以通过行运算化为系统形式,8.1.1 生成矩阵和校验矩阵,系统形式生成矩阵所产生的线性分组码，其每个码 字的前k比特与k比特信息总是相同的，而剩余的n-k 是k比特信息的线性组合，所以这样产生的n-k比特 称为校验位。 系统矩阵产生的(n,k)分组码称为系统码。,码的生成矩阵为,例8.1,假设编码的信息位为,8.1.1 生成矩阵和校验矩阵,生成矩阵产生的码字表示为,3比特校验位为,8.1.1 生成矩阵和校验矩阵,使用移位寄存器实现方法,8.1.1 生成矩阵和校验矩阵,线性(n,k)都存在对偶码; 对偶码共有2n-k个码矢量; 对偶码是(n,n-k)的线性分组码，生成矩阵用 H表示 ； 每

26、个码字都是从零空间中选取，所以有,将,代入,8.1.1 生成矩阵和校验矩阵,所以校验矩阵H为,对于二元码，其中的负号可以去掉，因为模2加法 与模2减法是一样的 。,例8.2 对于由例8.1的生成矩阵产生的系统(7,4)码 根据校验矩阵与生成矩阵之间关系可以得到矩阵H为,8.1.1 生成矩阵和校验矩阵,可以得到三个校验方程,8.1.1 生成矩阵和校验矩阵,由于最小重量等于其最小距离d0 ，可以知道H的行 矢量与d0是相关的，换句话说，H中不存在大于d0- 1列向量是线性独立。 由于H的秩最大为n-k，所以有,所以最小距离满足,如果校验矩阵的任意d0-1列都是线性无关，则汉明距 离为d0 。,8.

27、1.1 生成矩阵和校验矩阵,例如，校验矩阵H为,有2列线性无关，所以d0=3,8.1.1 生成矩阵和校验矩阵,扩展码,设线性二进制码的最小距离为d0，通过给每个码字 追加1比特校验位，可以构造一个二进制(n+1,k)码， 该校验位通常用作对码字中所有比特进行检验， 如果原始码字中有偶数个1，附加比特为0；反之， 附加比特为1。结果是，如果(n,k)码的最小重量或者 最小距离为奇数，附加的校验位增加了一位重量。 我们称该(n+1,k)码为(n,k)码的扩展码，校验矩阵为,码为,其中H是原始 码的校验矩阵,8.1.1 生成矩阵和校验矩阵,假设原始码字为（Cm1Cm2Cmn）,那么扩展码应当为（Cm

28、1Cm2CmnCm(n+1)），根据CHeT0，最后一列为 Cm1Cm2CmnCm(n+1)0。 由此可见，增加的校验位就是进行奇偶校验。,8.1.1 生成矩阵和校验矩阵,码的缩减,令l位信息位为0，则一个线性系统码可以缩短，也就是说，由k比特信息位和n-k比特校验位的系统分组码可以缩短为(n-l,k-l)线性码。,缩短后的(n-l,k-l)码共有2n-l个码字，其最小距离 至少与原始(n-l,k-l)相同。,8.1.2 一些特殊的线性分组码1.汉明码,特点：,取m位二进制所有非0组合排列构成校验矩阵； 根据生成矩阵与校验矩阵之间的关系得到生成 矩阵；,。,当m3时，就是(7,4)码。,由于校

29、验矩阵包含除了全0列矢量以外的所有n重，所以通过置换一定可以得到具有下列形式的校验矩阵,汉明码,根据生成矩阵和校验矩阵之间的关系，可以得到,二进制汉明码的最小汉明距离为d03,举例,例8.3 构造的汉明码 解：根据汉明码的性质可知：,汉明码,除了矢量0之外的所有排列为(001)，(010)，(011)，(100)，(101)， (110)，(111)。为了产生系统码，将(100)，(010)，(001)放在矩阵的最后3列，得到校验矩阵为,汉明码,系统形式,于是得到生成矩阵为,由于汉明码的校验矩阵中没有两列是线性相关的， 而总可以找到三列是线性相关的，所以汉明码的 最小距离为3。,8.1.3 循

30、环码,循环码是线性分组码子集； 码字C的循环移位都是码字 ； 循环特性允许在编码、译码中使用具有众多结构的码字 ； 在通信系统中实现具有大量码字的长码 。,汉明码,定义多项式,对于二进制码，多项式的每个系数为0或者1,现在将上述的多项式两边同乘因子p得到多项式,该多项式阶次等于n，不能表示码字,等式两边同除多项式pn1，,码字,由C循环移位一次得到。,类似地,对应一个码字,循环码的生成多项式是pn1的因子，具有下列通用形式,定义信息多项式,表示k比特信息,可以表示一个码字,例8.4 讨论长度n7的循环码。,可以取下列两个多项式之一作为生成多项式,具体产生过程如下：假设4比特信息为(0001)，

31、对应的信息多项式为x1(p)=1,所以码字多项式为,码字,当4比特信息为（0010）时，对应的信息多项式为 x(p)=p,码字多项式为,一般说来，多项式pn+1可以总是可以分解两个多项式之积,其中g(p)表示循环码的生成多项式，而则h(p)为校验多项式，其阶数为k，所以使用可以产生相应的对偶码。,定义的倒数多项式为,例8.5 讨论由例8.4 的循环码的对偶码。,解：例8.4使用下列多项式产生循环码,BCH码、RS码,二进制BCH的参数满足下列关系：,RS码也是循环码的一种，实际上属于BCH码的一个子类，其参数特性如下,码长 校验位 最小汉明距离为,表示进制数，即生成多项式项数。生成多项式为,其

32、中,为本原多项式的根,线性分组码的硬判决译码,误码元率很小时，最大似然译码可以简化为最小汉明距离译码，简称汉明距离译码； 一般的二元信道总是对称的，而误码元率一般都很小 ； 汉明距离译码是一种硬判决译码，需要逐个比较接收码字与各种可能码字的对应码元，选择汉明距离最小的码字作为译码估值 。,硬判决译码,硬件译码最简单的思路： 将接收序列Y与所有可能个码字逐个进行相减，找到所有具有最小汉明距离的码字，然后挑选一个码字作为译码估值即可。 对于二元码，Y与码字Ci运算得到的差错矢量中1的个数就是汉明距离。 硬判决译码更为有效的方法是利用校验矩阵 。,假设传输的码字为Cm，接收的码字为Y，则有,1硬判决

33、译码,其中,表示任意二进制差错矢量,由于CmHT0，于是,S称为差错图样的伴随式，是一个n-k的矢量; 如果接收矢量是编码码字，则S=0； 反之，如果Y不是编码码字，则为非全0矢量。,差错矢量共有2n可能差错图样，但是只有2n-k可能伴随式; 结果是不同的差错图样具有相同的伴随式。 e与S之间是多对一的映射，而不是一一映射，所以出现译码错误在所难免; 对于在纠错能力范围的差错，应当保证译码的唯一性。,1硬判决译码,S的维数为(n-k),e的维数为n，所以方程 S=eHT的解不是唯一的； 满足方程的解共有2k个，译码器只能挑选一个码字作为估计值； 挑选的原则：最小错误概率，当误码元率一定时，选择

34、所有解中最小重量的差错矢量作为估计值。,1硬判决译码,例8.10 利用生成多项式g(p)=p3+p+1构造的(7,4) 循环码的校验矩阵为,假设接收码字为(1001101),计算对应的伴随式， 并求出满足伴随式的差错图样,解：伴随式为,1硬判决译码,1硬判决译码,对于二元对称信道，假设码元错误概率为 pe,一个码字的n位码元中出现一位码元错误的概率为,出现 位错误的概率为,一般情况下，pe较小，所以l约大，错误概率越小； 择选择重量最小的作为估值是合理的。 由于e=C+Y，e 的重量最小就是C、Y之间的最小汉明距离，所以这种译码方式实际就是最小汉明译码，也是最大似然译码。,1硬判决译码,存在的

35、问题： 每接收一个码字译码器都要计算出伴随式，然后在解方程组找到重量最小的。 对于二元方程组，合理的解法是将所有可能取值代入方程SeHT，找到满足条件的解。 计算量太大； 简化方法 ： 伴随式取值只有种可能，且其值可以根据直接计算。 对于给定的S，可以根据最小汉明距离译码方法，事先确定一个唯一的差错图样与之对应，就可以按照所有的取值构造一个标准阵列译码表 ，然后查表得到译码估计值,标准阵列译码表的构造,(1) 确定各个伴随式唯一的差错图样 ； 即根据S的每种取值，求解方程SeHT 选取满足方程的、重量最小的e作为估值 ； S有2n-k种取值 ,得到每个S对应的e； (2)确定标准阵列的首行和首

36、列 ; 将编码使用的码字排列在第1行，相当于 e=0; 按照重量顺序将Si对应的ei作为首列 ;,1硬判决译码,(3)令阵列的第i行、第j列排列为ei+Cj，从而得到的阵列译码表。,1硬判决译码,3种译码方法,(1)直接搜索 直接在水平、垂直两个方向对译码表进行二维搜索，然后沿 着阵列的列找到对应的编码码字，将其作为译码输出。 不足：当n较大时，搜索量太大，从而降低译码速度 。 (2)首先计算伴随式S，根据伴随式的值确定接收码字所在行，沿着该行逐个搜索各个元素，找到对应的列，将该列的第S个元素作为译码输出。这种译码方式达到减少了搜索量，但是需要计算伴随式的值。 特点：计算伴随式，减小搜索量,1

37、硬判决译码,一种方法不需要构造译码表，其实现方法是计算伴随式的值S，同时确定所对应的差错图样 ，译码输出为 。 只要码元错误超出纠错能力，无论如何译码都会产生译码错误。 译码错误是无法避免的； 只是这种译码方法平均错误概率最小。,1硬判决译码,1硬判决译码,1硬判决译码,循环码的伴随式译码,循环码的伴随式译码,8.4 卷积码,分组码特点小结 分组码是将信息划分为组; 各个信息组单独进行信道编码，即按照一定规则增加一定的冗余，使得编码输出的码字具有检错或者纠错能力; 结合相应的差错控制方式实现信息的有效传输。 从信息论角度而言，信息流分割为独立码块不能利用组间之间的相关信息； 且编码定理表明分组

38、码的码长越长越好，而译码运算量却随着码长的增加而增加。,卷积码的特点 信息组之间不是独立编码的，而是具有一定的相关性； 系统译码时可以利用这种相关性进行译码。 为了表示这种关联性，卷积码一般表示为(n,k,m)，其中k为信息组的长度，n表示每组信息对应输出的码长度，而m是表示信息组关联的一个参数，称为信息组约束长度。,8.4.1 卷积码编码及描述方式,移位寄存器组对输入信息移位，原来最低位置的信息移往 下一个寄存器组，最后一个寄存器组的信息移出。 移位操作结束后，编码器输出寄存器内容运算的结果，经过n节拍即可输出编码器当前编码的码字。,卷积码的矢量描述,如同分组码一样，卷积码编码器可以用生成矩

39、阵加以描述。 由于输入序列是半无限的，卷积码的生成矩阵也是半无限的。 这种描述方式并不很简洁。 采用一个矢量来代替生成矩阵，矢量中的1表示对应寄存器内容参与模2加法运算，而0表示对应寄存器内容不参与摸2加法运算，这样n位编码输出只需要n个矢量即可; 每个矢量由m*k个元素构成，表示共有m*k位寄存器内容与指定模2加法器之间的连接关系。,(3,1,3)卷积码,函数生成器,根据函数生成器和移位寄存器的内容就可以得出当前编码输出码字。 假设移位寄存器的原始状态为(000)，输入序列为(1010)，编码过程为,1.首位输入1，寄存器状态变为(100),编码输出码字为C0=(111),(2)第2位信息0

40、输入后，移位寄存器内容为(010)，编码输出分别为,所以编码输出码字为C1=(001) . 同理可以得到C2=(100),C3=(001),还可以使用树图、格图和状态图来描述卷积码,树图,格图,卷积码的状态图,编码输出,状态转移,输入为1,输入为0,维特比译码,利用码字之间相关性； 码字自身的冗余进行有效。 编码过程可以看作是一个m阶的马尔可夫随机过程,或者,码序列的状态表示,由于卷积码可以用m阶马尔可夫链表示，所以可以使用状态来表示编码输出码字序列； 对于一个输出码序列Ci，总存在唯一的一个状态序列Si与之相对应 。 对于卷积码编码而言，每个码字序列是从全零状态出发最后回到全零状态，这就需要

41、在信息序列编码结束后，人为补充m组全零信息，使编码状态归0。,卷积码的另外一种理解,卷积码也可以理解为：每个码序列都是从全零状态出发，经过格图上的不同分支，最后回到全零状态的一条路径； 那么卷积码的译码实际就是找到这条编码路径。,假设接收序列为 根据最大后验概率译码准则，将接收序列译码为对于所有的i，使得概率 最大的码字Ci。 当输入符号服从独立同一分布、信道是无记忆的条件下，等效于对,进行判决。,考虑到码字序列Ci与状态序列Si之间的一一对应关系，有,上述概率可以表示为,两边同时取对数,定义,为第 支路的长度或者路径值，那么最大后验概率译码就等效为在格图上找到一条从全零状态出发，经过 条分支

42、后回到全零状态的最短路径值,如果输入是服从独立同一的等概率分布，对于所有的i而言，概率 是相等的,将最大后验概率译码简化为最大似然译码，并且对,进行最小判决译码。,对于二元对称信道，经过推导可以得出,码字序列与接收序列之间距离最小的路径就是最短路径。这样将概率译码简化为硬判决的最小汉明距离译码。,维特比译码寻找的是最短路径，而不是简单地求解上述极值问题 ； 格图中的每个节点就是表示一种状态，当前时刻编码结束时，下次编码使用的状态就确定下来，由于下次编码输入只有k位信息，所以该状态2k对应的分支共有个分支 ； 实际上，新状态的可能数量为2(m-1)k ，并不是所有这些状态都与当前状态连接的，剩余

43、的2(m-1)k -2k新状态与当前状态之间不能构成支路。,对于上图所示的(3,1,3)卷积码而言，假设当前状态为(00)，下一个状态只能是(00)、(10)两种，这两种状态能够与原状态构成支路。但是可能状态除了上述两种之外还有(01)、(11)，它们与状态之间不可能构成支路。,维特比译码时的总路径并不是简单将各个时刻的码字与对应的接收码字之间的距离进行累加，从而找出其中的最小值; 这种译码没有利用前后码字之间的关联性进行译码，与卷积码的编码思想不一致，所以是错误的。,对于每个可能状态，将从到的最短路径，称为第时刻的留存路径。 留存路径是从初始状态开始到当前状态的最近的路径，是累计值。 根据第

44、l时刻的幸存路径很容易计算出第(l+1)时刻的留存路径。 从格图上看，每个状态都有个可能的留存路径通过增加一条支路到达第时刻的某个指定状态，从中可以选择其中最短的路径作为该状态的留存路径。,如果出现多个路径长度相等，任意选择其中一个即可。 采用递推方法持续计算各个时刻的幸存路径，直到信息编码结束，然后选择m个全零分支结束递推运算。,具体算法,(1) 初始化 、 、 ； (2) 对于每个可能的状态，计算 记录从并使得上式最小的链接（即对应的输 入信息组的取值）；且令 (3) 如果 ，令 并且返回(2)；否则结束。 (4) 从 时刻的状态出发，反向搜索幸存路径，并且记录相应的信息组输入取值，得到接

45、收码字对应的译码输出。,例8.12 如图8.6所示的所示的卷积码，设信息序列为，编码格图如图8.10所示，对应的码字序列为。码字序列经过BSC传输后，接收序列为(111,001, 101,001,111,000)，试对接收序列进行维特比译码。,a:00,b:01,c:10,d:11,0,编码输出,000,111,接受码字,汉明距离,3,1,111,0,0,111,1,000,001,2,反向搜索得到译码输出,当码字序列长度较大时，如果等到计算完所有的状态再进行统一译码会造成译码延时太大，不利于信息实时处理； 可以分段进行译码也能构取得好的译码效果，所以反向搜索不是必需的。 如果码字序列长度不是

46、太大时，进行统一译码效果更好。,删余卷积码,经常需要使用高码率的卷积码，如码率 R=(n-1)/n; 直接对高码率卷积码进行译码的译码器实现复杂度很高 ； 既能够实现高码率的编码，同时又能避免高复杂度译码是可以实现的，方法就是从低码率的码字中删除一些码元 ； 在卷积码编码器输出端删除事先确定的码比特的方法称为删余,通过对1/n卷积码删余可以产生高码率的卷积码，同时保持1/n卷积码相同的译码低复杂度; 卷积码删余减小了自由距离，减小量取决删余程度。,周期删余,假设原始码率为1/n，而删余周期为Pc，对应编码器的Pc个输入，在一个周期内，编码器输出个nPc编码比特，矩阵表示为,矩阵元素pij如果为

47、0，则对应编码比特不输出；否则编码输出。,可达码率,其中,，N表示从nPc中删除n位输出,码率匹配删余卷积码(RCPC),部分信息比其它部分的信息更重要，需要增加更多的冗余保证这些信息的有效传输。 信息集合需要进行不均等错误保护，更重要的比特信息传输需要加入更多的冗余。 实现方法就是对同一种卷积码使用不同的删余矩阵进行删余。 删余矩阵的选择应当满足各种码率要求,这样产生的码成为码率匹配删余卷积码(RCPC).,将RCPC码应用于需要进行不均等错误保护的系统，需要对信息比特进行打包，将具有不同码率的信息组合在一起，然后按照码率的先后顺序进行排列，从而形成一帧数据，每种数据的长度是知道的，以便进行

48、译码器进行正确译码。,删余卷积码编码是通过删除部分编码比特实现的。 当采用维特比译码算法进行译码时，状态跳转过程所产生的码字使用对应的删余矩阵向量进行删余处理，而保持其它步骤不变即可实现译码。 或者说根据删余后的格图进行维特比译码。 对于RCPC也是如此，只是不同时刻的序列译码使用不同删余矩阵而已。,TCM码，级联码,通信系统中，调制解调器与纠错编译码器是两个主要的组成部分，分别是提高通信系统的信息传输速率和降低误码率的关键设备。 纠错码需要增加一定冗余来保证信息的有效传输，纠正信息传输过程出现的误码，冗余增加必然会降低信息传输速率。 如果将两种设备单独考虑进行设计，为了提高信息传输速率，就需

49、要增加信道带宽或者提高信号发送功率。,网格编码调制(TCM)将编码技术与调制技术结合起来，利用状态记忆和分集映射来增加码序列之间的距离。 不需要增加信道带宽或者信号传输功率，而是利用信号集空间的冗余提高信息传输效率。,网格编码调制一般由3个部分组成： (1) 差分编码: 与后续的映射相结合，避免接收端译码时的信号集相位混淆问题； (2) 卷积编码: 将m比特编码为m+1比特； (3) 分集映射器: 将m+1比特一一映射2m+1到个点信号集上。,输入信息b(n)经过一个差分编码器后，产生序列Y2(n)，其目的就是为了防止产生相位混淆 (或者模糊)；其作用与通信原理中的差分编码一样,另一路输入信息

50、a(n)一方面送往码率的卷积码编码器进行编码，产生两位输出 Y1(n) Y0(n)。 分集映射器的三路输入包含了两位信息，共有8种组合可以进行PSK调制，星座与输入信息之间并不是一一对应关系，映射关系应当以卷积码状态转移作为基础。,而送往分集映射器的三位信息Y2Y1Y0中, Y0(n)的实际就是卷积码状态S0,所以系统的输出码字就是 由于y2是卷积码的输出，整个编码系统的状态只有4种，而分集映射器的输入为三位，这样就会造成无论y2的取值如何，状态都会从一个状态跳转到另一个由卷积码编码器确定的状态，即状态转移路径增加了，从而造成平行状态转移 。,平行状态转移会影响卷积码的自由距离，系统从全零状态

51、出发又回到全零状态的距离的路径与全零路径的最小距离的路径不可能大于平行转移的距离， 并行转移对应的一组码字应当距离越大越好，对于调制而言就是使得欧氏距离越大越好，为此将8PSK对半地进行分集，使得每个子集具有大的欧氏距离，并且将并行转移的一组码字映射为对称的点上，从而保证并行转移具有最大的欧氏距离，这就是分集映射。,级联码,在信道特性一定情况下，为了得到差错概率小的好码，就需要增加码的长度，而且增加码长可以增加随机性。 无论是线性分组码还是卷积码，编码实现都比较简单，但是对于最佳译码或者最大似然译码两种最常用的方法而言，译码复杂度都是与信息长度或者码长成指数关系，所以采用直接增加码长的方法不是

52、一种有效办法，必要找到既能够增加码长同时又具有较低译码复杂度的方法。 有效方法就是利用短码拼接成长码，使得拼接后的码字具有短码的译码复杂度和长码的性能，这种编码方法就是级联码。,串行级联码,编码码率为R1R2，最小汉明距离为d1d2,级联码的内码常用卷积码，而外码则常用分组码,由于维特比译码是序列译码，一旦译码出错则整个序列都出现错误，相当于产生一个突发错误。 如果内码采用卷积码，那么外码应当采用纠错能力足够强的分组码，使得卷积码产生的绝大多数错误能够被纠正，常用的外码是RS码。 卷积码为内码的级联码适合高斯白噪声信道，因为卷积码属于纠随机错误码，如果将这种级联码用于突发错误信道，则需要在调制

53、器与编码器之间增加交织器 。,交织器可以将突发信道产生的突发错误分散到各个码字中，即将突发错误随机化，从而有利于进行纠错。,乘积码,8.4 Turbo码LDPC,Turbo码和LDPC 都是接近香农极限的码； 1993年提出的Turbo码实际上是级联码研究的重要成果，其编码采用并行级联码； 对一组信息进行交织后产生两组或者两组以上的校验序列，从而形成整个码字； 而译码算法采用迭代译码，每次迭代译码都采用软输入、软输出译码，通过反复迭代运算提高了译码增益，从而取得好的误码率性能。 无论是在高斯白噪声信道还是在衰落信道中，Turbo码都能够取得好的误码率性能。,LDPC（即低密度校验码）是另一种能

54、够逼近香农极限的码，是由Gallager于20世纪60年代提出的，由于受到条件的限制，并没有受到人们的重视。 后来随着Turbo码的发展，人们重新对其进行广泛、深入研究，在编译码方面已经取得了重要进展。 实际上，LDPC是线性分组码，其生成矩阵和校验矩阵都是稀疏矩阵； 理论上，LDPC的译码可以采用线性分组码的译码算法，不过大多采用和积算法以取得好的误码率性能。,尽管Turbo码和LDPC的译码具有很高的复杂度，但是超大规模技术可以实现实时译码，满足用户要求。 这两种码在空间通信，特别是深空通信中得到了应用，如在新的火星探测器（MRO）上美国就采用LDPC和Turbo码进行差错控制编码，信息传输率为12Mb