第7-8章-分组码和卷积码

1、第七第七-八章八章 分组码和卷积码分组码和卷积码1线性分组码线性分组码卷积码卷积码信道编码原理：信道编码原理：只要只要 R C，就存在一种编译码方式能够实现在，就存在一种编译码方式能够实现在 R 的速率下传输信的速率下传输信息，而且误码率还能够任意小。息，而且误码率还能够任意小。但是，这里只证明了存在性，并没有给出如何实现！但是，这里只证明了存在性，并没有给出如何实现！即使是随机编码的方式，也只能在编码长度无穷大时才能够获得任即使是随机编码的方式，也只能在编码长度无穷大时才能够获得任意小的误码率！意小的误码率！7.1 基本定义基本定义2基本概念：基本概念：u 由一组固定长度的码字矢量组成。由一

2、组固定长度的码字矢量组成。 码长码长矢量元数的个数矢量元数的个数 n。u 码字元素选自由码字元素选自由q个元素组成的字符集（二进制分组码，非二进个元素组成的字符集（二进制分组码，非二进制分组码）制分组码）长度为长度为n的码字的码字2n个码字个码字k个信息比特个信息比特2k种组合种组合(n, k) 码码映射映射nkRc u 信息比特与码字之间的关系信息比特与码字之间的关系码率：码率：7.1 基本定义基本定义3有限域，也称伽罗华域（有限域，也称伽罗华域（Galios Field）：二进制加法和乘法）：二进制加法和乘法的有限集合。的有限集合。+01001110X010001011. 基域：基域：mq

3、p GF(50, 1, 2, 3, 4 ) )模模 5 的加法和乘法运算的加法和乘法运算扩域：扩域：mqp 2. 有限域上的多项式：有限域上的多项式：2012()mmg Xgg Xg Xg X GF( )igp 首一（首一（Monic）多项式：）多项式：1mg 既约多项式：多项式无法写成两个低次多项式的乘积。既约多项式：多项式无法写成两个低次多项式的乘积。22+1(1)XX 7.1 基本定义基本定义43. 扩域：本原多项式扩域：本原多项式GF(4)域的加法和乘法：域的加法和乘法：2+1XX +01XX+1001XX+1110X+1XXXX+101X+1X+1X10 x01XX+10000010

4、1XX+1X0XX+11X+10X+11X2=1XX 7.1 基本定义基本定义54. 本原元和本原多项式本原元和本原多项式GF(2m) )mg(X)2X2+X+13X3+X+14X4+X+15X5+X+16X6+X+17X7+X+18X8+X4+X3+X2+19X9+X4+110X10+X3+111X11+X2+112X12+X6+X4+X+17.2 线性分组码的一般性质线性分组码的一般性质6任何码字都是任何码字都是 G 的矢量的矢量 的线性组合：的线性组合：生成矩阵和奇偶校验矩阵生成矩阵和奇偶校验矩阵假设：假设：k个信息比特个信息比特码字（码字（n位）位）编码运算：编码运算：矩阵形式：矩阵形

5、式：j = 1, nG 生成矩阵生成矩阵mumcGmmcu kjmkjmjmmjgxgxgxc 2211 ig11221kmmiimmmkkicu gugugug knkknnggggggggg212222111211k21gggG7.2 线性分组码的一般性质线性分组码的一般性质7(n, k) 线性码的对偶码线性码的对偶码l是一种是一种 (n, n-k) 线性码，有线性码，有 2n-k 个码矢量个码矢量l生成矩阵生成矩阵 H，由，由 n-k 个线性无关的码矢量组成个线性无关的码矢量组成由于对由于对(n, k)码的每个码字都成立，于是：码的每个码字都成立，于是：(n, k)码码(n, k) 码任

6、意一个码字码任意一个码字 Cm 都正交于矩阵都正交于矩阵H的每一行的每一行l对偶码对偶码 (n, n-k)正交于正交于l H矩阵用于译码器检查收到的码字矩阵用于译码器检查收到的码字 c 是否满足是否满足 cHt = 0H 矩阵称为矩阵称为 (n,k) 码的一致校验矩阵码的一致校验矩阵 （简称校验矩阵）（简称校验矩阵）c H0tm GH0t 7.2 线性分组码的一般性质线性分组码的一般性质87.2.2 线性分组码的重量和距离特性线性分组码的重量和距离特性l 码字的重量：码字里非零码元的数量码字的重量：码字里非零码元的数量l 码字间的汉明距离：两个码字间不同码元的个数码字间的汉明距离：两个码字间不

7、同码元的个数l 码的最小距离码的最小距离l 线性分组码的最小重量与奇偶校验矩阵列之间的相关性有关线性分组码的最小重量与奇偶校验矩阵列之间的相关性有关( )w c1212min12,min(,)c cC ccdd c c l 码的最小重量码的最小重量min,0min( )c C cww c 7.2 线性分组码的一般性质线性分组码的一般性质97.2.3 重量分布多项式重量分布多项式l 码的重量分布多项式（码的重量分布多项式（WEP）：）：多项式的系数是该码字中不同重量的码字的个数多项式的系数是该码字中不同重量的码字的个数l对于正交对于正交 FSK 调制有调制有l 假设发送的是全零码字，则对于假设发

8、送的是全零码字，则对于 BPSK 调制有调制有2E()4()mbcmdsR w c min0()1nniiiiii dA ZA ZA Z2E()2()mbcmdsR w c 7.2 线性分组码的一般性质线性分组码的一般性质107.2.4 线性分组码的差错概率线性分组码的差错概率l 码字差错概率：码字差错概率：定义定义min020( )mmmnecicCi dcPPA P i 01Y(|0) (|)minciimiiyPp yp yc Y=(|0) (|1)yp yp y ()02=( ()mmw ccmPP w c min(21)dkeP 7.3 一些特殊的线性分组码一些特殊的线性分组码117

9、.3.1 重复码重复码： (n, 1) 码，全码，全0 或者全或者全11/cRn mindn 7.3.2 汉明汉明 (n, k) 码码：2121mcmmR 21, 21mmnkm (1)/2(1)/21()(1)(1)(1)1nnnA ZZnZZn 7.3.3 最大长度码最大长度码：汉明码的对偶码：汉明码的对偶码21, )mm （1()1(21)mmA ZZ 7.3.4 Reed-Muller码码：min02 , , 2rmm rimnkdi 7.4 线性分组码的最佳软判决译码线性分组码的最佳软判决译码12有效码字间的最佳检测，如相关度量计算有效码字间的最佳检测，如相关度量计算jcjrn 主要

10、问题：码字数量巨大，导致计算量巨大主要问题：码字数量巨大，导致计算量巨大1( ,)(21)nmmmjjjCMC r ccr min0/(21)cbR dNkePe 7.5 线性分组码的硬判决译码线性分组码的硬判决译码13先逐个码元进行判决后，再进行译码先逐个码元进行判决后，再进行译码1. 最小距离（最大似然）译码最小距离（最大似然）译码判决后的码字可能不是一个有效码字，寻找与该码字距离最小判决后的码字可能不是一个有效码字，寻找与该码字距离最小的有效码字作为译码的结果的有效码字作为译码的结果2. 伴随式和标准阵列伴随式和标准阵列mycettsyHeH 7.5.2. 硬判决译码硬判决译码min(1

11、)/ 2td纠错能力：纠错能力：7.6 硬判决与软判决译码的性能比较硬判决与软判决译码的性能比较147.7 线性分组码最小距离的边界线性分组码最小距离的边界157.7.1 辛格尔顿（辛格尔顿（Singleton）界）界：min1dnk 7.7.2 汉明界汉明界：min(1)/22011logdcinRni 7.7.3 普洛特金（普洛特金（Plotkin）界）界：对于：对于 q 元，元，1min1kkkdqqnq 1min221kkdn 对于对于 二进制，二进制，7.8 修改的线性分组码修改的线性分组码167.8.1 缩短和伸长缩短和伸长7.8.2 删余和扩展删余和扩展7.8.3 删信和增广删信

12、和增广7.9 循环码循环码17l循环码循环码是线性码的一个子集。是线性码的一个子集。 码字码字码字码字 C 的所有循环移位都是码字的所有循环移位都是码字循环码的码字多项式表示：循环码的码字多项式表示： n-1次多项式，用它与码字次多项式，用它与码字 C 联系起来联系起来特点：特点：若两边同乘若两边同乘 X：Xc(X) 除于除于 Xn+1：其中：其中：代表码字：代表码字：c1(X) 是是Xc(X)除于除于Xn+1的余式，因此：的余式，因此： 0121 Cccccnn 121210()nnnnc XcXcXc Xc 121210()nnnnXc XcXcXc Xc X (1)1()()11nnnX

13、c XCXcXX 1122301()nnnnncXcXcXc Xc （）12301 nnnccccc （）1()() mod1nc XXc XX7.9 循环码循环码18l 生成多项式生成多项式111()1n kn kn kg XXgXg X l 信息多项式：长度为信息多项式：长度为k121210()kkkku XuXuXu Xu l 码字多项式：长度为码字多项式：长度为n()() (), 1,2,2kmmcXuX g Xm 生成多项式生成多项式 g(X) 必须是必须是 Xn+1 的因式，例如的因式，例如323+1(1)(1)(1)nXXXXXX 系统循环码：系统循环码：-()()()()()n

14、 kXu Xr XQ Xg Xg X()()()n kc XXu Xr X 7.9 循环码循环码19l 循环码编码器：移位寄存器循环码编码器：移位寄存器l 循环码的译码循环码的译码7.10 BCH码码7.11 RS码码uBCH码的生成多项式由码的生成多项式由 的因式构成的因式构成特点：特点：u循环码的一个大类循环码的一个大类 ； （二进制，非二进制）（二进制，非二进制）u二进制二进制BCH码：码：m 和和 t 是任意正整数，是任意正整数， u非二进制非二进制BCH码：包括码：包括Reed-Solomon码码12 mnmtkn 12min td3 m112 mp8.1 卷积码的构造卷积码的构造2

15、0l二进制数据移位输入到编码器，沿着移存器每次移动二进制数据移位输入到编码器，沿着移存器每次移动 k 比特；比特；l每个每个 k 比特长的输入序列对应一个比特长的输入序列对应一个 n 比特长的输出序列；码率比特长的输出序列；码率 Rc=k/nlK（移存器的级数）称为卷积码的约束长度。（移存器的级数）称为卷积码的约束长度。编码器由编码器由 K 级移存器（每级级移存器（每级 k 比特）和比特）和 n 个模个模2加法器组成加法器组成编码过程：编码过程：卷积码的描述方法：树图、网格图、状态图卷积码的描述方法：树图、网格图、状态图8.2 卷积码的译码卷积码的译码21卷积码译码卷积码译码l卷积码没有固定长

16、度，有记忆，采用序列译码；卷积码没有固定长度，有记忆，采用序列译码；l译码器是一个最大似然序列估计器；译码器是一个最大似然序列估计器；l译码过程：搜遍网格图找出最可能的序列译码过程：搜遍网格图找出最可能的序列l译码度量：硬判决译码度量：硬判决汉明距离；软判决汉明距离；软判决欧氏距离欧氏距离8.3 二进制卷积码的距离特性二进制卷积码的距离特性228.9 Turbo码和迭代译码码和迭代译码23l编码器结构：编码器结构：由两个并联的卷积编码器组成，第由两个并联的卷积编码器组成，第2级编码器前串接了一个交织器级编码器前串接了一个交织器交织器：信息比交织器：信息比特进入下一级编特进入下一级编码器之前对它

17、们码器之前对它们重新排序重新排序对二进制卷积编码器输出的校对二进制卷积编码器输出的校验比特进行删余处理，目的是验比特进行删余处理，目的是为了提高码率为了提高码率带交织的并行级联卷积码带交织的并行级联卷积码 Turbo8.9 Turbo码和迭代译码码和迭代译码24特色之一：特色之一：两个编码器与交织结合的效果：两个编码器与交织结合的效果：使码字变得相对稀疏，即各码字极少有离它很靠近的邻码。使码字变得相对稀疏，即各码字极少有离它很靠近的邻码。交织导致紧邻码字数量的减少，由此使编码增益提高。交织导致紧邻码字数量的减少，由此使编码增益提高。已经证明，当交织器长度为已经证明，当交织器长度为 N 时，紧邻

18、码字的数目减少时，紧邻码字的数目减少 N 倍倍特色之二：特色之二：使用基于使用基于MAP准则的迭代译码准则的迭代译码8.9 Turbo码和迭代译码码和迭代译码25Turbo码的性能码的性能l影响影响Turbo码性能的一个重要因素码性能的一个重要因素交织长度（交织增益）交织长度（交织增益）l大交织产生的问题：译码时延；计算复杂大交织产生的问题：译码时延；计算复杂带交织的串行级联卷积码带交织的串行级联卷积码 1998年年 Benedetto另一种级联卷积码另一种级联卷积码在低误码率时，具有比并行级联码更好的性能在低误码率时，具有比并行级联码更好的性能使用足够大的交使用足够大的交织器，采用织器，采用

19、MAP迭代译码迭代译码Turbo码的性能码的性能可以非常接近可以非常接近Shannon限限8.11 LDPC码码26LDPC码：具有稀疏校验矩阵的线性分组码码：具有稀疏校验矩阵的线性分组码LDPC码的硬译码和软译码码的硬译码和软译码8.12 网格编码调制网格编码调制TCM27背景背景l分组码和卷积码：性能的改善是通过扩大传输信号带宽为分组码和卷积码：性能的改善是通过扩大传输信号带宽为代价而获得的；代价而获得的；l这种情况主要适用于功率受限信道的设计。这种情况主要适用于功率受限信道的设计。如如 (24, 12) Golay码：码： 当当 b=10 时，编码增益时，编码增益=5dB 但这个编码增益

20、以传输信号带宽增大但这个编码增益以传输信号带宽增大1倍而获得。倍而获得。l采用软判决译码的二进制采用软判决译码的二进制 (n, k) 分组码，与不编码系统相比，分组码，与不编码系统相比，所得到的性能改善约为：所得到的性能改善约为：如何解决带限信道的编码问题？如何解决带限信道的编码问题？要求：不扩展带宽而获得编码增益。要求：不扩展带宽而获得编码增益。dB )/2lnlog(10minbckdR 8.12 网格编码调制网格编码调制TCM28分析分析： （假设一次传输假设一次传输 2 个比特的情况）个比特的情况）编码编码要使编码后与不编码要使编码后与不编码QPSK具有具有同样的数据吞吐量同样的数据吞

21、吐量l不编码系统：不编码系统：QPSK ，4个点的信号星座个点的信号星座 ，每个符号携带，每个符号携带 2 比特比特l采用采用 2/3 的编码系统：的编码系统：必须必须结合如结合如8PSK的调制使用的调制使用2信息比特信息比特3编码比特编码比特l引出的问题：引出的问题： 与与QPSK星座相比，要保持相同的星座相比，要保持相同的Pe ，8PSK星座要求的信星座要求的信号功率必须增加号功率必须增加4dB！如何补偿由于信号集扩大而产生的这种要求？如何补偿由于信号集扩大而产生的这种要求？8.12 网格编码调制网格编码调制TCM29两种解决方案：两种解决方案：l按照传统的方法按照传统的方法 编码与调制分

22、别独立设计编码与调制分别独立设计u通过增大编码符号间的最小欧氏距离来弥补信号集扩大造成通过增大编码符号间的最小欧氏距离来弥补信号集扩大造成的损失。的损失。u要求编码器必须提供要求编码器必须提供 4 dB以上的编码增益才能补偿这一要求。以上的编码增益才能补偿这一要求。 u措施：措施： 通过采用大约束长度的卷积码，大分组长度的分组码。通过采用大约束长度的卷积码，大分组长度的分组码。l编码与调制结合在一起设计编码与调制结合在一起设计 网格编码调制的核心思想网格编码调制的核心思想l编码调制集成的关键：编码调制集成的关键：找到一种有效的办法，将编码比特映射到信号点集，而使最小找到一种有效的办法，将编码比

23、特映射到信号点集，而使最小欧式距离最大。欧式距离最大。8.12 网格编码调制网格编码调制TCM30途径：分集映射途径：分集映射l分集：分集： 遵循遵循“最小欧氏距离逐级增大最小欧氏距离逐级增大”的原则的原则第第1次分集：分为次分集：分为2个子集，每子集个子集，每子集4点，点，第第2次分集：两个子集又进一步划分，次分集：两个子集又进一步划分，最后一次分集得到最后一次分集得到8个子集，每个子集仅包含个子集，每个子集仅包含一个信号点一个信号点8PSK：各点间相隔的最小欧氏距离为：各点间相隔的最小欧氏距离为：将信号星座分割成子集，使子集中两个信号点之间的最将信号星座分割成子集，使子集中两个信号点之间的

24、最小欧氏距离随着每次分集变大。小欧氏距离随着每次分集变大。 765. 0)22(8sin20 d 21 d 22 d8.12 网格编码调制网格编码调制TCM31l每次子集隔点选取每次子集隔点选取l对矩形信号星座而言，每一级分集可使最小欧氏距离增加对矩形信号星座而言，每一级分集可使最小欧氏距离增加 倍。倍。l第一次分集后，点间距离从第一次分集后，点间距离从 增加到增加到16QAM信号星座的分集信号星座的分集 2 2222/1 iidd8.12 网格编码调制网格编码调制TCM32编码过程：编码过程：l 映射（编码）映射（编码）k2个未编码比个未编码比特用来在各子特用来在各子集中选择某一集中选择某一

25、信号点。信号点。信息输入信息输入m比比特分为两路特分为两路从编码器得出的从编码器得出的n比特用来选择子比特用来选择子集（在分集后信集（在分集后信号星座的号星座的2n个子个子集中选择其一）集中选择其一）k1k28.12 网格编码调制网格编码调制TCM33分两步实现：分两步实现：译码译码 （软判决译码）（软判决译码）l子集译码子集译码确定每一子集中的最佳信号点；确定每一子集中的最佳信号点； （即确定每个子集中离接收信号点最近的点）（即确定每个子集中离接收信号点最近的点）l路径译码路径译码 将每个子集选出的信号点及相应的平方距离量度对应到将每个子集选出的信号点及相应的平方距离量度对应到Viterbi算法的分支中，在网格图中找出一条信号路径，该算法的分支中，在网格图中找出一条信号路径，该路径与接收信号序列的距离平方之和最小。路径与接收信号序列的距离平方之和最小。8.12 网格编码调制网格编码调制TCM34性能性能 （网格编码调制所能获得的编码增益一览）（网格编码调制所能获得的编码增益一览）码率为码率为1/2，一维，一维PAM调制时：调制时：当当 Pe 在在 10-610-8 范围时，范围时，128状态可获得状态可获得 5.8dB 的编码