Design d’un codeur-décodeur chaotique auto-synchronisant en temps réel et en présence de bruit

DESIGN D’UN CODEUR-DÉCODEUR CHAOTIQUE AUTO-SYNCHRONISANT EN TEMPS RÉEL ET EN PRÉSENCE DE BRUIT

Laboratoire d’Automatique et d’Informatique Industrielle-POITIERS

1

ENSEA, GdR MACS 18/12/2008

Jean-Philippe Mangeot - Frédéric Launay - Sébastien Cauet - Patrick Coirault

Objectifs2

Implantation d’un codeur-décodeur

chaotique auto synchronisant en présence de bruit.

Encodage et Décodage temps réel Débit de 10 MChips/sec

PLAN3

Contexte de transmission Observateur d’état par estimation

ensembliste Quelles sont les ressources disponibles? Optimiser ces ressources : Vers un

algorithme génétique

SOMMAIRE4

Contexte de transmission Observateur d’état par estimation

ensembliste Quelles sont les ressources disponibles? Optimiser ces ressources : Vers un

algorithme génétique

Objectifs5

Implantation d’un codeur-décodeur

chaotique auto synchronisant en présence de bruit.

Encodage et Décodage temps réel Débit de 10 MChips/sec

6

Contexte de transmission

7

Structures AR

Equations d’état du système chaotique

8

Diagramme de bifurcation pour un système AR d’ordre 2, modulo 256

G1 variant de -1 à 4 G2= -1

Structures AR

Sans redondance9

-Bonjour, dit le petit prince.-Bonjour, dit l'aiguilleur.-Que fais-tu ici? dit le petit prince.-Je trie les voyageurs, par paquets de mille, dit l'aiguilleur. J'expédie les trains qui les emportent.

Sans redondance10

-Bonjour, dit le petit prince.-Bonjour, dit l'aiguilleur.-Que fais-tu ici? dit le petit prince.-Je trie les voyageurs, par paquets de mille, dit l'aiguilleur. J'expédie les trains qui les emportent.

onjour, dit le petit prince.-Bonjour, dit l'aiguilleur.-Que fais-tu ici? dit le petit prince.-Je trie les voyageurs, par paquets de mille, dit l'aiguilleur. J'expédie les trains qui les emportent.

Avec redondance (x10)11

-Bonjour, dit le petit prince.-Bonjour, dit l'aiguilleur.-Que fais-tu ici? dit le petit prince.-Je trie les voyageurs, par paquets de mille, dit l'aiguilleur. J'expédie les trains qui les emportent.

Avec redondance (x10)12

-Bonjour, dit le petit prince.-Bonjour, dit l'aiguilleur.-Que fais-tu ici? dit le petit prince.-Je trie les voyageurs, par paquets de mille, dit l'aiguilleur. J'expédie les trains qui les emportent.

-Bonjour, dit le petit prince.-Bonjour, dit l'aiguilleur.-Que fais-tu ici? dit le petit prince.-Je trie les voyageurs, par paquets de mille, dit l'aiguilleur. J'expédie les trains qui les emportent.

13

Contexte de transmission Observateur d’état par estimation

ensembliste Quelles sont les ressources disponibles? Optimiser ces ressources : Vers un

algorithme génétique

SOMMAIRE

• Avec des circuits de Frey:

14

Idée : Retrouver analytiquement l’ensemble des antécédents possible à chaque symbole reçu :

Sn-1

Sn-2

Sn

La fonction est surjective, il existe 256 couples (Sn-1,Sn-2) antécédents possibles pour chaque symbole reçu

11

9797

195

195

0

Observateur d’état par estimation ensembliste

• Avec des circuits de Frey: linéarisation par morceaux

15

S(n-1)=S(n)-2S(n-2)-carry si S(n-1) + 2S(n-2) + carry < 2N -1S(n-1)=S(n)-2S(n-2)-carry si 2N -1< S(n-1) + 2S(n-2) + carry < 2N+1 -1S(n-1)=S(n)-2S(n-2)-carry si S(n-1) + 2S(n-2) + carry > 2N+1 -1

Observateur d’état par estimation ensembliste

• Avec des circuits de Frey: Les premières itérations de l’algorithme ensembliste

16

50

NN-1N-2 N+1

Observateur d’état par estimation ensembliste

• Avec des circuits de Frey: Les premières itérations de l’algorithme génétique.

17

50

NN-1N-2 N+1

105

Observateur d’état par estimation ensembliste

• Avec des circuits de Frey: Les premières itérations de l’algorithme génétique.

18

50

NN-1N-2 N+1

105 84

Observateur d’état par estimation ensembliste

• Avec des circuits de Frey: Les premières itérations de l’algorithme génétique.

19

50

NN-1N-2 N+1

105 84

Estimation ensembliste des conditions initiales

• Avec des circuits de Frey: Les premières itérations de l’algorithme génétique.

Estimation ensembliste des conditions initiales

20

50

NN-1N-2 N+1

105 84 222

• Avec des circuits de Frey: Les premières itérations de l’algorithme génétique.

21

Estimation ensembliste des conditions initiales

• Avec des circuits de Frey: Les premières itérations de l’algorithme génétique.

22

Estimation ensembliste des conditions initiales

• Avec des circuits de Frey: Les premières itérations de l’algorithme génétique.

23

Estimation ensembliste des conditions initiales

24

• Avec des circuits de Frey: Résultats avec un bruit de +-100 LSB

Observateur d’état par estimation ensembliste

25

• Au fur et à mesure, les séquences candidates qui « sortent» sont éliminées

Estimation ensembliste des conditions initiales

26

• Au fur et à mesure, les séquences candidates qui « sortent» sont éliminées

Estimation ensembliste des conditions initiales

Méthode 3: Estimation des conditions initiales

27

• Avec des circuits de Frey: Résultats avec un bruit de +-100 LSB (SNR=2.45dB)

• Pendant les 5 premières itérations, la population de couples à traiter est supérieure à 10.000.

Evolution du cardinal des séquences possibles en fonction du nombre d’itérations

• Avantages:

Pas de restriction sur les conditions initialesPossibilité d’ intégrer plusieurs utilisateursAlgorithmes faciles à implanter pour des applications temps

réel.

• Inconvénients:

Obligation de travailler sur un bruit bornéNombre de ressources s’accroit exponentiellement en fonction

du niveau de bruit.

28

Estimation ensembliste des conditions initiales

PLAN29

Contexte de transmission Observateur d’état par estimation

ensembliste Quelles sont les ressources disponibles? Optimiser ces ressources : Vers un

algorithme génétique

2 principales contraintes pour l’implantation:

• Il faut que l’algorithme respecte les contraintes de temps

• Il faut que l’algorithme respecte les contraintes de place sur le composant

30

Contraintes dues à l’implantation

31

En 1999, Deep-Crack aura mis 22 heures et 15 minutes pour trouver une clés parmi les 2^56 possibles de DESPossibilités testées : 90 milliards de clés par seconde

Source: Cracking DES - Secrets of Encryption Research, Wiretap Politics & Chip Design

Contraintes dues à l’implantation

Structure du Codeur : Structure de Frey

32

Avec G1=1 et G2=2 (Rotation circulaire) on trouve un générateur très compact d’un point de vue électronique

s(k)=mod( s(k-1)+f (s(k-2)+e(k))

33

Contraintes dues à l’implantation: ce qui existe

Chez ALTERA:DSP Development Board for Stratix II

48000 Macro-Cellules

Implantation du codeur34

Implantation du codeur35

Consommation

• 157 ALUTs/48.352 (<1%)

Implantation du décodeur36

• Décalage et réplicas du codeur

• Système de récupération

d’horloge

• Décision temps réel

Implantation du décodeur37

Consommation pour 8 réplicas

Reconstitution horloge: 47 ALUs

8 Réplicas: 8*53= 424 ALUs

Décision Temps réel: 111 ALUs

Autres: 116 ALUs• _____________________________

698 ALUs /48.352 (1.4%)

Implantation du décodeur38

A titre d’information :

Coût d’un filtre de NYQUIST= 5127 cellules ( 100 coefficients représentés sur 16 bits, précision gardée en sortie du MAC de 35 bits) Fe=100Mhz

Coût d’une PLL =de 200 à 2000 cellulesVITERBI= 1000 cellules

Implantation du décodeur39

Ordre de grandeur:

Il faut compter environ 100 cellules par réplica

Ce qui laisse la possibilité d’implanter 256 réplicas en parallèle

Implantation du décodeur40

Synchro

SOMMAIRE41

Contexte de transmission Estimation ensembliste des conditions

initiales Quelles sont les ressources disponibles? Optimiser ces ressources : Vers un

algorithme génétique

42

Principe de l’algorithme génétique: estimer l’état du codeur

Algorithme:

Critère de sélection:

Population de base:

43

Principe de l’algorithme génétique: estimer l’état du codeur

Actualisation de la population:

44

Résultats

45

Conclusion

Implantation d’un codeur décodeur auto synchronisant sur FPGA validée.

•Travaux en cours •Algorithme de tri: Optimiser l’algorithme de sélection (tri) de la population en un coup d’horloge

46

Conclusion

Implantation d’un codeur décodeur auto synchronisant sur FPGA validée.

•Travaux en cours •Algorithme de tri: Optimiser l’algorithme de sélection (tri) de la population en un coup d’horloge

GénérateurChaotique

1

Clé 1

Canal

Générateurs inverses

GénérateurChaotique

2

Clé 2

GénérateurChaotique

N

Clé N

Méthode proposée: Le CSK généralisé47

Message Information

Clé 1

Clé 2

Clé N

Générateurs inverses

Générateurs inverses

Déte

ctions d

e C

oh

ére

nce

Restitution du message

GénérateurChaotique

1

Canal

Générateurs inverses

48

Message Information dans l’état

du générateur

Symbole 1

Symbole 2

Symbole N

Générateurs inverses

Générateurs inverses

Déte

ctions d

e C

oh

ére

nce

Restitution du message

Méthode proposée: Le CSK généralisé