1
$\begingroup$

If you transmit a sequence of bits over some line, errors may creep in. For instance, if the Bit Error Rate of this line is 1%, on average, every 1 out of 100 bits will flip to the opposite value.

For a single transmitted bit, this relates to a Bernoulli trial with $p=0.99$ for being a 'success' and $q=1-p=0.01$ for a failure.

If this same bit is transmitted over two identical lines, there are two pathways of getting a correct result: two correct transmissions or two wrong transmissions (flipping the bit twice). The probability, therefore, is $p*p+q*q$.

Following this sequence for multiple transmissions, we get:

$$ \begin{array}{r¦c¦c} \textbf{ }&\textbf{correct}&\textbf{wrong}\\ \textbf{1}&p&q\\ \textbf{2}&p^{2}+q^{2}&2pq\\ \textbf{3}&p^{3}+3pq^{2}&3p^{2}q+q^{3}\\ \textbf{4}&p^{4}+6p^{2}q^{2}+q^{4}&4p^{3}q+4pq^{3} \end{array} $$

The parameters in front of each term seem to relate to Pascal's triangle. Furthermore, the 'correct' descriptions are 'symmetric' in q (even exponents), while the 'wrong' ones are 'anti-symmetric' (odd exponents). Can somebody explain the connection, and is there perhaps a general function which describes this series?

My real question is the following: what if the bits are transmitted across different lines $i$ each with a different BER $p_i$. The table then becomes:

$$ \begin{array}{r¦c¦c} \textbf{ }&\textbf{correct}&\textbf{wrong}\\ \textbf{1}&p_{1}&1-p_{1}\\ \textbf{2}&2p_{1}p_{2}-p_{1}-p_{2}+1&p_{1}-2p_{1}p_{2}+p_{2}\\ \textbf{3}&4p_{1}p_{2}p_{3}-2p_{1}p_{2}-2p_{2}p_{3}-2p_{3}p_{1}+p_{1}+p_{2}+p_{3}&etc. \end{array} $$

Is there a general function which describes this behaviour? Can someone explain anything more about this series? Does this have a name?

$\endgroup$
1
$\begingroup$

In the case of the repeated Bernoulli trials with identical probabilities, I believe the connection between this concept and Pascal's triangle can be visualised using the following graph.

Pascal's pathways

If we start at the top and define 'correct' to be a step to the right (bit does not flip) and 'wrong' to be a step to the left (the flipping of a bit), we can see there are 4 pathways to arrive at a 'wrong' result where the bit has flipped only once.

Similarly, there are 6 ways to arrive at a 'correct' bit which has flipped twice within 4 transmissions.

Therefore, the total probability of getting a correct answer is the sum of alternating Pascal's numbers, starting at the far right, moving to the left, each time skipping one number, and multiplying by the appropriate $p$'s or $q$'s.

This is the link with the 'symmetry' and 'anti-symmetry' mentioned in the original post.

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