burrage2.pdf (214.12 kB)
Linear complexity for sequences with characteristic polynomial fv
conference contributionposted on 2012-03-16, 16:26 authored by Alex J. Burrage, Ana SalageanAna 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.
- Computer Science
CitationBURRAGE, 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
- NA (Not Applicable or Unknown)
NotesPersonal 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.