Fast Multi-Sequence Shift-Register Synthesis with the Euclidean Algorithm

Abstract : Feng and Tzeng's generalization of the Extended Euclidean Algorithm synthesizes the shortest--length linear feedback shift--register for \$s \geq 1\$ sequences, where each sequence has the the same length \$n\$. In this contribution, it is shown that Feng and Tzeng's algorithm which solves this multi--sequence shift--register problem has time complexity \$\ONsn^2\$. An acceleration based on the Divide and Conquer strategy is proposed and it is proven that subquadratic time complexity is achieved.
Mots-clés : euclid irs multisequence
Type de document :
Article dans une revue
Advances in Mathematics of Communications, AIMS, 2011, 5 (4), pp.667-680. 〈10.3934/amc.2011.5.667〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00647586
Contributeur : Alexander Zeh <>
Soumis le : vendredi 2 décembre 2011 - 12:41:13
Dernière modification le : mercredi 28 novembre 2018 - 15:36:02
Document(s) archivé(s) le : samedi 3 mars 2012 - 02:30:51

Fichier

zeh_11_fast_713877.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Citation

Alexander Zeh, Antonia Wachter. Fast Multi-Sequence Shift-Register Synthesis with the Euclidean Algorithm. Advances in Mathematics of Communications, AIMS, 2011, 5 (4), pp.667-680. 〈10.3934/amc.2011.5.667〉. 〈hal-00647586〉

Partager

Métriques

Consultations de la notice

638

Téléchargements de fichiers

539