基4-Booth编码方法及门电路和流水线大数乘法器

摘要

本发明基4-Booth编码方法，乘数B每相邻的三位共有八种组合方式，不同的组合形式分别代表部分积选择是0，±A，±2A之中的一种，其中A代表被乘数，编码值Xi等于1表示绝对值是被乘数自身的组合方式，编码值Xi等于0表示其余组合方式；编码值Mi等于1表示部分积为负数的组合方式；编码值Modifyi等于1表示绝对值非零的六种组合方式，本发明同时提供了实现该编码的门电路以及基于该编码的流水线大数乘法器，本发明编码方法可缩短Booth编码的延时，流水线大数乘法器可实现256位大数乘法运算，应用于公钥密码算法模乘运算中，可大幅提高公钥密码芯片的性能。

主权项

1.一种基4-Booth编码方法，其特征在于，如下表所示：乘数B每相邻的三位共有八种组合方式，不同的组合形式分别代表部分积选择是0，±A，±2A之中的一种，其中A代表被乘数，编码值X_i等于1表示绝对值是被乘数自身的组合方式，编码值X_i等于0表示其余组合方式；编码值M_i等于1表示部分积为负数的组合方式；编码值Modify_i等于1表示绝对值非零的六种组合方式，所述编码值中的i表示生成第i个部分积所需要的编码值序号，对256位乘法器来说，其范围是0～128；所述编码值X_i、M_i、Modify_i的逻辑表达式概括如下：$X_i=B[2i-1]\oplus B\left[2i\right]$M_i=B[2i+1]${\mathrm{Modify}}_i=B[2i+1]\oplus B[2i-1]+B\left[2i\right]\oplus B[2i-1]$部分积每一比特位的生成如下述逻辑表达式所示：$p_i\left[j\right]=\left(A\right[j]\oplus M_i+(~X_i))·\left(A\right[j-1]\oplus M_i+X_i)·(X_i+{\mathrm{Modify}}_i)$其中B[2i]代表乘数的第2i比特位，A[j]表示被乘数A的第j比特位。