高速可扩展的Montgomery乘法器设计方案
本文提出一种高速可扩展的Montgomery乘法器设计方案,该方案是在Tenca提出的Booth-8Montgomery模乘法器的基础上,采用Booth-64编码进行改进,使速度平均提高了48%。同时对数据通路进行了优化,使得流水线数据通路的平均延迟大大降低。
本文引用地址://m.amcfsurvey.com/article/187254.htm![](http://m.amcfsurvey.com/editerupload/fetch/20131113/187254_1_1.jpg)
其中,k表示基,X为模乘运算的乘数,Y是被乘数,M是模数。其中,操作数长度为N,部分积用为S表示,Y、M和S分成NW个BPW bit的字进行运算,xj表示X的第j bit,Sk(i)表示第i个字的第k位,Ca、Cb表示进位,qyj、qMj分别是在计算部分积过程中Y和M的系数。
核心数据路径采用流水线组织结构,每一级之间用寄存器隔开。每个MMcell单元完成一轮外循环,每个时钟输入Y、M、SS、SC的一个字参与运算,并把Y、M和计算出来的SS、SC传递该下一级。为了能使数据路径可伸缩,加入了两个FIFO分别用来存储SS和SC。如图1所示,NS是流水线级数,由面积和时间需求来决定。
![](http://m.amcfsurvey.com/editerupload/fetch/20131113/187254_1_2.jpg)
2 基为64的高速Montgomery乘法器设计
Tenca提出的模乘器设计中Booth编码采用的基为8,并且能够支持操作数长度可变的模乘运算,对操作数按字进行运算,缩短了关键路径的延迟,并且使用CSA(Carry Save Adder)提高了整体的系统性能。
通过分析,采用基为8的Booth编码可以将部分积数量减少为原来的1/3,而采用基为64的Booth编码则可以将部分积数量减少为原来的1/6。据此本文对Tenca提出的设计方案进行改进,因此提出基为64的高速Montgomery乘法器。
对于基为64的设计,乘数X每次扫描6 bit,经Booth编码后得到7 bit的输入数据,同时Y和M每次输入一个字。乘数X的Booth编码为:
![](http://m.amcfsurvey.com/editerupload/fetch/20131113/187254_1_3.jpg)
![](http://m.amcfsurvey.com/editerupload/fetch/20131113/187254_1_4.jpg)
![](http://m.amcfsurvey.com/editerupload/fetch/20131113/187254_1_5.jpg)
评论