基于二次Booth编码的大数乘法器

摘要

基于二次Booth编码的大数乘法器，属于公开密钥密码体制算法的集成电路设计技术领域，其特征在于利用线性变换式B＝8a+b对部分积产生的Booth 64算法结果进行二次编码，基于二次Booth 64编码的乘法器分为3级流水线结构。第1级结构由一个超前进位加法器预计算3倍的被乘数。在预计算的同时，分别对权为8¹的a_j和权为8⁰的b_j进行二次Booth编码；第2级结构由两个相同部分积选择和压缩阵列，分别进a_j和b_j的的部分积化简。第3级结构将第二级得到的部分积通过加法器进行相加。本发明提高了乘法运算的速度，可用于高性能的RSA、ECC芯片的实现，适用于服务器上大型PKI系统的应用。

主权项

1.基于二次Booth编码的大数乘法器，其特征在于，由第一级流水线、第二级流水线以及第三级流水线组成，其中，第一级流水线包括：加法预计算器、权为81的aj编码器、以及权为80的bj编码器，其中，加法预计算器，输入信号为被乘数X[n-1:0]，以及把被乘数X左移后生成的2X，该加法预计算器的输出信号为3X，权为81的aj编码器，输入信号为乘数Y[n-1:0]，进行以下操作得到输出信号sel_a：设定一个二次Booth64编码表，是一个所述二次Booth64编码结果Bj与其所对应的信号a，以及信号b的映射表，j＝1，2，3，...7，8，...，32，按下式计算二次Booth64编码结果Bj：Bj＝-32Y6r+5+16Y6r+4+8Y6r+3+4Y6r+2+2Y6r+1+Y6r+Y6r-1其中，r＝0，1，2，...，n/6；查所述二次Booth64编码表得到与所述编码结果Bj对应的位宽为5位的输出信号sel_a，输出信号sel_a中有且只有一个比特为高电平，其余比特为低电平，该高电平比特信号用sel_a[i]表示，所述i为a的二次Booth64编码结果，表示第i项，权为80的bj编码器，输入信号为乘数Y[n-1:0]，利用所述二次Booth64编码表，由所述信号Bj得到对应的位宽为5位的输出信号sel_b，该信号sel_b中有且只有一个比特为高电平，其它比特为低电平，该高电平比特信号用sel_b[j]表示，所述j为b的二次Booth编码结果，表示第j项，第二级流水线包括：第1部分积选择多路选择器，第1部分积阵列n/6:2缩减器，第2部分积选择多路选择器，以及第2部分积阵列n/6:2缩减器，其中，第1部分积选择多路选择器，输入信号是被乘数X、所述第一级流水线产生的部分积3X以及所述控制用的信号sel_a；当所述sel_a[i]为高电平时，选择所述被乘数的i倍输出，第2部分积选择多路选择器，输入信号是被乘数X、所述第一级流水线产生的部分积3X以及所述控制用的信号sel_b；当所述sel_b[j]为高电平时，选择所述被乘数的j倍输出，第1部分积阵列的压缩采用Wallace树结构，部分积阵列采用4-2计数器和免进位加法器进行部分积的化简，直至得到两个部分积carry_a、sum_a输出，第2部分积阵列的压缩采用Wallace树结构，部分积阵列采用4-2计数器和免进位加法器进行部分积的化简，直至得到两个部分积carry_b、sum_b输出，第三级流水线，是一个部分积阵列4:2缩减器，输入信号是所述第二级流水线产生的carry_a、sum_a、carry_b、sum_b，对于所述信号a和信号b，按照二次Booth64编码变换式B＝8a+b，先通过移位产生8_carry_a、8_sum_a，再把所述8_carry_a、8_sum_a、carry_b、sum_b通过一个4:2部分积压缩电路得到最终的两个部分积Sum、Carry。