0
$\begingroup$

Today we talked about Information Theory and the binary symetric channel.

For newbies here is a little explanation :

enter image description here

For instance if I want to send a binary to someone :

The bit will be "flipped" with a "crossover probability" of p, and otherwise is received correctly.

Example :

enter image description here

Note that in order to reduce the probability of the "flip" we repeat the bit 2,3,4... times. Here we use a R3 encoding cause the bit is repeated 3 times. Then to decide the transmitted bit we choose the most popular in this packet of 3 bits (in this case).

Up to here it's ok but i'm struggling with a question of my homework :

Let's suppose we use a R3 encoding, what's the probability a bit will be flipped ?

Thanks !

$\endgroup$
1
  • 2
    $\begingroup$ If you are stuck, try writing out all the cases, the probability that each one occurs, and then calculate the probability of incorrect decoding by summing things up. There are not that many for $R_3$! You can be systematic and treat things like $000 \to 100, 000 \to 010, 000 \to 001$ together. $\endgroup$ Sep 22 '20 at 20:18
1
$\begingroup$

R3 encoding is a pair of algorithms:

  • Encoding: a bit $b \in \{0,1\}$ is encoded as the packet $bbb$.
  • Decoding: a packet $xyz \in \{0,1\}^3$ is decoded as the majority bit (the bit occurring most often).

Since the situation is symmetric, in order to understand the transmission error, it suffices to consider the case $b = 0$. Suppose we encode the bit $0$. So we transmit the packet $000$. Every bit is flipped with probability $p$, and this gives us a distribution on the received packet $xyz$. Finally, a transmission error occurs if $xyz$ is decoded as $1$, that is, if the majority of $xyz$ is $1$.

Therefore, the transmission error is the probability of the following event:

If $x,y,z \in \{0,1\}$ are independent identically distributed bits such that $\Pr[x=1] = p$, what is the probability that the majority of bits in $x,y,z$ is $1$?

You can compute this probability by brute force.

$\endgroup$
1
  • $\begingroup$ Ho thanks I was working with binomial theoreme but I'll try your solution thanks ! $\endgroup$ Sep 24 '20 at 19:18

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.