信道编码(卷名：电子学与计算机)
channel coding
在信道与信源之间和信道与信宿之间必须有变换信号的设施，其中用于提高信道可靠性的称为信道编码器和译码器，它们的基础就是信道编码，是信息论的重要内容之一。信道编码大致可分为两类，一类是信道编码定理，从理论上解决理想编码器、译码器的存在性问题；另一类是构造性的编码方法以及这些方法能达到的性能界限。
编码定理的证明，从离散信道发展到连续信道，从无记忆信道到有记忆信道，从单用户信道到多用户信道，从证明差错概率可接近于零到以指数规律逼近于零，正在不断完善。至于编码方法，在离散信道中一般用代数码形式，其类型有较大发展，各种界限也不断有人提出，但尚未达到编码定理所启示的限度，尤其是关于多用户信道，更显得不足。在连续信道中常采用正交函数系来代表消息，这在极限情况下可达到编码定理的限度。
编码定理 信道容量是信道能传送的最大信息率。编码定理就是解决达到这个最大值的可能性和超过这个最大值时的传输问题。一般的编码定理是：若信道容量为C，在信道中传送的信息率为R（均以每信道符号计），如R＜C，只要输入符号的数目N足够大，总有一种使接收端译码差错概率任意小的编码方法。反之，如R＞C，必定不存在能使接收端译码差错概率任意小的编码方法；当N→∞，差错概率将接近1。
对于多用户信道，其容量是一个区域的外界“面”(见信道容量)，则须把上述的R＜C换成(R1，R2，…)矢量在界“面”的内部，把R＞C换成(R1，R2，…)矢量在界面的外部，其他情况不变。因此，信道容量是一个界限，在这个界限之内可以几乎无错误地传输，而在这个界限之外就不可能。在这个界限上的情况则是不明确的。有时把上述定理中的R＜C称为编码定理，而把R＞C称为其反定理。
不是所有信道的编码定理都已被证明。只有无记忆单用户信道和多用户信道中的特殊情况的编码定理已有严格的证明；其他信道也有一些结果，但尚不完善。其实，当信道的编码定理未被证明之前，信道容量的概念也并不明确。
证明信道编码定理通常采用随机编码的概念。所谓编码，实际上是从各种输入符号序列中选取M种作为码字来传递信息。例如输入N个符号X1，X2，…，XN，每个符号Xr∈A，若A中有n个元，则一共有nN种序列，从中任选M种作为码字，就有nNM种选法，也就是有nNM种编码方法。然后计算每种编码在接收端检测时出错概率的上界，再对每种编码赋予一个概率测度，也就是说采用一种编码是随机的，但却可计算所有编码的平均差错概率的上界。经过复杂的运算可得到这个平均差错概率圴e的上界是
圴e＜exp[-NE(R)]式中
为所传送的信息率，E(R)称为可靠性函数。当R小于信道容量时，E(R)大于零。因此当N→∞，圴e的上界将为零。既然所有编码的平均差错率将逼近于零，则必有一种较好的编码，差错概率也将逼近于零，这就证明了能无错误地传送的编码方法的存在性。反定理也可相仿地证明，只是此时应求正确概率的上界，并证明它的平均值逼近于零。关于多用户信道编码定理的证明，基本上仍用单用户理论，只是引入了时分内插原理。例如在二址接入信道中，把一个输入作为干扰，就成为单用户问题，这样可得到一种编码方法；再把另一个输入作为干扰，又得到另一种编码方法；然后这两种编码方法按时间来分配，也就是某段时间用前一种编码，而另一段时间用后一种编码，这样就扩展了容量区域，成为原来两种编码的区域的凸包，从而证明二址接入信道的编码定理，因为分别位于两个二维区域中 (Rí，R娦)和(R媹，R崉)两点的连线上的任一内点(R1，R2)就是时间分配的结果。
可靠性函数E(R)指出了差错概率与信息率 R和序列长度N的关系，但这是上界公式，还不能确切指出最佳编码的实际差错值。人们试图计算差错概率的下界，以得到相仿的指数关系，只是所得到的 E1(R)与上述E(R)不完全相同，还不能得到差错概率的确切值或确切的逼近零的速度，因此这也是编码定理中尚存的问题之一。
编码方法 编码定理只证明了最佳编码方法的存在性。50年代发展起来的纠错码理论，是为实现最佳编码方法而发展的。以二元对称信道为例，n个输入符号共有2n种序列，只选用2k种序列(k＜n)作为码字，则信息率R＝k/n比特/符号。倘若这种编码方法能纠正传输引起的t个错误符号，则当n→∞、信道的误码率ε小于t/n时，就能达到无错误的传输，这时信道容量已知为 1-H(ε)比特／符号，其中H(ε)是熵函数，即
H(x)＝-xlog2x-(1-x)log2(1-x)当
时，H(ε)是单调递增的，因而编码定理所规定的无错传送的界限是
取等号时的曲线称为汉明上限（见图）。任何编码方法不可能超过此界限。
现用的纠错码大多是线性码，可证明这类码的上界是伊莱亚斯上限，一定能达到的有V-G下限。现有的线性码是不能达到理想编码的。这些还都是理论性结论，实际编码如BCH码，当n→∞，t/n保持一定时，k/n将趋于零；反之，k/n保持不变时，t/n也将趋于零，这与编码定理的结果就有更大的距离。以后发展的许多纠错编码如戈帕码、卷积码都有类似的情况。至于后来出现的包括算术码的非线性编码，其极限情况还不十分明朗。