Architecture générique de décodage de code LDPCboutillon/ldpc/conf_SCEE_ldpc.pdf · Gallager LDPC 1962 Berrou, Glavieux Turbo Codes 1993 MacKay LDPC 1995 Wiberg Graphes 1995 Richardson,

7 Avril 2005

E. Boutillon1/54http://lester.univ-ubs.fr/

Architecture génériqueArchitecture génériquede décodage de code LDPCde décodage de code LDPC

F. GUILLOUDE. BOUTILLON

[email protected]@univ-ubs.fr

0 1 2 3 4 5 6

7 Avril 2005


Prédiction de Shannon (année 50)zone de couverture potentiel

Importance du codage...

Invention des turbo-codes1993 (Berrou Glavieux)

Situation en 1990zone de couverturede l'émetteur

Emetteur

1995 : Redécouverte des codes LDPC(Gallager 1960)

Compétition LDPC-Turbo-Code...

7 Avril 2005


Low Density Parity Check Code

Gallager LDPC 1962Berrou, Glavieux Turbo Codes 1993MacKay LDPC 1995Wiberg Graphes 1995Richardson, Urbanke Density Evolution 2001

Premières architectures de décodeurs 2001Standard DVB-S2 2003

Inventé en 1961 par Gallager (thèse MIT), oublié, redécouvert en 1995 (MacKay, Ritchardson).

7 Avril 2005


Code de parité Principe des codes LDPCArchitecture de décodeur LDPCEn guise de conclusion

PLAN

7 Avril 2005


Parity check

Parity check (3,2,1) :

(b0, b1, b2) codeword <=> Sum of 1 = 0 mod 2.

CP(3,2,1) = {(0, 0, 0) ; (0, 1, 1) ; (1, 1, 0) ; (1, 0, 1)}

b0 b1 b2 bits

CP

Generalization: Parity Check (n, n-1, 1)

7 Avril 2005


Décodage d'un code de Parité

bj∈ {0,1} Mod.xj∈ {-1,+1}

N(0,σ)

Démod.xj yj = xj +wj

wj

L'observation yj donne l'information intrinsèque ij du bit bj:

ij = (p(bj=0/yj) , p(bj=1/yj))

que l'on exprime aussi par le "log likelihood ratio":

ij = ln(p(bj=1/yj)/p(bj=0/yj)) = 2yj/σ2

Note: sign(ij) => décision dure, | ij | fiabilité de la décision

7 Avril 2005


Décodage d'un code de Parité

Quelle information i1 et i2donnent sur la valeur b0 ?

En utilisant:

p(b0=0/y1 ,y2) = p(b1=0/y1). p(b2=0/y2) + p(b1=1/y1) . p(b2=1/y2) p(b0=1/y1 ,y2) = p(b1=0/y1). p(b2=1/y2) + p(b1=1/y1) . p(b2=0/y2) on obtient une observation e0 de la valeur de b0 indépendante de i0 :

)1ln(21

21210 ii

ii

eeeeiie

+

⋅+=⊕=

e0 est appelé information extrinsèque

? b1 b2 bits

CPi1 i2e0

7 Avril 2005


Décodage d'un code de parité

Enfin, i0 et e0 sont additionnés pour obtenir la valeur finale.

Le processus est symétrique pour tous les bits.

b0 b1 b2

y0 y1 y2

2.92.2ij

b0 b1 b2

1.4

ij

ej -1.0-1.2-1.7

2,92,21,4

1.91-0.32.92.21.4

Mot de code

7 Avril 2005


Conseil : éviter les auto-confirmations

Jean et Claire… 80%

Pierre

Paul



90%

Jacques Jean et Claire… 80%

7 Avril 2005


Note: itération

Si le processus itère de nouveau, il y a autoconfirmation

b0 b1 b2

1,91Ij

b0 b1 b2

-0,3

Tj

Ej 0,10,2-0,8

1,91-0,3

21,2-1,1

1,91-0,3

Et le système diverge...

7 Avril 2005



PLAN

7 Avril 2005


LDPC Code

Peut être défini par un graph bi-partite

0 1 2 3 4 5 6 Bit bi

Parity checks (PC)

Branches

(b0, b1, … , b6) mot de code <=> toutes les PC sont respectées

7 Avril 2005


Pourquoi le nom de LDPC ?

Représentation algébrique :X = (x0, x1, …, x6)T mot de code si H.X = 0

0 1 1 1 1 0 01 0 1 1 0 1 01 1 0 1 0 0 1H =

0 1 2 3 4 5 6

Matrice de parité

Nombre de 1 sur une ligne = dc=nombre de bit associé au PCNombre de 1 sur une ligne = dv=nombre de PC associé à la bit

N=nombre de bits

P=nombre de PC

Moins de 1% des bits de H sont égaux à 1

7 Avril 2005


Exemple de matrice LDPC

Matrice de parité H de taille (1024, 512), (dv,dc)=(3,6)Question : rendement du code ? Nombre de 1 de la matrice ?

7 Avril 2005


Comment construire un bon codeLDPC ?

Application => taille du code et rendement

Sélection de la répartition optimale des spectres de répartitiondes poids des branches (en utilisant des EXIT Chart [ref]):

exemple:90 % bits => dv =3 branches, 10 % bits dv=> 12 branches70 % PC => dc = 6 branches, 30 % PC => dc = 8 branches

et on choisi le code aléatoirement... en évitant juste les cycles :

bi bj

…et on obtient un bon code

7 Avril 2005


Algorithme à propagation decroyance

Step1: calcul du LLR des bits reçus (informationintrinsèque)Step2: Message bit->parité + traitement paritéStep3: Message parité->bit + traitement bitStep4: répéter 2 et 3 jusqu'au décodage correct ou"max iteration".

7 Avril 2005


Décodage itératif

0 1 2 3 4 5 6 8 9 10 11 12 13 147

y1 y2y0 y13 y14y12y10 y11y9y7 y8y6y4 y5y3

Première itération: message bit-> parité

7

7 Avril 2005


Décodage itératif

0 1 2 3 4 5 6 8 9 10 11 12 13 147


7

0 1 2 3 4 5 6 8 9 10 11 12 13 147

Première itération: message parité-> bit

7 Avril 2005


Décodage itératif

0 1 2 3 4 5 6 8 9 10 11 12 13 147


7

0 1 2 3 4 5 6 8 9 10 11 12 13 147

Deuxième itération: message parité -> bit

7 Avril 2005


Calcul d'un nœud de variable

∑≠

−=+=imm

iini ateia,

∑+=m

mn eit

Bit Nodebn

yn

in

e0 e1 e2 e3

Bit Nodebn

in

a0= t-e0 a1 a2 a3

yn

tt

7 Avril 2005


Calcul d'un nœud de parité

dciiiij

i aaaaaae ⊕⊕⊕⊕== +−≠⊕ ...... 1121

Check Node

b0 b1 b2 b3 b4

a0 a1 a2 a3 a4

Check Node

b0 b1 b2 b3 b4

e0 e1 e2 e3 e4

Deux méthodes de calcul : directe ou fréquentielle

7 Avril 2005


Calcul parité: méthode fréquentiellea) calcul du signe

XOR

XOR XOR XOR XOR

sign(a1) sign(a2) sign(a3) sign(a4)

sign(e1) sign(e2) sign(e3) sign(e4)

7 Avril 2005


Calcul parité: méthode fréquentielleb) calcul du module

∑≠

− ΦΦ=

ji

kk ae ))((1

avec

))2/ln(tanh()( xx −=Φ

LUT φ LUT φ LUT φ LUT φ

+

LUT φ−1 LUT φ−1 LUT φ−1 LUT φ−1

- - - -

1a 4a

1e 4e2e 3e

2a 3a

7 Avril 2005


0 1 2 3 4 50

1

2

3

4

5

6

x

-ln(ta

nh(x

/2)

Fonction Φ(x)= Φ−1(x)

On obtient : e = min(a1,a2,a3) - offset

a1=0.5a2=1,2 a3=1,9

e=0,3

a1 a2 a3e

∑≠

− ΦΦ=

ji

kk ae ))((1

7 Avril 2005


Exercice

Processeur de parité

b0 b1 b2 b3 b4

-6 8 3 -2 4

Processeur de parité

b0 b1 b2 b3 b4

?

La sous-optimalité engendre une perte de 0,5 dB en convergence.

=> solution : on soustrait une constante pour compenser la sur-évaluation de l'extrinsèque : min(ek-β, 0)

=> CONVERGENCE PLUS RAPIDE !!!! (Fossorier)

2 -2 -2 3 -2

7 Avril 2005


Traitement des parités

ΦΦ= ∑

∈

−

nmNn

nmnm ae\)('

',1

, )(

Traitement des variables

∑∈

+=

−=

mnMm

nmn

nmnnm

ei

eta

\)('

,'

,,• Algorithme BPPropagation de croyance(Belief Propagation)Initialisation :

In = 2yn/σ²Extrinsèque branche : Em,n=0Fiabilités : Tm,n=0

Itérations : tous lesmessages sont traités

Propagation V → P

Propagation P → V

7 Avril 2005


Performances DVB-S2

64k 50 itérations

LDPC + BCH

7 Avril 2005


Sequencement par inondation(Méthode classique)

0 1 2 3 4 5Flooding

0

=> postulat faux : unique séquencement efficace

0 1 2 3 4 5

7 Avril 2005


Sequencement horizontal(Mansour)

011110101101110101

Matrice LDPC

0 1 2 3 4 5

7 Avril 2005



011110101101110101

Matrice LDPC

0 1 2 3 4 5

7 Avril 2005



011110101101110101

Matrice LDPC

0 1 2 3 4 5

7 Avril 2005



2 3011110101101110101

Matrice LDPC

0 1 2 3 4 5

Convergence en moitiée moins d'itération

7 Avril 2005


Sequencement vertical(Fossorier)

0 1 2 3 4 5011110101101110101

Matrice LDPC

7 Avril 2005



0 1 2 3 4 5011110101101110101

Matrice LDPC

7 Avril 2005



0 1 2 3 4 5011110101101110101

Matrice LDPC

7 Avril 2005


0 1 2 3 4 5011110101101110101

Matrice LDPC

De nouveau, convergence en moitiée moins d'itération !


7 Avril 2005


Problème séquencement H et V

Trouver une architecture adaptée...

7 Avril 2005



PLAN

7 Avril 2005


Architecture parallèle

ExempleBlanksby, Howland, « A 690-mW1-Gb/s 1024-b Rate-1/2 Low-Density Parity-Check CodeDecoder » (IEEE Trans. onSolid-State Circuits, 2002.)

Avantagesperformance: 1Gb/s 64iterationsPower dissipation : 690mWPER=2 10-4 @ 2,5 dB

DrawbackComplex routing =>add ocCAD toolFixed codeSize : 52.5mm2 , 0.16µTechno

(3) Architecture : introduction

7 Avril 2005


Architecture série-parallèle

Puissance de calcul Pc : nombre de branche à traiter/ cycle d’horloge.

Pc dépend de : code (3,6)N nombre de symboles du code ;E nombre de branche du code 3NR rendement du code ; 1/2D débit d’information (bit/s) ; 10 Mbit/sNit nombre moyen d’itération ; 20 fclk réquence d’horloge . 100 MHz

[ ] [ ]

[ ]yclebranches/c125,010

10203

yclevariable/cariablebranches/v

8

7=

×××=

×=Rf

DN

ENPclk

itc

7 Avril 2005


Degré de parallélismeP processeurs deparités(α cycles)Processeurs devariables(β cycles)Parallèle :P=M, α=1, β=1

Série :P=1, α=dc, β=dv

Entrelacementdirect

Entrelacementinverse

……

……

Contrôle

Processeursde variables

Processeursde parités

Permutationsspatiales

βvv dd ='

'vdd = 'vdd =

1 P.dc’/dv’…

…'vd'vd

1 P…

…'cdd ='cdd =

'cd αcc dd =' 'cd

7 Avril 2005


Position du réseau d'interconnection

( )xf

Σ

( )xf 1−

Σ×

signe

signes) des(produit ×Processeur de parité

Processeur de variableOpérateur

générique

Position du réseau

ΣofΣ− o1f

2

2

ff oo Σ−1Σ

1

1

foΣ

1−Σ fo

3

31−Σ ff oo

Σ

4

4

⊗

Note : Φ=f=f-1

7 Avril 2005


Opérateur Σ ou xa) Mode compact

a) Mode compact et parallèle(α ou β = 1)

a) Mode compact et série(α ou β = d)

7 Avril 2005


Opérateur Σ ou xb) Mode distribué mise à jours différée

)()(1

)(0

)( ... id

iii eeet +++=

)1(1

)1(0

)1( ... +−

++ ++= ik

ii eet

ancien nouveau

)(iks

)(ike

)(it )1( +it

Réseau de permutation

)1( +ike

)1( +ike

titération i

-

7 Avril 2005


Opérateur Σ ou xb) Mode distribué mise à jours immédiate

)()()1(1

)1(0

)1( ... id

ik

ik

ii eeeet +++= +−

++nouveau

)(iks

)(ike

)1( +it

Réseau de permutation

tItération i)1( +i

ke

)1( +ike

)()1()1(1

)1(0

)1( ... id

ik

ik

ii eeeet +++= ++−

++-

7 Avril 2005


Modèle génériqueParamètres :

Processeurs de nœuds:ArchitecturePosition du réseaud’interconnexion(1,2,3,4)

Parallélisme : P, α, βContrôle desprocesseurs

Toutes lescombinaisonssont possibles

7 Avril 2005


Séquencementvertical

InondationInondation (parités)

• Combinaison des Contrôles

Inondation Inondationparités

Inondationvariables

séquencementhorizontal

Contrôledes branches

CompacteDistribué

Mise à jourdifférée

Mise à jourimmédiate

VARIABLES

PARITES

Compacte

Dis

tribu

é Mise à jourdifférée


Entrelacement (vertical)

7 Avril 2005


Mansour

Nouveau(algo Fossorier)

• Etat de l’art

Blanksby(parallèle)

Boutillon,Chen, Zhang,

Nouveau

-

CompacteDistribué



VARIABLES

PARITES

Compacte

Dis

tribu



7 Avril 2005


N+ f(E)

N + M + E

• Etat de l’art : taille mémoire

N + E 3N+ f(E)

N + 2M + E

-

CompacteDistribué



VARIABLES

PARITES

Compacte

Dis

tribu



E : Nombre debranchesF( ) : compression

7 Avril 2005



PLAN

7 Avril 2005


Conclusion

Présentation d'un modèle d'architecture générique=> classement des architectures existantes

Proposition d'architectures nouvelles pour des séquencements verticaux ou horizontaux

=> convergence en 1/2 moins d'itération=> architecture requiérant moins de mémoire.

7 Avril 2005


Conclusion sur LDPC

Pour les codes de taille importante (n > 104) les LDPCs irréguliers ont des meilleures équivalentes à celle des Turbo-Codes

- moins de 0,1 dB de la limite de Shannon pour n = 106

(travaux de Mac-Kay, Richardson).

De rapide progrès dans la construction des matrices et des algorithmes de décodage.

Travaux en cours:

LDPC sur GF(2q)

Digital fountain

7 Avril 2005


LDPC vs Turbo-Codebits d’informationsredondance

codeur 1redondance

codeur 2

Entrelaceur

Une autre vision d'un turbo-code

LDPC et Turbo-code sont aux deux extrémités du spectre des graphes de Tanner

Il existe des solutions intermédiaires (turbo-code produit par exemple)

Compromis performances-complexité : un débat complexe et non tranché (DVB-S2)

7 Avril 2005


Nouvelle technique de décodage

Utilisation de décodeur purement analogique :

- propagation des messages de façon continue

- faible sensibilité des décodeurs à la précision

- les équations du transistor identiques à celle du MAP !

Gain en consommation et vitesse de décodage d'un facteur 10 à 1000 !

=> Solution très prometteuse...

7 Avril 2005


Exemple constructionmatrice/architecture conjoint


Matrice prototype : Hi =

1 0 0 1 1 0 0 00 1 1 0 1 1 0 01 0 1 0 0 1 1 00 1 0 1 0 0 1 1

Πi,j(Ip ) =

0 0 1 0 0 00 0 0 1 0 00 0 0 0 1 00 0 0 0 0 11 0 0 0 0 00 1 0 0 0 0

0 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 0

P

P

N = nP

M=mP

Très peu d'information pour mémoriser la matrice

7 Avril 2005


Exemple constructionmatrice/architecture conjoint


Matrice prototype : Hi =

1 0 0 1 1 0 0 00 1 1 0 1 1 0 01 0 1 0 0 1 1 00 1 0 1 0 0 1 1

N = nP

M=mP

rotation

m

P

t=1..E

ind rot

Processeurs de parité : calcul série

add

Mémoires

Documents

Architecture générique de décodage de code LDPCboutillon/ldpc/conf_SCEE_ldpc.pdf · Gallager LDPC 1962 Berrou, Glavieux Turbo Codes 1993 MacKay LDPC 1995 Wiberg Graphes 1995 Richardson,