1. Introduction sur les codes correcteurs - Infoscience - EPFL
Dans le domaine de la théorie de l'information, les codes sont utilisés pour
détecter et corriger les erreurs de transmission. En effet, lorsqu'une source
souhaite ...
part of the document
Finite fields
And
Error-correcting codes
Etudiante : Nelly Burrin
Master en systèmes de communication
Projet de semestre, été 2006
Prof. Amin Shokrollahi
Assistant: Andrew Brown
Laboratoire d'algorithmique
SOMMAIRE
TOC \o "1-3" \h \z \u HYPERLINK \l "_Toc139368214" SOMMAIRE PAGEREF _Toc139368214 \h 3
HYPERLINK \l "_Toc139368215" 1. Introduction sur les codes correcteurs : PAGEREF _Toc139368215 \h 5
HYPERLINK \l "_Toc139368216" 1.1. Intérêt : PAGEREF _Toc139368216 \h 5
HYPERLINK \l "_Toc139368217" 1.2. Définition mathématique des codes: PAGEREF _Toc139368217 \h 5
HYPERLINK \l "_Toc139368218" 1.3. Caractéristiques d'un code : PAGEREF _Toc139368218 \h 6
HYPERLINK \l "_Toc139368219" 1.4. Exemples de codes simples : PAGEREF _Toc139368219 \h 7
HYPERLINK \l "_Toc139368220" 1.4.1. Code répétitif : PAGEREF _Toc139368220 \h 7
HYPERLINK \l "_Toc139368221" 1.4.2. Parity Check code : PAGEREF _Toc139368221 \h 7
HYPERLINK \l "_Toc139368222" 2. Notions d'algèbre : PAGEREF _Toc139368222 \h 8
HYPERLINK \l "_Toc139368223" 2.1. Théorie des anneaux et des corps : PAGEREF _Toc139368223 \h 8
HYPERLINK \l "_Toc139368224" 2.1.1. Les anneaux : PAGEREF _Toc139368224 \h 8
HYPERLINK \l "_Toc139368225" 2.1.2. Les corps : PAGEREF _Toc139368225 \h 9
HYPERLINK \l "_Toc139368226" 2.1.3. Les idéaux : PAGEREF _Toc139368226 \h 10
HYPERLINK \l "_Toc139368227" 2.2. Les corps finis : PAGEREF _Toc139368227 \h 10
HYPERLINK \l "_Toc139368228" 2.2.1. Construction d'un corps fini : PAGEREF _Toc139368228 \h 10
HYPERLINK \l "_Toc139368229" 2.2.2. Exemple: PAGEREF _Toc139368229 \h 11
HYPERLINK \l "_Toc139368230" 3. Codes linéaires : PAGEREF _Toc139368230 \h 13
HYPERLINK \l "_Toc139368231" 3.1. Définition : PAGEREF _Toc139368231 \h 13
HYPERLINK \l "_Toc139368232" 3.1.1. Définition générale des q-ary codes: PAGEREF _Toc139368232 \h 13
HYPERLINK \l "_Toc139368233" 3.1.2. Cas particulier des codes binaires : PAGEREF _Toc139368233 \h 13
HYPERLINK \l "_Toc139368234" 3.2. Matrice génératrice (generator matrix) : PAGEREF _Toc139368234 \h 14
HYPERLINK \l "_Toc139368235" 3.3. Matrice de vérification (parity-check matrix) : PAGEREF _Toc139368235 \h 14
HYPERLINK \l "_Toc139368236" 3.4. Distance minimum: PAGEREF _Toc139368236 \h 15
HYPERLINK \l "_Toc139368237" 3.4.1. Définition : PAGEREF _Toc139368237 \h 15
HYPERLINK \l "_Toc139368238" 3.4.2. Calcul de la distance minimale d'un code : PAGEREF _Toc139368238 \h 16
HYPERLINK \l "_Toc139368239" 3.5. Détection et correction des erreurs : PAGEREF _Toc139368239 \h 17
HYPERLINK \l "_Toc139368240" 3.5.1. Mécanisme de décodage d'un mot : PAGEREF _Toc139368240 \h 17
HYPERLINK \l "_Toc139368241" 3.5.2. Distance minimale et capacité de détection et correction d'erreurs : PAGEREF _Toc139368241 \h 18
HYPERLINK \l "_Toc139368242" 3.6. Bornes caractérisant les codes : PAGEREF _Toc139368242 \h 19
HYPERLINK \l "_Toc139368243" 3.6.1. Singleton Bound: PAGEREF _Toc139368243 \h 19
HYPERLINK \l "_Toc139368244" 3.6.2. Sphere Packing Bound: PAGEREF _Toc139368244 \h 20
HYPERLINK \l "_Toc139368245" 3.7. Exemple : les codes de Hamming : PAGEREF _Toc139368245 \h 21
HYPERLINK \l "_Toc139368246" 3.7.1. Cas général des q-ary codes de Hamming: PAGEREF _Toc139368246 \h 21
HYPERLINK \l "_Toc139368247" 3.7.2. Cas particulier des codes de Hamming binaires: PAGEREF _Toc139368247 \h 23
HYPERLINK \l "_Toc139368248" 4. Les codes cycliques: PAGEREF _Toc139368248 \h 26
HYPERLINK \l "_Toc139368249" 4.1. Description: PAGEREF _Toc139368249 \h 26
HYPERLINK \l "_Toc139368250" 4.1.1. Définition: PAGEREF _Toc139368250 \h 26
HYPERLINK \l "_Toc139368251" 4.1.2. Représentation polynomiale des mots de code: PAGEREF _Toc139368251 \h 26
HYPERLINK \l "_Toc139368252" 413. Définition des codes avec les représentations polynomiales: PAGEREF _Toc139368252 \h 27
HYPERLINK \l "_Toc139368253" 4.2. Construction du code: PAGEREF _Toc139368253 \h 28
HYPERLINK \l "_Toc139368254" 4.2.1. Polynôme générateur: PAGEREF _Toc139368254 \h 28
HYPERLINK \l "_Toc139368255" 4.2.2. Propriétés importantes de g(x): PAGEREF _Toc139368255 \h 29
HYPERLINK \l "_Toc139368256" 4.2.3. Exemple: PAGEREF _Toc139368256 \h 30
HYPERLINK \l "_Toc139368257" 4.3. Matrices génératrice et de vérification: PAGEREF _Toc139368257 \h 31
HYPERLINK \l "_Toc139368258" 4.3.1. Matrice génératrice : PAGEREF _Toc139368258 \h 31
HYPERLINK \l "_Toc139368259" 4.3.2. Matrice de vérification : PAGEREF _Toc139368259 \h 32
HYPERLINK \l "_Toc139368260" 4.4. Codage et détection des erreurs: PAGEREF _Toc139368260 \h 32
HYPERLINK \l "_Toc139368261" 4.4.1. Code non systématique: PAGEREF _Toc139368261 \h 33
HYPERLINK \l "_Toc139368262" 4.4.2. Code systématique: PAGEREF _Toc139368262 \h 33
HYPERLINK \l "_Toc139368263" 4.4.3. Exemple: PAGEREF _Toc139368263 \h 33
HYPERLINK \l "_Toc139368264" 4.4.4. Détection des erreurs: PAGEREF _Toc139368264 \h 34
HYPERLINK \l "_Toc139368265" 4.5. Racines d'un code cyclique et distance minimum : PAGEREF _Toc139368265 \h 35
HYPERLINK \l "_Toc139368266" 4.5.1. Racines du polynôme générateur: PAGEREF _Toc139368266 \h 35
HYPERLINK \l "_Toc139368267" 4.5.2. Distance minimale d'un code cyclique: PAGEREF _Toc139368267 \h 36
HYPERLINK \l "_Toc139368268" 4.5.3. Exemple: PAGEREF _Toc139368268 \h 37
HYPERLINK \l "_Toc139368269" 5. Les codes BCH : PAGEREF _Toc139368269 \h 40
HYPERLINK \l "_Toc139368270" 5.1. Historique : PAGEREF _Toc139368270 \h 40
HYPERLINK \l "_Toc139368271" 5.2. Description et construction des codes : PAGEREF _Toc139368271 \h 40
HYPERLINK \l "_Toc139368272" 5.2.1. Caractéristiques générales de ces codes: PAGEREF _Toc139368272 \h 40
HYPERLINK \l "_Toc139368273" 5.2.2. Définition: PAGEREF _Toc139368273 \h 40
HYPERLINK \l "_Toc139368274" 5.2.3. Construction: PAGEREF _Toc139368274 \h 41
HYPERLINK \l "_Toc139368275" 5.2.4. 524. Exemple: PAGEREF _Toc139368275 \h 41
HYPERLINK \l "_Toc139368276" 5.3. Décodage des codes BCH binaires: PAGEREF _Toc139368276 \h 42
HYPERLINK \l "_Toc139368277" 5.3.1. Décodage de 2 erreurs: PAGEREF _Toc139368277 \h 43
HYPERLINK \l "_Toc139368278" 5.3.2. Exemple du décodage de 2 erreurs d'un code [15, 7, 5]2 : PAGEREF _Toc139368278 \h 44
HYPERLINK \l "_Toc139368279" 5.3.3. Décodage de t erreurs avec les relations de Newton: PAGEREF _Toc139368279 \h 46
HYPERLINK \l "_Toc139368280" 5.3.4. Décodage de t erreurs avec les équations matricielles: PAGEREF _Toc139368280 \h 48
HYPERLINK \l "_Toc139368281" 5.3.5. Exemple d'un décodage de 2 erreurs avec les équations matricielles: PAGEREF _Toc139368281 \h 50
HYPERLINK \l "_Toc139368282" 6. Les codes Reed-Solomon (R-S codes): PAGEREF _Toc139368282 \h 51
HYPERLINK \l "_Toc139368283" 6.1. Introduction: PAGEREF _Toc139368283 \h 51
HYPERLINK \l "_Toc139368284" 6.2. Utilisation: PAGEREF _Toc139368284 \h 51
HYPERLINK \l "_Toc139368285" 6.3. Construction et caractéristique: PAGEREF _Toc139368285 \h 51
HYPERLINK \l "_Toc139368286" 6.3.1. Définition: PAGEREF _Toc139368286 \h 51
HYPERLINK \l "_Toc139368287" 6.3.2. Construction du code: PAGEREF _Toc139368287 \h 52
HYPERLINK \l "_Toc139368288" 6.3.3. Distance minimale: PAGEREF _Toc139368288 \h 52
HYPERLINK \l "_Toc139368289" 7. Bibliographie: PAGEREF _Toc139368289 \h 54
Introduction sur les codes correcteurs :
Pour commencer, il nous semble important d'introduire quelques concepts basiques concernant les codes correcteurs d'erreurs, qui seront utilisés dans les paragraphes suivants.
Nous illustrerons ensuite le concept de code correcteur par des exemples très simples.
Intérêt :
En communication, une fonction d'encodage est une règle qui permet de convertir de l'information sous une autre forme de représentation, appelée code. Dans le domaine de la théorie de l'information, les codes sont utilisés pour détecter et corriger les erreurs de transmission. En effet, lorsqu'une source souhaite transmettre un message à un destinataire, elle envoie ce message au travers d'un canal dans lequel peuvent apparaître des erreurs dues à des bruits. Ainsi le message que le destinataire reçoit peut avoir été modifié. Afin de protéger l'information de ce genre d'erreurs, on ajoute au message de la redondance avant de le transmettre dans le canal. A la réception, le décodeur tente de récupérer le message originel à partir du message reçu.
Le schéma suivant illustre la chaîne d'actions qui permet à une source de transmettre de l'information à un destinataire :
SHAPE \* MERGEFORMAT
Un message m = (m1,m2,
mk) constitué de k symboles est généré par la source et envoyé au codeur. Celui-ci va l'encoder en mots de code x de longueur n, avec n > k. On envoie donc des mots de la forme x = (x1x2
xn) au travers du canal.
A la sortie du canal, on obtient un mot qui contient un certain nombre d'erreurs qui sera noté y = (y1y2
yn). Le décodeur récupère le message m à partir de y en appliquant une règle de décodage, qui peut être, par exemple, le principe du maximum de vraisemblance. On peut donc retrouver le message de départ, à condition que le nombre d'erreurs ne soit pas trop grand. En outre, plus on a ajouté de symboles redondants, plus on peut corriger d'erreurs.
Nous nous intéresserons donc aux mécanismes par lesquels l'information va être codée puis décodée, ainsi qu'aux outils mathématiques qui ont été développés pour ce fait.
Définition mathématique des codes:
On considère que les mots sont constitués d'éléments appartenant tous à un alphabet Sð contenant q éléments. Le mécanisme de codage fournit des mots de code de n éléments appartenant tous à Sð.
Si on appelle Vn(Sð) l'ensemble de toutes les séquences de taille n, on a donc :
|Vn(Sð)| = qn
Un code serait donc un sous-ensemble de Vn(Sð). Donnons une définition plus précise de ce terme ainsi que de la fonction d'encodage :
Définition : Un code C défini sur un alphabet Sð ðest un sous-ensemble de Sðn. Le code ainsi obtenu est appelé un q-ary code de longueur n.
Définition : Une fonction d'encodage f est une fonction injective qui, à chaque élément de l'espace du message, associe un mot de code. On a donc:
EMBED Equation.3
Un code est donc l'image obtenue par cette fonction : C = Im{f}
Dans le cas où q=2, le code est dit binaire. On a alors Sð ð=ð ð{ð0ð,ð1ð}ð. Le code C est donc un sous-ensemble de {0,1}n et |Vn(Sð)| = 2n.
Notation : On note (n, M, d), un code qui transforme des blocs de message en mots de code de n éléments, avec une distance minimale égale à d. M représente le nombre de mots de codes.
Caractéristiques d'un code :
Les codes correcteurs sont caractérisés par quatre données importantes :
La longueur des mots de code n.
Dans les codes par blocs, on code le message en mots de longueur n. On souhaite envoyer des blocs de messages relativement grands car dans ce cas, le nombre d'erreurs se rapproche de son espérance, ce qui implique que la probabilité d'erreurs est meilleure. Cependant, au niveau du décodeur, si la complexité de l'algorithme de décodage est en O(n2), on souhaitera que n soit petit afin que le décodage ne soit pas trop long.
Le rendement ou taux de codage (= « rate » en anglais) correspondant au nombre d'de symboles d'information des blocs du message divisé par le nombre d'éléments des mots de code, c'est-à-dire k/n. Si ce taux est très petit, cela signifie que pour envoyer un petit bloc de message, il va être nécessaire de transmettre un mot de code très grand. Or ceci n'est pas souhaitable car la vitesse de transmission va être fortement réduite, et il faudra beaucoup de temps pour envoyer un court message. Le but étant d'optimiser cette vitesse de transmission, on cherchera à avoir le meilleur rendement possible.
La probabilité d'erreurs du code.
Cette probabilité va dépendre de la distance minimale entre les mots de code (ce terme sera défini plus clairement plus loin). Il est en effet évident que plus les mots seront différents les uns des autres, plus la capacité à retrouver le message originel va augmenter.
La complexité de l'algorithme d'encodage et de décodage.
La complexité de ces algorithmes est une donnée importante car elle décidera du temps de calcul et des ressources nécessaires pour l'exécution des fonctions de codage et de décodage. Il s'agit donc d'une donnée à prendre en compte lors du choix d'un type de code.
Exemples de codes simples :
Pour ces exemples de codes, nous considérerons des codes binaires. Les blocs de messages seront des éléments de {0,1}k, et les mots de code générés seront des éléments de {0,1}n.
Pour illustrer ces codes, nous utiliserons le bloc de message : 1011001.
Code répétitif :
Il s'agit d'un code très simple dans lequel on répète n fois chaque bit du message à envoyer.
On a alors C = {(00
0); (11
1)}.
Illustration : Considérons le cas où n = 5, on obtiendrait alors le mot de code :
11111 00000 11111 11111 00000 00000 11111
On remarque qu'il n'y a que deux mots de code possibles qui sont {(00
0); (11
1)}, où les bits sont répétés n fois. On déduit donc que la distance minimale de ce code est de n, c'est-à-dire que les mots diffèrent de n bits au minimum.
De plus, on code des blocs de 1 bit en mots de n bits. Nous verrons plus loin que l'on note ce code [n, 1, n], pour signifier un code de dimension 1, de longueur n et de distance minimale n. Nous verrons également que le fait que ces mots soient distants de n bits implique que l'on pourra détecter n-1 erreurs et corriger ëð(n-1)/2ûð ðerreurs.
Illustration : Le code répétitif où » = 5 peut donc détecter jusqu'à 4 erreurs et corriger 2 erreurs. En effet, si le décodeur applique la règle du maximum de vraisemblance, si un mot a 3 erreurs, le décodeur va retourner le mauvais bit. En revanche, il ne pourra pas retrouver le mot originel car le mot reçu sera plus proche d'un autre mot de code.
Remarque : Si on analyse ce code, on se rend compte qu'il s'agit d'un code qui a un rendement faible puisque pour transmettre un bit il faut le répéter » fois.
Parity Check code :
Dans ce code, on ajoute un bit correcteur à la fin du bloc de message pour indiquer si le nombre de 1 est pair ou impair. Il faut que le mot de code possède un nombre pair de 1.
Le codage s'effectue donc de la façon suivante :
Si le nombre de bits 1 dans le bloc est pair, on ajoute 0.
Si le nombre de bits 1 dans le bloc est impair, on ajoute 1.
On a donc C = {(c1,& , cn) / Sðci = 0}.
Illustration : Etant donné que dans notre exemple, le nombre de bits 1 est égal à 4, on ajoute un 0 à la fin du mot. Le mot de code ainsi généré serait donc : 10110010.
Si l'on code des blocs de k bits, on obtient donc des mots de code de k+1 bits.
De plus, si on prend deux blocs qui ne diffèrent que d'un seul bit, on obtient deux mots de code distants de 2 bits. Ainsi la distance minimale du code est de 2.
On va donc noter ce code comme étant [k+1, k, 2]. Si on pose n = k + 1, on peut également écrire cette définition de la façon [n, n-1, 2].
Ce code peut détecter 1 erreur, mais ne peut pas la corriger.
Notions d'algèbre :
Les corps finis sont à la base de beaucoup de codes correcteurs d'erreurs. Il est donc essentiel de comprendre la théorie des corps finis afin de pouvoir comprendre par la suite le fonctionnement des codes linéaires et des codes cycliques. Nous allons rappeler brièvement les concepts importants qui seront utiles pour la compréhension des mécanismes de codage qui seront développés par la suite.
Théorie des anneaux et des corps :
Les anneaux :
Afin de pouvoir définir simplement un corps, nous allons tout d'abord introduire le concept d'anneau.
Définition : Un anneau est un ensemble R muni de deux opérations internes + et · et de deux éléments particuliers distincts 0 et 1 satisfaisant les propriétés suivantes :
L'associativité de l'addition : (a + b) + c = a + (b + c) pour tout a, b, c EMBED Equation.3 R
La commutativité de l'addition : a + b = b + a pour tout a, b EMBED Equation.3 R
L'existence d'un élément neutre 0 pour l'addition : a + 0 = 0 + a = a pour tout a EMBED Equation.3 R
L'existence de l'opposé : pour tout a R, il existe un élément a tel que a + (-a)=0
L'associativité de la multiplication : (a · b) · c = a · (b · c) pour tout a, b, c EMBED Equation.3 R
L'existence d'un élément identité 1 : a · 1 = 1 · a = a pour tout a EMBED Equation.3 R
La distributivité de l'addition par rapport à la multiplication : a · (b+c) = a · b + a · c pour tout a, b, c EMBED Equation.3 R
On le note en général (R, +, ·, 0, 1) afin de spécifier les deux opérations ainsi que les éléments particuliers. Cependant, dans le cas où il n'y aurait aucune ambiguïté, on le notera simplement R.
Exemple : L'ensemble Z/mZ est l'ensemble des classes de congruences modulo m, où la classe de congruence d'un nombre a modulo m, notée [a]m est définie comme étant l'ensemble des entiers congrus à a modulo m.
Cet ensemble Z/mZ muni de l'addition et de la multiplication est un anneau. L'élément neutre est [0] m et l'élément identité est [1] m.
Définition : Un ensemble S Ìð R est un sous-anneau de R s'il satisfait les propriétés suivantes :
1R EMBED Equation.3 S
a EMBED Equation.3 S implique que a EMBED Equation.3 S
a, b S implique que a + b EMBED Equation.3 S et que a · b EMBED Equation.3 S
L'ensemble S ainsi obtenu, muni des mêmes opérations que R est un anneau.
Définition : Un anneau R est dit commutatif si pour tout a, b dans R, on a a · b = b · a.
Définition : Un anneau commutatif R est dit intègre si le produit de deux éléments non nuls est non nul. Ainsi pour tout a, b dans R, on a : a · b = 0 implique que a = 0 ou b = 0.
Exemple : L'anneau défini plus haut Z/mZ n'est pas toujours intègre. En effet Z/8Z n'est pas intègre car on peut trouver deux éléments non nuls dont le produit est nul. Ainsi, [4]8 et [2] 8 sont tous les deux non nuls, mais on a [4] 8 · [2] 8 = [8] 8 = [0] 8.
En revanche, Z/5Z est intègre, car on ne peut pas trouver d'éléments non nuls dont le produit soit nul.
Définition : Un diviseur de zéro d'un anneau R est un élément a ¹ð 0 tel qu'il existe b ¹ð 0 et ab = 0.
D'après les deux définitions précédentes, on peut déduire qu'un anneau intègre ne possède aucun diviseur de zéros.
Définition : Une unité d'un anneau R est un élément a tel qu'il existe b EMBED Equation.3 R tel que ab = ba = 1.
Unités et diviseurs de zéros dans Z/mZ :
Dans cet anneau, tout élément non nul est soit un diviseur de zéro, soit une unité. Le théorème suivant permet de distinguer rapidement quels sont les unités et quels sont les diviseurs de zéro d'un tel anneau :
Théorème : Soit a EMBED Equation.3 Z et m EMBED Equation.3 N. On a
Si m | a alors [a]m = [0] m EMBED Equation.3 Z/mZ
Si (m, a) = 1, alors [a]m est une unité dans Z/mZ.
Si 1 < (a, m) < m, alors [a]m est un diviseur de zéro modulo m.
On peut donc déduire de ce théorème que si m est un nombre premier noté p, alors Z/pZ ne contiendra que des unités.
Les corps :
Nous pouvons à présent donner la définition d'un corps.
Définition : Un corps est un anneau commutatif dont tous les éléments non nuls sont des unités.
On déduit de cette définition que l'anneau Z/pZ avec p premier est un corps. Plus généralement, on a la proposition suivante :
Proposition : Un anneau Z/pZ est un corps si et seulement si p est premier.
On note alors ce corps Fp. Celui-ci contient p éléments.
Très simplement, on peut dire qu'un corps est un ensemble d'éléments dans lequel on peut réaliser l'addition, la soustraction, la multiplication et la division, tout en restant dans cet ensemble.
Le nombre d'éléments d'un corps est appelé l'ordre du corps. Si le corps contient un nombre fini d'éléments, on dit que le corps est un corps fini.
Etant donné qu'un corps est un anneau particulier, les propriétés des anneaux s'appliquent toutes aux corps. Résumons ici quelques propriétés propres aux corps qui découlent des propriétés des anneaux vus ci-dessus.
Propriétés : Soit un corps K, on a :
Pour tout élément a EMBED Equation.3 K, a · 0 = 0 · a = 0
Pour tout élément a et b non nuls de K, a · b `" 0
a · b = 0 et a `" 0 impliquent que b = 0
Pour tous a, b EMBED Equation.3 K, (a · b) = (-a) · b = a · (-b)
Pour tout a non nul de K, a · b = a · c implique que b = c.
Les idéaux :
La notion d'idéal nous sera utile lors de la définition des codes cycliques. Dans ce paragraphe, nous ne ferons que donner une définition et une proposition essentielle pour la suite. Le concept sera en effet revu plus tard.
Définition : Un sous-ensemble I d'un anneau commutatif R est un idéal si on a :
Pour tout x et x' EMBED Equation.3 I, on a x + x' EMBED Equation.3 I
Pour tout x EMBED Equation.3 I et tout a EMBED Equation.3 R, on a a · x EMBED Equation.3 I
Proposition : Soit un anneau R et a EMBED Equation.3 R. Le sous-ensemble {ax | x EMBED Equation.3 R} est un idéal noté aR.
Définition: Un idéal I `" R d'un anneau R est dit principal s'il existe un r EMBED Equation.3 R tel que :
I = {r · x / x EMBED Equation.3 R}
Les corps finis :
Nous avons vu au paragraphe précédent qu'un ensemble d'entiers modulo un nombre premier p (un anneau Z/pZ) forme un corps fini, noté Fp (pour "Field of order p") ou GF(p) (pour "Galois field of order p"). Plus généralement, on a le théorème suivant :
Théorème : Soit p un nombre premier et n un entier e" 1. Alors il existe un corps à pn éléments.
Le nombre d'éléments d'un corps fini est donc toujours une puissance d'un nombre premier.
Construction d'un corps fini :
Afin de construire un corps à pn éléments, on introduit les notions d'anneau de polynômes et de congruence modulo un polynôme f. Le corps voulu sera construit en considérant des polynômes à coefficients pris dans un corps Fp .
Considérons un anneau R et le polynôme f(X) = anXn + & + a1X + a0 tel que les ai, 0 d" i d" n, soient pris dans R.
L'anneau de polynôme R[X] est l'ensemble des polynômes à coefficients pris dans R, avec l'addition et la multiplication des polynômes comme opérations, le polynôme constant f(X) = 0 comme élément neutre 0, et le polynôme constant f(X) = 1 comme élément identité 1.
Restreignons nous maintenant au cas où R = K est un corps.
Définition : Soient f, g et m des polynômes de K[X] avec deg(m) > 0. On dit que les polynômes f et g sont congrus modulo m si le polynôme m divise le polynôme f g. On note :
f a" g (mod m)
De même que pour les entiers, on regroupe les polynômes qui sont congrus modulo m en une classe de congruence, notée K[X]/(m). La classe de f (mod m) est alors notée [f]m.
Théorème : L'anneau K[X]/(m) est un corps si et seulement si le polynôme m(X) est irréductible.
Ainsi, si l'on choisit un nombre premier p, on a que Fp = Z/pZ est un corps. Si l'on choisit un polynôme g EMBED Equation.3 Fp irréductible et de degré n, alors l'anneau Fp[X]/(g) est un corps qui contient pn éléments.
En effet, étant donné qu'un élément de Fp[X]/(g) est une classe de polynômes modulo f , toute classe peut être représentée par un polynôme de degré < n. De plus, deux polynômes distincts de degré < n ne sont pas congrus modulo g. Ils représentent donc deux classes différentes. Ainsi, il y a autant d'éléments dans Fp[X]/(g) que de polynômes de degré < n à coefficients dans Fp. Ces polynômes possèdent donc n coefficients qui peuvent être choisis dans un ensemble de p éléments. Il y a donc pn polynômes possibles et on en déduit que le corps construit contient pn éléments, où n = deg(g).
Exemple:
Afin d'illustrer la théorie développée ci-dessus, nous allons donner un exemple de construction de corps fini à partir d'un nombre d'éléments donné.
Pour exemple, nous allons construire un corps fini de 9 éléments. Ayant 9 = 32, on a bien un nombre d'éléments qui est une puissance d'un nombre premier p = 3.
On part donc du corps fini F3 = {0, 1, 2} où les opération d'addition et de multiplication sont faites modulo 3, et on cherche une extension de degré 2 sur ce corps.
La première étape pour construire ce corps est donc de trouver un polynôme de degré 2 qui soit irréductible sur F3. Pour cela, on commence par lister tous les polynômes de degré 2 à coefficients dans F3 et on cherche ceux qui sont irréductibles.
Les polynômes unitaires de degré 2 existants sont :
x2 ; x2 + 1 ; x2 + 2 ; x2 + x ; x2 + 2x ; x2 + x + 1 ; x2 + x + 2 ; x2 + 2x + 1 ; x2 + 2x + 2
Pour qu'un polynôme soit irréductible, il ne doit pas avoir de racine dans l'ensemble {0, 1, 2}.
Ainsi, tous les polynômes n'ayant pas de terme constant sont réductibles, car ils acceptent x = 0 comme racine. De fait, les polynômes x2 ; x2 + x ; x2 + 2x sont réductibles.
De plus, si l'on fait la somme des coefficients, celle-ci doit être différente de 1 car dans ce cas, le polynôme accepterait x = 1 comme racine. De fait, les polynômes x2 + 2 ; x2 + x + 1 sont réductibles.
Pour finir, on teste la racine x = 2 sur les polynômes restants. On remarque alors que le polynôme x2 + 2x + 1 est réductible.
Les polynômes suivant sont donc irréductibles sur F3 : x2 + 1 ; x2 + x + 2 ; x2 + 2x + 2.
On choisit par exemple x2 + 1, et on pose ² une racine de ce polynôme. On a donc ²2 + 1 = 0.
Le corps fini obtenu par extension de F3 est donc F3 /[x2 + 1]. Il s'agit bien d'un corps contenant 32 = 9 éléments, que l'on note F3[²].
Ce corps est formé des éléments suivants :
F3 /[x2 + 1] = {a ² + b / a, b F3} = {0, 1, 2, ², ² + 1, ² + 2, 2², 2² + 1, 2² + 2}
Codes linéaires :
Dans la première section, nous avons introduit quelques généralités sur les codes. Les codes dont nous avons parlés étaient essentiellement des codes par blocs (blocks codes), c'est-à-dire des codes qui s'appliquent sur des blocs de symboles. On obtenait ainsi des mots de code qui étaient par la suite transmis dans le canal.
A partir de maintenant, nous allons nous restreindre à une sous-classe des codes par blocs, les codes linéaires. Nous étudierons le cas général des q-ary codes, ainsi que le cas plus particulier des codes binaires car ceux-ci sont très couramment utilisés pour la transmission d'informations.
Nous commencerons par en donner une définition, puis nous donnerons une description des matrices génératrices et de vérification, puis nous définirons plus précisément ce qu'est la distance minimum d'un code et nous expliquerons quel est son intérêt. Dans la section 3.6, nous définirons quelques bornes sur le nombre de mots par rapport à la distance minimale du code. Et pour finir, nous illustrerons les codes linéaires par un exemple de code connu, les codes de Hamming.
Définition :
A partir de maintenant, on considère que l'on code des blocs de symboles de k éléments. Le message émis par la source est donc tout d'abord découpé en blocs qui seront encodés séparément.
Définition générale des q-ary codes:
Soit un alphabet Sð ð=ð ðFq, avec q une puissance d un nombre premier, i.e. q = pr avec p premier.
Définition : Un code par blocs C est un code linéaire si et seulement si ses mots de codes de longueur n forment un sous-espace de dimension k de F EMBED Equation.3 . Ce code est noté [n, k].
Ainsi, il existe k vecteurs g0, g1,
,gk-1 qui forment une base de ce sous-espace. Tout mot de code c appartenant à C peut s'écrire comme une combinaison linéaire de ces vecteurs :
c = u0 · g0 + u1 · g1 +
+ uk-1 · gk-1
où les ui, 0 d" i d" k-1, sont des éléments de l'alphabet Sð.ð
On déduit de cette notation qu'il existe qk mots de code différents.
Cas particulier des codes binaires :
Soit Sð ð=ð ðF2 = {0, 1}.
Le code par blocs C est dit linéaire si et seulement si ses 2k mots de code forment un sous-espace de dimension k de l'espace vectoriel de tous les vecteurs de longueur n.
Par conséquent C est défini comme étant un sous-espace vectoriel de dimension k de F EMBED Equation.3 .
Plus simplement, un code binaire est linéaire si la somme modulo 2 de deux mots de code est aussi un mot de code.
De plus, on a :
c = u0 · g0 + u1 · g1 +
+ uk-1 · gk-1
avec g0, g1,
,gk-1 les k vecteurs formant la base, et ui = {0, 1} pour 0 d" i d" k-1.
Matrice génératrice (generator matrix) :
Nous avons vu qu'un mot de code pouvait s'écrire comme la combinaison linéaire des k vecteurs de la base (g0, g1,& ,gk-1).
c = u0 · g0 + u1 · g1 + & + uk-1 · gk-1
Ces vecteurs gi permettent donc de générer un mot de code. Ils peuvent être regroupés dans une matrice G, k EMBED Equation.3 n, appelée matrice génératrice, formée de telle sorte que ses lignes soient composées des vecteurs de la base gi.
On obtient donc la matrice suivante :
G = EMBED Equation.3
Définition : Une matrice génératrice G d'un code linéaire C est une matrice k EMBED Equation.3 n dont les lignes sont une base de C.
Si on considère le mot à encoder u EMBED Equation.3 F2, avec u = (u0, u1,
, uk-1), le mot de code est obtenu en calculant :
EMBED Equation.3
On a alors EMBED Equation.3 .
Définition : On dit que G est dans une forme standard si G est de la forme (Ik P) ou (P Ik), où Ik est la matrice identité k EMBED Equation.3 k.
Dans ce cas, les k premiers (ou derniers, suivant la façon dont est formée la matrice génératrice) symboles du mot de code sont appelés les symboles d'information ("information symbols" en anglais), ils peuvent être choisis de façon arbitraire. Les n-k autres symboles calculés par la fonction d'encodage à partir des symboles d'information sont appelés symboles de contrôle ("parity-check symbols" en anglais).
Dans le cas d'un code binaire, on dit bits d'information et bits de contrôle.
Matrice de vérification (parity-check matrix) :
Une autre matrice très utile est la matrice H, appelée matrice de vérification ("parity-check matrix" en anglais). On la définit de la façon suivante :
Définition : La matrice de vérification H est une matrice n-k EMBED Equation.3 n, avec n-k lignes linéairement indépendantes, telle que chaque vecteur de l'espace des lignes de G est orthogonal aux lignes de H, et que tout vecteur orthogonal aux lignes de H est dans l'espace des lignes de G.
On peut alors définir un code linéaire de la façon suivante :
Un n-tuple c est un mot du code C généré par G si et seulement si c · HT = 0.
Remarque : Ayant c · HT = 0 et sachant que c = u · G, avec c EMBED Equation.3 C, on peut écrire :
u · G · HT = 0
Ayant u `" 0, on en déduit que :
G · HT = 0
Théorème : Si la matrice génératrice G de C est dans la forme standard (Ik ¦ P), alors une matrice de vérification pour C est H = (- PT ¦ Ir), avec r = n k.
Preuve : Pour cela, on vérifie que G · HT = 0.
EMBED Equation.3
#
Ainsi, la forme standard de G est (-PT ¦ In-k), avec In-k la matrice identité n-k EMBED Equation.3 n-k, et P une matrice n-k EMBED Equation.3 k.
Distance minimum:
Tout au long de ce paragraphe, nous considèrerons le code linéaire par blocs C ainsi que deux mots de ce code x et y.
Définition :
Commençons par définir les notions de distance entre deux mots de code et le poids d'un mot.
Définition : La distance de Hamming entre deux mots x et y, notée d(x,y) est le nombre de symboles différents entre ces deux mots. En définissant les mots x = (x1x2& xn) et y = (y1y2& yn), on a :
d(x,y) = {i / xi `" yi }
Exemple : Considérons les mots binaires x = (0 0 1 0 1 1 0) et y = (1 0 0 0 1 0 1).
On a alors :
d(x,y) = 4
Définition : Le poids w(x) d'un bloc de symboles x est défini par :
w(x) := d(x, 0)
où 0 = (0, 0,
, 0)
Exemple : Si on reprend les exemples ci-dessus, on a :
w(x) = 3 et w(y) = 3
Dans le cas d'un code binaire, si l'on réalise l'addition modulo 2 de deux mots x et y, les bits qui seront égaux à 1 seront placés aux endroits où x et y diffèrent. Ainsi, le poids de Hamming de cette somme sera égale à la distance de Hamming entre x et y, c'est-à-dire:
d(x, y) = w (x + y)
Exemple : Avec les mots x et y définis précédemment, on a :
w(x+y) = w(1 0 1 0 0 1 1) = 4 = d(x,y)
On peut alors définir la distance minimum du code, notée dmin, ou plus simplement d :
Définition : La distance minimum du code C, notée d, est le minimum des distances de Hamming entre les mots du code. On a donc:
dmin = min {d(x,y) / x, y EMBED Equation.3 C, x `" y}
Notation : Un code C ayant une distance minimale de d est noté [n, k, d]. Cette notation signifie que l on code des mots de k symboles en mots de code de n symboles étant tous distants les uns des autres de d symboles au minimum.
Calcul de la distance minimale d'un code :
Dans le cas où C est un code linéaire binaire, on a :
dmin = min {d(x,y) / x, y EMBED Equation.3 C, x `" y}
dmin = min {w(x + y) / x, y EMBED Equation.3 C, x `" y}
dmin = min {w(x) / x EMBED Equation.3 C, x `" 0} = wmin
On obtient donc le théorème suivant :
Théorème : La distance minimum d'un code linéaire par bloc est égale au poids minimum de ses mots de code non nuls.
Voyons à présent comment calculer la distance minimum d'un code à partir de sa matrice de vérification H.
Théorème : Soit C un code binaire [n, k], et H sa matrice de vérification. Pour chaque mot de code de poids w, il existe w colonnes de H telles que la somme de ces colonnes est nulle.
Inversement, s'il existe w colonnes de H dont la somme est nulle, alors il existe un vecteur de poids w.
Preuve : Pour plus de simplicité, on considère un code binaire C, ayant une matrice de vérification H = [h0, h1,
, hn-1] où hi est la ième colonne de H.
Soit r = (r0, r1,
, rn-1) un mot reçu au niveau du décodeur de poids w. r a donc w composantes non nulles égales à 1. On a donc ri1 = ri2 =
= riw = 1 avec 0 d" iw d" n-1.
r sera un mot de code si r · HT = 0, ce qui équivaut à :
r0 · h0 + r1 · h1 + & + rn-1 · hn-1 = 0
ri1 · hi1 + & + riw · hiw = 0
hi1 + & + hiw = 0
On a alors w colonnes de H dont la somme est nulle.
Pour montrer l'autre partie du théorème, on considère le n-tuple binaire x = (x0, x1,
, xn-1), de poids w, ayant les w composantes xi1, xi2,
, xiw non nulles. On a:
x · HT = xi1 · hi1 +
+ xiw · hiw = hi1 +
+ hiw
Si hi1 +
+ hiw = 0, on en déduit que x · HT = 0.
Donc x est un mot du code C, de poids w.
#
De ce théorème, on déduit les deux corollaires suivants :
Corollaires : 1. Soient C un code linéaire et H sa matrice de vérification. Si on ne trouve pas d-1 ou moins colonnes telles que leur somme est nulle, alors dmin e" d.
2. Soit C un code linéaire et H sa matrice de vérification. Le poids minimum du code wmin est le plus petit nombre de colonnes telles que leur somme soit nulle.
Ainsi on pourra calculer la distance minimum du code C en trouvant le nombre minimum de colonnes dont la somme est nulle.
Détection et correction des erreurs :
Mécanisme de décodage d'un mot :
L'encodage d'un mot u de k symboles s'effectue en calculant le vecteur c de longueur n tel que :
c = u · G
Puis on transmet c dans le canal. A la sortie du canal, on reçoit un message r. Le but du décodeur va donc être de tenter de retrouver le message qui a été envoyé à partir de celui qu'il a reçu. Il cherche donc à détecter s'il y a eu une erreur, puis dans un deuxième temps, il cherche à corriger cette ou ces erreurs.
Une méthode pour détecter la présence d'erreurs et de calculer le syndrome s = (s0, s1,
, sn-1), défini par :
s = r · HT
Si le vecteur s obtenu est égal au vecteur nul, étant donné que le produit d'un des mots du code C avec la transposée de la matrice de vérification est nulle, on peut déduire que r est un mot appartenant au code C. Le récepteur va alors considérer qu'il n'y a pas d'erreur, et qu'il s'agit du message envoyé.
Si le syndrome est différent du vecteur nul, cela signifie que le mot reçu r n'est pas un mot appartenant au code C. Par conséquent, on est sûr qu'une erreur est apparue lors de la transmission. Le but du décodeur va donc être de trouver où se situe cette erreur et de la corriger.
Voyons plus précisément le cas des codes binaires :
On pose e = (e0, e1,
, en-1), le vecteur d'erreur, représentant les erreurs ayant été introduite par le canal. Ce vecteur a des zéros partout sauf aux positions où une erreur s'est produite.
On a alors :
r = c + e
Le syndrome s est alors égal à :
s = (c + e) · HT
s = c · HT + e · HT
Or c · HT = 0, donc on a:
s = e · HT
On peut donc calculer les syndromes possibles à partir des vecteurs d'erreurs et constituer une table associant à chaque erreur pouvant apparaître dans le canal le syndrome que l'on obtiendrait. Ainsi lors du décodage, on pourra comparer s avec les entrées de la table et retrouver le vecteur erreur. Lorsque e est connu, on retrouve facilement c en calculant :
c = r + e
Distance minimale et capacité de détection et correction d'erreurs :
Voyons à présent comment la distance minimale nous permet de savoir combien d'erreurs pourront être détectées et corrigées.
Afin de comprendre le principe, commençons par réaliser une illustration des mots d'un code binaire C. Les petites étoiles représentent les 2k mots du code pris dans un ensemble de 2n éléments.
SHAPE \* MERGEFORMAT
Un mot n'appartient pas au code C si celui-ci n'est pas un des 2k mots représentés. Instinctivement, on déduit de ce schéma qu'on pourra détecter qu'un mot n'appartient pas à C s'il a une distance avec un mot de code non nulle et strictement inférieure à d.
De plus, en admettant que l'on utilise une règle de maximum de vraisemblance pour le décodage, on pourra corriger correctement les erreurs et retrouver le mot originel si la distance entre le mot reçu et le mot envoyé est inférieure à EMBED Equation.3 .
On obtient donc la propriété suivante :
Propriété : Un code ayant une distance minimale de d peut détecter (d-1) erreurs et peut corriger EMBED Equation.3 erreurs.
Ainsi, si l'on pose d = 2e + 1, on pourra détecter 2e erreurs et on pourra corriger e erreurs.
Bornes caractérisant les codes :
Nous avons vu que l'on caractérise un code par la longueur de ses mots de code n, son nombre de mots M (ou la longueur des blocs de message k), et la distance minimum d entre les mots de code. On dit alors qu'il s'agit d'un code (n, M, d).
Intuitivement, on comprend que les grandeurs M et d "jouent" l'une contre l'autre. En effet, si on a un très grand nombre de mots, ceux-ci auront une distance faible. Alors que si on a M petit, alors la distance entre les mots pourra être plus grande, permettant ainsi de détecter et de corriger plus d'erreurs.
Pour caractériser cette relation, on introduit la notation Aq(n, d) qui représente le nombre de mots M maximum tels qu'il existe un code q-ary (n, M, d).
Il va donc être nécessaire de trouver un compromis entre ces deux valeurs, afin d'avoir un nombre de mots suffisants et une distance minimale suffisamment grande pour pouvoir détecter et corriger un certain nombre d'erreurs. Pour cela, il existe des bornes qui caractérisent les grandeurs M et d. Nous allons étudier dans ce paragraphe deux bornes : le Singleton Bound et la Sphere Packing Bound, appelée également borne de Hamming.
Singleton Bound:
Considérons un code C [n, k, d]. Cette borne permet de trouver une borne maximale sur la distance minimale d par rapport aux valeurs n et k.
Théorème : Soit un code [n, k, d]. On a l'inégalité suivante :
d d" n k + 1
Preuve: Soient C le code [n, k, d]q, et x un mot de ce code.
Considérons le mot x' formé à partir de x auquel on enlèverait les (d-1) derniers symboles.
On obtient ainsi un nouveau code C' de taille n' = n (d 1) = n d + 1.
Comme C avait une distance minimale de d, tous les mots de C avaient une distance entre eux supérieure ou égale à d, donc si on enlève (d 1) symboles à ces mots, on obtient des mots qui sont tous différents d'au moins un symbole. Ainsi, tous les mots de C' sont différents les uns des autres, et on en déduit que C et C' ont le même nombre de mots de code.
On peut donc écrire que :
qk' = qk
ce qui implique :
k = k'.
C' est donc un code [n', k] avec n' = n d + 1. On en déduit qu'il existe un code de dimension k et de distance d e" 1 et de longueur n.
Or, on sait que la longueur des mots de code est toujours supérieure ou égale à la dimension du code, et donc on a la relation suivante :
n' e" k ( n d + 1 e" k
d d" n k + 1
#
Sphere Packing Bound:
Il s'agit d'une borne sur la dimension du code k.
Pour commencer, définissons une "balle" de rayon r = ëð(d-1)/2ûð autour de chaque mot de code . Celle-ci englobe tous les éléments de l'ensemble F EMBED Equation.3 qui se trouvent à une distance inférieure ou égale à r d'un mot de code.
Illustrons ce concept pour le cas d'un code binaire, à l'aide d'un schéma. Le cercle bleu représente la balle de rayon r. Pour des raisons de clarté, nous ne représenterons cette balle que pour un seul mot de code, l'idée étant la même pour tous les autres mots de codes.
SHAPE \* MERGEFORMAT
On s'intéresse alors au nombre de mots se situant dans cette balle, c'est-à-dire au nombre de mots se trouvant à une distance inférieure ou égale à r d'un mot de code c donné. On note :
Sr(c) = {x EMBED Equation.3 F EMBED Equation.3 / d(x, c) d" r } avec r = ëð(d-1)/2ûð
On calcule le cardinal de Sr(c). Pour cela, on compte le nombre de mots qui diffèrent d'un nombre de symbole de 0 à r du bloc c. On choisit donc i places (0 d" i d" r) dans le mot que l'on multiplie par le nombre de possibilités de changements d'un symbole. On obtient alors la formule suivante :
EMBED Equation.3
Pour finir, étant donné que les balles sont disjointes, le nombre de mots du code multipliés par le nombre d'éléments contenus dans cette balle doit donner un nombre inférieur ou égal au nombre total d'éléments de F EMBED Equation.3 . On obtient donc la borne suivante :
EMBED Equation.3
Théorème : Soit un code linéaire [n, k, d] défini sur un alphabet à q éléments. La borne de Hamming du code est la relation :
EMBED Equation.3
Dans le cas d'un code binaire, on a la relation :
EMBED Equation.3
Cette borne nous permet de définir la notion de code parfait.
Définition: Un code est dit parfait si la borne de Hamming est une égalité, c'est-à-dire si :
EMBED Equation.3
Plus simplement, un code est parfait si tous les éléments de F EMBED Equation.3 sont inclus dans les balles de rayon r autour des mots du code.
Exemple : les codes de Hamming :
Ces codes ont été inventés par Richard Hamming, et sont utilisés dans le domaine des "digital communications" et des systèmes de sauvegarde de données.
Le codage d'un mot de k bits s'effectue en ajoutant m bits de façon à obtenir des mots de codes de n bits. On a donc m = n k. Ces bits sont calculés à l'aide de la matrice génératrice.
Le code a une distance minimale de 3, il peut donc détecter 2 erreurs et en corriger 1.
Cas général des q-ary codes de Hamming:
Voyons tout d'abord comment on forme de façon générale les codes de Hamming définis sur un alphabet contenant q éléments.
On part du "projective space" Pn(Fq) de dimension n défini sur Fq. Cet ensemble est l'ensemble des classes d'équivalence de F EMBED Equation.3 \{0}, où deux vecteurs x et y sont dit équivalents si y = »x, avec » EMBED Equation.3 Fq*. Par conséquent, dans une classe d'équivalence, tous les éléments dont des multiples les uns des autres. Le principe est comparable aux classes d'équivalence définies sur Z/mZ.
1) Montrons que le nombre d'éléments de Pn(Fq) est EMBED Equation.3 :
Le nombre d'éléments de F EMBED Equation.3 \{0} est égal au nombre de vecteurs de longueur n+1 constitués d'éléments pris dans un ensemble de q éléments auquel on enlève le vecteur nul. On a alors :
| F EMBED Equation.3 \{0} | = qn+1 1
Pour trouver le nombre d'élément de Pn(Fq), on applique le principe suivant :
On regroupe tous les vecteurs de F EMBED Equation.3 \{0} en classes d'équivalence et on cherche le nombre d'éléments contenus dans une classe d'équivalence. De là, on pourra déduire le nombre de classe d'équivalence, qui est le nombre recherché.
Sachant que y = » · x, si l'on considère un vecteur x, on obtient tous les autres vecteurs de la classe représentée par x en multipliant x par un » EMBED Equation.3 Fq*. On a q - 1 possibilités pour choisir » (Fq* contient q-1 éléments car on y a exclu l'élément 0), ce qui implique que l'on a q - 1 éléments dans une classe d'équivalence.
Par conséquent, on en déduit que :
| Pn(Fq) | EMBED Equation.3
#
On considère maintenant la matrice H possédant n+1 lignes et N colonnes, où les colonnes de H sont les représentants de chaque classe d'équivalence qui sont les éléments de Pn(Fq).
2) Montrons que le rang de H est égal à n+1:
Ceci équivaut à montrer qu'il existe n+1 colonnes linéairement indépendantes.
Prenons les vecteurs e1, e2,
., en+1, définis de la façon suivante :
EMBED Equation.3 , EMBED Equation.3 ,
., EMBED Equation.3
On remarque que les ei sont tous dans des classes d'équivalence différentes, et que tout autre vecteur de n+1 composantes peut être défini par une combinaison linéaire de e1, e2,
., en+1. Par conséquent, (e1, e2,
., en+1) peut être considéré comme une base de l'espace des colonnes de H. Le rang de H est donc de n+1.
#
3) Montrons que la distance minimale du code obtenu est égale à 3:
Ceci revient à montrer que le poids minimum des mots du code est de 3.
On sait que si x est un mot du code C défini par la matrice de vérification H, alors :
EMBED Equation.3
Supposons que le poids minimum est strictement inférieur à 3, prenons le cas où il serait égal à 2.
Il existerait alors un mot EMBED Equation.3 de poids égal à 2, c'est-à-dire que les EMBED Equation.3 seraient tous nuls sauf aux deux positions EMBED Equation.3 et EMBED Equation.3 où on aurait EMBED Equation.3 EMBED Equation.3 .
On aurait alors :
EMBED Equation.3
où EMBED Equation.3 et EMBED Equation.3 sont les colonnes de HT (ou les lignes de H) se situant aux positions EMBED Equation.3 et EMBED Equation.3
EMBED Equation.3
De fait, les colonnes EMBED Equation.3 et EMBED Equation.3 seraient dans la même classe d'équivalence. Au moins une de ces deux colonnes n'est donc pas un représentant de cette classe. Ceci remet en cause la définition de la matrice, car celle-ci a été construite de telle sorte que ses colonnes soient les représentants des classes d'équivalence. Il y a donc une contradiction.
On en déduit que le poids minimum d'un mot doit être de 3, et donc on a dmin = 3.
#
La matrice H, n+1 EMBED Equation.3 N, décrite ci-dessus définie un q-ary code de Hamming. La matrice génératrice G de ce code est une matrice N-n-1 EMBED Equation.3 N.
On code donc des mots de N-n-1 symboles en mots de code de N symboles, avec EMBED Equation.3 .
4) Montrons que ce code est parfait:
On rappelle que le code a une dimension égale à k = N n 1, et une longueur de N, avec N défini comme auparavant, et une distance minimale dmin = 3.
Pour montrer que le code est parfait, il nous faut montrer que la borne de Hamming est une égalité. On montre donc que :
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
#
On a en déduit que le code de Hamming défini au point précédent est un code parfait.
Cas particulier des codes de Hamming binaires:
L'alphabet utilisé est {0,1}, donc q = 2. Le code C est défini de la façon suivante :
Sa longueur est: EMBED Equation.3 avec k = n+1.
Sa dimension est: EMBED Equation.3 .
On a donc un code [2k 1, 2k k 1, 3]. On code des mots de 2k k 1 bits en mots de 2k 1 bits en leur ajoutant k bits.
Etudions plus précisément l'exemple du code [7, 4, 3]. Dans ce code, on encode des mots de 4 bits en ajoutant 3 bits de contrôle. Nous donnons les matrices qui définissent ce code, puis nous illustrerons le fonctionnement de ce code en donnant l'exemple de l'encodage d'un mot, du décodage et de la correction d'un message reçu avec une erreur.
Matrices de vérification et génératrice en forme systématique:
EMBED Equation.3
Exemple de codage d'un mot u:
Soit le message à transmettre : u = (1 1 0 1).
On envoie le mot de code x défini par x = u · G :
EMBED Equation.3
On remarque que comme G est dans une forme systématique, les quatre derniers bits du mot x sont les bits d'information non modifiés. Les trois premiers bits de x sont donc les bits de contrôle.
Exemple du décodage d'un mot reçu r:
Imaginons qu'à la sortie du canal, on reçoive le mot r = (1 0 0 1 1 0 1) comportant une erreur au premier bit.
Pour décoder ce mot, on commence par calculer le syndrome s qui y est associé en le multipliant par la matrice de vérification H. Si le résultat est nul, ce mot est considéré comme ne comportant pas d'erreur. Si le résultat est non nul, on en déduit qu'une erreur a été introduite dans le canal. Dans le cas des Hamming codes, le vecteur obtenu se retrouve dans les colonnes de H, et la position de la colonne nous indique la position du bit erroné dans le mot reçu.
On calcule donc le syndrome :
EMBED Equation.3
Ayant s `" 0, on en déduit qu'une erreur a été introduite par le canal. De plus, la colonne (1 0 0) est en première position dans H, ce qui implique que l'erreur se trouve au premier bit de r.
On peut donc corriger le mot reçu en changeant le bit erroné. On obtient alors :
r' = (0 0 0 1 1 0 1)
Le message envoyé étant contenu dans les quatre derniers bits, on retrouve simplement le mot envoyé qui était bien m = (1 1 0 1).
Les codes cycliques:
Les codes cycliques ont été étudiés pour la première fois par Prange en 1957. Il s'agit d'une sous-classe des codes linéaires. Ils possèdent donc toutes les caractéristiques de ces codes, auxquelles viennent se rajouter d'autres spécifications que nous allons définir dans un premier paragraphe.
Ces codes sont intéressants pour plusieurs raisons. L'une d'elles est qu'ils possèdent des propriétés intéressantes (notamment en ce qui concerne le polynôme générateur) simplifiant le codage et le décodage, rendant ainsi une implémentation relativement simple.
Voyons donc quelles sont les principales caractéristiques de ces codes, de quelle façon on peut les former, et comment se passe le codage et la détection des erreurs. Pour finir, nous étudierons les racines de ces codes. Ce paragraphe nous permettra de faire le lien avec les codes BCH qui sont un code cyclique particulier.
Description:
Définition:
Un code linéaire cyclique C est un code pour lequel le shift d'une place vers la droite d'un de ses mots de code donne un autre mot de code. Ainsi, on a que:
Si c = (c0, c1,
, cn-1) EMBED Equation.3 C, alors c' = (cn-1, c0, c1,
, cn-2) EMBED Equation.3 C
On remarque que si l'on réalise une opération de décalage plusieurs fois de suite, on obtient toujours un mot de code. Ainsi, si l'on réalise cette opération i fois, on obtient le mot c(i) EMBED Equation.3 C, obtenu par le décalage vers la droite de ses éléments de i places, et défini par :
c(i) = (cn-i, cn-i+1,
, cn-1, c0, c1,
, cn-i-1)
On peut alors donner une définition plus générale:
Définition: Le code linéaire (n, k) C est dit cyclique si chaque shift d'un mot de C donne un autre mot de C, ce qui se traduit mathématiquement par :
c = (c0, c1,
, cn-1) EMBED Equation.3 C EMBED Equation.3 pour tout i, c(i) = (cn-i, cn-i+1,
, cn-1, c0, c1,
, cn-i-1) EMBED Equation.3 C
Représentation polynomiale des mots de code:
Afin de pouvoir étudier les mécanismes des codes cycliques, il nous faut introduire une autre forme de représentation. Les mots de codes seront dès à présent décrits par des polynômes de degré inférieur ou égal à n-1. Cette représentation algébrique des mots de codes va nous permettre de comprendre les mécanismes et les propriétés des codes.
On peut en effet réaliser l'identification suivante :
c = (c0, c1,
, cn-1) EMBED Equation.3 c(x) = c0 + c1 · x + c2 · x2 +
+ cn-1 · xn-1
L'élément 0 du mot est associé à un monôme de degré nul, l'élément 1 à un monôme de degré 1, et ainsi de suite jusqu'à l'élément n-1 qui est associé à un monôme de degré n-1. Etant donné qu'un mot possède n éléments, on comprend que le polynôme de code ne peut avoir un degré supérieur à n-1.
On peut donc établir un isomorphisme entre (F EMBED Equation.3 ,+) qui est l'espace vectoriel dans lequel sont choisis les vecteurs représentant les mots de code, où "+" représente l'addition des vecteurs; et le groupe des polynômes de degré inférieur ou égal à n-1, muni de l'addition de polynômes.
Étudions l'anneau de polynômes R = Fq[x]/(xn-1). D'après ce que nous avons vu dans la deuxième partie consacrée aux corps finis, on peut dire qu'il est constitué des éléments suivants :
R = { a0 + a1 · x + a2 · x2 + & + an-1 · xn-1 / ai EMBED Equation.3 Fq, 0 d" i d" n}
Il existe donc une bijection entre F EMBED Equation.3 et l'anneau de polynômes Fq[x] / (xn-1). On identifie donc un mot de code c EMBED Equation.3 F EMBED Equation.3 par un polynôme code c(x) EMBED Equation.3 Fq[x] / (xn-1).
413. Définition des codes avec les représentations polynomiales:
Afin de pouvoir décrire les codes cycliques par rapport à la représentation polynomiale des mots de code, on s'intéresse d'abord à la façon de réaliser le shift d'un bit d'un mot de code sur la représentation polynomiale de ce mot.
Nous avons vu que l'on identifie c par c(x) = c0 + c1 · x + c2 · x2 +
+ cn-1 · xn-1. De fait, le mot c(1) = (cn-1, c0, c1,
, cn-2) est représenté par c(1)(x) = cn-1 + c0 · x + c1 · x2 +
+ cn-2 · xn-1.
Or on a:
x · c(x) = c0 · x + c1 · x2 + c2 · x3 +
+ cn-2 · xn-1 + cn-1 · xn
= xn · cn-1 1 · cn-1 + cn-1 + c0 · x + c1 · x2 +
+ cn-2 · xn-1
= (xn 1) · cn-1 + c(1)(x)
Ainsi le décalage des éléments d'une place vers la droite s'effectue en multipliant le polynôme code par x et en prenant le reste de la division du polynôme obtenu par (xn 1).
Montrons à présent que pour obtenir le polynôme code d'un mot décalé de i positions vers la droite, il suffit de multiplier ce polynôme par xi puis de prendre le reste de la division du résultat par (xn 1) :
xi · c(x) = c0 · xi + c1 · xi+1 + c2 · xi+2 +
+ cn-2 · xn+i-2 + cn-1 · xn+i-1
= (xn 1) · (cn-1 · xi-1 + cn-2 · xi-2 +
+ cn-i)
+ (cn-i + cn-i+1 · x +
+ c0 · xi +
+ cn-i-1 · xn-1)
= (xn 1) · q(x) + c(i)(x)
où q(x) est le polynôme quotient résultant de la division de degré i-1.
Ainsi le shift de i positions s'obtient en multipliant c(x) par xi modulo (xn 1).
On peut à présent redéfinir le concept de code cyclique par le théorème suivant :
Théorème: Un code linéaire C dans F EMBED Equation.3 est cyclique si et seulement si C est un idéal de Fq[x]/(xn-1).
Preuve:
On rappelle que C est un idéal de R = Fq[x]/(xn-1) s'il existe a EMBED Equation.3 R et c EMBED Equation.3 C tels que a · c EMBED Equation.3 C.
Pour démontrer ce théorème, il nous faut montrer les deux sens de l'équivalence.
Soit c un mot de code appartenant à C et x, un monôme de degré 1, donc élément de R.
Commençons par montrer que si C est un idéal de R, alors C est cyclique :
C est un idéal de R revient à dire que x · c EMBED Equation.3 C. Or nous avons démontré ci-dessus, que x · c revenait à effectuer un shift d'une position des symboles de c. D'après la définition d'un code cyclique vue au paragraphe 411, nous pouvons donc déduire que C est cyclique.
Démontrons à présent que si C est cyclique, alors il est un idéal de R:
Si C est cyclique, alors tout shift de i positions d'un de ses mots de code est un autre mot de code. Ainsi, on a que tous les éléments xi · c(x), avec 0 d" i d" n-1, sont des mots de code de C. De plus, C étant linéaire, toute combinaison linéaire de plusieurs de ses éléments appartient à C. Si on pose EMBED Equation.3 , un élément arbitraire de R, on a donc:
EMBED Equation.3
Ainsi, comme a(x) · c EMBED Equation.3 C, on déduit que C est un idéal de R.
#
Construction du code:
Polynôme générateur:
C étant un idéal de R, si l'on prend un mot de C et qu'on le multiplie par un polynôme appartenant à R, on obtient un autre mot du code C. Ainsi les mots de C peuvent être définis comme étant la multiplication de deux polynômes u(x) et g(x).
Dans ce paragraphe, nous allons donc montrer qu'il existe un polynôme g(x) tel que tous les c(x) sont des multiples de g(x).
Proposition: Tous les idéaux de R = Fq[x]/(xn-1) sont principaux.
Preuve: Soit I un idéal de R. On veut montrer que l'on peut définir I comme étant I = a · R avec a EMBED Equation.3 R.
Soit a(x) un polynôme de degré minimum, non nul appartenant à I, et b(x) un élément de I.
La division euclidienne de b par a nous donne :
b(x) = q(x) · a(x) + r(x) avec deg(r) < deg(a) ou r(x) = 0
On a donc : r(x) = b(x) - q(x) · a(x)
Etant donné que a(x) et b(x) sont des éléments de I, r(x) est aussi un élément de I. Or a étant de degré minimum, r ne peut avoir un degré inférieur à celui de a, donc r(x) = 0.
On a donc b(x) = q(x) · a(x), d'où I = a(x) · R. L'idéal I de R est donc bien principal.
#
On sait que le code C est un idéal de R. Donc, il s'agit d'un idéal principal. Posons g(x) le polynôme unitaire de degré minimum tel que C = g(x) · R.
On en déduit que les mots de code de C sont obtenus en multipliant un polynôme u(x) par g(x). Ce polynôme g(x) est donc appelé polynôme générateur.
Propriétés importantes de g(x):
Dans ce paragraphe, nous allons démontrer quelques propriétés importantes du polynôme générateur, qui vont permettre de simplifier les processus de codage et de détection des erreurs. Tout au long de ces preuves, nous considérerons le code cyclique C, ayant des mots de code de longueur n, et défini par le polynôme générateur g(x), où :
g(x) = g0 + g1 · x + g2 · x2 +
+ gm · xm
Proposition: g(x) divise xn 1.
Preuve: Posons k = n deg g.
Multiplions g(x) par xk, et réalisons la division euclidienne du polynôme de degré n obtenu par xn 1 :
xk · g(x) = gm · (xn 1) + g(k)(x) où g(k)(x) est g(x) shifté de k positions
Etant donné que l'on effectue ces opérations dans R, les multiplications se font modulo xn 1, et donc gm · (xn 1) = 0, ce qui implique:
xk · g(x) = g(k)(x) mod (xn 1)
Or g(k)(x) étant g(x) shifté de k positions, il s'agit lui-même d'un mot de code, et l'on peut écrire :
g(k)(x) = a(x) · g(x) mod (xn 1) avec a(x) EMBED Equation.3 R
D'où xk · g(x) = a(x) · g(x) mod (xn 1)
g(x) · (xk a(x)) = 0 mod (xn 1)
On en déduit que xn 1 divise g(x) · (xk a(x)). Les degrés de ces deux polynômes étant identiques, on peut écrire que :
xn 1 = g(x) · (xk - a(x))
Si on pose h(x) = xk - a(x), on a donc xn 1 = g(x) · h(x), et donc g(x) divise xn 1.
#
Ainsi pour trouver g(x), on décompose xn 1 en produit de polynômes irréductibles :
xn 1 = f1(x) · f2(x) ·
· ft(x)
Le polynôme g(x) est alors défini comme une combinaison des facteurs fi. On a donc 2t façons de définir g(x), ce qui fait que l'on peut construire 2t codes différents. Dans le paragraphe suivant nous donnons un exemple de la construction de différents codes.
Proposition: Les mots de code sont de la forme c(x) = g(x) · u(x) avec deg(u) < n deg(g).
Preuve: Soit k = n deg(g).
On sait que C est un idéal dans R généré par g(x). Donc C peut être défini par :
C = {g(x) · v(x) / v(x) EMBED Equation.3 R}
Montrons maintenant que tout c(x) peut être exprimé sous la forme :
c(x) = g(x) · u(x) avec deg(u) < k
Soit c(x) C quelconque. On peut donc écrire :
c(x) = g(x) · v(x) pour un certain v EMBED Equation.3 R
Si deg(v) < k, alors la proposition est démontrée.
Soit deg(v) e" k. On réalise la division euclidienne de v par h où h est tel que xn 1 = g(x) · h(x):
v(x) = a(x) · h(x) + b(x) avec deg(b) hqEHCJ mH sH hÌb>hNCJ mH sH h\BhqEHmH sH hNmH sH h\BhNmH sH h\BhN5CJHmH sH hÌb>hN5CJHmH sH hqEHhqEH5CJ0aJ0mH sH hqEHhN5CJ0aJ0mH sH hÌb>hN5CJ(aJ(mH sH (j7hÌb>h$h?5CJ(UaJ(mH sH hÌb>hN5CJ4aJ4mH sH (jhÌb>h$h?5CJ4UaJ4mH sH jh¢T>UmHnHu%*ABCDEFGHIb£¤¥¦§¾ööêêêêêêêêêêêêêêêêêÞêêêêê $
ÆTa$gdqEH $
ÆTa$gdÌ^Û
ÆTgdÌ^Ûl9N:"0JU hÌb>hNCJ mHnHsH %jhÌb>hNCJ UmHnHsH hÌb>hNCJ(OJQJmH sH hÌb>hNmH sH hÌb>hÕ{ CJ mH sH hÕ{ CJ mH sH hqEHhqEHCJ(mH sH hqEHhNCJ(mH sH hqEHhqEHCJ mH sH hqEHhNCJ mH sH hÌb>hqEHCJ mH sH hqEHCJ mH sH hNCJ mH sH hÌb>hNCJ mH sH ¾Öòóôõ÷ø h Ö '
õ
X ² h Ò )
~
Õ
óóçççççÞÕÓÍÇÇÇÇÁÁÍÇÁÁÁ
Æ
ÆÀ
Æà
ÆTgdÌ^Û
ÆTgdÌ^Û $
ÆTa$gdÌ^Û $
ÆTa$gdqEH ; < = > F G H b c d e f g h i j ´ µ ¶ Ð Ñ Ò Ó Ô Õ Ö × Ø ô õ ö ÷ üóßÒþ´¾©´¾´ÒÒóüóÒÃþ´¾w´¾´ÒÒóüócÒ'jz h¢T>h¢T>>*B*Uphÿjý
h¢T>U'j
h¢T>h¢T>>*B*Uphÿ$h¢T>5CJ\aJmHnHsH tH j
h¢T>Ujh¢T>U h¢T> hOh¢T>0JmHnHsH jhOh¢T>0JU'j h¢T>h¢T>>*B*UphÿhOh¢T>0Jh¢T>&÷ û ü
!
"
#
$
%
&
'
(
)
E
F
G
H
L
M
o
p
q
¯
°
±
²
¶
·
Ó
Ô
Õ
ï
ð
ñ
ò
ó
ô
õ
ö
÷
÷è÷ãÙãÎÙãÙÁèÁ÷½÷©Á÷è÷ãÙãÙãÙÁèÁ÷½÷Á÷è÷ãÙãÙãÙÁèÁ÷jë
h¢T>U'jn
h¢T>h¢T>>*B*Uphÿjñ h¢T>U'jt h¢T>h¢T>>*B*Uphÿh¢T>jhOh¢T>0JUj÷ h¢T>Ujh¢T>U h¢T> h¢T>5\mHnHsH tH hOh¢T>0J2÷
6 7 8 R S T U V W X Y Z v w x y ¬ ® ¯ ° ± ² ³ ´ Ð Ñ Ò Ó üóßÒóÃó¾´¾©´¾´ÒÃÒóüóÒóó¾´¾{´¾´ÒÒóüógÒ'j\h¢T>h¢T>>*B*Uphÿjßh¢T>U h¢T>6]mHnHsH tH 'jbh¢T>h¢T>>*B*Uphÿjåh¢T>Ujh¢T>U h¢T> h¢T>5\mHnHsH tH jhOh¢T>0JU'jhh¢T>h¢T>>*B*UphÿhOh¢T>0Jh¢T>(Ó Ù Ú í î ï
- . / 0 2 3 F G H b c d e f g h i j ÷è÷ãÙãÎÙãÙÁèÁ÷½÷©ÁãÙã|ÙãÙÁÁ÷½÷hÁ÷'jPh¢T>h¢T>>*B*UphÿjÓh¢T>U$h¢T>5CJ\aJmHnHsH tH hOh¢T>0JmHnHsH 'jVh¢T>h¢T>>*B*Uphÿh¢T>jhOh¢T>0JUjÙh¢T>Ujh¢T>U h¢T> h¢T>6]mHnHsH tH hOh¢T>0J% ° ± ² Ì Í Î Ï Ð Ñ Ò Ó Ô ð ñ ò ó ù ú
#
$
%
&
'
(
)
*
+
G
H
I
J
P
Q
\
]
^
x
y
z
{
ñèãÙãÎÙãÙÁñÁè½è©ÁèèãÙãÙãÙÁÁè½è{ÁèèãÙãpÙãjÁh¢T>U'jDh¢T>h¢T>>*B*UphÿjÇh¢T>U h¢T>6]mHnHsH tH 'jJh¢T>h¢T>>*B*Uphÿh¢T>jhOh¢T>0JUjÍh¢T>Ujh¢T>U h¢T>hOh¢T>0J h¢T>5\mHnHsH tH ,{
|
}
~
¥
¦
²
³
´
Î
Ï
Ð
Ò
Ó
Ô
Õ
Ö
×
ó
ô
õ
ö
ú
û
()*,-./01MNöéÚéÑÍѹéÑÚÑ´ö´©ö´öéÚéÑÍÑéÑÑ´ö´{ö´öééÑÍÑjµh¢T>U h¢T>5\mHnHsH tH 'j8h¢T>h¢T>>*B*Uphÿj»h¢T>U h¢T>'j>h¢T>h¢T>>*B*Uphÿh¢T>hOh¢T>0J h¢T>6]mHnHsH tH jhOh¢T>0JUjh¢T>U+Õ
/ëCvç_¹
ó^íV±zìeÀkâfÄùóóíùóóùùùóóùóóùóóùóóíùóóëù
Æà
Æ
ÆÀNOPVWuvw¶·¸¹¿ÀÈÉÊäåæèéêëìí
ëÞÕÆÕÁ·Á¬·Á·ÞÆÞÕ¨ÕÞÕÆÕÁ·Á·Á·ÞÆÞÕ¨ÕuÞf hOh¢T>0JmHnHsH 'j&h¢T>h¢T>>*B*Uphÿj©h¢T>U'j,h¢T>h¢T>>*B*Uphÿh¢T>j¯h¢T>Ujh¢T>U h¢T> h¢T>6]mHnHsH tH hOh¢T>0JjhOh¢T>0JU'j2h¢T>h¢T>>*B*Uphÿ' !"@ABCDEabcdhiuvw¶·¸¹¿íÞÙÏÙÄÏÙÏ·í·®ª®·®®ÙÏÙ|ÏÙÏ··®ª®h·®'jh¢T>h¢T>>*B*Uphÿjh¢T>U h¢T>5\mHnHsH tH 'j h¢T>h¢T>>*B*Uphÿh¢T>hOh¢T>0JjhOh¢T>0JUj£h¢T>Ujh¢T>U h¢T> hOh¢T>0JmHnHsH $h¢T>5CJ\aJmHnHsH tH $¿Àäåæ %&'(./STUopqstuvwxÄÅÆàáâäñèãÙãÎÙãÙÁñÁè½è©ÁèñèãÙãÙãÙÁñÁè½èÁè{èãÙãpÙãj h¢T>U h¢T>5\mHnHsH tH 'j h¢T>h¢T>>*B*Uphÿj h¢T>U'j h¢T>h¢T>>*B*Uphÿh¢T>jhOh¢T>0JUjh¢T>Ujh¢T>U h¢T>hOh¢T>0J h¢T>6]mHnHsH tH ,äåæçèé
XYZ\]^_`a}~
²³´¶·¸¹º»×ØÙÚàöéÚéÑÍѹéÑÚÑ´ö´©ö´öéÚéÑÍÑéÑÚÑ´ö´ö´öéÚéÑÍÑvéÑ'jü h¢T>h¢T>>*B*Uphÿj h¢T>U'j h¢T>h¢T>>*B*Uphÿj
h¢T>U h¢T>'j h¢T>h¢T>>*B*Uphÿh¢T>hOh¢T>0J h¢T>5\mHnHsH tH jhOh¢T>0JUjh¢T>U.àáíîï
./0178bcd~
£¤¥¦ª«ÐÑÒìíîðñèãÙãÎÙãÙÁñÁè½è©ÁèñèãÙãÙãÙÁñÁè½èÁè{èãÙãpÙãjm"h¢T>U h¢T>5\mHnHsH tH 'jð!h¢T>h¢T>>*B*Uphÿjs!h¢T>U'jö h¢T>h¢T>>*B*Uphÿh¢T>jhOh¢T>0JUjy h¢T>Ujh¢T>U h¢T>hOh¢T>0J h¢T>6]mHnHsH tH ,ðñòóôõ;U'jä#h¢T>h¢T>>*B*Uphÿjg#h¢T>U h¢T> h¢T>6]mHnHsH tH 'jê"h¢T>h¢T>>*B*Uphÿh¢T>hOh¢T>0J h¢T>5\mHnHsH tH jhOh¢T>0JUjh¢T>U+
345OPQSTUVWXtuvw}~ª«¬®¯°±²³ÏÐÑÒØÙëÞÕÆÕÁ·Á¬·Á·ÞÆÞÕ¨ÕÞÕ
ÕÁ·Áz·Á·Þ
ÞÕ¨ÕfÞÕ
'jÒ&h¢T>h¢T>>*B*UphÿjU&h¢T>U h¢T>6]mHnHsH tH 'jØ%h¢T>h¢T>>*B*Uphÿh¢T>j[%h¢T>Ujh¢T>U h¢T> h¢T>5\mHnHsH tH hOh¢T>0JjhOh¢T>0JU'jÞ$h¢T>h¢T>>*B*Uphÿ(Ùîïð
/01267WXYstuwxyz{|¡¢ÉÊËåæçéê÷òèòÝèòèÐÁÐ÷½÷©Ð÷÷òèòèòèÐÐ÷½÷{Ð÷Á÷òèòpèòèjC)h¢T>U'jÆ(h¢T>h¢T>>*B*UphÿjI(h¢T>U h¢T>5\mHnHsH tH 'jÌ'h¢T>h¢T>>*B*Uphÿh¢T> h¢T>6]mHnHsH tH jhOh¢T>0JUjO'h¢T>Ujh¢T>U h¢T>hOh¢T>0J,êëìíî
BCD^_`bcdefg
¹º»½¾¿ÀÁÂòãòÚÖÚÂòÚãÚ½³½¨³½³òãòÚÖÚò
r
½³½g³½³òròÚj7+h¢T>U$h¢T>5CJ\aJmHnHsH tH hOh¢T>0JmHnHsH 'jº*h¢T>h¢T>>*B*Uphÿj=*h¢T>Ujh¢T>U h¢T>'jÀ)h¢T>h¢T>>*B*Uphÿh¢T>hOh¢T>0J h¢T>6]mHnHsH tH jhOh¢T>0JU(ÂÞßàáåæòóô3456h¢T>>*B*Uphÿj1,h¢T>Ujh¢T>U h¢T> h¢T>5\mHnHsH tH jhOh¢T>0JU'j´+h¢T>h¢T>>*B*UphÿhOh¢T>0Jh¢T>(¿ÀÁÛÜÝßàáâãäCDE_`acdefgh
¡¢£½¾¿ÁÂ÷è÷ãÙãÎÙãÙÁèÁ÷½÷©Á÷ãÙãÙãÙÁèÁ÷½÷Á÷{÷ãÙãpÙãÙj0h¢T>U h¢T>5\mHnHsH tH 'j/h¢T>h¢T>>*B*Uphÿj /h¢T>U'j¢.h¢T>h¢T>>*B*Uphÿh¢T>jhOh¢T>0JUj%.h¢T>Ujh¢T>U h¢T> h¢T>6]mHnHsH tH hOh¢T>0J,ÂÃÄÅÆâãäåëì !"#$%ABCDJKjkl«¬òãòÚÖÚÂòÚ³Ú®¤®¤®¤ò³òÚÖÚ
òÚ³Ú®¤®z¤®¤ò³òÚÖÚj
2h¢T>U'j1h¢T>h¢T>>*B*Uphÿj1h¢T>Ujh¢T>U h¢T> h¢T>6]mHnHsH tH 'j0h¢T>h¢T>>*B*Uphÿh¢T>hOh¢T>0J h¢T>5\mHnHsH tH jhOh¢T>0JU*Ä#àQ±~ßh¢T>>*B*Uphÿh¢T>j3h¢T>Ujh¢T>U h¢T> h¢T>6]mHnHsH tH hOh¢T>0JjhOh¢T>0JU'j2h¢T>h¢T>>*B*Uphÿ(yª«¬®¯°±²³ÏÐÑÒØÙòóô3456:;[\]wxy{|÷òèòÝèòèÐÁÐ÷½÷©Ð÷Á÷òèòèòèÐÁÐ÷½÷Ð÷{÷òèòpèòèjï6h¢T>U h¢T>5\mHnHsH tH 'jr6h¢T>h¢T>>*B*Uphÿjõ5h¢T>U'jx5h¢T>h¢T>>*B*Uphÿh¢T> h¢T>6]mHnHsH tH jhOh¢T>0JUjû4h¢T>Ujh¢T>U h¢T>hOh¢T>0J,|}~¥¦¼½¾ØÙÚÜÝÞßàáýþÿ 5 6 7 9 : ; Z [ òãòÚÖÚÂòÚ³Ú®¤®¤®¤ò³òÚÖÚ
òÚ³Ú®¤®z¤®¤ò³òÚÖÚjã8h¢T>U'jf8h¢T>h¢T>>*B*Uphÿjé7h¢T>Ujh¢T>U h¢T> h¢T>6]mHnHsH tH 'jl7h¢T>h¢T>>*B*Uphÿh¢T>hOh¢T>0J h¢T>5\mHnHsH tH jhOh¢T>0JU*[ \ ] c d l m n ® ¯ ° ¶ · Í Î Ï é ê ë í î ï ð ñ ò ëÞÕÆÕÁ·Á¬·Á·ÞÆÞÕ¨ÕÞÕÆÕÁ·Á·Á·ÞÆÞÕ¨ÕuÞÕf h¢T>5\mHnHsH tH 'jT;h¢T>h¢T>>*B*Uphÿj×:h¢T>U'jZ:h¢T>h¢T>>*B*Uphÿh¢T>jÝ9h¢T>Ujh¢T>U h¢T> h¢T>6]mHnHsH tH hOh¢T>0JjhOh¢T>0JU'j`9h¢T>h¢T>>*B*Uphÿ( F G H b c d f g h i j k ° ± ² Ì Í Î Ð Ñ Ò Ó Ô Õ ñ ò ó ô ú û ! " @ A ÷òèòÝèòèÐÁÐ÷½÷©Ð÷÷òèòèòèÐÐ÷½÷{Ð÷÷òèòpèòèjÅ=h¢T>U'jH=h¢T>h¢T>>*B*UphÿjËU h¢T>6]mHnHsH tH 'jNh¢T>>*B*Uphÿh¢T> h¢T>5\mHnHsH tH jhOh¢T>0JUjÑ;h¢T>Ujh¢T>U h¢T>hOh¢T>0J,A B C D E a b c d j k s t u ´ µ ¶ · ¹ º É Ê Ë å æ ç é ê ë ì í î òãòÚÖÚÂòÚãÚ½³½¨³½³òãòÚÖÚò
r
½³½g³½³òròÚj¹?h¢T>U$h¢T>5CJ\aJmHnHsH tH hOh¢T>0JmHnHsH 'j
