Binary Symmetric Channel

The forward transition matrix of a binary symmetric channel can be expressed as:

$$\mathbf{Q} = \left[ \begin{array}{ccc} 1-p & p \\ p & 1-p \\ \end{array}\right],$$

where $p$ is the cross over probability.

The unconstrained capacity is defined as:

$$C = \max_{\mathbf{p}}{I(X,Y)}$$ (1)

and is maximized to:

$$C = 1 - \mathcal{H}(p),$$ (2)

when the input distribution is uniform distribution: $p^* = [0.5,0.5]^T$ .

For a special case when the cross-over probability $p=0$ , i.e., all bits are transmitted reliably, $C = 1-\mathcal{H}(0) = 1\ bits/c.c$ .

Given an expense schedule $\mathbf{e}$ , and a constraint on the average expense of input $\sum_{x}{p(x)e(x)}\leq E$ , the constrained capacity can be defined as:

$$C(E) = \max_{\mathbf{p}\in P_E} {I(X;Y)} = \max_{\mathbf{p}\in P_E} {I(\mathbf{p};\mathbf{Q})},$$ (3)

where $P_E$ is the constrained set and is defined as:

$$P_E = \left\lbrace \mathbf{p}: p(x)\geq 0, \sum_{x}{p(x)}=1, \overline{E}=\sum_{x}{p(x)e(x)} \leq E \right\rbrace$$ (4)

If the expense schedule is set to $e=[0\ 1]^T$ for the BSC, we have $E_{min}=0$ when $\mathbf{p}=[1,\ 0]^T$ , i.e., only $X=0$ is transmitted to avoid any expense on transmission. Thus we expect that the corresponding channel capacity $C_{min}=0$ because no information is conveyed in the transmission. Likewise, $C_{max}=1-\mathcal{H}(p)\ bits/channel\ use$ is achieved when $p^*_{\ E_{max}}=p^*=[0.5\ 0.5]^T$ . And $E_{max}=0.5$ .

For any $E\in[E_{min},\ E_{max}]$ , since $p^*=[1-\alpha,\ \alpha]^T$ , we have $\alpha=E$ , therefore $p^*=[1-E,\ E]^T$ . And the corresponding channel capacity can be expressed as

$$C=I(\mathbf{p};\mathbf{Q})=\sum_{x}{p_x {\sum_{y} {p_{y\vert x}\log{\frac{p_{y\vert x}}{p_y}}}}}\ .$$ (5)

Figure 3 shows the result obtained by running the Blahut algorithm in the binary symmetric channel case, and $e=[0,\ 1]^T$ . Different cross-over probabilities are tried and plotted on the same figure.

Figure 3: Capacity Expense Curve of Binary Symmetric Channel for different cross-over probabilities. $e=[0\ 1]^T$