CHARADES ET CODES CORRECTEURS
(Texte faisant suite à l'article "Charades et codes correcteurs ?" Quadratures 52, Avril-Juin 2004)
Définitions
Charades à parités
Charades à tiroir
Charades optimales de petite taille
Charades longues


Toute contribution est bienvenue
(ronan.quarez@univ-rennes1.fr)




DÉFINITIONS

Une charade est une suite de symbole de la forme c = (c1, c2 , ..., ck, ck+1, ck+2, ..., cn), où il ne pèse aucune contrainte sur les k premiers symboles d'information c1, c2 , ..., ck tandis que les n-k suivants ck+1, ck+2, ..., cn consitutent une redondance et s'expriment en fonction des k premiers. L'ensemble des charades qui sont décrites par les relations portant sur les symboles de redondances est appelée un code.

Les symboles ci sont des éléments d'un Alphabet, qui peut être vu comme le semigroupe libre engendré par les syllabes. L'Alphabet est muni d'une opération interne : la concaténation que l'on note additivement. Si l'on désire que la soustraction deviennent une opération interne, on doit étendre l'Alphabet à l'ensemble des sommes et des différences de syllabes. L'Alphabet ainsi obtenu est le  symétrisé de l'Alphabet de départ et possède alors une structure de groupe. C'est le groupe libre engendré par les syllabes.


Par exemple, le code de parité (peut être le code correcteur d'erreurs le plus célébre) est défini comme l'ensemble des éléments du type (c1, c2 , ..., ck, ck+1) qui satisfont la relation ck+1= c1+ ... + ck. Si on définit le "tout" comme la somme des symboles d'information, une charade classique s'interprète juste comme un élément du code de parité.


CHARADES À PARITÉS

1) Parité multiple
Soit la charade de code : (c1, c2 , c3, c4 , c1 + c3 , c2 + c4 , c1 + c2 + c3 + c4)

Mon premier est pathologique,
Mon deuxième l'est pas,
Mon troisième en est le double,
De mon quatrième, elle en est la quatrième,
La somme de mes impairs tache, surtout si elle est consommée sur le dos d'un âne,
La somme de mes pairs se tartine sur du pain ou du sable,
Mon tout en témoigne si on arrive au bout.




2) Tout alterné
Soit le code : (c1 , c2 , ..., ck , c1 – c2 + c3 – c4 +...+ (–1)kc k)
Et une charade associée au cas k = 8 :


Mon premier taille,
Mon deuxième garde,
Mon troisième rame,
Mon quatrième bulle,
Mon cinquième est sueur,
Mon sixième est une matière première recherchée
quand on en veut pour son argent et encore plus,
Mon septième s'étend dans le sol,
Mon huitième s'étend sur les murs,
Mon tout alterné est une fable parmi les plus fameuses.




3) L'alterné tout
Soit la charade de code : (c1 , c2 , ..., ck , – c1 + c2– c3 + c4 +...+ (–1)k–1 c k)
Et une charade associée au cas k = 6 :

Mon premier est féminin,
Mon deuxième fait la vaisselle,
Mon troisième est féminin,
Mon quatrième ne fait pas la vaisselle,
Mon cinquième est féminin,
Mon sixième est accomplit devant la télé pendant la vaisselle,
Mon alterné tout ne semble pas être respecté au sein du foyer.




4) Tout et tout alterné
Soit le code type (14, 12 , 3) mêlant tout et tout alterné : (c1 , c2 , ..., c12 , c1 + c2 +...+ c 12 , c1 - c2+ ... + c11 – c 12)
Et la charade associée suivante, au sens caché...

Mon premier pour rendre docile,
Mon deuxième est étalon,
Mon troisième est leader, en couture comme ailleurs,
Mon quatrième récolte la monnaie,
Mon cinquième est emporté,
Mon sixième est passionné,
Mon septième se pratique à la sortie du fourneau,
Mon huitième se pratique à l'entrée en guerre,
Mon neuvième est complètement sans relief le,
Mon dixième a tendance à se trouver au milieu... sache « qu'il te ment le bougre ! »,
Mon onzième pourrait s'appeler Monopoly,
Mes douzièmes siègent à l'Olympe,
Mon tout est une revendication radicale,
Mon tout alterné résulte du succès de mon Tout.





CHARADES À TIROIR


CHARADES OPTIMALES DE PETITE TAILLE
On définit deux paramètres du code, à savoir la taille, traditionnellement notée n, et la dimension k qui mesure le nombre de symboles d'information.

Pour mesurer l'efficacité de la redondance introduite, il est une autre quantité qui revêt une importance : la distance minimale. Pour deux n-uplets c = (c1, c2 , ..., cn) et c' = (c'1, c'2 , ..., c'n), on définit la distance d(c, c') de c à c' comme le nombre d'indices i compris entre 1 et n tels que ci ≠ c'i. On appelle alors d la distance minimale du code, qui est la plus petite valeur de d(c, c') lorsque c et c' parcourent le code de telle sorte que c ≠ c'.

Le triplet (n, k ,d) est appelé le type du code ou de la charade.

Exemple : La distance minimale du code à parité est égale à 2.


Les charades optimales sont celles qui réalisent l'égalité dans l'inégalité de Singleton :

k + d ≤ n + 1


Question : Trouver des exemples de charades optimales. Ou à défaut, des exemples de charades qui s'approchent le plus du cas d'égalité.

1) Un code Vandermonde de redondance de taille 2
Soit le code, de type (5, 3, 3), donné par le codage : (c1, c2 , c3 , c1 + c2 + c3 , c1 + 2 c2 + 3 c3).
En voici deux exemples de charades associées, (un peu capilotractées certes).


a)

Mon premier est l'action de celui qui en aime, de nombreux et indéterminés,
Mon deuxième se doit d'être scrupuleusement respecté par les déménageurs,
Mon troisième se doit d'être scrupuleusement respecté par les musiciens,
Mon Vandermonde s'interroge sur les sentiments de quelqu'un que tu connais bien,
Mon tout témoigne de l'aversion de cette même personne.





b)


Mon premier est l'action de celui qui se donne sans réserve à...
Mon deuxième est un petit sur terre,
Mon troisième est gros dans l'eau,
Mon Vandermonde est une union que tu connais bien,
Mon tout est l'expression d'une sensualité, toutes lumières éteintes.




Note : je voudrais m'excuser d'avoir dévoilé dans ces lignes des données familliales confidentielles. Que ma tata et mon tonton me pardonnent.


x) D'autres charades optimales

Les charades à parité classique, ou encore les variantes du tout alterné ou de l'alterné tout sont optimales.
La charade à parité mêlées 4) est un exemple de charade optimale qui ne soit pas de même nature.



CHARADES LONGUES