Comment pourrais-je procéder pour implémenter cet algorithme?
-
20-08-2019 - |
Question
Il y a quelque temps, j'essayais de forcer brutalement une télécommande qui envoyait une "clé" binaire de 12 bits.
Le périphérique que j'ai fabriqué a fonctionné, mais a été très lent car il essayait chaque combinaison à environ 50 bits par seconde (4096 codes = 49152 bits = ~ 16 minutes)
J'ai ouvert le récepteur et j'ai constaté qu'il utilisait un registre à décalage pour vérifier les codes et qu'aucun délai n'était requis entre les tentatives. Cela signifiait que le destinataire regardait simplement les 12 derniers bits à recevoir pour voir s'ils correspondaient à la clé.
Cela signifie que si le flux 111111111111000000000000
a été envoyé, il a effectivement essayé tous ces codes.
111111111111 111111111110 111111111100 111111111000
111111110000 111111100000 111111000000 111110000000
111100000000 111000000000 110000000000 100000000000
000000000000
Dans ce cas, j'ai utilisé 24 bits pour essayer 13 combinaisons de 12 bits (> 90% de compression).
Est-ce que quelqu'un connaît un algorithme qui pourrait réduire mes 49152 bits envoyés en tirant parti de cela?
La solution
Ce dont vous parlez est une séquence de Bruijn . Si vous ne vous souciez pas de la façon dont cela fonctionne, vous voulez simplement obtenir le résultat, c'est ici .
Autres conseils
De mémoire, je suppose que retourner un bit dans chaque séquence de 12 bits permettrait de prendre en charge 13 combinaisons supplémentaires, par exemple 111111111101000000000010, puis 11111111111111000000000100100, etc. Cependant, vous devez encore faire beaucoup de permutations, même avec un bit, je pense que vous devez encore faire 111111111101000000000100 etc. puis retournez deux bits d'un côté et un de l'autre, etc.