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




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


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


Avec redondance (x10)12



13




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


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

16

50

NN-1N-2 N+1


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

17

50

NN-1N-2 N+1

105



18

50

NN-1N-2 N+1

105 84



19

50

NN-1N-2 N+1

105 84

Estimation ensembliste des conditions initiales



20

50

NN-1N-2 N+1

105 84 222


21



22



23


24

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


25

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


26

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


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


PLAN29




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


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%)


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


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


Synchro

SOMMAIRE41

Contexte de transmission Estimation ensembliste des conditions

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


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


2

Clé 2


N

Clé N

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

Message Information

Clé 1

Clé 2

Clé N



Déte

ctions d

e C

oh

ére

nce

Restitution du message


1

Canal


48

Message Information dans l’état

du générateur

Symbole 1

Symbole 2

Symbole N



Déte

ctions d

e C

oh

ére

nce

Restitution du message

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

Documents

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