Suche nach n Bitvektoren mit Hamming-Distanz d zueinander.



  • Hallo, ich suche numerisch eine handvoll (mehr ist numerisch nicht drin) Bitvektoren

    std::bitset<N>
    

    die alle zueinander die gleiche Hamming-Distanz aufweisen (ausser zu sich selbst).

    In etwa sowas:

    std::vector<std::bitset<256>> bitsets = do_magic<256>(3,100); // 3 Elemente, Distanz 100
    
    if ( (bitsets[0]^bitsets[1]).count() == 100 &&
         (bitsets[0]^bitsets[2]).count() == 100 &&
         (bitsets[1]^bitsets[2]).count() == 100 )
      std::cout << "nice" << std::endl;
    

    Wie sollte die Funktion

    template <size_t N>
    std::vector<std::bitset<N>> do_magic(size_t size, size_t dist);
    

    definiert werden? Was meint ihr?

    Danke



  • Eine schnelle Gedankenskizze
    1.) Wähle Zahl A zufällig und trage diese in die Liste L ein
    2.) Setze Zahl D (=Distanz) so dass die ersten X Bits gesetzt sind
    3.) Berechne B = A xor D
    4.) Füge B in L ein, sofern diese nicht schon vorhanden ist
    5.) D = random_shuffle(D)

    Die Idee dahinter ist folgende:
    A xor B = A xor (A xor D) = 0 xor D = D

    Denn wir rechne ich die Hamming Distanz aus? Ich berechne A xor B und zähle die Anzahl der gesetzten Bits. Und die ist in unserem Fall immer X.

    Edit:
    Kleinere Korrektur des letzten Satzes.



  • template <size_t N>
    std::vector<std::bitset<N>> do_magic(size_t size, size_t dist)
    {
    	assert(N % 2 == 0);
    	assert((N - dist / 2) / (dist / 2) >= size - 1);
    	vector<bitset<N>> solution;
    	solution.push_back(bitset<N>());
    
    	for (int i = 1; i < size; ++i)
    	{
    		bitset<N> b;
    		for (int j = 0; j < dist / 2; ++j)
    		{
    			b.set(j);
    			b.set(i * dist / 2 + j);
    		}
    		solution.push_back(b);
    	}
    	return solution;
    }
    


  • Das zweite assert kann man natürlich vereinfachen zu assert(2*N >= size * dist);



  • Und das erste assert sollte dist % 2 == 0 heißen. Die asserts sind sowieso etwas zu restriktiv bzw. der Algorithmus findet nicht immer eine Lösung, falls eine existiert. Bei N = 3, dist = 2 und size = 4 findet er z.B. nicht die Lösung {000,110,101,011}. Vielleicht reicht dir aber schon der gezeigte Algorithmus, denn er gibt zumindest immer korrekte Lösungen für den Fall dist % 2 == 0 && 2*n >= dist * size aus.



  • Wau, sehr gut m.e. Ich verstehe noch nicht die for-Schleife aber das kommt gleich.

    Vielen Dank


Log in to reply