信息论——信道及其容量

Posted on Edited on In

这次来介绍信道以及信道的容量。 ## 信道容量的定义以及性质 ## ### 通信是什么? ### 物理实体A的作用引发了物理实体B的状态变化，如果A与B的变化存在一致性，我们称AB通信成功。从信息角度来看，也就是比特流端到端的无差错复制。 ### 信道的分类 ###

按照输入输出的形式以及时间取值来划分

取值 时间 信道分类
离散 离散 离散信道，数字信道
连续 离散 连续信道
连续 连续 模拟信道
离散 连续 ——

按照信道随机过程的特点分类

离散信道可以表示为n阶转移概率矩阵 Qt1t2...tn={q(yt1t2...tn|xt1t2...tn)} Q_ {t_1t_2...t_n} = \left \{ q(y_ {t_1t_2...t_n} | x_ {t_1t_2...t_n}) \right\} * 无记忆信道 q(yt1t2...tn|xt1t2...tn)=∏i=1nq(yi|xi) q(y_ {t_1t_2...t_n} | x_ {t_1t_2...t_n}) = \prod_ {i=1}^nq(y_i|x_i)

无记忆信道不代表输出的符号不相关，这个和输入有关。 * 平稳信道： q(yi|xi)=q(y|x) q(y_i|x_i) = q(y|x)

DMC(Discrete Memoryless Channel)

I(Xn;Yn)=H(Yn)−H(Yn|Xn) \begin{align} I(X^n;Y^n) = H(Y^n) - H(Y^n|X^n) \end{align} H(Yn)=H(Y1)+H(Y2|Y1)+...+H(Yn|Y1...Yn−1)≤∑i=1nH(Yi) \begin{aligned} H(Y^n)&= H(Y_1) +H(Y_2|Y_1) +...+ H(Y_n|Y_1...Y_ {n-1})\\ &\leq \sum_ {i=1}^n H(Y_i) \end{aligned} H(Yn|Xn)=−𝔼XYlog⁡q(yn|xn)=−𝔼XYlog⁡∏i=1nq(y1|x1)=−𝔼XY∑i=1nlog⁡q(yi|xi)=−∑i=1n𝔼XYlog⁡q(yi|xi)=∑i=1nH(Yi|Xi) \begin{aligned} H(Y^n|X^n)&= -\mathbb{E}_ {XY}\log q(y^n|x^n) \\ &= -\mathbb{E}_ {XY}\log \prod_ {i=1}^nq(y_1|x_1)\\ &= - \mathbb{E}_ {XY}\sum_ {i=1}^n\log q(y_i|x_i)\\ &= -\sum_ {i=1}^n \mathbb{E}_ {XY}\log q(y_i|x_i)\\ &= \sum_ {i=1}^n H(Y_i|X_i) \end{aligned}

综上我们得到： I(Xn;Yn)≤∑i=1nI(Xi;Yi) I(X^n;Y^n) \leq \sum_ {i=1}^nI(X_i;Y_i)

这让我们想到，对一个序列的输入输出互信息，我们可以试图通过处理单个时刻的输入，然后让等号取得，也就得到序列输入输出互信息的最大值。

为了让上面的等号取得，实际是比较简单，也就是当YiY_i之间互相独立。下面我们来研究如何让单字母互信息得到最大值。 ### 信道容量定义 ### 对于离散无记忆信道，信道容量为： C=maxp(x)I(X;Y)=maxp(x)I(p,Q) C = \max_ {p(x)}I(X;Y) = \max_ {p(x)}I(p,Q)

当一个信道确定时，QQ也就确定了，因此我们要做的就是调整输入字母的分布，让这个信道输入输出互信息得到最大，也就得到了信道的容量。之前介绍互信息的时候介绍了I(p;Q)I(p;Q)这种形式，就是为了方便信道的解释。

离散无记忆信道的容量

现在来看一看最简单的信道：离散无记忆信道的容量应如何计算。这一小节主要通过举几个例子，然后再得到普遍的结论。 #### 无噪声二元信道 ####

输入X，输出Y。由于传输误差错，所以每次传输都传递了1 bit的无差错信息。所以直观来说信道容量为1 bit.

利用信道容量的定义来计算，则： $$ C=\max I(X;Y) = \max(H(X) - H(X|Y)) = \max H(X) = 1\\ p(X) = (0.5,0.5) $$ 如果字符个数变成m个，则这个信道容量变为：log⁡m\log m. #### 输出不重叠的噪声信道 ####

观察上图，我们发现这个信道有下面几个特点： 1. 信道存在噪声，输出不确定 2. 但是不确定性不影响正确估计输入 3. 信道实际是无差错的 4. X到Y是一对多映射 $$ C = \max I(X;Y) = \max(H(X)-H(X|Y)) = \max(H(X))=1\\ p(X) = (0.5,0.5) $$

因此可以看到即时有噪声，我们依然可以得到无差错的信道传输。

混乱打字机

混乱打字机把每个字母以0.5的概率映射为其自身或者下一个字母。

则： C=max⁡I(X;Y)=max⁡(H(Y)−H(Y|X))=max⁡(H(Y)−1)=log⁡26−1=log⁡13 \begin{aligned} C &= \max I(X;Y)\\ &= \max(H(Y) - H(Y|X))\\ &= \max(H(Y)-1)\\ &= \log 26 - 1 = \log 13 \end{aligned}

我们只是在互信息求得这个，但是我们不一定能找到一个实际的概率控制得到这个容量。而实际上，这个容量是可以达到的。

我们要求输入端只能输入A,C,E...A,C,E...这些字母，从而退化成了一个输出不重叠噪声信道，这称为无重叠约化。通过这个方法，我们实现了log⁡13\log13的容量。实际上香农告诉我们，任何一种混乱的信道，都可以看作是混乱打字机信道。

BSC(Binary Symmetric Channel)

C=maxp(x)I(X;Y)=max⁡(H(Y)−H(Y|X))=max⁡(H(Y)−H(p))=1−H(p) \begin{aligned} C &= \max_ {p(x)} I(X;Y)\\ &=\max( H(Y) - H(Y|X))\\ &=\max(H(Y) - H(p))\\ &=1-H(p) \end{aligned}

我们必须证明这个容量可以取到,也就是一个上确界，这样得到信道的容量才有意义。为了让H(Y)H(Y)最大，那么p(Y)=(0.5,0.5)p(Y)=(0.5,0.5),可以简单的发现这时候p(X)=(0.5,0.5)p(X) = (0.5,0.5).也就是我们可以通过调制信源的输入概率分布得到这个最大的容量 因此CBSC=1−H(p)C_ {BSC} = 1 - H(p)

EC(删除信道)

C=maxp(x)I(X;Y) C = \max_ {p(x)}I(X;Y) I(X;Y)=H(Y)−H(Y|X)=H(Y)−H(p)≤log⁡3−H(p) \begin{aligned} I(X;Y) &= H(Y) - H(Y|X)\\ &=H(Y) - H(p)\\ &\leq \log 3 - H(p) \end{aligned}

这时候我们就遇到问题了，我们不能通过调制信源的输入概率分布使得p(Y)=(13,13,13)p(Y)=(\frac{1}{3},\frac{1}{3},\frac 1 3)，因此上面得到的不是信道容量。因此重新计算这个容量,假设p(X)=(π,1−π)p(X) = (\pi,1-\pi)： I(X;Y)=H(Y)−H(p)=H((π(1−p),p,(1−π)(1−p)))=(1−p)H(π)+H(p)−H(p)=(1−p)H(π) \begin{aligned} I(X;Y) &= H(Y) - H(p)\\ &= H((\pi(1-p),p,(1-\pi)(1-p)))\\ &= (1-p)H(\pi) + H(p) - H(p)\\ &= (1-p)H(\pi) \end{aligned}

上式中用到了熵的可加性。这时候我们可以取到H(π)=1H(\pi)=1，因此得到C=1−pC = 1-p.

离散无记忆对称信道容量

实际上，上面的几个信道有很多都属于离散无记忆对称信道。他们的特点是概率转移矩阵QQ为对称矩阵，使得H(Y|X)H(Y|X)可以由信道性质确定，大大简化了我们要思考的问题。

离散无记忆对称信道的定义： 若信道的概率转移矩阵的行互为置换，列互为置换，则该信道对称，如果行互为置换，各列之和相等，则该信道弱对称。

强对称： [121316161213131612] \begin{bmatrix} \frac 1 2&\frac 1 3& \frac 1 6\\ \frac 1 6&\frac 1 2&\frac 1 3\\ \frac 1 3&\frac 1 6&\frac 1 2 \end{bmatrix}

弱对称： [131612131216] \begin{bmatrix} \frac 1 3 & \frac 1 6 &\frac 1 2\\ \frac 1 3 & \frac 1 2 & \frac 1 6 \end{bmatrix}

不管是强对称还是弱对称，他们都有一个好处，那就是H(Y|X)H(Y|X)不会随着信源的概率分布而改变，是一个常数。

弱对称信道Q的容量为：C=log⁡|Y|−H(Q的行向量对应的分布)C=\log \vert Y\vert - H(Q的行向量对应的分布),容量在输入为等概分布时候取得。

而EC不是一个对称信道： Q=[1−pp00p1−p] Q = \begin{bmatrix} 1-p & p & 0\\ 0 & p & 1-p \end{bmatrix}

一般离散无记忆信道的容量

由于I(p,Q)I(p,Q)是pp的上凸函数，因此求信道容量实际上可以表述为一个约束的极值问题： $$ \max _ {p} I(p,Q)\\ s.t. \sum_ {x}p(x)=1;p(x)\ge 0 $$

kkt condition

设f(x)f(x)为定义在Ｎ维无穷凸集SS, $S=\{x = \(x_1,x_2,...,x_N\):x_i \ge 0,i=1,...,N\}$上的可微上凸函数，设$x^\* = {x_1^\*,...,x_N^\*} \in S$，则f(x)f(x)在$x = x^\*$达到SS上的极大值的充要条件为： $$ \frac{\partial f(x)}{\partial x_n}\lvert_ {x = x^*} = 0,x_n^* > 0\\ \frac{\partial f(x)}{\partial x_n}\lvert_ {x = x^*} \leq 0, x_n^* = 0 $$

我们称$x^\*(x^\*=(x_1^\*,...,x_N^\*),x_n^\* > 0)$为SS的内点，而$\exists x_n^\* = 0$时，$x^\*$为SS的边界点。

用图像来看的话会更容易理解：

上图为：

min⁡f(x,y)=ax2−blog⁡y,0<x<100,0<y<100\min f(x,y)=ax^2-b\log y,0< x <100,0< y <100

实际上的kkt条件比这个更严谨，可以参考：kkt condition

由于它是一个凸函数下的充要条件，因此只要我们找到了一个点符合KKT条件，我们就可以称他为全局极值。

由KKT条件可以得到下面的关于信道容量的定理：

对于信道矩阵为QQ的离散无记忆信道，其输入分布$p^\*$能使互信息I(p,Q)I(p,Q)取得最大值的充要条件是： $$ I(X=x_k;Y) = C,p^*(x_k) > 0\\ I(X=x_k;Y) \leq C,p^*(x_k)=0\\ k \in {1,2,...,K} $$ 其中I(X=xk;Y)=∑j=1Jq(yj|xk)log⁡q(yj|xk)p(yj)I(X=x_k;Y) = \sum_ {j=1}^J q(y_j|x_k) \log \frac{q(y_j|x_k)}{p(y_j)},表示的是信源字母xkx_k传送的平均互信息。

当然我们拿到一个信道以后，不一定一定要通过这样的方法来求得信道容量，很多时候我们可以联系物理猜到最好的哪个情况。如下：

我们可以很容易看出来1是最差的情况，因为它可能映射到三种结果，而0,２一样好，因此我们猜测：p(x1)=0,p(x2)=p(x0)=0.5p(x_1) = 0,p(x_2)=p(x_0)=0.5，计算得到： I(X=x0;Y)=I(X=x2;Y)=0.75,I(X=x1;Y)=0.0251<0.75 I(X=x_0;Y) = I(X=x_2;Y)=0.75, I(X=x_1;Y) = 0.0251<0.75 符合kkt条件，因此它的容量就是0.75. ## 信道的组合 ##

现在我们尝试将信道组合起来。 ### 级联的独立信道 ###

如上图，我们可以得到： * 由数据处理定理可以得到：I(Y;Z)≥I(X;Z)I(Y;Z) \ge I(X;Z) * 随着串联信道数目的增多，整个信道容量趋近于0 * 将级联信道的QiQ_i乘起来，得到整个级联信道的Q，可求解级联信道的容量 * Vision：从统计的角度来看，数据处理不会带来信息增益，反而会损失信息 ### 输入并联信道 ###

这个信道的特点是，输入相同的X，输出不同的Y1,Y2,...,Y_1,Y_2,...,构成随机矢量Y。也就是我们将输入X同时送到N个信道中，如图：

  • 输入并联信道的容量大于任何一个单独的信道，小于max⁡H(X)\max H(X).
  • N个二元对称信道输入并联之后的信道容量，一般来说NN越大，CNC_N越大，越接近于H(X)H(X)。
  • Vision:通信中的分集，就是典型的输入并联信道（我并不懂通信）

并用信道

并用信道的图和并联信道非常像，不过它的输入不是相同的XX了，而是将XX费解成了X1,X2,...,XNX_1,X_2,...,X_N。 * 多输入，多输出。XX和YY是由比侧独立的N个信道传输 * 并用信道的容量：C=∑n=1NCnC = \sum_ {n=1}^N C_n * Vision:通信中的复用，就是典型的并用信道

虽然并用信道的容量结论很简单，但是在实际中的操作没那么容易。我们不能简单的将信源随意划分，而是让这个划分符合各个信道容量的噪声特性，以达到最好的传输效果。

和信道

和信道和并联信道并用信道不同的是，虽然它有多个信道，但是它并不是同时使用多个，而是每次只使用一个。 * 随机应用NN个信道中的一个，构成一个输入输出信道。 * 和信道的容量：C=log⁡∑n=1N2CnC = \log \sum_ {n=1}^N 2^{C_n}，信道的使用概率pn(C)=2Cn−Cp_n(C) = 2^{C_n - C} * Vision: 新型通信技术——机会通信 要注意这个结论有点反直觉。我们可能会想，如果某个信道的容量大，一直使用它不就行了吗？但是这样并不会得到最大的信道容量。

举个例子，如果一个信道的转移矩阵为QQ: $$ Q = \begin{bmatrix} 1 - \epsilon_1&\epsilon_1&0&0\\ \epsilon_1&1 - \epsilon_1 & 0 & 0 \\ 0&0&\epsilon_2 &1 - \epsilon_2\\ 0&0&1-\epsilon_2&\epsilon_2 end{bmatrix} $$

那么这个信道的容量为多大？

如果仔细观察，可以发现这个信道实际上是一个和信道。

C=log⁡(2C1+2C2) C = \log(2^{C_1} + 2^{C_2}) 如果： ϵ1=0,C1=1;ϵ2=0,C2=0\epsilon_1 = 0,C_1 = 1;\epsilon_2 = 0,C_2 = 0;

可以发现，这两个信道一个容量为0,另一个为1,而它们的和信道容量为log⁡3>1\log3>1。这是因为在选择使用哪个信道的时候，也包含了一定的信息。

连续信道的容量

连续信道时间依旧离散，取值是连续的。这就引发了一个问题：连续随机变量互信息非负但是不一定有限，如果输入输出相等，则此时互信息是无穷的。 这样，互信息最大值为信道容量的定义就失去了意义。 ### 容量费用函数 ### 首先说明一下，连续信道输入连续，输出连续，而信道特性不能再用一个概率转移矩阵来表示，而是一个概率密度函数。所以我们用三元组{X,q(y|x),Y}\{X,q(y|x),Y\}来表示一个连续信道。

费用函数: 设对于连续无记忆信道{X,q(y|x),Y}\{X,q(y|x),Y\}，有一个函数b(.)b(.)，对于每一个输入序列X=x1x2...xnX = x_1x_2...x_n，b(x)>0b(x)>0。称bb为XX的费用。设随机矢量X=X1X2...XnX = X_1X_2...X_n的联合分布为p(x)p(x)，则平均费用为： 𝔼[b(X)]≜∑xp(x)b(x) \mathbb{E}[b(X)] \triangleq \sum_ {x}p(x)b(x)

在费用约束的前提下，求输入输出互信息的最大值，得到容量费用函数： 设连续信道的NN维联合输入输出分别为X,YX,Y，则其容量－费用函数定义为： C(β)=limN→∞1Nmaxp(x){I(X;Y):𝔼[b(X)]≤Nβ} C(\beta) = \lim_ {N\rightarrow \infty} \frac{1}{N} \max_ {p(x)}\{I(X;Y):\mathbb{E}[b(X)]\leq N \beta \}

连续无记忆加性噪声信道的容量

这里我们来看一个最简单的连续信道的容量费用函数。这个信道为加性噪声信道。也就输入XX加上某个ZZ得到YY。

在这种情况下：q(y|x)=PZ(y−x)=PZ(z).q(y|x) = P_Z(y-x) = P_Z(z).

我们希望求得的是： C(PS)=maxp(x):𝔼X[X2]≤PSI(X;Y)=maxp(x):𝔼X[X2]≤PS[h(Y)−h(Z)]. C(P_S) = \max_ {p(x):\mathbb{E}_X[X^2] \leq P_S} I(X;Y) = \max_ {p(x):\mathbb{E}_X[X^2] \leq P_S} [h(Y) - h(Z)]. （这里的𝔼X[X2]\mathbb{E}_X[X^2]实际上是物理意义上均值为0的X的功率，因此这个约束是功率的约束） 之所以能得到上面的结论，因为： h(Y|X)=−∬XYPX(x)q(y|x)log⁡q(y|x)dxdy=−∬XZPX(x)PZ(z)log⁡PZ(z)dxdz=−∫zP(z)log⁡P(z)dz=h(Z) \begin{aligned} h(Y|X) &= -\iint_ {XY}P_X(x)q(y|x) \log q(y|x) dxdy\\ &=-\iint_ {XZ}P_X(x)P_Z(z) \log P_Z(z) dxdz\\ &= -\int_z P(z) \log P(z)dz \\ &= h(Z) \end{aligned} 因此在这个情况下：h(Y|X)=h(Z)h(Y|X) = h(Z)

高斯噪声

现在我们假设这个噪声为高斯噪声。

则： 𝔼[Y2]=𝔼[(X+Z)2]=𝔼[X2]+𝔼[Z2]=PS+PZ \mathbb{E}[Y^2] = \mathbb{E}[(X+Z)^2] = \mathbb{E}[X^2]+\mathbb{E}[Z^2] = P_S+P_Z 如果回顾连续随机变量的熵和互信息，我们可以得到： maxp(x):𝔼[x2]≤PSh(Y)=12log⁡2πe(PS+PZ) \max_ {p(x):\mathbb{E}[x^2]\leq P_S}h(Y) = \frac 1 2 \log 2\pi e(P_S+P_Z) 而h(Z)=12log⁡2πePZh(Z) = \frac 1 2 \log 2 \pi e P_Z 而这时候，我们可以得到： C(PS)=max⁡(h(Y)−h(Z))=12log⁡PS+PZPZ=12log⁡(1+PSPZ) \begin{aligned} C(P_S) &= \max(h(Y) - h(Z)) = \frac 1 2 \log \frac{P_S+P_Z}{P_Z} \\ &=\frac 1 2 \log(1+\frac{P_S}{P_Z}) \end{aligned}

上式中，PSPZ\frac{P_S}{P_Z}也就是常说的信噪比。可以看到，如果想要增加容量，我们可以想方设法提高信源功率，或者减少噪声。这是一个非常重要的公式，拓展到模拟信道的情况上，我们就可以得到著名的香农公式。

实际上，对于高斯分布的输入，高斯噪声具有最大的破坏力。即，在同样的功率约束条件下，加性高斯噪声使得信道的容量最小。

对于无记忆加性噪声信道，若输入信号XX具有高斯分布，加性噪声的功率为PNP_N，则当噪声具有高斯分布的时候，输入输出的互信息达到最小。

这一点并不难理解，因为噪声带来的影响在最终是要被去除的，而高斯情况下熵最大，去除的越多，留下的越少，所以使得信道容量最小。

一般的无记忆加性噪声信道容量

现在我们来看看一般的无记忆加性噪声的信道容量。

首先，我们必须明确，如果噪声是任意分布的，我们无法获得信道容量的解析解，但是我们可以给出其上界和下界。

  • 下界： C(PS)=maxP(X){I(X;Y):𝔼[X2]=PS}≥I(XG;Y)≥I(XG;YG)=12log⁡(1+PSPZ) \begin{aligned} C(P_S) &= \max_ {P(X)} \{I(X;Y):\mathbb{E}[X^2] = P_S\}\\ \ge I(X_G;Y)\ge I(X_G;Y_G) = \frac 1 2 \log(1 + \frac{P_S}{P_Z}) \end{aligned}

因为上面我们已经得到了。高斯噪声的破坏力是最大的。

  • 上界： $$ \mathbb{E}[Z^2] = P_N,\mathbb{E}[X^2] = P_S,\mathbb{E}[Y^2] = P_S+P_N\\ h(Y)\leq \frac{1}{2}\log [2\pi e (P_s +P_N)]\\ C_(P_S) \leq h(Y) - h(Z) = \frac 1 2 \log[2\pi e \frac{P_S+P_N}{P_e}]\\ $$ 上式中： Pe≜12πeexp⁡[2h(Z)] P_e \triangleq \frac 1 {2\pi e} \exp[2h(Z)]

说实话，我并不知道这个定义是从何而来。而且PeP_e中还包含着h(Z)h(Z)，又怎么能说是个上界呢？

并联连续高斯信道

输入Xn,PSnX_n,P_ {S_n}，信道噪声Zn,PNnZ_n,P_ {N_n}.

在总功率限定的情况下，求信道容量-费用函数： C(PS)=supP(X){I(X;Y):∑n=1NPSn=PS} C(P_S) = \sup_ {P(X)}\{I(X;Y):\sum_ {n=1}^N P_ {S_n} = P_S\} （这里的sup指的是Supremum，上确界）。

现在我们面临一个优化问题： max⁡I(Xn;Yn)=∑i12log⁡(1+PSiPNi) \max I(X^n;Y^n) = \sum_i \frac{1}{2} \log (1+\frac{P_ {S_i} }{P_ {N_i} }) s.t. ∑i=1nPSi=PS,PSi≥0\sum_ {i=1}^n P_ {S_i} = P_S,P_ {S_i} \ge 0

这个优化问题解决如下： $$ \frac{\partial }{\partial P_ {S_i} } \left[\sum_ {i=1}^n \frac{1}{2} \log(1+\frac{P_ {S_i} }{P_ {N_i} }) - \lambda (\sum_ {i=1}^n P_ {S_i} - P_S)\right] = 0\\ \frac{1}{2} \frac{P_ {N_i} }{P_ {S_i}+P_ {N_i} } \frac{1}{P_ {N_i} } - \lambda = 0, \text{for }1 \leq i \leq n\\ P_ {S_i} + P_ {N_i} = \frac{1}{2\lambda_i}, \lambda = \frac{n}{2(P_S+P_N)}\\ P_ {S_i} = \frac{P_S+P_N}{n} - P_ {N_i}, $$

要注意，这里我们将信道个数总数写成了nn，而PNP_N表示的是噪声功率。

有时候，我们发现，求得的PSiP_ {S_i}，也就是给该信道分配的功率是小于0的，这时候应该怎么办？ #### 注水功率 #### 下面介绍一个很形象的概念，叫注水功率。如下图： 可以看到的是，有的时候水是无法覆盖住某些地方的。这说明的是这个信道的噪声太大了，所以我们应该将其弃用。然后再重新计算这个功率的分配，直到没有负值。

模拟信道容量

模拟信道在时间和取值上都是连续的信道。是自然界最自然的一种信道，如电磁波，光纤，电缆等传播。

然而实际中模拟信道在数学上的研究是难以进行的。我们只研究最简单的一类模拟信道：AWGN信道。 ### AWGN信道 ### AWGN（Additive White Gaussian Noise）信道有下面几个特点： * 带宽有限：WW * 加性噪声：y(t)=x(t)+z(t)y(t) = x(t) + z(t) * 白色噪声：平稳遍历随机过程，功率谱密度均匀分布于整个频域，即功率谱密度（单位带宽噪声功率）为一常数 * 高斯噪声：平稳遍历随机过程，瞬时值的概率密度函数服从高斯分布

这个信道描述如下：

输入信号：x(t)x(t) * 带宽有限：输入信号带宽限制在[−W,W]内[-W,W]内 * 时间有限：T

输出信号：y(t)y(t)

噪声信号：z(t)z(t) * 加性白色高斯噪声 * 零均值 * 双边功率谱密度：$N(f) = \left { N02|f|≤W0||>w\begin{matrix} \frac{N_0}{2} & \vert f\vert \leq W\\ 0&\vert \vert > w \end{matrix}

. $

信道费用：输入信号的功率

信号的正交分解

  • 由于信道频带受限，信号时长受限，所以仅需要N=2WTN = 2WT个采样点就可以表示
  • 因此信道在时间上可以被离散化为2WT2WT个点，在每个点上取值连续
  • 这样变成了并联的连续信道 实际上，上面的采样就是著名的奈奎斯特采样。

之前我们说明了并联的连续信道的容量求法，但是前提是各个信道是独立的。现在我们必须要明白，经过采样的这N=2WTN = 2WT个信道是否互相独立？

答案是独立的。为了验证他们的独立性，我们只需要验证它们不相关即可，因为在高斯分布下，不相关就意味着独立。证明如下： (额，这里也不是很懂。对于信号处理和通信方面的知识已经忘的差不多了)

对于NN个信道，两两独立，每个噪声功率为N02\frac{N_0}{2}.

所以利用时域上采样定理将信号变成离散序列后，模拟信道可看成加性白色高斯噪声无记忆连续信道，相当于NN个高斯加性信道的并联信道。这时候我们可以用注水功率来分配这个功率。

并联信道总容量费用函数CT(PS)=12∑n=12WTlog⁡(1+PSnPNn)C_T(P_S) = \frac{1}{2} \sum_ {n=1}^{2WT} \log (1+ \frac{P_ {S_n} }{P_ {N_n} })

噪声约束：PNn=N02→PN=NPNn=2WTN02=WTN0P_ {N_n} = \frac{N_0}{2} \rightarrow P_N = NP_ {N_n} = 2WT\frac{N_0}{2} = WTN_0

功率约束：（类似于注水功率分配） PSn=PST+PNN−PNn=PST+2WTN022WT−N02=PS2W P_ {S_n} = \frac{P_ST+P_N}{N} - P_ {N_n} = \frac{P_ST+2WT\frac{N_0}{2} }{2WT}-\frac{N_0}{2} = \frac{P_S}{2W}

这时候，我们就得到了香农公式，AWGN信道的容量为： C=Wlog⁡(1+PSN0W) C = W \log (1+\frac{P_S}{N_0W}) 上式中，各个量的单位为C−bps,W−HzC-bps,W-Hz或者s−1s^{-1},PS−Watt,N0−Watt/HzP_S-Watt,N_0-Watt/Hz

Vision:提升容量的各种手段

  • 增加带宽 limW→∞C(PS)=limW→∞PSN0log⁡(1+PSN0W)N0WPS=PSN0log⁡e≈1.44PSN0 \lim_ {W\rightarrow \infty}C(P_S) = \lim_ {W\rightarrow \infty} \frac{P_S}{N_0}\log\left(1+\frac{P_S}{N_0W}\right)^{\frac{N_0W}{P_S} } = \frac{P_S}{N_0} \log e \approx 1.44\frac{P_S}{N_0}

  • 增加带宽 limPS→∞C(PS)≈ln⁡(PSN0W) \lim_ {P_S \rightarrow \infty} C(P_S) \approx \ln\left(\frac{P_S}{N_0W} \right)

因此，对于同样容量的传输要求，可以采用两种方式：减少带宽，发送较大功率的信号，或者增加带宽，用较小功率的信号传输。

可以看到的是，我们可以不断增加带宽来增加信道容量，不过这个性价比会越来越低，因为这是一个log函数。

Vision:信息与热力学的联系

这里有一个有意思的信息论角度对阿波罗登月的证伪，大家图一个乐，里面有很多假设和实际不符。 到目前为止，我们都只算出来了信道容量，没有讲过怎么编码能得到这些容量。接下来要做的就是说明，所有上面算出来的容量，都是可以实现的。 ## 信道编码 ##

这里我们先回忆一下之前的混乱打字机。之前说过，世界上任何一个数字信道，都可以直接或者间接地看作是混乱打字机模型。

对于信道{X,q(y|x),Y}\{X,q(y|x),Y\}的信道编码包含以下要素： * 输入符号集合{1,2,...,2nR}\{1,2,...,2^{nR} \} * 编码函数XnX^n:{1,2,...,2nR}→Xn\{1,2,...,2^{nR} \}\rightarrow X^n，该函数为每一个输入符号产生了相应的信道编码码字Xn(1),Xn(2),...,Xn(m)X^n(1),X^n(2),...,X^n(m)，这些码字构成的集合称为“码本”。 * 解码函数gg:Yn→{1,2,...,2nR}Y^n \rightarrow \{1,2,...,2^{nR} \}，该函数为一个确定性判决函数，将每一个可能的接受向量映射到一个输入符号。

意思也就是，对于符号个数为2nR2^{nR}的符号集，我们把它映射到一个长度为n的序列上,分n次传输。 ### 信道编码的码率 ###

(M,n)(M,n)码的码率Ｒ定义为： R=log⁡Mn, R = \frac{\log M}{n} , 单位为比特/传输。这是信道码的每个码字母所能携带的最大的信息量。

如何理解？对于输入集合如果取等概分布，则它的信息量为MM，这时候呢，nn次传输才能传达这么多的信息量，所以每个传输的量就是log⁡Mn=R\frac{\log M}{n} = R，则M=2nRM = 2^{nR}。称这样的码为(2nR,n)(2^{nR},n)码。

Example

重复码，输入字母数M=2M = 2:{0,1}\{0,1\}，重复n次，这个码率为1/n1/n。

二进制奇偶校验码，输入字母数M=2n−1:x1,x2,...,xn−1M = 2^{n-1}:{x_1,x_2,...,x_ {n-1} }，信道编码方案为C=x1,x2,...,xn−1xparityC = x_1,x_2,...,x_ {n-1}x_ {\text{parity} }，其中$x_ {\textP{parity} }$用于辨识码字中11的个数为奇数还是偶数，这个码率为：n−1n\frac{n-1}{n}。

信道编码的错误概率

输入为符号ii时的条件错误概率为： λi=Pr{g(Yn)≠i|Xn=xn(i)}=∑ynq(yn|xn(i))I(g(yn)≠i) \begin{aligned} \lambda_i &= Pr\{g(Y^n) \ne i \vert X^n = x^n(i)\}\\ &= \sum_ {y^n} q(y^n\vert x^n(i))I(g(y^n) \ne i) \end{aligned} 其中I(⋅)I(\cdot)为指示函数。

(M,n)(M,n)码的最大错误概率为： λ(n)=maxi∈1,2,...Mλi \lambda^{(n)} = \max_ {i \in 1,2,...M} \lambda_i

(M,n)(M,n)码的算术平均错误概率为： Pe(n)=1M∑i=1Mλi P_e^{(n)} = \frac{1}{M} \sum_ {i=1}^M\lambda_i

我们称一个码率RR是可达的，若存在一个信道编码(⌈2nR⌉,n)(\lceil 2^{nR}\rceil,n )，其最大差错概率在n→∞n\rightarrow \infty时趋于0。可以看出来可达要求无差错，而且是渐进的。

这时候我们得到信道容量的另外一个定义：一个信道的容量是该信道上所有可达码率的上确界，即C=sup RC = \text{sup }R，这意味着CC一定对应着一种信道编码方案。

经验主义式的设计

在信道传输中如何减少差错？由香农公式： CT(β)=WTlog⁡(1+PSN0W) C_T(\beta) = WT \log(1+\frac{P_S}{N_0W}) 可以得到，提高抗干扰能力的方法如下： 1. 增加功率(提高信噪比) 2. 加大带宽(信号变化剧烈) 3. 延长时间(降低速率)

C=maxp(x),功率约束{I(X;Y)}C = max_ {p(x),功率约束}\{I(X;Y)\}

而降低重复速率，实际上就是重复，增加冗余。

重复码

最直观的纠错方法就是：重复，增加冗余。 * 编码１：将每个输入元重复三次 * 纠正任一位上的错误 * 设码字记为(c8,c7,...,c0)(c_8,c_7,...,c_0) * 由编码方法可知，信道无误时： $$ c_8 = c_7 = c_6\\ c_5 = c_4 = c_3\\ c_2 = c_1 = c_0 $$ * 解码时，若c8=c6≠c7c_8 = c_6 \ne c_7，则判定c7c_7位出错，采用简单多数法进行判定 * 依据是：连续出现两个错误的概率远远小于出现一个错误的概率 如下图，如果我们将上述编码放进二进制对称信道，则想要得到无差错编码，n→0n \rightarrow 0，而码率也趋近于0，这不是一个好消息。

但是，是否对于信息的无差错传输，就意味着码率为0呢？答案是否定的。

现在我们考虑BSC信道，W={1,2,...,2k}W= \{1,2,...,2^k\},如图：

我们可以得到： nC≥nI(X;Y)≥I(Xn;Yn)≥I(W,Ŵ)=H(W)−H(W|Ŵ)≥k−kH(Pe) \begin{aligned} nC \ge nI(X;Y)\\ \ge I(X^n;Y^n)\\ \ge I(W,\hat W)\\ =H(W) - H(W\vert \hat W)\\ \ge k - k H(P_e) \end{aligned} 上式中最后一步是有Fano不等式得到的。

则：k≤nC1−H(Pe)k \leq \frac{nC}{1 - H(P_e)}

而由于BSC信道的容量可以得到：C=1−H(P)C = 1 - H(P)，所以我们得到一个R的上界： R=kn≥1−H(P)1−H(Pe) R = \frac{k}{n} \ge \frac{1 - H(P)}{1 - H(P_e)}

通过变形，我们可以得到： H(Pe)≥1−CR→Pe≥H−1(1−CR) H(P_e) \ge 1 - \frac C R \rightarrow P_e \ge H^{-1}\left(1 - \frac C R\right)

这意味着，如果想要让Pe≤0P_e\leq 0，则R≤CR \leq C，如果R>CR > C，则H(Pe)>0H(P_e)>0，所以我们一定可以得到Pe>0P_e>0，不可能进行可靠通信。

那么无差错传输的情况下，码率最大能有多少？先给你看一个preview，很直白的内容，不过它被证明确实是正确的：

想象信道将信源映射到一个球体里，而对每个输入符号也对应一个球。而这个球的体积就意味着噪声带来的体积，而大球中能容纳多少小球，正是这个信道编码在无错的情况下可以映射的符号数M。因为这个球的维度是n维的，我么可以得到： M=[PS+PN]n[PN]n=(1+PSPN)n2 M = \frac{\left[\sqrt{P_S +P_N}\right]^n}{\left[\sqrt{P_N}\right]^n} = (1 + \frac{P_S}{P_N})^{\frac n 2}

由上式，可以计算得出： R=12log⁡(1+PSPN) R = \frac 1 2 \log (1 + \frac{P_S}{P_N})

而这个值，正好与连续无记忆加性高斯噪声信道的容量一致。

当然，这个只是preview，不是严格的证明过程。下面对这个证明进行稍微严谨地推导，说明大多数噪声信道都有这样地特性。

为了证明这个东西，我们需要介绍一些别的定义。之前证明信源无失真压缩定理地时候，用到了典型序列，而这次我们在典型序列地基础上，重新介绍一个新的内容。 ### 证明香农第二定理 ### #### 联合典型序列 #### 设(Xn,Yn)(X^n,Y^n)是长为nn的随机序列对，其概率分布满足 p(xn,yn)=∏i=1np(xi,yi) p(x^n,y^n) = \prod_ {i=1}^n p(x_i,y_i) 若(Xn,Yn)(X^n,Y^n)满足以下条件，则称其为联合典型序列： * |−1nlog⁡p(xn)−H(X)|<ϵ\lvert -\frac 1 n \log p(x^n) - H(X) \rvert < \epsilon * |−1nlog⁡p(yn)−H(Y)|<ϵ\lvert -\frac 1 n \log p(y^n) - H(Y) \rvert < \epsilon * |−1nlog⁡p(xn,yn)−H(X,Y)|<ϵ\lvert -\frac 1 n \log p(x^n,y^n) - H(X,Y)\rvert < \epsilon 联合典型序列构成的集合为Aϵ(n)A_\epsilon^{(n)}。

联合典型序列与之前典型序列定义是有很大地相似性：信息论——Lossless-Encoding.我们首先要看看联合典型序列的性质，才能用它来证明。 #### 联合渐进等同分割定理（Joint AEP） #### 设(Xn,Yn)(X^n,Y^n)是长度为nn的随机序列对，其分布满足： p(xn,yn)=∏i=1np(xi,yi) p(x^n,y^n) = \prod_ {i=1}^n p(x_i,y_i) 则以下性质成立： * 当n→∞n \rightarrow \infty时，Pr((Xn,Yn)∈Aϵ(n))→1Pr((X^n,Y^n) \in A_\epsilon ^{(n)}) \rightarrow 1 * (1−ϵ)2n(H(X,Y)−ϵ)≤|Aϵ(n)|≤2n(H(X,Y)+ϵ)(1 - \epsilon)2^{n(H(X,Y) - \epsilon)} \leq \vert A_\epsilon ^{(n)} \vert\leq 2^{n(H(X,Y)+\epsilon)} * 设$(,)p(xn)p(yn) ,即,即,统计独立，且具有与统计独立，且具有与p(xn,yn)$一致的边缘分布，则： Pr((Xñ,Yñ)∈Aϵ(n))≤2−n(I(X,Y)−3ϵ) Pr\left((\tilde{X^n},\tilde{Y^n}) \in A_\epsilon ^{(n)}\right) \leq 2^{-n(I(X,Y) - 3\epsilon)} 若nn足够大，则： Pr((Xñ,Yñ)∈Aϵ(n))≥(1−ϵ)2−n(I(X,Y)+3ϵ) Pr\left((\tilde{X^n},\tilde{Y^n}) \in A_\epsilon ^{(n)}\right) \ge (1 - \epsilon)2^{-n(I(X,Y) + 3\epsilon)}

前两点都比较好理解，第三点中，(Xñ,Yñ)(\tilde{X^n},\tilde{Y^n})是由(Xn,Yn)(X^n,Y^n)的边缘分布依照Xn,YnX^n,Y^n独立形成的另一个联合分布，而这个分布属于典型序列的概率约等于2−nI(X,Y)2^{-nI(X,Y)}。

在这里我们证明以下第三条的前半部分： $$ \tilde{X^n},\tilde{Y^n}\text{ are independent. }\tilde{X^n}\sim P_X(x^n),\tilde{Y^n}\sim P_Y(y^n)\\ \begin{aligned} Pr\{(\tilde{X^n},\tilde{Y^n}) \in A_\epsilon^{(n)} \} &= \sum_ {(\tilde{x^n},\tilde{y^n}) \in A_\epsilon^{(n)} } P(x^n)P(y^n)\\ &\leq 2^{b(H(X,Y) + \epsilon)}\cdot 2^{-n(H(X) - \epsilon)} \cdot 2^{-n(H(Y) - \epsilon)}\\ &= 2^{-n(I(X,Y) - 3\epsilon)} \end{aligned} $$

下图可以帮助我们更好地理解这些性质： * 联合分布中，大约有2nH(X)2^{nH(X)}个典型X序列和2nH(Y)2^{nH(Y)}个典型Y序列 * 其组合共有2nH(X)+nH(Y)2^{nH(X) + nH(Y)}个，但是其中联合典型的只有2nH(X,Y)2^{nH(X,Y)}个 * 随机选择而出现联合典型序列的概率为2−nI(X,Y)2^{-nI(X,Y)}

现在来看一下联合典型序列的另一个解释： * 对于典型输入序列xnx^n，存在大约2nH(Y|X)2^{nH(Y|X)}个可能的输出，且它们等概 * 所有可能的典型输出序列大约有2nH(Y)2^{nH(Y)}个，这些序列被分成若干个不相交的子集 * 子集个数为2n(H(Y)−H(Y|X))=2nI(X;Y)2^{n(H(Y) - H(Y|X))} = 2^{nI(X;Y)}，表示信道可以无错误传递的最大字母序列个数

可达性的证明

可达性的证明也就是我们可以找到一个编码函数和解码函数，使得信道带到容量C，而且是无差错地传输。 W∈[1:2nR]→Xn∼PX(x)→q(y|X)→YnŴ W \in [1:2^{nR}] \rightarrow X^n \sim P_X(x) \rightarrow q(y|X)\rightarrow Y^n \hat W