IFT6170 Devoir 1

à rendre au début du cours le mercredi 1 octobre 1997

Polynôme Irréductible [4 points]

Considérez l’ensemble des nombres modulo 17 étiquetés ainsi:

{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,G},

les symboles “A,B,C,D,E,F,G” repésentant les nombres 10,11,12,13,14,15,16. On utilise sur ces nombres les opérations d’addition, soustraction et multiplication modulo 17. Par exemple F + 1 ≡ G (mod 17) et 3 ∗ A ≡ D (mod 17). On considère les polynômes sur F_{17} comme une suite finie de symboles parmis l’ensemble ci-haut. Par exemple (1 0 1 0 0 0 A B C D E F G) correspond à

1x^{12} + 1x^{10} + Ax^{6} + Bx^{5} + Cx^{4} + Dx^{3} + Ex^{2} + F x + G.

Donnez un polynôme irréductible sur F_{17} de degré 23 contenant votre date de naissance de façon consécutive dans sa représentation ainsi qu’une preuve de ce fait. Par exemple pour 17-02-62

(1 7 0 2 6 2 0 0 0 0 0 0 0 0 0 0 0 A 5 4 2 1 F 7)

pourrait être un tel polynôme contenant ma date de naissance. ( Je n’ai pas vérifié s’il est irréductible. )

Donnez également un élément primitif du corps fini engendré par votre polynôme. Pour vous aider, sachez que 17^{23} −1 = 2^{4} ∗47∗26552618219228090162977481. Vous pouvez utiliser les moyens (ordinateurs, logiciels, etc) que vous voudrez pour obtenir votre réponse.

Dual des codes de Hamming [4 points]

Les codes de Hamming forment une famille infinie {H_{m}}_{m>0} de codes linéaires binaires ayant les paramètres [2^{m}−1, 2^{m}−m−1, 3]. Donnez les paramètres [n_{m}, k_{m}, d_{m}] des codes {H_{m}^{⊤}}_{m>0} duaux des codes de Hamming en fonction de m. Ces codes sont-ils parfaits? Prouvez vos réponses.

Codes ISBN [4+1 points]

Le code ISBN que l’on trouve sur les livres est un code linéaire sur F_{11} où l’on utilise l’alphabet

{0,1,2,3,4,5,6,7,8,9,X},

le symbole “X” repésentant le nombre 10. Les paramètres de ce code sont [10, k, d]. Utilisez un certain nombre de livres (donnez les titres et numéro ISBN des livres utilisés) afin de déterminer une matrice génératrice pour ce code, sous forme systématique. Donnez les valeurs de k et d pour ce code. Démontrez finalement que ce code a la propriété supplémentaire que si l’on permute deux symboles différents d’un mot de code, le mot résultant n’est plus un mot de code. Justifiez vos réponses.

Un point supplémentaire à celui ou celle qui trouvera un plus petit ensemble de livres (je veux les titres et les codes ISBN) dont les codes ISBN sont linéairement dépendants...

Canaux de transmission [total 4 points]

–canal majorité [1.5 points]

Considérez le canal suivant:

MAJ_{ϵ}^{k}(x) = maj \{\overbrace{BS_{ϵ}(x), BS_{ϵ}(x), ..., BS_{ϵ}(x)}^{2k−1}\}.

C’est-à-dire que MAJ_{ϵ}^{k}(x) retourne le bit majoritaire parmis 2k − 1 exécutions indépendantes de BS_{ϵ}(x). Trouvez un ϵ_{k} tel que

MAJ_{ϵ}^{k}(x) = BS_{ϵ_{k}}(x).

Montrez que

lim_{k→∞} ϵ_{k} = 0.

–canal xor [1.5 points]

Considérez le canal suivant:

XOR_{ϵ}^{k}(x) = \overbrace{BS_{ϵ}(x) ⊕ BS_{ϵ}(x) ⊕ ... ⊕ BS_{ϵ}(x)}^{2k−1} .

C’est-à-dire que XOR_{ϵ}^{k}(x) retourne le ou–exclusif de 2k − 1 exécutions indépendantes de BS_{ϵ}(x). Trouvez un ϵ_{k} tel que

XOR_{ϵ}^{k}(x) = BS_{ϵ_{k}}(x).

Montrez que

lim_{k→∞} ϵ_{k} = 1/2.

–canal mixte [1 point]

Soient U = BS_{ϵ}(x) et V = BS_{ϵ}(x) deux échantillons indépendants obtenus à travers un canal bruyant de probabilité d’erreur ϵ. Considérez le canal suivant:

MIX_{ϵ}(x) = \{ \begin{matrix}b & si U = V = b \\ ε & si U ≠ V \end{matrix} .

C’est-à-dire que MIX_{ϵ}(x) retourne le bit commun obtenu de deux exécutions indépendantes de BS_{ϵ}(x), mais la chaîne nulle si ces deux exécutions ne donne pas la même réponse. Trouvez des α, β tels que

MIX_{ϵ}(x) = EF_{α}(BS_{β}(x)).