Registre à décalage

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un registre à décalage est un registre, c'est-à-dire un ensemble de bascules synchrones, dont les bascules sont reliées une à une, à l'exception de deux bascules qui ne sont pas forcément reliées. À chaque cycle d'horloge, le nombre représenté par ces bascules est mis à jour.

Types[modifier | modifier le code]

Registre à décalage SISO ou SIPO

Différents types de registre à décalage existent :

  • SISO (Serial In - Serial Out) : à chaque cycle d'horloge, on ne peut écrire que dans une bascule (lorsque deux bascules ne sont pas reliées entre elles, c'est celle dont l'entrée n'est pas reliée à une autre bascule), et on ne peut lire qu'une autre (lorsque deux bascules ne sont pas reliées entre elles, c'est celle dont la sortie n'est pas reliée à une autre bascule)
  • SIPO (Serial In - Parallel Out) : à chaque cycle d'horloge, on ne peut écrire que dans une bascule (lorsque deux bascules ne sont pas reliées entre elles, c'est celle dont l'entrée n'est pas reliée à une autre bascule), mais on peut lire les valeurs de toutes les bascules
  • PISO (Parallel In - Serial Out) : à chaque cycle d'horloge, on peut forcer la valeur de toutes les bascules, mais on ne peut en lire qu'une (lorsque deux bascules ne sont pas reliées entre elles, c'est celle dont la sortie n'est pas reliée à une autre bascule)
  • PIPO (Parallel In - Parallel Out) : à chaque cycle d'horloge, on peut forcer la valeur de toutes les bascules, et on peut toutes les lire

Le registre à décalage réversible est un registre à décalage où le décalage s'effectue vers la droite ou vers la gauche en fonction du niveau logique appliqué à l'entrée "Sens de décalage".

Exemples d'applications[modifier | modifier le code]

  • SISO : L'information que l'on veut introduire dans le registre est présentée à l'entrée de la première bascule. Lors d'une impulsion d'horloge, le bit d'information est introduit dans le registre, et tous les autres bits sont décalés. Le bit qui était mémorisé dans la dernière bascule est perdu s'il n'est pas stocké ou réinséré dans la structure d'une manière quelconque. Les registres SISO sont utilisés pour réaliser des lignes à retard numériques (en). Le délai entre l'entrée de l'information dans le registre et sa sortie dépend du nombre de bascules et de la fréquence d'horloge.
  • PIPO : En décalant tous les bits d'un nombre binaire vers la droite ou vers la gauche, on divise ou on multiplie le nombre par 2. Un registre PIPO peut donc être utilisé pour effectuer des calculs (multiplication ou division par une puissance de 2). Il suffit d'opérer le nombre adéquat de décalages vers la gauche ou la droite entre le moment où l'on introduit les bits dans le registre et le moment où on les récupère.
  • PISO et SIPO : Ces deux types de registres sont utilisés dans les liaisons série ; ils forment la base des UART et des modems. Imaginons que l'on veuille transmettre une information entre deux ordinateurs distants de quelques mètres ou dizaines de mètres. Transmettre l'information sous forme "parallèle" nécessiterait au moins 9 fils (8 pour les 8 bits, un pour la masse), sans compter les fils supplémentaires pour le dialogue entre les ordinateurs. Il est plus simple d'employer un registre PISO pour envoyer les bits constituant chaque octet que l'on désire transmettre en une suite de 8 bits apparaissant l'un après l'autre sur une seule ligne. Au bout de la ligne, un registre SIPO reçoit les bits qui arrivent à la queue-leu-leu et reconstitue des octets qui sont transmis à l'ordinateur de destination.
  • Registres SISO réversibles : Ils permettent par exemple de réaliser ce que l'on appelle des piles LIFO (Last In, First Out) : on charge les bits dans le registre ; puis on inverse le sens du décalage. Les bits apparaissent à la sortie de la première bascule dans l'ordre inverse de leur entrée.

Registre à décalage avec rétroaction linéaire[modifier | modifier le code]

Article détaillé : Linear feedback shift register.

Un LFSR, ou Linear Feedback Shift Register, est une variante avec une unité logique ou arithmétique. Le 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), en particulier pour le filtrage. Ce type de circuit est aussi utilisé lors de la phase de test des circuits intégrés en permettant la génération automatique d'entrées (vecteurs de tests).

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

Les suites de bits produites par un registre à décalage à rétroaction linéaire sont des suites récurrentes linéaires sur le corps fini à deux éléments F2. Elles sont nécessairement périodiques à partir d'un certain rang. Cette période est de longueur maximale 2n -1, où n est la taille du registre. La longueur est atteinte si le polynôme caractéristique de la matrice de la suite récurrente linéaire est un polynôme primitif. Il suffit cependant des 2n premiers bits de cette suite pour déterminer entièrement le dispositif, c'est-à-dire la fonction de rétroaction (n bits) et une initialisation du registre (n bits également), et on peut les obtenir par un algorithme de complexité quadratique en n, l'algorithme de Berlekamp-Massey (en).

Utilisation[modifier | modifier le code]

  • chiffrement par flot en cryptologie
  • division par une puissance de deux (décalage vers la gauche ou la droite)
  • tampons pour la réception de données (FIFO : first in - first out)
  • compteur, temporisateur