Convolutional codes 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 tell you a little bit about
the use of digital communication schemes
in the space program and part of that is
it's not wasn't just the use a lot of
coding theory was developed for use in
this program so in the early days there
was no error control coding so they have
very slow transmission rates and tried
to compensate for not having error
control coding by taking a long time to
send a bit over but in later years with
the Mariner and Viking probes they
started to use our control codes and
linear block codes are what we're
talking about this would be the typical
parameters for such a code so we now to
read this this is 32 bits per block six
data bits and minimum Hamming distance
of 16 a particular kind of code called a
bi-orthogonal code or a Hadamard code
which had specific characteristics and
specific symmetries that actually helped
with the decoding so for instance on
Mariner 9 its 1971 this went into Mars
orbit and the code was used to encode
the picture transmissions so each data
word was six bits to encode 64 gray
levels in a picture it turned out that
because of transmission issues the safe
number of bits for a block was 30 bits
and after that you have to do a little
bit of realigning or tweaking so you
could send 30 bits at a time safely and
so that was a choice of n in that
vicinity was a natural choice one thing
you could have thought to do would be
take the six bits and repeat them five
times in the 30 bit window and that
would be a repetition code it turned out
that with this particular Hadamard code
you could actually get the same data
rates or comparable data rates let's see
what would the data rate be we K over
and
six over 32 but with much better error
correction properties so let's see how
many errors could you correct in this
code per block somebody seven yeah
because you've got a minimum having
distance of 16 so you want D minus 1
over to the floor of that it's you could
correct up to 7 errors per block and
this code was actually used on space
probes right into the 80s and as I
mentioned this particular code has
various symmetries that allow actually
something called the fast Fourier
transform to be used in the decoding and
so that's really what drove this now as
you read about these probes is actually
staggering how much they did with so
little let's see this thing went half a
billion miles almost it had an onboard
computer with a memory of 512 words
right so you can imagine the kind of
engineering that went into organizing
all this the transmitters and this is
typical of these space probes you can't
put you don't have lots of energy
generated from your solar panels
necessarily so 20 watt transmitters so
these have to transmit over this kind of
distance the data that you want to send
in the presence of noise and various
other errors okay so quite an
engineering feat now the kinds of
pictures that you would get well these
are pretty amazing actually considering
what the probes have to do so over the
lifetime it sent over 7,000 images
Mariner 9 is still orbiting Mars from
what I understand it's not sending back
it stopped sending back transmissions
one or two years after this but it's
still in orbit till it's so it slows
down enough to
crash in okay so as I said you're
typically talking about low-power 20
watts W and B are what what's the
typical radio station power on a college
campus they advertise something on the
order of 700 watts for their transmitter
right so we're talking about doing a lot
with a little here a lot of the art is
in the antenna so you have an antenna
that directs this power very sharply
towards the intended receiver
but the more sharply you try to direct
that the bigger of a control problem you
have because you've got to point that
antenna all that more carefully so all
of these are coupled issues and then of
the receiver and you've got very high
quality amplifiers and signal processing
but the data coding and error correction
schemes are a key part of that and it
turns out that as you got more ambitious
with these transmissions you had to go
to more complicated codes and these are
the codes we're going to talk about
today what are called convolutional
codes will talk about the coding today
and then we'll talk about the decoding
with what's called a Viterbi algorithm
next lecture so this has been used
extensively from late 1970s onwards more
recently you have codes that are
actually combinations of convolutional
codes what are called turbo codes and
another family of codes load low-density
parity-check codes which were developed
in Bob Gallagher's PhD thesis here Bob
Gallagher is on our faculty
but convolutional codes were really a
workhorse of the whole system okay so an
example is now Cassini which is in orbit
around Saturn and it's actively sending
pictures this if I read the website
correctly is a picture from August 29th
and I saw the pictures posted from June
and July so this is a picture of one of
Saturn's moons and you can see the Rings
and the shadows of the Rings and so on
this is actually we created a natural
color for multiple images this I guess
is part picture and part artists
transition but that shows you what
Cassini looks like is only one of them
out there I don't think there's
something else to photograph Cassini so
the kind of code that's used as a
convolutional code we'll learn what
these parameters mean how they enter
into the definition of the code and here
is a typical code rate you're talking
about something on the order of
eighty-three thousand bits per second as
the code rate here the sorry not the
code rate this is the data rate okay so
the the messages are coming let's see
yeah you're sending six times this
amount per second but this is the rate
at which the data is coming in okay
so convolutional codes and again I keep
coming back to MIT names Peter Elias was
on our faculty here he was a department
head for a while and in a short paper in
1955 invented the idea of convolutional
codes so the idea here is not to divide
up your data into blocks but to actually
work on the streaming data and as the
data goes past you generate parity bits
at a regular rate and what you transmit
in most typical schemes are just the
parity bits you don't send the message
bits so this would be a non systematic
code if you like so you're not there's
no part of that message that's directly
observing the the message bits now you
you will actually generate and send
multiple multiple parity bits so you'll
have a message sequence X 0 X n sorry X
0 X 1
and from this you derive parity bits and
you do that using the standard sorts of
equations we've seen with block codes
each parity bit here for instance parity
but zero at time and will be some linear
combination of message bits but it's the
message bits as they're streaming by so
you might have for instance this is your
choice for a parity bit number zero okay
and then parity bit number one could be
some of the combination here so for
instance xn plus
xn minus 2 okay so it's a linear
combination of some set of a set of
message bits just the way we've been
generating parity bits all along the the
plus here of course is we're talking
about binary messages so this is
addition in GF 2 so it's exclusive or or
modulo 2 addition and you can imagine a
whole bunch of such parity bits so in
general you would have our such parity
bits computed off some set of message
bits and transmitted instead of the
message bits so you might have in for
each message bit coming in you might
actually be sending out our parity bits
so what you do is just send these out in
sequence you'd send out the p0 value the
p1 value at time n then we compute a
time n plus 1 and keep going alright so
actually I have them here I didn't see
that
so all this happens on a sliding window
this happens for a particular choice of
n then it happens for the next choice of
N and the next choice of n so you're
doing this on the fly with a streaming
sequence right
so let me just put up an equation that
explains why this is called a
convolutional code it turns out that
expressions of this type where you take
a data stream coming in and generate new
data streams of this form it turns out
that the operation that's being carried
out here is something referred to as
convolution so in general what is p0 of
n it's some weighted combination of X at
the current time x1 time step back x2
time steps back in general K different
values involved so what I have is p0 n
being a summation from let's say J
equals 0
of cg0 J X of n minus J all right so
this is just some set of numbers 0 1
just as these bits are these are 0 or 1
but this is the general form right
this particular kind of combination is
referred to as a convolution operation
on the input stream and we'll see much
more of this when we come later to
modeling channels the physical channels
will talk about convolution type models
so here it's not so important that you
master this expression we'll have plenty
of opportunity to work with expressions
like this is just for you to know that
an expression of this type wherever you
see a summation with indices that are in
this form this is referred to as a
convolution okay so it's convolution of
the message stream with some set of
weights
yeah
the G is just a set of weights here so
in this particular case for parity
expression 0 g 0 1 g 0 of 0 would be 1 g
0 1 would be 1 g 0 2 1
okay it's just a set of weights
so yeah this expression is a bit of
overkill for the kind of use we're
making of it but it's just to explain
the origin of the name it turns out
later when we use it for channel
modelling the exes will not just be
zeros or ones they could take arbitrary
old values and the G's could take
arbitrary real values so we'll be
working with much more elaborate
versions of this okay
the number K is referred to as the
constraint length and it's the maximum
number of message bits involved when you
look over all your parity expressions so
in this particular instance K would be
equal to three right it's the maximum
window of data that you're using in a
non-trivial way to generate for this so
here you're using up to three to
generate this well in this case also
you're using a window of three message
bits it happens that you're ignoring the
one in the center but the constraint
length is the the length of message that
you're actually looking at okay
so in some sense if you want to think of
it this way the the number of parity
expressions that you use well that's
straightforward that's just telling you
how much redundancy you're willing to
put in whereas the constraint length is
telling you how deeply you're folding
that redundancy into the message so the
bigger the constraint length the more
message bits are involved in generating
a parity bit and so the more you're
scrambling up the message and spreading
it over a large section of what's
transmitted and so you might expect that
you get better error correction
properties with larger constraint links
okay
okay
this is not saying anything new so
so how do we come to actually
transmitting well we generate the parity
bits and then as I said you send all the
parity bits associated with your
computation at time zero then all the
parity bits associated with the
computation at time one so in the case
of the code used on the Cassini probe
that's one over six rate code it's
actually computing six parity
expressions so it's transmitting six
parity bits for each message but that
comes in what happens then of the next
time instant is that you shift
everything up by one
okay
now you can actually and I'll have this
up on the slides you can actually crank
through the equations but it's not the
most illuminating way to think of things
it's much easier to think of it visually
through a block diagram of this type and
using the idea of what's called a shift
Gen shift register so what is a shift
register you may have encountered it in
other places so we think of a shift
register as it's basically a box that
can remember something okay that's the
register part of it a register is
something that remembers a number you've
got some input stream that comes in and
some output stream emerging at any time
this stores a particular number which is
available to the output so whatever
stored in the register is available to
the output the shift part of this
description is that whatever's at the
input will get shifted in at the next
clock cycle or the next time instant
okay so the input gets shifted in at the
next clock cycle whatever is in here is
remembered for that one clock cycle and
is available at the output right so if I
have
a sequence xn being fed in for n 0 1 2 3
and so on if I'm seeing an X n here what
must have gone into the previous time if
I see X n here at time n if I'm seeing a
particular input at time n what must
have gone in the previous time is xn
minus 1 so what's sitting here is xn
minus 1 right and xn minus 1 is
available to me at the output the next
clock cycle the next input comes along
the xn goes in here and the whole thing
shifts alright now what you have up
there is a cascade of shift registers
you've got two shift registers if you
keep in mind the operation that I
described if this is xn if I'm looking
at this at time n xn sitting here what
must be in this shift register is the
input of the previous time so that's xn
minus 1 this these are shown adjacent
what we really mean is that one shift
register is feeding into the next one
they're just shown as adjacent but what
must be sitting here then is xn minus 2
ok and if I read off something from here
what's what I'm looking at is xn minus 1
maybe what's sitting in the register
what I'm looking at here is xn minus 2
all right so do you see how this is
working now this is actually the same
example that I had written up earlier I
guess for the computation of parity bit
so here's except it's yeah it's the same
one p0 and maybe I have the equations
let's see if I can display them for you
so what's p0 n p0 n is xn that's
connecting from here plus xn minus 1
again by the way in this diagram what I
showed is an arrow coming from the
output of the shift register there's
just a shorthand here that shows the
arrow coming out of the register it's
the same thing we're talking about
okay so p0 of n is the sum of these
three message bits so we're talking
about constraint length 3 here and what
about p1 n it's xn plus xn minus 2 with
nothing of xn minus 1 so imagine this
being the picture for every N you start
off at time 0 and keep going right we
refer to the state of the shift
registers as the pair of numbers that we
find in here
so if we're talking about X's that can
be zeros or ones the shift register
combination here can be in one of four
states right 0 0 0 1 1 0 or 1 1 so four
states so here's a four state shift
register into which we're feeding in the
street and what gets put out on the
channel are these parity bits
interleaved
not care enough okay
nothing I haven't said here right
so let's actually work through an
example step by step this is clear
enough but let's just see it concretely
let's assume that I'm starting out with
the shift registers in the zero state
and now I've got this message sequence
coming in that I want to send out okay
so the sequence is 1 0 1 1 so the first
bit that appears here is the 1 and I've
got to generate p 0 and P 1 well p 0 is
the exclusive r of these three things so
it's 1 P 1 is the exclusive or of the
first and the last so it's again 1 so
that defines p 0 and P 1 at time N and
the same way at the next time instant
the next input the next message input
bit comes in so we had 1 0 1 1 we took
care of the 1 here
now comes a 0 we do the same thing so
the exclusive or of all 3 of them
appears here that's the one the
exclusive R of the first and the last
appears there and that's the 0 so you
can see how things are getting folded
together because the input that was here
before is now sitting in here and plays
a role in generation of the parity bit
for the next step okay in fact the word
convolved means to fall together and
this is what it's actually trying to
capture you're folding together these
these two sets of weights the weights on
the top here and the input sequence
weight
and then the next two cases similarly
okay and that's what gets sent out at
the bottom
so this is the transmitted sequence so
it's the 1 1 1 0 0 0 0 1 right that's
all there is to it
the implementation of the shift register
is very easy and so this is actually a
very straightforward thing to implement
now there's another viewpoint that's
also very useful here another way to
look at what's going on which is
thinking in terms of the state of the
register and how you move between the
states I guess I mean here we're doing
double o4 are those the ones with smiles
on their faces yeah ok you see a lot of
this there I imagine okay so how do I
read a diagram like this I've got a
circle for each state that the shift
register can be in so the shift register
can be in 0 0 1 0 sorry 0 0 0 1 1 0 1 1
right
each of these arcs represents a
transition from one state to another so
let me ask you this what does it take
if I'm in the zero zero state with my
shift register so what you've got the
picture is your shift register sitting
there with zero zero what does it take
for me to get to the one zero step
what was my input of being to get to the
one zero state
imagine how these shift registers
operate right if I'm going to get from 0
0 to 1 0
I must have fed in a1 the previous time
instant right so it takes so an input of
1 to go from the 0 0 to the 1 0 so to go
from 0 0 to 1 0 use an input of 1 that's
the number that we right before the
slash that's our labeling Convention for
the arcs we put the input that it takes
to make that transition and then after
the slash we put the parity bits that
are emitted so what we've got for the 1
1 is the parity bits that are emitted
when you've got input 1 sitting here 0 0
here and you're using the parity
computation that I had before to do so p
0 is going to be xn plus xn minus 1 plus
6 and minus 2 so that gives you 1 and
what about P 1 P 1 is xn plus xn minus 2
gives you another one okay so you here
in state 0 the 0 0 state and you get an
input of 1 you're going to transition to
1 0 and you're going to emit 1 1 okay so
the state diagram captures all that and
similarly all the way around so I
haven't checked each of these but I hope
they're not mistakes in it but if you're
in 1 0 well by the way if you're in 0 0
there's no way to get to 0 1 right so
you don't see any arc from 0 0 to 0 1 if
you're in 1 0 you can get to 1 1 or you
can get to 0 1 depending on what you
feed it ok so it's very straightforward
than to actually build up this diagram
why don't we do okay so
if I'm actually abstracting from the
shift register picture to something
that's more like the state picture I'm
going to say here are my four states
I've just drawn a different a little
differently than I have in the upper
picture instead of circles with these
states in them I prefer to think of them
this way so what we said is if you get
an input of one you limit one one and
you'll get to that state what does it
take to get to this state somebody
you'll have a hand in the cloud voice
yeah okay and then I guess you've got to
go back to this to think about what's
happening so I'll allow you to think of
a zero sitting at the input here so what
would the parity bits be
so the first parity bit will be the
exclusive or of the zero one and zero so
it's going to give you a one right and
then the next parity bit is going to be
exclusive or of what's here and there so
it's going to be a zero I hope that
matches with what I have upstairs we're
talking about going from one zero two
zero one it takes a zero input to do
that and what you emit is one zero right
so you can fill in all of these this is
the state transition diagram okay
let's see and we say that if you've got
a constraint length of three then of K
equals 3 for instance or let's say if
you've got a constraint length of K
you've got 2 to the K minus 1 States
well that's because in that constraint
length one of the bits involved is the
input bit that's not sitting in the
shift registers so you've got K minus 1
bits left over so your shift register is
K minus 1 stages long and so you've got
2 to the K minus 1 States all right so
you could imagine generalizing this to
more complicated sorts of situations
let's see just going back to the cassini
example let me jump back a bit
there was a K there what was it
Keio 15 okay so for Cassini you're using
one input bit and 14 more okay so you've
got two to the 14 possible states there
so in these codes are actually using
very large constraints
okay
all right I want to go from the state
machine view to another view now which
is what's called so this is the state
machine view to something called the
trellis view
this is something by the way there was a
way of looking at things that was
developed by someone else's on our
faculty David Forney in fact if you
visit his home you'll see his garden has
a nice trellis around it and you'll see
why when I when we draw this okay so
what's the trellis view the trellis view
says take the state machine but unfolded
in time so that all your transitions
over time are not happening here every
time step you draw the picture again and
look to see where you get to so let's do
this this is the one I want to be most
careful with and where I'll introduce a
few notational conventions so that our
later life is simplified
okay so we've got state 0 0 state 0 1
state 1 0 and state 1 1 okay except but
this is going to be the picture that I
have a time let's say at time N equals 0
at time N equals 1 well I've got this
the same shift registers I'm going to
draw this picture again
the easiest way to learn this is to just
follow through one example so please
keep your attention here and you'll have
it sorted out and then you won't have to
worry about it again it's the same thing
as with lzw so it looks kind of detailed
maybe tedious but it's actually very
simple just hang in there and follow
through one example okay so what does
this say I'm and a time N equals zero
I'm in zero zero suppose I get the input
zero suppose the input is zero what
state do I transition here right
so if I have an input zero I'm going to
transition here so this is with an input
of zero and what are my parity bits
going to be
both zeros right
what about if I get an input of one
where do I transition to well we've
already seen that here if I get an input
of one I'm going to transition to here
and what am I going to admit what we've
already calculated them that we're going
to admit a 1 1 right
let's do it for one more case we're in
0-1 what states can I transition to I
could go to zero zero and I would do
that if my input was 0 right
and what would my parity bits be well
that's another case for us to look at if
our input is zero and we're in state
zero one
what would the parity bits be for this
choice of parity bits it depends on what
specific choice you made of course
1/1
you agree
and if I get an input of one instead
where do I go if I get an input of one
I'm going to go to one zero which is
here
okay so if I had an input of one I would
go to one zero my parity bits would be
what would they meet
can I have a hand on the voice yeah
zero zero
okay so it's that simple that's all you
have to do fill out this picture and
you're seeing what this picture
translates to the next time instant
we're not using anything more than is in
the state-transition a certain the in
the state machine diagram but we're
unfolding things in time which is
actually very helpful now there's a
simplification
we'll make in drawing this because I've
arranged the states in natural binary
counting order 0 0 0 1 1 0 & 1 1 it's
always the case that the upper arrow
that emanates from a state corresponds
to an input of 0 and the lower arrow
corresponds to an input of 1 okay so I
don't really need that first thing
before the - I'm just going to dispense
with it so if you're going up of the two
choices that you have when you come out
of a box if you're going up it's 0 the
input was 0 and if you're going down the
input was 1 so I'm just going to label
that as 0 0 I'm going to label this as 1
1
and I guess I've forgotten already what
some of these are
like you can see what the whole thing
just starts to look like
so let me actually I'm not going to do
these in detail but let's just see how
this the next stage would differ at all
when I come to N equals two well it's
the same story all over again right so
whatever pattern of arrows I had coming
out of here I have the same pattern of
the next stage with the same labels
there's nothing so if you'll allow me
let me actually fill out a few of these
and you get practice drawing one of
these when you do recitation maybe for
another example so I can keep going with
these let's see here this is going to be
one one if I haven't found two arrows
coming out of each box and I'm not done
oh this is wrong right thank you
from zero one I can go to one zero
okay so the two arrows coming out of
each one the upper arrow corresponds to
an input having mean zero the lower
corresponds to an input having mean one
and there are two arrows going into each
box as well
corresponding to whether the bit that's
going to get dropped off is a 0 or a 1
alright so there's a real symmetry to
this I'll go one more stage just a
little bit to make a point here
okay so you can keep going
so how do you generate a code word from
the trellis diagram you're starting in
some state typically it's the all 0
state in fact what you usually do is
have a header for your message stream
which is all 0 so you force the shift
register to be in the zero State once
the real message bits come in and then
you from here so you're typically
starting here and then you navigate so
if the first message bit is a 1 you're
going to go down here if the next
message bit is a 0 you're going to go up
here 0 you're going to go up there and
the code word that you emit is going to
be in that case 1 1 1 0 right assuming
you're staying zero from that so
depending on the message sequences you
can actually go through the trellis it's
infinitely long or as long as your
message sequences and figure out what
the code word is that submitted so this
is actually just a graphical way of
displaying code words so the set of code
words that I get does that correspond to
a linear code let's assume that
somewhere downstream all these things
come back down to 0 0 okay so I'm only
considering a finite
window of things it's not going to go on
forever so suppose I'm gonna end my
input messages with zero zero at the end
then come back down to that state
so my messages will always start with
zero zero to force the register to the
zero zero state and they'll end with
zero zero okay the set of possible code
words is a set of parity bits i omit
along the way as I navigate through the
trellis is the set of code words does
the set of code words constitute a
linear code in question
maybe not obvious right
the way you answer that is actually
thinking back to this setting so one
particular codeword would correspond to
a particular input sequence that
generated it in particular data a
message sequence that generated another
code would would correspond to another
message sequence and the question is is
there a message sequence that would
generate the sum of these two code words
that you have and actually turns out
that it the answer is yes because these
priority relationships are based on a
nice linear operation okay so it turns
out that the set of code words that you
generate constitute the linear code so
if you were going to think of a minimum
Hamming distance for this code what
would what would you want to be thinking
of
I don't know if I've actually drawn this
correctly right now does anyone spotted
any errors along the way or do I have it
right
seems to be okay
what would cars how would you look for a
minimum Hamming distance in the set of
code words generated over this this
window
sorry I didn't hear where that came from
yeah
it is pretty speak up
the minimum number of ones in a non zero
code word right okay so it'd be the
weights the minimum weight code word
you'd find among all the longer code
words so you would have to find a path
starting here all my code words are
going to start here and end there you'd
have to find the path through this that
picks up the minimum number of ones a
pot that's different from the all zeroes
but okay find a path through there which
has the minimum number of ones in it and
the code word so what would that be
in this particular case maybe this path
highlighted in another color
I don't know if this is not a proof this
is just a suggestion that this might be
it and you you would have to draw in all
the pots explore all the other pots but
what would be the minimum weight along
this one let's see I got 1 1 there 1 0
here 1 1 there so I would get a weight
of 5 on this path and the question is
whether you could find another path with
a smaller number of and I think if you
work this out in detail and stare at it
you'll find that you're actually stuck
with 5 ok now it turns out that the
interpretation of this number is not
quite as straightforward as the
interpretation of minimum Hamming
distance in block codes and the reason
is that actually this is a more
complicated kind of picture because it
continues on with the structure so we
don't actually call it the minimum
Hamming distance we call it the free
business
so I'm just trying to evoke this so the
the minimum weight code word you find
among the non zero code words will
indeed be a code word of weight 5 but
the interpretation of that number may
not be directly as simple as in the case
of the Hamming distance but it's close
okay so what it really tells you is that
over a data length that is maybe not
much longer than this the code words
that you have are separated by so you
might expect that you could correct two
two-bit errors over data lengths that
correspond to code words that are
somewhat longer than this perhaps okay
so that's all very hand wavy but that's
all we're going to do with the notion of
free distance so this is more
complicated to deal with in a block code
but the free distance actually has that
kind of intuition it has the intuition
of minimum Hamming distance locally all
right over this window of data even if
this went on for thousands of bits if
you got a burst of errors in this
stretch that adds up to two errors you
could correct them now we haven't talked
about decoding we're going to talk about
that the next time okay
so that answers this piece
now let me say one thing about decoding
just to set us up for next time if I
didn't have any noise in my channel it
actually turns out that decoding is
pretty trivial how is that if I gave you
the sequence of parity bits can you
think of a way that you could recover
the input sequence
good yeah you see if I have these two I
get xn minus one equals p0 n so if you
give me the parity bit stream I can
reconstruct for you exactly the input
with a one step delay that's pretty good
I'm happy with that if it's taken me you
know minutes for the signal to reach me
from Saturn I'm happy with the ones that
delay here in the decoding all right so
in the absence of noise the inversion is
simple the inversion meaning deducing
the input message bits from the output
the parity bits and this is a theme
you'll see in many other settings if
there's no noise inversion is easy you
can look at the output of a system and
figure out what the input was if you
know exactly how the system was creating
the output from the input but in the
presence of noise you've got a problem
because you see if you have these parity
bits corrupted at some rate every few
bits you've got errors well your
interpreted message is going to have
that same kind of error okay so it's
really in the presence of noise it's an
unsatisfactory way to do it so this
doesn't work we'll be looking at
something more careful next time
I think well actually since I have you
here let me put up a spot please we
haven't quite hit the mark so can you
answer these for me
what's the constraint length of this
code
anyone who hasn't answered yeah or right
because you've got X n xn minus 1 xn
minus 3 that's the largest window over
what you're picking things what about
the code rate
one over three right because for every
message bit you're generating three
parity bits
you're gonna ship out those sweet parity
bits before you do the shifting on the
shift registers so the code rate is one
over three the coefficients of the
generators of course you can read up
there what about the number of states in
the state machine here
what ate right because constraint length
is four but one of those is the input
the about three bits that you're storing
in memory to to the three is eight so
the number of states in the machine is
three is eight okay so more complicated
picture than this but the same principle
all right we'll continue next time