Studies on error linear complexity measures for multisequences

Abstract

In this thesis we develop a theory of $k$-error linearcomplexity for multisequences by introducing three new complexity measures,namely $k$-error joint linear complexity, $k$-error $\mathbb{F}_q$-linearcomplexity and $\vec{\bf k}$-error joint linear complexity. We find analogsof some of the known results in the single sequence case for the multisequencecase. Mainly, we establish various enumeration results and lower bounds on theexpected values of these error linear complexity measures in both the finitelength as well as the periodic case. Multisequences with period length a primeor a prime power receive greater attention in this thesis. In particular,in the latter case, we devise algorithms to compute the error linearcomplexity measures. In this case, we also give formulas for countingfunctions for the $1$-error joint linear complexity.We also present some results on periodic multisequences which possess maximaljoint linear complexity and large error linear complexity, and demonstratethat, for multisequences with suitable parameters, a major proportion ofthem have this property.