Transcript Week7_1

Cyclic Codes
• Hamming code is useful but there exist codes
that offers same (if not larger) error control
capabilities while can be implemented much
simpler.
• Cyclic code is a linear code that any cyclic shift
of a codeword is still a codeword.
• Makes encoding/decoding much simpler, no
need of matrix multiplication.
Cyclic code
• Polynomial representation of cyclic codes, here,
assume all coefficients are either 0 or 1.
• That is, if your code is (1010011) (c6 first, c0 last),
you write it as
• Addition and subtraction of polynomials --- Done by
doing binary addition or subtraction on each bit
individually, no carry and no borrow.
• Division and multiplication of polynomials. Try divide
by
.
Cyclic Code
• A (n,k) cyclic code can be generated by a
polynomial g(x) which has degree n-k and is a
factor of xn-1. Call it the generator polynomial.
• Given message bits, (mk-1, …, m1, m0), the
code is generated simply as:
• In other words, C(x) can be considered as the
product of m(x) and g(x).
Example
• A (7,4) cyclic code g(x) = x3+x+1.
• If m(x) = x3+1, C(x) = x6+x4+x+1.
Cyclic Code
• One way of thinking it is to write it out as the
generator matrix
• So, clearly, it is a linear code. Each row of the
generator matrix is just a shifted version of the
first row. Unlike Hamming Code.
• Why is it a cyclic code?
Example
• The cyclic shift of C(x) = x6+x4+x+1 is C1(x) =
x5+x2+x+1.
• It is still a code polynomial, because it the
code polynomial if m(x) = x2+1.
Cyclic Code
• Given a code polynomial
• We have
• C1(x) is the cyclic shift of C(x) and (1) has a
degree of no more than n-1 and (2) divides
g(x) (why?) hence is a code polynomial.
Cyclic Code
• So, to generate a cyclic code is to find a
polynomial that (1) has degree n-k and (2) is a
factor of xn-1.
Generating Systematic Cyclic Code
• A systematic code means that the first k bits
are the data bits and the rest n-k bits are
parity checking bits.
• To generate it, you let
where
• The claim is that C(x) must divide g(x) hence is
a code polynomial. 33 mod 7 = 5. Hence 335=28 can be divided by 7.
Division Circuit
• Division of polynomials can be done efficiently by the
division circuit. (just to know there exists such a thing, no
need to understand it)
Remaining Questions for Those Really
Interested
• Decoding. Divide the received polynomial by
g(x). If there is no error you should get a 0
(why?). Make sure that the error polynomial
you have in mind does not divide g(x).
• How to make sure to choose a good g(x) to
make the minimum degree larger? Turns out
to learn this you have to study more – it’s the
BCH code.
Finite Field
• A field is a set of elements plus the + and *
operation:
Finite Field
• Continued…
Finite field
• A finite field is a field with finite number of
elements.
• The simplest field is the binary field: {0,1}. The
+ operation is bitwise xor and the * operation
is bitwise and.
• All requirements satisfied.
Beyond finite field
• Why do we have to deal with fields other than
the binary field?
– Better code can be constructed.
• We only consider the extension field of the
binary field.
• GF(2m) contains 2m elements.
GF(2m)
• It is convenient to represent the 2m elements
in GF(2m) as polynomials.
– The difference with the cyclic code is that here the
polynomial represent the element, not a
codeword!
– The 8 element in GF(23) can be represented as:
GF(23)
•
represents ith polynomial in GF(23).
• The + operation is defined as adding two
polynomials:
• For example,
GF(23)
• The * operation is defined as
where f(y) has degree 3 and is irreducible
(cannot be expressed as the product of two
polynomials )and is called the “base
polynomial.”
• For example, f(y)=y3+y+1.
GF(23)
• 0 and 1 element in GF(23) are just 0 and 1,
respectively.
• As long as f(y) is irreducible, other
requirements all satisfy.
– For example, the reciprocal of an element. An
element multiplying all other elements must
result in different results if f(y) is irreducible.
Primitive element
• Consider the power series an element:
• Because the number of elements is finite, at
some point, it will repeat a previous element.
• We will be able to find
, and therefore
and we say it has order n.
• It can be shown that there exists an element
with order 2m-1.
• This element is called the primitive element
and denoted as
Primitive element
• The powers of the primitive element
generates all elements. Let
• Non-primitive elements may have order less
than 2m-1, but are all factors of it.
Finite Field
• After defining the elements in the finite filed
and the + and * operation, we can plug an
element into a polynomial.
• For example, if g(x) = x4+x3+x2+1 , and we
substitute x with . That is, find the value of
• Since
the result is 0.
• In this sense, is the root of g(x).
Minimum Polynomial
• Given an element, the minimum polynomial is
defined as the minimum degree polynomial
such that this element is a root of it.
• The minimum polynomial is irreducible.
BCH code
• The BCH code is defined on some finite field
GF(q). Meaning that the elements in the
codeword must be from GF(q).
• The requirement is that the length of the code n
must be n=qm-1 for some m.
• Given m and n, suppose is a primitive element
of GF(qm) with order n.
• Get d-1elements:
• The generator polynomial is the least common
multiple of the product of the minimum
polynomials for
BCH code
• The BCH code has minimum distance d.
• Proof: Suppose the minimum distance is less
than d. It means that there exists a code
polynomial with less than d non-zero
coefficients. Let this code polynomial be
so, because
we have
are the roots of C(x),
BCH code
• This means that
• Or, the determinant of the matrix must be 0
BCH code
•