Registre à décalage

En électronique et en informatique, un registre à décalage est un registre de taille fixe dans lequel les bits sont décalés à chaque coup d'horloge.



Catégories :

Matériel informatique - Circuit intégré logique - Circuit intégré - Composant actif - Composant électronique - Processeur

Page(s) en rapport avec ce sujet :

  • Définition 1 Un registre à décalage à rétroaction linéaire binaire de longueur. L se compose d'un registre à décalage contenant une suite de L bits... (source : iml.univ-mrs)
  • ... Un registre à décalage, c'est une série de bascules, organisées de telle sorte... (Tx -> Rx) transmet une série de bits, qu'on reconstitue à l'arrivée... (source : forums.futura-sciences)

En électronique et en informatique, un registre à décalage est un registre de taille fixe dans lequel les bits sont décalés à chaque coup d'horloge (dans le cas d'un dispositif synchrone sur l'horloge).

Un registre à décalage est généralement constitué d'un chaînage de bascules synchronisées sur l'horloge, la sortie d'une bascule étant reliée à l'entrée de la suivante. Il se décline en plusieurs variantes :

Les entrées ou sorties en parallèle permettent d'insérer et de récupérer plusieurs bits en même temps. Prenons exemple d'une information de 4 bits (ex : 1001).

Signalons aussi l'existence de registres à décalage réversibles, càd. de registres où le décalage s'effectue vers la droite ou vers la gauche selon le niveau logique appliqué à l'entrée "Sens de décalage".

Registre à décalage SISO ou SIPO

Exemples d'applications

Registre à décalage avec rétroaction linéaire

Article détaillé : Linear feedback shift register.

Fréquemment nommé LFSR, pour Linear Feedback Shift Register en anglais, c'est une variante avec une unité logique ou arithmétique L'ou les bit (s) en sortie du registre subissent une série d'opérations et de transformations pour être réinsérés dans le registre. Ce type de registre est utilisé en cryptographie pour les implantations matérielles de certains algorithmes de chiffrement de flot. On les retrouve aussi dans certains microprocesseurs dédiés au traitement de signal (DSP), surtout pour le filtrage. Ce type de circuit est aussi utilisé lors de la phase de test des circuits intégrés en donnant la possibilité la génération automatique d'entrées (vecteurs de tests).

Rétroaction basée sur un XOR entre plusieurs bits

Représentation par les suites

Les suites de bits pouvant être produites par un registre à décalage à rétroaction linéaire sont simples à décrire mathématiquement : ce sont les suites récurrentes linéaires. C'est à dire, on peut obtenir le terme t+n∼ à partir des termes t,...,t+n-1∼ par une équation linéaire du type

u_{t+n}= \alpha_n u_{t}+\alpha_{n-1} u_{t+1}+...+\alpha_{1} u_{t+n-1}∼

où les \alpha_i∼ valent 0 ou 1.

Représentation polynômiale

Il est aussi envisageable de les décrire en utilisant les séries formelles :

si à une suite U=(u_i)∼ on associe la série U(X)=\sum_{i=0}ˆ{\infty} u_iXˆi∼ alors l'équation ci-dessus peut se mettre sous la forme suivante :

U(X) P(X)= T(X)∼

Le polynôme T∼ correspond à l'initialisation du registre, tandis que le polynôme P, nommé polynôme de rétroaction, caractérise le registre.

Périodicité

Il est facile de voir qu'une suite produite par un tel registre est obligatoirement périodique : le nombre de possibilité pour un n-uplet est au plus de 2n, par conséquent f:t\mapsto
(u_{t},...,u_{t+n-1}) est surjective, soit \exists t_0,t_1,
f(t_0)=f(t_1). Mais, clairement on a \forall x,y et i, f(x)=f(y)\Rightarrow f(x+i)=f(y+i). En prenant i = max (t0t1, t1t0) on a par conséquent un multiple de la période de la suite.

La période maximale est 2n − 1 car si le n-uplet tout à zéro est atteint, la suite est obligatoirement constante égal à zéro. On sait prévoir quand cette valeur atteinte, une condition indispensable et suffisante étant que le polynôme de rétroaction soit primitif -- i. e. est irréductible et tel que, dans l'anneau F2[X] des polynômes à cœfficients binaires, le plus petit t tel que ce polynôme divise Xt − 1 est 2n − 1 (c'est le polynôme minimal d'un élément d'ordre multiplicatif 2n − 1 dans le corps à 2n éléments).

Une suite de période maximale est nommée m-sequence dans la terminologie anglo-saxonne.

Notion de complexité linéaire

Tout m-uplet de bits peut être généré par un LFSR. Plus exactement, il existe toujours un LFSR -- i. e. un polynôme de rétroaction ainsi qu'une initialisation -- tel que les m premières sorties de ce LFSR correspondent au m-uplet. Dans le pire des cas on prend un registre de longueur m, le polynôme de rétroaction important peu dans ces conditions.

Ceci donne lieu à la définition de la complexité linéaire d'une suite (finie) comme la longueur minimale d'un LFSR généré cette suite. Comme le prouve la remarque ci-dessus cette complexité est bornée supérieurement par la longueur de la suite.

Cette notion intervient surtout en cryptographie à cause de l'existence de l'algorithme de Berlekamp-Massey.

Registre à décalage et cryptographie

Génération de pseudo-aléatoire

Un problème essentiel en cryptologie est la production de suites de bits «aussi aléatoires que envisageable». Un exemple évident étant la génération des clefs de chiffrement (symétrique ou asymétrique).

Ce problème se décompose en fait en deux parties : d'une part la génération de bits par des procédés physiques -- mesure de temps entre frappes de touches sur un clavier, déplacement de la souris, ... --, et d'autre part l'expansion d'une courte suite aléatoire de bits en une suite bien plus grande. Dans ce dernier cas, on parle de suite pseudo-aléatoire.

Le chiffrement par masque jetable illustre bien les enjeux. Dans ce chiffrement, le texte chiffré est produit par addition bit à bit (modulo 2) de la clef de chiffrement. Le déchiffrement est aussi effectué par addition bit à bit de la clef. Le problème est qu'il est alors indispensable de partager une donnée secrète, à savoir la clef, de la même taille que le message à échanger. C'est fréquemment impraticable. Vient alors l'idée d'engendrer la clef à partir d'un procédé déterministe -- il faut pouvoir le faire au chiffrement et au déchiffrement -- utilisant une donnée secrète plus petite. C'est certainement légèrement de là l'origine du chiffrement par flot.

Une première possibilité consiste à choisir un LFSR ainsi qu'à utiliser la donnée secrète partagée comme initialisation du registre. Cependant, l'algorithme de Berlekamp-Massey met vite fin à cette tentative : une connaissance même particulièrement partielle de la suite produite sert à retrouver l'ensemble des informations voulues.

Dans la pratique, les LFSRs ne sont par conséquent pas utilisés de manière isolée, mais principalement sous la forme des registres combinés ou filtrés.

Algorithme de Berlekamp-Massey

Un LFSR de taille n produisant des suites récurrentes linéaires d'ordre n, la connaissance de n termes consécutifs d'une suite et de l'équation linéaire -- ou bien de manière équivalente le polynôme de rétroaction -- détermine toute la suite.

Si désormais on ne suppose plus connu le polynôme de rétroaction, que peut-on déduire de l'observation d'une partie de la sortie du LFSR, par exemple les termes u_{t_0},u_{t_0+1},...,u_{t_0+L-1} ? L'algorithme de Berlekamp-Massey répond à cette question de la façon suivante : si L est supérieur où égal à deux fois la taille du plus petit LFSR générant la suite (ui) alors on peut retrouver le polynôme de rétroaction et l'initialisation du registre. En abrégé : tout. On voit ainsi apparaître la complexité linéaire comme le paramètre permettant d'estimer la quantité d'information indispensable pour recréer une suite sous forme de LFSR.

L'algorithme de Berlekamp-Massey fut introduit en 1969 par James Massey (Massey, J. L. "Shift-Register Synthesis and BCH Decoding. " IEEE Trans. Information Th. 15, 122-127, 1969. ). C'est une adaptation d'un algorithme, dû à Elwyn Berlekamp, de décodage de codes correcteurs -- les codes de Bose-Chaudhuri-Hocquenghem.

Utilisation

Voir aussi

Liens externes


Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Registre_%C3%A0_d%C3%A9calage.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 07/04/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu