On the linear complexity of functions of periodic GF(q) sequences

It is proved that the product of arbitrary periodic GF(q) sequences attains maximum linear complexity if their periods are pairwise coprime. The necessary and sufficient conditions are derived for maximum linear complexity of the product of two periodic GF(q ) sequences with irreducible minimal characteristic polynomials. For a linear combination of products of arbitrary periodic GF(q) sequences, it is shown that maximum linear complexity is achieved if their periods are pairwise coprime and the polynomial x -1 does not divide any of their minimal characteristic polynomials; assuming only that their periods are pairwise coprime, the author establishes a lower bound on the linear complexity which is of the same order of magnitude as maximum linear complexity. Boolean functions are derived that are optimal with respect to the maximum linear complexity. Possible applications of the results in the design of sequence generators are discussed