线性分组码,卷积码,交织码原理

MATLAB第六次预习报告

研五队

李振坤

S201301104

线性分组码

1. 基本概念

●系统码：编码后，信息码元本身不变，只在信息码元后加入监督码元。

●线性码：监督码元和信息码元成线性关系的码型。

●分组码：将信息码分组，并为每组信息码附加若干监督码的编码。分组码一般用表

示，为实际传送的码长，是信息码长，是监督码长。

●线性分组码：分组码的信息码元和监督码元，由一些线性代数方程联系起来。分组是指编、译码过程是按分组进行的，而线性是指分组码中的监督码元按线性方程生成的。

【注】

线性分组码的编码问题，就是要建立一组线性方程组，已知k个系数（即信息码），要求n－k个未知数（即监督码）。

2. 线性分组码的主要性质

（1）封闭性

封闭性是指码中任意两许用码组之和(逐位模2和)仍为一许用码组，这就是说，若A1和A2为码中的两个许用码组，则A1+A2仍为其中的一个许用码组。

（2）码的最小距离等于非零码的最小重量

因为线性分组码具有封闭性，因而两个码组之间的距离（模2减）必是另一码组的重量。为此，码的最小距离也就是码的最小重量，当然，除全“0”码组外。

3. 汉明码

汉明码是用于纠正单个错误的线性分组码，其特点为：

（1）最小码距

（2）纠错能力 【注】

（3）监督码长

（4）总码长（）

（5）信息码长（）

（6）编码效率 （当r很大时，R趋向于1，效率高）

因此，当r＝3，4，5，6……时，分别有（7，4）、（15，11），（31，26），（63，57）等汉明码。

4. （7，4）汉明码

在（7，4）汉明码中，码组为，其中为4个信息元，为3个监督码元。监督码元与信息元之间的关系为：

（9－4）

生成矩阵G：编码时使用，用于产生整个码组，包括信息码和监督码。

改写为

其中称为生成矩阵，它的各行是线性无关的。为阶单位矩阵；为阶矩阵。

由生成矩阵可以产生整个码组，码组C是系统码（即信息码保持不变，监督码附加其后）。

【注】

（1）上述生成矩阵为典型形式，保证能产生系统码。

（2）生成矩阵中的每一行，都是一个许用码组，它们是线性无关的。

（3）线性分组码中任意k个线性无关的许用码组，就构成该线性分组码的生成矩阵。即使此矩阵不是典型形式，也可以经过线性变换，就可以得到对应的典型生成矩阵。

监督矩阵H：译码时使用，决定信息码元与监督码元之间的校验关系。

移项得 （5-1）

将式（5-1）改写为： （5-2） 【注】模2加

改写为矩阵形式

（5-3）

简记为 。

其中： （5-4）

称为监督矩阵，决定信息码元与监督码元之间的校验关系，该矩阵各行线性无关。为

阶矩阵，为阶单位矩阵。

【说明】

生成矩阵G和监督矩阵H之间存在一一对应的关系。只要G确定，则H也就确定了；反之

亦然。

5. 总结

（1）线性分组码完全可以由生成矩阵G和监督矩阵H决定。一般在讨论编码问题时，常采用生成矩阵G；在讨论译码问题时，常采用监督矩阵H。

（2）当是其他的线性分组码时，生成矩阵G和监督矩阵H会发生变化，但是

的格式不变。

（3）如果生成矩阵和监督矩阵不具备上述的典型形式，总可以通过初等矩阵变换，把它们变成典型形式。 卷积码

卷积码将k个信息比特编成n个比特，但k和n通常很小，特别适合以串行形式进行传输，时延小。与分组码不同，卷积码编码后的n个码元不仅与当前段的k个信息有关，还与前面的N-1段信息有关，编码过程中互相关联的码元个数为nN。卷积码的纠错性能随N的增加而增大，而差错率随N的增加而指数下降。在编码器复杂性相同的情况下，卷积码的性能优于分组码。

以一个例子来说明卷积码

以卷积码（n.k.N）=（3,1,3）为例来说明卷积码编码过程。编码器结构如图所示，1bit输入，3bit输出。输入输出关系为

设编码器初始状态的寄存器值为0，即m1m2m3=000,输入的信息位是1101，则此编码器的工作状态变化为下表

由表可见，当输入为1101时，输出为111 110 010 100 。。。为了使输入的信息位全部通过移存器，使移存器能够回到初始状态，在表中信息位后面加上了3个0.此外，由于m3m2只有4种状态：00,01,10,11，因此可用abcd来表示。

移存器状态与输入输出码元的关系如下图 321331211,,mmmcmmcmc

该编码的状态图如下图

编码过程

自上而下的四行节点分别表示a,b,c,d四种状态，网格中状态通常有2^k(N-1)种，从第N个节点开始，图形开始重复。

维特比译码属于概率译码，基本原理是将接收到的序列和所有可能的

发送序列作比较，选择其中汉明距离最小的序列当做是现在的发送序。现在通过卷积码（3,1,3）为例来说明译码过程。

现在的发送信息位为1101，为了移存器中的信息位全部移出，在信息位后面加入了3个0，即1101000。编码后的发送序列为111 110 010 100 001 011 000，接收序列：111 010

010 110 001 011 000，可见，在接收序列中第4和第11码元出错。由于这是一个（3,1,3）卷积码，发送序列的约束长度为N=3，所以首先需要考察3个信息段，即考察3n=9bit，即接收序列前9位111 010 010.由网格图可见，沿路径每一级有4种状态a,b,c,d。每种状态只有两个路径可以到达。故4种状态共有8条路径。

译码第一步：比较网格中的这8条路径和接收序列之间的汉明距离。例如，由出发点状态a经过3级路径后到达状态a的两条路径上面一条为000 000 000，它的接收序列为111 010

010的汉明距离为5，下面一条为111 001 011，它和接受序列的汉明距离等于3，将这8个的比较结果列在下表

译码第二步，继续考察接收序列中的后继3个比特110，计算4条幸存路径上增加1级后的8条可能路径的汉明距离。列于下表

上表中总距离最小为2，其路径是abdc+b，相应的序列为111 110 010 100

它和发送序列相同，股对应发送信息位1101.按照幸存路径可画出网格图

译码第三步，在编码时，信息位后面加了3个0，若把这3个0仍然看做是信息位，则可按照上述算法继续解码。这里不再赘述。

上例中卷积码的约束长度为N=3，需要存储和计算8条（2^kN）路径的参量。由此可见，维特比译码算法的复杂度随着约束长度N按指数增长，故维特比译码适合约束长度较小（<10）的编码。

交织码

交织编码是在实际移动通信环境下改善移动通信信号衰落的一种通信技术。将造成数字信号传输的突发性差错，利用交织编码技术可离散并纠正这种突发性差错，改善移动通信的传输特性。交织编码的目的是把一个较长的突发差错离散成随机差错，再用纠正随机差错的编码（FEC）技术消除随机差错。交织深度越大，则离散度越大，抗突发差错能力也就越强。但交织深度越大，交织编码处理时间越长，从而造成数据传输时延增大，也就是说，交织编码是以时间为代价的。因此，交织编码属于时间隐分集。在实际移动通信环境下的衰落，将造成数字信号传输的突发性差错。利用交织编码技术可离散并纠正这种突发性差错，改善移动通信的传输特性。

下面，我们以一个最简单的例子入手来讨论交织器与去交织器的设计，以及如何通过交织与去交织变换，将一个突发错误的有记忆信道改造为独立差错的无记忆信道。

假若，发送一组信息122425X(......)xxxx，首先将X送入交织器，同时将交织器设计成按列写入按行取出的5*5的列存储器，然后从存储器中按行输出送入突发差错的有机一心到，信道输出送入反交织器，他完成交织的相反变换，即按行写入按列取出，它仍是一个5*5阵列存储器。去交织器的输出，即阵列存储器中按列输出的信息，其差错规律就变成独立差错。

原始信息：

12345678910111213141516171819202122232425X()xxxxxxxxxxxxxxxxxxxxxxxxx

交织矩阵：16111621271217223813182349141924510152025xxxxxxxxxxxxxxxxxxxxxxxxx 按列写入按行读出

'16111621271217223813182349141924510152025X()xxxxxxxxxxxxxxxxxxxxxxxxx 假设在信道传输中1116212xxxx出差错变成了1116212XXXX，141924xxx变成了141924XXX。

因而，接收到的信息为：

''16111621271217223813182349141924510152025X()xxXXXXxxxxxxxxxxxXXXxxxxx 去交织矩阵：12345678910111213141516171819202122232425xXxxxxxxxxXxxXxXxxXxXxxXx

'''12345678910111213141516171819202122232425X()xXxxxxxxxxXxxXxXxxXxXxxXx

因而可见，连续的编码错误，被离散化了，再用一般的纠错码就可以解决这种错误了。