Comment pourrais-je procéder pour implémenter cet algorithme?

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?

Answer 1

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 .

Answer 2

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.