#usr/bin/python#encoding:utf8#ceci#est#un#script#en#python#youpiimport itertoolsimport randomdef hamming(a,b): return bin(a^b).count("1")"""On cherche à générer 2**12 vecteurs distants deux à deux d'au moins 7(en distance de Hamming).On pose que le mot nul (poids de hamming = 0) est valide,et on cherche à générer un ensemble de mots valides de poids 7(les plus proches).Chaque mot de poids 4 doit correspondre à un unique mot validede poids 7. On peut donc faire un brute-force sur les mots de poids4, suivi (chaque fois qu'on en trouve un encore non-couvert) d'un bfsur les triplets susceptibles de le compléter."""u7 = set()for _v4 in itertools.combinations(range(23),4): v4 = sum(1<<i for i in _v4) if any(hamming(v4,v)<=3 for v in u7): continue for _v3 in itertools.combinations(range(_v4[-1]+1,23),3): v3 = sum(1<<i for i in _v3) if all(hamming(v4|v3,v)>=7 for v in u7): u7.add(v4|v3) break"""Les mots valides d'un code forment un espace vectoriel.En effet, soit un espace dont les éléments sont {e_1, ... e_n},et tel que hamming(e_i, e_j)>=7 (i!=j).On y introduit un nouveau vecteur V qui respecte la même condition.L'ensemble devient:{e_1, ..., e_n, e_1^V, ..., e_n^V}La condition se propage à toutes les nouvelles combinaisons:hamming(e_i, e_j^V) = hamming(e_i^e_j, V) qui est >=7 par hypothèse.On peut générer l'ensemble des mots valides en partant de l'espace trivial {0} et en combinant avec les mots de poids 7."""u23 = set([0])base = []for v in sorted(u7): smp = random.sample(u23,1)[0] if smp^v not in u23: u23.update([v^w for w in u23]) base.append(v)assert(len(u23)==4096 and len(base)==12)print "Base:"for v in base: print format(v,"023b")#for v in sorted(u23):print format(v, "023b")#vérificationhamdict=dict()for i,j in itertools.combinations(u23,2): h=hamming(i,j) hamdict[h]=hamdict.get(h,0)+1assert(min(hamdict.values())>=7)print hamdict