图一：编码性能举例（引自[1]图4）
除了分组码以外，另一类编码是卷积码。它是基于卷积运算，如图二所示。图中输入数据进入移位寄存器。在每一个时钟点，移位寄存器里储存的比特依次向前移一位，也就是得到一位（比特）新的输入数据，同时丢掉一位最老的数据。同时，寄存器里的数据与两个系数序列（图上标为码1和码2）逐位相乘，结果相加后成为输出比特。在输出端，两个码产生的两个输出比特被依次输出。注意，以上说的加法是以2为模的。即0+0=0，0+1=1，1+1=0，没有进位。
在这种情况下，每个输入比特产生两个输出比特。所以编码率是1/2。对于一个传送序列，开始的一段和最后的一段是收，发双方约定的，用来帮助解码。我们也可以说卷积码是一种很长的分组码：一个传送序列就是一个码组。当然，由于卷积结构的限制，卷积码的性能并不是同样长度分组码中的最优。
图二：卷积码编码器举例
卷积码没有复杂的代数结构，其解码方法就是上面描述过的最大似然法。上面说过，这种方法的复杂度与码长成指数关系。幸运的是，1967年维特比（Viterbi）提出了著名的维特比算法。它遵照最大似然法的原则（因而也是最优的），但利用了卷积码的结构，而使得解码器的复杂度与序列长度成线性关系。这个发明使得卷积码成为一种实用和有吸引力的编码方法。
维特比算法的基本原理可以用一个简单的例子来说明。假如我们要找一条从A到B费时最短的路。这就是最大似然法的基本要求。从A到B要经过一座桥C。从A到C有5条路，从C到B有4条路。这样组合一下就有20（5×4）种走法，需要做20次测量来找出费时最小的选择。但是，维特比指出了另一种方法：我们可以先找出A到C的最好路程，需要做5此测量。然后再找出从C到B的最好路程，4次测量。总共测量9次（5+4），就解决问题了。这个乘法到加法的转变，就把复杂度从指数增长变成了线性增长。这个问题可以简化的关键在于：我们要优化的参数（时间）是每段路程之值的线性相加。而卷积码正具有这个特性。
以上说的解码方法，都是基于已经解调的信号（也就是收到的比特序列）。但解调过程中已经丢掉了一些信息。如果我们规定收到-1V为0，1V为1，那么如果收到0.1V或0.9V，解调的结果都是1。但是这两种情况下这个“1”的确定程度是不同的，前者更有可能出错。要提高解码增益，就要试图利用这个附加信息，也就是把解调与解码结合起来。对于分组码，这样做法需要特殊的设计。而对于卷积码，这个要求可以在维特比算法下自然完成。这也就是卷积码的主要吸引力。
卷积码的另一个特点，就是它在低信噪比条件下解码增益高，而在高信噪比条件下表现就不那么好。也就是说，在输入数据含有很多错误时，它可以把误码率降低。但在低误码率的输入情况下，它的进一步的纠错能力就不高了。于是，人们把两种编码方法合起来使用。把分组码作为“外码”，即最先编码，最后解码。而卷积码作为“内码”。这样，在接收器中，收来的信号先经过维特比算法的解调/解码，产生较低误码率的比特序列。这个序列再经过分组码解码，进一步降低误码率。
以上谈到的分组码和卷积码有一个共性，就是码字是经过精心设计的，使得码字之间的最小距离尽可能大，来增强纠错能力，降低误码率。分组码有着种种特别的数学性质，以便使用巧妙的解码方法。而卷积码通常用维特比算法来解码。另外，还有把调制和卷积码编码结合在一起的“格状编码调制”（Trellis Coding Modulation, TCM），这里就不细谈了。这些码的性能离开香农极限都有几个分贝。在一段时间内，人们认为要达到香农极限即使可能也是非常困难的。
但是柳暗花明，九十年代初期人们走出了另一条路。回到香农定理的证明，那里的“码字”就是“典型序列”。而如果我们随机产生序列的话，只要足够长，绝大多数结果都是典型序列。所以随机产生的码字就是好码字。问题是，这样没有结构的码没有好的解码方法。所以长的随机码是不现实的。但是人们发现了具有一定结构的码也可以具有这样随机的特性。而它们的结构可以帮助解码。首先发现的是turbo码。它也叫乘积码。编码方法是把两个短码（分组码或卷积码），一个编码后把次序按一定规律打乱，再编一次码。这样，最后的码长是两个短码长度的乘积。解码时，也是对于两个短码分别解，但采用迭代的办法。第一次解码，只是得到一个“可能”的结果。把这个结果及其相关的概率再输入解码器一遍，就得到一个更加“可靠”一些的结果。如此反复，就能提高解码增益。从理论上讲这种方法不一定是最优的，但实际上最后性能非常接近香农极限。Turbo码也是有结构的，但这个结构不是为了增加码字间的最小距离，而是为了给解码提供方便。在Turbo码的码字中，可能有距离很近（也就是很容易出错）的码字。但这些码字只占总体的很小一部分，所以总的来说误码率还是很低。而在分组码，卷积码中，不同码字出错的几率是差不多的。可见，Turbo码的思路与以前的编码技术有很大区别，可以说是一场革命。在此启发下，又有人重新发现了另一种随机码——低密度奇偶校验码（LDPC）也有类似的特征。LDPC码也可以用迭代方法解码，性能也接近香农极限。LDPC码早在1960就被提出了，但后来几十年间这个技术慢慢被人遗忘了。直到1990年代中叶，人们用图论重新诠释LDPC码，找到了系统的设计方法和有效的解码技术，才使得LDPC重振雄风。
随机码的发明使得编码增益大大提高，基本达到了香农极限。到2000年代，这些码已经被现代通信系统采纳了。当然，它们的实现还是比较复杂，所以常常是作为可选功能。
从香农的信息论提出后的半个多世纪，人们为了实现香农预言的传送速度极限作出了巨大的努力，发展了很多精致有效的数学工具，也进行了很多大海捞针式的搜寻。随着香农极限的基本达到，编码的研究是否到了终点呢？当然，性能和复杂性的权衡总是有工作要做的，特别是在硬件性能突飞猛进的今天。另外，除了香农所研究的基本信道外，还有许多更加复杂有趣的信道。特别是无线通信的发展，产生了多天线通信，协同通信等新技术，给信道容量和实现信道容量提出了很多新课题。这些方面我们以后会继续介绍。
【参考文献】
[1]D. J. Costello and D. Forney, “Channel Coding: The Road to Channel Capacity”, Proceedings of the IEEE, vol. 95, No. 6, June 2007 p. 1150
相关文章
数字通信介绍（1） 调制数字通信介绍（2）香农与信息论
图二：卷积码编码器举例
卷积码没有复杂的代数结构，其解码方法就是上面描述过的最大似然法。上面说过，这种方法的复杂度与码长成指数关系。幸运的是，1967年维特比（Viterbi）提出了著名的维特比算法。它遵照最大似然法的原则（因而也是最优的），但利用了卷积码的结构，而使得解码器的复杂度与序列长度成线性关系。这个发明使得卷积码成为一种实用和有吸引力的编码方法。
维特比算法的基本原理可以用一个简单的例子来说明。假如我们要找一条从A到B费时最短的路。这就是最大似然法的基本要求。从A到B要经过一座桥C。从A到C有5条路，从C到B有4条路。这样组合一下就有20（5×4）种走法，需要做20次测量来找出费时最小的选择。但是，维特比指出了另一种方法：我们可以先找出A到C的最好路程，需要做5此测量。然后再找出从C到B的最好路程，4次测量。总共测量9次（5+4），就解决问题了。这个乘法到加法的转变，就把复杂度从指数增长变成了线性增长。这个问题可以简化的关键在于：我们要优化的参数（时间）是每段路程之值的线性相加。而卷积码正具有这个特性。
以上说的解码方法，都是基于已经解调的信号（也就是收到的比特序列）。但解调过程中已经丢掉了一些信息。如果我们规定收到-1V为0，1V为1，那么如果收到0.1V或0.9V，解调的结果都是1。但是这两种情况下这个“1”的确定程度是不同的，前者更有可能出错。要提高解码增益，就要试图利用这个附加信息，也就是把解调与解码结合起来。对于分组码，这样做法需要特殊的设计。而对于卷积码，这个要求可以在维特比算法下自然完成。这也就是卷积码的主要吸引力。
卷积码的另一个特点，就是它在低信噪比条件下解码增益高，而在高信噪比条件下表现就不那么好。也就是说，在输入数据含有很多错误时，它可以把误码率降低。但在低误码率的输入情况下，它的进一步的纠错能力就不高了。于是，人们把两种编码方法合起来使用。把分组码作为“外码”，即最先编码，最后解码。而卷积码作为“内码”。这样，在接收器中，收来的信号先经过维特比算法的解调/解码，产生较低误码率的比特序列。这个序列再经过分组码解码，进一步降低误码率。
以上谈到的分组码和卷积码有一个共性，就是码字是经过精心设计的，使得码字之间的最小距离尽可能大，来增强纠错能力，降低误码率。分组码有着种种特别的数学性质，以便使用巧妙的解码方法。而卷积码通常用维特比算法来解码。另外，还有把调制和卷积码编码结合在一起的“格状编码调制”（Trellis Coding Modulation, TCM），这里就不细谈了。这些码的性能离开香农极限都有几个分贝。在一段时间内，人们认为要达到香农极限即使可能也是非常困难的。
但是柳暗花明，九十年代初期人们走出了另一条路。回到香农定理的证明，那里的“码字”就是“典型序列”。而如果我们随机产生序列的话，只要足够长，绝大多数结果都是典型序列。所以随机产生的码字就是好码字。问题是，这样没有结构的码没有好的解码方法。所以长的随机码是不现实的。但是人们发现了具有一定结构的码也可以具有这样随机的特性。而它们的结构可以帮助解码。首先发现的是turbo码。它也叫乘积码。编码方法是把两个短码（分组码或卷积码），一个编码后把次序按一定规律打乱，再编一次码。这样，最后的码长是两个短码长度的乘积。解码时，也是对于两个短码分别解，但采用迭代的办法。第一次解码，只是得到一个“可能”的结果。把这个结果及其相关的概率再输入解码器一遍，就得到一个更加“可靠”一些的结果。如此反复，就能提高解码增益。从理论上讲这种方法不一定是最优的，但实际上最后性能非常接近香农极限。Turbo码也是有结构的，但这个结构不是为了增加码字间的最小距离，而是为了给解码提供方便。在Turbo码的码字中，可能有距离很近（也就是很容易出错）的码字。但这些码字只占总体的很小一部分，所以总的来说误码率还是很低。而在分组码，卷积码中，不同码字出错的几率是差不多的。可见，Turbo码的思路与以前的编码技术有很大区别，可以说是一场革命。在此启发下，又有人重新发现了另一种随机码——低密度奇偶校验码（LDPC）也有类似的特征。LDPC码也可以用迭代方法解码，性能也接近香农极限。LDPC码早在1960就被提出了，但后来几十年间这个技术慢慢被人遗忘了。直到1990年代中叶，人们用图论重新诠释LDPC码，找到了系统的设计方法和有效的解码技术，才使得LDPC重振雄风。
随机码的发明使得编码增益大大提高，基本达到了香农极限。到2000年代，这些码已经被现代通信系统采纳了。当然，它们的实现还是比较复杂，所以常常是作为可选功能。
从香农的信息论提出后的半个多世纪，人们为了实现香农预言的传送速度极限作出了巨大的努力，发展了很多精致有效的数学工具，也进行了很多大海捞针式的搜寻。随着香农极限的基本达到，编码的研究是否到了终点呢？当然，性能和复杂性的权衡总是有工作要做的，特别是在硬件性能突飞猛进的今天。另外，除了香农所研究的基本信道外，还有许多更加复杂有趣的信道。特别是无线通信的发展，产生了多天线通信，协同通信等新技术，给信道容量和实现信道容量提出了很多新课题。这些方面我们以后会继续介绍。
【参考文献】
[1]D. J. Costello and D. Forney, “Channel Coding: The Road to Channel Capacity”, Proceedings of the IEEE, vol. 95, No. 6, June 2007 p. 1150
相关文章
