Binary Symmetric Channel Video Lecture - Electronics and Communication

we're going to take a look at the binary
symmetric channel which is abbreviated
BSC this is a model for a communication
channel and it is defined by a parameter
called P sub e the probability of error
of the channel and basically this BSC
lets us model transmitting bits over a
channel that have some probability of
arriving or being decoded at the
receiver in error so it's basically
defined by this conditional probability
the probability I've listed here is the
probability that our receiver decides a
zero was transmitted given that a one
was transmitted so this would be an
error if I actually sent a one but
received a zero that's an error and that
probability in this model is equal to
the probability that my receiver
receives a 1 given that a zero is
transmitted so that's why we use the
word symmetric channel because these two
different probability of errors are
actually equal and they're equal to P
sub e so these are the errors that can
occur when I transmit data over this
channel similarly there's a probability
of being correct so if I actually
transmit a zero receive a 0 or if I
transmit a binary one receive a binary
one that those would be correct
decisions so those are equal to 1 minus
the probability of error because these
conditional probabilities have to sum to
1 so in my probability of making an
error is P sub E the probability of
being correct is 1 minus that
probability we can represent this
channel in a figure like this this kind
of butterfly diagram on the Left we have
the transmitter and on the right we have
the receiver and I can think about
transmitting bits across this channel so
if my transmitter actually transmits a 0
if my receiver receives a 0
well that occurs with probability 1
minus P sub e so we've labeled that edge
of the graph with the probability 1
minus P sub E so this is kind of a
correct decision path the other correct
decision path is on the bottom if we've
transmitted a 1 and received a 1 that
occurs with probability 1 minus P sub E
the cross terms
after the error probabilities so if I
transmit a zero but receive a one that's
an error which we denoted had error
probability piece of e and then finally
if I transmit a one but receive a zero
that's the same probability of error PCP
so this is how we can kind of picture
mathematically what the binary symmetric
channel looks like and all that's doing
is capturing probabilities of receiving
bits given certain bits were transmitted
and this is done one at a time if I
transit one bit what's the probability
of error or the probability of being
correct at the receiver what we would
like to do is we would like to transmit
n bits so instead of thinking of
transmitting just one bit let's think of
transmitting n bits in succession so
transmit a bit transmit another bit
transmit another bit until we have
transmitted n bits and what we're
interested in computing is what is the
probability that out of all n bits
transmitted that K of them are receiving
error so maybe just to be concrete maybe
you want to think of n as being 10 and K
is being 2 so if I actually transmit 10
bits down this channel in succession
what is the probability that two of them
are an error so what this should make us
think of essentially is Bernoulli trials
if you remember back to the charts on
Bernoulli trials Bernoulli trials were
repeated and it was concerned with
computing probabilities of having K
successes out of the n trials so it's a
little weird right here because
Bernoulli use the the verbage success
where as what we're looking for here is
error but don't keep be confused by that
really what the Bernoulli trial is doing
is it was saying given I've done
something N times did I see some event K
times so that's what we're doing here
given that I've transmitted bits n times
did I see the event I got an error K
times so that's what we're really
wanting to compute here so we have a
easy way to write this probability if I
want to compute the probability that K
errors have occurred out of the N bits I
can write this down very easily just
using my Bernoulli trial expression so
that error is n choose K times P sub e
to the K times
one minus P sub e to the N minus K so
this is a general expression for the
probability that K errors have occurred
out of the n bits and remember this
formulation does not care about where
these caterers have occurred so if I was
transmitting ten bits if n was equal to
ten this is the probability that
accounts for all different arrangements
of K errors so maybe the first K or an
error may be the last K bits were an
error maybe with some random assortment
of the n bits k of them were an error
this accounts for all permutations of k
out of the n so let's let's actually
plug in specific numbers just to make
this a little more concrete what if n
was equal to 8 my probability of error
on a single bit transmission was 10 to
the negative 5 and I was worried about K
equals 2 what's the probability of 2 out
of my 8 bits being an error so if I plug
that in that turns into a choose 2 10 to
the negative fifth to the squared 1
minus 10 to the negative fifth to the 6
because n minus K is equal to 6 so I can
write that out 8 choose 2 is 8 factorial
over 2 factorial times the difference of
8 & 2
8 minus 2 is 6 6 factorial 10 to the
negative fifth squared is 10 to the
negative 10 and then 1 minus 10 to the
negative 5th to the 6 so if I plug this
into my calculator I get a number that
is approximately 2.8 times 10 to the
negative 9 so I have computed the
probability of two of my bit errors two
of my bits being an error out of the
eight and again this calculation assumes
that all of these trials are independent
that was one of the assumptions in the
Bernoulli formulation we're assuming as
I transmit each bit each bit that I
transmit in turn the probability of
error is independent from transmission
to transmission so this is a very nice
general expression for computing this
probability of error and we've
specifically evaluated it just to make
it a little more concrete for this
example and obtain this number