“?在ECC和RSA算法硬件實現(xiàn)(Barrett約減和Montgomery約減)中，需要提前計算某些參數(shù)，會應用到除法器。”

01

—

傳統(tǒng)除法器

傳統(tǒng)除法器的設計非常單純：一、先取除數(shù)和被除數(shù)的正負關系，然后正值化被除數(shù)。傳統(tǒng)除法器因為需要遞減的關系，所以除數(shù)就取負值的補碼，方便操作。二、被除數(shù)遞減與除數(shù)，每一次的遞減，商數(shù)遞增。三、直到被除數(shù)小于除數(shù)，遞減過程剩下的是余數(shù)。四、輸出的結果根據(jù)除數(shù)和被除數(shù)的正負關系。傳統(tǒng)的除法器設計簡單，但是如果除數(shù)比較大，被除數(shù)比較小，計算起來就會占用更多的時鐘周期。

02

—

移位相減除法器

移位相減除法器的優(yōu)勢在于，計算時間只與除數(shù)、被除數(shù)位寬有關，與除數(shù)和被除數(shù)大小無關。

03

—

移位相減除法器實現(xiàn)

對于32的無符號除法，被除數(shù)a除以除數(shù)b，他們的商和余數(shù)一定不會超過32位。首先將a轉換成高32位為0，低32位為a的temp_a。把b轉換成高32位為b，低32位為0的temp_b。在每個周期開始時，先將temp_a左移一位，末尾補0，然后與b比較，是否大于b，是則temp_a減去temp_b將且加上1，否則繼續(xù)往下執(zhí)行。上面的移位、比較和減法(視具體情況而定)要執(zhí)行32次，執(zhí)行結束后temp_a的高32位即為余數(shù)，低32位即為商。

04

—

移位相減除法器原理

假設4bit的兩數(shù)相除 a/b，商和余數(shù)最多只有4位 (假設1101/0010也就是13除以2得6余1)。我們先自己做二進制除法，則首先看a的MSB，若比除數(shù)小則看前兩位，大則減除數(shù)，然后看余數(shù)，以此類推直到最后看到LSB；而上述算法道理一樣，a左移進前四位目的就在于從a本身的MSB開始看起，移4次則是看到LSB為止，期間若比除數(shù)大，則減去除數(shù)，注意減完以后正是此時所剩的余數(shù)。而商呢則加到了這個數(shù)的末尾，因為只要比除數(shù)大，商就是1，而商0則是直接左移了，因為會自動補0。這里比較巧因為商可以隨此時的a繼續(xù)左移，然后新的商會繼續(xù)加到末尾。經(jīng)過比對會發(fā)現(xiàn)移4位后左右兩邊分別就是余數(shù)和商。

Something else：

除數(shù)Divisor,被除數(shù)Dividend，商數(shù)Quotient，余數(shù)Reminder。

部分轉載自：

http://xilinx.eetrend.com/d6-xilinx/forum/2013-11/6071.html

https://wenku.baidu.com/view/6fdbfa0f52ea551810a687c2.html

總結

以上是生活随笔為你收集整理的硬件除法器原理_[ECCamp;RSA]除法器的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。