信道编码技术

信道编码技术第一页，共一百四十六页，2022年，8月28日目录1.线性分组码

1.1生成矩阵和校验矩阵

1.2一些特殊的线性分组码

1.3循环码

1.4BCH码、RS码

1.5线性分组码的硬判决译码

2.卷积码第二页，共一百四十六页，2022年，8月28日

2.4删余卷积码7.3TCM码，级联码7.4Turbo码和LDPC第三页，共一百四十六页，2022年，8月28日香农第二定理解决的问题与不足1、解决的问题阐述了当信息传输率小于信道容量时，通过增加码长可以降低平均错误概率，并且根据随机编码思想对定理进行了证明。2、不足没有给出构造好码的具体方法，而随机编码面临编码和译码的困难。第四页，共一百四十六页，2022年，8月28日本章主要内容1、线性分组码：

-生成矩阵和校验矩阵的表示和相互之间的关系。

-校验矩阵与纠错能力之间的关系。2、卷积码，卷积码的码字之间具有相关性，可以利用这种相关性进行译码，从而取得好的效果。

第五页，共一百四十六页，2022年，8月28日7.1线性分组码

特点：1、将需要传输的信息分割为等长的信息组，然后将每组中的信息映射为长度固定码字；2、码字是由长度固定的矢量集合构成；3、组与组之间独立编码；

信息组1信息组2……信息组n码字1码字2……码字n第六页，共一百四十六页，2022年，8月28日(n,k)线性分组码的数学定义定义（n,k)线性分组码是有限域GF(q)上的n维线性空间Vn中的一个k维子空间Vn,k。由于该线性子空间在加法运算下构成阿贝尔群，所以线性分组码又称为群码。当q=2时，为2元码，码字取自集合｛0，1｝当q>2时，非2元码，码字取自集合｛0,1,…q-1}线性分组码一个码字用(cn-1,cn-2,…,c1,c0)表示，且第七页，共一百四十六页，2022年，8月28日二元（n,k）码：从种可能码字选择种码字作为编码使用的码字；码率:R=k/n;码字的重量:码字所包含的非0元素的个数每个码字都有自己的重量，一个码字的所有重量集合构成该码的重量分布。当所有M个码字具有相同重量时，该码称为等重量码。第八页，共一百四十六页，2022年，8月28日举例比如对于（7，4）码，R＝4/7;对于其中的一个码字（1101011），其重量为5；假设码字为（0000000），（0001101），（0011010），（0010111），（0110100），（0111001），（0101110），（0100111），（1101000），（1100101），（1110010），（1111111），（1011100），（1010001），（1000110），（1001011）重量分布为（0，3，3，4，3，4，4，4，3，4，4，7，4，3，3，4，）7.1线性分组码第九页，共一百四十六页，2022年，8月28日有限域线性分组码的码字都是由有限个元素的域构造的，这种域称为有限域，也称为伽罗华域(GaloisField);每个域都至少有一个0元素和一个1元素；0、1两个元素安模2加、模2乘构成域GF(2).第十页，共一百四十六页，2022年，8月28日有限域的加法1.加法运算是闭合的，2.加法运算满足结合律3.加法运算满足交换律4.集合F包含一个称为0的元素，满足

(加法恒等元）5.每个元素都有一个负元素，如果b是一个元素，其负元素记作－b，两个元素减法运算定义为

(加法逆元）7.1线性分组码阿贝尔群第十一页，共一百四十六页，2022年，8月28日有限域的乘法

乘法运算是闭合的乘法运算满足结合律乘法运算满足交换律乘法对加法运算满足分配律集合中的每个元素都有一个单位元素1，满足

（乘法恒等元）除0之外，每个元素都有一个逆元，两个元素的除法运算定义为（乘法逆元）7.1线性分组码阿贝尔群第十二页，共一百四十六页，2022年，8月28日+01001110·010001017.1线性分组码GF（2）加法GF（2）乘法第十三页，共一百四十六页，2022年，8月28日+01234001234112340223401334012440123·01234000000101234202413303142404321负元素每行、每列只有一个逆元素每行、每列只有一个负元素逆元素GF（5）加法GF（5）乘法第十四页，共一百四十六页，2022年，8月28日如果q=pm

，p为素数，可以将域扩展为GF(pm)，此时称GF(pm)为GF(p)的扩域扩域元素的加法、乘法运算都是基于p模的。

7.1线性分组码扩域第十五页，共一百四十六页，2022年，8月28日分组码的有关概念汉明距离dij:对于(n,k)分组码，两个码字之间的码字之间不同码元的个数，满足最小汉明距离d0：7.1线性分组码第十六页，共一百四十六页，2022年，8月28日线性空间和子空间

1、线性空间平面上二维矢量的全体构成一个二维的矢量空间；空间中，三维矢量的全体构成一个三维的矢量空间；域F上的n重元素集合V满足：（1）V关于加法构成阿贝尔群；（2）数乘封闭对有（3）分配律对有（4）结合律对有第十七页，共一百四十六页，2022年，8月28日2、子空间若子集，且满足线性空间的条件，则称V1是V的子空间。3、“张成”的概念线性空间V的每一矢量，可由其中的一组矢量集S’中的矢量线性组合而成，则称S’张成了矢量空间V.4、在任何线性空间中，能张成该空间的线性独立矢量的集合，称为该线性空间的基底。该组线性独立的矢量的数目为该线性空间的维数。5、矢量正交两个矢量a、b的内积a.b=0,则矢量互为正交。第十八页，共一百四十六页，2022年，8月28日所有n重（码字）集合形成一个矢量空间Vn;从S空间中选取k（<n）个线性独立的子集，并构造出所有矢量的线性组合的集合，所产生集合形成S的k维子空间Sc(=Vn,k);任何k个线性独立的矢量集合构成空间Sc的一组基。S中的矢量集合，它们与Sc的基中任何矢量都是正交的，这个矢量集合也是的一个子空间，称为的零空间；如果Sc的维数为k，零空间的维数应当为n-k。线性分组码与线性空间第十九页，共一百四十六页，2022年，8月28日对于二元分组码（n,k)：矢量空间是由2k个二元值的n重构成的;线性码（n,k）是2k个n重的集合，所有码字构成二元域子空间

Sc;Sc中共有2k个码字，Sc的基底有k个，这就是说需要k个线性独立的码字去构造2k种线性组合，从而产生整个码。Sc的零空间是另一种线性码，它是由码长为n，信息比特数为n-k的2n-k个码字所组成。第二十页，共一百四十六页，2022年，8月28日对于（7，4）码，矢量空间由24=16个长为7的码字构成，构成2元域子空间V7,4这16个码字的基底有4个，需要4个线性独立的码字去构成16种线性组合，产生16个码字。（7，4）码的零空间是另一组线性分组码(7，3)，码长为7，信息比特数为3.第二十一页，共一百四十六页，2022年，8月28日线性码的几个性质1、线性码必须包含全0码字(任何域包含0，任何基底乘以0，得0矢量)2、等重量码是非线性的。（码不可能全0）第二十二页，共一百四十六页，2022年，8月28日最小汉明距离与码字重量由（n,k)线性分组码的数学定义，由于是群码，有：C1是（n,k)分组码的一个码字C2是（n,k)分组码的一个码字C1+C2是（n,k)分组码的一个码字C1与C2的距离码字(C1+C2)的重量最小汉明距离为重量最小的非0码字第二十三页，共一百四十六页，2022年，8月28日举例对于右图的码字表，码字（1010011）和码字（1101001），距离为4，它是码字（0111010）的重量。非0码字的最小重量为4，最小距离d0=4信息组码字00000000000010011101010010011101101110101001001110101101001111011010011111110100(7,3)码的码字表第二十四页，共一百四十六页，2022年，8月28日k比特信息的矢量表示形式为7.1.1生成矩阵和校验矩阵

线性分组码的编码码元可以用下列方程表示该方程组表示为矩阵形式为第二十五页，共一百四十六页，2022年，8月28日其中G称为该码的生成矩阵

任何码字都是G的行矢量的线性组合

7.1.1生成矩阵和校验矩阵

{gj}必须是(n,k)码的基底。由于n维空间的基矢量不是唯一的，G也不是唯一的，G的秩就是子空间的维数k;第二十六页，共一百四十六页，2022年，8月28日(n,k)码的任何生成矩阵都可以通过行运算化为系统形式。系统形式生成矩阵所产生的线性分组码，其每个码字的前k比特与k比特信息位总是相同的，而剩余的n-k

是k比特信息的线性组合，这样产生的n-k比特称为校验位。系统矩阵产生的(n,k)分组码称为系统码。系统形式的生成矩阵与系统码第二十七页，共一百四十六页，2022年，8月28日码的生成矩阵为例7.1

假设编码的信息位为

第二十八页，共一百四十六页，2022年，8月28日生成矩阵产生的码字表示为

3比特校验位为

7.1.1生成矩阵和校验矩阵

比如对于信息位（0001），计算的3为校验位为011，对应的码字为0001011如果计算所有码字，将信息位0000~1111分别计算得16个码字。所有非0码字中，重量最小的码的重量即最小距离。第二十九页，共一百四十六页，2022年，8月28日使用移位寄存器实现方法7.1.1生成矩阵和校验矩阵

第三十页，共一百四十六页，2022年，8月28日1、线性码(n,k)都存在对偶码（零空间上的码字）;2、对偶码共有2n-k个码矢量;3、对偶码是(n,n-k)的线性分组码，生成矩阵用H表示；4、每个码字都是从零空间中选取，所以有将代入

校验矩阵H，因Xm是任意K维矢量，第三十一页，共一百四十六页，2022年，8月28日所以校验矩阵H为：对于二元码，其中的负号可以去掉，因为模2加法与模2减法是一样的。例7.2

对于由例7.1的生成矩阵产生的系统(7,4)码，根据校验矩阵与生成矩阵之间关系可以得到矩阵H为生成矩阵G为：第三十二页，共一百四十六页，2022年，8月28日可以得到三个校验方程

译码器可以根据矩阵去检验接收到的序列Y是否满足条件;称矩阵H为(n,k)码对应的校验矩阵是合理的.

设码字

由第三十三页，共一百四十六页，2022年，8月28日定理：（n,k)线性分组码有最小距离d0

的充要条件为，H矩阵任意d0-1列线性无关。如果校验矩阵的任意d0-1列都是线性无关，则最小汉明距离为d0

。（此定理为构造各类码的基础，交换H各列不影响码的最小距离）d0的界：由于H的秩最大为n-k，所以有所以最小距离满足码字的校验矩阵

与其最小距离的关系第三十四页，共一百四十六页，2022年，8月28日例如，校验矩阵H为任意2列线性无关，所以d0=37.1.1生成矩阵和校验矩阵

第三十五页，共一百四十六页，2022年，8月28日扩展码设C是最小距离为d0的二进制(n,k)线性分组码，它的码字有奇数重量，也有偶数重量。对每一个码字增加一个校元，满足原码字重量为奇数，加上全校验元（1）后，重量变为偶数，码长增加一位；原码字重量为偶数，加上全校验元（0）后，重量不变，码长增加一位；码字变为（n+1,k)，增加校验元为了进行奇偶校验。第三十六页，共一百四十六页，2022年，8月28日若原码的校验矩阵为H,扩展码的校验矩阵为(7,4,3)汉明码，附加一个全校验位变为（8,4,4）扩展汉明码。(7,4,3)汉明码的H矩阵第三十七页，共一百四十六页，2022年，8月28日缩短码在某些情况下，如果找不到合适的码长或信息位个数，可把某（n,k,d)码缩短。在(n,k,d)码字中，挑选前i位均为0的所有码字，组成新子集，组成了(n-i,k-i,d)分组码，称为（n,k,d)码的缩短码。00000000011101010011101110101001110101001111010011110100组成（6，2，4）缩短码000000011101100111111010（7，3，4）码第三十八页，共一百四十六页，2022年，8月28日缩短码的G矩阵只要在原(n,k,d)码去掉左边i列和上边i行；H矩阵只要在原码的H矩阵去掉第一列；缩短码的纠错能力至少与原(n,k,d)码相同，码率要小，总的看来，性能比原码差。第三十九页，共一百四十六页，2022年，8月28日7.1.2一些特殊的线性分组码

特点：取m位二进制所有非0组合排列构成校验矩阵；根据生成矩阵与校验矩阵之间的关系得到生成矩阵；。当m＝3时，就是(7,4)码。1.汉明码第四十页，共一百四十六页，2022年，8月28日由于校验矩阵包含除了全0列矢量以外的所有n重，所以通过置换一定可以得到具有下列形式的校验矩阵汉明码

根据生成矩阵和校验矩阵之间的关系，可以得到二进制汉明码的最小汉明距离为d0＝3第四十一页，共一百四十六页，2022年，8月28日举例例7.3构造m=3的汉明码解：根据汉明码的性质可知：汉明码

除了矢量0之外的所有排列为(001)，(010)，(011)，(100)，(101)，(110)，(111)。为了产生系统码，将(100)，(010)，(001)放在矩阵的最后3列，得到校验矩阵为第四十二页，共一百四十六页，2022年，8月28日汉明码

系统形式于是得到生成矩阵为

由于汉明码的校验矩阵中没有两列是线性相关的，而总可以找到三列是线性相关的，所以汉明码的最小距离为3。第四十三页，共一百四十六页，2022年，8月28日7.1.3循环码

循环码是线性分组码子集，有如下性质：（1）具有严谨的代数结构，性能易分析。已发现的大部分线性码可归结于循环码。（2）具有循环特性，编译码电路，特别是编码电路简单易于实现。第四十四页，共一百四十六页，2022年，8月28日循环码的定义定义：一个n重子空间若对任何一个恒有则称为循环子空间或循环码。第四十五页，共一百四十六页，2022年，8月28日码的多项式表示有限域GF(p)上所有n重构成一个线性空间Vn,其中每个矢量是分量取自GF(p)上的n重，将每个n重和系数取自GF(p)上的多项式对应：n重：多项式：它们之间建立了一一对应关系。对于GF(2),n重的ci取0或1.第四十六页，共一百四十六页，2022年，8月28日循环码与多项式对(n,k)循环码，码字的多项式表示它的循环右移一位的码字为对应的多项式为相当于f(p)乘以p后，用(pn-1)取模，二进制用(pn+1)取模。第四十七页，共一百四十六页，2022年，8月28日类似地对应循环码的一个码字第四十八页，共一百四十六页，2022年，8月28日剩余类线性结合代数所有次数小于n的多项式一定在模n次多项式

不同剩余类中，即因此，Vn中每一个n重都与GF(p)上的次数低于n次的一个多项式对应，并必在模F(x)的某一剩余类中。在模F(x)运算下，模F(x)的剩余类构成剩余类环。在环中定义一个数乘,模F(x)的剩余类构成n维线性空间，称为剩余类线性结合代数。第四十九页，共一百四十六页，2022年，8月28日定理以多项式xn-1为模的剩余类线性结合代数中，其一个子空间Vn.k是一个循环子空间（循环码）的充要条件是：Vn.k是一个理想。第五十页，共一百四十六页，2022年，8月28日代数结构1、群Abel群2、环Abel群,乘法封闭，乘法结合律，和乘之间有分配率3、域加法构成Abel群，乘法构成Abel群，加、乘之间有分配律有限域，0、1按模2加、模2乘构成域GF(2)第五十一页，共一百四十六页，2022年，8月28日4、子环环中的子集S,关于R中的代数运算也构成环，则称S是R的子环。5、理想是一类子环，定义：设R是交换环，I是R中的非空子集，若（1）对任意两个元素（2）对任意则称I是R中一个理想。由（1）知，I是一个Abel群由（2）知，I的某些元素都由某一元素a的倍数构成。第五十二页，共一百四十六页，2022年，8月28日6、主理想理想中的元素由一个元素的所有倍数及其线性组合构成，则称这个理想为主理想。7、生成多项式理想必是某一元素的倍数所构成。因此，至少可在理想中找到一个次数最低的非零首一多项式g(x),由它的一切倍式生成一个理想（循环码）。此多项式为生成多项式。首一多项式：最高次数为1的多项式。第五十三页，共一百四十六页，2022年，8月28日循环码的生成多项式定理

(n,k)循环码的生成多项式是pn＋1的因子，具有下列通用形式

定义信息多项式用表示k比特信息

用可以表示一个码字第五十四页，共一百四十六页，2022年，8月28日例7.4

讨论长度n＝7的循环码。可以取下列两个多项式之一作为生成多项式（生成(7,4)码，生成多项式最高次数7-4=3)具体产生过程如下：假设4比特信息为(0001)，对应的信息多项式为x1(p)=1,所以码字多项式为码字第五十五页，共一百四十六页，2022年，8月28日当4比特信息为（0010）时，对应的信息多项式为x(p)=p,码字多项式为第五十六页，共一百四十六页，2022年，8月28日对偶码一般说来，多项式pn+1可以总是可以分解两个多项式之积其中g(p)表示循环码的生成多项式，而则h(p)为校验多项式，其阶数为k，所以使用可以产生相应的对偶码。第五十七页，共一百四十六页，2022年，8月28日定义的倒数多项式为例7.5讨论由例7.4的循环码的对偶码。解：例7.4使用下列多项式产生循环码第五十八页，共一百四十六页，2022年，8月28日信息位码字0000000000000010010111001001011100011011100101001011100010110010110110111001001111100101第五十九页，共一百四十六页，2022年，8月28日1.4BCH码、RS码

二进制BCH的参数满足下列关系：RS码也是循环码的一种，实际上属于BCH码的一个子类，其参数特性如下码长校验位最小汉明距离为第六十页，共一百四十六页，2022年，8月28日表示进制数，即生成多项式项数。生成多项式为其中为本原多项式的根

第六十一页，共一百四十六页，2022年，8月28日线性分组码的硬判决译码误码元率很小时，最大似然译码可以简化为最小汉明距离译码，简称汉明距离译码；一般的二元信道总是对称的，而误码元率一般都很小；汉明距离译码是一种硬判决译码，需要逐个比较接收码字与各种可能码字的对应码元，选择汉明距离最小的码字作为译码估值。第六十二页，共一百四十六页，2022年，8月28日1．硬判决译码

硬件译码最简单的思路：将接收序列Y与所有可能个码字逐个进行相减，找到所有具有最小汉明距离的码字，然后挑选一个码字作为译码估值即可。对于二元码，Y与码字Ci运算得到的差错矢量中1的个数就是汉明距离。硬判决译码更为有效的方法是利用校验矩阵。第六十三页，共一百四十六页，2022年，8月28日假设传输的码字为Cm，接收的码字为Y，则有1．硬判决译码其中表示任意二进制差错矢量

由于CmHT＝0，于是S称为差错图样的伴随式，是一个n-k的矢量;如果接收矢量是编码码字，则S=0；反之，如果Y不是编码码字，则为非全0矢量。第六十四页，共一百四十六页，2022年，8月28日差错矢量共有2n可能差错图样，但是只有2n-k可能伴随式;结果是不同的差错图样具有相同的伴随式。e与S之间是多对一的映射，而不是一一映射，所以出现译码错误在所难免;对于在纠错能力范围的差错，应当保证译码的唯一性。1．硬判决译码第六十五页，共一百四十六页，2022年，8月28日S的维数为(n-k),e的维数为n，所以方程S=eHT的解不是唯一的；满足方程的解共有2k个，译码器只能挑选一个码字作为估计值；挑选的原则：最小错误概率，当误码元率一定时，选择所有解中最小重量的差错矢量作为估计值。1．硬判决译码第六十六页，共一百四十六页，2022年，8月28日例7.10利用生成多项式g(p)=p3+p+1构造的(7,4)循环码的校验矩阵为假设接收码字为(1001101),计算对应的伴随式，并求出满足伴随式的差错图样解：伴随式为1．硬判决译码第六十七页，共一百四十六页，2022年，8月28日1．硬判决译码第六十八页，共一百四十六页，2022年，8月28日对于二元对称信道，假设码元错误概率为pe,一个码字的n位码元中出现一位码元错误的概率为出现位错误的概率为一般情况下，pe较小，所以l约大，错误概率越小；择选择重量最小的作为估值是合理的。由于e=C+Y，e的重量最小就是C、Y之间的最小汉明距离，所以这种译码方式实际就是最小汉明译码，也是最大似然译码。1．硬判决译码第六十九页，共一百四十六页，2022年，8月28日存在的问题：每接收一个码字译码器都要计算出伴随式，然后在解方程组找到重量最小的。对于二元方程组，合理的解法是将所有可能取值代入方程S＝eHT，找到满足条件的解。计算量太大；简化方法：伴随式取值只有种可能，且其值可以根据直接计算。对于给定的S，可以根据最小汉明距离译码方法，事先确定一个唯一的差错图样与之对应，就可以按照所有的取值构造一个标准阵列译码表，然后查表得到译码估计值第七十页，共一百四十六页，2022年，8月28日标准阵列译码表的构造(1)确定各个伴随式唯一的差错图样；即根据S的每种取值，求解方程S＝eHT选取满足方程的、重量最小的e作为估值；S有2n-k种取值,得到每个S对应的e；(2)确定标准阵列的首行和首列;将编码使用的码字排列在第1行，相当于e=0;按照重量顺序将Si对应的ei作为首列;1．硬判决译码第七十一页，共一百四十六页，2022年，8月28日(3)令阵列的第i行、第j列排列为ei+Cj，从而得到的阵列译码表。1．硬判决译码第七十二页，共一百四十六页，2022年，8月28日3种译码方法(1)直接搜索直接在水平、垂直两个方向对译码表进行二维搜索，然后沿着阵列的列找到对应的编码码字，将其作为译码输出。不足：当n较大时，搜索量太大，从而降低译码速度。(2)首先计算伴随式S，根据伴随式的值确定接收码字所在行，沿着该行逐个搜索各个元素，找到对应的列，将该列的第S个元素作为译码输出。这种译码方式达到减少了搜索量，但是需要计算伴随式的值。特点：计算伴随式，减小搜索量1．硬判决译码第七十三页，共一百四十六页，2022年，8月28日一种方法不需要构造译码表，其实现方法是计算伴随式的值S，同时确定所对应的差错图样，译码输出为。只要码元错误超出纠错能力，无论如何译码都会产生译码错误。译码错误是无法避免的；只是这种译码方法平均错误概率最小。1．硬判决译码第七十四页，共一百四十六页，2022年，8月28日1．硬判决译码第七十五页，共一百四十六页，2022年，8月28日1．硬判决译码第七十六页，共一百四十六页，2022年，8月28日循环码的伴随式译码

第七十七页，共一百四十六页，2022年，8月28日循环码的伴随式译码第七十八页，共一百四十六页，2022年，8月28日7.2卷积码

分组码特点小结分组码是将信息划分为组;各个信息组单独进行信道编码，即按照一定规则增加一定的冗余，使得编码输出的码字具有检错或者纠错能力;结合相应的差错控制方式实现信息的有效传输。从信息论角度而言，信息流分割为独立码块不能利用组间之间的相关信息；且编码定理表明分组码的码长越长越好，而译码运算量却随着码长的增加而增加。第七十九页，共一百四十六页，2022年，8月28日卷积码的特点信息组之间不是独立编码的，而是具有一定的相关性；系统译码时可以利用这种相关性进行译码。为了表示这种关联性，卷积码一般表示为(n,k,m)，其中k为信息组的长度，n表示每组信息对应输出的码长度，而m是表示信息组关联的一个参数，称为信息组约束长度。第八十页，共一百四十六页，2022年，8月28日7.2.1卷积码编码及描述方式移位寄存器组对输入信息移位，原来最低位置的信息移往下一个寄存器组，最后一个寄存器组的信息移出。移位操作结束后，编码器输出寄存器内容运算的结果，经过n节拍即可输出编码器当前编码的码字。第八十一页，共一百四十六页，2022年，8月28日卷积码的矢量描述如同分组码一样，卷积码编码器可以用生成矩阵加以描述。由于输入序列是半无限的，卷积码的生成矩阵也是半无限的。这种描述方式并不很简洁。采用一个矢量来代替生成矩阵，矢量中的1表示对应寄存器内容参与模2加法运算，而0表示对应寄存器内容不参与摸2加法运算，这样n位编码输出只需要n个矢量即可;每个矢量由m*k个元素构成，表示共有m*k位寄存器内容与指定模2加法器之间的连接关系。第八十二页，共一百四十六页，2022年，8月28日(3,1,3)卷积码函数生成器第八十三页，共一百四十六页，2022年，8月28日根据函数生成器和移位寄存器的内容就可以得出当前编码输出码字。假设移位寄存器的原始状态为(000)，输入序列为(1010)，编码过程为1.首位输入1，寄存器状态变为(100)编码输出码字为C0=(111)第八十四页，共一百四十六页，2022年，8月28日(2)第2位信息0输入后，移位寄存器内容为(010)，编码输出分别为所以编码输出码字为C1=(001).同理可以得到C2=(100),C3=(001)第八十五页，共一百四十六页，2022年，8月28日还可以使用树图、格图和状态图来描述卷积码

树图格图第八十六页，共一百四十六页，2022年，8月28日卷积码的状态图编码输出状态转移输入为1输入为0第八十七页，共一百四十六页，2022年，8月28日维特比译码

利用码字之间相关性；码字自身的冗余进行有效。编码过程可以看作是一个m阶的马尔可夫随机过程或者第八十八页，共一百四十六页，2022年，8月28日码序列的状态表示由于卷积码可以用m阶马尔可夫链表示，所以可以使用状态来表示编码输出码字序列；对于一个输出码序列Ci，总存在唯一的一个状态序列Si与之相对应。对于卷积码编码而言，每个码字序列是从全零状态出发最后回到全零状态，这就需要在信息序列编码结束后，人为补充m组全零信息，使编码状态归0。第八十九页，共一百四十六页，2022年，8月28日卷积码的另外一种理解卷积码也可以理解为：每个码序列都是从全零状态出发，经过格图上的不同分支，最后回到全零状态的一条路径；那么卷积码的译码实际就是找到这条编码路径。第九十页，共一百四十六页，2022年，8月28日假设接收序列为根据最大后验概率译码准则，将接收序列译码为对于所有的i，使得概率最大的码字Ci。当输入符号服从独立同一分布、信道是无记忆的条件下，等效于对进行判决。第九十一页，共一百四十六页，2022年，8月28日考虑到码字序列Ci与状态序列Si之间的一一对应关系，有上述概率可以表示为两边同时取对数第九十二页，共一百四十六页，2022年，8月28日定义为第支路的长度或者路径值，那么最大后验概率译码就等效为在格图上找到一条从全零状态出发，经过条分支后回到全零状态的最短路径值如果输入是服从独立同一的等概率分布，对于所有的i而言，概率是相等的第九十三页，共一百四十六页，2022年，8月28日将最大后验概率译码简化为最大似然译码，并且对进行最小判决译码。第九十四页，共一百四十六页，2022年，8月28日对于二元对称信道，经过推导可以得出码字序列与接收序列之间距离最小的路径就是最短路径。这样将概率译码简化为硬判决的最小汉明距离译码。第九十五页，共一百四十六页，2022年，8月28日维特比译码寻找的是最短路径，而不是简单地求解上述极值问题；格图中的每个节点就是表示一种状态，当前时刻编码结束时，下次编码使用的状态就确定下来，由于下次编码输入只有k位信息，所以该状态2k对应的分支共有个分支；实际上，新状态的可能数量为2(m-1)k

，并不是所有这些状态都与当前状态连接的，剩余的2(m-1)k-2k新状态与当前状态之间不能构成支路。第九十六页，共一百四十六页，2022年，8月28日对于上图所示的(3,1,3)卷积码而言，假设当前状态为(00)，下一个状态只能是(00)、(10)两种，这两种状态能够与原状态构成支路。但是可能状态除了上述两种之外还有(01)、(11)，它们与状态之间不可能构成支路。第九十七页，共一百四十六页，2022年，8月28日维特比译码时的总路径并不是简单将各个时刻的码字与对应的接收码字之间的距离进行累加，从而找出其中的最小值;这种译码没有利用前后码字之间的关联性进行译码，与卷积码的编码思想不一致，所以是错误的。第九十八页，共一百四十六页，2022年，8月28日第九十九页，共一百四十六页，2022年，8月28日对于每个可能状态，将从到的最短路径，称为第时刻的留存路径。留存路径是从初始状态开始到当前状态的最近的路径，是累计值。根据第l时刻的幸存路径很容易计算出第(l+1)时刻的留存路径。从格图上看，每个状态都有个可能的留存路径通过增加一条支路到达第时刻的某个指定状态，从中可以选择其中最短的路径作为该状态的留存路径。第一百页，共一百四十六页，2022年，8月28日如果出现多个路径长度相等，任意选择其中一个即可。采用递推方法持续计算各个时刻的幸存路径，直到信息编码结束，然后选择m个全零分支结束递推运算。第一百零一页，共一百四十六页，2022年，8月28日具体算法(1)初始化、、；(2)对于每个可能的状态，计算记录从并使得上式最小的链接（即对应的输入信息组的取值）；且令

(3)如果，令并且返回(2)；否则结束。(4)从时刻的状态出发，反向搜索幸存路径，并且记录相应的信息组输入取值，得到接收码字对应的译码输出。第一百零二页，共一百四十六页，2022年，8月28日

例7.12

如图7.6所示的所示的卷积码，设信息序列为，编码格图如图7.10所示，对应的码字序列为。码字序列经过BSC传输后，接收序列为(111,001,101,001,111,000)，试对接收序列进行维特比译码。第一百零三页，共一百四十六页，2022年，8月28日a:00b:01c:10d:110编码输出000111接受码字汉明距离311110011110000012第一百零四页，共一百四十六页，2022年，8月28日第一百零五页，共一百四十六页，2022年，8月28日反向搜索得到译码输出第一百零六页，共一百四十六页，2022年，8月28日当码字序列长度较大时，如果等到计算完所有的状态再进行统一译码会造成译码延时太大，不利于信息实时处理；可以分段进行译码也能构取得好的译码效果，所以反向搜索不是必需的。如果码字序列长度不是太大时，进行统一译码效果更好。第一百零七页，共一百四十六页，2022年，8月28日删余卷积码经常需要使用高码率的卷积码，如码率R=(n-1)/n;直接对高码率卷积码进行译码的译码器实现复杂度很高；既能够实现高码率的编码，同时又能避免高复杂度译码是可以实现的，方法就是从低码率的码字中删除一些码元；在卷积码编码器输出端删除事先确定的码比特的方法称为删余第一百零八页，共一百四十六页，2022年，8月28日通过对1/n卷积码删余可以产生高码率的卷积码，同时保持1/n卷积码相同的译码低复杂度;卷积码删余减小了自由距离，减小量取决删余程度。第一百零九页，共一百四十六页，2022年，8月28日周期删余假设原始码率为1/n，而删余周期为Pc，对应编码器的Pc个输入，在一个周期内，编码器输出个nPc编码比特，矩阵表示为矩阵元素pij如果为0，则对应编码比特不输出；否则编码输出。第一百一十页，共一百四十六页，2022年，8月28日可达码率其中，N表示从nPc中删除n位输出第一百一十一页，共一百四十六页，2022年，8月28日第一百一十二页，共一百四十六页，2022年，8月28日码率匹配删余卷积码(RCPC)

部分信息比其它部分的信息更重要，需要增加更多的冗余保证这些信息的有效传输。信息集合需要进行不均等错误保护，更重要的比特信息传输需要加入更多的冗余。实现方法就是对同一种卷积码使用不同的删余矩阵进行删余。删余矩阵的选择应当满足各种码率要求,这样产生的码成为码率匹配删余卷积码(RCPC).第一百一十三页，共一百四十六页，2022年，8月28日第一百一十四页，共一百四十六页，2022年，8月28日将RCPC码应用于需要进行不均等错误保护的系统，需要对信息比特进行打包，将具有不同码率的信息组合在一起，然后按照码率的先后顺序进行排列，从而形成一帧数据，每种数据的长度是知道的，以便进行译码器进行正确译码。第一百一十五页，共一百四十六页，2022年，8月28日删余卷积码编码是通过删除部分编码比特实现的。当采用维特比译码算法进行译码时，状态跳转过程所产生的码字使用对应的删余矩阵向量进行删余处理，而保持其它步骤不变即可实现译码。或者说根据删余后的格图进行维特比译码。对于RCPC也是如此，只是不同时刻的序列译码使用不同删余矩阵而已。第一百一十六页，共一百四十六页，2022年，8月28日7.3TCM码，级联码

通信系统中，调制解调器与纠错编译码器是两个主要的组成部分，分别是提高通信系统的信息传输速率和降低误码率的关键设备。纠错码需要增加一定冗余来保证信息的有效传输，纠正信息传输过程出现的误码，冗余增加必然会降低信息传输速率。如果将两种设备单独考虑进行设计，为了提高信息传输速率，就需要增加信道带宽或者提高信号发送功率。第一百一十七页，共一百四十六页，2022年，8月28日

网格编码调制(TCM)将编码技术与调制技术结合起来，利用状态记忆和分集映射来增加码序列之间的距离。不需要增加信道带宽或者信号传输功率，而是利用信号集空间的冗余提高信息传输效率。第一百一十八页，共一百四十六页，2022年，8月28日网格编码调制一般由3个部分组成：(1)差分编码:与后续的映射相结合，避免接收端译码时的信号集相位混淆问题；(2)卷积编码:将m比特编码为m+1比特；(3)分集映射器:将m+1比特一一映射2m+1到个点信号集上。第一百一十九页，共一百四十六页，2022年，8月28日输入信息b(n)经过一个差分编码器后，产生序列Y2(n)，其目的就是为了防止产生相位混淆(或者模糊)；其作用与通信原理中的差分编码一样第一百二十页，共一百四十六页，2022年，8月28日另一路输入信息a(n)一方面送往码率的卷积码编码器进行编码，产生两位输出Y1(n)Y0(n)。分集映射器的三路输入包含了两位信息，共有8种组合可以进行PSK调制，星座与输入信息之间并不是一一对应关系，映射关系应当以卷积码状态转移作为基础。第一百二十一页，共一百四十六页，2022年，8月28日而送往分集映射器的三位信息Y2Y1Y0中,Y0(n)的实际就是卷积码状态S0,所以系统的输出码字就是由于y2是卷积码的输出，整个编码系统的状态只有4种，而分集映射器的输入为三位，这样就会造成无论y2的取值如何，状态都会从一个状态跳转到另一个由卷积码编码器确定的状态，即状态转移路径增加了，从而造成平行状态转移。第一百二十二页，共一百四十六页，2022年，8月28日平行状态转移会影响卷积码的自由距离，系统从全零状态出发又回到全零状态的距离的路径与全零路径的最小距离的路径不可能大于平行转移的距离，并行转移对应的一组码字应当距离越大越好，对于调制而言就是使得欧氏距离越大越好，为此将8PSK对半地进行分集，使得每个子集具有大的欧氏距离，并且将并行转移的一组码字映射为对称的点上，从而保证并行转移具有最大的欧氏距离，这就是分集映射。第一百二十三页，共一百四十六页，2022年，8月28日级联码在信道特性一定情况下，为了得到差错概率小的好码，就需要增加码的长度，而且增加码长可以增加随机性。无论是线性分组码还是卷积码，编码实现都比较简单，但是对于最佳译码或者最大似然译码两种最常用的方法而言，译码复杂度都是与信息长度或者码长成指数关系，所以采用直接增加码长的方法不是一种有效办法，必要找到既能够增加码长同时又具有较低译码复杂度的方法。有效方法就是利用短码拼接成长码，使得拼接后的码字具有短码的译码复杂度和长码的性能，这种编码方法就是级联码。第一百二十四页，共一百四十六页，2022年，8月28日1.串行级联码编码码率为R1R2，最小汉明距离为d1d2

级联码的内码常用卷积码，而外码则常用分组码第一百二十五页，共一百四十六页，2022年，8月28日由于维特比译码是序列译码，一旦译码出错则整个序列都出现错误，相当于产生一个突发错误。如果内码采用卷积码，那么外码应当采用纠错能力足够强的分组码，使得卷积码产生的绝大多数错误能够被纠正，常用的外码是RS码。卷积码为内码的级联码适合高斯白噪声信道，因为卷积码属于纠随机错误码，如果将这种级联码用于突发错误信道，则需要在调制器与编码器之间增加交织器。第一百二十六页，共一百四十六页，2022年，8月28日交织器可以将突发信道产生的突发错误分散到各个码字中，即将突发错误随机化，从而有利于进行纠错。第一百二十七页，共一百四十六页，2022年，8月28日2.乘积码第一百二十八页，共一百四十六页，2022年，8月28日第一百二十九页，共一百四十六页，2022年，8月28日7.4Turbo码LDPCTurbo码和LDPC都是接近香农极限的码；1993年提出的Turbo码实际上是级联码研究的重要成果，其编码采用并行级联码；对一组信息进行交织后产生两组或者两组以上的校验序列，从而形成整个码字；而译码算法采用迭代译码，每次迭代译码都采用软输入、软输出译码，通过反复迭代运算提高了译码增益，从而取得好的误码率性能。无论是在高斯白噪声信道还是在衰落信道中，Turbo码都能够取得好的误码率性能。第一百三十页，共一百四十六页，2022年，8月28日LDPC（即低密度校验码）是另一种能够逼近香农极限的码，是由Gallager于20世纪60年代提出的，由于受到条件的限制，并没有受到人们的重视。后来随着Turbo码的发展，人们重新对其进行广泛、深入研究，在编译码方面已经取得了重要进展。实际上，LDPC是线性分组码，其生成矩阵和校验矩阵都是稀疏矩阵；理论上，LDPC的译码可以采用线性分组码的译码算法