Module EN218 → Cours 4

Module EN218 → Cours 4
Systèmes numériques
pour
les communications numériques
Année 2013-2014 / Camille LEROUX
1
Plan du cours 4
Systèmes de communications numériques
Fonction types d’un système de comm. num.
Codes convolutifs
Algorithme de Viterbi
Architecture du décodeur de Viterbi
2
Système de communications numériques
(simplifié)
Transmitter
Transmission Channel
m
Source
Source
Encoder
u
Channel
Encoder
c
Modulator
s(t)
Noisy
Transmitted
Information
Transmitted
m’
: 0 0011010 011 10
Received
y
:
Received
s(t)
:
d
Decoded
z(t)
:
u
:
m
:0 01 0 1 01
c
:
Codeword
Signal
message
signal
vector
00 01 00 11
message
vector
101
1
11
b(t)
Noise,
Interference,
…
010 1
0
00 11
z(t)=s(t)+b(t)
Receiver
Sink
m’
Source
Decoder
d
Channel
Decoder
y
Demodulator
3
Système de communications numériques
(réel : émetteur norme DVB-T)
Codage
source
Scrambler
(LFSR)
Codeur RS
Entrelaceur
symboles
Codeur
convolutif
Entrelaceur
bits
Code BCH
pour
protéger les
pilotes
4
Structure des paquets et octets de synchro
Paquet MPEG-2 = 188 octets = 1 octet SYNC + 188
octets DATA
•
•
•
SYNC = 47HEX ou la version complémenté
not(SYNC)=B8HEX (tous les 8 paquets)
L’envoi de SYNC et not(SYNC) se fait « MSB first »
Les données sont « randomisées » Pr(0)=Pr(1)
On ajoute de la redondance
pour protéger les données :
RS(204,188,8) ???
Rajout de la redondance +
entrelacement des octets
5
Quelle taille pour le flux de données ?
Codage
source
Scrambler
(LFSR)
Codeur RS
Entrelaceur
symboles
Codeur
convolutif
Entrelaceur
bits
Code BCH
pour
protéger les
pilotes
Traitement
bits
Traitement
octets/symboles
6
Caractéritiques des systèmes pour les
télécommunications
• Application type « Machine à coudre »
• Données traitées uniformes (bits, échantillons, symboles, trame)
• Fréquence d’arrivée des données constante
• Algorithme à appliquer à chaque donnée uniforme
• Algorithme de traitement connu à l’avance (norme)
• Cibles technologiques
• ASIC (circuit sur mesure)
• Très bonnes performances (vitesse, conso., surface) car optimisé
pour une seule application
• Coût élevé (seulement pour les produits de grande consommation)
• FPGA (circuit prédiffusé)
• Performance moindre bien que croissantes
• Coût unitaire réduit
• Cibles architecturales
• Archi dédiées (on concoit l’architecture pour une seule appli ou norme)
• Archi type processeur (on utilise un jeu d’instruction qui s’execute sur
un processeur)
Plan du cours 4
Systèmes de communications numériques
Fonction types d’un système de comm. num.
Codes convolutifs
Algorithme de Viterbi
Architecture du décodeur de Viterbi
8
Linear Feedback Shift Registers (LFSR)
• Génération efficace de vecteurs de test
• Flip-Flops + quelques XORs
• Plus efficace qu’un compteur (moins de portes, fréquence plus élevée)
• CRC
• Encodeur Reed-Solomon / BCH
• Génération de séquences pseudo-aléatoire
• Deux types de LFSR
• Boucle de retour externe (external feedback)
• Boucle de retour interne (internal feedback) : fréquence plus élevée
LFSR (2)
• Un LFSR est caractérisé par un polynôme
• Le polynôme définit la position des XOR
• P(x) = x4+x3+x+1
• n = nombre de Flip-flops = degré du polynôme
• Un LFSR génère une séquence périodique
• Il DOIT partir d’un état non-nul sinon … que des zéros
• La longueur maximale de la séquence est 2n-1
• La séquence tout à zéro n’est pas générée (état bloquant)
• Le polynôme caractéristique d’un LFSR générant une séquence de
longueur maximale est un polynôme primitif
• Une séquence de longueur maximale est pseudo-aléatoire:
• Nombre de ‘1’ = nombre de ‘0’ + 1
LFSR (3)
• Exemple: P(x) = x3 + x + 1
• Etat de départ : tout à ‘1’
• Le cycle complet dure 7 cycles d’horloges
• Longueur maximale = 2n-1
• P(x) est un polynôme primitif
Polynômes primitifs avec un minimum de
XORs
Scrambler (DVB-T)
Polynôme P(x) = ?
• Le premier bit généré par le LFSR doit être appliqué au premier bit du
premier octet suivant le premier octet de synchro
• La séquence d’initialisation doit être chargée dans le LFSR/PRBS tous les
8 paquets
• Durant l’envoi des 7 autres octets de synchro le LFSR doit continuer
d’évoluer mais la sortie doit être désactivée (enable=0)
13
Encodeur RS
•
•
•
•
C’est un LFSR dans un Corps de Galois
Multiplieurs de Galois
Additionneurs de Galois
Bascules D
14
Entrelacement
ThisIsAnExampleOfInterleaving...
ThisIsAnExampleOfInterleaving...
ThisIs______pleOfInterleaving...
TIEpfeaghsxlIrv.iAaenli.snmoten.
TIEpfe_____Irv.iAaenli.snmoten.
T_isI_AnE_amp_eOfInterle_vin_...
Entrelacement:
- Utilisé en complément des codes correcteurs d’erreurs
- Permet de dispercer les erreurs
- Permet de compenser en partie les effacements et évanouissement
- Augmente la latence du système
15
Entrelaceur (symboles DVB-T)
16
Codeur convolutif (DVB-T)
17
Conversion série/parallèle
18
Plan du cours 4
Systèmes de communications numériques
Fonction types d’un système de comm. num.
Codes convolutifs
Algorithme de Viterbi
Architecture du décodeur de Viterbi
19
Intérêt du codage convolutif
Code convolutif + VITERBI:
- permet de tirer parti de l’information sur la fiabilité des décisions prises
- Ramène le TEB à 10-3
- Laisse des bursts d’erreurs en sortie
20
Intérêt du codage Reed-Solomon
Code Reed-Solomon:
- Est efficace surtout quand TEB d’entrée < 10-2
- Corrige les erreurs par bursts
- Complémentaire avec les codes convolutifs
21
Code convolutif
Bit à
transmettre
0
Longueur de contrainte K=3
(1 bit à transmettre + 2 bits
d’état)
1
Etat du codeur à l’instant t
L’évolution de l’état du codeur est représenté par un treillis:
Etat (t)
Etat (t+1)
Etat (t+2)
Etat (t+3)
0 0
0 0
0 0
0 0
0 1
0 1
0 1
0 1
1 0
1 0
1 0
1 0
1 1
1 1
1 1
1 1
Bit à
transmettre à 0
Bit à
transmettre à 1
22
Code convolutif
Bit à
transmettre
0
Longueur de contrainte K=3
(1 bit à transmettre + 2 bits
d’état)
1
Etat du codeur à l’instant t
L’évolution de l’état du codeur est représenté par un treillis:
Etat (t)
Etat (t+1)
Etat (t+2)
Etat (t+3)
0 0
0 0
0 0
0 0
0 1
0 1
0 1
0 1
1 0
1 0
1 0
1 0
1 1
1 1
1 1
1 1
1
0
0
Bit à
transmettre à 0
Bit à
transmettre à 1
Chemin du bit
transmis
23
Code convolutif
X1
Bit à transmettre
0
Les sorties X1 et X2
représentent la signature
des transitions du bit à
transmettre (redondance =>
rendement 1/2)
1
X2
0 0
00
0 0
0 0
0 1
0 1
0 1
1 0
1 0
1 1
1 1
X1 X2:
00
10
11
BIT
1
0
0
1 1
10
1 0
24
Plan du cours 4
Systèmes de communications numériques
Fonction types d’un système de comm. num.
Codes convolutifs
Algorithme de Viterbi
Architecture du décodeur de Viterbi
25
Algorithmes de décodage des codes
convolutifs
• Viterbi (décision souple en entrée, dure en sortie)
• Chemin survivant optimal
• SOVA (décision souple en entrée, souple en sortie)
• Fiabilité approximative, complexité réduite
• Permet de décoder les « turbo-codes »
• Forward-Backward (décision souple en entrée, souple en
sortie)
• Fiabilité exacte des bits décodés
• +0.5dB de mieux que le SOVA
26
Décodage de Viterbi
• Le décodage consiste à retrouver le chemin parcouru par
le bit dans le treillis en utilisant une de recherche de
maximum de vraisemblance
2
2
3
3
1
2
4
3
1
1
4
4
27
Décodage de Viterbi
• A chaque nœud, la distance parcourue la plus courte est
calculée et le chemin pris est mémorisé. Il faut arriver à
destination pour en déduire le chemin le plus court =
chemin survivant
2
2
3
2
3
1
3
4
4
3
2
4
3
5
4
1
6
7
1
Chemin
survivant
28
Entrée pondérée (souple, soft)
29
Métriques de branche
Instant t
00
Instant t+1
00
00
01
01
10
10
11
10
Distance Euclidienne
Distance de Manhattan
11
30
Décodage de Viterbi
• La recherche de la séquence émise nécessite le calcul des
métriques de branches et métriques de noeuds
Métrique de branche
= Distance(Y1Y2 reçue; Y1Y2 attendu)
MNA
00
11
0
MNC
2
MNB
Y1Y2 reçu = 00
Métrique de nœud
= Min(MNA+0,MNB+2°
• A chaque nœud est associé la décision correspondant à la branche la
plus vraisemblable : décision = [(MNA+0<MNB+2)? 0, 1]
• La valeur du bit de décidé est donnée par la position de nœuds. Au
Nord, le bit est à 0, au Sud le bit est à 1.
31
Décodage de Viterbi
t=0
0
0
0
0
1
t=2
t=3
11
11
00
1
1
1
0
2
t=1
0
2
10
Exercice : Calculer les métriques de branches et métriques de nœuds note: les
nœuds sont équiprobables à t=0
32
Décodage de Viterbi
Solution:
t=0
0
0
0
0
1
1
1
1
0
2
t=1
1
0
1
0
2
10
0
2
0
0
2
1
1
t=2
0
1
1
1
11
1
1
2
0
0
2
1
1
t=3
1
2
0
1
11
1
2
0
2
2
0
1
1
1
1
2
1
1
1
00
33
Décodage de Viterbi
Exercice : Recherche la séquence émise
Il suffit de remonter le chemin à partir de la destination, en considérant les
décisions aux niveau des noeuds
T
T+1
T+2
T+3
T+4
T+5
T+6
T+7
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
1
0
1
0
0
1
1
0
1
0
0
0
0
Propriété: Les chemins convergent en remontant sur une profondeur L
suffisamment grande, L=longueur de convergence :
L=6K
K=longueur de contrainte (Nbre d’états = 2K-1)
34
Décodage de Viterbi
Solution :
T
T+1
T+2
T+3
T+4
T+5
T+6
T+7
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
1
0
1
0
0
1
1
0
1
0
0
0
0
0
0
1
1
0
1
1
1
?
35
Plan du cours 4
Systèmes de communications numériques
Fonction types d’un système de comm. num.
Codes convolutifs
Algorithme de Viterbi
Architecture du décodeur de Viterbi
36
Architecture du décodeur
Symboles
d’entrée
Bits
décodés
Métriques de
branches
Métriques de
noeuds
Gestion du
chemin survivant
Points critiques:
Puissance de calcul pour les métriques de nœuds
Accroissement infini des métriques de nœuds
Gestion de la mémoire survivante
37
Calcul des métriques de branches
(distance Euclidienne)
𝑀𝐵00 = 𝑑 𝑌1𝑌2,00 = 𝑌12 + 𝑌22
𝑀𝐵01 = 𝑑 𝑌1𝑌2,01 =
𝑌12 + (𝑌𝑀𝐴𝑋 − 𝑌2)2
𝑀𝐵10 = 𝑑 𝑌1𝑌2,10 =
(𝑌𝑀𝐴𝑋 − 𝑌1)2 + 𝑌22
𝑀𝐵11 = 𝑑 𝑌1𝑌2,11 =
(𝑌𝑀𝐴𝑋 − 𝑌1)2 + (𝑌𝑀𝐴𝑋 − 𝑌2)2
Multiplieurs (mise au carrée)
Additionneurs/Soustracteurs
Opérateur SQRT
38
Calcul des métriques de branches
(distance de Manhattan)
𝑀𝐵00 = 𝑑 𝑌1𝑌2,00 = 𝑌1 + 𝑌2
𝑀𝐵01 = 𝑑 𝑌1𝑌2,01 = 𝑌1 + (𝑌𝑀𝐴𝑋 − 𝑌2)
𝑀𝐵10 = 𝑑 𝑌1𝑌2,10 = (𝑌𝑀𝐴𝑋 − 𝑌1) + 𝑌2
𝑀𝐵11 = 𝑑 𝑌1𝑌2,11 = (𝑌𝑀𝐴𝑋 − 𝑌1) + (𝑌𝑀𝐴𝑋 − 𝑌2)
Additionneurs uniquement !
Performances de décodage équivalentes
39
Calcul des métriques de noeuds
Métrique de nœud = Min(MNA+MBA,MNB+MBB)
Instant t
MN0
Instant t+1
MB00
MN0
MN1
MN1
MN2
MN2
MN3
MB33
Si K=7 (64 états)
Débit 30Mb/s
MN3
2 Additionneurs
1 Comparateurs
1 Sélecteur (MUX)
Opérateur
ACS
MN3=Min(MN2+MB23; MN3+MB33)
6 G additions/s !!
40
Opérateurs ACS
MNA
Additionneurs
Comparateur
+
MBAC
MNB
+
MBBC
MNC
Sélectionneur
41
Interconnection des ACS
MN0
Reg
ACS1
Reg
ACS2
Reg
ACS3
Reg
MN0
MN1
MN1
MN2
MN2
MN3
ACS0
MN3
42
Dynamique des métriques de noeuds
X ≤ MN ≤ X + 3M
X ≤ MN ≤ X+2M
X ≤ MN ≤ X+M
X ≤ MN ≤ X + 3M
X ≤ MN ≤ X + 3M
X ≤ MN ≤ X+2M
X ≤ MN ≤ X + 3M
X ≤ MN ≤ X + 3M
X ≤ MN ≤ X+2M
X
X ≤ MN ≤ X + 3M
X ≤ MN ≤ X + 3M
X ≤ MN ≤ X+M
X ≤ MN ≤ X+2M
X ≤ MN ≤ X + 3M
A tout instant t, Max-Min ≤ (K-1)M
43
Rééchelonnage
Exemple: M=15 => Max-Min=45
La métrique de nœud est codée sur 7 bits. Quand les
MSBs sont à 1 ils sont tous remis à 0 (rééchelonnage)
128
45 max
64
0
La fréquence de rééchelonnage donne une information sur le niveau
de bruit du canal.
44
Gestion du chemin survivant
Après une remontée sur une longueur L (typiquement 6xK), le chemin
parcouru devient indépendant du nœud initial: c’est le chemin survivant
t=L
Bit 0
Bit 1
t=L+1
Bit 2
t=L+2
45
Echange de registres
• L’idée est de mémoriser les chemins survivants dans des
bancs de registres.
• Chaque registre a une profondeur de L.
• On dispose d’un registre par état.
• Le registre Ri contient le chemin survivant partant du
nœud i
46
Echange de registres
• L’idée est de mémoriser les chemins survivants dans des
bancs de registres.
• Chaque registre a une profondeur de L.
• On dispose d’un registre par état.
• Le registre Ri contient le chemin survivant partant du
nœud i
t-4
t-3
t-2
t-1
t
H
H
H
H
B
H
H
H
B
H
H
H
H
B
H
H
H
H
B
H
Chemin survivant partant du
nœud 0
47
Echange de registres
• L’idée est de mémoriser les chemins survivants dans des
bancs de registres.
• Chaque registre a une profondeur de L.
• On dispose d’un registre par état.
• Le registre Ri contient le chemin survivant partant du
nœud i
t-5
t-4
t-3
t-2
t-1
t
B : R0 <= R1
H : R1 <= R2
H : R2 <= R0
B : R3 <= R3
H
H
H
H
B
H
H
H
B
H
H
H
H
B
H
H
H
H
B
H
48
Echange de registres - Architecture
If d0=0 R0<=R0 Else R0 <= R1
If d1=0 R1<=R2 Else R1 <= R3
If d2=0 R2<=R0 Else R2 <= R1
If d3=0 R3<=R2 Else R3 <= R3
Résultats
identiques
0
1
1
0
1
0
0
0
1
0
0
1
1
0
1
0
1
1
1
1
Inconvénients: nombre de registres, interconnexions, consommations
Si L=100, K=7, il faut 6400 registres !
L’échange de registre est utilisé avec peu d’états (<32)
49

Download Report