Как бы я приступил к реализации этого алгоритма?

Question

Некоторое время назад я пытался принудительно использовать пульт дистанционного управления, который отправил 12-битный двоичный "ключ".

Созданное мной устройство работало, но было очень медленным, поскольку оно пробовало каждую комбинацию со скоростью около 50 бит в секунду (4096 кодов = 49152 бита = ~ 16 минут).

Я открыл приемник и обнаружил, что он использует сдвиговый регистр для проверки кодов, и никакой задержки между попытками не требуется.Это означало, что получатель просто просматривал последние 12 битов, которые должны были быть получены, чтобы увидеть, совпадают ли они с ключом.

Это означало , что если поток 111111111111000000000000 был отправлен через, он эффективно опробовал все эти коды.

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

В этом случае я использовал 24 бита, чтобы попробовать 13 12-битных комбинаций (сжатие> 90%).

Кто-нибудь знает об алгоритме, который мог бы уменьшить отправленные мной 49152 бита, воспользовавшись этим?

Answer 1

То, о чем вы говорите, - это последовательность де Брейна.Если вас не волнует, как это работает, вам просто нужен результат, вот оно.

Answer 2

Навскидку, я полагаю, что переключение одного бита в каждой 12-битной последовательности привело бы к появлению еще 13 комбинаций, например 111111111101000000000010, затем 111111111011000000000100 и т.д.Но вам все равно придется сделать много перестановок, даже с одним битом, я думаю, вам все равно придется сделать 111111111101000000000100 и т.д.Затем переверните два бита с одной стороны и 1 с другой и т.д.