burrage2.pdf (214.12 kB)
0/0

Linear complexity for sequences with characteristic polynomial fv

Download (214.12 kB)
conference contribution
posted on 16.03.2012 by Alex J. Burrage, Ana Salagean, Raphael C.-W. Phan
We present several generalisations of the Games- Chan algorithm. For a fixed monic irreducible polynomial f we consider the sequences s that have as characteristic polynomial a power of f. We propose an algorithm for computing the linear complexity of s given a full (not necessarily minimal) period of s. We give versions of the algorithm for fields of characteristic 2 and for arbitrary finite characteristic p, the latter generalising an algorithm of Kaida et al. We also propose an algorithm which computes the linear complexity given only a finite portion of s (of length greater than or equal to the linear complexity), generalising an algorithm of Meidl. All our algorithms have linear computational complexity. The algorithms for computing the linear complexity when a full period is known can be further generalised to sequences for which it is known a priori that the irreducible factors of the minimal polynomial belong to a given small set of polynomials.

History

School

  • Science

Department

  • Computer Science

Citation

BURRAGE, A.J., SALAGEAN, A.M. and PHAN, R.C.-W., 2011. Linear complexity for sequences with characteristic polynomial fv. IN: IEEE International Symposium on Information Theory Proceedings, (ISIT), St. Petersburg, Russia, July 31 - Aug 5th., pp. 688 - 692

Publisher

© IEEE

Version

NA (Not Applicable or Unknown)

Publication date

2011

Notes

Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

ISBN

9781457705946;9781457705960

ISSN

2157-8095

Language

en

Exports

Logo branding

Keyword(s)

Exports