Skip to main content
7 of 8
added 1 character in body
user827822
  • 319
  • 1
  • 10

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

user827822
  • 319
  • 1
  • 10