Existe-t-il un code binaire de longueur 6, de taille 32 et de distance 2?

Le problème est de prouver ou de réfuter l'existence de $C$ , st, ; ; . ( signifie hamming distance)$|c| = 6,\forall c\in C$$|C| = 32$$d(c_i,c_j)\geq2,1\leq i<j\leq32$$d$

J'ai essayé de construire un code satisfaisant. Le mieux que je puisse obtenir est de laisser , une concaténation de , qui est de taille 16. 32 se trouve être la limite supérieure théorique de la taille, maintenant je ne sais pas quoi faire ensuite pour résoudre le problème.$C = C'\times C'$$C' = \{000,011,110,101\}$

Oui, il existe un tel ensemble. Vous êtes en fait sur la bonne voie pour trouver l'exemple suivant.

Soit . Vous pouvez vérifier les éléments suivants.$C = \{c : |c|=6 \text{ and there are even number of 1's in c}\}$

• $|C|=32$ .
• $d(u,v)\geq2$ pour tout , . (En fait, ou 4 ou 6.)$u,v\in C$$u\not=v$$d(u,v)=2$

Voici quatre exercices connexes, classés par ordre de difficulté croissante. Comme dans la question, seul le code binaire est concerné.

Exercice 1. Donnez un autre exemple d'un ensemble de 32 mots de longueur 6 et d'une distance par paire d'au moins 2.

Exercice 2. Montrez qu'il n'y a que deux ensembles de ce type, comme indiqué dans la réponse et dans l'exercice 1.

Exercice 3. Généraliser ce qui précède à des mots d'une longueur donnée et d'une distance par paire d'au moins 2. (Indice, .)$32=2^{6-1}$

Exercice 4. (généralisation supplémentaire indiquée dans la réponse de Yuval) Si est la taille maximale d'un code de longueur et la distance par paires minimale , alors .$A(n,d)$$n$$d$$A(d,2d)=A(n-1,2d-1)$

Tous les mots de parité paire à partir d'un code linéaire avec mots de code et une distance minimale de .$2^{n-1}$$2$

Plus généralement, si est la taille maximale d'un code de longueur et de distance minimale , alors .$A_2(n,d)$$n$$d$$A_2(n,2d) = A_2(n-1,2d-1)$