[Diffusion de la culture scientifique]
Axes de Recherche de l'équipe |
Analyse de trains binaires en contexte non-coopératif
pour les communications numériques
Responsable : Roland
Gautier (MC),
Intervenants permanents : Gilles
Burel (PR), Stéphane
Azou (MC), Koffi-Clément
Yao (MC),
Intervenants non permanents : Mélanie
Marazin (Doctorante)
I. Contexte
Les systèmes de transmissions pour les communications
numériques sont en constante expansion et leur utilisation s'est
généralisée dans l'ensemble des domaines d'applications
de la vie courante, que ce soit dans le domaine privé ou professionnel.
Ils sont présents dans les communications radio-mobiles (i.e
Cellulaires), dans les réseaux locaux (ou métropolitains)
sans fils, dans les applications en acoustique sous-marine, satellitaires,
spatiales et beaucoup d'autres encore. Nous assistons donc également
de fait à une prolifération des standards ou normes de
transmission, ce qui entraîne de gros problèmes de compatibilité
et un manque de souplesse du point de vue de l'utilisateur. Il devient
donc nécessaire de concevoir des systèmes (terminaux)
adaptatifs et auto-configurants. De plus, cette prolifération
de standards et applications faisant appel à des systèmes
de communications numériques soulève également
des problèmes de sécurité de ces applications et
il est également nécessaire de mettre au point des récepteurs
capables de mettre à l'épreuve les systèmes de
transmissions pour les communications numériques actuels au niveau
de l'identification des paramètres de la transmission sans connaissance
a priori sur ceux effectivement utilisés par l'émetteur.
Au sein du laboratoire, l'équipe « Traitement du Signal
pour les Télécommunications » (TST) s'intéresse
particulièrement depuis quelques années à la détection
et l'analyse de transmissions. En particulier, nous avons commencé
à nous pencher sur l'analyse de trains binaires obtenus après
démodulation de signaux interceptés issus de transmissions
pour les communications numériques. Cet axe de recherche a été
initié à l'origine par un intérêt scientifique,
car l'étude des caractéristiques à partir d'un
train binaire d'une transmission pour les communications numériques
est très difficile puisque tout doit se faire en aveugle sans
connaissance a priori de ce que l'on doit trouver et donc très
stimulant pour un chercheur. Cependant, les applications possibles de
telles techniques de détection et de reconnaissance en aveugle
sont nombreuses, que ce soit dans le domaine militaire, que dans le
domaine civil pour la surveillance du spectre radiofréquences,
la sécurité des transmissions ou les systèmes auto-configurants.
L'équipe TST possède un savoir faire dans le domaine de
la détection et de l'analyse des différents blocs composant
un chaîne de transmission numérique en contexte non-coopératif.
Après détection de la présence de signaux de télécommunication
au sens large du terme, même lorsque ceux-ci sont cachés
sous le niveau du bruit ou sous une autre transmission (cf Sous thème
- Détection/analyse de transmissions à spectre étalé
: Application aux techniques d'accès multiples CDMA), il est
alors nécessaire de déterminer l'ensemble des paramètres
de ces signaux afin de récupérer au final l'information
utile.
Cependant de nos jours les chaînes de transmissions numériques
font appel à des techniques de codage de source et de codage
canal de plus en plus performantes destinées à améliorer
le débit, à combattre les erreurs de transmission et également
à diminuer la probabilité de retrouver l'information en
cas d'interception par un tiers. Ces techniques sont, par exemple, la
compression ou la cryptographie au niveau du codage de source et l'entrelacement,
l'embrouillage (« scrambling ») ou différent types
de codage (codes en bloc, code convolutifs, code de Reed-Solomon, turbocodes,
etc …) au niveau codage canal. Il devient alors très difficile
d'identifier ces paramètres en aveugle, comme par exemple dans
le cas des turbocodeurs, qui sont reconnus comme très performants
par leur capacité de correction lors du décodage en réception.
Pour ces raisons, l'équipe TST du LEST développe des nouvelles
méthodes basées sur l'analyse du train binaire en réception,
permettant l'identification des paramètres de ces compresseurs,
entrelaceurs, embrouilleurs et codeurs, destinées à la
mise en oeuvre de récepteurs adaptatifs et auto-configurants
suivant le standard de transmission utilisé, mais également
à la surveillance du spectre radiofréquence pour éviter
toute utilisation illicite, l'interception et l'écoute des télécommunications
ou la surveillance des communications acoustiques sous-marines.
II. Résumé des travaux
Le cadre d'étude de ce sous-thème intitulé
« Analyse de trains binaires en contexte non-coopératif
pour les communications numériques », fait partie du thème
principal « Interception des communications numériques
et des signaux radars. Cette sous-thèmatique porte sur l'identification
des paramètres des différents blocs de codage au sens
large du terme qui peuvent être divisés en deux catégories
distinctes et qui sont par ordre d'apparition au niveau du récepteur
:
- Le « Codage Canal » ;
- Le « Codage de Source ».
Ces deux groupes de blocs de traitement ont des rôles bien distincts
au niveau de la chaîne standard de transmission (i.e en contexte
coopératif) :
- Le « Codage Canal » ayant pour but de
rajouter de la redondance, de disperser temporellement les éléments
d'un même mot de code afin d'augmenter les performances de correction
du code associé, de rendre difficilement accessible les données
d'un utilisateur particulier par embrouillage de celles-ci, tout cela
afin de pallier les erreurs engendrées par le canal de transmission
et les éventuels brouilleurs potentiels.
N.B : Nous ne parlerons pas ici des blocs de « mapping »
permettant de convertir le train binaire par regroupement d'éléments
binaires en symboles d'une constellation numérique associée
(exemples : BPSK, MAQ 4, 16 …,PSK8) dont la détection
et l'identification font également l'objet de travaux au sein
de l'équipe ou du bloc étalement de spectre qui est traité
de manière spécifique au sein du sous-thème Détection/analyse
de transmissions à spectre étalé : Application
aux techniques d'accès multiples de type CDMA.
- Le « Codage de Source » ayant
pour but, d'une part d'éliminer au maximum les redondances présentes
dans les données binaires informatives afin de diminuer au maximum
la quantité de données à transmettre et du même
coup augmenter le débit de la transmission, d'autre part de protéger
l'information contre toute tentative de récupération de
l'information par une personne non autorisée.
L'équipe TST a donc été amenée à
développer des méthodes et algorithmes permettant d'identifier
les différents paramètres de chacun des blocs de ces deux
catégories, ceci principalement dans le cadre de contrats avec
des organismes militaires et des grandes entreprises travaillant dans
le domaine.
Nous allons maintenant faire un petit résumé des différents
travaux déjà effectués dans les domaine en commençant
par les blocs de Codage Canal, puis en abordant la partie codage de
Source.
II.1 Détection
et identification des blocs « Codage Canal »
Les différents blocs « Codage Canal » que nous avons
jusqu'à présent traités sont :
- Embrouillage ou « scrambling » ;
- Codage ;
- Entrelacement.
La première étude que nous avons entreprise a porté
sur l'identification de l'état initial d'un embrouilleur décrite
ci-dessous.
II.1.1 Etudes sur l'identification de l'état initial d'un embrouilleur
Le bloc embrouilleur ou « scrambler » consiste à
multiplier élément par éléments les données
binaires par une séquence pseudo aléatoire donnée
de très grande taille afin de brouiller le train binaire initiale
et rendre plus difficile l'interception du signal. Dans le cas de la
norme GSM, c'est ce bloc d'embrouillage qui sert à différencier
les différents utilisateurs par utilisation d'un décalage
(« offset ») de la séquence de brouillage propre
à chaque utilisateur et présent dans la carte SIM du téléphone
et dans la base de donnée de l'opérateur. Tous les téléphones
ont à l'intérieur un générateur de séquence
d'embrouillage identique synchronisé par rapport aux horloges
atomique des satellites de télécommunications et/ou GPS,
permettant ainsi de générer une séquence de très
longue durée (40 jours ~). La seule différence entre les
différents utilisateurs réside dans l'initialisation à
un instant donné de la position temporelle à l'intérieur
de la séquence globale du générateur de séquence
d'embrouillage d'un utilisateur particulier. Cette position temporelle
particulière à l'intérieur de la séquence
d'embrouillage est donnée, d'une part pour tous les utilisateurs
par le temps courant et d'autre part par le décalage particulier
affecté à un utilisateur donné. Le processus d'embrouillage
permet d'assurer un degré de sécurité raisonnable
au niveau du caractère privé des données et également
de générer un train binaire le plus aléatoire possible
avec de bonnes propriétés spectrales.
Précision importante
: Il ne faut surtout pas confondre
le bloc d'embrouillage avec celui d'étalement de spectre. D'une
part, l'opération d'étalement de spectre modifie le débit
puisque le train de symboles informatif est multiplié par une
séquence pseudo aléatoire de fréquence L fois supérieure
à celle du train de symboles initial, avec L la longueur de la
séquence d'étalement. Dans le cas de l'embrouillage la
fréquence de la séquence d'embrouillage est identique
à celle du train informatif. D'autre part, ce qui prête
souvent à confusion, c'est le fait que le bloc d'étalement
de spectre est généralement utilisé comme technique
d'accès multiple de type CDMA et que dans ce cas il est dit que
l'utilisation de séquences différentes permet de différencier
les signaux de plusieurs utilisateurs. En vérité, la technique
CDMA permet de différentier les canaux physiques de données
où effectivement certains peuvent contenir les données
de différents utilisateurs à l'intérieur d'une
cellule donnée, mais peuvent également différencier
des canaux de type différents pour un même utilisateur
(canal trafic, canal paging, canal d'accès …). Cependant,
même si le CDMA permet de séparer les signaux de différents
utilisateurs de façon générique, le bloc d'embrouillage
permet lui d'identifier « physiquement » de manière
unique l'utilisateur qui transmet. Pour simplifier nous pouvons donner
l'exemple suivant : le CDMA (bloc d'étalement de spectre) permet
de dire voici le signal d'un utilisateur que l'on peut noter n°1
et celui d'un autre utilisateur que l'on peut noter n°2. L'embrouillage
permet de dire, le signale n°1 est celui de Mr Michel Duran et le
signal n°2 est celui de Mr Charles Dupont.
Le but de notre étude a été de développer
une méthode permettant d'identifier le décalage («
offset ») à l'origine de la séquence de brouillage
pour un utilisateur donné.
Résumé de la méthode développée pour
l'identification de l'état initial d'un embrouilleur en
contexte non-coopératif :
Comme le montre la Figure 1, dans de nombreux systèmes de transmissions
numériques les données binaires sont tout d'abord encodées
pour les protéger des erreurs liées au canal de transmission
(en utilisant, par exemple, un code en bloc ou un code convolutif).
Ensuite, le flux binaire est embrouillé en effectuant un OU exclusif
(XOR) avec une séquence speudo-aléatoire longue. Les données
binaires embrouillées sont finalement envoyées au bloc
numérique d'émission chargé d'effectuer la mise
sur porteuse, le filtrage et l'amplification.
Figure 1 : Schéma général des blocs codeur + embrouilleur au niveau de l'émetteur
Du coté du récepteur, le signal reçu est démodulé
afin de retrouver le train binaire embrouillé. Puis, les données
sont désembrouillées et décodées.
Le récepteur classique est capable d'effectuer le désembrouillage
car il connaît la séquence d'embrouillage et le décalage
temporel initial de celle-ci pour l'utilisateur en question. Nous avons
donc proposé une méthode permettant en contexte non-coopératif,
d'identifier ce décalage.
Hypothèses de travail :
- Le polynôme générateur de la
séquence d'embrouillage est supposé connu : i.e donné
dans la norme.
- La structure du codeur et ses paramètres
sont connus : i.e donné dans la norme.
Méthode proposée :
Le principe de la méthode est d'utiliser la redondance introduite
par le codeur et peut être décomposée de la manière
suivante :
1- Projection des données observées
sur le sous-espace orthogonal engendré par le codeur ;
2- Estimation du décalage de la séquence
par résolution d'un système d'équations linéaires
;
3- Récupération du train binaire informatif.
Modèle mathématique de l'embrouillage :
Figure 2 : Schéma de principe pour la modélisation mathématique de l'embrouillage
Les données binaires embrouillées sont décrites
par l'équation suivante :
Description mathématique de la méthode :
- Calcul du sous-espace orthogonal 
dans GF(2) tel que : 
;
- Projection du train binaire de données sur
: 
;
l'intérêt étant que les données encodées
n'ont aucune influence sur 
;
- Obtention d'un système linéaire :
;
- Finalement nous obtenons : 
; ce qui nous permet d'effectuer un désembrouillage classique,
ainsi que le décodage pour retrouver le train binaire informatif
initial.
La Figure 3 montre les différentes étapes de la méthode
mathématique sous une graphique de représentation de matrices
et vecteurs, avec tous les calculs effectués dans GF(2).
Figure 3 : Représentation sous forme graphique du processus d'embrouillage à partir d'un exemple
Des simulations ont été effectuées pour illustrer
et valider la méthode sur des exemples où les différents
paramètres ont été pris dans des normes de télécommunications
comme l'IS95, la norme WLAN 802.11a. Les résultats ont été
concluants et ont montrés la pertinence de notre approche. Cette
étude a fait l'objet d'un stage de DEA et également d'une
publication dans une conférence internationale.
II.1.2 Etudes sur la détection et l'identification de codeurs
et entrelaceurs
Les blocs codage et entrelacement font partie des préoccupations
majeures de l'équipe, car ils sont présents dans tous
les standards et normes pour les communications numériques. De
plus, ils sont également de part leurs performances accrues en
termes de corrections des erreurs de transmissions et leur complexité
un challenge permanent au niveau de leur détection et identification
en aveugle en contexte non-coopératif.
La plupart des études et résultats actuels dans ce domaine
sont étroitement liés à des contrats, permettant
à l'équipe de financer les études plus académiques
de l'équipe. Cependant les difficultés inhérentes
au problème de l'identification de ces codeurs et entrelaceurs
sont d'un point théorique une source de questions permanentes
en termes de recherche de nouveaux algorithmes et mises en oeuvre d'outils
mathématiques existants dans un contexte totalement différent
de leurs utilisations traditionnelle.
Ces études ont un lien direct avec la cryptanalyse et repose
sur des fondements mathématiques complexes, ainsi que sur des
propriétés liées à la conception même
des chaînes de traitement pour les communications numériques,
qui ne sont en général pas ou peu exploitées en
contexte coopératif. Dans le contexte non-coopératif,
toutes les bonnes propriétés imposées aux codeurs
pour que la réception se passe sans problème dans le cas
classique coopératif et que la correction des erreurs puisse
être efficace ont des implications fortes sur la faisabilité
d'une identification en aveugle.
Il est possible de séparer les axes abordés dans ces études
sur les codeurs et les entrelaceurs en deux :
- Un premier axe consiste en l'étude du bloc
codage seul avec tous les types de codeurs envisageable et le développement
d'algorithme d'identification de ces codeurs.
- Un deuxième axe consiste en l'étude
conjointe des blocs codeur et entrelaceur, sachant que l'étude
du bloc entrelaceur sans faire l'hypothèse de la présence
d'un codeur en amont à l'émission est irréaliste
d'un point de vue purement théorique.
Rôle d'un codeur :
Le but d'un codeur est de permettre en réception la correction
des erreurs liées au canal de transmission par introduction de
redondance dans le train binaire au niveau de l'émetteur.
Les performances en termes de correction dépendent :
- Du type de codeur :
o Codes en blocs ;
o Codes convolutifs ;
o Code Reed-Solomon ;
o Turbocodes ;
o Codes LDPC, etc ….
- Des paramètres du codeur à l'intérieur
d'une classe donnée :
o Taille des mots d'information en entrée du
codeur ;
o Taille des mots de code en sortie du codeur ;
o Distance minimale ;
o Distance libre ;
Rôle d'un entrelaceur :
Le but d'un entrelaceur est de disperser temporellement les éléments
binaires appartenant à un mot de code particulier, afin de permettre
en réception de faciliter la tâche du décodeur lorsque
le canal de transmission génère des erreurs par paquets
(« Burst errors »). L'opération d'entrelacement correspond
d'un point de vue mathématique à un ensemble de permutations
des éléments binaires à l'intérieur du flux
de données et l'introduction de retards. La plupart des codes
correcteurs d'erreurs permettent de corriger un nombre limité
de bits ou symboles sur un mot de code et en plus à condition
que c'est erreurs soient uniformément réparties dans le
temps. Malheureusement, certains types de canaux engendrent des séquences
d'erreurs consécutives et dépassent le pouvoir de correction
du code utilisé. Pour cette raison, l'adjonction d'un entrelaceur
à l'emission, permet en réception après désentrelacement
de re-disperser les erreurs et donc de réduire de manière
conséquente les erreurs à l'intérieur d'un même
mot de code.
Les performances en termes de correction et la facilité de mise
en oeuvre dépendent :
- Du type d'entrelaceur :
o Entrelaceurs par blocs ;
o Entrelaceurs multiplexés ou convolutifs.
- Des paramètres de l'entrelaceur à
l'intérieur d'une classe donnée :
o Taille ou longueur de l'entrelaceur (cas desentrelaceurs
par blocs);
o Taille et nombre des bancs de registre (cas des
entrelaceurs convolutifs);
o Mémoire ;
o Latence ;
o Facteur d'étalement ;
o Facteur de dispersion, etc …
Les algorithmes qui ont été développés dépendent
donc en grande partie des caractéristiques propres des codeurs
et entrelaceurs utilisés.
Approches utilisées :
Nous avons mis en oeuvres plusieurs méthodes afin d'être
en mesure de détecter la pésence de codeurs/entrelaceurs
et d'identifier les paramètres des codeurs/entrelaceurs étudiés.
L'ensemble des algorithmes développés sont basés
sur des calculs dans le corps de Gallois GF(q) (souvent GF(2) dans le
cas binaire).
1) Approches algébriques :
Nous avons été amené à développer
dans un premier temps des méthodes purement algébriques
basées sur des critères de rang de matrice dans GF(2)
dans le cas de transmission non-entachée d'erreurs, afin de déterminer
les paramètres des codeurs/entrelaceurs. Ces travaux ont fait
l'objet d'une publication dans une conférence internationale.
Exemple de procédure d'estimation en aveugle des paramètres
caractéristiques d'un bloc conjoint codeur/entrelaceur en contexte
non-coopératif :
La Figure 4 est un schéma simplifié des traitements effectués
au niveau de l'émetteur avec présence d'un codeur en bloc
et d'un entrelaceur par bloc. Il décrit également, pour
comparaison et la bonne compréhension des difficultés
inhérentes au contexte non-coopératif, l'ensemble des
paramètres qui sont connus ou inconnus en contexte coopératif
et non-coopératif.
Figure 4 : Schéma simplifié des blocs codeur + entrelaceur
N.B : Dans cet exemple, le but n'est pas de montrer l'ensemble de la
procédure permettant l'identification complète du codeur
et de l'entrelaceur, mais de montrer une approche permettant d'identifier
certains paramètres des ces deux blocs permettant au lecteur
d'obtenir un petit aperçu des travaux effectués dans le
domaine par notre équipe.
La méthode proposée consiste plus précisément
à :
- Estimer la période (ou taille) de l'entrelaceur
;
- D'effectuer une synchronisation aveugle sur les
blocs de l'entrelaceur ;
- D'estimer le rendement du code.
Cette méthode exploite la structure particulière de la
matrice reliant les données interceptées aux données
initiales avant codage et entrelacement, comme cela est illustré
sur la Figure 5 ci-dessous. Cette figure est établie pour un
code en bloc, mais le raisonnement est similaire pour un code convolutif.
Sur cette figure, Gi désigne une matrice (inconnue) représentant
globalement l'effet du bloc « codeur+entrelaceur ». Les
dimensions (inconnues) ni et ki de cette matrice représentent
respectivement la taille de l'entrelaceur et cette taille multipliée
par le rendement du codeur.
Figure 5 : Structure de la matrice reliant données interceptées / données initiales avant codage
Cette figure fait apparaître les différentes inconnues
du problème :
• La taille de l'entrelaceur, ni
• La position des blocs entrelacés. Cette
inconnue est représentée par le décalage entre
les blocs réels et une fenêtre d'analyse de taille na.
Déterminer ce décalage consiste à réaliser
une synchronisation aveugle.
• Le rendement du codeur. Ce rendement est égal
au rapport ki/ni.
• Le contenu de la matrice Gi. La détermination
de ce contenu revient à identifier globalement le bloc «
codeur+entrelaceur ».
La méthode fonctionne en utilisant une fenêtre d'analyse
de taille na. Le contenu de cette fenêtre et lié aux données
non codées et non entrelacées par un matrice inconnue
Ga, représentée sur la figure.
Si la taille na de la fenêtre d'analyse est multiple de la taille
de l'entrelaceur, les matrices Ga correspondant aux fenêtres d'analyse
successives deviennent identiques (voir Figure 5 ci-dessous), alors
qu'elles sont différentes dans le cas contraire. Il apparaît
alors une cohérence globale entre les fenêtres d'analyse,
qui conduit à l'observation d'une chute de rang dans une matrice
construite par empilement de toutes les fenêtres d'analyse.
Figure 6 : Structure de la matrice reliant données interceptées / données initiales avant codage lorsque la taille na des fenêtres d'analyse est multiple de la taille de l'entrelaceur
La Figure 7 suivante montre un exemple d'évolution du rang normalisé
de cette matrice en fonction de la taille de la fenêtre d'analyse.
Des bornes théoriques (courbes en rouge et en vert) peuvent être
calculées, ce qui permet de prédire l'importance de la
chute de rang éventuelle. On voit notamment que la première
chute de rang peut parfois être invisible (lorsque la borne supérieure
est atteinte), ce qui mettrait en défaut une méthode trop
optimiste, utilisant trop peu de données interceptées.
Figure 7 : Courbe représentant l'évolution du rang normalisé en fonction de la taille de la fenêtre d'analyse
Lorsque la taille de l'entrelaceur a été estimée,
une synchronisation aveugle est réalisée. On peut montrer
que le rang atteint un minimum lorsque la fenêtre d'analyse est
correctement synchronisée. La Figure 8 ci-dessous illustre l'évolution
du rang en fonction de la position de la fenêtre d'analyse. La
courbe en rouge représente un minimum théorique, que l'on
peut pré-calculer. On peut observer que ce minimum théorique
est atteint lorsque la synchronisation est correcte.
Figure 8 : Courbe d'évolution du rang en fonction de la position de la fenêtre d'analyse
Cela est dû au fait que dans le cas synchronisé, la matrice
Ga prend sa forme la plus compacte, comme on peut le voir sur la Figure
9 ci-dessous.
Figure 9 : Forme la plus compacte de la matrice globale
Lorsque la synchronisation aveugle a été réalisée,
des outils d'algèbre linéaire, permettent d'identifier
le contenu de la matrice Gi.
Dans le cas des codeurs convolutifs, des algorithmes basés sur
la résolution de systèmes linéaire dans GF(2),
nous ont permis de remonté jusqu'aux polynômes générateurs
des codeurs.
Nous avons également été capables, dans le cadre
d'un contrat d'identifier l'ensemble des paramètres d'un Turbocodeur
convolutif parallèle et de retrouver une grande partie de ceux
d'un Turbocodeur série.
2) Approches probabilistes et itératives :
Dans un deuxième temps, nous avons exploré des améliorations
possibles dans le cas de l'extension au cas où le train binaire
est entaché d'erreurs de transmission. Ces approches ont consisté
à utiliser un critère probabiliste pour quantifier la
quantité de redondance introduite par le codeur et de rendre
le processus itératif afin d'améliorer à chaque
passe la qualité de l'estimation des paramètres.
3) Approches statistiques :
Finalement, dans le cadre d'un autre contrat avec une grande entreprise,
nous avons mis en œuvre des algorithmes purement statistiques,
basés sur les sous-espaces duaux des codeurs et l'identification
de matrice de parités.
II.2 Détection
et identification des blocs « Codage de Source »
L'étude sur la détection et l'identification des blocs
« Codage de Source » a essentiellement porté jusqu'à
présent sur le bloc « Compression », le bloc «
cryptographie » étant à lui tout seul un domaine
à part relevant plus particulièrement des Mathématiques
appliquées à l'informatique qu'au traitement du signal
pour les communications numériques. Cette étude fait partie
des travaux de recherche entamés en interne au sein de l'équipe
TST depuis quelques années dans le domaine de l'analyse de train
binaire et tout particulièrement sur la détection et l'identification
des paramètres de compresseurs en contexte non coopératif.
L'émergence des applications nouvelles qui intègrent la
voix et les données dans une même communication nécessite
la mise au point de méthodes de compression efficaces, flexibles
et qui garantissent la confidentialité des messages. Chaque type
d'information (texte, image, audio, vidéo) possède son
propre système de codage. Les exigences du codage à débit
réduit (la bande passante n'est pas une ressource extensible)
conduisent à des algorithmes de compression de plus en plus variés
et sophistiqués. Parmi ceux-ci, on peut citer les standards de
compression pour :
• les textes et donnée binaires
(ZIP, GZIP, LZW, etc..) ;
• l'audio (vocodeurs LPC, MP3, Ogg, etc..) ;
• les images (JPEG, GIF, PNG, etc..) ;
• la vidéo (MPEG-n, etc..) ;
• la télécopie (JBIG, CCITT Groupe4,
etc..).
Dans certaines situations comme par exemple la surveillance des fréquences,
l'écoute en environnements non coopératifs, l'opérateur
peut être conduit à intercepter des signaux dont il n'est
pas forcément destinataire. Dans ces cas, une fois la démodulation
et le décodage de canal réalisé(e)s, il lui est
nécessaire de disposer de méthodes permettant l'identification
des algorithmes de codage de source ayant servi à la compression
des signaux.
Il existe une multitude d'algorithmes de compression regroupés
sous divers standards. Suivant que ces algorithmes sont conçus
dans le but de pouvoir reconstruire entièrement ou partiellement
la donnée originale après décompression, on parle
d'algorithmes de compression sans perte et avec perte.
- La compression sans perte restitue entièrement
les données originales après la décompression,
ce qui lui vaut d'ailleurs d'être désignée parfois
comme une procédure de compactage.
- La compression avec perte s'appuient généralement
sur la quantification et le codage par transformée. Ces techniques
sont utilisées pour des applications où une certaine dégradation
des données est tolérée, situations que l'on rencontre
dans la compression des images et des sons par exemple.
Qu'ils soient avec ou sans perte, les codeurs de source peuvent être
regroupés en trois catégories :
- Les algorithmes à base de dictionnaire ;
- Les algorithmes à base de transformation
;
- Les algorithmes à base de modélisation
statistique
Les quelques procédures présentées dans le paragraphe
précédent et utilisées pour la compression des
données soulignent la grande diversité et surtout la complexité
des codeurs de sources. On peut dès lors envisager deux grandes
familles d'approches pour l'identification de codeurs de source en contexte
non coopératif :
- Une approche basée sur la reconnaissance
de marquants spécifiques à chaque standard (structure
de trame, d'entête, mots de contrôle, …). Cette approche,
qui nécessite un important travail pour répertorier les
standards et en extraire les marquants, devrait donner d'excellents
résultats dès lors que le signal intercepté correspond
à l'un des standards répertoriés et que la totalité,
ou tout au moins l'entête du signal est disponible.
- Une approche purement statistique, basée
sur l'exploitation des imperfections statistiques de la plupart des
codeurs de source. Cette approche ne nécessite pas la disponibilité
de zones particulières du signal (entête, …) et
a l'avantage d'être simple et rapide, mais, de par sa nature statistique,
elle présente des risques de confusions résiduelles qu'il
conviendra d'estimer.
La première approche relève par nature d'une recherche
exhaustive des propriétés des normes en vigueurs et n'a
aucun intérêt en termes de méthodes innovantes en
traitement du signal pour les télécommunications. Seule
la seconde approche a été choisie afin de développer
des algorithmes novateurs et intéressants d'un point de vue traitement
du signal.
L'avantage de la méthode statistique est qu'elle ne nécessite
pas de connaître les algorithmes de compression dans les moindres
détails pour réaliser leur identification. L'idée
est en effet d'étudier les propriétés statistiques,
énergétiques, temporelles et spectrales des données
compressées afin d'en déduire les codeurs de source ayant
servi à leur compression. Le prix à payer pour cet avantage
est le risque de confusions résiduelles, comme mentionnées
plus haut. En effet, la méthode réalise la reconnaissance
en apprenant à détecter automatiquement les imperfections
statistiques de chaque compresseur. A mesure que les algorithmes de
compression s'améliorent, le train binaire compressé ressemble
de plus en plus à un bruit blanc et l'approche statistique peut
donc être mise en défaut avec certains algorithmes de compression
récents. En résumé, l'approche statistique peut
donc constituer un complément ou une alternative à la
méthode basée sur la reconnaissance de marquants.
Principe général de la méthode statistique actuellement
proposée pour la détection et l'identification de compresseurs
:
La compression a vocation à réduire la redondance contenue
dans le signal informationnel. L'un des principaux effets du codage
de source, bien que non initialement recherché, est de dissimuler
le signal informationnel en le transformant en un signal ayant l'apparence
du bruit blanc. Cette opération a pour conséquence de
rendre plus difficile l'interception et le décodage du signal
utile en contexte non coopératif. Ainsi, un opérateur
non destinataire du message et qui, par conséquent, ignore le
codeur de source employé pour comprimer ce signal peut avoir
des difficultés à extraire de l'information de ce signal
très proche d'un bruit blanc.
Cependant, malgré la multiplicité et la complexité
croissantes des algorithmes de compression, on peut s'attendre, à
juste titre, à ce que la transformation réalisée
sur le signal informationnel par les codeurs de source ne soit pas parfaite.
Comment mettre donc en évidence les traits caractéristiques
des codeurs de sources ? Une approche possible consiste à développer
un système de classifieurs en mode supervisé.
La démarche adoptée peut s'articuler autour de trois phases
:
1) le développement des outils de traitement
du signal pour l'extraction des paramètres ;
2) l'extraction et la sélection des paramètres
discriminants (paramètres susceptibles de contenir des informations
pertinentes sur le compresseur) ;
3) la classification et l'identification des compresseurs
à partir des vecteurs de paramètres associés.
Figure 10 : Un exemple d'organigramme de la procédure d'aide à l'identification de codeurs de source
Nous avons imaginé le développement de classifieurs dédiés
à l'identification d'un type particulier de compresseur (ex.
MELP, OGG, GSM … ) à la suite d'un premier classifieur
qui permet lui d'identifier la classe à laquelle appartient ce
compresseur, c'est-à-dire la classe audio dans l'exemple. On
réalise ainsi un système à coopération de
classifieurs. L'organigramme de la Figure 10 décrit un exemple
de procédure à suivre pour l'aide à la décision.
Cependant, avant cette procédure, il est nécessaire de
constituer une base de données des signaux compressés
selon la démarche suivante (voir Figure 11):
• Constituer une batterie de programmes exécutables
de compresseurs associés aux types de données (texte,
images, audio...) considérées ;
• Constituer une base de données originales
(texte, images, audio...) ;
• Générer une base de fichiers
compressés : à chaque classe de fichiers originaux, on
applique le compresseur dédié pour générer
les fichiers compressés équivalents.
Ce sont ces fichiers qui serviront de base pour l'étude. Une
étude approfondie des propriétés temporelles, statistiques,
énergétiques et spectrales de ces fichiers compressés
permet alors de révéler leurs paramètres caractéristiques
pouvant servir à leur identification.
Figure 11 : Construction de la base de données des signaux compressés
Quelques outils de traitement du signal pour l'extraction des paramètres
:
Nous nous sommes intéressés à des outils de traitement
du signal très simples à mettre en œuvre. Ces outils
doivent permettre de générer des paramètres caractéristiques
afin d'alimenter le classifieur (Figure 12).
Les signaux sont constitués de trains binaires qui sont lus sur
des groupements de n bits, afin d'en faire ressortir certains comportements
caractéristiques, appelés également paramètres
discriminants, après application des outils de traitement du
signal.
Figure 12 : Apprentissage en mode supervisé du classifieur neuronal
Les outils que nous avons mis en œuvre et qui ont donnés
des résultats prometteurs sont :
- La densité spectrale de puissance (DSP) estimée
: La densité spectrale de puissance (DSP) d'un signal donne la
répartition de la puissance de ce signal en fonction de la variable
fréquentielle. La DSP est de fait une estimation du spectre de
ce signal. Elle permet de révéler des périodicités
cachées (présence de pics spectraux) dans le signal lorsque
par exemple la représentation temporelle ne le permet pas.
L'un des effets du codage de source étant de transformer le signal
codé en un bruit (presque) blanc, la performance du codeur de
source pourrait se mesurer à « la platitude » de
la DSP du signal compressé résultant. Le niveau spectral
du signal compressé peut donc être un facteur discriminant
pour identifier un algorithme de compression (voir la Figure 13 ci-dessous)
Figure 13 : Représentation de la densité spectrale de puissance (DSP) de quelques signaux de vocodeurs
- La densité de probabilité a posteriori
(DDP) estimée : La diversité et la complexité des
codeurs de source peuvent naturellement donner à penser que les
signaux issus de la compression des données par ces codeurs présentent
des lois de probabilité très différentes. En outre,
si l'on admet qu'un signal original (signal avant compression) contient
des redondances, il est à tout à fait légitime
de penser que sa densité de probabilité (DDP) après
compression soit différente de celle de l'original.
- La modélisation par prédiction linéaire
(LPC) : Nous avons extrait les coefficients de prédiction linéaire
(ou LPC pour Linear Predicting Coding) comme paramètres caractéristiques
pouvant aider à l'identification des codeurs de sources surtout
les compresseurs de signaux audio. En effet, la plupart des vocodeurs
(codeurs spécialisés pour les signaux audio) utilisent
le principe de la prédiction linéaire, ceci afin de prendre
en compte la corrélation entre les échantillons voisins
du signal.
Non seulement le modèle de prédiction linéaire
permet de prendre en compte la corrélation entre échantillons
voisins mais en outre il peut contenir les traits caractéristiques
du vocodeur. Fort de ce constat, cette modélisation a été
considérée dans le cadre d'un contrat sur l'identification
de standards de codeur de source au sein de l'équipe TST. Les
coefficients LPC extraits des fichiers compressés exhibent certes
des caractéristiques des vocodeurs étudiés mais
le critère de sélection des coefficients pertinents parmi
ceux-ci, reste quelque peu heuristique. Il faudra donc pousser les investigations
en vue de l'amélioration de la procédure de sélection
de ces paramètres.
- L'analyse par corrélation canonique (ACC)
: L'analyse par corrélation canonique (ACC) est une méthode
qui permet de mesurer la dépendance linéaire entre deux
variables aléatoires multidimensionnelles. Introduite pour la
première fois par H. Hotelling en 1936, la CCA est un outil standard
en analyse statistique des données habituellement utilisée
en économie, métrologie etc… mais étrangement
absente dans la communauté du traitement du signal et de l'apprentissage.
L'ACC peut être vue comme une méthode qui vise à
déterminer deux vecteurs de base x et y à partir de deux
jeux de données, de sorte que la corrélation entre les
projections de ces variables sur ces vecteurs de base soient mutuellement
maximales. Une propriété importante de l'ACC, c'est qu'elle
reste invariante par rapport à une transformation affine, ce
qui constitue la propriété principale qui différentie
l'ACC de l'analyse par corrélation classique.
On peut utiliser ce type d'analyse lorsque l'on veut trouver les relations
entre différentes représentations des mêmes objets
par exemple.
Les premiers résultats obtenus dans le cadre d'un contrat avec
un organisme militaire sont très encourageants en termes de performance
de classification.
Les principaux points durs du problème à résoudre
et les questions en cours d'investigations :
- La multiplicité et la complexité des
standards actuellement disponibles ne sont pas de nature à faciliter
le développement d'un système d'identification en contexte
non coopératif.
- Le nombre de bits de lecture des trains binaires
interceptés : Dans l'état actuel de nos travaux sur l'identification
de codeurs de source, un fichier lu sur un ou deux bits révèle
moins de caractéristiques saillantes par rapport au même
fichier lu sur un nombre de bits différents. Un choix précédent
de 8 bits de lecture a donné des résultats très
satisfaisants mais peut-on pour autant plébisciter ce choix pour
tout type de données ?
- La durée d'observation du signal : Combien
d'échantillons faut il prendre en compte pour une estimation
correcte des paramètres ?
II.3 Optimisation
des algorithmes et aspects opérationnels
La plupart des algorithmes ont été développés
initialement à l'aide du logiciel MATLAB® qui est très
gourmant en espace mémoire à cause de son codage des nombres
en double précision pour effectuer ses calculs en interne. Pour
cela, nous avons à chaque étape du développement
de nos algorithmes fait en sorte d'optimiser les calculs en effectuant
les opérations strictement nécessaires et de la manière
la plus appropriée en fonction des données manipulées.
Nous avons également, à l'issue des phases de test de
validité de nos algorithmes, codé une grande partie de
ces algorithmes en C afin d'accélérer les calculs et de
profiter des optimisations possibles inhérentes à la manipulation
de données binaires en terme de stockage et type d'opérations.
Cependant, les algorithmes nécessitent tout de même de
manipuler de grande quantités de données pour la résolution
de systèmes linéaire de grande taille, tout cela en fonction
des paramètres des codeurs et des entrelaceurs à intercepter,
dont les tailles peuvent devenir très importantes dans les normes
ressentes (le taille d'un entrelaceur peut atteindre facilement 10000
ou plus, ce qui entraine le traitement de blocs de données de
l'ordre de 100 M bits). Pour cela nous avons fait l'acquisition de deux
serveurs bi-processeurs 64 bits (dont un est représenté
sur la photo de la Figure 15) avec une capacité mémoire
de 8Go spécialement dédiés pour ces applications
afin d'être en mesure d'effectuer des tests sur des configurations
proches de celles utilisées dans les normes actuelles.
Figure 15 : Serveur de calcul bi-processeurs 64 bits
III. Perspectives
La plupart de ces travaux ayant été développés
dans le cadre de contrats, il n'a pas encore été possible
de les publier. Cependant plusieurs publications sont en cours de rédactions
et une thèse vient d'être lancée sur le sujet afin
d'explorer de manière plus approfondie l'ensemble de ce sujet
de recherche et d'aboutir à la valorisation des travaux par des
publications internationales. Cette thèse financée par
la Région Bretagne, a également pour but l'intégration
de nos algorithmes sur une chaîne matérielle RF à
2.4 GHz, afin de tester en situation réelle nos algorithmes et
de disposer d'un démonstrateur opérationnel.
La Figure 16 montre une photo de la chaîne RF complète
permettant à partir d'un PC via liaison ethernet de transmettre
un flux de données générées par exemple
à l'aide du logiciel MATLAB® ou provenant d'un fichier.
Figure 16 : Chaîne matérielle d'émission / réception RF 2.4 GHz générique
La Figure 17 montre l'ensemble des modules matériels de la partie
émission, qui comprend une partie interface ethernet pour liaison
avec un PC, un module de stockage en RAM, un module de conversion numérique
/ analogique avec sorties I/Q, un modulateur avec mise sur porteuse
dans la bande des 2.4 GHZ avec choix de la fréquence centrale
et un étage d'amplification comprenant un duplexeur In/Out.
Figure 17 : Partie émission
Respectivement la Figure 18 montre l'ensemble des modules matériels
de la partie réception, qui comprend un étage d'amplification
comprenant un duplexeur In/Out, un démodulateur avec convertisseur
analogique / numérique intégré avec obtention des
symboles I/Q numériques, un module de stockage en RAM et une
interface ethernet pour liaison avec un PC..
Figure 18 : Partie réception
L'ensemble des modules des parties émission et réception
sont entièrement configurables à distance via une liaison
série ou ethernet.
Cette chaîne a l'avantage d'être générique
et de permettre dans un premier temps le post-traitement en réception
par des algorithmes aveugle d'interception et dans un second temps d'adjoindre
des blocs génériques à base de FPGA ou de DSP,
où il sera possible d'implémenter nos algorithmes à
l'aide de descriptions VHDL ou en C.
IV. Applications et valorisations
Les domaines d'application de ces travaux relèvent
initialement en grande partie du domaine de l'interception militaire,
beaucoup d'autres applications voient le jour, comme les récepteurs
auto-configurant dans le cadre des projets « radio logiciel »,
la surveillance du spectre radiofréquence et surtout la sécurité
des transmissions domaine mis en avant dans les pôles de compétitivités
liés aux Télécoms.
L'arrivée de terminaux adaptatifs et auto-configurants permettra
de mettre en œuvre de nouvelles applications et services interactifs,
qui de plus pourront fonctionner quelque soit le standards ou/et le
pays. Les terminaux pourront donc être vendus indépendamment
du pays où se fera réellement l'exploitation et seront
reconfigurables lors de l'utilisation pour une application donnée
ou même pour mise à niveau du terminal sans nécessité
de le renvoyer en usine ou d'en racheter un nouveau. Les « bugs
» pourront donc être corrigés comme pour des logiciels
de manière transparente pour l'utilisateur.
De plus, nos approches visent à l'amélioration de la sécurité
des transmissions, par l'apport de moyen de test pour vérifier
le degré de résistance d'une structure d'émetteur
et de ses paramètres face à une tentative d'identification
aveugle des paramètres de cette transmission.
Les aspects matériels de notre projet sont indéniablement
des apports potentiels important au progrès technologique régional
et sont tout à fait en adéquations avec les préoccupations
des pôles de compétitivités développés
au sein de la région. Sont concernés en particulier le
pôle "Image et Réseaux", par l'intermédiaire de
la préoccupation croissante de reconfigurabilité et de
sécurité des transmissions sur réseaux, et le pôle
Mer, par l'intermédiaire de la sécurisation des transmissions
en acoustique sous-marine.
V. Thèses
* Mélanie MARAZIN, « Mise en oeuvre d'un
récepteur auto-configurant en aveugle: Application à la
sécurité des transmissions pour les communications numériques
»
Financement : Région Bretagne
Directeur de thèse : G. Burel, Co-encadrant : R. Gautier
Date de soutenance prévisible : octobre 2009
VI. Publications
Une grande partie de ces publications sont disponibles
au format PDF dans la rubrique générale Publications de
ce site.
* R. Gautier, G. Burel, J. Letessier, and O. Berder, "Blind Estimation
of Scrambler Offset using Encoder Redundancy", Thirty-Sixth Annual Asilomar
Conference on Signals, Systems, and Computers, Pacific Grove, California,
November 3-6, 2002.
* G. Burel and R. Gautier, “Blind Estimation of Encoder and Interleaver
Characteristics in a Non Cooperative Context”, IASTED International
Conference on Communications, Internet and Information Technology (CIIT
2003), Nov. 17-19, 2003, Scottsdale, AZ, USA.
VII. Contrats
[1] Reconnaissance de compresseurs à partir
de transmissions interceptées
Période : 2003-2004, Type de client : organisme
militaire.
[2] Détection et identification de turbocodeurs
Période : 2003-2004, Type de client : organisme
militaire.
[3]Détection et reconnaissance de codeurs et d'entrelaceurs à
partir d'une transmission interceptée
Période : 2005-2007, Type de client : grande
entreprise.