Come potrei implementare questo algoritmo?
-
20-08-2019 - |
Domanda
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?
Soluzione
Di cosa stai parlando è una della sequenza di Bruijn . Se non ti interessa come funziona, vuoi solo il risultato, eccolo .
Altri suggerimenti
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.