实现基4-Booth编码方法的门电路和基于该方法的流水线大数乘法器

摘要

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

主权项

一种实现基4‑Booth编码方法的门电路，所述基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)\right)·\left(A\right[j-1]\oplus M_i+X_i)·(X_i+{\mathrm{Modify}}_i)$其中B[2i]代表乘数的第2i比特位，A[j]表示被乘数A的第j比特位；其特征在于，所述门电路包括：第一异或门(1)，其一路输入端接B[2i‑1]，另一路输入端接B[2i]；第二异或门(2)，其一路输入端接B[2i‑1]，另一路输入端接B[2i+1]；第一或门(3)，其一路输入端接第一异或门(1)的输出X_i，另一路输入端接第二异或门(2)的输出；第三异或门(5)，其一路输入端接B[2i+1]，另一路输入端接A[j]；第四异或门(4)，其一路输入端接B[2i+1]，另一路输入端接A[j‑1]；非门(6)，其输入端接第一异或门(1)的输出X_i；第二或门(7)，其一路输入端接第三异或门(5)的输出，另一路输入端接非门(6)的输出；第三或门(8)，其一路输入端接第一异或门(1)的输出X_i，另一路输入端接第一或门(3)的输出Modify_i；第四或门(9)，其一路输入端接第一异或门(1)的输出X_i，另一路输入端接第四异或门(4)的输出；与门(10)，其输入端分别接第二或门(7)、第三或门(8)和第四或门(9)的输出；所述B[2i‑1]表示乘数B的第2i‑1比特位，B[2i]表示乘数B的第2i比特位，B[2i+1]表示乘数B的第2i+1比特位，A[j]表示乘数A的第j比特位，A[j‑1]表示乘数A的第j‑1比特位。