差错控制编码解决加性噪声 第14页

Definition 7   A linear code is called cyclic if

implies

For example, if is in a cyclic code, then is also in the code. The definition is recursive and so every cyclic shift of the elements is in the code.

In order to formalize the discussion we can use the following isomorphism 需要完整内容的请联系QQ3249114，转发请注明出处www.751com.cn

between the -dimensional vector space and the residue class of polynomials . Recall from algebra that

We can now speak of codewords in as the polynomials , and the following theorem follows

Theorem 2   A linear code in is a cyclic code if is an ideal in .

Proof. If is an ideal in and is any codeword, then is also a codeword. Thus If is cyclic, then for every codeword the word is also a codeword. Therefore is in for every , and since is linear is in for every polynomial . It follows that is an ideal.

The next theorem states the general structure of cyclic codes.

Theorem 3   Let be a cyclic code of length over a finite field . To each codeword , associate the polynomial in . Among all the nonzero polynomials obtained from in this way, let have the smallest degree. We may assume that is monic. This polynomial is called the generating polynomial for . Then

1. is uniquely determined by .

2. is a divisor of .

3. is exactly the set of coefficients of the polynomials of the form
with deg .

4. Write . Then corresponds
to an element of ,if .

Proof. (1)The codespace is spanned by the rows of a matrix. Because the row space of the matrix is closed under subtraction the difference between any two vectors, or polynomials, in the space is still in the space. So if there was another monic generating polynomial with minimum degree, then is also in the space. But this is a contradiction since this new polynomial has smaller degree than both and .

(2)Divide into . By the division algorithm we get

mod

where degdeg.

But multipying by powers of corresponds to a cyclic shift of the corresponding code vector and multiplication by a polynomial is thus a linear combination of the codevectors in the generating matrix and all of their cyclic shifts. So is in the code space of . Since degdeg, must be equal to zero. Thus . Notice then that is not a field since it has zero divisors.

(3)Let correspond to an element in . Divide into

with degdeg. From (2) we know that corresponds to a codeword and by assumption so does . So, since is closed under subtraction, modis also a codeword. But this is just and has degree less than . It follows that and is the product of the generating polynomial with another polynomial. Because each codeword has length , deg so deg deg. Conversely, we have shown that the product of any two polynomials is in . Thus, these polynomials yield all of the code words of .

(4)By (2) we can write . Let correspond to an element in . Then by (3)

mod

Next suppose that mod. Then

for some polynomial . We can now divide through by and get

 << 上一页  [11] [12] [13] [14] [15] 下一页