Upload
trinhliem
View
229
Download
1
Embed Size (px)
Citation preview
Timisoara 18-20 mars 2003
ENST Bretagne 1
Turbo Turbo ccodesodes((convolutifsconvolutifs))
Timisoara18-20 mars, 2003
Michel Jézéquel,
Claude Berrou et Catherine Douillard ENST Bretagne
Plan
1. Les codes correcteurs d’erreurs 1. Généralités2. Limites Théoriques
2. Les codes convolutifs1. Les codes classiques2. Les codes RSC3. Poinçonnage et terminaison
3. Les algorithmes SISO1. SOVA2. MAP3. SUB-MAP
4. Turbo codes• La philosophie• Les différents schémas• Turbo décodage
5. Permutation• Régulière• Aléatoire • Pseudo-aléatoire
6. Turbo codes duo-binaires• Principe et avantages• Performance
7. Conclusions et perspectives
Timisoara 18-20 mars 2003
ENST Bretagne 2
Chapitre 1
Les codes correcteurs d’erreurs
Sourcenumérique Codage
Modulation et filtrage
Milieude
transmission
Filtrage etdémodulation
DécodageDestinataire
Canal de transmission
Di
Di
Une chaîne de transmission
Timisoara 18-20 mars 2003
ENST Bretagne 3
Codes correcteur d’erreurs Généralités
Codage de source : réduire le débit d’informationCodage de canal : ajouter de la redondanceSécurité, cryptographieAuthentification, watermarkingCDMA...
Différentes familles de codage
Codes correcteur d’erreurs GénéralitésSéquence d’information à transmettre : [d1 d2 ... di ... dk]
Addition d’une redondance linéaire : [r1 r2 ... rj ... rn-k](le code est dit systématique)
2mod ...1
, dprki
ijij ∑=
= (pi,j = 0 ou 1)
[r1 r2 ... rj ... rn-k] = [d1 d2 ... di ... dk]
p1,1
pk,1
p1,n-k
pk,n-k
Forme matricielle
Timisoara 18-20 mars 2003
ENST Bretagne 4
Rendement de codage : R =k/n
Code (n , k , dmin) de distance minimale dmin
Codes correcteur d’erreurs Généralités
Le code étant linéaire, la séquence « tout zéro » peut être prise comme référence
La distance dmin est le nombre minimum de « 1 » des mots de code [d1 d2 ... di ... dk] [r1 r2 ... rj ... rn-k]si [d1 d2 ... di ... dk] ≠ « tout zéro »
[d1 d2 ... di ... dk][r1 r2 ... rj ... rn-k] : mot de code
Un bon code est un code avec une grande distance dminmais ce n’est pas tout :• il doit pouvoir être décodé !
(contre-exemple : les codes aléatoires)• il doit exister un décodeur permettant d’utiliser
la capacité de correction du code
Exemple :
Codes correcteur d’erreurs Généralités
Timisoara 18-20 mars 2003
ENST Bretagne 5
5
5
5
5
5
5
5
5
10-1
10-3
10-4
10-6
10-7
10-8
20 1 3 4 5 6 7 8 9 10 11 12
Eb/N0 (dB)
TEB
non codé
mauvaise convergence, gain asymptotique élevé
Bonne convergence, faible gain asymptotique
10-2
10-5
Limite théorique(R=1/2, 188 octets)
MDP4, canal gaussien, taux d’erreurs cible : 10-8
Ga = 10 log (R.dmin)
dmin > 25
∫∞
=−=
xt
b
dttxerfc
avecNEerfc
)exp(2)(
)(21
2
0
π
distinction traditionnelle mais inappropriée entre
Les codes en « bloc » : Hamming, Golay, BCH, Reed-Solomon, ...
Les codes « convolutifs »
Une distinction plus naturelle prendrait en compte l’algorithmede décodage, en particulier :• hard – dur (algébrique)• soft – souple (probabiliste)
Exemple :
Codes correcteur d’erreurs Généralités
Timisoara 18-20 mars 2003
ENST Bretagne 6
di Hamming étendu
Yi di Hamming étendu
Yi
0000 0000 0000 1111 1111 11110001 0111 1011 1110 1000 01000010 1101 0111 1101 0010 10000011 1010 1100 1100 0101 00110100 1110 1110 1011 0001 00010101 1001 0101 1010 0110 10100110 0011 1001 1001 1100 01100111 0100 0010 1000 1011 1101
000001010011100101110111
di
(donnée)
Xi
s3s2s1
Yi
Etat
X=0, Y=0X=0, Y=1X=1, Y=0X=1, Y=1
Comment transformer un code de Hamming parfait (8,4,4)
(autre exemple : le code de Golay étendu (24, 12, 8) peut être représenté par un treillis circulaire 16 états)
Codes correcteur d’erreurs Généralités
Codes correcteur d’erreurs GénéralitésCode aléatoire (Shannon)
1 .... i ... kInformation Redondance
1 .... j ... n- k10000000 ... 0000000000000001000000 ... 0000000000000000100000 ... 000000000000001111010001...0001111011
00000000 ... 00000000000001
0010010111...01100001001001110100...0011101001
1010101110...1010111101.............
10010110 ... 100011000101010011101011...1110010100
Σ
dmin ≈ (n-k)/4 = k.(1-R)/4R où R = k/n
Timisoara 18-20 mars 2003
ENST Bretagne 7
Codes correcteur d’erreurs Généralités
dmin ≈ (n-k)/4 = k.(1-R)/4R où R = k/n
Exemple : k = 1504 (MPEG), R = 1/2dmin ≈ 375 !!
(un code convolutif 64 états a une distance dmin = 10 pour R = 1/2 !!)
Mais non décodable en pratique ...
Codes correcteur d’erreurs Généralités
extensionde la bande (dB)0 1 2 3
Limite (Eb/N0, dB) (k infini) [Shannon, Proakis]
0
1
2
3
canalcontinu
canalà entréebinaire
R=1/2R=2/3R=3/4R=4/5R=5/6
(sur la base d’un code aléatoire)
Timisoara 18-20 mars 2003
ENST Bretagne 8
Taille du bloc (k)
∆ Eb/N0 (dB)
1
2
3
4
5
100 101 102 103 104 105
(taux d’erreurs paquets = 10-4)
Correction à prendre en compte pour des bocks de taille k :[S. Dolinar, D. Divsalar and F. Pollara, "Code performance as afunction of block size", TMO progress report 42-133, JPL, NASA].
Codes correcteur d’erreurs Généralités
Calcul des limites
Un outil de calcul des limites théoriques a été développé par un étudiant en thèse il est disponible à l’adresse :http://www-elec.enst-bretagne.fr/~emaury/Capa_UI.html
Timisoara 18-20 mars 2003
ENST Bretagne 9
Chapitre 2
Codes convolutifs
Plan
• Codes convolutifs classiques– Représentations– Propriétés
• Codes convolutifs systématiques• Codes convolutifs récursifs systématiques• Rendement de codage et poinçonnage• Fermeture de treillis
Timisoara 18-20 mars 2003
ENST Bretagne 10
Codes convolutifs
b bits
d’information1 2 3 K=m+1
Registre à décalage (mb étages)
fonctions linéairesmot de code n symboles
K= longueur de contrainte
R=b/n (rendement de codage)
b b
di di-1 di-2D D
xi
yi
di di-1 di-2D D
yi
Elias, 1954
Forney, 1970
Mémoire du code : ν = 2
Longueur de contrainte :K = ν + 1 = 3
R = 1/2
Code convolutif classique
Timisoara 18-20 mars 2003
ENST Bretagne 11
Exemple
D Ddi di-1 di-2
xi
yi
• K=3
• b=1
• n=2
•R=b/n=1/2
Exemple
state 0 0 2 1 0 0 2 3 1 0 0 0 0 0
D Ddi di-1 di-2
di
xi
yi
xi
yi
Timisoara 18-20 mars 2003
ENST Bretagne 12
Générateurs
D Ddi di-1 di-2
∑=
−=2
0
1
jjiji dgx
∑=
−=2
0
2
jjiji dgy
[ ] [ ]1,0,1,, 12
11
10
1 == gggg ( ) 212
11
10
1 DgDggDG ++=
[ ] [ ]1,1,1,, 22
21
20
2 == gggg ( ) 222
21
20
2 DgDggDG ++=
Générateurs sous la forme octale : (5,7)
Représentation des codes convolutifs
• arbre• machine d’état• treillis
Trois formes :
Timisoara 18-20 mars 2003
ENST Bretagne 13
arbreD D
00
11
0
110
01 1100
00 00
11110110
1001
di di-1 di-2
xi
yixi yi
Machine d’états
D Ddi =0
di =1
00
01
10
1100
11 10
01
11
0001
10
xi yi
xi yi
di di-1 di-2
xi
yi
Timisoara 18-20 mars 2003
ENST Bretagne 14
TreillisD D
00
01
10
11
0011 11
011010
0001
0011 11
011010
0001
0011 11
011010
0001
0011
10
01
0011
di =0
di =1
xi yi
xi yi
di di-1 di-2
xi
yi
Treillis
D Ddi di-1 di-2
xi
yi
00
01
10
11
0011 11
011010
0001
di =0 xi yi
di =1 xi yi
Timisoara 18-20 mars 2003
ENST Bretagne 15
Distance
00
11 11
011010
00
01
00
11 11
011010
00
01
00
11 11
011010
00
01
00
11
10
01
00
1100
01
10
11
00
11
01
11
00 00 00
Distance de Hamming 0 0212+ ++ + + 0 =5
(K=3) (5,7) -> distance libre = dlibre=5(K=3) (5,7)
Poids=P=1
Distance
00
11 11
011010
00
01
00
11 11
011010
00
01
00
11 11
011010
00
01
00
11
10
01
00
1100
01
10
11
00
11
01
11
00 00 00
Distance de Hamming 0 2112+ ++ + + 0 =6
(K=3) (5,7) -> distance libre = dlibre=5
11
1010
11
00 00
Poids =P=2
Timisoara 18-20 mars 2003
ENST Bretagne 16
Poids =P=2+2=4Poids =P=2
Distance
00
11 11
011010
00
01
00
11 11
011010
00
01
00
11 11
011010
00
01
00
11
10
01
00
1100
01
10
11
00
11
01
11
00 00 00
Distance de Hamming 0 1012+ ++ + + 2 =6
(K=3) (5,7) -> distance libre = dlibre=5
11
1010
11
00 00
1111
00
0101
00
Distance
• Longueur de contrainte : K = 3• Générateurs (5,7)
– Distance libre minimale = 5 – Spectre des distances:
• Distance = 5 (1 cas), P=1• Distance = 6 (2 cas), P=4• Distance = 7 (4 cas), P=12• ….
Timisoara 18-20 mars 2003
ENST Bretagne 17
Codes systématiques
xi
D Ddi
yi
xi=di
NSC(Non Systematic Convolutional)
D Ddi
yiSC
(Systematic Convolutional)
Exemple : K=3, b=1, n=2, R=b/n=1/2
Codes systématiques(machine d’états)
xi
D Ddi
yi
xi=di
NSC
D Ddi
yiSC
10
00
01
1100 11 10
0111
0001
1000
01
10
1100 11 10
0101
1011
00
di =0 xi yi
di =1 xi yi
Timisoara 18-20 mars 2003
ENST Bretagne 18
Codes systématiques (treillis)
D D
NSC
D D
SC
di =0
di =1
00
01
10
11
0011 11
011010
0001
00
01
10
11
0011 01
011000
1001
xi
di
yi
xi=di
di
yi
xi yi
xi yi
Codes systématiques(distance)0000
01
10
11
00
11
01
11
00 00
Distance libre minimale
0 0212+ ++ + =5NSC
0 0112+ ++ + =4SC
01
01
11
00 00
11
00
1000
01
0 1012+ ++ + =4
Poids=P=1+2=3Poids=P=1
Timisoara 18-20 mars 2003
ENST Bretagne 19
Spectre des distances
4486400d=111923220134d=10801600d=93285813d=812400d=742155d=6
51205122052233d=14230425600d=13102412865589d=12
1100d=50032d=4P NSCnP SCn
n = nombre de cas
P = poids
Codes systématiques (Taux d’Erreurs Binaire)
1,E-08
1,E-07
1,E-06
1,E-05
1,E-04
1,E-03
1,E-02
1,E-01
1,E+00
0 2 4 6 8 10 12
Non codéSCNSC
Eb/N0
TEB
Timisoara 18-20 mars 2003
ENST Bretagne 20
Interprétation des résultats
Codes convolutifs
Existe-t-il un code convolutif combinant :
• les distances minimales des codes non systématiques• le bon comportement à faible rapport signal/bruit
????
La réponse est : OUI
Timisoara 18-20 mars 2003
ENST Bretagne 21
Codes récursifs systématiques
di
xi
D D
yiNSC
Exemple:K=3, b=1, n=2, R=b/n=1/2
D Ddi
yi
xi
[1,(1+D+D2)/(1+D2)]
D Ddi
yi
xi
[1,(1+D2)/(1+D+D2)]
[(1+D2),(1+D+D2)]
Codes récursifs systématiques (treillis)
xi
D Ddi
yiNSC RSC
di =0 xi yi
di =1 xi yi
00
01
10
11
0011 11
011010
0001
D Ddi
yi
xi
00
01
10
11
0011
10
01
11
00
01
10
Timisoara 18-20 mars 2003
ENST Bretagne 22
Codes Récursifs systématiques(machine d’états)
xi
D Ddi
yiNSC RSC
10
00
01
1100 11 10
0111
0001
1000
01
10
1100 11 10
0111
0001
10
di =0 xi yi
di =1 xi yi
D Ddi
yi
xi
Codes récursifs systématiques(distance)00
11
Distance libre minimale =5RSC
00
11
10
01
00
11 11
101001
00
01
00
11 11
101001
00
01
00
01
10
11
00
2+
11
2+
11
0+
00
0
00
1+
01
Poids=P=2
Timisoara 18-20 mars 2003
ENST Bretagne 23
Spectre des distances
76801024112641024d=155122561286432168421n
3584166476835216072321462P RSC
44864d=1119232d=108016d=9328d=8124d=742d=6
5120512d=142304256d=131024128d=12
11d=5P NSCn
n = nombre de cas
P = poids
Codes récursifs systématiques (Taux d’Erreurs Binaires)
1,E-08
1,E-07
1,E-06
1,E-05
1,E-04
1,E-03
1,E-02
1,E-01
1,E+00
0 2 4 6 8 10 12
Non codéSCNSCRSC
Eb/N0
TEB
Timisoara 18-20 mars 2003
ENST Bretagne 24
Rendement de codage et poinçonnage
D Ddi
yi
Multiplexage &Poinçonnage
Sortie
R=1/2 xi yi xi+1 yi+1 xi+2 yi+2 xi+3 yi+3 xi+4 yi+4
R=2/3 yi+5 xi+6xi xi+1 yi+1 xi+2 xi+3 yi+3 xi+4 xi+5
R=3/4 xi xi+1 xi+2 yi+2 xi+3 xi+4 xi+5 yi+5 xi+6 xi+7
R=3/5 xi xi+1 yi+1 xi+2 yi+2 xi+3 xi+4 yi+4 xi+5 yi+5
xi
Codes poinçonnés (Taux d’Erreurs Binaire)
1,E-08
1,E-07
1,E-06
1,E-05
1,E-04
1,E-03
1,E-02
1,E-01
1,E+00
0 2 4 6 8 10 12
Non codéNSCRSC
Eb/N0
TEB Rendement de codage =3/4
Timisoara 18-20 mars 2003
ENST Bretagne 25
1 2 ν
d X
Y
Générateurpseudoaléatoire
R = 1/2 R = 2/3 R = 3/4 R = 4/5
R = 5/6 R = 6/7 R = 7/8
-0.2 0.2 0.6
0.03
0.07
0.06
0.04
0.05
0.020.8 1.2 1.6
0.021.6 2.0 2.4
0.03
0.07
0.06
0.04
0.05
0.02
0.06
0.05
0.03
0.04
0.011.2 1.6 2.0
= 2 = 4
= 6
0.02
0.06
0.05
0.03
0.04
0.01
0.02
0.06
0.05
0.03
0.04
0.01
0.01
0.05
0.04
0.02
0.03
0.001.6 2.0 2.4 1.8 2.2 2.6 2.2 2.6 3.0
= 8
Limite de Shannon(canal gaussien entrée binaire)
ν ν
ν ν
0.05
0.09
0.08
0.06
0.07
0.04
TEBE /Nb 0
Plus le registreest grand, meilleur est le code convolutif
Fermeture de treillisdi =0
di =1
00
01
10
11
01
10
110 1 2 3 n-1 n
Bloc de k bits, 2k bits transmis → R=1/2
00
Initialisation
0 0D Ddi
yi
xi
Timisoara 18-20 mars 2003
ENST Bretagne 26
Fermeture de treillisdi =0
di =1
00
01
10
1100
01
10
110 1 2 3 n-1 n
Bloc de k bits, 2k+K-1 bits transmis → R=k/(2k+K-1)
Initialisation
0 0
Transmission de l’état final
(K-1 bits)
D Ddi
yi
xi
Fermeture de treillis
00
01
10
110 1 2 3 n-1 n
Initialisation
0 0Insertion
detail bits
00
D Ddi
yi
xi
Bloc de k bits, 2k+2(K-1) bits transmis → R=k/2(k+K-1)
0D Ddi
yi
xi
Timisoara 18-20 mars 2003
ENST Bretagne 27
D DD
000001010011100101110111
yi
di
Codes convolutifs circulaires
0 1 1 1 1 10 0
D DD
000001010011100101110111
yi
di
Codes convolutifs circulaires
Timisoara 18-20 mars 2003
ENST Bretagne 28
Calcul de l’état circulation
s1 s3s2AB
11. −− += iii XSGS
S X Gi
i
i
i
i
i i
i
i
sss
A BBB
=
=+
=
1
2
3
1 0 11 0 00 1 0
,
,
,
; ;
Mod 2 (1)
La période L du générateur est telle que (Identité)
En partant de (1), nous pouvons en déduire :
G IL =
11. −− += iii XSGS
221 . −−− += iii XSGS
001 . XSGS +=
Après codage d’une séquence de longueur k :
∑=
−−+=
kpp
pkkk
...110. XGSGS (2)
Si est inversible, il existe un tel que . est appelé état de circulation.
S S Sc k= = 0Sc
Sc
∑=
−−
+=kp
pk-pk
c...1
11
. XGGIS (3)
kGI +
Timisoara 18-20 mars 2003
ENST Bretagne 29
En pratique :
Le codeur est initialisé à ; la séquence de longueur k est codée donnant, d’après (2) :
(3) devient :
(4)
La correspondance entre est mémorisée dans une petite fonction combinatoire (3 bits en entrée, 3 bits en sortie).
S 00 =
∑=
−−=
kpp
pkk
...11
0 XGS
S I G Sck
k= +−1 0.
0et kSS
000001010011100101110111
Codes convolutifs circulaires
0 1 1 1 1 10 0
- Codage de la séquence d’information- Détermination de l’état de circulation
• Pré-codage :
• Initialisation à l’état de circulation• Codage
- Initialisation à l’état tout zéro
000
010
Timisoara 18-20 mars 2003
ENST Bretagne 30
Prologue
Codes convolutifs circulaires (comment décoder ?)
Fermeture de treillis
• “tail bits” rendement de codage
☺ facile à implémenter
• codes circulaires (“tail biting” NSC)pré-codage
☺ rendement de codage
Timisoara 18-20 mars 2003
ENST Bretagne 31
Chapitre 3
Algorithmes de décodage à entrée et sortie pondérées ou
SISO (Soft-In Soft-Out)
Codes convolutifs algorithmes SISO
Le turbo-décodage utilise des décodeurs élémentaires à entrées et sorties pondérées.
Deux familles d’algorithmes de décodage SISO pour les codes convolutifs :
• Les algorithmes basés sur l’algorithme deViterbi
• L’algorithme MAP (Maximum A Posteriori) et ses approximations
Timisoara 18-20 mars 2003
ENST Bretagne 32
Illustration avec le code suivant :
D Did
iX
iY
00 (0)
01 (1)
10 (2)
11 (3)
00 (0)
01 (1)
10 (2)
11 (3)
0=id1=id
i-1 i
Codes convolutifs algorithmes SISO
Modèle de la chaîne de transmission
Les symboles transmis Xi et Yi, i = 1…k prennent leurs valeurs dans {-1,+1}
Codeurconvolutif
Canalgaussien
decodeurSISO{ }kdd ,,1 L
{ }kXX ,,1 L
{ }kYY ,,1 L
{ }kxx ,,1 L
{ }kyy ,,1 L{ }kdd ˆ,,1̂ L
source destinataire
k1c k
1r
),( avec } ,,{ 11 iiikk YXccc == Lc
: séquence codée et modulée (MDP2)k1c
k1r : séquence bruitée reçue
),,( avec } ,,{ 11 iiikk yxrrr == Lr y
iiixiii nYynXx +=+= ,
Codes convolutifs algorithmes SISO
Timisoara 18-20 mars 2003
ENST Bretagne 33
Application de l’algorithme de Viterbi
Codes convolutifs algorithmes SISO : SOVA
• L’algorithme de Viterbi est utilisé pour chercher le chemin à vraisemblance maximale dans le diagramme en treillis.
• Critère de décodage : maximiser }{Pr 11kk|CR
( ) ( )
σ−−
σ−−∏
σπ=
∏=
=
=
2
2
2
22
1
111
2exp
2exp
21
}{Pr}{Pr
iiiik
i
k
iii
kk
YyXx
C|R|CR
• Maximiser minimiser }{Pr 11kk|CR [ ]∑ −+−
=
k
iiiii YyXx
1
22 )()(
22 )()( iiiii YyXxL −+−=x
xxxxii
i
jji LMLM +=∑= −
=1
1
• Calcul (récursif) de la métrique de chemin associée au chemin x.
xiM
• A chaque instant i, calcul de la métrique de branche associée à chaque chemin x dans le treillis, c-a-d de la distance euclidienne entre le symbole reçu ri et le symbole codé ci associé au chemin x.
xiL
Application de l’algorithme de Viterbi
Codes convolutifs algorithmes SISO : SOVA
Timisoara 18-20 mars 2003
ENST Bretagne 34
0
1
2
3
0
1
2
3
di = 0di = 1
i-1 i
(-1,-1)
(1,1)
(1,-1)
(-1,1)
(-1,-1)
(1,1)
(-1,1)
(1,-1)
(Xi, Yi)
Exemple22, )1()1( +++== iiii yxLL 00x
x00x1
22, )1()1( −++++== iiiii MyxMM
x
22, )1()1( ++−== iiii yxLL 12xx12x
122, )1()1( −+++−== iiiii MyxMM
x
Codes convolutifs algorithmes SISO : SOVA
Application de l’algorithme de Viterbi
• Pour chaque nœud s, recherche du chemin à métrique minimale (le survivant) et mémorisation de la métrique associée avec la valeur de di.
)(ssiM
0
1
2
3
0
1
2
3
i-1 i
(-1,-1)
(1,1)
(1,-1)
(-1,1)
(-1,-1)
(1,1)
(-1,1)
(1,-1)
(Xi, Yi)
01,iM
00,iM )(0s
iM⇒0
13,iM
12,iM )(1s
iM⇒121,
iM20,
iM)(2s
iM⇒2
32,iM
33,iM
)(3siM⇒3
Application de l’algorithme de Viterbi
Codes convolutifs algorithmes SISO : SOVA
Timisoara 18-20 mars 2003
ENST Bretagne 35
0
1
2
3i1−i2−i2−− Li1−− LiLi −
))((min)(,...,
s230s
si
si MM
==
• A l’instant i-L, la décision est la valeur binaire stockée dans le nœud appartenant au chemin survivant.
Lid −ˆ
Lid −ˆ
• A l’instant i, sélection du nœud à métrique minimale,
chemin survivant
Application de l’algorithme de Viterbi
Codes convolutifs algorithmes SISO : SOVA
• Remontée le long du chemin survivant (pour profiter du futur).
• L’algorithme de Viterbi ne peut pas être utilisé pour le décodage itératif !
Il produit des décisions binaires
Il doit être modifié pour produire des décisions pondérées=> SOVA (Soft-Output Viterbi Algorithm)
Codes convolutifs algorithmes SISO : SOVA
Timisoara 18-20 mars 2003
ENST Bretagne 36
0)()()( ≥−=∆= sss si
ciii MMMw
• Une première estimation de la fiabilité ou du poids de la décision peut être donnée par la différence entre les métriques du chemin survivant et de l’autre chemin ( le chemin concurrent):
• Mais cette estimation doit être affinée! => algorithmes de révision des poids
0)(Si 1 >>∆ − 1iM0)(et =∆ 2iM
=> le poids à l’instant i-1 doit être revu à la baisse
0
1
2
32−− Li1−− LiLi − i1−i2−i
survivant concurrent
Codes convolutifs algorithmes SISO : SOVA
• Encore appelé algorithme BCJR (Bahl, Cocke, Jelinek, Raviv), algorithme APP (A Posteriori Probability), ou algorithme Aller-Retour (Backward-Forward)
• But de l’algorithme : calcul du Logarithme de Rapport de Vraisemblance (LRV) relative à la donnée di
L’algorithme MAP (Maximum A Posteriori)
}0{Pr
}1{Prln)(
1
1k
i
ki
id
dd
r
r
=
==Λ
k1r désigne la séquence bruitée reçue
),( avec } ,,{ 11 iiikk yxrrr == Lr
signe ⇒ décision binairevaleur absolue ⇒ fiabilité
Codes convolutifs algorithmes SISO : MAP
Timisoara 18-20 mars 2003
ENST Bretagne 37
},,{Pr 11k
ii rsSsS =′=−
iS : état du codeur à l’instant i
0
1
2
3
0
1
2
3i-1 i
∑
∑
∈′−
∈′−
=′=
=′=
=Λ
0
1
),(11
),(11
},,{Pr
},,{Pr
ln)(
i
i
T
kii
T
kii
id
ss
ss
rsSsS
rsSsS
=>
1,0}{Pr
},,{Pr
}{Pr1
),(11
1 =
=′=
==∑
∈′−
jjd kT
kii
ki
ji
r
rsSsS
r ss
• Chaque APP (A Posteriori Probability) est estimée par le biais des probabilités conjointes
}{Pr 1k
i jd r=
jiT : ensemble des transitions du treillis
associées à di = j
Codes convolutifs algorithmes SISO : MAP
• Principe de l’algorithme MAP : traiter séparément les données relatives aux instants compris entre 1 et i et celles relatives aux instants compris entre i +1 et k.
=> Introduction des probabilités « aller » (forward) et « retour » (backward)
relatives aux états du treilliskii L1),( =α s kii L1),( =β s
}{Pr)( 1 sSrs ==β + ikii
},{Pr)( 1i
ii rsSs ==α
=> et des probabilités relatives aux transitions du treillis
Codes convolutifs algorithmes SISO : MAP
},{Pr),( 1 sSsSss ′===′γ −iiii r
Timisoara 18-20 mars 2003
ENST Bretagne 38
• On peut montrer que
=>∑
∑
∈′−
∈′−
β′γ′α
β′γ′α
=Λ0
1
),(1
),(1
)(),()(
)(),()(
ln)(
i
i
Tiii
Tiii
id
ss
ss
ssss
ssss
)(),()(},,{Pr 111 ssssrsSsS iiik
ii β′γ′α==′= −−
Codes convolutifs algorithmes SISO : MAP
Exemple 0
1
2
3
0
1
2
3
0=id1=id
i-1 i
L)(),()()(),()()(),()()(),()(ln)(
11
111133000011220011
iiiiii
iiiiiiid
βγα+βγαβγα+βγα=Λ
−−
−−
)(),()()(),()()(),()()(),()(
11
113322221133332200
iiiiii
iiiiiiβγα+βγα+βγα+βγα+
−−
−−L
)(),()(},,{Pr 111 2211r2S1S iiik
ii βγα=== −−** )(),()(},,{Pr 111 2200r2S0S iii
kii βγα=== −−
Codes convolutifs algorithmes SISO : MAP
Timisoara 18-20 mars 2003
ENST Bretagne 39
• Récursion aller : calcul de )(siα
Initialisation: si s0 est l’état initial du codeur
00
00
0)(1)(
ssss
≠∀=α=α
∑−
=
ν
α
α=α′12
0')'(
)()(
ss
ss
i
ii
NB: pour éviter les problèmes de précision, peut être normalisé à chaque étape de calcul ( est un rapport)
)(siα)( idΛ
∑−
=′−
ν
′γ′α=α12
01 ),()()(
sssss iii (ν = mémoire du code)
Codes convolutifs algorithmes SISO : MAP
)0(iα
)1(iα
)2(1+iα
)3(1−iα
)1(1−iα
)0(1−iα
)2(1−iα
0
1
2
3
0
1
2
3
0ou 1 =+ii dd1ou 1 =+ii dd
1−i 1+ii
Exemple:(sans normalisation)
* ),()(),()()( 11 1221331 iiiii γα+γα=α −−
),()(),()()( 11 0110000 iiiii γα+γα=α −−*
),()(),()()( 111 2002112 +++ γα+γα=α iiiii*
Codes convolutifs algorithmes SISO : MAP
Timisoara 18-20 mars 2003
ENST Bretagne 40
∑−
=++
ν
′γβ=′β12
011 ),()()(
sssss iii
• Récursion retour : calcul de )(s′βi
kkkk ssss ≠∀=β=β 0)(,1)(
Si l’état final est inconnu :
ss ∀=β ν21)(k
Normalisation:
∑−
=′
ν
β
β=β′12
0)'(
)()(
ss
ss
i
ii
Initialisation : si sk est l’état final du codeur
Codes convolutifs algorithmes SISO : MAP
)1(1−βi
0
1
2
3
0
1
2
3
0ou 1 =+ii dd1ou 1 =+ii dd
1−i 1+ii
)0(iβ
)2(iβ
)0(1+βi
)1(1+βi
)2(1+βi
)3(1+βi
Exemple:(sans normalisation)
* ),()(),()()( 1111 1213232 ++++ γβ+γβ=β iiiii
),()(),()()( 1111 2020000 ++++ γβ+γβ=β iiiii*
),()(),()()(1 0102121 iiiii γβ+γβ=β −*
Codes convolutifs algorithmes SISO : MAP
Timisoara 18-20 mars 2003
ENST Bretagne 41
• Calcul des probabilités de branches ),( ss′γi
S’il n’y a pas de transition entre s' et s dans le treillis.
sinon
si di = j est le bit d’information et ci le symbole codé et modulé correspondant à la transition s' → s du treillis et ri est le symbole reçu, à l’instant i .
Pour une transmission sur canal gaussien :
−−= 2
2
2 2exp
21}{Pr
σπσii
ii
crcr
σ2 : variance du bruit sur le canal
Codes convolutifs algorithmes SISO : MAP
0),( =′γ ssi
}{Prj}{Pr),( iiii crd ==′γ ss
σ−−
σ−−
πσ=′γ 2
2
2
2
2 2)(exp
2)(exp
41),( iiii
iYyXxss
Ν. Β. Λ(di) étant un rapport, K peut être omis dans les expressions de αi(s) et βi(s).
211}{Pr0}{Pret ),( ),,( Si ====== iiiiiiii ddyxrYXc
• Calcul des probabilités de branches ),( ss′γi
Codes convolutifs algorithmes SISO : MAP
)1,1(expexp),(
)1,1(expexp),(
)1,1(expexp),(
)1,1(expexp),(
22
22
22
22
+=+=
σ−
σ−=′γ
−=+=
σ
σ−=′γ
+=−=
σ−
σ
=′γ
−=−=
σ
σ
=′γ
iiii
i
iiii
i
iiii
i
iiii
i
YXyxK
YXyxK
YXyxK
YXyxK
ss
ss
ss
ss
Timisoara 18-20 mars 2003
ENST Bretagne 42
Solution 1: Log-MAP
Le terme est pré-calculé et stocké dans une table)1ln( bae −−+
Multiplications => additions Les exponentielles dans les probas de branches s’éliminentAdditions => ?
L’algorithme MAP dans le domaine logarithmique (Log-MAP)
☺ Performance MAPConnaissance de σ requise
)1ln(),max()ln( baba ebaee −−++=+
Codes convolutifs algorithmes SISO : Log-MAP et Sub-MAP
Performance < MAP (qqes dixièmes de dB)☺ Estimation de σ inutile
Solution 2: Sub-MAP (Max-Log-MAP)
),max()ln( baee ba ≈+
⇒ Algorithme « Dual Viterbi »
L’algorithme MAP dans le domaine logarithmique (Sub-MAP)
Codes convolutifs algorithmes SISO : Sub-MAP
Timisoara 18-20 mars 2003
ENST Bretagne 43
• Reformulation de Λ(di)
∑∑∈′
−∈′
− β′γ′α−β′γ′α=Λ01 ),(
1),(
1 )(),()(ln)(),()(ln)(ii T
iiiT
iiiidssss
ssssssss
( ){ }
( ){ })(),()(lnmax
)(),()(lnmax)(
1),(
1),(
0
1
ssss
ssss
ss
ss
iiiT
iiiT
i
i
i
d
β′γ′α−
β′γ′α≈Λ
−∈′
−∈′
Métriques de nœuds et de branches :
)(ln)(
)(ln)(
2
2
ss
ss
iBi
iFi
M
M
βσ−=
ασ−=∆
∆Métrique de nœud aller (forward)
Métrique de nœud retour (backward)
),(ln),( 2 ssss ′γσ−=′∆
iim Métrique de branche
Codes convolutifs algorithmes SISO : Sub-MAP
L’algorithme Sub-MAP calcule :)(2
)(2
ii dd Λσ=Λ′∆
{ }
( )
+′+′−
+′+′≈Λ′
−∈′
−∈′
)(),()(min
)(),()(min21)(
1),(
1),(
1
0
ssss
ssss
ss
ss
Bii
Fi
T
Bii
Fi
Ti
MmM
MmMd
i
i
+±−′−
+±+′≈Λ′
−∈′
−∈′
})()({min
})()({min21)(
1),(
1),(
1
0
ss
ss
ss
ss
Biii
Fi
T
Biii
Fi
Ti
MyxM
MyxMd
i
i
Codes convolutifs algorithmes SISO : Sub-MAP
Timisoara 18-20 mars 2003
ENST Bretagne 44
0
1
2
3
0
1
2
3i-1 i
([
)(
)])(),()(),(),()(
),(),()(,)(),()(min
)(),()(),(),()(
),(),()(),(),()(min21)(
11
11
11
11
33332200
11220011
33222211
11330000
Bii
Fi
Bii
Fi
Bii
Fi
Bii
Fi
Bii
Fi
Bii
Fi
Bii
Fi
Bii
Fii
MmMMmM
MmMMmM
MmMMmM
MmMMmMd
++++
++++−
++++
++++=Λ′
−−
−−
−−
−−
Exemple:
Codes convolutifs algorithmes SISO : Sub-MAP
})({min)(
}),()({min)(
1120
1120
iiFi
Fi
iFi
Fi
yxMM
mMM
±±′≈
′+′≈
−−=′
−−=′
ν
ν
ss
ssss
s
s
L
L
Codes convolutifs algorithmes SISO : Sub-MAP
sont calculés récursivement :)(et )( ss Bi
Fi MM
})({min)(
}),()({min)(
111120
11120
+++−=
++−=
±±≈′
′+≈′
ν
ν
iiBi
Bi
iBi
Bi
yxMM
mMM
ss
ssss
s
s
L
L
Timisoara 18-20 mars 2003
ENST Bretagne 45
0
1
2
3
0
1
2
3
0ou 1 =+ii dd1ou 1 =+ii dd
1−i 1+ii
Exemple
* ( )),()(),,()(min)( 11 1221331 iFii
Fi
Fi mΜmΜΜ ++= −−
( )),()(),,()(min)( 11 0110000 iFii
Fi
Fi mΜmΜΜ ++= −−*
( )),()(),,()(min)( 111 2002112 +++ ++= iFii
Fi
Fi mΜmΜΜ*
)(1 2FiM +
)(0FiM
)(1FiM
)(1 3FiM −
)(1 1FiM −
)(1 0FiM −
)(1 2FiM −
Codes convolutifs algorithmes SISO : Sub-MAP
0
1
2
3
0
1
2
3
0ou 1 =+ii dd1ou 1 =+ii dd
1−i 1+ii
)(0BiM
)(2BiM
)(1 0BiM +
)(1 1BiΜ +
)(1 2BiM +
)(1 3BiM +
* ( )),()(),,()(min)( 1111 3231212 ++++ ++= iΒii
Βi
Βi mΜmΜΜ
( )),()(),,()(min)( 1111 2020000 ++++ ++= iΒii
Βi
Βi mΜmΜΜ*
( )),()(),,()(min)(1 2120101 iΒii
Βi
Βi mΜmΜΜ ++=−*
)(1 1BiM −
Codes convolutifs algorithmes SISO : Sub-MAP
Exemple
Timisoara 18-20 mars 2003
ENST Bretagne 46
• Obtention de l’information extrinsèque pour le décodage itératif :
peut s’écrire :)( idΛ′
iii Zxd +≈Λ′ )(
est l’information extrinsèque produite par le décodeuriZ
+±−′−
+±+′≈Λ′
−∈′
−∈′
})()({min
})()({min21)(
1),(
1),(
1
0
ss
ss
ss
ss
Biii
Fi
T
Biii
Fi
Ti
MyxM
MyxMd
i
i
Codes convolutifs algorithmes SISO : Sub-MAP
Codes convolutifs algorithmes SISO : Biblio[1] G. Battail, “Pondération des symboles décodés par l’algorithme de Viterbi”, Ann.
Télécomm., vol. 42, N°1-2, pp. 31-38, Jan. 1987.[2] J. Hagenauer and P. Hoeher, “A Viterbi algorithm with soft-decision outputs and its
applications”, in Proc. IEEE Globecom’89, Dallas, Texas, Nov. 1989, pp. 4711-4717.
[3] C. Berrou, P. Adde, E. angui, and S. Faudeil, “A low complexity soft-output Viterbi decoder architecture”, in Proc. IEEE Int’l Conf. on Comm., Geneva, Switzerland, 1993, pp.737-740.
[4] L.R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate”, IEEE Trans. Inform. Theory, vol. IT-20, pp. 284-287, 1974.
[5] P. Robertson, E. Villebrun, and P. Hoeher, “ A comparison of optimal and sub-optimal MAP decoding algorithms operating in the log domain”, in Proc. IEEE Int’l Conf. on Comm., Seattle, WA, 1995, pp.1009-1013.
[6] A. J. Viterbi, “An intuitive justification and a simplified implementation of theMAP decoder for convolutional codes”, IEEE Journal on Selected Areas in Comm.,Vol. 16, N°2, Feb. 1998.
[7] B. Vucetic, J. Yuan, Turbo Codes, Principles and Applications, Kluwer Academic Publishers, 2000.
Timisoara 18-20 mars 2003
ENST Bretagne 47
Chapitre 4
Turbo codes
Plan
• Mots croisés• “turbo codes historique”• Pourquoi de si bons résultats ?• Différents schémas
– Turbo Codes en bloc – Turbo Codes convolutifs
Timisoara 18-20 mars 2003
ENST Bretagne 48
☺☺☺☺☺☺☺☺☺☺
ETRESVTNESUIVRENIDIIIAGEMOIITAGEDI54321
Mots croisés
HorizontalI. DommageII. LettreIII. RepasIV. MinentV. Enchâssement
Vertical1. Gras2. Envoyée3. Indisposer4. Intermédiaire5. Gâteau
GIRADVTNRSUIVRENIDIIIAMMAGIITAGEDI54321☺☺☺
Turbo Codes
Inventés* en 1990, les Turbo Codes est une mise en oeuvre de la déclaration de Claude Shannon (1953) :
A scheme of coding and decoding can be found allowing correction of all transmission errors, if the information rate
is inferior or equal to the channel capacity.
* première publication à ICC’93 – Genève - Suisses
Travaux précédents : Tanner, Gallager, Battail, Hagenauer & Hoegher, …
Timisoara 18-20 mars 2003
ENST Bretagne 49
Turbo CodesCodeurCodeurUn Turbo codeur est constitué d’au moins deux codeurs élémentaires de codes convolutifs systématiques (RSC) codes séparés par un entrelaceur
Concaténation parallèle de 2 codes RSC
Code 1
Code 2
Données
diy1i
y2i
Redondance
xi
π Rendement naturel :1/3
Turbo CodesCodeurCodeurUn Turbo codeur est constitué d’au moins deux codeurs élémentaires de codes convolutifs systématiques (RSC) codes séparés par un entrelaceur
Concaténation parallèle de 2 codes RSC(R=1/2)
Code 1
Code 2π
Données
di
y1i
y2i
Poinçonnage
Redondanceyi
xi
Timisoara 18-20 mars 2003
ENST Bretagne 50
Xi = (2xi-1) + ni (xi=di)Y1i = (2y1i-1) + n1iY2i = (2y2i-1) + n2i
Décodeur 1 Décodeur 2Xi
Y1i
Y2i
π-1π di^
Code 1
Code 2π
Données
diy1i
y2i
Redondance
xi
Turbo CodesDécodeur
Construit sur la base de décodeurs élémentaires à entrées et sorties pondérées (Soft Input Soft Output SISO)Processus itératif (effet turbo)
Décodeur 1 Décodeur 2(SISO) (SISO)
Xi
Y1i
Y2i
π-1π
Xi = (2xi-1) + ni (xi=di)Y1i = (2y1i-1) + n1iY2i = (2y2i-1) + n2i
di^
π-1
Timisoara 18-20 mars 2003
ENST Bretagne 51
Turbo CodesDécodeur
Construit sur la base de décodeurs élémentaires à entrées et sorties pondérées (Soft Input Soft Output SISO)Processus itératif (effet turbo)
Décodeur 1 Décodeur 2
Z1i : information extrinsèque
(SISO) (SISO)
première itération
Xi
Y1i
Y2i
π-1π Z1i
Xi = (2di-1) + niY1i = (2xi-1) + n1iY2i = (2yi-1) + n2i
Turbo CodesDécodeur
Décodeur 1 Décodeur 2(SISO) (SISO)
Itération p
Xi
Y1i
Y2i
π-1π Zp i
Zp i : information extrinsèque associée à la donnée diZp i et Xi sont altérées par des bruits non corrélés (effet de la diversité)
Zp-1 i
π-1 di^
Timisoara 18-20 mars 2003
ENST Bretagne 52
xi
Code 1
Code 2
Données
diy1,i
y2,iπ
Décodeur 1
Décodeur 2
Xi
Y1,i
Y2,i
π -1π
π
Comment faire pour que les deux décodeurs travaillent conjointement, c’est à dire que le décodeur 1 profite de Y2et que le décodeur 2 profite de Y1 ?
« Message passing »« turbo »
Turbo décodage Information extrinsèque
X1
X2
• Critère de décodage : les deux décodeurs doivent converger vers la même solution (décision et probabilité associée)
X
Y1
Y2
π
O1 =X1+Z1
O2 =X2+Z2
Z1
Z2
π-1
Décodeur 1(SISO)
Décodeur 2(SISO)
Timisoara 18-20 mars 2003
ENST Bretagne 53
O2 =(X2+Z1)+Z'2
O1 =(X1+Z2)+Z'1
X1+Z2
X2+Z1
Turbo décodage Information extrinsèque
X
Y1
Y2
Décodeur 1(SISO)
Décodeur 2(SISO)π
Z1
Z2
π-1
• Critère de décodage : les deux décodeurs doivent converger vers la même solution (décision et probabilité associée)
Turbo décodage Le principe turbo
Décodeur 2G2
Décodeur 1G1 SNRZ1out
SNRZ2inSNRZ2out
SNRZ1in
Canal Eb/N0
Itérations et convergence d’un turbo décodeur
L’information Extrinsèque est approximée à une variableGaussienne de moyenne λ et de variance σλ
2
22 / λ∆
σλ=SNRChaque décodeur est considéré au travers d’une fonction de transfert non-linéaire de rapport signal à bruit (SNR)SNRZ1out=G1 (SNRZ1in , Eb/N0)SNRZ2out=G2 (SNRZ2in , Eb/N0)
Timisoara 18-20 mars 2003
ENST Bretagne 54
Turbo décodage Le principe turbo
Itérations et convergence d’un turbo décodeur
G1
G2-1
SNRin
SNRout
1ère itération2ème itération
3ème itérationtunnel
dépend de Eb/N0
D. Divsalar, S. Dolinar, F. Pollara, "Low Complexity Turbo-like Codes", Proc. 2nd International Symposium on Turbo Codes and Related Topics, Brest, France sept. 2000, pp. 73-80
Turbo codeur Turbo décodeur :une structure à contre-réaction
sortiedécodéeY2
Y1
d̂
LLR (d)
LLR (d)1
2
X1
X2
Z1
Z2
X
décodeurSISO8 états
Π
Π
Π−1
x
y1
y2
permutation
d(données)
C1
Π C2 décodeurSISO8 états
x β x β
Adaptée pour un circuit analogique, mais pas pour un circuit numérique !!⇒ Processus itératif
Timisoara 18-20 mars 2003
ENST Bretagne 55
Turbo codeur Turbo décodeur
sortiedécodéeY2
Y1
d̂
LLR (d)
LLR (d)1
2
X1
X2
Z1
Z2
X
décodeurSISO8 états
Π
Π
Π−1
x
y1
y2
permutation
d(données)
C1
Π C2 décodeurSISO8 états
x β x β
Information extrinsèque
Décodeurs à entrées et sortiespondérées
Réglage dugain de boucle
Pourquoi de si bons résultats ?
Timisoara 18-20 mars 2003
ENST Bretagne 56
Turbo codes :similaires à des RSC de grande longueur
Il peut être comparé à un code convolutif ayant une grande longueur de contrainte,qu’il est possible de décoder.
xi
Code 1
Code 2
Données
diy1i
y2iπ
Décodeur 1
Décodeur 2
Xi
Y1i
Y2i
π -1π
1 2 ν
d X
Y
Générateurpseudoaléatoire
R = 1/2 R = 2/3 R = 3/4 R = 4/5
R = 5/6 R = 6/7 R = 7/8
-0.2 0.2 0.6
0.03
0.07
0.06
0.04
0.05
0.020.8 1.2 1.6
0.021.6 2.0 2.4
0.03
0.07
0.06
0.04
0.05
0.02
0.06
0.05
0.03
0.04
0.011.2 1.6 2.0
= 2 = 4
= 6
0.02
0.06
0.05
0.03
0.04
0.01
0.02
0.06
0.05
0.03
0.04
0.01
0.01
0.05
0.04
0.02
0.03
0.001.6 2.0 2.4 1.8 2.2 2.6 2.2 2.6 3.0
= 8
Limite de Shannon(canal gaussien entrée binaire)
ν ν
ν ν
0.05
0.09
0.08
0.06
0.07
0.04
TEBE /Nb 0
Plus le registreest grand, meilleur est le code convolutif
Timisoara 18-20 mars 2003
ENST Bretagne 57
Code 1
Code 2π
Données
diY1,i
Y2,i
xi
Mémoire ν
k bits
Code simple
ν ≤ mémoire ≤ k +2ν
À prouver !
Turbo codes :similaires à des RSC de grande longueur
Pourquoi de si bons résultats ?Lorsqu’un paquet d’erreurs affecte “code 1”, les erreurs sont disséminées pour le “code 2” et vice versa.
xi
Code 1
Code 2
Données
diy1i
y2iπ
Décodeur 1
Décodeur 2
Xi
Y1i
Y2i
π -1π
Timisoara 18-20 mars 2003
ENST Bretagne 58
Turbo codes :une approche du codage aléatoire
Concaténation parallèle de N codes
CRSC:
Codage quasi-aléatoire
(pour N ≥ 4)
Et c’est décodable !!Tirés de manière aléatoire
Heureusement, N = 2 est suffisant:
turbo codes
permutationk donnéesbinaires
Mot
de
code
Partiesystématique
ΠCRSC
permutationΠ
CRSC
permutationΠ
CRSC
N
2
1(identity)
YN,i
Y1,i
Y2,i
Treilliscirculaire
0k-1
Y1,0
Y1,k/N-1
Y2,0
YN,0
YN,k/N-1
Y2,k/N-10k-1
0k-1
Treilliscirculaire
Treilliscirculaire
Xi = (2xi-1) + ni (xi = di)Y1,i = (2y1i-1) + n1iY2,i = (2y2i-1) + n2i
Code 1
Code 2π
Data
diy1,i
y2,i
xi
Le rôle fondamental de π :minimiser la probabilité que les 2 décodeurs défaillent
(un problème très complexe combinant algèbre, géométrie, ...)
Decodeur 1
Decodeur 2
Xi
Y1,i
Y2,i
π
Timisoara 18-20 mars 2003
ENST Bretagne 59
Différents schémas de turbo codes
Turbo code en blocCode 1(k , n) πDonnées
Code 2(k , n)
M1 C1 M2 C2
concaténation série de deux codes en bloc
Mot de
code
k colonnes
n colonnes
k lignesn lignes
Mot de code 2
Mot de code 1
Redondance 1
Redondance 2
Timisoara 18-20 mars 2003
ENST Bretagne 60
Turbo code en blocCode 1(k , n) πDonnées
Code 2(k , n)
M1 C1 M2 C2
Propriétés (sans poinçonnage) :• n = n1.n2• k = k1.k2• R = R1.R2• dmin = dmin1.dmin2
Turbo codes convolutifs auto-concaténés
Code 1
Code 2
Données
diy1i
y2iπ
xi
Code 1Données
diyi
xi
π
Timisoara 18-20 mars 2003
ENST Bretagne 61
Principe de décodage
1
Données Données entrelacées
k
Information extrinsèque (z)
Code 1
Code 2
données
diy1i
y2iπ
xi
Code 1données
diyi
π
xi
Quelques schémas Turbo codes convolutifs
Code 1
Code 2
données
ai,bi y1i
y2iπ
Code 1
Code 2
données
diy1i
y2iπ
xi
classique Auto-concaténé
duo-binaire série Et plein d’autres ...
Timisoara 18-20 mars 2003
ENST Bretagne 62
Chapitre 5
La permutation
Permutation(Permutation ≡ entrelacement)
C1
C2
Π
données A
Y1
Y2
Le comportement à faibleTEB (<10-5) est fonctionde la façon dont Π estconçu
Le rôle fondamental de la permutation : si une séquence directe est RTZ, il fautminimiser la probabilité que la séquence permutée soit aussi RTZ (et vice-versa).
Timisoara 18-20 mars 2003
ENST Bretagne 63
Illustration avec le code suivant :
Séquences RTZ
00
01
10
11
0011 11
01
10
00
di =0 xi yi
di =1 xi yi
D Ddi
yi
xi
10
01
Séquences RTZ00
11
Distance de Hamming =5
00
11
10
01
00
11 11
011010
00
01
00
11 11
011010
00
01
00
01
10
11
00
2+
11
2+
11
0+
00
0
00
1+
01
00
11 11
011010
00
01
0+
00
Timisoara 18-20 mars 2003
ENST Bretagne 64
Séquences RTZ00
11
Distance de Hamming =6
00
11
10
01
00
11 11
011010
00
01
00
11 11
011010
00
01
00
01
10
11
00
2+
11
1+
01
0
00
1+
01
00
11 11
011010
00
01
0+
00
2+
11
Séquences RTZ00
11
Distance de Hamming
00
11
10
01
00
11 11
011010
00
01
00
11 11
011010
00
01
00
01
10
11
00
2+
11
1+
01
0
00 00
11 11
011010
00
01
0+
00
0+
00
1+
01
Timisoara 18-20 mars 2003
ENST Bretagne 65
Séquences RTZ
D Ddi
yi
xidi =0 xi yi
di =1 xi yi
00
01
10
1100 11 10
0111
0001
10
Permutation Régulière
0010110010...0110001...................................0100100100...10010100011110100...10110110101000110...0101001
Écriture en
ligne
Lecture encolonne
M colonnes
N lignes
Condition : k = M.N
Ordre naturel :adresse k-1
Ordre naturel :adresse 0
Timisoara 18-20 mars 2003
ENST Bretagne 66
Permutation Régulière
0k-1Adresse naturelle : i0 ≤ i ≤ k-1
Adresse permutée : j0 ≤ j ≤ k-1
j = P.i mod. k
(P et k premiers entre eux)
Permutation Régulière
0100000010...0000000...................................0000000000...00000000000000000...00000000000000000...0000000
M colonnes
N lignespériode : 7
période : 7
La permutation régulière est adaptée aux poids 2
k → ∞ ⇒ d(w=2) → ∞
Timisoara 18-20 mars 2003
ENST Bretagne 67
D D
diyi
xi di =0 xi yi
di =1 xi yi
000
D
001 101
100111
010
011
110
0010
11 11
10
1111
00
0100
00
01
01
01
11
10
Permutation Régulière
M colonnes
N lignespériode : 7
période : 7
La permutation régulière est adaptée aux poids 3
k → ∞ ⇒ d(w=3) → ∞
0110100000...0000000...................................0000000000...00000000000000000...00000000000000000...0000000
Timisoara 18-20 mars 2003
ENST Bretagne 68
Permutation Régulière
0100000010...00000000000000000...00000000000000000...00000000000000000...00000000000000000...00000000000000000...00000000000000000...00000000100000010...0000000.....................................
M colonnes
N lignespériode : 7
période : 7
La permutation régulière n’est pas adaptée aux poids 4
k → ∞ ⇒ d(w=4) est limité
Permutation Régulière
M colonnes
N lignespériode : 7
période : 7
La permutation régulière n’est pas adaptée pour différents poids
0110100000...00000000110100000...00000000000000000...00000000110100000...00000000000000000...00000000000000000...00000000000000000...00000000000000000...0000000.....................................
Timisoara 18-20 mars 2003
ENST Bretagne 69
Il faut donc introduire du désordre, mais pas de n’importe quelle manière !!
Une bonne permutation doit assurer :(1) Un maximum de dispersion des données(2) Un maximum de désordre dans la séquence permutée
(ces deux conditions sont contradictoires)
Permutation Aléatoire
Timisoara 18-20 mars 2003
ENST Bretagne 70
Permutation AléatoirePermutation aléatoire selon S. Benedetto et G. Montorsi
Tous les entrelaceurs sont considérés, de manière statistique,en y incluant les pires
Quels sont les pires ?
0100000010...0000000...................................0000000000...00000000000000000...00000000000000000...0000000ce couple a une
probabilité de 1/kde rester inchangéaprès permutation
Permutation Aléatoire Permutation aléatoire selon S. Benedetto et G. Montorsi
0100000010...0000000...................................0000000000...00000000000000000...00000000000000000...0000000
Cette approche conduit naturellementà une borne qui a l’allure suivante :
≈
0
min...1N
dERerfck
P be
Donnant une évaluation très pessimiste !
Timisoara 18-20 mars 2003
ENST Bretagne 71
Permutation pseudo-aléatoire (= désordre contrôlé)
Chacun a ses recettes
CCSDS 101.0-B-4: Telemetry Channel Coding.Blue Book. Issue 4. May 1999.
voir http://ftp.ccsds.org/all_books.html#telemetry
Par exemple, l’entrelacement du Consultative Committee forSpace Data Systems (CCSDS)
Permutation CCSDS
;67;61;59;53;47;43;37;31
)14(2)(8
mod 21
1 8 mod 4 mod 119
821
14
2 mod 1
8765
4321========
−++=Π
+=
+=+=
−=
=
−=
pppppppp
mcts
kmjpc
tqit
iks-j
ks- i
sm
q
0110101000...0100000110010011101001110110101...0010011000100011010011010001100...1000100111011001011101100101000...1100110000101010010110111101000...0100001110011110101010100010101...0010011000101011010011010001100...1000100011011001111101100101000...110011000000101001001.....................................0100101011...1100110100110010010101110101010...0101100110010110101100100010101...001001100010101101001
non-uniformité de degré 8
Timisoara 18-20 mars 2003
ENST Bretagne 72
Permutation
En conclusion :
•Pas de permutation idéale pour le moment (existe-t-elle ?)•Il n’est pas nécessaire de l’avoir
Timisoara 18-20 mars 2003
ENST Bretagne 73
Chapitre 6
turbo codes duo-binaires
Turbo codes duo-binaires
C1
C2
Π
données (bits)X
Y1
Y2
C1
C2
Π
données (couples) A
Y1
Y2
B
R = 1/3 (1/2 //1/2) R = 1/2 (2/3 //2/3)
binaire duo-binaire
Timisoara 18-20 mars 2003
ENST Bretagne 74
5
5
5
5
5
5
5
5
10-1
10-3
10-4
10-6
10-7
10-8
20 1 3 4 5 6 7 8 9 10 11 12
Eb/N0 (dB)
TEB
non codé
mauvaise convergence, gain asymptotique élevé
Bonne convergence, faible gain asymptotique
10-2
10-5
Limite théorique(R=1/2, 188 octets)
Rappel MDP4, canal gaussien, taux d’erreurs cible : 10-8
Ga = 10 log (R.dmin)
dmin > 25
∫∞
=−=
xt
b
dttxerfc
avecNEerfc
)exp(2)(
)(21
2
0
π
Contribution des codes duo-binaires sur la convergence
kk / 2
k / 2k
binaire
duo-binaire :Diminue la corrélationDurant le décodage
C1
C2
Π
C1
C2
Π
Turbo codes duo-binaires
cheminerroné
motifs deverrouillage
k
k
Timisoara 18-20 mars 2003
ENST Bretagne 75
Turbo codes duo-binaires Contribution des codes duo-binaires sur les distances minimales
C1
C2
Π
données (couple) A
Y1
Y2
BC1
C2
Π
données (bit)
Y1
Y2
Π : permutation inter-symbole Π : permutation inter-symbole + intra-symbole
Le rôle fondamental de la permutation : si une séquence directe est RTZ,il faut minimiser la probabilité que la séquence permutée soit aussi RTZ(et vice-versa).
Rappel :
X
Turbo codes duo-binaires Contribution des codes duo-binaires sur les distances minimales
000
001
010
011
100
101
110
111
000
001
010
011
100
101
110
111
Treillis binaire
Treillis Duo-binaire(partiel)
X AB
(a) (b)
AB
Y
X
Y
100000010 00 00 00 00 00 010000001
2010 00 00 00 00 00 0201
1300000000000013
1
2
3
0
00
0
k
kk / 2
k / 2
00 : 001 : 110 : 211 : 3
Périodicités du Code duo-binaire
exemples demotifs à faibles distances avec unepermutationrégulière
Timisoara 18-20 mars 2003
ENST Bretagne 76
Grâce à cette technique, les distances minimales sont généralementplus grandes que celles des concaténations séries (codes produits) !!!!
Turbo codes duo-binaires Contribution des codes duo-binaires sur les distances minimales
Permutation intra-symbole
2 0 10 00 00 00 00 00 02 0 1
1 30 00 00 00 00 00 01 3
3 0 0 0 0 0 0 30 00 00 02 0 0 0 0 0 0 2
3 0 0 0 0 0 0 30 00 00 00 00 00 03 0 0 0 0 0 0 3
1 30 00 00 00 00 00 00 00 00 00 00 00 00 01 3
Ces motifs ne sont pluspossibles si les couples sontInversés périodiquement
Motifs d’erreurs possiblesavec une grande distance
(A,B) devient (B,A)avant le codage vertical,une fois de temps en temps
(sans introduction de désordre aléatoire !)
• Latence divisée par 2 (codage et décodage)• Débit de traitement des données doublé (parallélisme intrisèque)• Plus faible dégradation MAP → SUB-MAP• Meilleur mapping pour constellations à grand nombre d’états
Turbo codes duo-binaires Autres avantages des codes duo-binaires
Timisoara 18-20 mars 2003
ENST Bretagne 77
Turbo codes duo-binairesStandard DBV-RCS (+RCT)
permutation(k/2)
k/2 couplesde données
MoT
de
code
partie systématique
redondance
1
2poinçon-nage
Y2 Y1
A
B
coupledécodé
, Y2Y1
LLR
LLR 1
2
Z1
Z2
A, B
SUB-MAP8 états4 chemins
SUB-MAP8 états4 chemins
Π
Π
Π
Π−1
1 1
, Y2Y12 2
s1 s3s2AB
Y1
partie systématique
redondance
Y2
Complexité≈ 20.000 portespar bit.itération@ horloge système+ mémoire
Turbo codes duo-binaires Standard DVB-RCS (+RCT)
Niveau 1 (intra-couple)if j=0 mod 2 (A,B)=(B,A) [inversion du couple]
Niveau 2 (inter-couple)if j=0 mod 4 P=0if j=1 mod 4 P=P1+ N/2if j=2 mod 4 P=P2if j=3 mod 4 P=P3 + N/2
i=π(j)=P0.j + P + 1 mod N
P0, P1, P2 et P3 sont des entiers, pour chaque N (nombre de couples).
Permutation générique Π
Timisoara 18-20 mars 2003
ENST Bretagne 78
Taille des blocs : 12, 16, 53, 55, 57, 106, 107, 108, 110, 188, 212, 214, 216 octets
Rendements : 1/3, 1/2, 2/3, 3/4, 4/5, 6/7
Turbo codes duo-binaires Standard DVB-RCS (+RCT)
Turbo codes duo-binaires Standard DVB-RCS (+RCT)
Exemple de performance : TC1000 (TurboConcept)(Mesures, 53 octets, SUB-MAP, 4 bits de quantification, 8 itérations)
1e-09
1e-08
1e-07
1e-06
1e-05
0.0001
0.001
0.01
0.1
1
0 1 2 3 4 5 6 7 8 9 10
Taux
d’e
rreur
s pa
quet
s
Eb/N0
Non codé53 octets 1/2 8 it.53 octets 2/3 8 it.53 octets 3/4 8 it.53 octets 4/5 8 it.53 octets 6/7 8 it.
Timisoara 18-20 mars 2003
ENST Bretagne 79
Turbo codes duo-binaires Standard DVB-RCS (+RCT)
Exemple de performances : TC1000 (TurboConcept)(Mesures, 188 octets, SUB-MAP, 4 bits de quantification, 8 itérations)
1e-09
1e-08
1e-07
1e-06
1e-05
0.0001
0.001
0.01
0.1
1
0 1 2 3 4 5 6 7 8 9 10
Taux
d’e
rreur
s pa
quet
s
Eb/N0
Non codé188 octets 1/3 8 it.188 octets 2/5 8 it.188 octets 1/2 8 it.188 octets 2/3 8 it.188 octets 3/4 8 it.188 octets 4/5 8 it.188 octets 6/7 8 it.
Duo-binaire turbo codesStandard DVB-RCS (+RCT)
Exemple de performances : mini-slots(simulation, SUB-MAP, 4 bits de quantification, 6 itérations)
Eb/N0 (dB)
Taux d’erreurs paquets
5
5
5
5
5
5
5
5
10-8
10-3
10-4
10-5
10-6
10-7
10-1
10-2
3 4 5 6
12 oct.
16 oct.
12 oct.14 oct.16 oct.
14 oct.
4 oct.
R = 1/2R = 1/2
R = 1/3
R = 2/3
7 8
12 oct.14 oct.16 oct.
4 oct.
R = 4/5
R = 4/5
12 oct.
16 oct.14 oct.
Timisoara 18-20 mars 2003
ENST Bretagne 80
Chapitre 7
Conclusions et perspectives
1e-09
1e-08
1e-07
1e-06
1e-05
0.0001
0.001
0.01
0.1
1
0 1 2 3 4 5 6 7 8 9 10
Taux
d’e
rreur
s pa
quet
s
Eb/N0
Non codé188 octets 1/3 8 it.188 octets 2/5 8 it.188 octets 1/2 8 it.188 octets 2/3 8 it.188 octets 3/4 8 it.188 octets 4/5 8 it.188 octets 6/7 8 it.
Conclusions et perspectives Codage
Limites théoriques
0.3 dB (turbo + it.) + 0.3 dB (SUB-MAP) + 0.15 dB (quantification) + 0.05 dB (matériel)+ 0.4 dB (?)
perte @ PER = 10-4
≈ 1.2 dB
Timisoara 18-20 mars 2003
ENST Bretagne 81
1e-09
1e-08
1e-07
1e-06
1e-05
0.0001
0.001
0.01
0.1
1
0 1 2 3 4 5 6 7 8 9 10
Taux
d’e
rreur
s pa
quet
s
Eb/N0
Non codé188 octets 1/3 8 it.188 octets 2/5 8 it.188 octets 1/2 8 it.188 octets 2/3 8 it.188 octets 3/4 8 it.188 octets 4/5 8 it.188 octets 6/7 8 it.
Conclusions et perspectives Codage Génération suivante (2002)1 dB gain @ TEP = 10-7
pour une complexité double
Standards actuels
Application turbo code terminaison polynômes rendements
CCSDS binaire,16 états
tail bits 23, 33, 25, 37 1/6, 1/4, 1/3, 1/2
IMT-2000 binaire,8 états
tail bits 15, 13, 17 1/4, 1/3, 1/2
DVB-RCS duo-binaire,8 états
circulaire 15, 13 de 1/3 à 6/7
DVB-RCT duo-binaire,8 états
circulaire 15, 13 1/2, 3/4
Inmarsat (mini M)
binaire,16 états
no 23, 35 1/2
Skyplex duo-binaire,8 états
circulaire 15, 13 4/5, 6/7
Timisoara 18-20 mars 2003
ENST Bretagne 82
Conclusions et perspectives turbo-X• Turbo (dé)modulation• Turbo égalisation• Turbo détection (CDMA)• Turbo synchronisation• Turbo (dé)codage de source
processeurprobabiliste
informationintrinsèquelocale
informationextrinsèque1
4
3
2
modèle général d’un turbo processeur
informationintrinsèquepartagée
Applications
1990 1995 2000
inventionpatents
publication
CCSDS
M4
UMTSCDMA2000
DVB-RCSDVB-RCT
HiperAccess
Disques durs ?CD-ROM ?
DVB-S ?DSL ?
turbo-égalisation,turbo-synchro,turbo-crypto,...
Timisoara 18-20 mars 2003
ENST Bretagne 83
Information générale à propos des Turbo codes
- C. Heegard, S. B. Wicker, Turbo Coding, Kluwer Academic Publishers, 1999- Branka Vucetic, Jinhong Yuan, Turbo Codes, Principles and Applications, Kluwer Academic Publishers, 2000- C. Schlegel, Trellis coding, IEEE Press, 1997- B.J. Frey, Graphical Models for Machine Learning and Digital Communication, MIT Press, 1998- R. Johannesson , K. Sh. Zignagirov, Fundamentals of Convolutional Coding, IEEE Press, 1999- Hanzo, Lajos, Adaptative wireless transceivers, John Wiley & sons, 2002 - Hanzo, Lajos, Turbo coding, turbo equalisation and space-time coding for transmission over fading channels, John Wiley & sons, 2002
- sites WEB : http://www-turbo.enst-bretagne.fr/2emesymposium/presenta/turbosit.htmest un bon point de départ
- base de données IEEE Xplore : mot clé : turbo, 1974 réponses le 13 mars, 2003