Skip to main content
explicit manipulation
Source Link
AlexTP
  • 6.7k
  • 2
  • 21
  • 38

A binary symmetric channel (BSC) can be characterized by its complemented probability $p$. Its well-known capacity is

$$C = 1 - H(p) = 1 - (-p\log(p) - (1-p)\log(1-p))$$

where $H(p)$ is binary entropy function:

enter image description here


A $L-$concatenated BSC, which is also a BSC characterized by $p_L$, can be visualized as in the figure below

L concatenated BSC

The complemented probability $p_L$ is derived

\begin{align} p_L &= p_{L-1} (1-p) + (1-p_{L-1}) p \\ &= p + (1-2p)p_{L-1} \end{align}\begin{align} p_L &= p_{L-1} (1-p) + (1-p_{L-1}) p \\ &= p + (1-2p)p_{L-1}\\ \implies 1 - 2 p_L &= (1-2p)(1-2p_{L-1}) \\ \implies 1 - 2 p_L &= (1-2p)^L \\ \end{align}

Thus $$p_L = \frac{1}{2}(1 - (1-2p)^L)$$

If $p=0$ then $p_L = 0$, $H(p_L) = 0$ and $C = 1$.

If $p=1$ then $p_L = 0$ or $p_L = 1$ depending on $L$ is pair or impair; $H(p_L) = 0$ and $C = 1$.

If $0 < p < 1$ then $\lim_{L \to \infty} p_L = 0.5$; $H(p_L) = 1$ and $C = 0$.

Conclusion: if the unit BSC is not certain $(p \neq 0, 1)$, the capacity of infinitely-concatenated BSC tends to $0$.

A binary symmetric channel (BSC) can be characterized by its complemented probability $p$. Its well-known capacity is

$$C = 1 - H(p) = 1 - (-p\log(p) - (1-p)\log(1-p))$$

where $H(p)$ is binary entropy function:

enter image description here


A $L-$concatenated BSC, which is also a BSC characterized by $p_L$, can be visualized as in the figure below

L concatenated BSC

The complemented probability $p_L$ is derived

\begin{align} p_L &= p_{L-1} (1-p) + (1-p_{L-1}) p \\ &= p + (1-2p)p_{L-1} \end{align}

Thus $$p_L = \frac{1}{2}(1 - (1-2p)^L)$$

If $p=0$ then $p_L = 0$, $H(p_L) = 0$ and $C = 1$.

If $p=1$ then $p_L = 0$ or $p_L = 1$ depending on $L$ is pair or impair; $H(p_L) = 0$ and $C = 1$.

If $0 < p < 1$ then $\lim_{L \to \infty} p_L = 0.5$; $H(p_L) = 1$ and $C = 0$.

Conclusion: if the unit BSC is not certain $(p \neq 0, 1)$, the capacity of infinitely-concatenated BSC tends to $0$.

A binary symmetric channel (BSC) can be characterized by its complemented probability $p$. Its well-known capacity is

$$C = 1 - H(p) = 1 - (-p\log(p) - (1-p)\log(1-p))$$

where $H(p)$ is binary entropy function:

enter image description here


A $L-$concatenated BSC, which is also a BSC characterized by $p_L$, can be visualized as in the figure below

L concatenated BSC

The complemented probability $p_L$ is derived

\begin{align} p_L &= p_{L-1} (1-p) + (1-p_{L-1}) p \\ &= p + (1-2p)p_{L-1}\\ \implies 1 - 2 p_L &= (1-2p)(1-2p_{L-1}) \\ \implies 1 - 2 p_L &= (1-2p)^L \\ \end{align}

Thus $$p_L = \frac{1}{2}(1 - (1-2p)^L)$$

If $p=0$ then $p_L = 0$, $H(p_L) = 0$ and $C = 1$.

If $p=1$ then $p_L = 0$ or $p_L = 1$ depending on $L$ is pair or impair; $H(p_L) = 0$ and $C = 1$.

If $0 < p < 1$ then $\lim_{L \to \infty} p_L = 0.5$; $H(p_L) = 1$ and $C = 0$.

Conclusion: if the unit BSC is not certain $(p \neq 0, 1)$, the capacity of infinitely-concatenated BSC tends to $0$.

Source Link
AlexTP
  • 6.7k
  • 2
  • 21
  • 38

A binary symmetric channel (BSC) can be characterized by its complemented probability $p$. Its well-known capacity is

$$C = 1 - H(p) = 1 - (-p\log(p) - (1-p)\log(1-p))$$

where $H(p)$ is binary entropy function:

enter image description here


A $L-$concatenated BSC, which is also a BSC characterized by $p_L$, can be visualized as in the figure below

L concatenated BSC

The complemented probability $p_L$ is derived

\begin{align} p_L &= p_{L-1} (1-p) + (1-p_{L-1}) p \\ &= p + (1-2p)p_{L-1} \end{align}

Thus $$p_L = \frac{1}{2}(1 - (1-2p)^L)$$

If $p=0$ then $p_L = 0$, $H(p_L) = 0$ and $C = 1$.

If $p=1$ then $p_L = 0$ or $p_L = 1$ depending on $L$ is pair or impair; $H(p_L) = 0$ and $C = 1$.

If $0 < p < 1$ then $\lim_{L \to \infty} p_L = 0.5$; $H(p_L) = 1$ and $C = 0$.

Conclusion: if the unit BSC is not certain $(p \neq 0, 1)$, the capacity of infinitely-concatenated BSC tends to $0$.