Cours de codes (UE Codes-Signal).pdf

(197 KB) Pobierz
Universit´ Bordeaux I
e
Master CSI 2
Ann´ e 2004-2005
e
Cours de codes (UE Codes/Signal)
Christine Bachoc
Bibliography
[1] J.H. van Lint,
Introduction to coding theory,
3eme edition, Springer
[2] W. C. Huffman, V. Pless,
Fundamentals of error-correcting codes,
Cam-
bridge University Press 2003
[3]
The handbook of Coding Theory
1
Chapter 1
Introduction
La th´ orie des codes s’est d´ velopp´ e pour r´ pondre au probl` me de la correc-
e
e
e
e
e
`
tion des erreurs introduites dans un syst` me de transmission de l’information. A
e
´
l’origine d´ velopp´ e par des ing´ nieurs en electronique, elle constitue maintenant
e
e
e
une branche des math´ matiques discr` tes. Dans le cadre du Master CSI, l’objectif
e
e
´
`
de ce cours est d’initier les etudiants a une autre probl´ matique de la transmission
e
des informations, en insistant sur les applications pratiques, et de d´ velopper les
e
connections de ce sujet avec la cryptographie.
Le support physique utilis´ pour transmettre ou stocker une information (par
e
exemple le t´ l´ phone, l’atmosph` re, l’espace (penser aux communications par
ee
e
satellite), mais aussi la m´ moire d’un ordinateur, les disques compacts, etc..)
e
`
soumet cette information a des distorsions ind´ sirables, ou
bruit,
qui l’alt` rent.
e
e
ˆ
Ce bruit peut etre caus´ par un rayonnement, une alt´ ration du support, des in-
e
e
terf´ rences, etc.. L’information recueillie par le receveur du canal est en g´ n´ ral
e
e e
´
diff´ rente de celle emise par la source. L’objectif de la th´ orie des codes est de
e
e
´
prot´ ger l’information de cet eventuelle alt´ ration.
e
e
En th´ orie de l’information, les caract´ ristiques statistiques du mode de trans-
e
e
mission consid´ r´ sont mod´ lis´ es par le
canal de transmission.
Par exemple, le
ee
e e
u
canal sym´ trique binaire transmet des mots binaires
c
∈
F
n
, o` chaque bit est
e
2
transmis ind´ pendamment, avec une probabilit´
p
d’erreur.
e
e
On peut sch´ matiser grossi` rement la situation de la facon suivante:
e
e
¸
2
Afin d’augmenter la fiabilit´ du canal, c’est-` -dire le taux d’information cor-
e
a
`
rectement transmise, on peut penser a introduire de la r´ p´ tition dans cette in-
e e
formation. Tous les enseignants savent bien que pour transmettre une informa-
`
´e
ˆ
´e e
tion a leurs el` ves, et pour etre sˆ rs que celle-ci n’a pas et´ d´ natur´ e, il ne faut
u
e
`
pas h´ siter a la r´ p´ ter aussi souvent que possible. Sur ce beau principe, imagi-
e
e e
nons que nous voulons envoyer le message binaire suivant :
11111111.
Si nous
l’envoyons deux fois, le receveur pourra comparer les deux versions de notre mes-
`
sage. Si ces deux versions ne sont pas identiques, il peut conclure a l’existence
d’une erreur au moins dans la transmission. Il faut remarquer ici que cet objectif
est aussi atteint en rajoutant seulement un
bit de contrˆ le de parit´
, c’est-` -dire la
o
e
a
`
valeur de la somme des bits modulo
2.
Ici cela donnerait
111111110.
A nouveau,
`
`
si la somme des bits n’est pas
0
modulo
2
a l’arriv´ e, on peut conclure a l’existence
e
d’une erreur au moins. Il est bon de remarquer que, dans le premier cas, le
taux de
´
transmission
du canal, qui est la proportion d’information utile transmise, est egal
`
a
1/2,
tandis que dans le second cas, ce taux vaut
8/9.
Reprenant l’exemple de
la r´ p´ tition, on voit intuitivement que, si le message est r´ p´ t´ un grand nombre
e e
e ee
`
de fois, le receveur pourra “jeter” a coup sˆ r un plus grand nombre de messages
u
erron´ s, et avoir une confiance plus solide en les messages qui ont “l’air” corrects.
e
Un nouveau ph´ nom` ne apparait mˆ me: si le message est r´ p´ t´
r
fois, et que ces
e
e
e
e ee
r
copies ne sont pas toutes identiques, le receveur peut opter pour la version du
message la plus souvent recue.
¸
1.1 Le canal sym´ trique binaire et la th´ orie de Shan-
e
e
non
Le canal sym´ trique binaire (BSC) transmet des mots binaires de longueur
n,
ap-
e
`
e
partenant a un code
C
⊂
F
n
. On suppose que les bits sont transmis ind´ pendamment,
2
et que un bit est transmis correctement avec probabilit´
1
−
p,
incorrectement avec
e
probabilit´
p.
On suppose
p <
1/2
et dans la pratique
p
est petit. (Sch´ ma). On
e
e
´
´
suppose egalement que les mots de
C
sont equiprobables.
Notons
c
la variable al´ atoire repr´ sentant le mot transmis,
y
la variable al´ atoire
e
e
e
repr´ sentant le mot recu. On a:
e
¸
3
n
prob(y
|
c)
=
i=1
prob(y
i
|
c
i
) = (1
−
p)
card{i|y
i
=c
i
}
p
card{i|y
i
=c
i
}
= (1
−
p)
n
p
1
−
p
card{i|y
i
=c
i
}
Un
d´ codeur par maximum de vraisemblance
choisit de renvoyer le mot
c
qui
e
ˆ
maximise
c
∈
C
→
prob(y
|
c).
Comme
p/(1
−
p) <
1,
maximiser
prob(y
|
c)
`
revient a minimiser
card{i
|
y
i
=
c
i
}.
Ainsi, le d´ codeur renvoi un mot du code
e
qui diff` re de
y
sur le moins de coordonn´ es.
e
e
On voit apparaitre ici la notion de
distance de Hamming
entre deux mots:
d
H
(c,
y)
= card{i
|
y
i
=
c
i
}.
Le
taux de transmission
d’un code
C
est par d´ finition
R
= log(|C|)/n.
Il
e
mesure la quantit´ d’information utile transmise. On pourrait penser que la fia-
e
ˆ
bilit´ de la transmission ne peut etre obtenue qu’au d´ triment de ce taux de trans-
e
e
mission. En fait il n’en est rien, comme l’a montr´ Shannon en 1948.
e
`
A tout canal est associ´ une valeur, appel´ e
capacit´
. Sans entrer dans les
e
e
e
d´ tails, la capacit´ du canal BSC est
C(p)
= 1 +
p
log
p
+ (1
−
p)
log(1
−
p).
Soit
e
e
P
err
la probabilit´ d’erreur, c’est-` -dire la moyenne des probabilit´ s que
c
=
c.
e
a
e
ˆ
Th´ or` me 1 (Shannon, 1948)
Soit
R < C(p)
et soit
>
0.
Pour
n
assez grand,
e e
il existe des codes
C
⊂
F
n
de taux de transmission egal a
R,
et tels que
P
err
<
.
´
`
2
Le th´ or` me de Shannon, que nous ne d´ montrerons pas ici, laisse entiers deux
e e
e
`
probl` mes majeurs: D’abord il est purement existentiel, il ne r´ pond donc pas a
e
e
la question de la construction effective de tels codes; ensuite, il ne prend pas en
compte le probl` me algorithmique, qui est surtout celui de r´ aliser un d´ codage
e
e
e
efficace.
4

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin