一種基于Verilog的大整數(shù)除法器的實(shí)現(xiàn).pdf

1、隨著計(jì)算機(jī)網(wǎng)絡(luò)和現(xiàn)代信息技術(shù)的蓬勃發(fā)展，大整數(shù)的除法作為一項(xiàng)基本運(yùn)算在各種場(chǎng)合扮演著越來(lái)越重要的作用。在物理學(xué)、生物學(xué)和化學(xué)等學(xué)科的許多研究中，都離不開(kāi)大整數(shù)的除法運(yùn)算。而在信息安全領(lǐng)域，眾多加解密技術(shù)如 RSA、ECC、DSA以及ElGamal等公鑰密碼算法更是以大整數(shù)的運(yùn)算為基礎(chǔ)的，而大整數(shù)的除法運(yùn)算正是大整數(shù)運(yùn)算的重要組成部分之一，因此，如何快速完成大整數(shù)的除法運(yùn)算，對(duì)這些加解密算法起著至關(guān)重要的作用。盡管在很多場(chǎng)合下，研究人員更

2、多的是采用C語(yǔ)言或者C++來(lái)實(shí)現(xiàn)大整數(shù)的各項(xiàng)運(yùn)算算法，但是由于這些加密算法都會(huì)運(yùn)用到芯片的加密程序中，因此大整數(shù)除法的硬件實(shí)現(xiàn)就顯得格外重要了。
　　由于在眾多硬件描述語(yǔ)言中，Verilog HDL語(yǔ)言效率高，靈活性強(qiáng)，而且最為常用，因此本文目標(biāo)是以Verilog HDL語(yǔ)言為基礎(chǔ)，實(shí)現(xiàn)位寬達(dá)到2048位的被除數(shù)對(duì)除數(shù)進(jìn)行相除的大整數(shù)除法器。本文首先對(duì)包括除法在內(nèi)的大整數(shù)的運(yùn)算的重要性及意義做了簡(jiǎn)明扼要的闡述，并且對(duì)從大整數(shù)除法得

3、到重視以來(lái)科學(xué)家們對(duì)其的研究與實(shí)現(xiàn)所做的大量工作做了一定的介紹。然后對(duì)大整數(shù)的存儲(chǔ)方法以及表示方法進(jìn)行了說(shuō)明，接著分析了大整數(shù)的加法、減法以及乘法的算法思想及實(shí)現(xiàn)思路，并且對(duì)常見(jiàn)的幾種大整數(shù)的除法算法盡行了分析和比較之后，確定使用估商試除法的思想來(lái)最終完成大整數(shù)除法器的設(shè)計(jì)。對(duì)于估商試除法來(lái)說(shuō)，最關(guān)鍵的一步就是估商的過(guò)程，因?yàn)閷?duì)商的估計(jì)越準(zhǔn)確，后續(xù)對(duì)商的糾正工作就會(huì)越簡(jiǎn)單，否則，修正商就會(huì)浪費(fèi)大量的時(shí)間與空間。因此在對(duì)商的估計(jì)與修正中，

4、采用了唐納德.克努特于六十年代提出的估商算法，這個(gè)算法可以使估商的誤差不大于2，使得整個(gè)除法的運(yùn)算量得到大大簡(jiǎn)化。
　　本文花了最大篇幅對(duì)大整數(shù)除法器的實(shí)現(xiàn)過(guò)程進(jìn)行了詳細(xì)的介紹。在確定了采用克努特估商算法聯(lián)合試除法的思想來(lái)設(shè)計(jì)除法器之后，本文首先明確了整個(gè)除法的運(yùn)算過(guò)程和步驟，并以此為基礎(chǔ)設(shè)計(jì)了除法器的主體架構(gòu)。然后根據(jù)大整數(shù)除法器的主體架構(gòu)對(duì)各個(gè)模塊進(jìn)行了劃分，并最終完成設(shè)計(jì)和驗(yàn)證工作。本文所設(shè)計(jì)的大整數(shù)除法器可以完成被除數(shù)位寬