¿Cómo haría para implementar este algoritmo?

Question

Hace un tiempo, estaba tratando de aplicar fuerza bruta a un control remoto que enviaba una 'clave' binaria de 12 bits.

El dispositivo que hice funcionó, pero era muy lento ya que intentaba cada combinación a unos 50 bits por segundo (4096 códigos = 49152 bits = ~ 16 minutos)

Abrí el receptor y descubrí que estaba usando un registro de desplazamiento para verificar los códigos y no se requirió demora entre intentos. Esto significaba que el receptor simplemente estaba mirando los últimos 12 bits que se recibirían para ver si coincidían con la clave.

Esto significaba que si la transmisión 111111111111000000000000 se enviaba, había probado efectivamente todos estos códigos.

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

En este caso, he usado 24 bits para probar 13 combinaciones de 12 bits (> 90% de compresión).

¿Alguien sabe de un algoritmo que podría reducir mis 49152 bits enviados al aprovechar esto?

Answer 1

De lo que estás hablando es de una de Bruijn secuencia . Si no te importa cómo funciona, solo quieres el resultado, aquí está .

Answer 2

Supongo que voltear un bit en cada secuencia de 12 bits se encargaría de otras 13 combinaciones, por ejemplo 111111111101000000000010, luego 111111111011000000000100, etc. Pero aún tiene que hacer muchas permutaciones, incluso con un bit Creo que todavía tienes que hacer 111111111101000000000100 etc. Luego voltea dos bits de un lado y 1 del otro, etc.