一、重复码

将同一数据重复多次发送，这就是重复码。

接收端根据少数服从多数的原则进行译码。例如：发送端将0编码为000发送，如果接收到的是001、010、100，就判为0；发送端将1编码为111发送，如果接收到的是110、101、011，就判为1。

重复码有一个很大的问题是：传输效率很低，传输效率只有1/3。

二、分组码

将k位信息比特分为一组，增加少量多余码元，共计n位，这就是分组码，一般记为（n，k）分组码。

2.1、奇偶校验码

最简单的分组码就是奇偶校验码，其监督码元只有1位。其原理为：据被传输的一组二进制码的数位中“1”的个数是奇数或偶数来进行校验。采用奇数的称为奇校验，反之，称为偶校验。

偶校验：收到1个码字，对所有位做异或，如果为0，正确；如果为1，错误。

奇校验：收到1个码字，对所有位做异或，如果为1，正确；如果为0，错误。

奇偶校验码只能检测奇数个错误，出现偶数个错误时不能正确检测出来，奇偶校验均不能纠正错误。

2.2、汉明码

最常用的（7，4）汉明码，信息码元为4位，监督码元为3位。

监督码元和信息码元的监督关系如下：

a2是a6、a5、a4的偶校验码，因此：a6⊕a5⊕a4⊕a2=0

a1是a6、a5、a3的偶校验码，因此：a6⊕a5⊕a3⊕a1=0

a0是a6、a4、a3的偶校验码，因此：a6⊕a4⊕a3⊕a0=0

遍历所有信息码元（4位），可以得到16个码字：

其检错原理如下：

分别对3组偶校验码的所有位做异或，得到s2、s1、s0：

s2=a6⊕a5⊕a4⊕a2

s1=a6⊕a5⊕a3⊕a1

s0=a6⊕a4⊕a3⊕a0

如果没有错误，则s2s1s0=000；

如果信息码元出错：

a6错误，则：s2s1s0=111；

a5错误，则：s2s1s0=110；

a4错误，则：s2s1s0=101；

a3错误，则：s2s1s0=011。

如果监督码元错误：

a2错误，则：s2s1s0=100；

a1错误，则：s2s1s0=010；

a0错误，则：s2s1s0=001。

发现错误位后，只要将对应位取反：0改为1，1改为0，就完成了纠错。

三、卷积码

分组码编码器每次输入k个信息码元，输出n个码元，每次输出的码元只与本次输入的信息码元有关，而与之前输入的信息码元无关。而卷积码编码器输出除了与本次输入的信息码元有关外，还与之前输入的信息码元有关。一般用（n，k，K）来表示卷积码，其中：n：编码器每次输出的码元个数；k：编码器每次输入的信息码元个数，一般k=1；K：约束长度，在k=1的情况下，表示编码器的输出与本次及之前输入的K个码元相关。

3.1、编码原理

（n，1，K）卷积码编码器一般使用（K-1）级移位寄存器来实现。

例如：（2，1，3）卷积码编码器需要2级移位寄存器，如下图：

编码器输入：mi，输出：u1和u2。

u1=mi⊕mi-1⊕mi-2

u2=mi⊕mi-2

两个移位寄存器的初始状态为：00；假定输入序列为：11011，左侧数据先输入；寄存器的状态及编码器输出变化如下表所示：

3.2、编码器网格图

两个寄存器的输出共有4种可能状态：00、10、01、11，沿纵轴排列，以时间为横轴，将寄存器状态和编码器输出随输入的变化画出来，这就是编码器网格图

两个寄存器的输出共有4种可能状态：00、10、01、11，沿纵轴排列，以时间为横轴，将寄存器状态和编码器输出随输入的变化画出来，这就是编码器网格图。

实线表示输入0，虚线表示输入1。

实线和虚线旁边的数字表示编码器输出。

t1时刻：寄存器状态为00。

t2时刻：如果输入为0，寄存器状态保持00，编码器输出00；如果输入为1，寄存器状态变为10，编码器输出11。

t3时刻：如果前一时刻寄存器状态为00：如果输入为0，寄存器状态保持00，编码器输出00；如果输入为1，寄存器状态变为10，编码器输出11。如果前一时刻寄存器状态为10：如果输入为0，寄存器状态变为01，编码器输出10；如果输入为1，寄存器状态变为11，编码器输出01。

t4时刻：如果前一时刻寄存器状态为00：如果输入为0，寄存器状态保持00，编码器输出00；如果输入为1，寄存器状态变为10，编码器输出11。如果前一时刻寄存器状态为10：如果输入为0，寄存器状态变为01，编码器输出10；如果输入为1，寄存器状态变为11，编码器输出01。如果前一时刻寄存器状态为01：如果输入为0，寄存器状态变为00，编码器输出11；如果输入为1，寄存器状态变为10，编码器输出00。　如果前一时刻寄存器状态为11：如果输入为0，寄存器状态变为01，编码器输出01；如果输入为1，寄存器状态保持11，编码器输出00。

t5时刻：与t4时刻情况相同。

t6时刻：与t4时刻情况相同。还以输入序列11011为例。通过编码器网格图，很容易得到输入序列11011编码得到的输出序列：11 01 01 00 01。

3.3、译码原理

卷积码的译码一般采用最大似然译码。

3.3.1 最大似然译码

假定信道的误码率为Pe，且Pe<0.5。编码器的输入信息序列长度为L，输出的码字序列有2L种可能：Ai=(i=1，2，…，2L)。

译码器在接收到码字序列B后，遍历Ai(i=1，2，…，2L)，计算发送码字序列为Ai、接收码字序列为B的发生概率，将发生概率最大的发送码字序列对应的发送信息序列作为译码结果，这就是最大似然译码。

以L=5为例，假定接收到的码字序列为：11 01 01 00 01。编码器输出的码字序列共有32种可能：

如果发送信息序列为11011，则编码器输出的码字序列为：11 01 01 00 01，全部码元传输正确，发生这种情况的概率为：(1-Pe)10。

如果发送信息序列为10011，则编码器输出的码字序列为：11 1011 11 01，5个码元传输错误，发生这种情况的概率为：Pe5(1-Pe)5。

如果发送信息序列为11010，则编码器输出的码字序列为：11 01 01 00 10，2个码元传输错误，发生这种情况的概率为：Pe2(1-Pe)8。

其他情况略。

很明显，发送信息序列为11011的概率最高，因此采用最大似然译码时译码结果为：11011。

还以L=5为例，假定接收到的码字序列为：11 01 01 10 01编码器输出的码字序列共有32种可能：

如果发送信息序列为11011，则编码器输出的码字序列为：11 01 01 00 01，1个码元传输错误，发生这种情况的概率为：Pe(1-Pe)9。

如果发送信息序列为10011，则编码器输出的码字序列为：11 1011 11 01，4个码元传输错误，发生这种情况的概率为：Pe4(1-Pe)6。

如果发送信息序列为11010，则编码器输出的码字序列为：11 01 01 00 10，3个码元传输错误，发生这种情况的概率为：Pe3(1-Pe)7。

其他情况略。

很明显，发送信息序列为11011的概率最高，因此采用最大似然译码的译码输出为：11011。

从上面两个例子可以看出：错误的码元越少，发生概率越高。要找到发生概率最高的发送序列，只要找出误码数最少的发送码字序列就可以了。而两码字间对应位不同的个数总和称为汉明距离，所以只要找出汉明距离之和最小的发送码字序列就行了。例如：01和10的汉明距离为2，00和01的汉明距离为1。

最大似然译码要遍历2L种可能码字序列计算概率才能完成译码，译码过程的计算量随L的增大而指数增长，难以实现。维特比发现了一种方法，可以大大减小译码的计算量，将最大似然译码推向实用，这就是著名的维特比译码算法。

3.3.2 维特比译码

维特比译码的原理可以结合译码器网格图来理解。

译码器网格图与编码器网格图类似，唯一的不同是：实线和虚线旁的数字不再表示编码器的输出，而是表示接收码字序列与编码器输出码字序列的汉明距离。接着前面的例子，假定接收码字序列为11 01 01 10 01（错误1个码元），画出译码器网格图。

更多内容关注公众号获取。