Analyse et traitements dans un système de communication

Comment determiner les performances asymptotiques d’un systeme ? Rappel sur le codage de canal Notion de decodage souple et utilisation de LLR

Analyse et traitements dans un systeme decommunication numerique avance

C. Poulliat

4 juin 2012


Plan

1 Comment determiner les performances asymptotiques d’unsysteme ?

Rappels de theorie de l’informationCapacite d’un canal discret sans memoireCapacite d’un canal a entrees et/ou sorties continues

2 Rappel sur le codage de canalQuelques definitions

3 Notion de decodage souple et utilisation de LLRDecodage soupleModulations codees a bits entrelaces


Plan






Entropie, entropie conjointe

X une variable aleatoire discrete a valeurs dans l’alphabet X de d.d.p.p(x) = Prob(X = x), x ∈ X

Entropie

H(X ) = −∑x∈X

p(X = x) log2 (p(X = x))

= −E(log2 p(X )) (1)

Entropie conjointe

H(X ,Y ) = −∑x∈X

∑y∈Y

p(X = x ,Y = y) log2 (p(X = x ,Y = y))

= −E(log2 p(X ,Y )) (2)


Entropie binaire

X ∈ {0,1} avec p(X = 1) = p

H(X ) = −p log2 (p)− (1− p) log2 (1− p) , H2(p)


Entropie conditionnelle et proprietes

Entropie conditionnelle

H(Y |X ) = −∑x∈X

∑y∈Y

p(X = x ,Y = y) log2 (p(Y = y |X = x))

= −E(log2 p(Y |X )) (3)

Proprietes1 0 ≤ H(X ) ≤ log2 |X |

egalite si X uniformement distribue2 H(X ,Y ) = H(X ) + H(Y |X )

3 H(X |Y ) ≤ H(X )egalite si X et Y independants


Information mutuelle

Information mutuelle

I(X ;Y ) = −∑x∈X

∑y∈Y

p(X = x ,Y = y) log2 (p(X = x)p(Y = y)p(X = x ,Y = y)

)

= −E(log2 (p(X )p(Y )

p(X ,Y ))) ≥ 0 (4)

Proprietes

I(X ;Y ) = H(X )− H(X |Y )

= H(Y )− H(Y |X )

= H(X ) + H(Y )− H(X ,Y )

= I(Y ;X ) (5)

I(X ;X ) = H(X )


Interpretations


Plan






Capacite d’un canal discret sans memoireDefinition

Codeur Canal Décodeur

S X Y S estimé

• X ∈ X , Y ∈ Y• Canal sans memoire caracterise par p(Y |X )

Definition

C = maxp(X)

I(X ;Y ) (6)

= maxp(X)

H(X )− H(X |Y ) = maxp(X)

H(Y )− H(Y |X )

Max. atteint pour distribution uniforme pour les canaux symetriques.


Capacite d’un canal discret sans memoireCanal a effacement (BEC)

0

1

0

e

1

1−pe

pe

pe

1−pe

C = 1− pe (7)

atteint pour une distribution d’entree uniforme


Canal binaire symetrique (BSC)

0

1

0

1

1−p

p

p

1−p

C = 1− H2(p) (8)

atteint pour une distribution d’entree uniforme


Theoreme du codage de canalCanal discret sans memoire

Theoreme du codage de canal (1/2)

Soit un canal discret sans memoire de capacite C, on peutcommuniquer a tout debit de transmission inferieur a C. Enparticulier, ∀R < C, il existe un code C(N,R) tel que

C(N,R) : {0,1}NR −→ {0,1}N

telle que la probabilite d’erreur bloc en sortie de decodage optimalsoit arbitrairement petite pour N suffisamment grand.

Interpretation

Communication fiable possible si on considere descommunications codees (quid du cas non code ?)Il existe un code de rendement R < C qui permet decommuniquer de facon fiable,fiable = avec une probabilite d’erreur arbitrairement faible.


Plan






Theoreme du codage de canal (2/2)Canal a temps discret et entrees/sorties continues

Theoreme du codage de canal

• Extension au cas d’entrees ou de sorties continues.• Les expressions precedentes mettent en jeu des densites de

probabilites.• Application principale : le cas du canal Gaussien.


Canal additif gaussien(AWGN)

B(ω)

↓X (ω) −→ ⊕ −→ Y (ω)

(9)

• X (ω) tel que σ2x ≤ P

• B(ω) ∼ N (0, σ2b)

C =12

log2 (1 + σ2x/σ

2b) bits/symbol (10)

=12

log2 (1 + 2RbEb/N0) =12

log2 (1 + 2Es/N0) (11)

max. atteint pour X (ω) ∼ N (0, σ2x = P)


Canal additif gaussien a entrees M-aire (CM-AWGN)Comment calculer cette capacite pour une modulation donnee ? (1/2)

B(ω)

↓X (ω) −→ ⊕ −→ Y (ω)

X (ω) ∈ X = {0, . . . ,M},avec p(X = x) = 1/MB(ω) ∼ CN (0, σ2

b = N0)

Calculer la capacite revient a evaluer

C = I(X ;Y )

Termes a calculer : H(X ), H(X |Y ).


Canal additif gaussien a entrees M-aire (CM-AWGN)Comment calculer cette capacite pour une modulation donnee ? (2/2)

Calcul de H(X ) : H(X ) = 1/MCalcul de H(X |Y ) :

H(X |Y ) = −E(log2 p(X |Y )) = E(h(X |Y ))

orp(X |Y ) =

p(Y |X )∑x∈X p(Y |X = x)

Estimateur de H(X |Y ) : par ergodicite, on a

H(X |Y ) = E(h(X |Y )) = limN→+∞

1N

∑n

h(X (n)|Y (n))

Methode par Monte-Carlo :1 Tirer aleatoirement et uniformement des symboles issue de

constellation,2 Calculer pour chaque couple (X (n),Y (n)), h(X (n)|Y (n)) et

moyenner.


Canal additif gaussien a entrees M-aire (CM-AWGN)Influence du nombre d’echantillonsBPSK Capacity as a Function of

Number of Simulation Trials

Eb/No = 0.2 dB

As N gets large, capacity converges to C=0.5

10 1 10 2 10 3 10 4 10 5 10 60.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

trials

capa

city


Canal additif gaussien a entrees M-aire (CM-AWGN)Exemples

-2 0 2 4 6 8 10 12 14 16 18 200

1

2

3

4

5

6

7

8

Eb/No in dB

Cap

acity

(bits

per

sym

bol)

2-D U

nconst

rained

Capacit

y

256QAM

64QAM

16QAM

16PSK

8PSK

QPSK

Capacity of PSK and QAM in AWGN

BPSK


Canaux selectif en frequence a entrees binaires(BI-ISI)24 Coding and Capacity

–2 0 2 4 6 8 10 120

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Cap

acity

(in

form

atio

n bi

ts/c

ode

bit)

PR1, PR4Proakis' Channel C

BI-AWGN

Eb/N0 (dB)

Figure 1.11 Capacity plots for the BI-AWGN channel, the PR1 and PR4 channels, and Proakis’Channel C.

As examples of applications of this approach, Figure 1.11 compares the capac-ity of the BI-AWGN channel with Ciud for (1) partial-response channels of theform 1±Dν , ν = 1, 2, . . ., which includes the Class I partial response (PR1) poly-nomial 1 +D and the Class IV partial response (PR4) polynomial 1−D2; and(2) Proakis’ Channel C (see Figure 10.2-5(c) in [8]), which is represented by thepolynomial 0.227 + 0.46D + 0.688D2 + 0.46D3 + 0.227D4. Proakis’ Channel C ischaracterized by a spectral null near the middle of the band, so it is not surprisingthat its (Ciud) capacity is significantly less than that of the other channels. ThePR1 channel has a spectral null at DC and the PR4 channel has spectral nullsboth at DC and at the Nyquist frequency (half of the channel bit rate). We observethat these two partial-response channels have the same Ciud curve (which is alsothe curve for all 1±Dν PR channels), and that there is a rate loss relative to theBI-AWGN channel.

Problems

1.1 A single error has been added (modulo 2) to a transmitted (7,4) Hammingcodeword, resulting in the received word r = (1011 100). Using the decoding algo-rithm described in the chapter, find the error.

y [n] =L−1∑k=0

h[k ]x [n − k ] + b[n] (12)

X ∈ X = {−1,+1}, avec p(X = x) = 1/2B ∼ N (0, σ2

b = N0/2)


Comparer l’efficacite des systemes de codage grace a la capacite.Power Efficiency of StandardBinary Channel Codes

Turbo Code1993

OdenwalderConvolutionalCodes 1976

0 1 2 3 4 5 6 7 8 9 10-1-2

0.5

1.0

Eb/No in dB

BPSK Capacity Bound

Cod

e R

ate

r

Shan

non

Capa

city

Boun

d

UncodedBPSK

IS-951991

510−=bP

Spe

ctra

l Effi

cien

cy

arbitrarily lowBER:

LDPC Code2001

Chung, Forney,Richardson, Urbanke


Plan






Codes en bloc lineairesQuelques definitions

On considere des codes definis sur le corps binaire F2 = GF (2).

Codes lineaires en blocs

Un code en blocs binaire C(N,K ) de longueur N est uneapplication g(.) de l’ensemble FK

2 = {0,1}K vers l’ensembleFN

2 = {0,1}N qui associe a tout bloc de donnees u un mot decode c.

g : FK2 → FN

2

u 7→ c = g(u) (13)

# mots de code : 2K .Rendement : R = K/N (K symb. d’inf., N symb. codes).C(N,K ) est dit lineaire si g(.) est une application lineaire (lesmots de codes sont un sous-espace vectoriel de FN

2 ).


Codes en bloc lineairesMatrice generatrice

Matrice generatrice

On note c = [c0, . . . , cN−1] et u = [u0, . . . ,uK−1]

la matrice generatrice G de dimensions K × N est definiecomme etant l’application linaire definie comme

c = uG

Espace du code : Im(C) = {c ∈ FN2 |c = uG, ∀u ∈ FK

2 }rang(G) = K (les lignes de G sont K mots de codesindependants) et G non unique.G est dite systematique si ∀k ∈ [0,K − 1],∃n ∈ [0,N − 1] tel quec[n] = u[k ]. G peut alors se mettre sous la forme

G = [P|IK ]


Codes en bloc lineairesMatrice de parite

Matrice de parite

Le code C⊥(N − K ,K ), dit code dual, verifie que tout mot ducode dual est orthogonal a tout mot du code C(N,K ). On note samatrice generatrice H.On a alors {c ∈ C(N,K )|cH> = 0}Relation avec G : GH> = 0Pour un code systematique, H = [IN−K |P>].Detection d’erreur a l’aide du syndrome : r = c + e

s = rH> = eH>

Si e est un mot de code, alors on parle d’erreurs non detectable.


Codes en bloc lineairesDistance minimum et spectre de distance du code

Matrice de parite

Distance de Hamming : dH(ci , cj) = w(ci ⊕ cj)

Distance minimale :

dmin = min {dH(ci , cj)|ci , cj ∈ C(N,K ); ci 6= cj}= min {w(c)|c ∈ C(N,K ), c 6= 0} (14)

Spectre de distance d’un code :

∀i = 1 . . .N,Ai = #c ∈ C(N,K ), w(c) = i

{A0,A1 . . .AN} est appele spectre de distance du codedmin est egale au plus petit nombre de colonnes dont la sommeest le vecteur nul.dmin − 1 erreurs detectables, b(dmin − 1)/2c erreurs corrigiblessur BSC.


Criteres de decodage

Decodage par Maximum a Posteriori (MAP)

c = arg maxc′

p(c′|y) (15)

= arg maxc′

p(y|c′)p(c′)p(y)

(16)

Decodage par Maximum de Vraisemblance (ML)

c = arg maxc′

p(y|c′) (17)

Exemple de canaux

canal BSC : c = arg minc′ dH(y,c′)canal BI-AWGN : c = arg minc′ dE(y,c′) = arg minc′

∑n (yn − c′n)2


Plan






Decodage ”souple”Utilisation de log-likelihood ratios (LLR)

LLR associe a

l(cn) , log(

P(c[n] = 0|y [n])P(c[n] = 1|y [n])

)LLR en fonction des probabiltes de transitions et a priori :

l(cn) = log(

P(y [n]|c[n] = 0)P(y [n]|c[n] = 1)

)+ log

(P(c[n] = 0)P(c[n] = 1)

)Lien avec critere MAP bit classique en BPSK

cn = arg maxcn

p(c[n]|y [n])

= signe(L(cn)) (18)


Decodage par Maximum de Vraisemblance revisite

BI-AWGN sans a priori : decodeur par correlation

c = arg minc′

∑n

(yn − c′n)2

= arg maxc′

∑n

l(c′n)c′n (19)

oul(c′n) =

2σ2 y [n]

Cas general : canal sans memoire, P(yn|cn), cn = 0,1

c = arg maxc′

∑n

l(c′n)c′n (20)

ouc′n = (1− 2c′n)


Demodulation MAP symbole et bit

Hypotheses

Les vecteurs binaires x [n] = [x1[n] · · · xm[n]] sont “mappes” surdes symboles s[n] ∈ S,Canal sans memoire a entrees M-aires equi-distribues.

Vraisemblance Symbole et critere MAP associe

Symbol Likelihood : P(y [n]|s[n]),MAP Symbole :

sn = arg maxsn

p(y [n]|s[n])

MAP bit

L(xi [n]) = log

(∑s[n]∈S i

0P(y [n]|s[n])P(s[n])∑

s[n]∈S i1P(y [n]|s[n])P(s[n])

)


Plan






Analyse EXIT chartsModulations codees a bits entrelaces

x[n]=[x1[n], …, xm[n]]

Пu[n]

ModulationM‐aire

s[n]

1 m

c[n]Code correcteur

Démodulateury[n]Décodeur canal

MAP Décodeur canal

SISOLext(xi[n])

Lext(C[n])

La(C[n])П‐1

Lext(C[n])

La(xi [n])

П

Bit-Interleaved Coded Modulation

systeme de transmission a haute efficacite spectrale :constellation M-aire S avec M = 2m.Peut-etre vu comme log2(M) canaux parallele,Capacite atteignable depend du mapping utilise :

C = m − 12

m−1∑k=0

1∑c=0

E

(log2

( ∑si∈S p(y |si)∑sj∈Sk

cp(y |sj)

))



932 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 3, MAY 1998

Fig. 4. BICM and CM capacity versus. SNR for 4PSK, 8PSK, and 16QAM over AWGN with coherent detection (SP denotesset-partitioning labeling).

Fig. 5. BICM and CM capacity versus SNR for 4PSK, 8PSK, and 16QAM over Rayleigh fading with coherent detection and perfect CSI (SP denotesset-partitioning labeling).

we conjecture that Gray labeling maximizes BICM capacity)while the performance of BICM with SP labeling is severaldecibels worse. Similar differences between Gray and SPlabelings can also be observed from the cutoff rate of theRayleigh fading channel.

Our next results are based on cutoff rate. This parameterappears to be more suitable than capacity to compare BICMand CM, possibly because there is no fixed relation between

and whereas , as we know from (16). Figs. 6and 7 show BICM and CM cutoff rate versus SNR for QAM

signal sets, over the AWGN and Rayleigh fading channels,respectively. For 4, 16, 64, and 256QAM signal sets we usedGray labeling. For 8, 32, and 128QAM—for which Graylabeling is not possible—we used aquasi-Gray labeling, i.e.,a labeling minimizing the number of signals for which theGray condition (of having at most one nearest neighbor inthe complement subset) is not satisfied. For AWGN, CMoutperforms BICM at all SNR. The performance gap, whichis large for large and low-rate codes, is reduced for high-rate codes. For example, CM256 QAM gains more than 3



CM vs. BICM Capacity for 16QAM

-20 -15 -10 -5 0 5 10 15 20 25 300

0.5

1

1.5

2

2.5

3

3.5

4

Es/No in dB

Cap

acity

CM BICM w/ SP labeling

BICM w/ gray labeling

Documents

Analyse et traitements dans un système de communication