Vendredi 13 novembre 1998 Arash Habibi TD6.text Le mercredi 11 novembre il n'y a pas eu TD. I. J'ai commence par distribuer le poly de Pascal M et par reecrire l'algorithme de Lempel-ziv en pseudo-code au tableau II. Une remise au point au sujet de la compression. Certains avaient compris que la compression pouvait servir a la detection d'erreur. 1/ Exercice : On dispose d'un canal de transmission qui peut transmettre jusqu'a R=2000 bauds sur deux niveaux. On veut transmettre sur ce canal, un flot de donnees constitue de 8 symboles (a,b,c,d,e,f,g,h) a raison de 1000 caracteres par seconde. a/ Dans le cas ou a priori les symboles sont equiprobables proposer un codage. Est-ce qu'avec ce codage, on peut transmettre ce flot de donnees sur ce canal ? Reponse : codage bete : a:000 b:001 c:010 d:011 e:100 f:101 g:110 h:111 Ce qui nous fait 3 bits par symboles d'ou un rythme de 3000 bit/s. Or sur le canal on ne dispose que de 2000bauds. Donc ca ne passe pas. b/ En fait il s'agit d'un message particulier ou parmi les 8 symboles, on n'en trouve que deux : a et h. Proposer une compression possible. Est-ce qu'avec cette compression ca passe ? Reponse : compression possible : 000 -> 0 et 111 -> 1 (On elimine la redondance) Ce qui nous fait 1 bit/symbole A raison de 1000 symboles par seconde ca nous fait 1000bit/s < 2000 donc ca passe. Conclusion : Quelquefois il suffit de comprimer un flot de donnees pour que ce qui ne passait pas puisse passer. III. Compression vs Erreur a:000 a:0 h:111 h:1 non-compresse compresse Des deux codes, c'est lequel qui prend le moins de bande passante ? Et pour les erreurs ? - Avec le compresse la moindre erreur est indetectable. Au lieu de 000 (aaa) on recoit 010 (aha) on n'y a vu que du feu. - Avec le non compresse on peut avoir jusqu'a un bit faux tous les trois bits : quand on recoit 010 on sait que c'est une erreur et si la frequence d'erreur ne peut pas depasser 1bit/3 alors on peut aussi corriger l'erreur (010 correspond a 000->a) Si on veut juste detecter les erreurs on peut aller jusqu'a une frequence d'erreur de 2bit/3. Compression et erreur sont souvent antinomiques La compression consiste a enlever la redondance, alors que la detection d'erreur revient souvent a rajouter de la redondance. La redondance peut etre une simple repetition (comme ci-dessus ou comme le prof qui repete plusieurs fois ce qu'il a dit pour que les gens du fond puisse entendre aussi). Mais ce n'est pas toujours une repetition. Ca peut etre aussi n'importe quoi qui permette de retrouver l'information utile. Il s'agit souvent d'interdire beaucoup de mots de code et ne permettre qu'un ensemble limite. Par exemple l'alphabet des aviateurs. Il y a une information utile (les lettres de l'alphabet) et les mots de code (seuls ces mots de code sont permis) Quand une erreur apparait, on raccroche au mot de code le plus proche. info:code A: Alpha O: Oskar B: Bravo P: Papa C: Charlie Q: Quebec D: Delta R: Romeo E: Echo S: Sierra F: Fox(trot) T: Tango G: Golf U: Uniform H: Hotel V: Victor I: India W: Whisky J: Juliet X: Xray K: Kilo Y: Yankee L: Lima Z: Zoulou M: Mike N: Novembre Au lieu de dire HDLC, on dit Hotel Delta Lima Charlie Ca prend plus de bande passante, mais on peut avoir l'immatriculation d'un appareil, quelque soit la friture sur la ligne et quelque soit l'accent de l'aviateur. IV. Correction/Detection d'erreur Les erreurs possibles se comptent en nombre de bits dans une chaine (en distance de Hamming). Si sur un medium on peut avoir 5 bits qui changent dans une trame, alors il faut avoir des mots de code qui sont au moins distants de 5+1 pour pouvoir detecter toutes les erreurs. Pour corriger les erreurs il faut que la distance entre les mots de code soit au moins de 2*5+1 = 11. \begin{representation} Representation adhoc : Les mots de 1bit peuvent etre representes sur un segement de droite 0---1 Les mots de 2bits peuvent etre representes sur un carre : 10-----11 | | | | | | | | 00-----01 Les mots de 3 bits peuvent etre representes sur un cube : 110----111 |\ |\ |100----101 | | | | | | | | 010|---011| \| \| 000----001 Et on peut continuer pour les mots de 4 bits, 5 bits etc. L'avantage de cette representation est qu'une erreur d'un bit revient a se deplacer le long d'une arete. \end{representation} Revenons a notre alphabet de 8 lettre a, b, c, d, e, f, g, h g------h |\ |\ | e------f | | | | | | | | c-|----d | \| \| a------b Toute erreur nous fait venir sur un autre code permis : Distance de Hamming : 1 Pas de detection, pas de correction Autre code avec juste 4 symboles (E == erreur) d------E |\ |\ | E------c | | | | a 00 0 | | | | b 01 1 E-|----b | c 11 0 \| \| d 10 1 a------E Distance de Hamming : 2 detection d'une erreur, pas de correction 1 bit de redondance : le dernier bit peut toujours se retrouver avec les deux premiers Autre code avec juste 2 symboles (E == erreur) E------b |\ |\ | E------E | | | | | | | | a 0 00 E-|----E | b 1 11 \| \| a------E Distance de Hamming : 3 detection de deux erreurs ou Correction d'une erreur. Deux bits de redondance puisque les deux derniers bits peuvent toujours etre retrouves avec le premier. V. CRC Parite : les mots de code sont l'ensemble des mots dont la somme des digits est 0 (%2) Dans le mot de code il y a un bit de redondance (le bit de controle) qui vaut 0 ou qui vaut 1 pour que la somme des digits soit effectivement paire. CRC (Cyclic Redundancy Check): Idem sauf que les mots et les informations sont consideres comme des polynomes : (e.g. 11101001 est un polynome de degre 7 : x7 + x6 + x5 + x3 + x0) Pour pouvoir bien separer l'info et les bits de controle, tout est fait modulo 2. En modulo2 addition = soustraction = OU exclusif (jamais de report) Dans la suite : I(x) : info G(x) : polynome generateur C(x) : mot de code (info ET bits de controle) Les mots de code sont les multiples d'un polynome generateur qui est connu de l'emetteur et du recepteur. Les bits de redondance (les bits de controle) sont la pour que tous les mots de code soient effectivement divisibles par ce polynome generateur Au decodage : on fait la division C(x)/G(x) si on trouve une reste nulle alors tout va bien. Sinon il y a une erreur Au codage : Soit n le degre du generateur Je prends I(x) x^n --> dividende (Si n=2 et I(x)=1011001 alors I(x)x^n = 1011001 00) Faire la division par le polynome generateur. Le quotient on s'en fout On prend le reste et on l'ajoute a I(x)x^n C(x) = I(x).X^n + R(x) Or par definition de la division : I(x)X^n = Q(x)G(x) + R(x) Donc C(x) = Q(x)G(x) + R(x) + R(x) = Q(x)G(x) (%2) Donc C(x) est bien multiple de G(x) Comment faire la division polynomiale modulo 2 ? Codage I(x) = 100110 G(x) = 101 100110 00 | 101 101 ---------- --- 11 000 --- 111 101 --- 100 101 --- 1 0 00 0 ---- 1 00 1 01 ---- 01 C(x)= 100110 01 Decodage C(x) = 100110 01 100110 01 | 101 101 ---------- --- 11 000 --- 111 101 --- 100 101 --- 1 0 00 0 ---- 1 01 1 01 ---- 00 Pas d'erreur Exercic : cf Tannenbaum I(x) = 1101011011 G(x) = 10011 (19) ... R(x) = 1110 Exercice : cf Halsall I(x) = 11100110 G(x) = 11001 ... R(x) = 110 VI. Les bascules pour la division modulo 2 Recette (on comprendra apres) Si le polynome generateur est de degre n alors on prend un registre a decalage avec n buffers On applique l'exemple du Tannenbaum. Supposons qu'il n'y a pas le peigne au dessus. Dans ce cas, a chaque top d'horloge, les chiffres avancent d'un pas dans les buffers. Maintenant, supposons que le cinquieme chiffre soit toujours 0. Dans ce cas, les chiffres ne font qu'avancer vers la gauche. Mais quand en plus il y a un 1 en X^4, alors les chiffres qui passent par les '+' sont changes. Au depart tout est initialise a 0. __________________>_____________________________>________ | | | | | | ^ ______ ______ ______ V ______ V | | | | | | | | | | | |-<-|buff|---|---|buff|---|---|buff|-- + ---|---|buff|-- + -<-|-<- 1101011011 0000 | |____| | |____| | |____| XOR | |____| XOR | X^4 X^3 X^2 X^1 X^0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 1 1 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 1 1 1 0 D'ou le reste qui est bien de 1110 En fait si on compare ces lignes avec les divisions a la main, on voit bien que ce sont les dividendes intermediaires. VII. Et puis pour finir j'ai dit deux mots du TP.