Calculateur LFSR - Registre à décalage linéaire

Un registre à décalage à rétroaction linéaire (LFSR) est un registre à décalage dont le bit d’entrée est une fonction linéaire (XOR) de certains bits de son état précédent. À chaque cycle d’horloge, le registre décale tous ses bits d’une position, le nouveau bit d’entrée est calculé en faisant XOR des bits situés à des positions spécifiques appelées taps de rétroaction, et la sortie est le bit décalé hors du registre. La séquence binaire obtenue semble aléatoire, mais elle est entièrement déterministe et se répète selon une période qui dépend de la longueur du registre et du choix des taps. Les LFSR sont largement utilisés dans les communications numériques, la cryptographie, les circuits BIST (built-in self-test), les systèmes à étalement de spectre et la génération de nombres pseudo-aléatoires. Comme un LFSR à n étages peut produire au maximum 2ⁿ − 1 bits avant de se répéter (l’état tout à zéro est exclu), et comme cette séquence de longueur maximale peut être obtenue avec des taps de polynômes primitifs soigneusement choisis, les LFSR constituent une implémentation matérielle efficace du pseudo-aléatoire. Il existe deux architectures courantes de LFSR. Dans le LFSR Fibonacci (rétroaction externe), le bit de rétroaction est calculé à partir d’un ensemble fixe de positions de taps, puis injecté dans l’étage le plus à gauche, tandis que tous les autres étages se décalent vers la droite. La sortie est prise sur l’étage le plus à droite. Dans le LFSR Galois (rétroaction interne), le bit de rétroaction est XORé directement dans plusieurs étages intermédiaires au lieu d’être renvoyé uniquement vers l’entrée. Les LFSR Galois sont plus rapides en matériel parce que toutes les opérations XOR se font en parallèle plutôt qu’en série. Un LFSR de longueur maximale — c’est-à-dire un LFSR qui parcourt les 2ⁿ − 1 états non nuls avant de se répéter — nécessite un polynôme primitif comme polynôme de rétroaction. Les positions de taps correspondent aux coefficients non nuls de ce polynôme. Pour un LFSR 4 bits avec des taps aux positions 4 et 3, le polynôme primitif est x⁴ + x³ + 1, et le LFSR parcourt les 15 états non nuls. Ce calculateur vous permet d’explorer toute combinaison de longueur de registre, seed, positions de taps et type de LFSR. Vous pouvez vérifier si les taps choisis produisent une séquence de longueur maximale en contrôlant la période dans les résultats — si la période vaut 2ⁿ − 1, les taps forment un polynôme primitif. Utilisez les exemples fournis pour voir des configurations de longueur maximale connues. Les applications des LFSR couvrent de nombreux domaines. Dans le Wi‑Fi et le Bluetooth, les LFSR fournissent les codes d’étalement pour le saut de fréquence et l’étalement de spectre à séquence directe. Dans le stockage et les communications, les circuits CRC (contrôle de redondance cyclique) sont implémentés comme des LFSR. Dans les chiffrements de flux cryptographiques, les LFSR constituent le primitif central (bien que les chiffrements modernes combinent plusieurs LFSR avec des composants non linéaires pour résister à la cryptanalyse linéaire). Dans le test de puces, l’analyse de signature basée sur LFSR compresse les données de réponse de test en une signature compacte.