台交大信息论 Lecture 9

这次回顾第九讲，这一讲主要介绍了数据传输和信道容量，对应视频15，16。

一个数据传输系统，由如下特征描述
- $W$表示传输消息。
- $X^n=(X_1,\ldots, X_n)$表示信道输入符号$W$对应的码字。
- $Y^n=(Y_1,\ldots, Y_n)$表示由于信道输入$X^n$而接收到的向量。
- $\hat W$表示从$Y_n$重构的消息。

离散通信信道由如下特征描述

离散无记忆信道(DMC)是转移分布序列$P_{Y^n| X^n}$满足如下条件的信道（对每个$x^n\in\mathcal X^n, y^n\in \mathcal Y^n,n=1,2\ldots$）。

$P_{Y^n|X^n}(y^n|x^n) =\prod_{i=1}^n P_{Y|X}(y_i|x_i)$

即DMC可以由转移概率分布矩阵$\mathbb Q:=[p_{x,y}]\in \mathbb R^{|\mathcal X|\times |\mathcal Y|}$描述，该矩阵满足

$\sum_{y\in \mathcal Y}p_{x,y}=1,\forall x\in \mathcal X$

假设$|\mathcal X| =|\mathcal Y|$，恒等（无噪声）信道的定义如下

$P_{Y|X}(y|x)=\begin{cases} 1& y=x\\ 0& y\neq x \end{cases}$

$\varepsilon\in [0,1]$被称称为信道交叉概率或误码率。
信道的转移概率矩阵为
$\begin{aligned} \mathbb Q &= [p_{x,y}]\\ &=\left[ \begin{matrix} P_{Y|X}(0|0) & P_{Y|X}(1|0)\\ P_{Y|X}(0|1) & P_{Y|X}(1|1) \end{matrix} \right]\\ &=\left[ \begin{matrix} 1-\varepsilon & \varepsilon \\ \varepsilon & 1-\varepsilon \end{matrix} \right] \end{aligned}$
$\varepsilon=0$退化为恒等（无噪声）信道。

在BEC中，接收器知道接收到的比特流或码字中错误的比特的确切位置，但不知道它们的实际值。
这些错误比特在传输过程中被声明为“擦除”。
信道的转移概率矩阵为
$\begin{aligned} \mathbb Q &= [p_{x,y}]\\ &=\left[ \begin{matrix} P_{Y|X}(0|0) &P_{Y|X}(E|0) & P_{Y|X}(1|0)\\ P_{Y|X}(0|1) &P_{Y|X}(E|1)& P_{Y|X}(1|1) \end{matrix} \right]\\ &=\left[ \begin{matrix} 1-\alpha & \alpha & 0 \\ 0 & \alpha & 1-\alpha \end{matrix} \right] \end{aligned}$
其中$0\le \alpha \le 1$被称为信道的擦除概率。

BSC与BEC结合，可以得到一个既有错误又有擦除的二进制信道。
通道的转移概率矩阵为
$\begin{aligned} \mathbb Q &= [p_{x,y}]\\ &=\left[ \begin{matrix} P_{Y|X}(0|0) &P_{Y|X}(E|0) & P_{Y|X}(1|0)\\ P_{Y|X}(0|1) &P_{Y|X}(E|1)& P_{Y|X}(1|1) \end{matrix} \right]\\ &=\left[ \begin{matrix} 1-\varepsilon- \alpha & \alpha & \varepsilon \\ \varepsilon & \alpha & 1-\varepsilon -\alpha \end{matrix} \right] \end{aligned}$
其中$\varepsilon, \alpha\in [0,1]$是信道的交叉概率和擦除概率。
$\alpha=0$时退化为BSC，$\varepsilon=0$时退化为BEC。
更一般的，$\mathbb Q$可以推广为
$\begin{aligned} \mathbb Q &= [p_{x,y}]\\ &=\left[ \begin{matrix} P_{Y|X}(0|0) &P_{Y|X}(E|0) & P_{Y|X}(1|0)\\ P_{Y|X}(0|1) &P_{Y|X}(E|1)& P_{Y|X}(1|1) \end{matrix} \right]\\ &=\left[ \begin{matrix} 1-\varepsilon- \alpha & \alpha & \varepsilon \\ \varepsilon' & \alpha' & 1-\varepsilon' -\alpha' \end{matrix} \right] \end{aligned}$

给定整数$q\ge 2$，则$q$元对称信道是BSC的扩展；它具有大小$q$的字母$\mathcal X =\mathcal Y = \{0, 1,\ldots,q - 1\}$，信道转移矩阵为
$\begin{aligned} \mathbb{Q}&=\left[p_{x, y}\right] \\ &=\left[\begin{array}{cccc} p_{0,0} & p_{0,1} & \cdots & p_{0, q-1} \\ p_{1,0} & p_{1,1} & \cdots & p_{1, q-1} \\ \vdots & \vdots & \vdots & \vdots \\ p_{q-1,0} & p_{q-1,1} & \cdots & p_{q-1, q-1} \end{array}\right] \\ &= {\left[\begin{array}{cccc} 1-\varepsilon & \frac{\varepsilon}{q-1} & \cdots & \frac{\varepsilon}{q-1} \\ \frac{\varepsilon}{q-1} & 1-\varepsilon & \cdots & \frac{\varepsilon}{q-1} \\ \vdots & \vdots & \vdots & \vdots \\ \frac{\varepsilon}{q-1} & \frac{\varepsilon}{q-1} & \cdots & 1-\varepsilon \end{array}\right]} \end{aligned}$
其中$0\le \varepsilon \le 1$是信道的对称错误率。
当$q=2$时退化为BSC。

给定一个整数$q\ge 2$，还可以考虑BEC的扩展，产生所谓的$q$元擦除信道。具体的，该通道的输入和输出字母分别为$\mathcal X = \{0, 1,\ldots,q - 1\}$和$\mathcal Y = \{0, 1,\ldots,q - 1， E\}$，其中$E$表示擦除，信道转移分布为
$P_{Y \mid X}(y \mid x)=\left\{\begin{array}{ll} 1-\alpha & \text { if } y=x, x \in \mathcal{X} \\ \alpha & \text { if } y=E, x \in \mathcal{X} \\ 0 & \text { if } y \neq x, x \in \mathcal{X} \end{array}\right.$
其中$0\le \alpha \le 1$为擦除概率。
当$q=2$时退化为BEC。