Linear recurring sequences and subfield subcodes

摘要

Linear recurring sequences over finite fields play an important role in coding theory and cryptography. It is known that subfield subcodes of linear codes yield some good codes. In this paper, we study linear recurring sequences and subfield subcodes. Let Mq^m(f(x)) denote the set of all linear recurring sequences over Fq^m with characteristic polynomial f(x) over Fq^m. Denote the restriction of Mq^m(f(x)) to sequences over Fq and the set after applying trace function to each sequence in Mq^m(f(x)) by Mq^m(f(x))|Fq and Tr(Mq^m(f(x))), respectively. It is shown that these two sets are both complete sets of linear recurring sequences over Fq with some characteristic polynomials over Fq. In this paper, we firstly determine these characteristic polynomials for the two sets. Then, using these results, we determine the generator polynomials of subfield subcodes and trace codes of cyclic codes over Fq^m.