一种适用于大数的快速模平方运算电路

摘要

本发明公开了一种适用于大数的快速模平方运算电路，该电路结构包括：掐头去尾移位补值电路，两个二输入与门阵列，一级进位保存加法器（CSA）结构，一级全加器（FA）单元，以及一系列扫描寄存器。本发明将平方运算按多项式乘法展开，原先的m个部分积求和压缩成m/2个部分积求和，且从高位向低位累加，因此平方运算时间减少为原来的一半。

说明书

技术领域

本发明涉及集成电路设计领域，具体涉及一种适用于大数的快速模平方 运算电路。

背景技术

目前，对于大数平方的研究通常采用的方案是蒙哥马利算法，该算法在 平方的运算过程所耗费的时间和输入数据的长度成正比。

有鉴于此，有必要研究一种新的平方算法，通过对运算过程的部分积的 优化，减少部分积的次数，从而减少整个平方的运行时间，解决上述问题。

发明内容

本发明的目的在于提供一种能够有效减少模平方运算时间的适用于大数 的快速模平方运算电路。

为了达到上述目的，本发明所采用的技术方案是：包括向左移位电路、 m位二选一数据选择器阵列、m位二输入与门阵列、m位部分积产生电路、 全加器FA阵列、m+3位扫描寄存器、约简电路以及带有一个m/2位的johnson 计数器的掐头去尾移位补值电路；掐头去尾移位补值电路的输入为m位的平 方运算输入项A，输出为掐头去尾移位补值电路中m位寄存器的输出Q，同 时输出掐头去尾移位补值电路中m/2位johnson循环移位计数器中寄存器的 输出Qc；向左移位电路的输入为平方输入项A的低m/2位；m位部分积产 生电路的输入端与m位二输入与门阵列的输出端相连，m位部分积产生电路 的输出端与全加器FA阵列的输入端相连，全加器FA阵列通过m+3位扫描 寄存器与简约电路相连；其中，160≤m≤15360。

所述的向左移位电路，每一个时钟上升沿到来时，向左移位电路中寄存 器的值左移一位，并把低位补零，同时将最高位寄存器的输出端引出，定义 为AL。

所述的m位二选一数据选择器阵列包括m位二选一数据选择器，其中m 位的二选一数据选择器的控制信号由掐头去尾移位补值电路中的Johnson循 环移位计数器输出Qc产生；其中，第一位二选一数据选择器和第二位二选 一数据选择器的控制信号为Qc的第二位数值，第三位二选一数据选择器和 第四位二选一数据选择器的控制信号为Qc的第三位数值，以此类推，第m-3 位二选一数据选择器和第m-2位二选一数据选择器的制信号为Qc的第m/2 位数值，第m-1位二选一数据选择器和第m位二选一数据选择器的制信号置 为1；m位二选一数据选择器的“0”端接向左移位电路的输出AL，“1”端 接掐头去尾移位补值电路的输出Q的最高位。

所述的m位二输入与门的输入端中的一个端口与m位二选一数据选择器 阵列的m位对应相连，另一个输入端按如下方式连接：

第一位与门连接掐头去尾移位补值电路的输出Q的最低位，第二位与门 连接Q的第二位，以此类推，第m-1位与门连接Q的次高位的反码，第m 位与门连接Q的次高位；m位与门阵列的输出为最终的m位部分积输出。

所述的m位部分积产生电路，在部分积产生后，送入m个全加器FA中 作为输入，其中，最低位的全加器的进位输入连接一个二选一数据选择器的 输出，二选一数据选择器的“0”端连接掐头去尾移位补值电路的m位输出 Q的最低位Q[0]，“1”端输入零，二选一数据选择器的控制信号为掐头去 尾移位补值电路中Johnson循环移位计数器的输出Qc的第二位Qc[1]；其余 全加器的进位输入均为来自低位的进位输出。

所述的m位全加器FA的和位输出送入扫描寄存器的输入端“0”端；最低 位扫描寄存器的“1”端连接一个二选一数据选择器的输出端，二选一数据选择 器的输入“0”端连接平方运算输入项A的最低位A[0]，“1”端输入零，二选一 数据选择器的控制信号为Sel，该信号由掐头去尾移位补值电路中Johnson计 数器的输出端Qc的最低位和最高位相异或产生；第二位扫描寄存器的“1”端 输入零，第三位扫描寄存器的“1”端输入第一位全加器FA的和位，第四位扫 描寄存器的“1”端输入第二位全加器FA的和位，以此类推，第m+2位扫描寄 存器的“1”端输入第m位全加器FA的和位，第m+3位扫描寄存器的“1”端输 入第m位全加器FA的进位输出。

所述的m+3位扫描寄存器的输出端送入约简电路进行约简。

与现有技术相比，本发明具有以下有益效果：

本发明部分积产生电路将m个部分积压缩为m/2个，最终平方运算采用 从高位到低位运算，第一个部分积产生后向左移两位，送入约简电路约简后 与第二个部分积相加，完成一次累加，以此类推，直到第m/2个部分积产生， 完成m/2次累加，最终完成模平方运算。

进一步的，本发明将平方运算按多项式乘法展开，原先的m个部分积求 和压缩成m/2个部分积求和，且从高位向低位累加，因此平方运算时间减少 为原来的一半。

附图说明

图1为本发明的电路结构示意图；

图2为本发部分积累加及约简的电路结构示意图。

具体实施方式

下面结合附图和实施例对本发明作进一步详细的说明：

参见图1和图2，本发明包括向左移位电路、m位二选一数据选择器阵 列、m位二输入与门阵列、m位部分积产生电路、全加器FA阵列、m+3位 扫描寄存器、约简电路以及带有一个m/2位的johnson计数器的掐头去尾移 位补值电路；掐头去尾移位补值电路的输入为m位的平方运算输入项A，输 出为掐头去尾移位补值电路中m位寄存器的输出Q，同时输出掐头去尾移位 补值电路中m/2位johnson循环移位计数器中寄存器的输出Qc；向左移位电 路的输入为平方输入项A的低m/2位；向左移位电路，每一个时钟上升沿到 来时，向左移位电路中寄存器的值左移一位，并把低位补零，同时将最高位 寄存器的输出端引出，定义为AL。m位部分积产生电路的输入端与m位二 输入与门阵列的输出端相连，m位二输入与门的输入端中的一个端口与m位 二选一数据选择器阵列的m位对应相连，另一个输入端按如下方式连接：第 一位与门连接掐头去尾移位补值电路的输出Q的最低位，第二位与门连接Q 的第二位，以此类推，第m-1位与门连接Q的次高位的反码，第m位与门 连接Q的次高位；m位与门阵列的输出为最终的m位部分积输出。m位部 分积产生电路的输出端与全加器FA阵列的输入端相连，全加器FA阵列通 过m+3位扫描寄存器与简约电路相连，m+3位扫描寄存器的输出端送入约简 电路进行约简；其中，160≤m≤15360。

m位二选一数据选择器阵列包括m位二选一数据选择器，其中m位的二 选一数据选择器的控制信号由掐头去尾移位补值电路中的Johnson循环移位 计数器输出Qc产生；其中，第一位二选一数据选择器和第二位二选一数据 选择器的控制信号为Qc的第二位数值，第三位二选一数据选择器和第四位 二选一数据选择器的控制信号为Qc的第三位数值，以此类推，第m-3位二 选一数据选择器和第m-2位二选一数据选择器的制信号为Qc的第m/2位数 值，第m-1位二选一数据选择器和第m位二选一数据选择器的制信号置为1； m位二选一数据选择器的“0”端接向左移位电路的输出AL，“1”端接掐 头去尾移位补值电路的输出Q的最高位。

m位部分积产生电路，在部分积产生后，送入m个全加器FA中作为输 入，其中，最低位的全加器的进位输入连接一个二选一数据选择器的输出， 二选一数据选择器的“0”端连接掐头去尾移位补值电路的m位输出Q的最 低位Q[0]，“1”端输入零，二选一数据选择器的控制信号为掐头去尾移位 补值电路中Johnson循环移位计数器的输出Qc的第二位Qc[1]；其余全加器 的进位输入均为来自低位的进位输出。

m位全加器FA的和位输出送入扫描寄存器的输入端“0”端；最低位扫描 寄存器的“1”端连接一个二选一数据选择器的输出端，二选一数据选择器的输 入“0”端连接平方运算输入项A的最低位A[0]，“1”端输入零，二选一数据选 择器的控制信号为Sel，该信号由掐头去尾移位补值电路中Johnson计数器的 输出端Qc的最低位和最高位相异或产生；第二位扫描寄存器的“1”端输入零， 第三位扫描寄存器的“1”端输入第一位全加器FA的和位，第四位扫描寄存器 的“1”端输入第二位全加器FA的和位，以此类推，第m+2位扫描寄存器的“1” 端输入第m位全加器FA的和位，第m+3位扫描寄存器的“1”端输入第m位 全加器FA的进位输出。

本发明适用于大数模平方运算的快速平方算法的电路实现结构包括：掐 头去尾移位补值电路、向左移位电路、一系列二选一电路、二输入与门阵列、 全加器FA阵列和一系列扫描寄存器和约简电路。其中，掐头去尾移位补值 电路中包含一个m/2位的johnson计数器。掐头去尾移位补值电路的输入为m 位的平方输入项A，输出为掐头去尾移位补值电路中m位寄存器的输出Q， 同时输出m/2位johnson循环移位计数器中寄存器的输出Qc。向左移位电路 的输入为平方输入项A的低m/2位，每一个时钟上升沿到来时，向左移位电 路中寄存器的值左移一位，并把低位补零，同时将最高位寄存器的输出端引 出，定义为AL。m位二选一阵列的控制信号主要由掐头去尾移位补值电路 中的Johnson循环移位计数器输出Qc产生。第一位和第二位二选一的控制信 号为Qc的第二位数值，第三位和第四位二选一的控制信号为Qc的第三位数 值，以此类推……第m-3位和第m-2位的二选一控制信号为Qc的第m/2位 数值，第m-1位和第m位的二选一控制信号置为1。m位二选一阵列的“0” 端接向左移位电路的输出AL，“1”端接掐头去尾移位补值电路的输出Q的最 高位。m位二输入与门输入端其中一个端口与m位二选一阵列的m位对应 相连，另一个输入端按如下方式连接：第一位与门连接掐头去尾移位补值电 路的输出Q的最低位，第二位与门连接Q的第二位，以此类推……第m-1 位与门连接Q的次高位的反码，第m位与门连接Q的次高位。m位与门阵 列的输出为最终的m位部分积输出。

部分积产生后，送入m个全加器FA中作为输入，其中，最低位的全加 器的进位输入连接一个二选一的输出，二选一的“0”端连接掐头去尾移位补值 电路的m位输出Q的最低位Q[0]，“1”端输入零，二选一的控制信号为掐头 去尾移位补值电路中Johnson循环移位计数器的输出Qc的第二位Qc[1]； 其余全加器的进位输入均为来自低位的进位输出。m位全加器的和位输出送 入扫描寄存器的输入端“0”端。最低位扫描寄存器的“1”端连接一个二选一的 输出端，二选一的输入“0”端连接平方运算的输入项A的最低位A[0]，“1”端 输入零，二选一的控制信号为Sel，该信号由掐头去尾移位补值电路中Johnson 计数器的输出端Qc的最低位和最高位相异或产生。第二位扫描寄存器的“1” 端输入零，第三位扫描寄存器的“1”端输入第一位全加器FA的和位，第四位 扫描寄存器的“1”端输入第二位全加器FA的和位，以此类推，第m+2位扫描 寄存器的“1”端输入第m位全加器FA的和位，第m+3位扫描寄存器的“1”端 输入第m位全加器FA的进位输出。m+3位扫描寄存器的输出端送入约简电 路进行约简。

在本发明中，部分积产生电路将m个部分积压缩为m/2个，最终平方运 算采用从高位到低位运算，第一个部分积产生后向左移两位，送入约简电路 约简后与第二个部分积相加，完成一次累加，以此类推，直到第m/2个部分 积产生，完成m/2次累加，最终完成模平方运算。

表1

参照表1，表1为按照多项式乘法展开后的平方运算的部分积求和表格， 整个过程需要对m个部分积进行求和，整个过程需要m-1个时钟周期。

表2

参照表2，表2为本发明优化后的部分积求和表格，将部分积压缩为表1 中的一半，整个过程只需m/2-1个时钟即可完成平方运算。

表3

            A5A4 A5(!A4) A7A1 A6A1 A5A1 A4A1 A3A1 A2A1+A2 0 A1         A6A5 A6(!A5) A6A4 A6A3 A6A2 A5A2 A4A2 A3A2+A3             A7A6 A7(!A6) A7A5 A7A4 A7A3 A7A2 A5A3 A4A3+A4             A8A7 A8(!A7) A8A6 A8A5 A8A4 A8A3 A8A2 A8A1                

参照表3，表3为以8位二进制数为例采用本算法的平方部分积求和表 格，以8位二进制数为例，采用本发明算法，将部分积压缩为4项。

本发明的运算过程：

参见图1和图2，初始化时RS=0，将寄存器全部置为0；工作时，RS=1， 第一个有效时钟沿后，掐头去尾移位补值电路输出Q=[A_m，A_m-1，A_m-2…A₂， A₁]、Qc=[11…111]；第二个有效时钟沿之后，第一次部分积累加完成，掐头 去尾移位补值电路输出Q=[A_m-1，A_m-2…A₂,A_m/2+1,A_m/2]、Qc=[11…110]；直至 第m/2个时钟沿之后，完成m/2-1个部分积累加，同时输出数据左移存入寄 存器，因此寄存器最低两位为00；第m/2+1个时钟沿到来时，所有的部分积 累加完成同时在最后两位寄存器中存入0和平方运算的输入项A的最低位； 在部分积累加的过程中，每个时钟上升沿到来后将m+3个扫描寄存器的输出 值值送入约简电路，约简完成后等待下一个时钟沿到来，与下一个部分积累 加，以此类推……直到第m/2+1个时钟沿之后，寄存器停止移位，最多再经 过两个时钟沿，最终完成模平方运算过程。