# Falcon FFT Coefficient 規律
[falcon fft/ifft coef](https://github.com/vic9112/PQC_Falcon/blob/63baa7bcaf1f84539ea66e38408ccfc1ddee5a9c/reference/falcon_py/fft_constants.py)

以下為 Falcon FFT 在不同階段所需係數的讀取順序與存入 RAM 規律：

1. 讀取 `phi4` 根（`phi4_roots`）：
- 只取偶數位置的係數（第 0）：
- 取出 `j`，共 1 個
- 這 1 個係數給 **Stage 1** 使用（第一個 BPE的第一個Stage只需要 1 個）

2. 讀取 `phi8` 根：
- 取偶數位置（0, 2）：共 2 個
- 作為 **Stage 2** 的係數（共 2 個係數供第一個 BPE的Stage 2使用）

3. 讀取 `phi16` 根：
- 取偶數位置，共 4 個
- 作為 **Stage 3** 的係數(BPE 2 )

4. 讀取 `phi32` 根：
- 取偶數位置，共 8 個
- 作為 **Stage 4** 的係數 (BPE 2)

5. 讀取 `phi64` 和 `phi128` 根：
- 分別取偶數位置，共 16 + 32 = 48 個
- 作為 **Stage 5** 與 **Stage 6** 的係數(BPE 3)

6. 讀取 `phi256` 和 `phi512` 根：
- 分別取偶數位置，共 64 + 128 = 192 個
- 作為 **Stage 7** 與 **Stage 8** 的係數(BPE 4)

7. 最後讀取 `phi1024` 根：
- 取偶數位置，共 256 個
- 作為 **Stage 9** 的係數(BPE 5)

> **備註**：不需 bit-reverse，只需按順序存入與讀取。

- 當第一次啟動 BPE₃ 時，給 Stage 3 的第一個係數，以及 Stage 4 的前兩個係數。
- 第二次啟動 BPE₃ 時，給 Stage 3 的第二個係數，以及 Stage 4 的第三和第四個係數。

前三個 BPE 均依此順序：**先**給 Stage s 的一個係數，**再**給 Stage (s+1) 的兩個係數。

-------

**iFFT** 方面：

- iFFT 他採用 DIF 方法實作，但推測：
- **配對階段與 FFT 相同**，僅須對所有 twiddle factor 取共軛後使用。

-------