3
$\begingroup$

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$?

$\endgroup$
6
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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!! $\endgroup$ – CristoJV Oct 6 '17 at 13:59
  • $\begingroup$ @Cristo see my update $\endgroup$ – AlexTP Oct 6 '17 at 15:41
  • $\begingroup$ @Cristo you may be interested in Dilip Sarwate's approach, which is much natural, to prove the complemented probability of $L$-cascade BSC. $\endgroup$ – AlexTP Oct 10 '17 at 9:31
2
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.