CG-NTT 完美洗牌算法原理解析与正确性证明

1. 核心概念：什么是完美洗牌（Perfect Shuffle）？

在恒定几何 NTT（Constant Geometry NTT, CG-NTT）中，为了保持每一级（Stage）蝶形运算的读取跨度（Stride）永远固定为 $N/2$，必须在每级计算后对数据进行完美洗牌。

完美洗牌的直观理解就像洗扑克牌：将数组对半劈开，然后像拉链一样交叉咬合。

数学定义： 假设数组长度为 $N$（$N=2^n$），索引为 $i \in [0, N-1]$。洗牌后的新位置 $P(i)$ 为：

\[P(i) = \begin{cases} 2i, & 0 \le i < \frac{N}{2} \\ 2i - N + 1, & \frac{N}{2} \le i < N \end{cases}\]

• 前一半数据映射到偶数位：$0, 2, 4 \dots$
• 后一半数据映射到奇数位：$1, 3, 5 \dots$

---

2. 数学证明：为什么洗牌等价于标准 NTT？

证明的核心在于数据索引的二进制位移。

2.1 标准 DIF-NTT 的配对规律

在标准频率抽取（DIF）NTT 中，蝶形运算的跨度逐级减半。假设索引的二进制表示为 $b_{n-1}b_{n-2}\dots b_1b_0$：

• Stage 0（跨度 $N/2$）：配对数据的二进制最高位（MSB, $b_{n-1}$）不同。
• Stage 1（跨度 $N/4$）：配对数据的次高位（$b_{n-2}$）不同。
• Stage $k$：配对数据的第 $n-1-k$ 位不同。

2.2 完美洗牌的“二进制魔法”

根据 $P(i)$ 的公式，完美洗牌在二进制层面的本质是：对索引进行一次循环左移（Cyclic Left Shift）。

\[P(b_{n-1}b_{n-2}\dots b_1b_0) = b_{n-2}b_{n-3}\dots b_1b_0b_{n-1}\]

2.3 结论：两者的完美契合

在 CG-NTT 中，硬件永远只抓取当前 MSB 不同的数据（即固定跨度 $N/2$）：

1. Stage 0：读取 MSB ($b_{n-1}$) 不同的数据，计算后执行洗牌（二进制左移）。
2. Stage 1：上一轮的洗牌将原本的次高位 ($b_{n-2}$) 推到了现在的 MSB 位置。此时硬件依然抓取 MSB 不同的数据，实际上抓取的就是原始数据中 $b_{n-2}$ 不同的数据。这与标准 NTT 第 1 级的配对要求完全等价。
3. 以此类推：每一级的洗牌，都自动把下一级需要比较的“特征位”推送到最高位，供硬件使用固定跨度读取。

---

3. 实例推演 ($N=8$, 3位二进制)

以 $N=8$ 为例（索引 $000$ 到 $111$）：

• Stage 0：
  • 硬件按跨度 4 读取：配对 $(000, 100)$, $(001, 101)$ 等（MSB 不同）。
  • 计算后洗牌（循环左移）：如 001 (1) 左移变 010 (2)；100 (4) 左移变 001 (1)。
• Stage 1：
  • 硬件继续按跨度 4 读取当前物理位置 $0$ 和 $4$。
  • 位置 $0 (000)$ 是原始的 $000$。
  • 位置 $4 (100)$ 是原始的 $010$ (上一轮 010 左移变成了 100)。
  • 实际配对的是原始的 $(000, 010)$，相当于跨度 2。完美符合标准 NTT 的需求！

---

4. 软硬件协同：HPU 中的具体实现

在受限的硬件（如 HPU 的向量寄存器）中，无法通过一条指令完成全局的循环左移。全局完美洗牌被拆解为两个维度的协同：

1. 微观重排（指令级）： 使用 pshuf2 指令。它在寄存器内部将两个向量块的数据进行交叉编织（提取 $b_0$ 位特征），完成局部的交错。
2. 宏观重排（访存级）： 使用 sstore 指令和地址偏移逻辑（如 addr_out_x = dst + i*2）。它将局部洗牌后的数据块，精准投递到全局左移后应处的 SRAM 物理位置。

总结： pshuf2（局部交叉） + sstore（跨距写回地址） = 全局完美洗牌（二进制循环左移）。