Linear complexity of transformed sequences

Abstract : This paper deals with the effect of bit change errors on the linear complexity of finite sequences. Though a change in a single bit can cause a large change in linear complexity, it is shown that on the average the change will be small even when many bits, e.g. 10 % are changed. General bijections and k-fold mappings on the set of sequences of length n are studied and tight bounds are found on the average difference in linear complexity between a sequence and its image. It is also shown that any mapping, on sequences of length n that take most sequences to images of low linear complexity must take many sequences to images that are far away from them in Hamming distance.
Type de document :
RR-1168, INRIA. 1990
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 18:07:27
Dernière modification le : vendredi 16 septembre 2016 - 15:11:36
Document(s) archivé(s) le : mardi 12 avril 2011 - 18:48:34



  • HAL Id : inria-00075390, version 1



H. Fell. Linear complexity of transformed sequences. RR-1168, INRIA. 1990. 〈inria-00075390〉



Consultations de la notice


Téléchargements de fichiers