UFR DE SCIENCES APPLIQUEES ET TECHNOLOGIE

********************
SECTION PHYSIQUE APPLIQUEE
**********
DIETEL III

TECHNIQUES MODERNES DE
TRANSMISSION
LES CODES A LONGUEUR MAXIMALE

Présentation SOUS LA DIRECTION DE

M. Cheikh Ahmet Tidiane DIENG Dr Pape Alioune FALL
M. Serigne Mbacké NDIAYE
M. Abdou Khadre NDOYE
M. Chérif Hamidou SY 1 28/03/2011
 PLAN
Introduction
1. Rappels
1.1 Etalement de spectre
1.2 Les séquences pseudo aléatoires
2. Codes à longueur maximale
2.1 Codes de Gold
2.2 Codes de Kasami
2.3 Codes de Walsh
2.4 Codes OVSF
3. Application: Le système CDMA
Conclusion
28/03/2011 2
 Introduction(1)

• Passage de l’analogique vers le numérique

• Processus de numérisation
- Quantification
- Echantillonnage
• Codage source
• Codage canal

28/03/2011 3
 Introduction(2)

La bande passante est une

ressource rare qu’il faut utiliser à
bon escient et partager entre tous
les utilisateurs. Il est donc nécessaire de
transmettre simultanément sur un même canal le
plus grand nombre de messages
possibles.

28/03/2011 4
 Introduction(3)

• Etalement de spectre
- par séquence directe
- par saut de fréquence
• Séquences pseudo-aléatoire
28/03/2011 5
 Introduction(4)
Les codes linéaires maximaux sont un exemple
de codes couramment utilisés dans les systèmes
de communications. Ils sont les briques de base
des codes plus complexes tels que les codes de
Gold utilisés en UMTS ou de Kasami.

28/03/2011 6
 1. Rappels
1.1 Etalement de spectre

1.1.1 Etalement par séquence directe (Direct

Sequence Spread Spectrum)

1.1.2 Etalement par saut de fréquence

1.2 Les séquences pseudo aléatoires

28/03/2011 7
 1.1 Etalement de spectre(1)
L’idée est de transformer un signal en bande relativement étroite
en un signal qui a l’apparence d’un bruit sur une large bande.

On obtient un spectre étalé en modulant le signal avec une

séquence connue sous le nom de séquence pseudo aléatoire
ayant une apparence de bruit, en remplacement de chaque bit de
message.

Le signal étalé (spectralement) doit apparaître comme du bruit,

en particulier pour les autres transmissions éventuelles utilisant
le même spectre étalé.
28/03/2011 8
 1.1 Etalement de spectre(2)
1.1.1 Etalement par séquence directe (Direct
Sequence Spread Spectrum)

Le principe en D.S.S.S consiste à remplacer chaque

bit 1 par une séquence-code à M ‘chips’ et chaque bit
‘0’ par la séquence complémentaire. Ces séquences-
codes sont judicieusement choisies pour leurs
propriétés mathématiques. Comme le signal obtenu
contient beaucoup plus de transitions (changement de
chip) que le signal-message original contient de
transitions (changement de bit), la bande spectrale est
élargie dans un rapport égal au nombre de chips.

28/03/2011 9
 1.1 Etalement de spectre(3)
1.1.2 Etalement par saut de fréquence
Il existe deux formes de sauts de fréquences pour
l’étalement de spectre, la première est le saut de
fréquences rapide qui consiste à changer la fréquence
porteuse à chaque chip (Fast Frequency Hopping
Spread Spectrum: FFH-SS), et la deuxième appelée
saut de fréquences lent consiste à changer la fréquence
de la porteuse à chaque bit d’information(Slow
Frequency Hopping Spread Spectrum: SFH-SS).

10 28/03/2011
 1.2 Les séquences pseudo
aléatoires(1)

On appelle code pseudo-aléatoire un signal

numérique le plus souvent binaire de moyenne
nulle (comportant autant de 1 que de 0),
périodique, et dont le spectre se rapproche de
celui d’un bruit blanc.

28/03/2011 11
 1.2 Les séquences pseudo
aléatoires(2)
1.2.1 Générateur pseudo aléatoire
Un générateur pseudo aléatoire de nombres est
une ou un ensemble de procédures permettant de
générer une séquence pseudo aléatoire de
nombres qui calcule chaque nombre à partir du
précédent et vérifiant certaines propriétés par
exemple : tous les nombres générés doivent être
indépendants les uns des autre de façon à ce que
aucune règle ne puisse être reconstituée à partir
de la suite de nombres générés.
28/03/2011 12
 1.2 Les séquences pseudo
aléatoires(3)
1.2.1 Générateur pseudo aléatoire
Afin de tester si un générateur est acceptable,
l’une des méthodes les plus courantes est
d’employer les principes de complexité
algorithmique : c'est-à-dire qu’en temps
raisonnable, aucun algorithme ne pourra prédire
le fonctionnement d’un générateur.

28/03/2011 13
1.2 Les séquences pseudo aléatoires(4)
1.2.2 Séquences pseudo aléatoires à Longueur
Maximale (MLLFSR: Maximum Length Linear Shift
Register)

Génération
Obtenue à l’aide d’un registre à décalage bouclée

28/03/2011 14
28/03/2011 15
28/03/2011 16
28/03/2011 17
28/03/2011 18
28/03/2011 19
28/03/2011 20
28/03/2011 21
28/03/2011 22
28/03/2011 23
28/03/2011 24
28/03/2011 25
28/03/2011 26
28/03/2011 27
1.2 Les séquences pseudo aléatoires(5)
1.2.2 Séquences pseudo aléatoires à Longueur Maximale
(MLLFSR: Maximum Length Linear Shift Register)

Propriétés:
-1- Dans une ML le registre à décalage va passer par toutes les
combinaisons possibles de "0" et de "1" sauf la combinaison
[0 0 0 ....0] qui est interdite car c'est une combinaison de
blocage
-2- Dans une ML le nombre de prises doit être pair. En effet, si
le nombre de prises est impair la combinaison [1 1 1.... 1] est
interdite car c'est une combinaison de blocage

28/03/2011 28
1.2 Les séquences pseudo aléatoires(6)
1.2.2 Séquences pseudo aléatoires à Longueur Maximale
(MLLFSR: Maximum Length Linear Shift Register)

Propriétés:

-3- Une ML séquence est périodique de période L=2𝑅 - 1

(conséquence de 1).
L−1 L+1
-4- Dans une ML il y a 2 fois "0" et 2 fois "1", c'est à dire qu'il
y a un "1" de plus par rapport aux "0" (conséquence de 1).
-5- La somme modulo 2 (XOR) d'une ML séquence avec une version
décalée de celle ci (0<décalage<L) donne une autre version de cette
même ML séquence.

28/03/2011 29
1.2 Les séquences pseudo aléatoires(7)
1.2.2 Séquences pseudo aléatoires à Longueur Maximale (MLLFSR:
Maximum Length Linear Shift Register)
Exemple: Registre à décalage de longueur 4
Prises sur cases 1 et 4
111101011001000
L=15
Nombre de "1"=8
Nombre de "0"=7
C(n): 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0
C(n+6): 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1
C(n) XOR C(n+6): 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1
28/03/2011 30
1.2 Les séquences pseudo aléatoires(8)
1.2.2 Séquences pseudo aléatoires à Longueur Maximale
(MLLFSR: Maximum Length Linear Shift Register)
Propriétés:
-6- L'autocorrélation d'une séquence ML ("0" représenté
par le niveau +1 et "1" représenté par le niveau -1) a la
forme suivante:

28/03/2011 31
1.2 Les séquences pseudo aléatoires(9)
1.2.2 Séquences pseudo aléatoires à Longueur Maximale (MLLFSR:
Maximum Length Linear Shift Register)
Propriétés:

-7- Sur une période de ML séquence il y a:

Aucune série de "0" de longueur R, Une série de "1" de longueur R
Une série de "0" de longueur R-1, Aucune série de "1" de longueur R-1
2R-P-2 séries de "0" de longueur P, 2R-P-2 séries de "1" de longueur P

Registre à décalage de longueur 4 (Prises sur cases 1 et 4)

111101011001000 1 série de R=4 "1"
111101011001000 1 série de R- 1=3 "0"
111101011001000 1 série de 2 "1"
111101011001000 1 série de 2 "0"
111101011001000 2 séries de 1 "1"
111101011001000
111101011001000 2 séries de 1 "0"
111101011001000 28/03/2011 32
 1.2 Les séquences pseudo aléatoires(10)
1.2.2 Séquences pseudo aléatoires à Longueur Maximale
(MLLFSR: Maximum Length Linear Shift Register)
Propriétés:
-8- La densité spectrale de puissance d'une ML séquence est un spectre de
raies:
+∞
𝐿+1 𝑘 𝑘 1
𝑆𝑐 𝑓 = 𝑠𝑖𝑛𝑐 2 𝛿 𝑓− + 𝛿(𝑓)
𝐿2 𝐿 𝐿. 𝑇𝑐 𝐿2
𝑘=−∞
𝑘≠0

28/03/2011 33
1.2 Les séquences pseudo aléatoires(11)
1.2.2 Séquences pseudo aléatoires à Longueur Maximale
(MLLFSR: Maximum Length Linear Shift Register)
Propriétés:
-10- Si un registre à décalage génère une ML séquence, le registre inverse
génère, lui aussi, une ML séquence qui est inversée:
Polynôme caractéristique du registre à décalage:

𝑓 𝑥 = 𝑎𝑘 𝑥 𝑘
𝑘=0
𝑀𝑜𝑑𝑢𝑙𝑜 2
Polynôme caractéristique réciproque:

𝑅 𝑘
1
𝒇𝒓é𝒄𝒊𝒑𝒓𝒐𝒒𝒖𝒆 𝑥 = 𝑥 𝑅 𝑎𝑘
𝑥
𝑘=0
𝑀𝑜𝑑𝑢𝑙𝑜 2
29/03/2011 34
 1.2 Les séquences pseudo aléatoires(12)
1.2.2 Séquences pseudo aléatoires à Longueur Maximale
(MLLFSR: Maximum Length Linear Shift Register)
Propriétés:
Exemple de polynôme caractéristique :

28/03/2011 35
 1.2 Les séquences pseudo aléatoires(13)
1.2.2 Séquences pseudo aléatoires à Longueur
Maximale (MLLFSR: Maximum Length Linear
Shift Register)
Propriétés:
Exemple: R=5
[5 2] génère une ML séquence, [5 3] génère la même ML séquence
à l'envers
0011001111100110100100001010111
1110101000010010110011111001100

28/03/2011 36
2. Codes à longueur maximale

2.1 Codes de Gold

2.2 Codes de Kasami

2.3 Codes de Walsh

2.4 Codes OVSF

28/03/2011 37
 2. Codes à longueur maximale(1)
2.1 Codes de Gold

• Le code de Gold est un type de séquence pseudo-

aléatoire très utilisé dans les codages CDMA. Il
appartient à la famille des codes d’embrouillage
appelés couramment Scrambling codes ou encore
codes PN (Pseudo Noise Codes).

• Le code de Gold permet d'éviter le problème

d'intercorrélation en multiplexage CDMA

28/03/2011 38
 2. Codes à longueur maximale(2)

2.1 Codes de Gold

Parmi une famille de ML (Max Length), séquences de

longueur L, il est possible de trouver des couples de ML
séquences qui ont une faible intercorrélation. Ces couples
sont appelés "paires préférées".

Gold a démontré que si f(x) et g(x) sont deux polynômes

générant des paires préférées (ML séquence de longueur L)
alors le polynôme z(x)=f(x).g(x) génère des séquences de
longueur L dont l'intercorrélation reste faible.
28/03/2011 39
 2. Codes à longueur maximale(3)
2.1 Codes de Gold
Soit α une racine de f(x) alors les "paires préférées" vérifient les
conditions suivantes:
2[𝑅−1]
+1
• α 2 est une racine de g(x) si R est impair
2[𝑅−2]
+1
• α 2 est une racine de g(x) si R est pair

Soient a(t) est une ML séquence générée par le polynôme irréductible

f(x) de degré R(non divisible par 4) et b(t) est une ML séquence
générée par le polynôme irréductible g(x) alors l’intercorrélation a les
propriétés suivantes:
(𝑅+1)
𝑅𝑎𝑏(𝑘) < 2 2 + 1 si R est impair
(𝑅+2)
𝑅𝑎𝑏(𝑘) < 2 2 + 1 si R est pair, R non divisible par 4

28/03/2011 40
 2. Codes à longueur maximale(4)
2.1 Codes de Gold
Obtention de paires préférées:
Dans le cas où R n’est pas un multiple de 4:
Si f(x) génère une ML séquence f(n) alors la séquence f(n)
échantillonnée avec une période de t(R) est aussi une ML séquence
et une paire préférée.
(𝑅+2)
(𝑅+2) (𝑅+2)
𝑡 𝑅 =1+2 2 avec la partie entière de
2 2

28/03/2011 41
 2. Codes à longueur maximale(5)
2.1 Codes de Gold

Exemple R=5, MI générée par[2,5], t(R)=9

ML52= 0 0 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 1 1

ML52 échantillonnée = 0 1 0 0 0 1 0…

28/03/2011 42
 2. Codes à longueur maximale(6)
2.1 Codes de Gold
Exemple: R=6, 𝒇 𝒙 = 𝒙𝟔 + 𝒙 + 𝟏 et 𝐠 𝐱 = 𝒙𝟔 + 𝒙𝟓 + 𝒙𝟐 + 𝟏

La valeur absolue de l’intercorrélation entre la ML séquence

(𝑅+2)
générée par f(x) et celle générée par g(x) sera bornée à 2 2 +1=17

28/03/2011 43
 2. Codes à longueur maximale(7)
2.1 Codes de Gold
Propriétés des codes de Gold: Valeurs de l'intercorrélation
Le tableau suivant donne les valeurs de l'intercorrélation entre ML
séquences classiques et codes de Gold:

28/03/2011 44
 2. Codes à longueur maximale(8)
2.1 Codes de Gold
f(n) ML
g(n) ML
f(n)⊕g(n) non ML
f(n)⊕g(n+1) non ML 3 valeurs pour l’intercorrélation:
f(n)⊕g(n+2) non ML -1,-t(R),t(R)-2
…. non ML
…. non ML
f(n)⊕g(n+L−1) non ML

𝑅+2 𝑅+2
avec t(R)=1+2 2 , R est la longueur du registre à décalage et la
2
𝑅+2
partie entière de
2

28/03/2011 45
 2. Codes à longueur maximale(9)
2.1 Codes de Gold
Gold a montré que l'intercorrélation entre deux séquences ne prend que
trois valeurs possibles avec une certaine probabilité connue.
On distingue trois classes codes de Gold :

28/03/2011 46
2. Codes à longueur maximale(10)
2.1 Codes de Gold

28/03/2011 47
2. Codes à longueur maximale(11)
2.1 Codes de Gold

28/03/2011 48
2. Codes à longueur maximale(12)
2.1 Codes de Gold

28/03/2011 49
2. Codes à longueur maximale(13)

2.2 Codes de Kasami, small set

Si R est pair et si f(n) est une ML générée par
f(x) alors on peut construire le «small set » des
séquences de Kasami de la façon suivante:
Echantillonner f(n) avec une période
𝑅
𝑠 𝑅 =1+2 2

afin d ’obtenir la séquence g(n).

28/03/2011 50
2. Codes à longueur maximale(14)
2.2 Codes de Kasami, small set

L’ensemble des codes du "small set " de Kasami est formé

par :
f(n) ML
f(n)⊕g(n) non ML
f(n)⊕g(n+1) non ML
𝑅
f(n)⊕g(n+2) non ML 2 séquences
2

…. non ML 3 valeurs pour

…. non ML l’intercorrélation:
𝑅
f(n)⊕g(n+2 − 2) non ML -1,-s(R),s(R)-2
2
𝑅
avec s(R)=1+2 , R est la longueur du registre à décalage
2
28/03/2011 51
2. Codes à longueur maximale(15)
2.2 Codes de Kasami, small set

Exemple R=6, ML générée par[1,6], s(R)=9

𝑅
Avec ces deux séquences on génère 2 = 8 codes de Kasami pour
2
former le « small set» des codes de Kasami

L’intercorrélation prend trois valeurs: -1, s(R)-2, s(R)

28/03/2011 52
2. Codes à longueur maximale(16)

2.2 Codes de Kasami, large set

On fabrique des codes de Kasami Large set en multipliant la
sortie de plusieurs générateurs de codes linéaires maximaux de
longueur différentes. Par exemple, deux codes linéaires
maximaux de longueur 2𝑘 − 1 avec un troisième code linéaire
maximal décimé(certains bits sont soustraits) de longueur
𝑘
2 + 1. La période des codes ainsi obtenue peut être très longue
2

mais le temps de synchronisation du système reste très court.

28/03/2011 53
2. Codes à longueur maximale(17)

2.2 Codes de Kasami, large set

Si R est pair et si f(n) est une ML générée par f(x) alors on peut
construire le «large set » des séquences de Kasami de la façon
suivante:
𝑅
• Echantillonner f(n) avec une période 𝑠 𝑅 = 1 + 2 afin2

d’obtenir la séquence g(n)

𝑅+2
• Echantillonner f(n) avec une période t(R)= 1 + 2 2 afin
d’obtenir la séquence h(n)

28/03/2011 54
2. Codes à longueur maximale(18)

2.3 Codes de Walsh

• Fonctions de Walsh: Signaux binaires orthogonaux

𝐻𝑀 𝐻𝑀
2 2 +1 +1
𝐻𝑀 = avec 𝐻2 =
𝐻𝑀 −𝐻𝑀 +1 −1
2 2

28/03/2011 55
2. Codes à longueur maximale(19)

2.3 Codes de Walsh

Exemple: 8 fonctions de Walsh avec 8 chips/fonction

1 1 1 1 1 1 1 1
1 −1 1 −1 1 −1 1 −1
1 1 −1 −1 1 1 −1 −1
1 −1 −1 1 1 −1 −1 1
𝑯𝟖 =
1 1 1 1 −1 −1− 1 −1
1 −1 1 −1 −1 1 −1 1
1 1 −1 −1 −1 −1 1 1
1 −1 −1 1 −1 1 1 −1

28/03/2011 56
2. Codes à longueur maximale(20)
2.3 Codes de Walsh
• Avantage: si les temps de propagation sont tous identiques
l'orthogonalité est parfaitement respectée: ce type de codes pourra
être utilisé dans un contexte radiomobile pour le sens de
transmission Station de Base vers Terminaux.
• Inconvénient: si les temps de propagation sont différents
l'orthogonalité n'est plus respectée (voir, par exemple, les fonctions
5 et 6 suivantes). Ces codes ne sont donc pas utilisables pour le sens
Terminaux vers Station de Base. De même, les trajets multiples
pourront détruire l'orthogonalité des fonction de Walsh.

28/03/2011 57
2. Codes à longueur maximale(21)
2.4 Codes OVSF
(Orthogonal Variable Spreading Code)

Tous les codes sont deux à deux orthogonaux sauf s’ils

appartiennent à des niveaux de branche différents, et que l’un est le
père de l’autre.
28/03/2011 58
2. Codes à longueur maximale(22)
2.4 Codes OVSF
Corrélation des codes OVSF

• La fonction d’autocorrélation d’un code OVSF, de longueur N, atteint la

valeur N lorsque le décalage est nul.

• Lorsque le décalage est non nul, la fonction prend des valeurs comprises
entre +N et- N, avec de grandes variations en fonction du décalage.

Soient les codes OVSF suivants:

𝐶1 = 1 1 1 1 − 1 − 1 − 1 − 1 1 1 1 1 − 1 − 1 − 1 − 1
𝐶2 = 1 1 1 1 − 1 − 1 − 1 − 1 − 1 − 1 − 1 − 1 1 1 1 1
𝐶3 = 1 1 − 1 − 1 − 1 − 1 1 1 1 1 − 1 − 1 − 1 − 1 1 1
28/03/2011 59
2. Codes à longueur maximale(23)
2.4 Codes OVSF
Corrélation des codes OVSF

La fonction d’intercorrélation d’un code OVSF est toujours nulle lorsque le

décalage est égal à 0. C’est pour cette raison que ces codes sont dits
orthogonaux. Lorsque le décalage est non nul, la fonction peut rester nulle,
ou bien prendre des valeurs entre +N et -N. 28/03/2011 60
3. Application: Le système
CDMA

28/03/2011 61
3. APPLICATION: LE SYSTÈME CDMA(1)

Une des applications majeures des codes à longueur

maximale est les réseaux de troisième génération de
type UMTS caractérisés par une interface radio basée
sur une technique WCDMA.

28/03/2011 62
3. APPLICATION: LE SYSTÈME CDMA(2)
Principe
L’accès multiple à répartition en code consiste à offrir à tous les
utilisateurs toute la bande disponible sur une durée illimitée : tout
le mode parle en même temps au même endroit ! Pour que ce
dispositif fonctionne, il faut alors que chacun parle une langue
différente pour que le récepteur reconnaisse l’information qui lui
est envoyé.

28/03/2011 63
3. APPLICATION: LE SYSTÈME CDMA(3)
Principe
La technique WCDMA, utilisée pour la voie montante de
l’UMTS, repose sur l’allocation de deux types de codes :
• les séquences pseudo-aléatoires utilisées pour différencier les
utilisateurs,
• les codes orthogonaux OVSF utilisés pour différencier les
services d’un même utilisateur.

La modulation se décompose en deux phases :

• 1re phase : l’étalement (ou spreading),
un code OVSF est alloué à chaque service d’un utilisateur

• 2e phase : le brouillage (ou scrambling),

une séquence pseudo-aléatoire est allouée à chaque utilisateur
29/03/2011 64
3.APPLICATION: LE SYSTÈME CDMA(4)

Avantages CDMA :
• protection (sécurité) des communications,
• qualité,
• faible consommation,
• flexibilité de l’allocation…

Le CDMA, s’il est intéressant pour la voix, présente

néanmoins des limites pour le transfert des données
fiables (fichiers de données sensibles, bancaires…).
Le TEB est limité à cause du bruit dû aux multiples
séquences des utilisateurs
28/03/2011 65
 Conclusion
Les performances des systèmes de radiocommunications
sont fortement liées aux choix techniques qui permettent à
des utilisateurs multiples (multi user) d'accéder à un canal
de transmission.

L'objectif des premières transmissions militaires étalées

était de résister au mieux à des brouilleurs bandes étroites
ou/et de réaliser des transmissions "discrètes".

28/03/2011 66
 Bibliographie
[1] Thierry Lucidarme, Principes de
radiocommunication de troisième
génération, Vuibert, Paris,2002

[2] D. Roviras, CDMA Accès Multiple

par Codage, Mastère RTSA 2006-2007

[3]Webographie.

28/03/2011 67
28/03/2011 68
28/03/2011 69