信道编码的前世今生

信道编码，也叫差错控制编码，是所有现代通信系统的基石。几十年来，信道编码技术不断逼近香农极限，波澜壮阔般推动着人类通信迈过一个又一个顶峰。5G到来，我们还能突破自我，再创通信奇迹吗？

所谓信道编码，就是在发送端对原数据添加冗余信息，这些冗余信息是和原数据相关的，再在接收端根据这种相关性来检测和纠正传输过程产生的差错。


这些加入的冗余信息就是纠错码，用它来对抗传输过程的干扰。


1948年，现代信息论的奠基人香农发表了《通信的数学理论》，标志着信息与编码理论这一学科的创立。根据香农定理，要想在一个带宽确定而存在噪声的信道里可靠地传送信号，无非有两种途径：加大信噪比或在信号编码中加入附加的纠错码。

这就像在嘈杂的酒吧里，酒喝完了，你还想来一打，要想让服务员听到，你就得提高嗓门（信噪比），反复吆喝（附加的冗余信号）。

但是，香农虽然指出了可以通过差错控制码在信息传输速率不大于信道容量的前提下实现可靠通信，但却没有给出具体实现差错控制编码的方法。


人类在信道编码上的第一次突破发生在1949年。

R.Hamming和M.Golay提出了第一个实用的差错控制编码方案。


受雇于贝尔实验室的数学家R.Hamming将输入数据每4个比特分为一组，然后通过计算这些信息比特的线性组合来得到3个校验比特，然后将得到的7个比特送入计算机。 

计算机按照一定的原则读取这些码字，通过采用一定的算法，不仅能够检测到是否有错误发生，同时还可以找到发生单个比特错误的比特的位置，该码可以纠正7个比特中所发生的单个比特错误。这个编码方法就是分组码的基本思想，Hamming提出的编码方案后来被命名为汉明码。

汉明码的编码效率比较低，它每4个比特编码就需要3个比特的冗余校验比特。另外，在一个码组中只能纠正单个的比特错误。

M.Golay先生研究了汉明码的缺点，提出了Golay码。

Golay码分为二元Golay码和三元Golay码，前者将信息比特每12个分为一组，编码生成11个冗余校验比特，相应的译码算法可以纠正3个错误；后者的操作对象是三元而非二元数字，三元Golay码将每6个三元符号分为一组，编码生成5个冗余校验三元符号，这样由11个三元符号组成的三元Golay码码字可以纠正2个错误。

Golay码曾应用于NASA的旅行者1号(Voyager 1)，将成百张木星和土星的彩色照片带回地球。

在接下来的10年里，无线通信性能简直是跳跃式的发展，这主要归功于卷积码的发明。

卷积码是Elias在1955年提出的。


卷积码与分组码的不同在于：它充分利用了各个信息块之间的相关性。
通常卷积码记为(n,k,N)码。卷积码的编码过程是连续进行的，依次连续将每k个信息元输入编码器，得到n个码元，得到的码元中的检验元不仅与本码的信息元有关，还与以前时刻输入到编码器的信息元(反映在编码寄存器的内容上)有关。同样，在卷积码的译码过程中，不仅要从本码中提取译码信息，还要充分利用以前和以后时刻收到的码组。从这些码组中提取译码相关信息,而且译码也是可以连续进行的，这样可以保证卷积码的译码延时相对比较小。通常，在系统条件相同的条件下，在达到相同译码性能时，卷积码的信息块长度和码字长度都要比分组码的信息块长度和码字长度小，相应译码复杂性也小一些。

很明显，在不到10年的时间里，通信编码技术的发展是飞跃式的，直到遇到了瓶颈。

根据香农前辈的指示，要提高信号编码效率达到信道容量，就要使编码的分段尽可能加长而且使信息的编码尽可能随机。但是，这带来的困难是计算机科学里经常碰到的"计算复杂性"问题。

还好，这个世界有一个神奇的摩尔定律。

得益于摩尔定律，编码技术在一定程度上解决了计算复杂性和功耗问题。而随着摩尔定律而来的是，1967年，Viterbi提出了Viterbi译码算法。

在Viterbi译码算法提出之后，卷积码在通信系统中得到了极为广泛的应用，如GSM、 IS-95 CDMA、3G、商业卫星通信系统等。

但是，计算复杂性依然是一道迈不过的墙。

尽管人们后来在分组码、卷积码等基本编码方法的基础上提出了许多简化译码复杂性的方法，但是均因无比高耸的计算复杂性之墙阻挡而变得不可逾越。
编码专家们苦苦思索，试图在可接受的计算复杂性条件下设计编码和算法，以提高效率，但其增益与香农理论极限始终都存在2~3dB的差距。

直到1993年，在日内瓦召开的 IEEE通信国际会议上，两位当时名不见经传的法国电机工程师C.Berrou和A.Glavieux声称他们发明了一种编码方法，可以使信道编码效率接近香农极限。