09-05-2012, 12:04 PM
Cyclic and convolution codes
CHAPTER 03 - Cyclic codes.ppt (Size: 198.5 KB / Downloads: 177)
Cyclic codes are of interest and importance because
They posses rich algebraic structure that can be utilized in a variety of ways.
They have extremely concise specifications.
They can be efficiently implemented using simple shift registers.
Many practically important codes are cyclic.
FREQUENCY of CYCLIC CODES
Comparing with linear codes, the cyclic codes are quite scarce. For, example there are 11 811 linear (7,3) linear binary codes, but only two of them are cyclic.
Trivial cyclic codes. For any field F and any integer n >= 3 there are always the following cyclic codes of length n over F:
No-information code - code consisting of just one all-zero codeword.
Repetition code - code consisting of codewords (a, a, …,a) for a Î F.
Single-parity-check code - code consisting of all codewords with parity 0.
No-parity code - code consisting of all codewords of length n
For some cases, for example for n = 19 and F = GF(2), the above four trivial cyclic codes are the only cyclic codes.
ENCODING of CYCLIC CODES II
Another method for encoding of cyclic codes is based on the following (so called systematic) representation of the generator and parity-check matrices for cyclic codes.
Theorem Let C be an (n,k)-code with generator polynomial g(x) and r = n - k. For i = 0,1,…,k - 1, let G2,i be the length n vector whose polynomial is G2,i(x) = x r+I -x r+I mod g(x). Then the k * n matrix G2 with row vectors G2,I is a generator matrix for C.
Moreover, if H2,J is the length n vector corresponding to polynomial H2,J(x) = xj mod g(x), then the r * n matrix H2 with row vectors H2,J is a parity check matrix for C. If the message vector m is encoded by
m Þ c = mG2,
then the relation between corresponding polynomials is
c(x) = xrm(x) - [xrm(x)] mod g(x).
On this basis one can construct the following shift-register encoder for the case of a systematic representation of the generator for a cyclic code: