代码之家 › 专栏 › 技术社区 › John

我将如何实现这个算法?

brute-force compression algorithm

9

John · 技术社区 · 17 年前

前一段时间,我试图对一个发送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位?

2 回复 | 直到 11 年前

1

13

Pesto 17 年前

你说的是一个 de Bruijn sequence . 如果你不在乎它是如何工作的,你只想要结果, here it is .

2

0

Chochos 17 年前

在我的脑海中,我假设在每个12位序列中翻转一位将处理另外13个组合,例如1111111111 01000000000010,然后111111111 011000000000100,等等。但是你仍然需要做很多排列,即使有一个位,我想你仍然需要做11111111101000000000100等,然后在一边翻转两个位,在另一边翻转一个位,等等。