伽罗瓦域GF(2^128)乘法器设计.doc

摘要 本文是在理解伽罗瓦域乘法器工作原理的基础上，设计一个伽罗瓦域乘法器，并通过verilog硬件描述语言，用Modelsim，Synplify软件对其进行仿真，综合。 关键词：伽罗瓦域 乘法器Verilog 仿真 综合Abstract This article is in understanding the working principle of Galois field multiplier based on the design of a Galois field multiplier, and through the verilog hardware descriptionlanguage, with Modelsim, Synplify software from simulation, synthesis.Key words: Galois Field Multiplier Simulation synthesis目录摘要. 1Abstract. 2正文. 4一、课题及设计要求. 4a）课题内容. 4b）设计要求. 4二、伽罗瓦域背景介绍. 4a）域和伽罗瓦域. 4b）伽罗瓦域两种操作加法与乘法. 4三、算法描述. 4四、设计过程. 6a）过程描述. 6b）程序流程图. 7五、verilog源代码. 8a）主程序. 8b）测试程序. 11六、modelsim仿真结果. 12a）仿真后主要信号、变量的波形. 12b）mul_128模块的输入信号和输出信号. 13c）dina和dinb输入和dout输出. 13d）验证参数. 13七、综合. 15八、现有伽罗瓦域乘法器实现方法优劣比较. 15九、总结. 15a）体会心得. 15b）建议. 16致谢. 17参考文献. 18 正文一、课题及设计要求a) 课题内容伽罗瓦域GF(2128)乘法器是Ghash算法(一种用于加解密系统散列算法)的核心部件，其速度与硬件开销决定着整个Ghash模块的整体性能。本题目的最终目的是：完成伽罗瓦域GF(2128)乘法器的设计。b) 设计要求1） 用verilog语言进行编程，语法要符合可综合设计的要求；2） 用modelsim完成系统功能仿真；3） 用synplify 或ISE进行综合；4） 完成设计报告。（设计报告中要对现有的几种伽罗瓦域GF(2128)乘法器实现方法进行比较，分析优劣）二、伽罗瓦域背景介绍a) 域和伽罗瓦域F是至少含有两个元素的集合，对F定义了两种运算“+”和“*”，并且满足以下三条件的代数系统称为域。F的元素关于运算“+”构成阿贝尔群，设其单位元为0。 F-0关于运算“*”构成阿贝尔群。对于a，b，cF，分配律成立。即：(a+b) c=a*c+b*c，c*(a+b)=c*a+c*b。若域F的元素有限个，则称之为有限域或伽罗瓦(Galoi)域.b) 伽罗瓦域两种操作加法与乘法这两种操作都是针对二元的操作。GF（2）是最小的有限域，它只含有两个域元素0和1。加法和乘法都进行模2操作，因此加法等效与逻辑异或，而乘法等效于逻辑与。有限域可以用非可约多项式 来定义，令 GF（2m）是 的根，即 。则称 为多项式基或标准基，GF（2m）中的每个元素都可以根据多项式基来表示。比如，对于 ,，可以表示为 ，其中 即为基下的坐标。假设 ， ，则 。三、算法描述Arash Reyhani-Masoleh等人1提出了一种新的算法，具体为多项式基乘法公式，该公式可以有效减少实现乘法所需的门数，提高乘法器的速度，因此我们选择该算法作为比特并行乘法器的算法。对于有限域GF（2m）乘法C=AB，Arash Reyhani-Masoleh等人证明，乘积C的坐标可以通过一个带矩阵Q的方程计算出来。该方程为： ，其中 是 的根， ，而T表示矩阵的转置。矩阵Q的准确定义与证明可以在1中找到，矩阵Q仅取决非可约多项式 。Ghash的多项式 。下面我们直接给出GF（2128）中的矩阵Q。 对于域GF（2m）,矩阵L如下： （1）对于域GF（2m）,矩阵U如下： （2）由（1）（2）可知，在已知输入A的情况下，可以很容易地得到矩阵L，U，因此，根据 ，我们即可算出有限域乘法的乘积。使用上述公式实现多项式基乘法，并令 ， ，则 ，其实现结构图（1）如示：图1 有限域乘法器结构图BTX:Binary Tree of XORs IB:Interconnection Bus结构图分为两部分：IP-network和Q-network。IP-network一共由m个模块组成，分别表示为 ，主要作用是根据 ， ，求出向量 , 。对于 ，模块 包括两个内部运算单元，即 和 。最后一个模块 只包含一个运算单元，即 。如图1所示， , 是Q-network的输入， 是输出。Q-network包括m个BTX。BTXi 中XOR门的个数等于矩阵Q中第i列中1的个数。我们知道，连接总线（IB）的条数是固定，且其值为m-1。在图1中，一共由3条总线，A，B和IB，线的总数为：3m-1。四、设计过程a) 过程描述伽罗瓦域乘法器的核心是这个公式： 所以，我们要做的工作就是如何实现一步一步地按照这个公式把输入的两个128位并行数据计算得出结果。根据背景介绍里面的算法描述，我们知道，Q矩阵是只与GF(2m)中的m有关，而本文的m是固定的，为128，所以，Q矩阵的所有值都是固定了的。那么，我们可以在初始化语句里面就把Q矩阵计算出来。另外，考虑到计算的时候用的是Q矩阵的转置，那么，在初始化程序断里面就可以把Qt也一并求出来。还是根据算法描述可以知道，L矩阵和U矩阵是只与输入的dina有关，那么，我们可以设置一个always语句，检测dina的输入，任何时候只要dina有输入，那么程序就立即计算出对应的L矩阵和U矩阵。当然，还需要编写一段复位语句，使程序的所有变量、参数等等复位。另外，由于仿真一般最开始都是先复位，也相当于初始化，那么，可以把计算Q和Qt两个矩阵的代码放到复位语句块里面。考虑到为了降低芯片的计算量，我们可以是在每个时钟周期的上升沿检测复位信号rst和使能信号en，当复位信号rst为低电平的时候，进行复位操作，如果不是低电平，再检测使能信号en，如果en为高电平（表明允许计算）才继续下一步。这时可以设置一个标志位flag，以检测本次的输入与上次的输入是否一样（假设相等的时候flag=0），如果flag=0，表明上次输入的dina和dinb与本次的相等，那么，也不继续进行下面的运算；只有当flag=1时，才进行伽罗瓦域乘法。根据 ，我们应该先计算Qt与U的乘积QtU，然后计算QtU和L的和LQtU，最后计算LQtU和dinb的乘积，即为dina和dinb的伽罗瓦域乘积。同时，考虑到verilog不支持类似于C语言的二维数组这种数据类型，只能使用存储器类型，即，不能对存储器的每一个字节单独操作，那么，必须使用一些中间变量来获取存储器的值，计算出结果之后再写回到存储器，这部分会占程序的大部分，而且很容易出错。由以上分析可知，只有在每个时钟周期的上升沿时候，检测到(rst=0)&(en=1)&(flag=1)的时候，才计算dina和dinb的伽罗瓦域乘积。计算出dout之后，置ready_o为高电平，表明dout线上的信号为有效值。最后，由于这仿真的波形比较复杂，手工设置输入信号太麻烦，也达不到要求，所以，我们需要编写一段testbench文件来测试主程序。Testbench文件应该达到以下要求：1， 标准的时钟方波信号，可以通过always #50 clk=clk； 实现；2，复位操作可以使在initial里面加入以下语句：rst=1；#20 rst=0；#60 rst=1；3，使能位置高电平，通过#60 en=1； 实现； 4，dina和dinb的输入。 b) 程序流程图 五、Verilog源代码a) 主程序 module mul_128(clk, /时钟信号，方波 rst, /复位信号，低电平有效 en, /使能信号，高电平有效 dina, /a输入口 dinb, /b输入 dout, /输出端口 ready_o); /输出有效端，高电平有效 input clk,rst,en; /输入信号input 127:0 dina,dinb;output ready_o; /输出信号output 127:0 dout; reg 127:0 dout; reg 127:0 dina_old,dinb_old; /保存上一次输入的a和b的值，防止重复计算reg ready_o;reg 127:0 L127:0,QtU127:0,LQtU127:0; /伽罗瓦域乘法器实现过程中的中间变量reg 127:0 U126:0,Q126:0;reg 126:0 Qt127:0;reg 127:0 temp,temp1,temp2;reg 126:0 temp4; integer i,j,k; /循环变量integer flag; /标志位，表示本次输入的a和b与上次的相同 always(dina) /a端一旦有输入，就立即计算出a对应的L矩阵beginL127127:0=dina127:0;for(i=0;i127;i=i+1)L126-i127:0=L127-i127:01;for(j=1;j1;end always(posedge clk) /每个时钟上升沿检测a和b输入端beginif(rst) /在程序最开始，是复位信号有效，进行一定初始化beginfor(i=0;i127;i=i+1)beginQti126:0=0;QtUi127:0=0;LQtUi127:0=0;endQtU127127:0=0;LQtU127127:0=0；dout127:0=0;temp127:0=0;temp1127:0=0;temp2127:0=0；temp4126:0=0;ready_o=0; Q0127:0=128he1000000000000000000000000000000;/计算Q矩阵所有值for(i=1;i1;Q121127:0=128he1000000000000000000000000000070;Q122127:0=Q121127:01;Q123127:0=Q122127:01;Q124127:0=Q123127:01;Q125127:0=Q124127:01;Q126127:0=128he6080000000000000000000000000003; for(i=0;i128;i=i+1) /计算Q矩阵的转置beginfor(j=0;j127;j=j+1)begintemp127:0=Qj127:0;temp4126-j=temp127-i;if(j=126)Qti126:0=temp4126:0;endendendelse if(en) /使能信号高电平有效beginflag=0; /使标志位置0，如果此次输入与上次不一致，则flag=1if(dina!=dina_old)|(dinb!=dinb_old) flag=1;if(flag=1) /此次输入的a和b的值与上次不同begintemp127:0=0; /一些初始化语句temp1127:0=0；temp2127:0=0;temp4126:0=0;for(i=0;i128;i=i+1) /计算Q的转置Qt矩阵与U矩阵的乘积QtUbegintemp4126:0=Qti126:0;for(j=0;j128;j=j+1)beginfor(k=0;k127;k=k+1)begintemp127:0=Uk127:0;temp1127-j=temp1127-j(temp4126-k&temp127-j);end;if (j=127) QtUi127:0=temp1127:0;endendtemp127:0=0; /一些初始化语句temp1127:0=0;temp2127:0=0;temp4126:0=0;for(i=0;i128;i=i+1) /计算QtU与L的和LQtUbegintemp127:0=Li127:0;temp1127:0=QtUi127:0;for(j=0;j128;j=j+1)begintemp2j=tempjtemp1j;if(j=127)LQtUi127:0=temp2127:0;endendtemp127:0=0; /一些初始化语句temp1127:0=0;temp2127:0=0;temp4126:0=0;temp127:0=dinb127:0;for(i=0;i128;i=i+1) /计算LQtU与dinb的乘积，即为a和b的乘积doutbegintemp1127:0=LQtUi127:0;for(j=0;j128;j=j+1)temp2127-i=temp2127-i(temp1127-j&temp127-j);enddout127:0=temp2127:0;dina_old127:0=dina127:0; /dina_old获取本次输入的a的值dinb_old127:0=dinb127:0; /dinb_old获取本次输入的b的值ready_o=1; /计算出结果后，把dout送到线上，并用ready_o高电平表示数据有效endendend endmodule b) 测试程序 module test_mul_128();reg clk,rst,en; /时钟信号、复位信号、使能信号reg 127:0 dina,dinb; /两个128位的并行输入端wire 127:0 dout; /128位并行输出端wire ready_o; /输出有效端mul_128 mul(.clk(clk),.rst(rst),.en(en),.dina(dina),.dinb(dinb),.dout(dout),.ready_o(ready_o); /调用mul_128模块 initial /初始化语句块beginclk=0; /时钟初始化为低电平en=0; /使能信号端初始化为低电平rst=1; /复位信号端初始化为高电平#20 rst=0; /20ns后，复位信号置高电平#60 rst=1; en=1; /60ns后，复位信号置低电平，使能信号置高电平#100 dina=128b0; /100ns后，a口输入0dinb=128b0; /b口输入0#200 dina=128h42831ec2217774244b7221b784d0d49c; /200ns后，a口输入第二个数据dinb=128hb83b533708bf535d0aa6e52980d53b78; /b口输入第二个数据#200 dina=128h90000000000000000000000000000012; /200ns后，a口输入第三个数据dinb=128h00000000000000000000000000000002; / b口输入第三个数据#400 $stop; /400ns后，停止仿真end always #50 clk=clk; /每隔50ns，时钟信号翻转一次，形成周期性方波 endmodule 六、modelsim仿真结果a) 仿真后主要信号、变量的波形 b) mul_128模块的输入信号和输出信号由图可以看出，最开始的时候rst置低电平进行复位操作，然后为高电平，同时使能信号en也变高，表示现在可以接受输入了。dina和dinb最开始输入全是0，dout大概延迟一个时钟周期之后输出，同时ready_o信号变为高电平，表明dout线上的数据时dina和dinb的伽罗瓦域乘积。 c) dina和dinb输入dina=128h42831ec2217774244b7221b784d0d49c;dinb=128hb83b533708bf535d0aa6e52980d53b78;输出dout：dout = 128h9e2213794cbee38902b8e6ae8cd41a9f。得到的值与理论计算值相等，表明程序应该是正确的。（理论计算值是使用matlab编写的一段GF(2128)域内的乘法运算，由于matlab自带维度低的伽罗瓦域乘法、并且矩阵运算及其方便，所以编写m=128的有限域乘法的算法比较容易） 输入为： dina=128h90000000000000000000000000000012;dinb=128h000000000000000000000000000000002;输出： dout = 128h200000000000000000000000000000a3。依然是与理论计算值相等。 d) 验证参数为检验结果的正确性，取一些中间参数的值进行验证1） Q126:0127:0的值 Q值与理论值相等2） Q的转置Qt127:0126:0的值 Qt值与理论值相等3） dina_old, dinb_old信号的波形图有图可以看出每次计算出dout的值之后，dina_old和dinb_old都成功地立即获得了当前的dina和dinb，为了与下次输入的dina和dinb相比较，当二者相等的时候程序不进行计算，只是保持原来的输出。 4） 说明其他的一些中间变量，比如 L、 U、 temp等等，由于光看波形不好验证是否正确，所以我没有把这些信号的波形拿来验证，只取了一些简单的来验证。当然，最主要的是输出dout正确，那中间的过程不出意外应该是没有问题的，所以也就不必去一一验证了。七、综合没有得出综合结果。八、现有伽罗瓦域乘法器实现方法优劣比较GF(2m)域乘法运算实现有多种分类方法，按照参加运算的域元素的表示方式来看，由于有限域每个元素由肌位矢量表示，常用的基有三种：标准基、正规基和对偶基，因此有基于标准基，正规基和对偶基三类乘法器。按照结构来分，又可分为基于比特的全串行结构、全并行结构以及串并结合的混合结构。这两种分类方法结合起来就产生了各种不同的乘法器。另外，近些年又出现了各种新的乘法实现结构，如采用脉动阵列实现乘法运算，具有规则性、高速等特点，又有避免脉动阵列缺点的半脉动阵列乘法嚣。目前大多