burrage2.pdf (214.12 kB)
Download fileLinear complexity for sequences with characteristic polynomial fv
conference contribution
posted on 2012-03-16, 16:26 authored by Alex J. Burrage, Ana SalageanAna Salagean, Raphael C.-W. PhanWe 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 - 692Publisher
© IEEEVersion
- NA (Not Applicable or Unknown)
Publication date
2011Notes
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;9781457705960ISSN
2157-8095Publisher version
Language
- en