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

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

Un registre à décalage à rétroaction linéaire, ou LFSR (acronyme de l'anglais linear feedback shift register), est un dispositif électronique ou logiciel qui produit une suite de bits qui peut être vue comme une suite récurrente linéaire sur le corps fini F2 à 2 éléments (0 et 1). La notion a été généralisée à n'importe quel corps fini.

Réalisé électroniquement, dans le cas particulier d'une suite de 0 et de 1, c'est un registre à décalage avec rétroaction linéaire, ce qui signifie que le bit entrant est le résultat d'un OU exclusif (ou XOR) entre plusieurs bits du registre, cette opération étant également l'addition sur le corps fini F2. Ces dispositifs sont simples, peu coûteux et efficaces.

La suite récurrente produite par un LFSR est nécessairement périodique à partir d'un certain rang. Les LFSR sont utilisés en cryptographie pour engendrer des suites de nombres pseudo-aléatoires. La fonction de rétroaction est alors choisie de façon à obtenir une période la plus grande possible.

L’étendue des applications est très large : chiffrement des communications, contrôle d'erreurs sur la transmission de données, auto-test des composants électroniques…

Schéma de fonctionnement d'un LFSR : le bit de rétroaction est obtenue par XOR sur une sélection des bits du registre.
Appuyer sur la touche "échap" pour faire cesser l'animation.

Fonctionnement[modifier | modifier le code]

Principe[modifier | modifier le code]

Principe de base d'un registre à décalage 8 bits à rétroaction linéaire à base de XOR initialisé avec 01110101.

Un LFSR est un dispositif dérivé du registre à décalage de type SIPO, Serial In - Parallel Out, dans lequel un ou plusieurs « étages » du registre subissent une transformation pour être réinjectés en entrée de celui-ci[1].

Il est dit de longueur « r » lorsqu'il est composé de r éléments appelés « étages » ou « cellules », le contenu de l'ensemble de ces éléments à un moment « t » est l'état du LFSR à ce moment[2]. À chaque top d'horloge le contenu d'un étage est transféré au suivant et le premier est rempli par le résultat d'une fonction linéaire qui prend en compte l'état d'un ou de plusieurs étages[2].

Exemple[modifier | modifier le code]

LFSR à 4 bits[3]
Horloge État du LFSR Sortie
0 0 1 1 0 -
1 1 0 1 1 0
2 0 1 0 1 1
3 0 0 1 0 1
4 0 0 0 1 0
5 1 0 0 0 1
6 1 1 0 0 0
7 0 1 1 0 0

Exemple des états successifs d'un LFSR à 4 bits avec une connexion des premier, second et quatrième étages au niveau de la fonction de retour :

  • à t = 0 l'état initial du LFSR est 0 1 1 0 ;
  • à t = 1 le bit d'entrée vaut 1 (0 \oplus 1 \oplus 0), l'état du LFSR est 1 0 1 1 et le bit de sortie vaut 0 ;
  • à t = 2 le bit d'entrée vaut 0 (1 \oplus 0 \oplus 1), l'état du LFSR est 0 1 0 1 et le bit de sortie vaut 1 ;
  • à t = 6 le bit d'entrée vaut 1 (1 \oplus 0 \oplus 0), l'état du LFSR est 1 1 0 0 et le bit de sortie vaut 0 ;
  • à t = 7 le bit d'entrée vaut 1 (1 \oplus 1 \oplus 0), l'état du LFSR est 0 1 1 0 et le bit de sortie vaut 0.

Au septième top d'horloge l'état du registre est identique à son état initial. On dit que le LFSR est de période 7[3].

Modèles mathématiques[modifier | modifier le code]

Conception[modifier | modifier le code]

Conception d'un LFSR

Un LFSR est défini comme suit sur un corps fini \mathbb{F}_{p^n} ou p est premier et n \ge 1[4] :

  • un entier r qui est sa taille ;
  • un état initial S_{r-1} =(a_{0}, a_{1}, \ldots, a_{r-1}) à éléments sur \mathbb{F}_{p^n} ;
  • une fonction linéaire de retour f() ;
  • on calcule a_{r}=f(a_{0}, a_{1}, \ldots, a_{r-1}) ;
  • on fait entrer a_{r} et fait sortir a_{0} ;
  • on obtient une nouvelle séquence de sortie S_{r} = (a_{1}, a_{2}, \ldots, a_{r}).

Définitions[modifier | modifier le code]

Un LFSR peut être défini comme un triplet {L} = \Bigl(\mathbb{F}_{q}, r, (c_{1}, c_{2}, ... , c_{r})\Bigr), où Fq est le corps fini à q éléments, r est le nombre de cellules du LFSR, les coefficients c1, …, cr sont des éléments de Fq[5].

Suite engendrée
La suite engendrée par ce LFSR est une suite (ai)i ∈ N vérifiant la relation de récurrence
a_{n}=\sum_{i=1}^{i=r} c_{i}a_{n-i}, \ \ i \geq r[5]
ou de façon équivalente
a_{r+n}=\sum_{j=0}^{r-1} c_{r-j}a_{n+j}[1].
Taille
La taille du LFSR est r le nombre de cellules.
Coefficients de connexion
les coefficients c1, …, cr sont appelés les coefficients de connexion du LFSR[5].
Fonction de retour ou de rétroaction
La fonction f définie par
f(x_{1}, x_{2}, ..., x_{r-1}, x_{r}) = c_{1}x_{1} + c_{2}x_{2} + ... + c_{r-1}x_{r-1} + c_{r}x_{r}
est appelée fonction de retour ou de rétroaction du LFSR[2]. Quand q=2, F2 est le corps des booléens et f est une fonction booléenne (linéaire).
Fonction génératrice
La fonction génératrice de la suite engendrée par un LFSR sur le corps Fq est la série formelle de Fq [[X]] définie par[6],[7]
A(X) = \sum_{i=0}^{\infty} a_{i}X^{i}

Représentations polynomiales[modifier | modifier le code]

Polynôme de rétroaction
Soit un LFSR {L} défini par le triplet \Bigl(\mathbb{F}_{p^n}, r, (c_{1}, c_{2}, ... , c_{r})\Bigr). Son polynôme de rétroaction, appelé aussi polynôme caractéristique, est T(X) = 1 + \sum_{i=1}^{r} c_{i}X^{i}[8].
Exemple : Un LFSR {L} = \Bigl(\mathbb{F}_{2}, 7, (1, 0, 1, 1, 0, 0, 1)\Bigr) aura comme polynôme de rétroaction T(X) = 1 + X^1 + X^3 + X^4 + X^7.


Polynôme de connexion
Pour un LFSR défini par le triplet {L} = \Bigl(\mathbb{F}_{p^n}, r, (c_{1}, c_{2}, ... , c_{r})\Bigr), le polynôme de connexion est q(X) = \sum_{i=1}^{r} c_{i}X^{i} - 1 dans \mathbb{F}_{p^n}[[X]][6],[7].
Exemple : Un LFSR {L} = \Bigl(\mathbb{F}_{2}, 7, (1, 0, 1, 1, 0, 0, 1)\Bigr) aura comme polynôme de connexion q(X) = X^7 + X^4 + X^3 + X^1 - 1.

Périodicité[modifier | modifier le code]

Puisque la prochaine valeur d'entrée d'un LFSR dépend uniquement des valeurs de certains étages de celui-ci et que l'état « tout à zéro » ne génère jamais de changement sa séquence est de période maximale q^{r}-1 sur \mathbb{F}_{q}{r} est la taille du registre[9],[10].

Une séquence d'un LFSR sur \mathbb{F}_{q} avec une période q^{r}-1{r} est la taille du registre est appelé une « m-sequence (en) »[3],[9].

Exemple : Un LFSR {L} = \Bigl(\mathbb{F}_{2}, 7, (1, 0, 1, 1, 0, 0, 1)\Bigr) aura une période maximale de 2^{7}-1 = 127.

Algorithme de Berlekamp-Massey[modifier | modifier le code]

Introduit en 1969 par James Massey l'algorithme de Berlekamp-Massey (en) permet d'obtenir le plus petit LFSR possible pour une séquence de sortie choisie[11]. Il suffit de capter {2}{r} bits consécutifs d'une m-séquence de période {2}^{r}-1 pour pouvoir reconstruire la séquence entièrement[12].

Description de l'algorithme[13] :

En entrée : les 2n éléments d'une séquence récurrente de manière linéaire définie sur \mathbb{K} avec n \in \N donnés par la liste (a_{0}, a_{1}, \ldots, a_{2n-1}). Le polynôme minimal est de degré limite n.

En sortie : le polynôme P(x) caractéristique minimal de la séquence.

Début

Variables locales
R, R_{0}, R_{1}, V, V_{0}, V_{1}, Q sont des polynômes de x.
Initialisation
R_{0} := x^{2n}; \quad R_{1} := \sum_{i=0}^{2n-1} a_{i}x^{i}; \quad V_{0} = 0; \quad V_{1} = 1;
Boucle, tant que n \leqslant deg(R1) faire :
Q := quotient de la division de R_{0} par R_{1};
R := reste de la division de R_{0} par R_{1};
V := V_{0} - QV_{1}
V_{0} := V_{1}
V_{1} := V
R_{0} := R_{1}
R_{1} = R
Fin boucle
d := max\Bigl(deg(V_{1}), 1 + deg(R_{1})\Bigr); \quad P := x^{d}V_{1}(1/x);
Retour
P := P/\text{leadcoeff}(P).

Fin

Modes de connexion[modifier | modifier le code]

Le mode le plus naturel pour représenter la connexion entre les différents étages du registre est le mode dit de « Fibonacci ». Il est appelé ainsi car la suite de Fibonacci se représente dans ce mode. En 2002 Andy Klapper et Mark Goresky (en) mettent en place le mode dit de « Galois »[14],[15].

Fibonacci[modifier | modifier le code]

LFSR de Fibonacci à 8 bits
LFSR de Fibonacci à 8 bits

Un registre en mode Fibonacci applique strictement la définition d'un LFSR : les contenus des différents étages sont ajoutés ou non les uns aux autres, le résultat de cette addition est ensuite placé dans l'étage d'entrée du registre et tous les étages subissent un décalage vers la sortie[14],[16].

Galois[modifier | modifier le code]

Exemple d'un LFSR Galois à 8 bits
Exemple d'un LFSR Galois à 8 bits

Dans le mode dit de Galois le contenu de l'étage de sortie est ajouté ou non au contenu des étages du registre puis tous les étages subissent un décalage vers la sortie et le contenu de l'étage sortant est réinjecté dans l'étage d'entrée[17].

Au niveau matériel les LFSRs sont souvent mis en œuvre en utilisant ce mode car celui-ci est plus rapide et présente moins de latence que le mode Fibonacci puisque les étages sont mis à jour simultanément[18],[19].

Applications[modifier | modifier le code]

Les LFSRs existent sous deux formes: matérielle et logicielle, mais c'est surtout la première configuration qui est utilisée car elle est simple à mettre en œuvre (matériel peu onéreux associé à un algorithme de traitement simple)[15].

L'usage de cette technologie peut se retrouver dans les domaines suivants[3] :

Génération de nombres pseudo-aléatoires[modifier | modifier le code]

Il y a eu beaucoup de publications à propos de la génération des nombres pseudo-aléatoires par les registres à décalage et à part quelques études sur les registres à rétroaction non linéaires (en), la majorité des auteurs utilisent la rétroaction linéaires[2].

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

Ce problème se décompose en fait en deux parties :

  • La génération de bits par des procédés physiques, dans le cas d'un ordinateur des mesures liées à l'activité de la machine (températures interne, déplacement de la souris, etc.)
  • L'expansion d'une courte suite aléatoire de bits en une suite éventuellement beaucoup plus grande; Dans ce dernier cas, on parle de suite pseudo-aléatoire.

Chiffrement des données[modifier | modifier le code]

Cryptographie[modifier | modifier le code]

Article détaillé : Cryptographie.
Schéma du A5/1 et ses trois registres à décalage. À chaque tour d'horloge, chaque registre est décalé si la valeur de son bit d'horloge (en orange) est majoritaire parmi celles des trois bits d'horloge (en orange). Le bit de sortie est alors le XOR des bits de sortie des trois registres.

Les générateurs pseudo-aléatoires à base de LFSR sont utilisés dans les chiffrements de flux que l'on retrouve sous le terme anglais cipher stream[21], ils constituent avec les chiffrements par bloc les 2 grandes catégories modernes du chiffrement symétrique de la cryptographie.

Les LFSRs sont les composants de base de nombreux générateurs chiffrants[22].

Les raisons pour lesquels les LFSRs sont utilisés dans un grand nombre de générateurs de flux de sont les suivantes[22] :

  • Les LFSRs sont bien adaptés à une configuration matérielle ;
  • Ils peuvent produire des grandes périodes de séquences binaires ;
  • Les séquences produites ont des bonnes propriétés statistiques ;
  • En raison de leur nature, ils peuvent être facilement analysés en utilisant des modèles mathématiques.


Cependant, l'utilisation des LFSRs dans leur configurations initiales est devenue très vite vulnérable aux attaques mathématiques (démontré par l'algorithme de Berlekamp-Massey).


Un système informatique pour ne pas être vulnérable doit être sécurisé contre les attaques connues et référencées, c'est pourquoi un LFSR ne doit jamais être utilisé par lui-même comme un générateur de flux de clés[23].

Néanmoins, les LFSRs restent encore utilisés en raison de leurs coûts de mise en œuvre très bas[23].


Trois méthodes peuvent être employées pour contourner l'effet des propriétés de linéarité des LFSRs[23] :

  • Associer une fonction non linéaire aux sorties de plusieurs LFSRs ;
  • Utiliser une fonction de filtrage non linéaire basé sur le contenu d'un seul LFSR ;
  • Utiliser plusieurs LFSRs en parallèle ou une horloge externe qui peut provenir d'un autre LFSR[24].


Les propriétés attendues d'un générateur de flux de chiffrement sont[23] :

  • Une grande période ;
  • Grande complexité linéaire ;
  • Bonnes propriétés statistiques.


Exemples d'algorithmes cryptographiques utilisant les LFSRs :

  • Codage/décodage des transmissions des téléphones cellulaires
    A5/1 : chiffrement des communications GSM[note 1], il utilise 3 LFSRs de 19, 22 et 23 bits (64 bits au total) ;
  • Codage du Bluetooth
    E0 : protocole de codage du Bluetooth utilisant quatre LFSR de longueurs 25, 31, 33, et 39 bits (128 bits au total)[25].

Stéganographie[modifier | modifier le code]

Article détaillé : Stéganographie.
génération d'une image stéganographie avec FPGA


La stéganographie est la technique qui permet de cacher de l'information, le plus souvent un texte dans des images, une des méthodes est de remplacer le bit de poids faible de chaque pixel formant l'image par un autre bit d'information[26].

Les séquences pseudo-aléatoires à base de LFSRs sont une des méthodes de cryptage de l'information[26].

Embarqués dans des circuits logiques programmables tels que les FPGA[note 2], ils répondent à un besoin croissant de cacher l'information[27].

Détection d'erreurs et correction de données[modifier | modifier le code]

Plusieurs type de CRC selon les applications[3]
Application Type taille LFSR
CRC CRC-12 12
CRC-16 16
Réseau ATM[note 3] CRC-32 32


Ce mécanisme que l'on appelle contrôle de redondance cyclique et que l'on retrouve sous le nom de CRC[note 4] est un dispositif de contrôle d'erreur lors des transmissions de données brutes dans le domaine du réseau, le stockage numérique ou encore dans la compression de donnée[28].

Les composants hardware LFSR sont un des moyens facile et bon marché pour générer des suite pseudo-aléatoire utilisées par ces procédés[28].

Auto-contrôle des circuits électronique[modifier | modifier le code]

Le test des circuits électroniques a été longtemps problématique car les solutions existantes donnant des temps de réponses corrects étaient souvent très onéreuses. Le coût n'est pas le seul problème, il faut aussi que le dispositif puisse répondre à 2 problématiques[29] :

  • Le temps : Il ne faut pas que le mécanisme consomme trop de temps à générer l'échantillonnage de test au détriment de l'efficacité du composant ;
  • Le volume de donnée : La taille de échantillonnage peut devenir tellement grande que le test n'est plus efficace.

La technologie BIST[note 5] est une méthode de test des composants électroniques qui s'appuie sur plusieurs mécanismes[30] :

  • Technique de parité ;
  • Technique de comptage ;
  • LFSRs.

Les tests aléatoires sur une partie du composant suppose de pouvoir agir sur un échantillonnage des données du composant[31].

Traitement numérique du signal[modifier | modifier le code]

C'est l’étude du traitement du signal numérisé tel que le filtrage ou la compression, elle est assurée par un processeur de signal numérique que l'on retrouve indiqué dans ce domaine par DSP[note 6]. Ces opérations seraient difficilement réalisables directement sur les données binaires en mémoire sans algorithme de compression/décompression.

Les LFSRs sont fréquemment utilisés pour cette tache car ils sont efficaces dans le traitement de grande quantité de données binaires et ils ont un faible cout d’implémentation dans leurs formes matériels [32].

Compteurs à base de LFSRs[modifier | modifier le code]

Les Compteurs binaires (en) sont des composants qui sont utilisés couramment dans des équipements nécessitant un comptage comme, par exemple, les montres digitales ou les chronomètres.

Un LFSR est un type spécial de compteur qui génère une séquence pseudo-aléatoire, il peut être utilisé en remplacement des compteurs binaires traditionnels[33].

Exemples d'utilisation[34]:

  • Compteurs à incrément ou décrément 'up/down counters' ;
    • Down counters - commence à w/ 111 ;
    • Utilise une porte 'XOR' pour la retroaction ;
    • L'initialisation ne doit pas être que des zéros.
  • 'Up counters' commence à w/ 000.

Utilisation du XNOR

Avantages[35] Inconvénients[35]
Nécessite peu de logique pour être mis en place ;
  • Les compteurs avec des grandes valeurs restent efficaces ;
    • Pas de besoin d'un nombre élevé de portes logiques ;
    • Ils sont très rapides.
  • Les erreurs sont détectables typiquement un timer 2*n.
  • Besoin d'initialiser le registre pour avoir un état valide ;
  • Certaines applications ont besoin d'une séquence binaire ;
  • Pas de moyen simple de prédire la séquence de comptage.

Autres utilisations des LFSRs[modifier | modifier le code]

L'industrie du jeu vidéo a utilisé le LFSR au travers d'un composant qui est le SN76489, on a pu ainsi sonoriser certaines consoles de jeux vidéo grâce à ce circuit électronique[36].

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. GSM pour Global System for Mobile Communications, historiquement Groupe Spécial Mobile
  2. FPGA pour Field-Programmable Gate Array
  3. ATM pour Asynchronous Transfer Mode
  4. CRC pour Cyclic Redundancy Check
  5. BIST pour Built-In Self-Test
  6. DSP pour Digital Signal Processor

Références[modifier | modifier le code]

  1. a et b Klein 2013, p. 17
  2. a, b, c et d Cagigal 1986, p. 191
  3. a, b, c, d et e Ahmad 2003, p. 2
  4. Marjane 2011, p. 80-81
  5. a, b et c Marjane 2011, p. 81
  6. a et b Klein 2013, p. 19
  7. a et b Marjane 2011, p. 83
  8. Ahmad 2003, p. 3
  9. a et b Klein 2013, p. 18
  10. Moon 2005, p. 154
  11. Reeds 1985, p. 505
  12. Marjane 2011, p. 14
  13. Ben Atti 2006, p. 76
  14. a et b Marjane 2011, p. 22
  15. a et b Lauradoux 2007, p. 2
  16. Goresky 2002, p. 2827
  17. Goresky 2002, p. 2828
  18. Joux 2006, p. 437
  19. Marjane 2011, p. 152
  20. Bresson 2011, p. 11
  21. Menezes 1996, p. 191
  22. a et b Menezes 1996, p. 195
  23. a, b, c et d Menezes 1996, p. 204
  24. Chambers 1988, p. 17
  25. Klein 2013, p. 126.
  26. a et b Gamil 2002, p. 239
  27. Sundararaman 2011, p. 24
  28. a et b PATEL 1971, p. 11
  29. McCluskey 1985, p. 21
  30. McCluskey 1985, p. 25
  31. Breuer 1988, p. 933
  32. Lauradoux 2007, p. 1
  33. Ajane 2011, p. 1
  34. Chen 2010, p. 3
  35. a et b Chen 2010, p. 8
  36. [[#A53|]], p. 1

Bibliographie[modifier | modifier le code]

Manuels et cours[modifier | modifier le code]

Articles de recherche[modifier | modifier le code]

  • (en) W. Liang et Jing Long, « A cryptographic algorithm based on Linear Feedback Shift Register », Computer Application and System Modeling (ICCASM), 2010 International Conference on,‎ 22-24 octobre 2010 (DOI 10.1109/ICCASM.2010.5622523) Document utilisé pour la rédaction de l’article
  • (en) Bernard Elspas, « The Theory of Autonomous Linear Sequential Networks », Circuit Theory, IRE Transactions on,‎ mars 1959, p. 45-60 (ISSN 0096-2007, DOI 10.1109/TCT.1959.1086506) Document utilisé pour la rédaction de l’article
  • (en) N.P. Cagigal et S. Bracho, « Algorithmic determination of linear-feedback in a shift register for pseudorandom binary sequence generation », Electronic Circuits and Systems, IEE Proceedings G,‎ août 1986, p. 191-194 (ISSN 0143-7089, DOI 10.1049/ip-g-1:19860031) Document utilisé pour la rédaction de l’article
  • (en) Lauradoux, « From Hardware to Software Synthesis of Linear Feedback Shift Registers », Parallel and Distributed Processing Symposium, 2007. IPDPS 2007. IEEE International,‎ 26-30 mars 2007, p. 1-8 (DOI 10.1109/IPDPS.2007.370643) Document utilisé pour la rédaction de l’article
  • (en) M. Scaffardi, G. Berrettin et A.T Nguyen, « Optical linear feedback shift register », Lasers and Electro-Optics Europe (CLEO EUROPE/EQEC), 2011 Conference on and 12th European Quantum Electronics Conference,‎ 22-26 mai 2011, p. 1 (ISSN 978-1-4577-0533-5, DOI 10.1109/CLEOE.2011.5942992)
  • (en) « A multiple seed linear feedback shift register », Computers, IEEE Transactions on,‎ février 1992, p. 250-252 (ISSN 0018-9340, DOI 10.1109/12.123404)
  • (en) « Linear feedback shift register design using cyclic codes », Computers, IEEE Transactions on,‎ octobre 1988, p. 1302-1306 (ISSN 0018-9340, DOI 10.1109/12.5994)
  • (en) « Deterministic built-in self-test using multiple linear feedback shift registers for test power and test volume reduction », Computers & Digital Techniques, IET,‎ juillet 2010, p. 317-324 (ISSN 1751-8601, DOI 10.1049/iet-cdt.2009.0092)
  • (en) « Analysis of the Berlekamp-Massey Linear Feedback Shift-Register Synthesis Algorithm », IBM Journal of Research and Development,‎ mai 1976, p. 204-212 (ISSN 0018-8646, DOI 10.1147/rd.203.0204)
  • (en) D.G. Maritsas, A.C. Arvillias et A.C. Bounas, « Phase-Shift Analysis of Linear Feedback Shift Register Structures Generating Pseudorandom Sequences », Computers, IEEE Transactions on,‎ juillet 1978, p. 660-669 (ISSN 0018-9340, DOI 10.1109/TC.1978.1675166)
  • (en) Arvind M Patel, « A multi-channel CRC register », AFIPS '71 (Spring) Proceedings of the May 18-20, 1971, spring joint computer conference,‎ 18 mai 1971, p. 11-14 (DOI 10.1145/1478786.1478789)
  • (en) J. Lawrence Carter, « The theory of signature testing for VLSI », STOC '82 Proceedings of the fourteenth annual ACM symposium on Theory of computing,‎ 5 mai 1982, p. 66-76 (DOI 10.1145/800070.802178)
  • (en) W.B. Jone et C.A. Papachristou, « A coordinated approach to partitioning and test pattern generation for pseudoexhaustive testing », DAC '89 Proceedings of the 26th ACM/IEEE Design Automation Conference,‎ juin 1989, p. 525-534 (DOI 10.1145/74382.74470)
  • (en) Salvatore Filippone, Paolo Santangelo et Marcello Vitaletti, « A vectorized long-period shift-register random number generator », Supercomputing '90: Proceedings of the 1990 ACM/IEEE conference on Supercomputing,‎ octobre 1990, p. 676-684
  • (en) Li-Ren Huang, Sy-Yen Kuo et Ing-Yi Chen, « A Gauss-elimination based PRPG for combinational circuits », EDTC '95 Proceedings of the 1995 European conference on Design and Test,‎ 6 mars 1995, p. 212
  • (en) Laurence Goodby et Alex Orailoğlu, « Pseudorandom-pattern test resistance in high-performance DSP datapaths », DAC '96 Proceedings of the 33rd annual Design Automation,‎ juin 1996, p. 813-818 (DOI 10.1145/240518.240671)
  • (en) D.V. Sarwate, « Mean-square correlation of shift-register sequences », Communications, Radar and Signal Processing, IEE Proceedings F,‎ avril 1984, p. 101-106 (ISSN 0143-7070, DOI 10.1049/ip-f-1:19840018)
  • (en) Ahmad Zawawi, Bin Seman Kamaruzzaman et Nurzi Juana Mohd Zaizi, « Randomness analysis on grain - 128 stream cipher », International Conference on Mathematical Sciences and Statistics 2013,‎ 5-7 février 2013 (DOI 10.1063/1.4823866)
  • (en) A. Ahmad, Sameer Al-Busaidi et Ahmed Al-Naamany, Measurement techniques of lfsr sequences,‎ mars 2003 Ouvrage utilisé pour la rédaction de l'article
  • (en) M. Goresky et A.M. Klapper, « Fibonacci and Galois representations of feedback-with-carry shift registers », Information Theory, IEEE Transactions on,‎ novembre 2002, p. 2826-2836 (ISSN 0018-9448, DOI 10.1109/TIT.2002.804048) Document utilisé pour la rédaction de l’article
  • (en) Andreas Klein, Linear Feedback Shift Registers,‎ 20 avril 2013 (DOI 10.1007/978-1-4471-5079-4), p. 17-58 Document utilisé pour la rédaction de l’article
  • (en) J.L. Massey, « Shift-Register Syntheses and BCH Decoding », Information Theory, IEEE Transactions on,‎ janvier 1969, p. 122-127 (ISSN 0018-9448, DOI 10.1109/TIT.1969.1054260)
  • Anne Canteaut, « Attaques de cryptosystèmes à mots de poids faible et construction de fonctions t-résilientes », {{Article}} : paramètre « périodique » manquant,‎ 10 octobre 1996, p. 147-167 (lire en ligne)
  • (en) P.H. Bardell et W.H. McAnney, « Pseudorandom Arrays for Built-In Tests », Computers, IEEE Transactions on,‎ juillet 1986, p. 653-658 (ISSN 0018-9340, DOI 10.1109/TC.1986.1676810)
  • (en) Dai Zongduo et Wan Zhexian, « A relationship between the Berlekamp-Massey and the euclidean algorithms for linear feedback shift register synthesis », Acta Mathematica Sinica,‎ 1er mars 1988, p. 55-63 (ISSN 1439-8516, DOI 10.1007/BF02560313)
  • (en) Nadia Ben Atti, Gema M. Diaz–Toca et Henri Lombardi, « The Berlekamp-Massey Algorithm revisited », Applicable Algebra in Engineering, Communication and Computing,‎ avril 2006, p. 75-82 (ISSN 0938-1279, DOI 10.1007/s00200-005-0190-z) Document utilisé pour la rédaction de l’article
  • (en) S.B. Gashkov et I.B. Gashkov, « Berlekamp—Massey Algorithm, Continued Fractions, Pade Approximations, and Orthogonal Polynomials », Mathematical Notes,‎ 2006, p. 41-54 (ISSN 0001-4346, DOI 10.1007/s11006-006-0004-z)
  • (en) Antoine Joux et Pascal Delaunay, « Galois LFSR, Embedded Devices and Side Channel Weaknesses », Progress in Cryptology - INDOCRYPT 2006,‎ 2006, p. 436-451 (ISSN 0302-9743, DOI 10.1007/11941378_31) Document utilisé pour la rédaction de l’article
  • Abdelaziz Marjane, Conception Vectorielle de Registre à rétroaction avec retenue sur les corps finis,‎ 8 juillet 2011 (lire en ligne) Ouvrage utilisé pour la rédaction de l'article
  • (en) J.A. Reeds et J.A. Sloane, « Shift Register Synthesis (Modulo m) », SIAM Journal on Computing,‎ août 1985, p. 505-513 (ISSN 00975397, DOI 10.1137/0214038) Document utilisé pour la rédaction de l’article
  • (en) T.N. Rajashekhara, « Signature analyzers in built-in self-test circuits: a perspective », Southern Tier Technical Conference,‎ 25 avril 1990, p. 275-281 (DOI 10.1109/STIER.1990.324654)
  • (en) M. Koutsoupia, E. Kalligeros et X. Kavousianos, « LFSR-based test-data compression with self-stoppable seeds », Design, Automation & Test in Europe Conference & Exhibition,‎ 20-24 avril 2009, p. 1482-1487 (ISSN 1530-1591, DOI 10.1109/DATE.2009.5090897)
  • (en) A. Ajane, P.M. Furth et E.E. Johnson, « Comparison of binary and LFSR counters and efficient LFSR decoding algorithm », Circuits and Systems (MWSCAS), 2011 IEEE 54th International Midwest Symposium on,‎ 07/10/2013 août 2011, p. 1548-3746 (ISSN 1548-3746, DOI 10.1109/MWSCAS.2011.6026392) Document utilisé pour la rédaction de l’article
  • (en) H Rizk, C Papachristou et F Wolff, « Designing self test programs for embedded DSP cores », Design, Automation and Test in Europe Conference and Exhibition, 2004. Proceedings,‎ 16-20 février 2004, p. 816 - 821 (ISSN 1530-1591, DOI 10.1109/DATE.2004.1268982)
  • (en) T. Jamil et A. Ahmad, « An investigation into the application of linear feedback shift registers for steganography », SoutheastCon, 2002. Proceedings IEEE,‎ 5 juin 2002, p. 239-244 (DOI 10.1109/.2002.995594)
  • (en) T Siegenthaler, « Decrypting a Class of Stream Ciphers Using Ciphertext Only », Computers, IEEE Transactions on,‎ janvier 1985, p. 81 - 85 (ISSN 0018-9340, DOI 10.1109/TC.1985.1676518)
  • (en) J. E. Meggitt, « Error correcting codes and their implementation for data transmission systems », Information Theory, IRE Transactions on,‎ octobre 1961, p. 234-244 (ISSN 0096-1000, DOI 10.1109/TIT.1961.1057659)
  • (en) R. David, « Testing by Feedback Shift Register », Computers, IEEE Transactions on,‎ juillet 1980, p. 668-673 (ISSN 0018-9340, DOI 10.1109/TC.1980.1675641)
  • (en) W. Daehn et J. Mucha, « A hardware approach to self-testing of large programmable logic arrays », Circuits and Systems, IEEE Transactions on,‎ novembre 1981, p. 1033-1037 (ISSN 0098-4094, DOI 10.1109/TCS.1981.1084933)
  • (en) S. Pupolin et Carlo Tomasi, « Moments of the Weights of Pseudo-Noise Subsequences », Military Communications Conference - Progress in Spread Spectrum Communications, 1982. MILCOM 1982. IEEE,‎ 17-20 octobre 1982, p. 15.3-1-15.3-4 (DOI 10.1109/MILCOM.1982.4805920)
  • (en) T. Siegenthaler, « Decrypting a Class of Stream Ciphers Using Ciphertext Only », Computers, IEEE Transactions on,‎ janvier 1985, p. 81-85 (ISSN 0018-9340, DOI 10.1109/TC.1985.1676518)
  • (en) E.J. McCluskey, « Built-In Self-Test Techniques », Design & Test of Computers, IEEE,‎ avril 1985, p. 21-28 (ISSN 0740-7475, DOI 10.1109/MDT.1985.294856)
  • (en) W.G. Chambers, « Clock-controlled shift registers in binary sequence generators », Computers and Digital Techniques, IEE Proceedings E,‎ janvier 1988, p. 17-24 (ISSN 0143-7062)
  • (en) S. Sastry et M. Breuer, « Detectability of CMOS stuck-open faults using random and pseudorandom test sequences », Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on,‎ septembre 1988, p. 933-946 (ISSN 0278-0070, DOI 10.1109/43.7792)
  • (en) A. Ahmad, N. Nanda et K. Garg, « The use of irreducible characteristic polynomials in an LFSR based testing of digital circuits », TENCON '89. Fourth IEEE Region 10 International Conference,‎ 22-24 novembre 1989, p. 494-496 (DOI 10.1109/TENCON.1989.176866)
  • (en) An Implementation Of The Noise Shift Register (lire en ligne) Ouvrage utilisé pour la rédaction de l'article
  • (en) R. Sundararaman, Stego System on chip with LFSR based Information Hidin Approach,‎ mars 2011, 24-31 p. (lire en ligne) Ouvrage utilisé pour la rédaction de l'article

Document utilisé pour la rédaction de l’article : document utilisé comme source pour la rédaction de cet article.

Voir aussi[modifier | modifier le code]

Liens externes[modifier | modifier le code]