web.syr.edu/~rrosenqu/ecc/cyclic.htm
Contents Cyclic Codes Introduction Cyclic codes are much studied and very useful error correcting codes. BCH codes (developed by Bose, Chaudhuri, and Hocquenghem) are a very important type of cyclic codes. Reed-Solomon codes are a special type of BCH codes that are commonly used in compact disc players. The cyclic codes we will explore on this page are also linear codes. The cyclical nature of these codes will give them more structure than was given us for linear codes on the last page. This added structure will help us in the decoding process and also provides more efficient implementation into hardware of the encoding and decoding processes.
Addition, multiplication and division should all be done as usual. Here, for those that are rusty on polynomial division, is an example. Thus 1 + x^2 divides 1 + x + x^2 + x^5 evenly and the result is 1 + x + x^3. For the decoding algorithm we'll also need to know how to do arithmetic modulo p, where p is a polynomial. This will involve to find f(mod p) you simply divide f by p and take the remainder. Note that if the degree (the number corresponding to the highest exponent present)of f is smaller than p then the result is simply f Example 2 Compute 1 + x^2 + x^5 (mod 1 + x^2). Notice that the cyclic shift of codewords of length n is accomplished nicely in polynomials by multiplying a polynomial by x and finding the remainder modulo x^n + 1. Example 3 Shift the codeword 1011 to the right once using polynomial manipulation. The vector 1011 corresponds to the polynomial 1 + x^2 + x^3. To Shift this polynomial to the right one we first multiply by x to get x + x^3 + x^4. Then we find x + x^3 + x^4 (mod x^n + 1) = x + x^3 + x^4 (mod x^4 + 1). Now 1 + x + x^3 corresponds to 1101 which is 1011 shifted once to the right. The Generator Polynomial To encode a message word in a cyclic code we first find the correspond polynomial then multiply it by a generating polynomial.
Theorem g is the generator polynomial for a linear cyclic code of length n if and only if g divides 1 + x^n. What this is saying is that to find generator polynomial g we must factor x^n + 1 for whichever length of codewords, n, we want. If n is the length of the code the length of the code, k = n - deg(g) where deg(g) denotes the degree of g. Example 4 Find a generating polynomial and for a code of length n = 15 which will encode messages of length k = 7. If we are to find a generator for a code of length 15 to encode messages of length 7 we need to find a divisor of x^15 + 1 of degree 15 - 7 = 8. The polynomial x^15 + 1 can be written as x^15 + 1 = (1 + x)(1 + x + x^2)(1 + x + x^2 + x^3 + x^4)(1 + x + x^4)(1 + x^3 + x^4) so we can choose g = (1 + x + x^2 + x^3 + x^4)(1 + x + x^4) = 1 + x^4 + x^6 + x^7 + x^8. Using this generator polynomial we can create a code with minimum distance of 5 and thus correct 2 errors. Now that we have a generator polynomial we can use it to encode our message, 0110110 . The polynomial corresponding to this vector is x + x^2 + x^4 + x^5.
|
http://csua.com/feed/