说实话，第一次听到 LFSR 这三个字母的时候，我脑子里蹦出来的画面是：一堆二进制位在电路板上像贪吃蛇一样钻来钻去。别被这个听起来高深的名字吓跑，它其实是个特别“接地气”的东西。想象一下你有一排开关，每个开关只有开或关两种状态，每次操作都是把最右边的开关状态移走，同时根据某些特定位置的开关状态计算出一个新的值，塞到最左边。就这样一直循环，就会产生一串看似杂乱无章、但实际上完全由规则决定的 0 和 1。这就是线性反馈移位寄存器，英语全称 Linear Feedback Shift Register，缩写就是 LFSR。
你可能会问，这东西有什么用？它的用处大到让你惊讶。手机里的 Wi-Fi 信号、GPS 定位、蓝牙连接、甚至你玩的电子游戏里的随机事件，背后都有 LFSR 的影子。今天我就带你深入 Java 代码世界，把这个看似神秘的技术掰开揉碎讲清楚。我会从最基础的概念讲起，然后给你展示如何实现一个标准的 LFSR，接着演示怎么用它生成伪随机数，最后深入讲解它在 CRC 校验中的经典应用。别担心，代码部分我会写得非常详细，保证你能看懂每一个 bit 的移动过程。
LFSR 到底是什么？一段比特流的“记忆”
要理解 LFSR，我们得先回到数字逻辑的起点。一个 LFSR 本质上就是一个寄存器，里面存储着 N 个比特的状态。这个“寄存器”在 Java 里可以用一个整数（int）或者一个布尔数组来表示。关键在于它的“反馈”机制。
每次时钟脉冲到来时，寄存器里的所有比特都会向左或向右移动一位。通常我们选择向左移位，这样最左边的比特会移出寄存器，而最右边的空位需要填入一个新比特。这个新比特不是随便填的，它是通过一个称为“抽头”（taps）的逻辑函数计算出来的。具体来说，新比特等于当前寄存器状态中某些特定位进行异或（XOR）运算的结果。
让我用一个具体的例子来说明。假设我们有一个 4 位的 LFSR，当前的状态是 1011（二进制），抽头位置在第 4 位和第 1 位（从右往左数，最低位是第 1 位）。那么新的比特就是第 4 位（值为 1）和第 1 位（值为 1）进行 XOR 运算：1 XOR 1 = 0。移位后，新状态就变成了 0101。
这个过程听起来可能有点抽象，但只要你动手在纸上画几个状态转换，或者看我下面给的 Java 代码，一切都会清晰起来。LFSR 的神奇之处在于，对于一个 N 位寄存器，如果抽头选择得当，它在一个周期内可以遍历 2^N - 1 种不同的状态（全 0 状态是唯一的例外，一旦进入就会永远停留在 0）。这种长周期性、看似随机的特性，正是它被广泛应用的原因。
构建你的第一个 LFSR：从概念到 Java 代码
现在我们来动手写代码。我会创建一个基础的 LFSR 类，让你能够清晰地看到每一步的状态变化。这个实现会采用最直观的方式：用一个整数来存储寄存器状态，用位运算来实现移位和反馈。
import java.util.BitSet;
public class LFSR {
private int register; // 寄存器状态
private int length; // 寄存器位数
private int[] taps; // 抽头位置数组
private int initialState; // 初始状态
/**
* 构造函数：创建指定长度和抽头位置的 LFSR
* @param length 寄存器位数
* @param taps 抽头位置数组，元素为从 0 开始的位索引
* @param initialState 初始状态，如果为 0 则使用默认状态
*/
public LFSR(int length, int[] taps, int initialState) {
if (length <= 0) {
throw new IllegalArgumentException("寄存器长度必须大于 0");
}
if (initialState == 0) {
throw new IllegalArgumentException("初始状态不能为 0");
}
if (initialState >= (1 << length)) {
throw new IllegalArgumentException("初始状态超出寄存器长度范围");
}
this.length = length;
this.taps = taps;
this.initialState = initialState;
this.register = initialState;
}
/**
* 重置 LFSR 到初始状态
*/
public void reset() {
this.register = this.initialState;
}
/**
* 执行一次移位操作，返回移出的比特
* @return 移出的比特值（0 或 1）
*/
public int clock() {
// 计算反馈比特：对所有抽头位置进行 XOR 运算
int feedback = 0;
for (int tap : taps) {
if (tap < 0 || tap >= length) {
throw new IllegalArgumentException("抽头位置超出范围");
}
// 提取该位的值并参与 XOR
feedback ^= ((register >> tap) & 1);
}
// 保存移出的比特（最高位）
int outgoingBit = (register >> (length - 1)) & 1;
// 左移一位，低位补反馈比特
register = ((register << 1) | feedback) & ((1 << length) - 1);
return outgoingBit;
}
/**
* 获取当前寄存器状态
* @return 当前状态值
*/
public int getState() {
return register;
}
/**
* 获取寄存器状态的二进制字符串表示
* @return 二进制字符串
*/
public String getBinaryState() {
StringBuilder sb = new StringBuilder();
for (int i = length - 1; i >= 0; i--) {
sb.append((register >> i) & 1);
}
return sb.toString();
}
/**
* 生成指定长度的伪随机比特序列
* @param bitsLength 需要的比特数
* @return 比特数组
*/
public int[] generateBits(int bitsLength) {
int[] bits = new int[bitsLength];
for (int i = 0; i < bitsLength; i++) {
bits[i] = clock();
}
return bits;
}
/**
* 获取下一个状态的十进制值（用于测试序列）
* @return 下一个状态值
*/
public int nextState() {
clock();
return register;
}
// 主方法：演示 LFSR 的工作过程
public static void main(String[] args) {
// 创建一个 4 位 LFSR，抽头在第 3 位和第 0 位（对应多项式 x^4 + x + 1）
// 注意：Java 位运算从右向左，最低位是第 0 位
int[] taps = {3, 0};
LFSR lfsr = new LFSR(4, taps, 0b1011); // 初始状态 1011
System.out.println("=== 4位 LFSR 状态转换演示 ===");
System.out.println("初始状态: " + lfsr.getBinaryState() + " (十进制: " + lfsr.getState() + ")");
System.out.println("抽头位置: 第 3 位和第 0 位");
System.out.println();
// 显示前 15 个状态（4 位 LFSR 的最大周期是 2^4 - 1 = 15）
for (int i = 1; i <= 15; i++) {
int newState = lfsr.nextState();
System.out.println("状态 " + i + ": " + lfsr.getBinaryState() + " (十进制: " + newState + ")");
}
System.out.println("\n=== 生成 32 位伪随机数 ===");
lfsr.reset();
int[] randomBits = lfsr.generateBits(32);
// 将比特序列转换为整数
int randomInt = 0;
for (int bit : randomBits) {
randomInt = (randomInt << 1) | bit;
}
System.out.println("生成的比特序列:");
for (int i = 0; i < 32; i++) {
System.out.print(randomBits[i]);
if ((i + 1) % 8 == 0) {
System.out.print(" ");
}
}
System.out.println();
System.out.println("对应的十进制整数: " + randomInt);
System.out.println("对应的十六进制: 0x" + Integer.toHexString(randomInt));
}
}
这段代码看起来有点长，但别担心，我们一步步来拆解。首先，LFSR 类有三个核心字段：register 存储当前状态，length 是寄存器位数，taps 是抽头位置数组。在构造函数中，我们做了大量的输入验证，这是为了确保代码的健壮性。特别是，我们禁止初始状态为 0，因为全 0 状态会导致 LFSR 永远停留在 0，无法产生任何有用的序列。
clock() 方法是 LFSR 的核心。它首先计算反馈比特，通过遍历所有抽头位置，提取对应位的值并进行 XOR 运算。然后，它保存移出的最高位，将寄存器左移一位，并在最低位填入计算出的反馈比特。这里有一个巧妙的位运算技巧：((1 << length) - 1) 创建了一个掩码，确保移位后的状态不会超出寄存器长度。
generateBits() 方法展示了 LFSR 作为伪随机数生成器的基本用法。它简单地调用多次 clock() 方法，收集移出的比特。在主方法中，我们创建了一个 4 位 LFSR，抽头在第 3 位和第 0 位，这对应于生成多项式 x^4 + x + 1。这是一个经典的“最大周期”抽头组合，意味着 4 位 LFSR 可以遍历所有 15 种非零状态。
运行这段代码，你会看到输出显示状态从 1011 开始，经过 15 次移位后回到 1011，形成一个完整的循环。这验证了 LFSR 的理论特性：一个 N 位最大周期 LFSR 会产生 2^N - 1 个不同状态。
伪随机数生成：LFSR 的“ randomness”魔法
现在我们来深入探讨 LFSR 在伪随机数生成中的应用。很多人一听“伪随机”就觉得不靠谱，但事实上，LFSR 生成的序列在统计特性上表现得相当不错。当然，如果你需要加密级别的随机性，LFSR 单独使用是不够的，但它作为基础组件，在很多场景中都非常有用。
让我先解释一下为什么 LFSR 能产生“看似随机”的序列。关键在于它的长周期性和良好的统计特性。一个设计良好的 LFSR，其输出序列具有平坦的频谱，自相关函数接近理想值，而且 0 和 1 的分布大致均衡。这些特性使得 LFSR 生成的序列在通信、测试和模拟等领域非常有用。
但是，LFSR 也有它的局限性。首先，它是确定性的：给定相同的初始状态和抽头配置，它总是产生相同的序列。其次，线性反馈机制意味着序列在统计上并非完全随机，对于某些高级应用来说可能不够“随机”。此外，如果攻击者能够观察到足够长的输出序列，他们可能能够重建 LFSR 的内部状态（这涉及到 Berlekamp-Massey 算法，但这超出了我们今天讨论的范围）。
为了克服这些局限性，实际应用中常常会对 LFSR 的输出进行后处理。比如，我们可以使用 LFSR 生成比特序列，然后将它们组合成整数，或者使用 LFSR 作为更复杂随机数生成器的基础。
让我给你一个更实用的 Java 实现，专门用于生成伪随机数：
”`java import java.util.Random;
public class LFSRRandom {
private LFSR lfsr;
private int bitLength;
/**
* 构造函数：创建基于 LFSR 的伪随机数生成器
* @param bitLength 寄存器位数，建议至少 16 位以获得较好的随机性
* @param seed 种子值，必须非零
*/
public LFSRRandom(int bitLength, int seed) {
// 选择经典的抽头配置（针对不同长度有推荐的抽头）
int[] taps = getRecommendedTaps(bitLength);
this.lfsr = new LFSR(bitLength, taps, seed);
this.bitLength = bitLength;
}
/**
* 根据寄存器长度返回推荐的抽头配置
* 这些配置来自标准 LFSR 表，确保最大周期
*/
private int[] getRecommendedTaps(int length) {
// 这是常见的最大周期 LFSR 抽头配置
switch (length) {
case 4: return new int[]{3, 0};
case 5: return new int[]{2, 0};
case 6: return new int[]{5, 0};
case 7: return new int[]{6, 0};
case 8: return new int[]{6, 5, 2, 0};
case 9: return new int[]{5, 2, 0};
case 10: return new int[]{7, 6, 1, 0};
case 11: return new int[]{9, 2, 0};
case 12: return new int[]{6, 5, 1, 0};
case 13: return new int[]{7, 3, 0};
case 14: return new int[]{9, 6, 0};
case 15: return new int[]{14, 13, 1, 0};
case 16: return new int[]{15, 14, 1, 0}; // 经典配置
case 24: return new int[]{23, 22, 17, 0};
case 32: return new int[]{32, 22, 2, 1}; // CRC-32 常用
default:
// 对于其他长度，返回一个通用的配置
// 实际应用中应该查阅 LFSR 表
return new int[]{length - 1, length - 2};
}
}
/**
* 生成一个 0 到 1 之间的双精度浮点数
* @return 伪随机 double 值
*/
public double nextDouble() {
// 生成 31 个随机比特（避免符号位）
int randomBits = 0;
for (int i = 0; i < 31; i++) {
randomBits = (randomBits << 1) | lfsr.clock();
}
// 映射到 0-1 范围
return (double) randomBits / (1 << 31);
}
/**
* 生成一个指定范围内的整数
* @param bound 范围上界（不包括）
* @return 伪随机整数
*/
public int nextInt(int bound) {
if (bound <= 0) {
throw new IllegalArgumentException("范围必须大于 0");
}
int randomBits = 0;
// 计算需要的比特数
int bitsNeeded = Integer.numberOfLeadingZeros(bound - 1);
for (int i = 0; i < bitsNeeded; i++) {
randomBits = (randomBits << 1) | lfsr.clock();
}
// 避免偏差：拒绝采样
int threshold = (1 << bitsNeeded) - (1 << bitsNeeded) % bound;
while (randomBits >= threshold) {
randomBits = 0;
for (int i = 0; i < bitsNeeded; i++) {
randomBits = (randomBits << 1) | lfsr.clock();
}
}
return randomBits % bound;
}
/**
* 生成指定长度的二进制字符串
* @param length 二进制字符串长度
* @return 二进制字符串
*/
public String nextBinaryString(int length) {
StringBuilder sb = new StringBuilder(length);
for (int i = 0; i < length; i++) {
sb.append(lfsr.clock());
}
return sb.toString();
}
/**
* 重置生成器到初始状态
*/
public void reset() {
lfsr.reset();
}
// 演示程序
public static void main(String[] args) {
// 创建 16 位 LFSR 随机数生成器
LFSRRandom random = new LFSRRandom(16, 0x1234);
System.out.println("=== LFSR 伪随机数生成演示 ===");
System.out.println("使用 16 位 LFSR，种子: 0x1234");
System.out.println();
// 生成 10 个随机整数
System.out.println("前 10 个随机整数:");
for (int i = 0; i < 10; i++) {
int num = random.nextInt(1000);
System.out.print(num + " ");
}
System.out.println();
// 生成一些随机 double 值
System.out.println("\n前 5 个随机 double:");
for (int