Errors, Channel Codes - Electronics and Communication Engineering Video Lecture | Electrical Engineering Optional Notes for UPSC

the following content is provided under
a Creative Commons license your support
will help MIT OpenCourseWare continue to
offer high quality educational resources
for free
to make a donation or view additional
materials from hundreds of MIT courses
visit MIT opencourseware at ocw.mit.edu
I wanted to give you an overview of what
the system is that we're talking about
the communication network we have a
source that's trying to communicate to a
receiver we've talked about converting
while we'll talk more some more actually
about converting the source information
to binary digits and then where we've
spent a lot of time is talking about
source coding which is trying to extract
the redundancy in the message that you
want to send so that basically every
binary digit you then put on the channel
carries as much information as possible
so now I'm going to really stop making a
distinction between bits and binary
digits I'll just say bits when I might
mean binary digits but once you're into
the system here and you've done your
source coding a binary digit carries a
bit of information in general right if
you've done a good job of extracting the
redundancy so we're talking about a bit
stream here that you're trying to get
across to the other end at the other end
the bit stream is received there's a
decoding step which is what we've seen
with Huffman or lzw the decoding N and
then you do whatever it is you're going
to do in the application so we've really
said all we're going to say about source
coding and decoding and the rest of what
we're going to do is focus on what
happens inside here okay
now what happens inside there at some
stage involves physical communication
link so you might be talking about bit
streams at either end but somehow you've
got to deal with the fact that most of
these channels most of the channels of
interest they're physical channels they
work with continuous valued continuous
time quantities for instance the voltage
on a cable might be used to transmit
information light on the fiber
electromagnetic waves through space
acoustic waves in air or water in fact
acoustic waves in air is something
you'll see a lot of when you come to the
later labs indentations on VIN aisle or
plastic let's see that's records or CDs
and that actually brings up a point we
don't often think of storage as being
communication but storage is really
communication with potentially a very
long time delay in the channel right you
put something on the storage medium and
then weeks or months or years or
centuries later you're trying to extract
that information so we can still think
of all of this as the communication
channel and decoding ideas are essential
to making CDs work to having a CD
resistant to scratches and thumb prints
and everything else that all the other
indignities that they're subject to
magnetization so all of these physical
modalities that are used to translate
information here's one you may not have
thought about mud pulse telemetry so
when you're drilling for oil you'd like
to get information from the drill bit of
the bottom and normal electronics
doesn't work too well because the
temperatures are fiercely hot down there
you need that information to help you
steer the drill bit to get information
about what sort of rock you're going
through and all of that so they actually
seriously do use pressure pulses in the
slurry
schooling the drill bit to try and
convey information back to the top okay
so they'll modulate the pressure down at
the end of the drill bit and hope that
you can detect it at the top oh one word
over there that stands out is they talk
about digital information so even in the
context of communicating through mud
they're thinking about how to actually
have bits that they communicate on this
analog channel so this is very much in
the flavour of what we're trying to do
we're trying to communicate digital
information this is sequences of numbers
or sequences of signs or symbols but
we're trying to do it over a physical
channel that takes continuous valued
continuous-time waveforms so that's
really some of what we'll be talking
about so the kind of link that we have
starts off with bits but in the middle
has to deal with the physical link on
which you have signals will refer to
these continuous-time waveforms they're
not always continuous time you could
sample them and get discrete-time
waveforms as well but the signals that
you see in the physical medium will
refer to the quantities you see in the
physical medium will refer to as signals
you need some way to map the bits to the
signal so you've got a bit sequence you
need to convert it to a continuous time
waveform in some fashion and then at the
other end to recover the bit stream and
you might do that by some sampling and
processing and then translation process
back
the little lightning there is meant to
suggest that you're subject to all sorts
of noise and disturbances when you're on
that physical link so that's something
that's critical to design of the system
you have to design your overall system
so that you're robust to perturbations
in that middle section okay so the
particular application is beginning with
your specifics and with producing a bit
stream that's got the redundancy mapped
out of it at this point is it doesn't
matter to me for communication across
the channel what that bit stream is
where it came from
I'm just trying to do a good job of
delivering it to the other end where the
user can extract that now here's the
funny thing that we've just done a lot
of work to extract redundancy from the
messages here we're going to put
redundancy back in because the way you
guard against disturbances in the
channel is by introducing redundancy you
need to give yourself a little room to
recognize that something bad has
happened to your signal or something bad
has happened to the data you're sending
across and then to recover from it so we
will actually be talking about how to
reintroduce redundancy but this is
introducing it now in a bit stream where
the binary digits are essentially
equally likely you pulled out all the
application-specific knowledge and used
it to do the source coding now you've
just got a stream of zeros and ones each
one carrying a bit of information
presumably and now you want to protect
it for transport across the channel and
you're going to do that by putting in
additional bits okay so you're going to
introduce bits in a structured way to
provide some redundancy so we'll be
talking about that in more detail okay
so this is the single link picture
when you've got a network it's a little
different so I haven't shown all the
other lengths here but you you should
imagine of network with many possible
paths from a source to a destination
some of these links might come down and
so you'll want to find an alternative
path some of these links might be busy
and you want to find an alternative path
so there's a whole network of links in
here in this setting it turns out that
the good way to do this is to break up
your bit stream into what are called
packets these are you know maybe a
thousand bits or four thousand bits or
whatever your protocol is they're broken
up into packets of chunks of bits and
then treated as packets for transport
along the network so the point is that
one packet to a given user might travel
one particular route but another packet
might travel another route and then
these get reassembled at the destination
so you think in terms of packets when
you think in terms of routing on the
network this idea of packet
communication by the way there's a name
associated with that which is Kleinrock
again a PhD student at MIT and the in
the same Golden Ears that I keep
referring back to but it's it's a very
broad area so you've got the packets
those arrive at the links they're
actually switches here that decide which
of the links emanating from the switches
you want to send the packet on so again
imagine out the links I haven't drawn
them in so the packet gets treated as a
unit for shipping on the links but once
you've committed to a particular link
it's like transmitting on a single link
again so you've got to go through your
packets two bits two signals two bits
two packets transformation okay so it's
not that there's a particular
transformation and going from packets to
bits you're just viewing it differently
you're not treating it as a as a packet
you're looking in at each bit you're
looking to code each bit on an analog
signal get it across the physical medium
okay so that's really the the key to
this what we end up doing is coding or
mapping or the word modulating is used
and we'll see more of that we modulate
the desired bit sequence onto a
continuous time waveform so what you
might imagine is you you could have a
sequence 0 1 1 0 1 and what you're going
to do with your mapping is try and
generate a continuous time waveform
which in some fashion codes that
sequence and it could be very simple it
could be a voltage level of zero held
for some interval of time to represent
the 1 sorry to represent the zero held
for some time again to represent the
second symbol which is again a 1 and
then you come back down to 0 back to 1
again so it could be as simple as this
ok so this is now you can think of it as
some voltage we use the word voltage a
lot we we just mean an analog signal
we'll use the word voltage we think your
voltage on like cable but it could be
any analog signal so this is really the
digital signaling end of it so you take
the bit sequence represented now on
coated onto a continuous time wait for
more modulated onto a continuous time
waveform will see richer uses of that
word as we progress the particular
scheme I've shown here is what you'd
call a bi-level
signalling scheme the two voltage levels
that you use we refer to that also as
bipolar signalling although sometimes
that's restricted to the case where the
two voltage levels are opposite and sign
so you can imagine a signalling scheme
that uses this for zero this for one
okay and so this could be bipolar scheme
all right and then this continuous-time
waveform gets put on the physical
channel presumably gets distorted it
gets some noise added to it so the other
end you get some approximation to this
and then you've got to reconstruct the
bit sequence you might do that by
sampling this and processing the samples
and then taking some measure of the
waveform we'll see more of that later
you'll do that in lab 2 in labs as well
so in some fashion you recover from this
your estimate of the bit sequence but
you can imagine when a waveform like
this goes through a physical channel
with distortion noise and then we
sampling and processing and so on you
are likely to get errors back at the
receiving end okay ideally you would get
exactly this waveform at the receiving
end you'd have no trouble distinguishing
between the samples of the two levels
and you could reconstruct the bit
sequence okay
now we are going to in the middle
section of the score say a lot more
about the signals aspect of it but for
us now it's actually helpful to stick to
thinking in terms of bits
so we've got bits and bits out somewhere
in here we've got signals on the
physical channel signals noise physical
channel and then we've got whatever it
is that does the transformation from
bits to so this is some kind of a
transformer let's say from bits to
signals and from signals to bits but
let's look at an abstraction that's end
to end here bits to bits
if you say what's coming in as a bit
stream what you're receiving is a bit
stream okay and there's um there's an
idealization of this channel that's used
a lot and that's referred to as the
binary symmetric channel and what that
says is you get a 1 coming in that's
most likely going to be received as a 1
but there's some chance it's going to be
received as a 0 ok and you let's put
probabilities here I think the notes use
epsilon I seem to have used P little P
on my slide so let me stick to little P
okay so a one coming in is transferred
transformed in error to a zero with some
small probability presumably small with
one - B it's intact and then the same
thing on this side okay a zero comes in
with some probability comes out as a
zero but with some probability it
actually gets flipped to a one now we
use the word symmetric here to say that
we're is human
identical probabilities of going one to
zero or zero to one you can easily
imagine an unsymmetrical where you have
different probabilities in the two
directions but we'll stick to the
symmetric case binary of course because
we're dealing with binary sequences of
the two ends and what we're imagining is
that this is a memoryless channel in
other words I can look at this
transmission by transmission so a bit
comes in this is how the output is
determined and then the next bit comes
in and knows nothing there's no memory
in the system right it knows nothing
about what decision was made in the
previous case now you can imagine more
complicated channel models with memory
but this is a good starting point okay
so that's the binary symmetric Channel
okay so question now if we wanted to get
a bit stream over reliably any ideas on
how we can contract the effect of this P
probability of flipping yeah
well at this point I'm back to ones and
zeros there's no signals right the
signals are in here so what you're
thinking of maybe is how do I reliably
map bits to signals and what you're
saying is you can design your signaling
here in a way that reduces the P okay
the P that I'm thinking of here is the
end-to-end error probability if I design
the inner part better I might lower the
P but for a given P is there something
that I could be doing to improve my
chances of getting the bit across
correctly yeah sorry okay so the
suggestion is that we introduce your
done and C by just repeating it okay so
seven to one repeat the one repeated
many times if you need to and so what
would you suggest that the receiver
should do if you do a repetition like
this how should the receiver decide if I
send five ones in a row yeah
sorry sir
you're talking about requesting a retry
I'm not hearing well which
okay so you're using the word request
you're talking about the receiver
sending some thing back to the sender
but if we're with this channel and the
sender has to make its own decisions
about how do you think get things across
without a possibility of feedback
okay
okay okay so I think I understand better
now if you're repeating this the chance
of more than half of them being wrong is
very small I think that was the idea
that you had as well so repetition is
likely to reduce the chances that you'll
go wrong here if you use a majority rule
majority rule would be a simple rule
right send five repetitions and if only
two are flipped
well you just decided in favor of the
majority because it's more likely that
none or one or two are flipped and that
three or four or five or four okay so
that's the idea so this is what's called
a replication code and actually can work
very well so what you see on the
horizontal axis is the replication fact
that you can replicate at five times ten
times 15 times and here's the
probability of error and it actually
goes down and you can do the computation
this is actually a fairly simple
computation you're basically doing coin
tosses and seeing what's the probability
that more than half of the coins I flip
come up one way all right on your
counting that to decide how the majority
rule works I'm sorry for the epsilon
here it's supposed to be the P okay so
is this good good enough
yeah
the more you send the more you're
wasting wasting time on that one bit
right so this is the point that you can
do the replication and reduce your
probability of error but what's the
information you're getting across your
you were doing all of this to get that
one bit across reliably but you've got a
lot of bits backing up waiting to get
across okay so the the code rate the
rate at which information gets across is
a 1 over N if you do n replications if
you're doing n replications it's only 1
over n the rate at which you're getting
information across in terms of bits is 1
over n okay so you're dropping the
probability of error but you're also
dropping the transmission rate so this
is really unacceptable it turns out
though that we can do a lot better we
can do a lot better what I'm going to do
now is say a little bit about what
Shannon had to say about it I hope
you'll allow me to teach you about
something that we're not going to test
you on just so you can learn a little
bit about this and then I'll get back to
stuff that we will test you on okay is
that all right I know you didn't pay for
this but we'll do it anyway all right so
here's Shannon defining something that
the thermodynamics people and so on
didn't really think to do they may have
done it indirectly but it didn't horizon
where they were working with entropy and
all of them Shannon defined something
called mutual information given by this
symbol x and y are random variables
random quantities we know that H of X is
the entropy and X so it's our
uncertainty about X it's the expected
information when you're told something
about X this symbol denotes the
uncertainty and X given information
about Y okay so it's the conditional
entropy here and so what this is asking
is how much is our uncertainty about X
reduced by having information having a
measurement of Y
okay that's very relevant to a channel
where the input is X and the output is y
we're saying we see the output of the
channel we want to infer what happened
at the input what the input sent the
mutual information between these two
random variables surely has to be
important so what's the reduction in
uncertainty that results from having a
measurement of Y that's a question of
interest not just in communications as
such but in all sorts of inference
questions okay I'm gonna have a slide of
equations they might look scary but
actually they're very simple given what
you already know how to do first I have
to define for you what I mean by
conditional entropy so I'm saying it's
the entropy of X conditioned on having a
particular measurement of Y so suppose
you know that Y takes the value little Y
sub J you'd use the same formula that
we've used for entropy except you're
probabilities and are all now
probabilities conditioned on that
information so instead of just P of X I
you have P of X i given Y J so it's the
same formula but if you've been given
information then you have to conditioned
on it okay so that's the the definition
this is the conditional entropy given a
specific value for Y but if all I tell
you is I'm going to be giving you a
value for Y and I haven't told you the
value yet what's the conditional entropy
then what you want to do is average over
all possible Y's that you might get so
you're going to take this conditional
entropy for the given Y and then take
the weighted average with the
probabilities okay so that's how you
compute this quantity and it's quite
straightforward it's not very different
from what you have
okay and then if you put in what you
know about how joint probabilities and
conditional probabilities work this was
the definition of conditional
probability that we had and I think the
first lecture you discover that actually
this the joint entropy of these two
random variables can be factored in two
particular ways and that allows you to
deduce that the mutual information is
symmetric in other words the mutual
information between x and y is the same
as the mutual information between y and
x okay so there's no difference in that
that might be a little surprising given
that we were thinking of x as the input
to the channel and y is the output of
the channel but it turns out that that's
the case okay so let's actually compute
it for the channel that we know this is
the binary symmetric channel let's
compute the mutual information between
the input and output for the binary
symmetric channel so here's the
definition I XY we've just shown that
doesn't matter which order you take it
in and it turns out the computation is
easier if you flip the order so I'm
going to write this as uncertainty in Y
minus the uncertainty in Y given a
measurement of H of X sorry okay so I'm
going to compute it in that fashion
what's the uncertainty in Y
actually I should I should probably have
said here that let's let's assume X
takes 0 & 1 I might be wrong and saying
that this doesn't depend on the
distribution of the input let's assume 0
& 1 are equally likely at the input okay
if the 0 & 1 are equally likely at the
input
what's the uncertainty in Y is it a bit
of uncertainty it's equally likely to be
a 0 or 1
I had actually written that assumption
in and then I took it out but I think
I'm wrong in saying that ok so here we
have the 1 for the uncertainty and y
what about the uncertainty in Y given X
so I give you a particular value for X
let's say X is equal to 1 so I'll give
you a particular value for x
what's the uncertainty in Y well Y is 0
with probability little P and it's 1
with probability 1 minus P and that's
really the binary entropy function that
we had drawn last time so you can
actually work out all these pieces and
discover let's see here's the binary
entropy function just to remind you this
is for a coin toss if something can be 1
with probability P 0 with probability 1
minus P or the other way around the
entropy associated with that is H of P
and we have 1 minus H of P for the
mutual information between the input and
output of the binary channel so here's
what 1 minus H of P looks like
all right so what's a low-noise channel
a low-noise channel is one with a very
small value of P and what this says is
that the mutual information between the
input and output is on the order of one
bit okay so if you're told what Y is
you've got a very good idea what X is
that makes sense because it's a
low-noise channel but if you get to a
channel that has around 0.5 probability
of flipping the bit then the mutual
information is very small okay so it
doesn't reflect what you'd like to see
here's another notion which is entirely
Shannon which is the idea of channel
capacity and what he's saying now is in
order to characterize the channel rather
than the input or the output let's ask
what the maximal mutual information is
over all possible distributions that you
might have for X so I'm not going to
specify X being 0 on 1 with equal
probability if you go through that
computation you find that it's exactly
the shape that we had before it's
exactly for the binary symmetric channel
it happens to be exactly this curve okay
so the channel capacity for the binary
channel is exactly for the binary
symmetric channel is exactly this curve
okay so that gives us an idea of the
maximum information that you could be
transmitting across the channel now
that's just the definition but it turns
out to have some very practical
implications for how fast and how
accurately you can transmit data on a
channel and here's Shannon's result what
he says is that you can theoretically
transmit information at an average rate
below the channel capacity
with arbitrarily low error okay so
that's the shocking thing that as long
as you stay below channel capacity you
can transmit with arbitrary low error if
you try and get to channel Kappa if you
try and get to rates above that you're
going to run into trouble okay you can't
get that probability of error to vanish
now how do you do this well the
prescription is take long strings of
that input message stream take K bits of
that input message stream code it onto
it and larger than K code words send
that through the channel if n is very
large and K is very large the rate at
which you're transmitting is K over N
you can transmit at a rate K over N that
lives below C with as low an error as
you want the way to make the error
smaller is to take longer and longer
blocks okay
this was kind of an existence proof he
didn't actually show you specific
constructions necessarily in that proof
for how to introduce the redundancy to
make this happen but it was actually a
result that said you can't be satisfied
with the replication code you can do a
lot better and how much better you can
do is indicated by that channel capacity
okay let's come back to testable stuff
okay we're going to actually design ways
to introduce redundancy motivated by
this channel result for very practical
settings and a key notion we're going to
use is that of the Hamming distance
between two strings so the Hamming
distance you've seen this in some
recitations basically the having
distance between two strings
it's just a number of positions in which
the two strings does differ from each
other okay so the hamming distance here
between these two strings let's say
string 1
string2 is what one two three right
these strings different three positions
another way to think of it is how many
bits do I have to flip in one to get the
other one okay so how many hops does it
take in some sense to get from one to
the other all right
so here's how the notion of adding
redundancy comes in suppose we have a 0
or a 1 to send a cross this is our bit
for that transmission what we're going
to do is actually code it not a zero on
one but a 0 0 & 1 1 ok if we've got just
a single bit corrupted we go to
something that's not a code word we go
from 1 1 to 0 1 or 2 1 0 or we go from 0
0 to 0 1 or 1 0 we receive something
that's not a code word that allows us to
detect that an error was made okay so
what we've essentially done is in
Hamming distance we've introduced some
distance between the code words that
we're using to transmit on the channel
it takes two hops to get from one code
word to the other there's a Hamming
distance of 2 and therefore if you only
have a single bit error when you
transmit on the channel you're not going
to get all the way to another code word
you won't be at any code word you
recognize and you'll know that you made
in there ok so this is an example of how
you start to introduce redundancy in the
stream so that you can detect and
perhaps even correct errors here's
another example now this is these by the
way are still looking like replication
codes because to send a 0 we're
repeating 0 3 times and to send a 1
we're repeating 1 one time but we're
going to do more elaborate versions of
this that I'm not replication codes okay
but imagine now I've drawn the corners
of a cube each circle here across on
edge is having distance 1 from the
adjacent one right so to go from the
sequence that I'm using to represent a
zero to the sequence that I use to
represent a 1 I've got to do one two
three hops there's a Hamming distance of
3 there
okay so if I had only a single bit error
is it possible for me to correct if I
know that my errors are limited to
single bit errors can I correct when I
receive an incorrect string if I start
with 0 0 0 and I have a single bit error
I can only go to these adjacent vertices
and those are not going to be confused
with vertices that are one-step adjacent
to the 1 1 1 okay so I'll know that I've
made an error and I'll know to correct
it back to 0 0 0 provided I know that
only 1 error has been made ok now I
might just assume that only one error
has been made and so once in a while
I'll think I'm correcting but I'll be
getting something wrong and that has to
be contended with and calculated but
this is the basic idea okay
more generally what we're thinking about
is taking Kay message bits so this
corresponds to 2 to the K possible
messages we're going to embed this in
and bit code words where n is greater
than K so if you imagine a
generalization of this picture what
we've got is a hypercube with 2 to the N
possible nodes corresponding to all the
possible combinations here
we're going to assign two to the K of
those nodes two codewords
and the rest will be left free to just
leave some space between the code words
okay
the rate of the code then the rate of
the code is how many message bits are
you getting across it on average per
transmission and so the rate is going to
be K over N because for every n bits
that you send you're getting across K
bits of information this K message bits
and every end transmitted bits right
so here's the general statement
in terms of having distance and what you
can do with the code so first of all
I've got a set of code words what's
really important is what's the minimum
Hamming distance between my code words
because that's the point of greatest
vulnerability that's where I'm most
likely to get confused okay so if you
give me a set of code words I can look
at the Hamming distance between any two
of them I've got to search all these
pairs and find out which is a minimum
having distance that's the point of
maximum vulnerability okay and this is
what we're calling D little D okay so
the picture I like to think about is
I've got some valid code word here I've
got some other valid code word here
and if I told you that over all the code
words in my set the minimum Hamming
distance I find is three what that means
is I've got to do three hops to get to
the other codeword right this hop means
I've changed one bit in the valid
codeword to get to some other sequence
not a codeword and then one bit to get
to this one and one more bit to get to
this one and this is now another valid
codeword okay so if I say the minimum
Hamming distance of three that means
that you will find a pair of code words
with these three hops to get you from
one to the other
okay
how many errors can you detect with a
code like this so you send a valid
codeword across the channel bits get
flipped up to how many errors could you
detect without being fooled if I tell
you this less than or equal to e errors
how large can EB to guarantee that you
won't get the transmission of one valid
code word that ends up is another valid
codeword yeah sorry I'm talking about
about correction but about detection of
an error right how many errors could you
detect in this kind of a picture so I
can afford to have one error two errors
and the third error will bring me to a
valid codeword and I won't know that
I've made an error okay so if you want
to look at how many errors you can
detect it's what's given by the upper
one there D minus one okay so if the
minimum Hamming distance is D you can
detect up to D minus one errors what
about correction
how many errors could you correct here
can you correct any errors here up to
one right and then you can look at this
more generally and you see the general
formula is D minus one over to the floor
of that is that tells you how many
errors you can collect correct
so the minimum Hamming distance is
actually a key thing now how do you
build codes which have desired
characteristics so for instance suppose
you want to send four bit messages to K
equals four you want to have single
error correction so that means you want
this kind of a picture here you need
Hamming distance three at least
how will you produce a code all right so
this is not an obvious thing at all
here's an example of one that satisfies
the construction you need to actually
expand to sending seven bits so n is
equal to seven how many messages do we
have we have sixteen messages so that
corresponds to a K of four right two to
the four sixteen so we've got sixteen
different messages we could have counted
those messages with four bits but we're
going to add in redundancy to get seven
bits for a message resulting in these
code words these code words the set of
code words has the property that the
minimum Hamming distance is three so you
can correct up to a single error here
okay but it takes in principle it takes
a search and it's not necessarily easy
to do but we'll see how to do that
efficiently all right let me show you
how and this is something that you're
probably quite familiar with how by
making n equals k plus 1 you can already
suppose I choose n equals k plus 1 which
means I'm taking the message bit and
adding 1 bit okay we're going to add
what's called a parity bit and you can
do this in different ways but we're
going to do
let's see out what I'm going to do with
this is guarantee that the minimum
distance between valid code words is at
least 2
okay
so let's see how to do that and there'll
be some computation and not just the
parity calculations but other stuff will
do that builds on computations of zeros
and ones the computations are which
you've probably seen elsewhere with
boolean algebra this is what's called
computation and Galois field
- so GF - is another symbol you'll see 0
plus 0 is 0 1 plus 0 or 0 plus 1 is 1 1
plus 1 is 0 so this is like an exclusive
or addition and multiplication works in
the usual fashion so all our
computations are with zeros and ones and
you want to keep that in mind as we go
through this so here's what we do for a
simple way to add redundancy we will
take the message and add a single bit to
make the total number of ones in the
resulting code word even ok so this is
what's called even parity you could have
the opposite choice of odd parity so if
you now receive a code word with an odd
number of ones you know you've made a
mistake right how do I know that the
minimum Hamming distance is 2 in this
case
I have to be able to produce for you
some other code word that are I've had
with to helps
any ideas there so I give you a code
word which is the original message word
with the parity bit can I make two-bit
flips on that and get a new code word I
mean a valid code word because then I
could have then I have having distance
to write can you think of what to do
yeah
but that's not yet given me so the
suggestion was flip one of the bits okay
so okay good so if you flip for instance
an easy way to see this is flip one of
the message bits and flip the parity bit
for instance okay no that doesn't do it
does it yeah because then you've changed
to zeros - one or two ones to a zero and
your parity is wrong then okay so so you
can have a two bit error that ends up
not being detected but all single bit
errors will get detected that again
correlates with the fact that we said
the minimum Hamming distance is two the
number of errors you can detect is d
minus 1 that's 1 and the number of
errors you can correct
well it's D minus 1/2 the floor of that
and you can't correct any errors
all right now we're going to be building
more elaborate codes than parity or
replication these are going to be called
linear block codes sorry
and their different ways to set this up
here's one way to think of it if you're
comfortable with matrix multiplication
here's one way to think of it and we're
going to be using this actually so if
you aren't already comfortable with
matrix multiplication maybe you should
get comfortable soon what we have is a
vector here which has our message in it
okay so we stick our message in there
this is just a bunch of zeros and ones
I've got a matrix here which I call a
generator matrix generator matrix
and this is a matrix of zeros and ones
as well
and so on okay so we've got things in
there how do i generate my code words I
just put in my message carry out this
multiplication and see what I get for a
code word so for instance if I my
message is one and all zeros what's my
code word well I take this and I
multiply it all the way through the
matrix because of the special structure
here all of these are zeros so the rows
below the first one don't matter at all
what I get for a code word is 0 1 0 1 1
0 1 in other words I get the first row
of G ok if I had a 1 and a 1 with 0 0
I'm going to get the sum of the first
two rows of G and all of these
computations are done and with the
modulo-2 arithmetic so in GF 2 right so
this is one way to think of what a
linear code is another way to think of
it is every bits in your code word is a
linear combination of the bits in the
message it's just that you have more
bits here so you're taking multiple
linear combinations of the bits and the
message to get the bits in the code word
right so this is a highly structured
kind of code and the key fact about this
is that the sum of any two code words is
also a code word and we'll leave you to
look at that in recitation so it's true
that any code word generated this way
plus any other code word generated this
way will give you a code word generated
this way now can you deduce from that
that the code word of all zeros has to
be in any linear code why is it true
that
every linear code has to have the all
zero code word in this instance
well you can see it sorry has to have
the all zero code word why am i doing
that
yeah
yeah so candy from this picture if your
input is all zeroes you've got to have
the zero code word can you tell me from
this statement that the sum of any two
code words has to be a code word can you
deduce from that that the all zeroes
code word has to be in there
subtraction or addition so suppose I
take a code word and add it to itself
what do I get in GF 2 if I take a code
word and add it to itself I get the all
zeros but code word right so the all
zeros has to always be in there if you
don't have the all zeroes code word you
know too you don't have a linear code
okay now it turns out that for a linear
code it's easy to determine the minimum
distance between the minimum Hamming
distance between code words which we saw
was crucial to establishing what the
error correction or detection properties
work if you've got a linear code to
determine the minimum distance between
code words you only have to look for the
distance the minimum distance between
the zero code word and all the other
code words okay so it turns out that in
a linear code the minimum best distance
that you find between any two code words
is the same as the minimum distance
you'll find between the zero code word
and any other code word now what's the
distance between the zero code word and
some other code word is just a number of
ones and that other code word so all you
have to do for a linear code to
determine the minimum Hamming distance
is look at all the nonzero code words
and see which one has the minimum number
of ones ok so let's see
it's not obvious that these are
necessarily linear codes but they turn
out to be in this particular case here's
a code with N equals three we've got
only two messages being sent so what's
the value of K two messages means K
equals 1 right because 2 to the K is the
number of messages so n is 3 K is 1 and
the minimum Hamming distance is 3 which
is the weight of the the smallest weight
you find among the nonzero code words
here's another instance this is again
linear code well is it a linear code
yeah
the minimum weight you see among the
nonzero code words is 2 so the Hamming
distance is 2 so the way we denote this
code is it's and the value of n is 4
because there are 4 different code words
sorry the four different bits here four
bits sorry in the code word it's not
four different code words two is the
value of K because 2 to the to the 4 is
the number of messages that you have and
the minimum Hamming distance is 2 so
with each other's you can actually
compute the Associated rate
and just to wind up these are not linear
codes how do we know they're not linear
codes well some two of them and you'll
discover that in some instances you
don't get the remaining one in the set
this is the code set that I put up
earlier turns out to be a linear code so
if I claim that it's a linear code can
you tell me what the minimum Hamming
distances between code words here three
you find a code word here of weight
three and you don't find any code words
here also another one you don't find any
code words of weight less than three
okay all right so this is enough to get
you going will
quick with this you'll continue in
recitation and we'll pick it up again
and lecture next time thank you