IFT6170 Claude Crépeau. 39

IFT6170 Devoir 3

à rendre au début du cours le mercredi 5 novembre 1997

Équivalence de problèmes sur les codes [4 points]

Démontrez l’équivalence polynomiale des problèmes PMCS0 et PPMC restreints aux mots de codes (dans les deux directions).

Duaux [4 points]

Donnez pour chaque q, le plus grand ϵ_{q} que vous puissiez pour lequel il existe une famille de codes {C_{n}}_{n>n_{0}} et sa famille de codes duaux {C_{n}^{⊥}}_{n>n_{0}} constituées de codes linéaires C_{n}, C_{n}^{⊥} ⊆ F_{q}^{n} qui soient tous deux de distance minimale ϵ_{q}n. Justifiez votre réponse. Quelle est la valeur de lim_{q→∞} ϵ_{q}?

Donnez le plus petit ϵ que vous puissiez pour lequel il n’existe pas de famille de codes {C_{n}}_{n>n_{0}} et sa famille de codes duaux {C_{n}^{⊥}}_{n>n_{0}} constituées de codes linéaires C_{n}, C_{n}^{⊥} ⊆ F_{2}^{n} dont la distance minimale moyenne des deux soit ϵn. Justifiez votre réponse.

Codes Intersectants [8 points]

On dit qu’un code C engendré par G est intersectant si pour toute paire de mots de codes c_{0}, c_{1} ∈ C − {0} il existe une position i où c_{0}^{i} ≠ 0 ≠ c_{1}^{i}. Soit G la matrice génératrice n × k d’un code intersectant sur

F_{2}.Par exemple la matrice G = [ \begin{matrix}1 & 1 & 0 \\ 0 & 1 & 1 \end{matrix} ] engendre un code intersectant puisque ses mots de codes sont

000, 110, 011, 101 et que 110, 101 intersectent en position 1, 110, 011 intersectent en position 2, et 011, 101 intersectent en position 3.

1. Montrez que deux mots binaires c_{0}, c_{1} intersectent si et seulement si w(c_{0} ⊕ c_{1}) ≠ w(c_{0}) + w(c_{1}).

2. Donnez un code intersectant binaire de longueur n = 18 et dimension k = 6.

3. Montrez que pour un [n, k, d] code intersectant binaire on a toujours d ≥ k.

4. Montrez qu’asymptotiquement il n’existe pas de code intersectant binaire pour n < 3.53k.

5. Montrez qu’asymptotiquement il existe un code intersectant binaire pour n > 4.81k.