极客观点
项目管理
HarmonyOS
最近我反复接触到 LFSR 的概念，我觉得它很有趣，因为它与不同领域的联系，而且它本身也很吸引人。我花了一些努力才明白，最后的帮助是这个非常好的 页面，比（起初）神秘的 维基百科条目 要好得多。所以我想为一个像 LFSR 一样工作的程序编写一些小代码。更准确地说，它以某种方式展示了 LFSR 是如何工作的。这是经过更长时间的尝试（Python）后我能想到的最干净的东西：
def lfsr(seed, taps):
sr, xor = seed, 0
while 1:
for t in taps:
xor += int(sr[t-1])
if xor%2 == 0.0:
xor = 0
else:
xor = 1
print(xor)
sr, xor = str(xor) + sr[:-1], 0
print(sr)
if sr == seed:
break
lfsr('11001001', (8,7,6,1)) #example
我将 XOR 函数的输出命名为“xor”，不太正确。然而，这只是为了展示它如何遍历其可能的状态，事实上你注意到寄存器是由一个字符串表示的。没有太多的逻辑连贯性。
这可以很容易地变成一个你可以看几个小时的好玩具（至少我可以:-)
def lfsr(seed, taps):
import time
sr, xor = seed, 0
while 1:
for t in taps:
xor += int(sr[t-1])
if xor%2 == 0.0:
xor = 0
else:
xor = 1
print(xor)
print('')
time.sleep(0.75)
sr, xor = str(xor) + sr[:-1], 0
print(sr)
print('')
time.sleep(0.75)
然后我突然想到，这在编写软件中有什么用？我听说它可以生成随机数；是真的吗？如何？所以，如果有人可以：
- 解释如何在软件开发中使用这样的设备
- 想出一些代码来支持上面的观点，或者像我一样用任何语言展示不同的方法
此外，由于关于这块逻辑和数字电路的教学内容不多，如果这可以成为新手（像我一样）更好地理解这个 东西的 地方，或者更好地理解它是什么，那就太好了是什么以及它在编写软件时如何发挥作用。应该把它变成一个社区维基吗？
也就是说，如果有人想打高尔夫球……不客气。
原文由 MattiaG 发布，翻译遵循 CC BY-SA 4.0 许可协议
python
实际上，基于 LFSR 的算法非常普遍。 CRC实际上直接基于LFSR。当然，在计算机科学课上，人们在谈论输入值应该如何与累加值进行异或运算时会谈论多项式，而在电子工程中，我们会谈论抽头。它们是相同的，只是术语不同。
CRC32是一种很常见的。它用于检测以太网帧中的错误。这意味着当我发布这个答案时，我的 PC 使用基于 LFSR 的算法来生成 IP 数据包的哈希值，以便我的路由器可以验证它正在传输的内容是否未损坏。
Zip 和 Gzip 文件是另一个例子。两者都使用 CRC 进行错误检测。 Zip 使用 CRC32，Gzip 同时使用 CRC16 和 CRC32。
CRC 基本上是哈希函数。它足以让互联网正常工作。这意味着 LFSR 是相当不错的哈希函数。我不确定您是否知道这一点，但通常好的散列函数被认为是好的随机数生成器。但是 LFSR 的问题是选择正确的抽头（多项式）对于散列/随机数的质量非常重要。
您的代码通常是玩具代码，因为它对一串 1 和 0 进行操作。在现实世界中，LFSR 处理字节中的位。通过 LFSR 推送的每个字节都会更改寄存器的累加值。该值实际上是您通过寄存器推送的所有字节的校验和。将该值用作随机数的两种常见方法是使用计数器并通过寄存器推送数字序列，从而将线性序列 1,2,3,4 转换为一些散列序列，如 15306,22,5587， 994，或者将当前值反馈到寄存器中，以看似随机的顺序生成一个新数字。
应该注意的是，天真地使用位摆弄 LFSR 执行此操作非常慢，因为您必须一次处理位。所以人们想出了使用预先计算的表格来一次八位甚至一次 32 位的方法。这就是为什么您几乎看不到 LFSR 代码的原因。在大多数生产代码中，它伪装成其他东西。
但有时一个简单的有点麻烦的 LFSR 可以派上用场。我曾经为 PIC micro 编写了一个 Modbus 驱动程序，该协议使用 CRC16。预先计算的表格需要 256 字节的内存，而我的 CPU 只有 68 字节（ 我不是在开玩笑）。所以我不得不使用 LFSR。