Décalage circulaire

Un article de Wikipédia, l'encyclopédie libre.

Un décalage circulaire est une opération sur une liste ordonnée (ou n-uplet), consistant à faire passer le dernier élément au début et à décaler tous les autres ; ou à l'inverse, faire passer le premier élément à la fin, et décaler les autres. Cette opération peut être répétée de manière récursive.

Il s'agit d'un cas particulier de permutation, à distinguer de la permutation circulaire à laquelle il est apparenté.

Par exemple, si l'on prend la liste (a, b, c) — c'est un triplet —, alors ses décalages circulaires successifs sont :

(a, b, c) ;
(c, a, b) ;
(b, c, a).

De manière générale, si l'on a un n-uplet

(a₁, a₂, …, a_n)

alors les décalages circulaires sont obtenues en appliquant l'algorithme récursif suivant :

premier décalage

a ¹₁ = a _n

pour 1 < i < n, a ¹_i+1 = a _i

j ^e décalage (j < n) :

a ^j₁ = a ^j-1_n

pour 1 < i < n, a ^j_i+1 = a ^j-1_i

[modifier] Parité

Un décalage circulaire est

une permutation paire si le nombre d'éléments est impair ;
une permutation impaire si le nombre d'éléments est pair.

Ceci peut se démontrer par récurrence sur le nombre d'éléments :

pour un doublet, le décalage circulaire est une transposition (a, b) → (b, a), c'est donc une permutation impaire ;
pour un n-uplet, le décalage circulaire s'obtient en permutant le premier et le dernier élément, puis en appliquant un décalage circulaire sur les éléments de rang 2 à n dans la nouvelle liste (donc les éléments a₂, a₃, …, a_n-2, a_n-1, a₁)
$(a_1,a_2,...,a_{n-1},a_n) \rightarrow (a_n,[a_2,...,a_{n-1},a_1])$
le décalage circulaire de n éléments est donc le produit d'un transposition avec le décalage circulaire d'ordre n-1, il y a donc un changement de parité entre n-1 et n.

[modifier] Utilisation en informatique

En informatique, le décalage circulaire décale tous les bits de l'opérande considéré. Lorsque l'opérande est un ensemble d'octets représentant un nombre, cet opérateur ne conserve pas le signe du nombre ni la mantisse et l'exposant. Contrairement aux registres à décalage, les places laissées vacantes par le décalage ne sont pas laissées vides mais sont remplies par les bits poussés hors de l'opérande.

Le décalage circulaire est souvent utilisée en cryptographie

Exemple: Si la séquence de bits 0110 1111 1010 0011 est soumise à un décalage circulaire de quatre bits vers la gauche, le résultat est 1111 1010 0011 0110

Notez que le quartet le plus à gauche, 0110, devient le quartet le plus à droite.