# Capacity of cascade binary symmetric channels

Let's imagine that we have interconnected in cascade $L$ binary symmetric channels each with the same transition probability $p(y|x) \in \{p, q=1-p\}$, where the output of each BSC is connected to the input of the next.

The overall channel is also a BSC channel, but what happens as $L \to \infty$?

## 3 Answers

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: A $L-$concatenated BSC, which is also a BSC characterized by $p_L$, can be visualized as in the figure below 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$.

• Wow @AlexTP . Incredible answer but how did you get from: p_L =p+(1-2p)p_{L-1} To: p_L = \frac{1}{2}(1 - (1-2p)^L) ? Thank you!! – CristoJV Oct 6 '17 at 13:59
• @Cristo see my update – AlexTP Oct 6 '17 at 15:41
• @Cristo you may be interested in Dilip Sarwate's approach, which is much natural, to prove the complemented probability of $L$-cascade BSC. – AlexTP Oct 10 '17 at 9:31

A cascade of $L$ binary symmetric channels (BSCs) with cross-over probability $p$ is the same as a single BSC with cross-over probability $$p_L = \left.\left.\frac 12 \right(1 - (1-2p)^L\right).\tag{1}$$ To get to $(1)$, note that the cascaded BSC output is incorrect if and only if the transmitted bit was flipped an odd number of times as it traversed the cascade; even numbers of flips result in error-free transmission in accordance with the age-old principle that two wrongs make a right. The number of flips is a Binomial$(L,p)$ random variable $X$ for which \begin{align} P(X ~\text{odd}) &= \sum_{i=1,3,5,\ldots}\binom{L}{i}p^i (1-p)^{L-i}\\ &= ~~~\frac 12\left(\sum_{i=1,3,5,\ldots}\binom{L}{i}p^i (1-p)^{L-i} + \sum_{i=0,2,4,\ldots}\binom{L}{i}p^i (1-p)^{L-i}\right)\\ & ~~~~+ \frac 12\left(\sum_{i=1,3,5,\ldots}\binom{L}{i}p^i (1-p)^{L-i} - \sum_{i=0,2,4,\ldots}\binom{L}{i}p^i (1-p)^{L-i}\right)\\ &= \frac 12\left(\sum_{i=0}^L\binom{L}{i}p^i (1-p)^{L-i} - \sum_{i=0}^L \binom{L}{i}(-p)^i (1-p)^{L-i} \right)\\ &= \left.\left.\frac 12 \right(1 - (1-2p)^L\right). \end{align} As AlexTP points out, $p_L \to \frac 12$ for all $p \in (0,1)$, and so the non-trivial cascaded BSC has capacity approaching $0$ as $L \to \infty$.

This answer is a bit late, but the problem has quite an elegant solution based on the Fourier transform and I wanted to add it.

The action of the BSC can be modeled as a$$\pmod 2$$ sum of the data bit, $$X$$, and a random noise bit, $$N$$, who's probability distribution is $$P(N=0)=1-p$$ and $$P(N=1)=p$$,

$$Y = X \oplus N.$$

The distribution over the output, $$Y$$, is a convolution of the quantities $$P(X)$$ and $$P(N)$$,

$$P(Y=y) = \sum_{x \in \{0,1\}} P(X=x)P(N=x\oplus y).$$

This is a linear transformation of the probabilities. The circulant convolution matrix obtained from one of the vectors is diagonalized by the 2x2 DFT Hadamard matrix,

$$H = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix},$$

and the convolution becomes a product of spectra in the transform domain. The sum of $$L$$ identically distributed noise bits corresponds to exponentiation in the transform domain followed by an inverse transform,

$$H^{-1}\left(H\begin{bmatrix}1-p\\p\end{bmatrix}\right)^L = \frac{1}{2}\begin{bmatrix}{1 + (1 - 2p)^L}\\{1 - (1 - 2p)^L}\end{bmatrix},$$

where the second element of the result vector represents the probability $$P(N_1 \oplus N_2 \oplus N_3 \oplus \ldots \oplus N_L = 1)$$, which is the flip probability for the cascaded BSC.