Linear recurring sequences and subfield subcodes of cyclic codes

详细信息    查看全文

• 作者：ZhiHan Gao (14633)
  FangWei Fu (14633)
  
• 关键词：linear recurring sequences ; characteristic polynomial ; cyclic codes ; subfield subcodes ; trace codes ; 94A55 ; 94B15
• 刊名：SCIENCE CHINA Mathematics
• 出版年：2013
• 出版时间：July 2013
• 年：2013
• 卷：56
• 期：7
• 页码：1413-1420
• 全文大小：220KB
• 参考文献：1. Delsarte P. On subfield subcodes of modified Read-Solomon codes. IEEE Trans Inform Theory, 1975, 21: 575鈥?76 CrossRef
  2. Gao Z H, Fu F W. The minimal polynomial over $\mathbb{F}_q$ of linear recurring sequence over $\mathbb{F}_{q^m }$ . Finite Fields Appl, 2009, 15: 774鈥?84 CrossRef
  3. Gao Z H, Fu F W. The minimal polynomial of a sequence obtained from the componentwise linear transformation of a linear recurring sequence. Theor Comput Sci, 2010, 411: 3883鈥?893 CrossRef
  4. Lidl R, Niederreiter H. Finite Fields. Massachusetts: Addison-Wesley Publishing Company, 1983
  5. Niederreiter H. Sequences with almost perfect linear complexity profile. In: Chaum D, Price W L, eds. Advances in Cryptology-EUROCRYPT. Lectures Notes on Computer Science, vol. 304. Berlin: Springer, 1987, 37鈥?1
  6. Shibuya T, Matsumoto R, Sakaniwa K. Simple estimation for the dimension of subfield subcodes of AG codes. IEICE Trans Fundam, 1997, 80: 2058鈥?065
  7. Shibuya T, Matsumoto R, Sakaniwa K. An improved bound for the dimension of subfield subcodes. IEICE Trans Fundam, 1997, 80: 876鈥?80
  8. Stichtenoth H. On the dimension of subfield subcodes. IEEE Trans Inform Theory, 1990, 36: 90鈥?3 CrossRef
  9. Wan Z X. Algebra and Coding, 3rd ed (in Chinese). Beijing: Higher Education Press, 1997
  10. Youssef A M, Gong G. On linear complexity of sequences over / GF(2ⁿ). Theor Comput Sci, 2006, 352: 288鈥?92 CrossRef
  
• 作者单位：ZhiHan Gao (14633)
  FangWei Fu (14633)
  
  14633. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, N2L3G1, Canada
  

文摘

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 $\mathcal{M}_{q^m } (f(x))$ denote the set of all linear recurring sequences over $\mathbb{F}_{q^m }$ with characteristic polynomial f(x) over $\mathbb{F}_{q^m }$ . Denote the restriction of $\mathcal{M}_{q^m } (f(x))$ to sequences over $\mathbb{F}_q$ and the set after applying trace function to each sequence in $\mathcal{M}_{q^m } (f(x))$ by $\left. {\mathcal{M}_{q^m } (f(x))} \right|_{\mathbb{F}_q }$ and $Tr\left( {\mathcal{M}_{q^m } \left( {f\left( x \right)} \right)} \right)$ , respectively. It is shown that these two sets are both complete sets of linear recurring sequences over $\mathbb{F}_q$ with some characteristic polynomials over $\mathbb{F}_q$ . In this paper, we firstly determine the characteristic polynomials for these two sets. Then, using these results, we determine the generator polynomials of subfield subcodes and trace codes of cyclic codes over $\mathbb{F}_{q^m }$ .