Tip:
Highlight text to annotate it
X
Welcome to the next lecture on wireless communications. Today we will talk about various coding techniques
for mobile communication. First a brief outline for today’s talk. We will first summarize
what we have learnt so far followed by a study of the Galois field. We will then move over
to an interesting domain of cyclic codes which happens to be a sub class of linear block
codes and finally we will talk about the BCH codes. In the previous lecture we talked about
linear block codes, we realized that linear block codes are LBC’s have a fixed block
length N and you can have a generator matrix to generate the entire set of code words.
We then visited briefly Galois field and had a very short introduction to cyclic codes.
Now let us refresh our memories about the Galois field theory, we know that a field
F is a set of elements with two operations addition and multiplication and the elements
satisfy the following 8 properties. First of all F is closed under summation and multiplication
that is a + b and a into b are contained in the set. Also for all a, b and c within F
the commutative law, the associative law and the distributive law holds good which is a
+ b is equal to b + a, (a + b) + c is equal to a + (b+c) are equal, under distributive
law a times (b + c) is a times b + a times c these must hold. Further two interesting
identity elements exists, one is a +0, the 0 should give back a and a times 1 should
give back a; also there exists an additive inverse and the multiplicative inverse if
we have to talk about a field.
If the last property doesn’t hold for the elements that is there is not the presence
of multiplicative inverse but only an additive inverse we call it a ring. If only the first
7 properties are satisfied it is called a ring otherwise it’s a field. Now we learned
last time that the objective of error control coding is to add redundancies in a known manner;
in a known manner such that there is enough structure, algebraic structure within the
code and whenever there is an error this structure breaks and if we are smart enough we should
be able to detect an error and hopefully reconstruct it back. So that is the whole idea of adding
structures.
Cyclic code is one step forward, it is a sub class of linear block code that it has one
additional requirement an additional constraint, an additional structural requirement. What
is that? A code C is cyclic if C is a linear code and on top of that any cyclic shift of
a codeword is also a codeword. So if a0 a1 so and so forth till an-1 forms a elements
of codeword then any cyclic rotation if you put an-1 before like this and then a0 a1 up
to an-2 this itself is also a valid codeword if it is a cyclic code.
Here is an example of binary cyclic code; here if you can see all of the elements if
you rotate them to the left or to the right, you end up with another valid codeword. Please
note this is another example of a linear block code but here it is not a cyclic code. The
two properties of a linear block code are, the all zero codeword must exists as a valid
codeword and some of any two codewords is also a valid codeword, on top of that any
cyclic rotation of a codeword gives you another valid codeword that makes it is a cyclic code.
Now let us take a brief mathematical detour and get into the domain of polynomials because
we will learn that it is very easy and logical to express a codeword which is a cyclic codeword
as a polynomial. There is a one to one correspondence. So what is a polynomial? A polynomial is a
mathematical expression, it can be denoted as follows and the symbol X is called indeterminate
and the coefficients f0, f1 up to fm are the elements of any GF (q), a Galois field. So
we can define a polynomial over a field. It depends from what are you taking the coefficients
from. If it is a binary polynomial then GF (2) is in question and then you have f0 f1
etc either a zero or a one, if it is GF (3) then your fi can be 0, 1, 2.
If fm the coefficient of the highest power is not zero then m is called the degree of
the polynomial as denoted by degree f (x). A polynomial is called monic if its leading
coefficient is unity. So here is a polynomial over GF (8) so you can see the coefficients
can take values some 0, 1, 2 up to 7 but the highest power X6 as a coefficient unity, hence
this is the monic polynomial of degree 6.
Now let’s have some definitions now let us explore the properties of f(x) which makes
this F[X] divided by f(x) of field. So what is this capital F[X]? This is a set of polynomials
and if you divide it by f(x) then you are doing a modulo operation that is whatever
is the remainder after you divide any element, any symbol within this by f(x). You are left
with a remainder and we are talking about that’s it, what we are interested in finding
out is the properties of f(x) which makes this thing of field that is it satisfies the
8 properties of a Galois field.
We will shortly find out that the polynomial f(x) must be irreducible which is the polynomial
version of non factorizable. That is you cannot represent it as a multiplication of two other
polynomials. So polynomial f(x) in F[x] is said to be reducible if f(x) is a(x) times
b(x) where both a(x) and b(x) are elements of f(x) and degree a(x) and degree b(x) are
both smaller than degree f(x), it doesn’t hold then it is called irreducible. A monic
irreducible polynomial of degree at least one is called a prime polynomial, we will
use this definition many times.
Now continuing with our mathematical detour, the ring F[x] over f(x) is a field if and
only if f(x) is a prime polynomial in F[x]. So we are trying to find out when will this
set be a field and the claim is this will only happen if and only if small f(x) is a
prime polynomial. So if this is true we have an elegant mechanism of generating Galois
fields. If we can identify a prime polynomial of degree n over GF (q), we can construct
a Galois field with qn elements. Such a field will have polynomials as the elements of the
field. These polynomials will be defined over GF (q) and consist of all polynomials of degree
less than n. We are talking about taking modulo f (x), small f (x) has highest power n so
you can have the coefficients f0, f1, f2 up to fn-1 and all the polynomials that will
remain if you perform this operation, will have the degree less than n but there be n
coefficients. Each of the coefficients can take value as one of the q elements of the
Galois field. So there will be qn such polynomials.
So let us denote capital F[x] over f(x) as a set of polynomials in F[x] of degree less
than the degree f(x) with addition and multiplication carried out modulo f(x). So you divided and
whatever may be the remainder is the element. Now if a(x) and b(x) belong to capital F[x]
by f(x) then the sum a(x) + b(x) in F[x] by f(x) is the same as in F[x], this is because
we have already put the degree of a(x) is less than f(x) and degree of b(x) is also
less than f(x). Carrying on this philosophy the product a(x) times b(x) is the unique
polynomial of degree less than degree f(x) to which a(x) times b(x) multiplication is
carried out in F[x] is congruent modulo f(x).
So capital F[x] over f(x) is called the ring of polynomials over F[x] modulo f(x). So what
are we looking at? This capital F[x] over f(x) is a set of polynomials all of which
have degree less than that of degree of f(x) because if it is a remainder after you carry
out the division and we are talking about when will this set form a ring and when will
it form a field. As mentioned earlier a ring satisfies the first seven of the 8 axioms
that define a field. A ring in which every element also has a multiplicative inverse
forms a field.
So now after this brief mathematical detour let’s go back to cyclic codes and see how
this arithmetic with polynomials can help us construct cyclic codes. Now let’s fix
for a change rf(x) the polynomial with which we divide as xn-1. This is very interesting
as we will soon see and we also denote if your small f(x) is xn -1 then the set capital
F[x] divided by f(x) by Rn. Let’s make the following observation; xn is 1 provided you
are taking it modulo xn -1. So xn is unity in Rn. So the modulo xn -1 can be reduced
simply by replacing xn by 1 xn +1 by x and so and so forth. A codeword can be uniquely
represented by a polynomial; this is the most important observation on this slide.
A codeword consists of a sequence of elements and they can correspond one to one to the
coefficients of the polynomial. So we can use a polynomial to represent the locations
and the values of all the elements in the codeword. So if my codeword has a block length
n then there are n elements in a codeword so we can use these elements of the codeword
as coefficients of a polynomial. So polynomial has a unique codeword and a codeword can be
uniquely represented by a polynomial. So for example the codeword c1, c2, up to cn can
be represented by the polynomial c0 + c1 x + c2 x square up to cn so there is a one to
one correspondence. Codeword c0 c1 c2 can be represented like this c0 is missing.
Another example of the codeword over GF (8) let’s say 207735 then we have 27735 because
the zero is missing because it is zero times x. You can uniquely represent any codeword
as a polynomial. Now what is interesting is multiplying any polynomial by x raises the
power of each of this x by 1 and hence it represents a single right cyclic shift. So
shifting the elements, rotating them by one is very simple is just multiplying the polynomial
representation of the codeword by x. If you multiply it again you shift it one more time
and so and so forth. The only problem is that my block length of any codeword is fixed and
is n.
If I keep on multiplying the power of x increases, if it is goes beyond xn then I am actually
elongating my codeword, I cannot. In fact I must have a way to put the maximum power
back to here, I must do a modulo operation and this operation of putting the highest
power which exceeds the block length back to the first place is done by modulo xn-1.
So as long as you keep on multiplying by x but finally take modulo xn -1 you restrict
the block length to n and at the same time you perform the proper cyclic shifts. So please
note if you multiply c(x) by x, you raise the power by 1 but I need some way to put
the cn back before c0 because this is clearly a representation of a codeword which is longer
than block length n. We need to put this back here and this is done by modulo xn -1hence
the importance of modulo f(x).
Now here is a theorem, a code C in Rn we know is when you take modulo xn -1is a cyclic code
if and only if C satisfies the following condition, a(x) and b(x) the elements in C then a(x)
plus b(x) is an element in C, it’s a linearity condition and a(x) element of C, r(x) element
of Rn then a(x) r(x) is an element of C. So here is a brief proof for this one and the
basic philosophy here is that if you have a cyclic code, it can be simply represented
in Rn. So cyclic code will have polynomials contained in f(x) over small f(x) where small
f(x) is xn -1 and it will satisfy these following two properties; it’s easy to prove these
two here.
Now let us move over to a method for generating cyclic codes because all this mathematical
tools are going to help us generate cyclic codes. First take a polynomial f(x) in Rn,
obtain a set of polynomials simply by multiplying f(x) by all possible polynomials in Rn. So
when you multiply f(x) by any other polynomial you do two things; you can multiply with something
x raise to power something that will do a cyclic shift and then add it up which means
that you are taking one codeword and adding with another valid codeword.
The set of polynomials obtained above correspond to the set of codewords belonging to a cyclic
code. The block length of the code is n. Let us take a simple exercise, if f(x) is a polynomial
in Rn then if you multiply this by x+1 which is a valid polynomial, it tantamount to first
multiplying f(x) by x which is again a valid polynomial and then adding it to f(x) which
is multiplying f(x) with one which also is a valid polynomial and the together the addition
should also be a valid codeword in Rn. Hence we satisfy the definition of a cyclic code
and this can be generalized for any complex polynomial within Rn.
So let C be a (n, k) non-zero cyclic code in Rn then there exists a unique monic polynomial
g (x) of the smallest degree in C. This is the special polynomial, the cyclic code C
consists of all multiples of the generator polynomial g(x) so we call this as the generator
polynomial. It is the analog of the generator matrix, this has the capability to generate
all the other valid cyclic code words. So the cyclic code C consists of all multiples
of the generator polynomial g(x) by polynomials of degree k-1 or less and most importantly
g(x) is a factor of xn -1.
This is the most important fact, if this is true then we have a very elegant and simple
way to find out a generator polynomial simply by factorizing xn -1. In fact this will be
one of a preferred ways to find g(x) for cyclic codes, factorize xn -1. All we have to do
is to factorize this quantity into irreducible monic polynomials. These are the conditions
required for g (x). We also can find all possible cyclic code words of block length n, simply
by factorizing xn -1. Note a cyclic code C may contain polynomials other than the generator
polynomials which will also generate C. However the polynomial with the minimum degree is
called the generator polynomial and the degree of g(x) is n-k.
So let us see how we can encode using generator polynomial, please note the generator polynomial
itself is a valid codeword. If you multiplied with unity you get a polynomial g(x) which
should be also valid codeword. A simple encoding rule to generate the code words from the generator
polynomial is as follows; c(x) which is a codeword polynomial, we have established before
a one to one correspondence between a polynomial and a word so c(x) be the codeword polynomial,
i(x) be the information word and g(x) be the generator polynomial. So if you multiply i(x)
with g(x) you would get a valid code word polynomial.
The error vector can also be represented as the error polynomial e (x). It should show
at what location what is the magnitude of the error. Thus the received word at the receiver
after passing through a noisy channel can simply be expressed as the received word v
(x) is equal to c(x) the codeword polynomial plus the error polynomial e (x). Now let us
maintain the analogy, so we had a generator matrix, generator polynomial we have a syndrome,
we have a syndrome polynomial also. The syndrome polynomial s (x) is the remainder of v(x)
under the division by g (x).
Clearly if g (x) completely divides c (x) that is the remainder is zero then you have
a valid polynomial. Whatever be the residue that is the remainder after dividing by g
(x) is the syndrome polynomial. Please note s (x) is the remainder if you divide by g
(x), what v (x) which is nothing but remainder when you divide by g (x). What is v (x), nothing
but c(x) plus e(x) and then by simple rule you can separate them out but c (x) when divided
by g (x) should be zero by definition because g(x) times i(x) is c (x). So what you get
is the remainder of e (x) when you divide it by g (x). Thankfully the syndrome depends
only on the error polynomial as it should and has nothing to do with the code word polynomial.
Just as a syndrome or a symptom of a disease tells about the disease, similarly the syndrome
polynomial should tell us what kind of an error you have encountered. If you have a
one to one mapping for every error pattern a unique syndrome then it is very easy to
map back.
It is also possible to have a matrix description of cyclic codes simply because it is a sub
class of linear block code and must have a generator matrix but the generator matrices
very easy to represent, once you have the generator polynomial and you have the generator
polynomial which is very easy once you can factorize xn -1, n is your block length. So
if I give you a block length we can immediately take xn -1 factorize it, get g (x) as a polynomial
which can generate all the valid code words, once you have g (x) you can have generator
matrix which is simply written as the shifted coefficients of g (x) in the various rows,
is again a k by n matrix for (n, k) code. It is a one to one correspondence here if
you have g (x) you can write the generator matrix.
Now just like we have a parity check matrix, we have a parity check polynomials for a valid
cyclic code. What should it do? If you multiply it with the valid codeword you should get
a zero and otherwise you should get a non-zero syndrome of sorts. So we already know that
g (x) is a factor of xn -1 hence you can write xn -1 is equal to h (x) times g (x), so factor
after all. Now h (x) is some polynomial, it’s kind of a dual so the following can be concluded
simply by observing the above equation. Since g(x) is monic, h(x) has to be monic because
xn is, the highest coefficient is one but please note here we are not talking only of
binary cyclic codes, this is valid for all Galois fields.
So even if I am talking about cyclic codes over g (8), g (16) this will still hold good
but g (x) must be monic. There is the highest coefficient should have coefficient equal
to one, the highest power of x. So since g(x) is monic h(x) has to be monic because the
left hand side of the equation is also monic. Since the degree of g (x) is n- k, the degree
of g(x) must be the degree of h(x) must be k. Suppose C is a cyclic code in Rn with generator
polynomial g (x) recall that we denoting F[x] by small f(x) by Rn where f(x) is xn -1. Then
any codeword belonging to C can be written as c(x) is equal to a(x) times g (x), we have
noted this before where the polynomial e (x) is within Rn.
Therefore within Rn c(x) times h (x) is equal to a(x) g(x) h (x) but for every valid g(x)
and h(x) it should be zero, so it is zero. That means if you multiply c(x) with h(x)
you end up with a zero, just like the parity check matrix we multiplied with the codeword
vector, you end up with a zero vector; if you multiply the parity check polynomial with
a valid codeword polynomial you end up with the zero polynomial. Had there been an error
you will get a non-zero polynomial and that will form your error polynomial.
So let’s look at an example for binary codes of block length n =7, we have xn -1is equal
to x7 -1 and the first step always in the search of cyclic codes is to factorize this.
In a previous lecture we had looked at certain factorizing techniques.So the first step is
simple x7 -1 is x -1 times x6 +x5 and so and so forth up to x0 which can be further factorized
into these two terms. So we done the factorization and all of them are irreducible, they cannot
be factorized further which means the three of them and any product thereof can form a
valid generator polynomial, it has to be a factor of x7 -1. So just consider x3 +x +1
since g(x) is a factor of x7 -1 is a cyclic code that can be generated by it. Now having
found out a generator polynomial which in our case here is x3 + x+1 I can simply write
the generator matrix by using the coefficients 1 1 0 1 are the first three coefficients in
the decreasing order because the coefficients of x2 is zero here which is reflected here.
So x0 x1 x2 and x3 and then a cyclic shifted (Not understandable) another one and another
one.
The number of rows is 4, the number of columns is 7, n =7 and k =4 and n- k is the highest
power of x0. If you know G you can also find out the parity check matrix so this is nothing
but whatever is remaining. So if you multiply x -1 with x3 + x2 +1 you get this one and
this corresponds to the coefficients of the parity check matrix. The number of rows is
n – k is equal to 3, the number of columns is equal to n =7. So this is the G and the
H matrix for your cyclic code. Please note here we have a recipe to make as many generator
polynomials as possible. In fact 1, 2, 3 are clearly visible. Then product of these two
4, product of these two 5, product of these two 6 and then there are two more factors
for x7 -1, one is unity it’s also a factor and itself x7 -1 that’s also a factor of
x7 -1.
So you have 8 possible generator polynomials out of x7 -1.Question is being asked about
h(x), h(x) as we know has a very interesting property. We have denoted h(x) times g(x)
is equal to xn -1. So if I choose my generator polynomial for an instance as x3 + x+1 then
whatever other two terms left their product is h (x). Had I chosen my generator polynomial
is x3 +x2 +1 it’s also valid generator polynomial because it’s a fact is a monic, is a factor
of x7 -1. In that case the product of x -1 and x3 + x+1 the first two terms would have
been h (x), so g (x) times h (x) is xn -1. So after the effort that we put in, to figure
out factorization of polynomial it is now a piece of cake to figure out how to get to
the various kinds of generator polynomials.
In fact once you factorize, you found out all possible generator polynomials for the
block length 7 because I factorize x7 -1 once. In fact I have not one, not two but the existence
of 8 possible cyclic codes here, of course some of them are trivial. So the minimum distance
of this code is 3 and if you observe it carefully this happens to be the (7, 4) hamming code.
So the hamming code which is also perfect code also happens to be a cyclic code, a very
versatile code. Now let us give a flavour to this error control coding from the perspective
of mobile communications. In mobile communications we have already encountered that the wireless
channel is a very hostile channel, it goes through deep fades and whenever we pass through
a fade, we have a burst of errors.
It depends upon the fade duration, if the fade duration is large then we have several
bits wiped out at a time and these are consecutive bits so far the philosophy of error control
coding has been that we can handle random errors but if the errors start happening in
bursts that is all the errors are situated next to each other then we are in problem.
Then we must device some smart techniques to overcome the burst errors as we will see
cyclic codes are phenomenally good in overcoming burst errors. In many real life channels as
we know in wireless channels errors are not random but occur in bursts. For example the
mobile radio channel, when errors occur at a stretch as opposed to random errors we call
them burst error. A cyclic burst of length t is a vector whose nonzero components are
among the t successive components but note the first and the last of which are nonzero.
So if you say it’s a burst of length t then the first and the last elements in the error
pattern should not be zero. Let’s take a small example that the transmitted sequence
of bits transmitted at 10 kilobits per second over a wireless channel be follow.
Suppose after 0.5 millisecond of the start of transmission, the channel experiences a
fade of duration one millisecond. Now we have already devised mathematical tools to predict
the average duration of fade. Let this be a measured quantity one millisecond. So during
this time interval the channel corrupts all the transmitted bits so here is a start of
fade and the fade lasts for so long and then the fade ends because we know that the data
rate and we also know how long the fade last here this is kind of an error patterns. So
all the bits within this fade have been flipped but clearly we do not know the fact that all
of them have been flipped. If you knew it will just flip it back and a problem is solved.
So fade doesn’t mean that the all the bits are exactly flipped.
In fact we do not know whether the bit is flipped or not but there is a possibility
have been flipped but most importantly for the burst of length t, the first and the last
should not be zero, rest all can be zeros. It could have been 1 0 0 0 0 0 0 up to here
and then one again it will still qualify as a burst of length t. This is an example of
a burst error where a portion of the transmitted sequence gets garbled due to the channel;
here the length of the burst is 10 bits.
So let’s look at an example for a binary code of block length n =15, consider the generator
polynomial like this. So generator polynomial gives you a lot of information you only know
n=15 but you know that the highest power 6 corresponds to n-k. So n-k 6 so you can find
out k from here and then you can find out the code rate. This code is capable of correcting
burst of length 3 or less, to prove this we must show that all syndromes corresponding
to the different burst errors are distinct. The different bursts are burst of length one,
it’s just saying that one bit occurs at any one of the 15 locations. What are the
15 locations? 0 through 14 so e(x) which is our polynomial for burst error is xi, bursts
of length 2 can be denoted by e(x) is equal to xi (1+ x) because they have to be two consecutive
bits which are in error it’s a bursts of length 2.
Bursts of length 3 can be denoted as follows, there have to be 3 consecutive errors, it
can be shown that the syndrome of all this 56 possibilities. So they have only 56 possible
bursts lengths of burst length 1, 2 or 3. So if I say this code can correct all burst
errors of up to length 3 then all the possible error patterns, all the possible burst error
patterns must have a unique syndrome polynomial. How do we find out the syndrome polynomial?
Take this e (x) divided by g (x), whatever is the remainder is a syndrome polynomial.
So it can be shown it for all these cases, if you take it modulo g (x) you come up with
unique polynomials. If we have unique polynomials you can map it back and hence correct all
errors of burst length 3 or less. A table can be made for each pattern and the corresponding
syndrome which can be used for correcting a burst error of length 3 or less can be found
out.
Let us look at another example, a code which is good at correcting burst errors it is called
the fire codes. A fire code is a cyclic burst error correcting code over GF(q) with the
generator polynomial given as g(x) is equal to x2t-1 -1 times p (x) where p(x) is a prime
polynomial over GF(q) whose degree m is not smaller than t and p(x) does not divide x2t-1
-1. So under this constraint whatever code you form is called a fire code. It has some
very interesting properties. The block length of the fire code is the smallest integer n
such that g(x) divides xn -1. A fire code can correct all burst errors of length t or
less so within the definition of your generator polynomial I have put in how many burst errors
can I correct. So I have designed rule here I fit in a value of t, if it is 3 you have
x5 -1times p (x) where p (x) must satisfy this property, p (x) does not divide x5 -1.
What is interesting is fire codes become more efficient as we increase t. What is it mean?
Efficiency in terms of the code rate. So if you increase this t, you have on the y axis
the code rate and how do you get the code rate from here, n - k is the highest power
of this whole thing. So as you increase your t on the x axis, the code rate tends to go
up but your block length also tends to go up, so fire codes of large block lengths are
very useful.
Let us now speak briefly into a sub class of cyclic codes which is the Bose Chaudhuri
Hocquenghem codes or more popularly known as the BCH codes.
So the BCH codes are a sub class of cyclic codes which are a sub class of linear block
codes. The class of BCH codes is one of the most powerful known class of linear cyclic
block codes. The BCH codes are known for their multiple error correcting capabilities and
the ease of decoding and encoding. Now there is also paradigm shift, so far our approach
has been to construct a code and then find out its minimum distance. The BCH code tells
you please tell me how much is the desired minimum distance of the code and it will design
a code accordingly. So it’s an other way round so far we make a code we construct a
code and then find the minimum distance and we talk about how many errors it can correct.
If you go the other way round it tells you or it ask for the parameter how many errors
is required to be corrected by the code and then constructs a code accordingly. In this
case we start at the other end.
Now the class of BCH codes were discovered independently by Hocquenghem in 59 and Bose
Ray Chaudhuri in 60 and hence the name BCH. The Reed Solomon codes are a sub class of
BCH codes but an important sub class with a wide range of applications in digital signal
processing is to communications and data storage. The Reed Solomon codes were discovered by
Reed and Solomon who published a five page paper in the journal of society for industrial
and applied mathematics in 60.
Despite their advantages RS codes, the Reed Solomon codes did not go into use immediately
after their invention. Why? They had to wait for the hardware technology to catch by that
time. So today the very popular RS codes which we find in our CD, the audio CDs, the video
CDs even for deep space exploration and lot of wireless communication devices could not
be put into immediate use because the required technology was not there. So in 60’s there
was no such thing as fast digital electronics not by today’s standard.
So we will summarize today’s talk here. We started off by looking at the Galois field
followed by a detailed understanding of cyclic codes. We came up with an interesting polynomial
representation of cyclic codes.
We realize that there is a one to one correspondence between polynomials and cyclic codes, what
was interesting is that if you multiply a polynomial by x you right shift the codeword
elements and what is important is for cyclic codes any shift, any cyclic shift of the codewords
is also a valid codeword. Then we realize that there is a notion of a generator polynomial
in cyclic codes and then the analogy doesn’t stop there, you have a syndrome polynomial
and is a parity check polynomial.
We also realize the importance that you have to take modulo xn -1 so that when you multiply
g(x) by any valid polynomial you do not over the block length. Then we also realize that
g(x) the generator polynomial must be a factor of xn -1 thereby we figured out a way to come
up with all possible valid cyclic codewords of a certain block length n. All we have to
do is take xn -1 and factorize it and in front of our eyes will have all the possible valid
generator polynomials. We then moved over to the domain of burst error correction. We
realize that in mobile environments where we encounter deep fades, we tend to lose not
random bits but also bits which are in burst error so we lose a sequence of bits. Our regular
error control techniques are incapable of overcoming burst errors. We have to have special
kind of codes for that. We looked at certain cyclic codes which are known to be good burst
error correcting codes, one of the most important one is the fire codes.
We then briefly had a peak at the BCH codes which form an important sub class of cyclic
codes not only because you can very easily encode and decode them but also that you can
have a constructive strategy for BCH codes. At this moment in time please note that cyclic
codes BCH codes and Reed Solomon code which is a sub class of BCH codes though non-binary,
all form are from the linear block codes they all subsets of the linear block codes. So
all the techniques that we have learned and developed for linear block codes are also
valid for cyclic codes, your BCH codes and Reed Solomon codes. However in the subsequent
lectures we will look at efficient encoding, decoding strategies for Reed Solomon and BCH
codes as well. So this is a nice place to conclude our lecture and we will look at BCH
codes starting from the next class.