Page 73 - 《软件学报》2025年第10期
P. 73
4470 软件学报 2025 年第 36 卷第 10 期
确的输入系数分布在 8 个不同的地址位, 因此每 8 个时钟周期可得到一组正确的操作数组. 第 2 种置换模式将
NTT 运算的输出顺序转化为初始顺序, 并在乘法累加运算开始之前完成数据重排, 如图 4(b) 所示, 初始顺序的前
8 个数据分布在 4 个 NTT 运算的数据结果中, 因此每 4 个时钟周期可得到一组正确的操作数组. 在向量 t 的运算
过程中, INTT(As 1 ) 运算的输出结果需要与向量 s 2 中的对应系数进行模加操作, 考虑到向量 t 中的多项式系数需
要以初始顺序参与下一步的 H (ρ ∥ t 1 ) 运算, 因此本文选择将 INTT 运算的输出顺序转化为初始顺序, 并将其定义
为第 3 种置换模式, 如图 4(c) 所示. 此外, 由于点乘运算 (cs 1 ,cs 2 ,ct 0 ) 的结果存在于 NTT 域内, 需要在参与下一步
运算之前需要将 NTT 运算的输出顺序转化为 INTT 的输入顺序, 此过程定义为第 4 种置换模式, 如图 4(d) 所示.
−q
−2q
−3q 26
+2q
+3q
w 46 +4q
+ +5q
23 LSB2 << 23 − MSB3 q 24
15 sum 23 LSB12 << 13 + 26 + 26 24 23 res
3 24
clk −
24
25 −2 +1 23 0 23 24 −1 25 −1
24
23
23
−2 +1 −2 −2 +1 −2 +1 2 −1 2 24 −1 2 +2 2
−4q −3q −2q −q q 2q 3q 4q
−33554431 −2516823 −16777215 −8388607 8388607 16777215 2516823 33554431
100 101 110 111 000 001 001 001
+5q +4q +3q +2q 0 −q −2q −3q
图 3 基于 Barrett 算法的改进型约减运算硬件设计 (包含修正逻辑)
x E0 x 60 x C0 x 40 x A0 x 20 x 80 x 00 x 07 x 06 x 05 x 04 x 03 x 02 x 01 x 00 x 04 x 00 x 80 x 00
x E1 x 61 x C1 x 41 x A1 x 21 x 81 x 01 x 87 x 86 x 85 x 84 x 83 x 82 x 81 x 80 x 84 x 80 x 81 x 01
x E2 x 62 x C2 x 42 x A2 x 22 x 82 x 02 x 27 x 26 x 25 x 24 x 23 x 22 x 21 x 20 x 06 x 02 x 82 x 02
x E3 x 63 x C3 x 43 x A3 x 23 x 83 x 03 Model a x A7 x A6 x A5 x A4 x A3 x A2 x A1 x A0 x 86 x 82 Model c x 83 x 03
x E4 x 64 x C4 x 44 x A4 x 24 x 84 x 04 x 47 x 46 x 45 x 44 x 43 x 42 x 41 x 40 x 05 x 01 x 84 x 04
x E5 x 65 x C5 x 45 x A5 x 25 x 85 x 05 x C7 x C6 x C5 x C4 x C3 x C2 x C1 x C0 x 85 x 81 x 85 x 05
x E6 x 66 x C6 x 46 x A6 x 26 x 86 x 06 x 67 x 66 x 65 x 64 x 63 x 62 x 61 x 60 x 07 x 03 x 86 x 06
x E7 x 67 x C7 x 47 x A7 x 27 x 87 x 07 x E7 x E6 x E5 x E4 x E3 x E2 x E1 x E0 x 87 x 83 x 87 x 07
cycle#8 cycle#7 cycle#6 cycle#5 cycle#4 cycle#3 cycle#2 cycle#1 cycle#16 cycle#15 cycle#14 cycle#13 cycle#12 cycle#11 cycle#10 cycle#9 cycle#2 cycle#1 cycle#4 cycle#3
x 06 x 04 x 02 x 00 x C0 x 80 x 40 x 00 x 06 x 04 x 02 x 00 x C0 x 40 x 80 x 00
x 07 x 05 x 03 x 01 x C1 x 81 x 41 x 01 x 07 x 05 x 03 x 01 x C1 x 41 x 81 x 01
x 46 x 44 x 42 x 40 x C2 x 82 x 42 x 02 x 46 x 44 x 42 x 40 x C2 x 42 x 82 x 02
Model b Model d
x 47 x 45 x 43 x 41 x C3 x 83 x 43 x 03 x 47 x 45 x 43 x 41 x C3 x 43 x 83 x 03
x 86 x 84 x 82 x 80 x C4 x 84 x 44 x 04 x 86 x 84 x 82 x 80 x C4 x 44 x 84 x 04
x 87 x 85 x 83 x 81 x C5 x 85 x 45 x 05 x 87 x 85 x 83 x 81 x C5 x 45 x 85 x 05
x C6 x C4 x C2 x C0 x C6 x 86 x 46 x 06 x C6 x C4 x C2 x C0 x C6 x 46 x 86 x 06
x C7 x C5 x C3 x C1 x C7 x 87 x 47 x 07 x C7 x C5 x C3 x C1 x C7 x 47 x 87 x 07
cycle#4 cycle#3 cycle#2 cycle#1 cycle#8 cycle#7 cycle#6 cycle#5 cycle#4 cycle#3 cycle#2 cycle#1 cycle#8 cycle#7 cycle#6 cycle#5
图 4 置换网络工作模式
由于第 1 种置换模式所需的延迟周期数最多, 因此以第 1 种情况为基础进行多功能置换网络的设计, 所需的
硬件资源可同时兼容其余 3 种情况. 根据上述分析, 本文的重排序网络主要由两组寄存器构成, 每组包含 8 个位宽
