Come potrei implementare questo algoritmo?

Question

Qualche tempo fa stavo cercando di rinforzare un telecomando che inviava una 'chiave' binaria a 12 bit.

Il dispositivo che ho realizzato ha funzionato, ma è stato molto lento poiché stava provando ogni combinazione a circa 50 bit al secondo (4096 codici = 49152 bit = ~ 16 minuti)

Ho aperto il ricevitore e ho scoperto che stava usando un registro a scorrimento per controllare i codici e non era richiesto alcun ritardo tra i tentativi. Ciò significava che il ricevitore stava semplicemente guardando gli ultimi 12 bit da ricevere per vedere se corrispondevano alla chiave.

Ciò significa che se lo stream 111111111111000000000000 era stato inviato, aveva effettivamente provato tutti questi codici.

111111111111    111111111110    111111111100    111111111000
111111110000    111111100000    111111000000    111110000000
111100000000    111000000000    110000000000    100000000000
000000000000

In questo caso, ho usato 24 bit per provare 13 combinazioni a 12 bit (> compressione al 90%).

Qualcuno conosce un algoritmo che potrebbe ridurre i miei 49152 bit inviati sfruttando questo?

Answer 1

Di cosa stai parlando è una della sequenza di Bruijn . Se non ti interessa come funziona, vuoi solo il risultato, eccolo .

Answer 2

Suppongo che capovolgere un bit in ogni sequenza di 12 bit si occupi di altre 13 combinazioni, ad esempio 111111111101000000000010, quindi 11111111101100000000000000, ecc. Ma devi ancora fare molte permutazioni, anche con un po 'penso che devi ancora fare 111111111101000000000100 ecc. Quindi gira due bit da una parte e 1 dall'altra, ecc.