## Abstract

Non-trivial lower bounds on the linear complexity are derived for a sequence obtained by performing a combination of up to k substitutions, insertions, and deletions. The bounds derived are similar to those previously established for either k substitutions, k insertions or k deletions within a single period. The bounds are useful when T/2k < λ < T/k, where λ is the linear complexity of the original sequence and T is its period. It is shown that similar bounds hold for the joint linear complexity of periodic multisequences. Similar results are obtained for the N-adic complexity of periodic sequences over {0,... , N - 1}. New non-trivial lower bounds on the minimum number of operations needed to decrease the complexity are also given. The derivations are simpler compared to those in previous work on these problems.

Original language | English |
---|---|

Pages (from-to) | 95-116 |

Number of pages | 22 |

Journal | Cryptography and Communications |

Volume | 1 |

Issue number | 1 |

DOIs | |

State | Published - Apr 2009 |

### Bibliographical note

Funding Information:This material is based upon work supported by the National Science Foundation under Grant No. CCF-0514660. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

## Keywords

- FCSR
- LFSR
- Linear complexity
- N-adic complexity
- k-error complexity

## ASJC Scopus subject areas

- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics