Chapitre 4 - Codage Canal

Thorie de
lInformation et
Codage
Pr. Hicham Ghennioui
Email: [email protected]
Universit Sidi Mohammed Ben Abdellah
Facult des Sciences et Tchnique - Fs
Dpatement Gnie Electrique
Labaratoire Signaux, Systmes et Composants
Plan du cours
Chap. 1 Elments de la
linformation
Chap. 2 Signaux et sources
Cours. 2 Codage de source
Cours. 3 Codage de canal
Pr H. Ghennioui
thorie
de
Chapitre -4-
CODAGE CANAL
Introduction gnrale (1/2)
Dans un canal bruit (H(Y/X) 0)

l'observation des symboles de sortie du canal est
affecte d'erreurs de transmission.
Rappel :
Objectif du codage canal:

Lutter efficacement contre les erreurs de transmission qui
affectent les symboles individuels.
En groupant les symboles en mots de code dans lesquels on
introduit de la redondance (rptition de l'information) dont on
utilisera les proprits pour corriger tout ou partie des erreurs de
symbole. Donc le codage canal consiste former des mots de
code de canal que nous dsignerons par i et qui sont
constitus de n symboles de l'alphabet d'entre.
i ai1 , ai2 , , ain

4
Introduction gnrale (2/2)
Le codage canal consiste transformer le mot code source

Xi de k bits un mot code canal i de n bits.
i (n bits)
Xi (k bits)
A la sortie du canal, on reoit une squence j de n

symboles bj appartenant l'alphabet de sortie:
j b j1 , b j2 , , b jn
Rgle de dcision (1/2)
A la rception, le dcodage aura pour fonction de

reconnatre les mots de code envoys sur le canal.
i (2k)
CANAL
j (2n)
Rgle de
dcision
mj
p=P(bj/ai)
d(j)=mj
Le dcodeur devra disposer d'une rgle de
dcision qui lui permettra, par observation de la
squence reue, d'identifier le mieux possible le
mot de code envoy l'entre du canal.
6
Rgle de dcision (2/2)
La rgle de dcision est un critre qui, toute

squence de sortie j, fait correspondre un mot
mj dtermin parmi tous les mots i du code
d'entre:
d j mj
Probabilit derreur de
dcodage (1/2)
Si P(E/ j) est la probabilit de faire un dcodage

incorrect lorsqu'on reoit la squence j (qui dpend de
la rgle de dcision). La probabilit pour que le mot de
code mj, choisi par la rgle de dcision, soit
effectivement le mot de code envoy sur le canal vaut
P mj j
tel que:
P E j 1 P mj j
Codes correcteurs derreurs

(1/7)
Objectif : Construire de bons codes avec des circuits

de complexit modre.
Hypothses :
Canal de transmission : canal symtrique binaire - CSB,

de probabilit d'erreur de symbole p
Alphabet dentre : M messages quiprobables

(2/7)
Deux grandes familles,
Les codes en bloc : le codage/dcodage dun bloc

dpend uniquement des informations de ce bloc. Ils
sont utiliss dans les rseaux informatiques.
Les codes en treillis ou convolutifs : le
codage/dcodage
dun
bloc
dpend
des
informations dautres blocs (gnralement des blocs
prcdemment transmis). Ils sont utiliss dans le
cas des liaisons satellites ou terrestres (milieux trs
bruits).
10

(3/7)
Vocabulaire & dfinitions
Mot de code de canal: il est de longueur n form partir du mot

de code source de longueur k (M = 2k).
Symboles de contrle
k symboles binaires
(n-k) symboles binaires
Les symboles de contrle sont appels aussi symboles de parit.
Le code est not C(n,k). Le rendement dun code est R=k/n

Poids dun code : cest par dfinition le nombre de caractres non
nuls que contient le mot code.
Exemples: 11011000 est de poids

4, 00000000
Un code est dit de poids fixe (ou poids constant) si tous les mots
du code ont le mme poids.
Symboles dinformation
11

(4/7)
Vocabulaire & dfinitions
Distance de Hamming: la distance de Hamming dij entre deux

mots de code est le nombre de bits dont ils diffrent (Astuce =
nombre de 1 du OU exclusif).
Exemple: 11001000 et 10011010 ont une distance
de 3.
Distance minimale du code : cest le minimum de l'ensemble

des distances entre codes :dmin = min { dij }
Exemples: DH1 ( {110, 101, 011} ), DH2 ( {0011, 0101, 1001, 0110,
1010, 1100 } ) .
DH1 = DH2=2
Code linaire: un code est linaire s'il rpond au principe de

superposition : ai Ci + aj Cj = Ck
Pour un code linaire, le poids minimal est gal la distance

minimale.
12

(5/7)
Pouvoir dtecteur dun
code
Dfinition: On parle derreur dordre k lorsquun mot

mis u diffre par k bits du mot reu v, i.e. dh(u,v) = k.
Pour dtecter une erreur dordre 1, quelle doit tre la

distance de Hamming du code ?
Rponse : DH(C) = 2. En effet, dans ce cas, une erreur

simple ne peut pas changer un mot du code en un autre
mot du code.
Gnralisation : la distance de Hamming du code pour

dtecter une erreur dordre k est :DH(C) = k+1.
13

(6/7)
Pouvoir correcteur dun
code
Pour pouvoir corriger une erreur dordre 1, une distance

de Hamming DH(C) = 2 est-elle suffisante ?
Rponse :non. il faut DH(C) = 3. En effet, si DH(C) = 2, une erreur

simple peut nous produire un mot exactement au milieu de 2
mots du code, distance 1 de chacun !
si DH(C) = 3, une erreur simple produit un mot qui reste le plus
proche du mot transmis : on peut donc le retrouver !
Gnralisation : pour corriger une erreur dordre k, il

faut DH(C) = 2k+1.
14

(7/7) dun code
Rsum dtecteur-correcteur
Un code C peut,
dtecter des erreurs dordre DH(C) 1
corriger des erreurs dordre (DH(C) 1)/2 (partie entire)
Distance de
Hamming du code
Ordre maximal des

erreurs dtectables
Ordre maximal des

erreurs corrigibles
2
15
Exemples de codes
dtecteurs
(1/3)
Codage pour
la dtection sans
correction
Quand un canal bidirectionnel existe entre la source et la

destination,
le
rcepteur
peut
demander
la
retransmission dinformation avec des erreurs dtectes.
Cest une stratgie appele la requte automatique de
retransmission (ARQ: Automatic Repeat Request).
Il est utilis en particulier par des systmes de
communications de donnes tels que des rseaux
informatiques.
Il requiert moins de bits de redondance.
16
Exemples de codes
dtecteurs
(2/3) Check ou
Contrle de
parit (Vertical Redundancy
Vertical Redundancy Checking)
Principe: ajouter un bit supplmentaire (bit de parit)

un mot de code (gnralement 7 bits) : un 1 si le nombre
de bits du mot de code est impair, 0 dans le cas
contraire.
Exemple:
Proprit: dtecte les erreurs qui sont d'ordre impair.
Inconvnients:
il ne permet de dtecter que 50% des erreurs.

Il ne permet pas de corriger les erreurs dtectes (il exige la
retransmission de loctet erron).
17
Exemples de codes
dtecteurs
(3/3)de redondance
Contrle de
parit crois (contrle
longitudinale ou Longitudinal Redundancy Check,
not LRC)
Principe: contrler l'intgrit des bits de parit d'un bloc

de caractres et non pas seulement dun mot-code
(caractre).
Exemple:
18
Codes contrle de parit

Principe : Relations(1/22)
linaires entre les symboles de
contrle et les symboles d'information.
En arithmtique modulo 2, la linarit est quivalente

des tests de parit.
Reprsentation matricielle:
Mot de code source :
X x1 , x2 , , xk
Mot de code de canal:
a1 , a2 , , ak , ak 1 , , an
Condition de linarit :
ai
x g
l
l 1
l ,i
i 1,2 , , n
O les gl,i sont des coefficients binaires, et les multiplications et

additions sont faites modulo-2.
19

(2/22)
Cas des codes systmatiques
g l ,i l , i
ai
1 i k
xi
x g
l
l 1
lorsque
l ,i
lorsque
1 i k
k 1 i n
20

Matrice gnratrice(3/22)
X G
G gli
g11 g1n

gk 1 gkn
l 1,2 , , k
i 1,2 , , n
O [G] est une matrice k lignes et n colonnes.
21

(4/22)
Codes systmatiques
G gli
1 0 0 g1, k 1 g1n

0 0 1 gk , k 1 gkn
avec gl ,i l ,i Lorsque
Ou encore :
G Ik
l 1,2 , , k
i 1,2 , , n
1 i k
p11 p1, n k
P
pk 1 pk , n k
22

(5/22)
Thorme: Les mots
d'un code contrle de parit
sont des combinaisons linaires des lignes de la
matrice gnratrice de ce code.
k
i uj g j
j 1
i 1,2 , ,2 k
A tout code linaire correspond un code contrle

systmatique de parit.
23

Exemple: Code bloc(6/22)
linaire systmatique avec k = 4
et n = 7. Le nombre de mots de code source tant
24=16
24

Exemple: (suite) (7/22)
G 4, 7 I 4
a1
a
2
a3
a4
x1
x2
x3
x4
1
0
P4,3
0
0
1
0
0
0
0
1
0
0
0
0
1
1
0
1
1
1
1
1
0
0
1
1
a5 x1 x3 x4
a6 x1 x2 x3
a x x x
2
3
4
7
25

(8/22)
Matrice de contrle : cest une matrice [H] n lignes et
(n-k) colonnes telle que :
G H O
Cas dun code contrle systmatique de parit :
P
H I
n k
p11 p1, n k

pk 1 pk , n k
0 0

0 0 1
1 0 0

0 0 1
C d.
g1, k 1 g1n

gk , k 1 gkn
H 1
26

(9/22)
Thorme: Le produit
d'un mot quelconque du code
canal par la matrice de contrle est un vecteur (n-k)
lments identiquement nul:
H o
Rciproquement, toute squence , , n lments dont

le produit par la matrice de contrle est identiquement nul,
appartient au code canal.
27

(10/22)
Exemple: Code bloc
linaire systmatique avec k = 4 et n
= 7.
H 7 ,3
1
0
1
P4,3
I3 1
0
0
1
1
1
0
0
1
0
0
1
1
1
0
0
1
G 4, 7 H 7 ,3 O 4,3
0
0
0
0
0
0
0
0
0
28
Codes contrle de
parit(11/22)
(mot de code )
vers le canal
Entre
xk
[X]
x2
x1
xk
x2
x1
xk
x2
x1
pk,n-k
p2,n-k
p1,n-k
pk,1
p2,1
p1,1
an
ak+1
vers le canal
Circuit de codage dun code linaire systmatique 29
Codes contrle de
parit(12/22)
Exemple: Code
bloc linaire systmatique avec k = 4 et n
= 7.
Entre
[X]
x4
x2
x3
x1
x1
x2
x3
x4
vers
le canal
a7
a6
a5
30

(13/22)
Syndrome: Squence reue aprs transmission d'un mot
de code sur un canal bruit :
b1 , b2 , , bn
En gnral, ne fait pas partie du code :
H S s1 , s 2 , , s n k 0
S vecteur (n-k) lments : syndrome de la transmission,
avec
sj
de contrle de parit
h
bquations
l
l 1
l, j
j 1,2 , , n k
31

(14/22)
Circuit de calcul de syndrome dun code linaire
systmatique (n,k)
Squence
reue
bn
bn
b2
bk
b2
b1
pk,n-k
p2,n-k
p1,n-k
sn-k
bk+1
b1
bk
b2
b1
pk,1
p2,1
p1,1
s1
32

(15/22)
Exemple : Code bloc linaire systmatique avec k = 4
et n = 7.
Squence reue
[]
b7
b6
b5
b4
b3
b2
b1
b1
b2
b3
b4
b5
b6
b7
s3
s2
s1
33

(16/22)
Exemple : Code bloc linaire systmatique avec k = 4 et n
= 7.
H 7 ,3
1
0
1
P4,3
I3 1
0
0
1
1
1
0
0
1
0
0
1
1
1
0
0
1
Dterminer les quations de

contrle de parit,
s1 b1 b3 b4 b5
s2 b1 b2 b3 b6
s b b b b
2
3
4
7
3
34

(17/22)
Syndrome:
si c est un code alors cH=0.

Soit le mot reu y tel que y=c+e o e comporte des 1 l o une
erreur a t commise. Le syndrome scrit alors,
s(y)=s(c+e)=(c+e)H=cH+eH=eH.
Le syndrome ne dpend que de lerreur (maladie) mais ne pas du
mot reu (le patient).
Le procdure de dcodage du mot reu y se rsume de la manire
suivante:
Si s(y)=0, y est un mot code.
Sinon, on recherche la squence z de longueur n de poids
minimum telle que zH=s(y) et on dcode y en c=y+z.
35

(18/22)
Construction de la table
de dcodage
Le problme consiste trouver z de poids minimum vrifiant

zH=s(y).
La table est construite comme suit:
On liste les q(n-k) valeurs possibles de s du syndrome et on recherche

pour chacune la squence z de longueur n de poids minimum vrifiant
zH=s.
Le plus simple est de commencer par z=0 puis de faire correspondre
une valeur s aux z de poids 1, puis aux z de poids 2, On sarrte
lorsque toutes les valeurs de s ont un z correspondant.
Comme on choisit le mot code c tel que c=y+z, les erreurs corriges
sont celles apparaissent dans la table. En consquent la probabilit
derreur lie a cette stratgie de dcodage est la probabilit des
squences derreurs qui ne figurent pas dans la table.
Note : le mot est crit dans la 2me colonne si la 1re fois que le
syndrome apparat.
36

(19/22)
Exemple 1 : Code bloc linaire systmatique avec k = 4 et
n = 7.
H 7 ,3
1
0
1
P4,3
I3 1
0
0
1
1
1
0
0
1
0
0
1
1
1
0
0
1
Dterminer les valeurs des

syndromes possibles,
Syndrome
Sequence z
000
0000000
001
0000001
010
0000010
011
0000011
100
0000100
101
0000101
110
0000110
111
0000111
37

(20/22)
Exemple 1: (suite)
On suppose que lon reoive le mot y=1101111. Dcoder y.

zH=s(y) conduit la valeur 111. La table de dcodage permet
de dterminer z=0000111. Le dcodage de y est
c=y+z=11010000.
38

(21/22)
Exemple 2: Code de Hamming
Dfinition : cest un code systmatique tel que n=2m-1

et k=2m-m-1 (n-k=m).
Principe de construction : dH(C)=3 et les lignes de la
matrice de contrle H sont toutes distinctes et non
nulles.
Autocorrection: le syndrome du mot reu est identique
la colonne de la matrice de contrle correspondant au
bit corriger.
39

(22/22)
Exemple 2: illustration
Calculer la matrice gnratrice puis les syndromes des
codes reus suivants :
c1=[0 0 1 0 1 1 1], c2=[0 0 1 0 1 1 0], c3=[0 0 0 1 1 1 1]
c1H= [0 0 0], i1= [0 0 1 0].

c2H=[0 0 1], erreur sur le dernier bit, i2=[0 0 1 0].
c3H=[1 0 1], erreur sur le 5me bit, i3=[0 0 0 1] .
40
Conclusion sur la technique

matricielle
La mthode matricielle impose de travailler sur des
mots de taille fixe, ce qui est un inconvnient majeur
pour les rseaux informatiques o les messages sont
de taille variable.
41
Codes polynomiaux (1/5)
Notation : tout vecteur peut tre prsent sous une forme

polynmiale,
U = <u0,u1,u2,...,un>
U(x) = u0+u1.x+u2.x2+...+un.xn
Avec les oprations sont binaires,
Somme polynmiale :
Produit polynmial :
Produit vectoriel
Exemple : <x3+1> . <x+1> = <x4+x3+x+1>
Division polynmiale
Somme deux deux de chaque coefficient (somme vectorielle).

Exemple : <x3+1> + <x4+x2+1> = <x4+x3+x2>.
Exemple : <x4+x3+x2+1> / <x+1> = <x3+ x+1>
Modulo : <x4+x3+x2+x+1> // <x+1> = 1
42
Dfinition: Un code polynmial est un code linaire dont

chacun des mots du code est un multiple dun polynme
gnrateur (not g(x)).
les lignes de la matrice gnratrice sont engendres par
le polynme gnrateur et le degr du polynme est gal
la longueur du champ de contrle derreur.
Exemple:
Soit le polynme gnrateur : g(x) = x+1, on sintresse un code

C(3,2) (les calculs se feront modulo x3+1),
1 et x sont pris comme coefficients multiplicateurs,
premire ligne : (g(x). 1)//(x3+1) = x+1
deuxime : (g(x).x)//(x3+1) = x2+x
ce qui donne la matrice gnratrice suivante :
43

Principe de codage : Le mot de code c(x) dun code
polynmial (n, k) de polynme gnrateur g(x) associ au
mot initial m(x) est dfini par :
c(x) = m(x). xn-k + r(x),
o r(x) est le reste de la division de m(x).xn-k par le polynme
gnrateur g(x) (not : r(x) = m(x).xn-k//g(x) ).
Remarques:
Les r = n-k bits de r(x) (de degr n-k-1) forment les bits du
champ de contrle.
Les bits de poids fort (de degr > n-k-1) forment le mot initial
(code systmatique).
Lopration de codage effectue lmission est ramene
une division polynmiale, qui peut tre ralise simplement
(lectroniquement).
44

Exemple:
Code polynmial C(5,4) de polynme gnrateur g(x)= x+1.
m(x) = x3 + x + 1
m(x). x = x4 + x2 + x
r(x) = (x4 + x2 + x) // (x+1) = 1
c(x) = x4 + x2 + x + 1
Principe de Dcodage: A la rception, chaque mot reu
c(x) est divis par le polynme gnrateur g(x).
Un reste non-nul indique quil y a eu erreur lors de la
transmission.
Syndrome de c(x) : c(x)//g(x) 0
Erreur !
Attention: Si le reste est nul cela ne veut pas dire quil ny a
pas eu derreurs.
45
Exemple:
c(x) = x4 + x2 + x + 1
S(c(x)) = c(x) // g(x) = (x4 + x2 + x + 1) // (x+1) = 0
d'erreur dtecte.
pas
Schma lectronique dun diviseur polynmial:
La multiplication est ralise par un ET logique, laddition par un OU

exclusif, plus des registres dcalage.
Le diviseur : g(x) = g0+g1.x+g2.x2+...+gn-k.xn-k
- les registres ri sont mis zros
- les bits du mot diviser sont
insrs en entre (k tapes), bits de
poids fort en tte.
- les registres ri contiennent alors le
reste, quon extrait (n-k tapes).
46
Codes cycliques (1/10)
Dfinition: Un code cyclique (n, k) est un code linaire (n,

k) tel que toute permutation circulaire dun mot du code est
encore un mot du code.
Exemples:
Un code cyclique (2, 1) possde les mots de code suivants :

{01, 10} ou {00, 11}, mais pas {01, 11}.
Un code cyclique (3, 1) possde les mots de code suivants :
{000, 111}.
Un code cyclique (n, k) est un code polynmial dont le polynme

gnrateur divise xn + 1.
Les dispositifs de codage et de dcodage sont identiques ceux
des codes polynmiaux.
47
Les codes cycliques (n, k) dont le polynme gnrateur est

primitif et tel que n=2n-k + 1, sont des codes de Hamming.
On appelle priode du polynme H(x) le plus petit entier
u tel que H(x) divise xu+1.
Un polynme est irrductible sil ne possde aucun
diviseur de degr suprieur zro.
Si la priode dun polynme irrductible est gale n-k
alors le polynme est dit primitif.
48
Capacit de dtection des erreurs:
Un code cyclique (n, k) dont le polynme gnrateur au

moins 2 coefficients non-nuls (donc il ne divise pas xi, i<n)
permet de dtecter toutes les erreurs simples.
Si le polynme gnrateur dun code cyclique (n, k) a un
facteur irrductible de trois termes (il ne divise ni xi ni 1 + xj-i,
i<j<n), le code permet de dtecter les erreurs doubles.
par exemple : g(x) = x3 + x + 1
Pour quun code polynmial dtecte toutes les erreurs dordre
impair, il suffit que son polynme gnrateur ait (x+1) comme
facteur.
par exemple : le code de polynme gnrateur (x+1), qui
est quivalent la parit.
49

Capacit de dtection des paquets derreurs :
Un code cyclique (n, k) permet de dtecter toutes les erreurs
dordre 1 n-k (cest--dire infrieur au degr du polynme
gnrateur).
Et la probabilit de ne pas dtecter les erreurs dordre 1>n-k
est trs faible et gale : 2-(n-k).
50
Contrle
de
redondance
Redundancy Check, not LRC)
cyclique
(Cyclic
Principe: A chaque trame est associ un bloc de

donnes, appel code de contrle (parfois CRC par abus
de langage ou FCS pour Frame Check Sequence dans le
cas d'un code de 32 bits). Le code CRC contient des
lments redondants vis--vis de la trame, permettant de
dtecter les erreurs, mais aussi de les rparer.
51
Contrle de redondance cyclique
Principe: Le principe du CRC consiste traiter les squences

binaires comme des polynmes binaires, c'est--dire des polynmes
dont les coefficients correspondent la squence binaire. Ainsi la
squence binaire 0110101001 peut tre reprsente sous la forme
polynomiale suivante :
0*X9 + 1*X8 + 1*X7 + 0*X6 + 1*X5 + 0*X4 + 1*X3 + 0*X2 + 0*X1 + 1*X0 soit X8 +
X7 + X5 + X3 + X0 ou encore X8 + X7 + X5 + X3 + 1
Toutes les expressions polynomiales sont manipules par la suite avec une
arithmtique modulo 2.
Dans ce mcanisme de dtection d'erreur, un polynme prdfini (appel
polynme gnrateur et not G(X) est connu de l'metteur et du rcepteur.
La dtection d'erreur consiste pour l'metteur effectuer un algorithme sur
les bits de la trame afin de gnrer un CRC, et de transmettre ces deux
lments au rcepteur. Il suffit alors au rcepteur d'effectuer le mme calcul
afin de vrifier que le CRC est valide.
52
Application pratique:
Soit M le message correspondant aux bits de la trame envoyer

et M(X) le polynme associ. Appelons M' le message transmis,
c'est--dire le message initial auquel aura t concatn le CRC
de n bits. Le CRC est tel que M'(X)/G(X)=0. Le code CRC est
ainsi gal au reste de la division polynomiale de M(X) (auquel on
a pralablement concatn n bits nuls correspondant la
longueur du CRC) par G(X).
Prenons le message M de 16 bits suivant : 1011 0001 0010 1010
Prenons G(X) = X3 + 1 (reprsent en binaire par 1001). Etant
donn que G(X) est de degr 3, il s'agit d'ajouter 4 bits nuls M :
10110001001010100000. Le CRC est gal au reste de la division
de M par G (1001) : 0011.
53
Application pratique:
Pour crer M' il suffit de concatner le CRC ainsi obtenu aux bits
de la trame transmettre :
M' = 1011000100101010 + 0011 M' = 10110001001010100011
Ainsi, si le destinataire du message effectue la division de M' par
G, il obtiendra un reste nul si la transmission s'est effectue sans
erreur.
54

Polynmes gnrateurs:
Les polynmes gnrateurs les plus couramment employs
sont :
CRC-12 : X12 + X11 + X3 + X2 + X + 1
CRC-16 : X16 + X15 + X2 + 1
CRC CCITT V41 : X16 + X12 + X5 + 1
(Ce code est notamment utilis dans la procdure HDLC.)
CRC-32 (Ethernet) : X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 +
X 8 + X7 + X 5 + X 4 + X2 + X + 1
55
Codes correcteurs performants
Les codes BCH (Bose-Chaudhuri-Hocquenghem) sont

ceux qui ont la plus grande capacit de correction derreurs
indpendantes pour une redondance et une longueur
donnes. Leur rendement nest pas trs lev. Ce sont une
extension des codes cycliques, ils sont non pas construit
sur un alphabet binaire mais un alphabet compos dun
grand ensemble de symboles.
Les codes RS (Reed-Solomon) sont des codes correcteurs
trs puissants. Ils peuvent tre prsents comme des
codes BCH dans lequel chaque bit des mots du code est
remplac par un entier dfini modulo 2v (avec n=2v-1). La
distance dun code RS(m, n) est gale n-m+1.
56

Chapitre 4 - Codage Canal

Transféré par

Droits d'auteur :

Formats disponibles

Chapitre 4 - Codage Canal

Transféré par

Informations du document

Description originale:

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Chapitre 4 - Codage Canal

Transféré par

Droits d'auteur :

Formats disponibles

Thorie de

Introduction gnrale (1/2)

Dans un canal bruit (H(Y/X) 0)

Objectif du codage canal:

i ai1 , ai2 , , ain

Introduction gnrale (2/2)

Le codage canal consiste transformer le mot code source

A la sortie du canal, on reoit une squence j de n

Rgle de dcision (1/2)

A la rception, le dcodage aura pour fonction de

Rgle de dcision (2/2)

La rgle de dcision est un critre qui, toute

Si P(E/ j) est la probabilit de faire un dcodage

Codes correcteurs derreurs

Objectif : Construire de bons codes avec des circuits

Canal de transmission : canal symtrique binaire - CSB,

Codes correcteurs derreurs

Les codes en bloc : le codage/dcodage dun bloc

Codes correcteurs derreurs

Mot de code de canal: il est de longueur n form partir du mot

(n-k) symboles binaires

Les symboles de contrle sont appels aussi symboles de parit.

Le code est not C(n,k). Le rendement dun code est R=k/n

Exemples: 11011000 est de poids

Codes correcteurs derreurs

Distance de Hamming: la distance de Hamming dij entre deux

Exemple: 11001000 et 10011010 ont une distance

Distance minimale du code : cest le minimum de l'ensemble

Code linaire: un code est linaire s'il rpond au principe de

Pour un code linaire, le poids minimal est gal la distance

Codes correcteurs derreurs

Dfinition: On parle derreur dordre k lorsquun mot

Pour dtecter une erreur dordre 1, quelle doit tre la

Rponse : DH(C) = 2. En effet, dans ce cas, une erreur

Gnralisation : la distance de Hamming du code pour

Codes correcteurs derreurs

Pour pouvoir corriger une erreur dordre 1, une distance

Rponse :non. il faut DH(C) = 3. En effet, si DH(C) = 2, une erreur

Gnralisation : pour corriger une erreur dordre k, il

Codes correcteurs derreurs

dtecter des erreurs dordre DH(C) 1

corriger des erreurs dordre (DH(C) 1)/2 (partie entire)

Ordre maximal des

Ordre maximal des

Quand un canal bidirectionnel existe entre la source et la

Principe: ajouter un bit supplmentaire (bit de parit)

il ne permet de dtecter que 50% des erreurs.

Principe: contrler l'intgrit des bits de parit d'un bloc

Codes contrle de parit

En arithmtique modulo 2, la linarit est quivalente

Mot de code source :

Mot de code de canal:

O les gl,i sont des coefficients binaires, et les multiplications et

Codes contrle de parit

Codes contrle de parit

O [G] est une matrice k lignes et n colonnes.

Codes contrle de parit

Codes contrle de parit

A tout code linaire correspond un code contrle