一種高速乘法器的製作方法

2023-10-11 16:17:04

專利名稱：一種高速乘法器的製作方法
技術領域：
本發明涉及一種乘法器及除法器，特別是一種用於計算機中心處理單元(CPU)及各種數位訊號處理中的運算器。
目前的乘法器電路實現二個n位整數相乘時，技術上採用移位__加的算法，做n次加法與n次位移，是一種最慢最簡單的乘法器。有許多改進方案，例如歐州專利0534760″高速乘法裝置″，不是由乘數一位位的決定移位__加，而是按乘數編碼組決定被乘數的位移__加。美國專利4769780″高速乘法器″根據一次4比特(16進位)的乘數決定被乘數的位移__加，得出部分和，直到做完4次(64比特)，用高階基數作位的計算單位，但仍是串行計算。大規模並行計算中的陣列乘法器，將問題化為一個矩陣部份積產生器和一個加法陣列，其實現上有各種方案。例如進位保存陣列加法方案(CSA)，有n2個與門細胞元，得出n2個部分積後一位位陣列相加，CSA相加採用Wallace樹的CSA互連結構，減少部份積為2個操作數，儘可能並行處理，是技術上最快的一種算法之一。各種Wallace樹的改進，如美國專利申請NO653053和美國專利4799183″具有並行進位保留加法樹的矢量乘法器″將乘數分成4個16比特的組，分別同被乘數64比特相乘，每級流水用較多時間執行16×64。這類分組並行的組越多，級數越多，每級用時少，流水長。反之，每組用時多，流水線短，當n大時尤為突出。現有的乘法器技術都是一次將n位操作數全部存入操作數寄存器才能進行運算。進行多級連續相乘，必須等待上級運算的全部2n位乘積全都出來才能開始下級。目前整數定點運算電路精度高、運算快，但是數的動態範圍小。傳統上浮點數表示數的動態範圍大但卻影響精度。技術上實現多個部份積相加時，進位由最低位向高位推進過程經歷較多進位延遲。這種串行進位的時間與位數n成比例增長。
發明的主要目的在於提供一種達到操作數局部並行相乘，部份積的高位、低位、低到高的進位並行相加，流水得到部份高位乘積，循環得到全部積的乘法器；利用單乘法器多級串聯能夠順序流水處理多級連乘提高運算速度；不限定操作數長度，運算過程可僅僅處理高位數據、捨棄任意的低位操作即可以加快運算，又可以達到浮點動態範圍大優點的定點乘法器。
發明的又一目的在於提供一種基於單乘法器的大規模並行乘法裝置，把上述單乘法器多重並行設置，對所有部份積達到並行相加和進位，以達到比傳統相加更快速地得到乘積。
發明的又一目的在於提供一種基於乘法電路加少部份輔助電路單元進行除法的除法器，按乘法過程並行執行除數乘以全部可能商(試商)，比較其乘積和被除數確定商，循環求得所需精度的高速運算除法器。
本發明的目的可以通過以下措施來達到本發明的乘法器由兩n比特寄存器RA(被乘數)、RB(乘數)、操作數輸入電路、陣列乘法單元、部分積加法CSA樹電路、2n比特寄存器RC(乘積)組成。
操作數輸入電路由m個k比特被乘數寄存器、m個k比特乘數寄存器組成。
陣列乘法單元由m個k比特積產生單元、m個高位進位保留加法器CSA、m個低位進位保留加法器CSA、m個進位鎖存器組成；或者由m個k比特直接乘單元組成。
部分積加法CSA樹電路由一個m端CSA樹、另一個同樣結構的CSA樹、一m+1端CSA加法樹、一個移位累加器、一k端與非門組成；或者由一個m端CSA樹、另一個同樣結構的CSA樹、一m端CSA加法樹、3端CSA加法器、一個移位累加器、一k端與非門組成；或者由一個m端CSA樹、另一同樣結構的CSA樹、兩個加法器、一個移位累加器、一k端與非門組成。
寄存器RA、RB將操作數按每個時鐘節拍由高到低順序輸出到操作數輸入電路，整個乘法過程共進行2m-1次；操作數輸入電路按同樣的節拍、順序、數據長度接收RA、RB的數據，將每K比特的被乘數與所有的K比特乘數配對，輸出到陣列整個乘法過程共進行2m-1次，每次分別配對1、2、---、m、---、1對；陣列乘法單元按同樣的節拍、順序、數據長度將操作數輸入電路的配對數據相乘，生成的比特積項分高位、低位相加，得出1或m個k比特的高、低位部份積送到部份積加法CSA樹，整個乘法過程共進行2m-1次；部份積加法CSA樹電路按同樣的節拍、順序將陣列乘法單元送來的1-m個k比特高位部份積、低位部份積，或者連同它們之間進位同時相加，輸出最高k比特乘積到寄存器RC，整個乘法過程中一共進行2m-1次；寄存器RC按同樣的節拍、順序接收部份積加法CSA樹送來的高位的k比特乘積，左移k比特後準備下次接收低位的乘積，整個乘法過程共進行2m次；本發明乘法器將兩個相乘的n比特操作數通過二個寄存器，按高到低順序各取k比特送1-m個比特積產生單元。得到部份積輸入兩進位保留加法器CSA--高位CSA和低位CSA--中相加。兩部份和--高位和低位--分別於高位CSA樹和低位CSA樹相加，結果與m個進位鎖存中的值於進位CSA樹中相加。輸出和與高位CSA樹的和直接於移位累加器內累加並左移k比特輸出一高位到乘積寄存器(1位＝k比特，下同)。第一高位積將於此過程進行常數a次後，k端與非門根據輸入是否為全″1″，由移位累加器左移k比特輸出到乘積寄存器。否則左移後不輸出，直到當k端與非門滿足條件時移位累加器左移輸出a＊k比特之前的所有積。常數a受操作數位數m限制當m＝16，a＝3；當m＝256，a＝4。乘法器可對任意小於m位的兩操作數m1、m2相乘，這種情況下乘法的計算少進行(m-m1)＊(m-m2)項，省略2m-(m1+m2)位乘積運算，提前得出乘積。
或者三個部份和--高位、低位、進位--分別於高位CSA、低位CSA樹、進位CSA樹中相加。三個的和輸出直接於3端CSA加法器相加，相加的進位與高位CAS進位於另一加法器相加。三個和直接送移位累加器累加並左移k比特，輸出過程同上。
或者將兩個相乘的n比特操作數通過兩個寄存器RA、RB，並行送入k比特直接乘單元。一拍執行m個kxk。其高、低位積的和分別由高位CSA-H和低位CSA-L得到。高位和與低位進位於一加法器相加，相加的進位與高位CAS進位於另一加法器相加。三個和直接送移位累加器累加並左移k比特，輸出過程同上。
本發明的更高速並行乘法裝置由2m-1個上述單乘法、2m-2個加法器CSA、2m-2個部份和鎖存器、2m-3個進位鎖存器、2m-3個與門、2m-1個加法單元組成。
本發明的大規模更高速並行乘法裝置將上述包含第二種部分積加法CSA樹電路的乘法器重複設置2m-1個。其中各內含的陣列乘法單元數不等，分別為1、2、…、m、m-1、…、1。兩操作數A、B各取k比特通過兩寄存器RA、RB送入不同單元一步執行m2個Ai＊Bj，產生低位積P2m及其它高位部份積。這些部份積經2m-2個加法器CSA相加一次，產生次低位積P2m-1，輸出2m-3個k比特部份積P′2、---、P′2m-2到2m-3個和鎖存器和2m-3個進位鎖存器。2m-3個與門檢測它們的值全為″1″時，對高位有進位，再次相加，產生2m-3個低位積P2P3---P2m-2。如果產生所有低位積的過程對最高位有進位，再次加後得出最高位積P1。所有部份積僅僅經執行三次k比特加法，效率比並行相加串行進位提高近m/3倍，實現用一步(5拍)產生2m位乘積P＝P1P2P3...P2m-1P2m。比單乘法少用2m-1步(拍)。
本發明的除法器由兩個操作數寄存器(被除數、除數)、兩個結果寄存器(商、餘數)、一個輔助寄存器、w(w＝2k，下同)個乘法器、w個試商發生器、w個減法器、一2k端比較器、一計數器、一比較器、一減1器組成。
本發明的除法器設置w個乘法器，除數寄存器、被除數寄存器存放操作數，商寄存器、餘數寄存器存放結果，輔助寄存器存放精度控制參數。w個試商發生器每次產生O-w-1個可能商值。每次將已求出的前i-1個商結合第i個試商值與i位除數相乘，乘積由w個減法器被除數相減求得w個餘數。w個比較器將找出餘數集合中的最小正數對應的試商值作為商值。取下一位除數，循環求下一商；若餘數集合全小於零，則減1器中將前i位商值減1，重新相乘、相減，直到餘數得正數。循環到精度p位。這種基於高速乘法的除法運算，執行速度很快。將除數寄存器換成商寄存器的連接，除法時對兩個寄存器的值同時減1。除法器能夠求出被除數的開平方。
把本發明的單乘法器多重設置，第一個乘積寄存器輸出直接與第二個的被乘數寄存器相連，第二個與第三個按同樣方式，…直到連完。多操作數A、B、C、D…分別存放於第一、二、三、…個乘法器的乘數寄存器，可得到一種高效的連乘裝置。
把本發明的上述單乘法器，增加兩大數操作數寄存器、一輸入控制邏輯、兩累加器(第一、第二累加器)、一n端與非門、一大數乘積寄存器可構成一種任意字長、任意精度的乘法器。
本發明與現有技術相比具備如下效果由於本發明的乘法器採用每次部份操作數並行相乘，部份積的高、低位、進位並行相加，流水級少，每級時間短，速度快。由高到低得出一位位乘積，不影響高位的精度時捨棄任意低位的操作，能夠贏得速度。可對大整數運算，以定點整數電路結構得到相當浮點的動態範圍。把單乘法裝置串聯多級，能順序流水處理多級連乘A＊B＊C…，減少連乘間的數據相關度，提高連乘情況下總運算速度。基於單乘法器的大規模並行相乘的裝置，一次對所有mz個操作數相乘，採用並行加法進位的手段以比傳統並行相加串行進位快3倍的速度相加部份積，能夠比單乘法器快數倍得到全部乘積。採用基於乘法器可對任意兩小於m位的操作數相乘的特點，每次並行執行除數乘以試商，比較調整後確定k比特商、循環達到一定精度的除法器，電路筒單、高速。
附圖的圖例說明

圖1.乘法器結構框2.乘法器電路3.部分積加法CSA樹之二電路4.乘法器電路之二5.大規模並行乘法裝置6.除法運算流程7.除法裝置圖本發明的最佳實施方式下面結合附圖進一步祥細解釋本發明(實施方式中，n為操作數比特數，k為每位比特數，m＝n/k 為位數。k∶m為1∶4或1∶2或1∶1或2∶1或4∶1。1∶1較合理，當n＝64時，k可取8，則m為8，當n＝32時，k可取4，則m為8)如圖1所示本發明乘法器將兩個n比特寄存器RA(被乘數)1、RB(乘數)2的輸出連接到操作數輸入電路DATAIN3輸入端，其輸出連接到陣列乘法單元MUUNIT4輸入端，後者又連接到部分積加法CSA樹電路CSATREE5的輸入端，其輸出連接到2n比特寄存器RC(乘積)6的輸入端。
如圖2所示本發明乘法器電路圖，將操作數輸入電路3中寄存器RA1的輸出按每組k比特由高到低順序連接到m個k比特被乘數寄存器Ra7、9、11，將寄存器RB2的輸出連接到乘數寄存器Rb8的輸入端，寄存器Rb8的輸出連接到寄存器Rb10的輸出端，按此方式直到連完m個寄存器Rb12。第1對寄存器Ra7與Rb8連接到陣列乘法單元MUUNIT4的第1個比特積產生個單元MA13兩輸入端、第2對寄存器Ra9與Rb10連接到第2個比特積產生單元MA14輸入、第m對寄存器Ra11與Rb12連接到第m個比特積產生單元MA15。m個k比特積產生單元MA13、MA14、MA15的k個高位比特積輸出端連到對應的m個有k輸入端的高位CSACSA16、17、18；k個低位比特積輸出端連到m個有k輸入端的低位CSACSA19、20、21。m個高位CSA的輸出連到一個m端CSA樹HCSA25；m個低位CSA連到另一同樣結構的CSA樹LCSA27。低位CSA19、20、21的進位輸出連到m個進位鎖存器CL22、23、24，後者輸出與LCSA27輸出共同連到一m+1端CSA加法器CCSA26的m+1個輸入端，其輸出與CSA樹HCSA25的輸出連到移位累加器SA29兩操作數端。移位累加器SA29的輸出連到乘積寄存器RC6的輸入端。移位累加器SA29的接收當前數據的高端a＊k比特(a對特定m為常數)之處輸出k比特連到k輸入與非門A28，後者的輸出又反饋到它的控制輸入端。
本發明乘法器操作數輸入電路3的寄存器RA1按時鐘節拍每次由高到低順序輸出k比特數據到m個寄存器Ra7、9、11。寄存器RB2每時鐘節拍由高到低順序輸出k比特數據到寄存器Rb8，寄存器Rb8輸出k比特到寄存器Rb10，最後傳到寄存器Rb12。m對寄存器--Ra7與Rb8、Ra9與Rb10、Ra11與Rb12--按時鐘節拍每次輸出k比特數據到陣列乘法單元MUUINT4的m個k比特積產生單元MA13、MA14、MA15的輸入。比特積產生單元MA13、14、15具有由n2個與門組成的相同結構。一拍執行n2個乘。設A、B為m位操作數(序號小的為高位端)A＝A1A2…Am其中Ai＝ai1ai2…aip…aik為k比特1≤i≤mB＝B1B2…Bm其中Bj＝bj1bj2…bjp…bjk為k比特1≤j≤m高位CSA16、17、18對2≤p+q≤k的那些比特積項aip＊bjq相加，低位CSA19、20、21對k+1≤p+q ≤2k的積項aip＊bjq相加。高位CSA16、17、18得高位部份積，低位CSA19、20、21得低位部份積。兩數一拍內分別於HCSA25、LCSA27內相加，進位鎖存器CL22、23、24的值與LCSA27的輸出同一拍於CSA加法器CCSA26內相加。HCSA25的輸出與CCSA26的輸出在下一拍於移位累加器SA45與原有的值先後累加並左移k比特。第一高位積將於位移a次後輸出最高k比特到乘積寄存器RC6；乘積寄存器RC6帶左移功能，左移k比特後輸入1位積；若k端與非門A28輸出″0″，SA45、RC6僅僅左移但不輸出，等下一循環當與非門A28滿足條件(輸出為″1″)時，移位累加器一次輸出判斷位(接收當前數據的高端a個k比特處)之前的所有位乘積。整個過程經3級流水。可在第3+a拍得出第一位積，以下每拍一位或者一拍多位，(視與非門A28是否滿足條件)。這裡每拍用時僅僅相當m個k比特進位保留加法器CSA的加法時間。共需3+a+2m-1拍得出全部2m位乘積。常數a與特定操作數位數m有關當m＜＝16時，a＝3；當m＜＝256時，a＝4。它的意義是最高位輸出延時a拍。假如n＝64，k＝8，則m＝64/8＝8，21拍得出128比特乘積；如n＝16，k＝4，則m＝16/4＝4，13拍得出32比特乘積。乘法器可對任意小於m位的兩操作數m1、m2相乘，這種情況下乘法Ai＊Bj(m1＜i＜＝m，m2＜j＜＝m，m1、m2不必相等)的計算少進行(m-ml)＊(m-m2)項，省略2m-(m1+m2)位乘積運算，提前得出乘積。
如圖3所示本發明的部分積加法CSA樹電路之二，m端高CSA樹HCSA25的和輸出與低CSA樹LCSA27的進位輸出及CSA加法器CCSA30的輸出連到CSA加法器CSA31的三個輸入端，HCSA25的進位輸出與CCSA31的進位輸出連到加法器ADD32的兩操作數端。其輸出與CSA31、LCSA27的和輸出共同連到移位累加器SA34的操作數端。移位累加器SA34的輸出次商位連到一k輸入與非門A33，其輸出反饋到它的控制輸入端。移位累加器SA34連到乘積寄存器RC6的輸入端。
本發明乘法器的部分積加法CSA樹電路之二的高、低位部份積之和，進位鎖存器CL22、23、24的值之和分別由高位CSA樹HCAS25、低位CSA樹LCSA27、進位CSA樹CCSA30於同一拍內於得到。HCSA25的和、LCSA27的進位、CCSA30的和於CSA加法器CSA31內相加。進位與HCAS25的進位在同一拍於加法器ADD32相加。其輸出、CSA31與LCSA27的3k比特和輸出於下一拍與移位累加器SA34中原有值累加後左移k比特。第一高位積將於位移a次後輸出最高k比特到乘積寄存器RC6；乘積寄存器RC6帶左移功能，左移k比特後輸入1位積；若k端與非門A33輸出″0″，SA34僅僅左移但不輸出，等下一循環。
如圖4所示本發明乘法器電路之二，將操作數輸入電路3的輸出連接到m個k比特直接乘單元MUL35、MUL36、MUL37的兩輸入端。其k比特高位積輸出連到一個m端CSA樹CSA-H38；k比特低位積連到另一個同樣結構的CSA樹CSA-L39。CSA-H38的和輸出與CSA-L39的進位輸出連到加法器AD-140的兩輸入端。後者與CSA-H38的進位輸出連到加法器AD-241的兩輸入。CSA-L39、AD-140的和輸出與AD-241的輸出共同連到移位累加器SA34，移位累加器SA34的接收當前數據的高端a＊k比特之處輸出連到與非門A33，後者的輸出又反饋到它的控制輸入端。移位累加器SA34輸出連到乘積寄存器RC6。
本發明的乘法器電路之二將兩個相乘的n比特操作數通過兩個寄存器RA1，RB2並行送入k比特直接乘單元MUL35、36、37。一拍執行m個kxk，其高、低位積的和分別由高位CSA-H38和低位CSA-L39得到。CSA-H38的和與低位CSA-L39的進位在一拍內於加法器AD-140內相加，相加的進位和CSA-H38的進位在同一拍內於加法器AD-241相加。AD-140、CSA-L39、AD-241的和輸出在下一拍送移位累加器SA34。
如圖5所示本發明的更高速並行乘法裝置將將部分積加法CSA樹電路之二(圖3)組成的乘法器MU42中自ADD32、CSA31、LCSA27引出的低位輸出k比特、3個乘法器MU43、46、47中自ADD32、CSA31、LCSA27引出二個和輸出(2k比特，由左到右依次為高、低2位)以及2m-5個乘法器MU44、45中自ADD32、CSA31、LCSA27引出的三個和輸出端(3k比特，由左到右依次為進、高、低3位)按圖5示連到CSA加法器CSA51、52的二個、CSA48、49、50的三個輸入端。2m-3個CSA加法器CSA48、49、50、51的和輸出連到個2m-3個部份和鎖存器SL53、54、55、56的輸入，2m-3個CSA加法器CSA49、50、51、52的進位輸出連接到2m-3個進位鎖存器CL57、58、59、60的輸入端。部份和鎖存器SL53、54、55、56的輸出端連接到2m-3個加法單元AD67、68、69、70的被加數端。進位鎖存器CL57、58、59、60的輸出端一方面連接到2m-3個加法單元AD67、68、69、70加數端；另一方面連到2m-3個判斷與門61、62、63、64的輸入端。判斷與門62、63、64的輸出又連到高一級的部份和鎖存器SL53、54、55、71和進位鎖存器CL57、58、59的控制端。2m-3個CSA加法器CSA48、49、50、51的和輸出又連到2m-3個判斷與門61、62、63、64另外的輸入端。乘法器MU42高位輸出k比特連到加法器AD65的被加數端，其加數端來自CSA加法器CSA48的進位輸出端，AD65的和輸出連到鎖存器SL71的輸入端，SL71輸出連到加法器AD66的被加數，其加數來自判斷與門61的輸出。
本發明的更高速並行乘法裝置的2m-1個乘法器中，每個所含的比特積產生單元數MA13、14、15不等，分別為1、2、…、m-1、m、m-1、…、2、1。操作數A、B按圖示規律各取k比特送入不同比特積產生單元MA13、14、15。按圖3所示本發明的部分積加法CSA樹電路之二中ADD32、CSA31、LCSA27形成的k比特部份積送入加法器CSA48，按ADD32、CSA31、LCSA27形成的2k比特部份積送入加法器CSA48、49、51、52，按ADD32、CSA31、LCSA27形成的3k比特部份積送入加法器CSA48、49、50，僅進行一次k比特加法。直接產生低位積P2m-1、P2m，以及將2m-3個部份積P′2、P′3、…、P′2m-2輸出到2m-3個部份和鎖存器SL53、54、55、56輸入端，部份積P′1由MU42的高k比特和CSA加法器CSA48的進位於加法器AD65相加得出，再送SL71；CSA加法器CSA49、50、51、52的後級到前級的進位輸出到2m-3個進位鎖存器CL57、58、59、60的輸入端。2m-3個判斷與門61、62、63、64根據2m-3個部份和鎖存器SL53、54、55、56及進位鎖存器CL57、58、59、60的值是否全″1″，決定是否向高一級進位；控制SL53、54、55、56、SL71以及CL57、58、59、60的控制端。輸出到對應的2m-3個加法單元AD67、68、69、70，再進行一次k比特加法，產生2m-3位積P2P3---P2m-2。如果產生所有低位積的過程對最高位有進位，AD66再次加，得出最高位積P1。所有部份積僅僅經執行三次k比特加法，效率比並行相加串行進位提高近m/3倍，產生乘積P＝P1P2P3...P2m-1P2m。實現一步(5拍)產生2m位乘積，比單乘法少用2m-1步(拍)。
如圖6所示除法流程圖，輸入x位除數A＝A1A2…Ax，y位被除數D＝D1D2…Dy(x不必等於y)精度p(正整數)。初始化i＝1商值B1＝0，2k個可能試商B′ui＝u(u為0、1、2、…、2k-1)。i位除數和i-1位商、一位(第i位)試商B′ui送入2k個乘法器並行相乘A1…Ai＊B1…Bi-1B′ui得乘積C＝C1C2…Ci-1C′ui，2k個餘數R′ui＝D1D2…Di-C1C2…Ci-1C′ui。若R′ui ≥0，找出最小的R′ui所用的試商--u(min)，令商Bi＝試商B′ui＝u(min)及i+1--＞i。取下一個Ai(若i＝＞n，Ai＝″0″)和新試商B′ui＝u(0、1、2、…、2k-1)。計算A1…Ai＊B1…Bi-1B′ui；若不存在R′ui的正數，則(B1…Bi-1)-1--＞B1…Bi-1，計算A1…Ai＊B1…Bi-1B′ui，直到精度p為止。
如圖7所示本發明的除法裝置將除數寄存器RA72和商寄存器RB73、w(w＝2k)個試商發生器IN75、IN76、IN77的輸出端連到w個乘法器MUL78、MUL79、MUL80的被乘數和乘數輸入端，w個乘法器MUL78、MUL79、MUL80的乘積輸出端和被除數寄存器RD89的輸出端分別連到w個減法器ST81、ST82、ST83的被減數和減數輸入端。減法器ST81、ST82、ST83的差輸出端連到一w端比較器MIN85的輸入端。它的輸出一個連到餘數寄存器RR84，另一個連到商寄存器RB73，第三個連到一計數器ICONT86的輸入端，第四個連到RA72、RB73的控制端。後者的輸出連到比較器PCOM88的一個輸入，精度寄存器RP87連到它的另一個輸入端。比較器PCOM88的一個輸出端連到除數寄存器RA72和商寄存器RB73的控制輸入端。商寄存器RB73輸出又連到減1器ST174輸入端。它的輸出連到商寄存器RB73數據輸入端。
本發明的除法裝置，將上述圖2的乘法器設置2k個，每個乘法器不使用連到移位累加器SA29的接收當前數據高端a＊k比特之處k輸入與非門A28，並且SA29一次輸出所有乘積。寄存器RA72和寄存器RD89存放除數和被除數，所求商B＝B1B2…Bp(p為計算精度)存放商寄存器RB73中，所求餘數R＝R1R2…Rp存餘數寄存器RR84。試商的w個可能值B′ui＝0、1、2、…、2k-1，由w個試商發生器IN75、IN76、IN77產生並隨商寄存器RB73已有商值一同輸w個入乘法器MUL78、MUL79、MUL80的乘數輸入端，其被乘數Ai來自寄存器RA72。假設已求出前i-1(第1個商值為″0″)個商值B1…Bi-1(2≤i≤p)，求第i個商的過程如下每次由寄存器RA72中取出新的一位Ai，與前i-1位除數，w個新試商B′ui結合前i-1位商由w個乘法器MUL78、MUL79、MUL80算出w個乘積C1C2…Ci-1 C′ui＝A1…Ai＊B1…Bi-1B′ui。用被除數D＝D1D2…Di-1Di分別於w個減法器ST81、ST82、ST83減得w個餘數R′ui的集合。經比較器MIN85對R′ui的集合找出其中最小大於或等於零的餘數所對應的u(min)。輸出一成功找到信號到除數寄存器RA72和商寄存器RB73的公共控制輸入端，將此u(min)寫到商寄存器RB73的最低一位。計數器ICONT86對位數參數i計數1次。如果餘數R′ui都小於零，輸出不成功信號到RA72和RB73的公共控制輸入端，將RB73中的前i-1個值B1B2…Bi-1在減1器ST174減1。循環此過程直到比較器PCOM88在達到精度i＝＞p時輸出停止信號到除數寄存器RA72和商寄存器RB73的公共控制輸入端，使它們不再輸出數據。由於乘法器可對任意小於m位並且不必是相等的兩操作數相乘，位數越少時乘法過程短，試商基本不校正，最多一次，因此速度快，商寄存器RB73輸出商B＝B1B2…Bp，餘數寄存器RR84輸出餘數R＝D1…Dn-C1…Cp。
若將除數寄存器RA72亦換成商寄存器RB73的連接，即RA72的輸出連接到試商發生器IN75、IN76、IN77的輸出，輸入連到RB73的輸入，除法時同時對除數、商在減1器ST174中減1，則可進行被除數的開平方運算。
本發明的連乘裝置將上述單乘法器設置多個。第一個乘法的乘積寄存器RC6輸出直接與第二個的被乘數寄存器RA1相連，第二個與第三個按同樣方式，…直到連完。多操作數A、B、C、D…分別存放於第一、二、三、…個乘法器乘數寄存器RB2中。當第一乘積寄存器RC6得到A＊B的最高1位時，即啟動第二個乘以C的最高1位，第一個A＊B＊C的最高位出來即運算A＊B＊C＊D，整個過程為乘法級 運算乘積1A＊B C11C12…C1j…C1m2A＊B＊C C21C22…C2j…C2m3A＊B＊C＊D C31C32…C3j…C3m·……uA＊B＊C＊D＊… Cu1Cu2…Cuj…Cum。流水運算減少數據間的相關度，M級連乘能在(3+a)M拍得出第M級的一位乘積，其後每拍一位。(3+a)M+m-1拍完成每級m位精度，而單乘法需(3+a)M+(m-1)＊M拍，且m與M越大，效率越高。
把本發明的單乘法器的操作數寄存器RA1、RB2的輸入端連接到兩大數寄存器的輸出端。輸入控制邏輯連接到大數寄存器的控制輸入端，單乘法器的乘積寄存器RC6的輸出端連接到第一累加器的輸入端，第一累加器的輸出端連接帶移位功能的第二累加器的輸入端，此移位累加器的接收當前數據的高端a′＊k比特之處輸出連到一n端與非門，後者輸出又反饋到它的控制輸入端。第二累加器的輸出端連接到大數乘積寄存器的輸入端。可將乘法器用於大整數、任意精度的操作數相乘。
將二待乘大整數A，B分為p(p＞n)個n比特A＝A1A2A3…Ap B＝B1B7B3…Bp輸入控制邏輯按規律每次從兩大數寄存器存放A、B中取一對Ai、Bj(0≤i≤n，0≤j≤n)，在單乘法器中執行Ai＊Bj。每次乘積結果於第一累加器按以上規律累加1到p次如下i+j-1取數Ai、Bj累加次數1 A1B1 12 A1B2 A2B1 23 A1B3 A2B2 A3B1 3·… ·n A1Bp A2Bp-1 A3Bp-2 ApB1 p·… ·2n ApBp 1輸出一個2n比特部份積到二級累加器，累加並位移n比特，第一累加器復位零。為得到第一n比特高位積，當位移達到數a′時，與非門判斷第二累加器的第2個n比特高位是否為2n-1，左移n比特，輸出最高n比特積到大數乘積存器；否則累加並左移不輸出。如此循環得出一位位n比特積。設置精度控制單元，可以在第q個(1≤q≤2p)n比特積時終止。結果表示為以2k為基P＝P1P2…Pq＊WzN-q其中Pj為n比特積(1≤j≤q，W＝2k)。這樣便得到任意字長、任意精度的乘法運算。a′的意義是最高n比特輸出延時a′拍(這裡一拍得出n比特乘積)。a′與p的關係p＝16時，a′＝3；當p＝256時，a′＝4。
權利要求
1.一種高速乘法器，其特徵在於乘法器由兩n比特寄存器RA(被乘數)、RB(乘數)、操作數輸入電路、陣列乘法單元、部份積加法CSA樹電路、2n比特寄存器RC(乘積)組成；寄存器RA、RB按每個時鐘節拍由高到低順序輸出到操作數輸入電路，整個乘法過程共進行2m-1次；操作數輸入電路由m個k比特被乘數寄存器、m個k比特乘數寄存器組成，操作數輸入電路按同樣的節拍、順序、數據長度接收RA、RB的數據，將每K比特的被乘數與所有的K比特乘數配對，輸出到陣列整個乘法過程共進行2m-1次，每次分別配對1、2、---、m、---、1對；陣列乘法單元由m個k比特積產生單元、m個高位進位保留加法器CSA、m個低位進位保留加法器CSA、m個進位鎖存器組成，或者由m個k比特直接乘單元組成，陣列乘法單元按同樣的節拍、順序、數據長度將操作數輸入電路的配對數據相乘，生成的比特積項分高位、低位相加，得出1或m個k比特的高、低位部份積送到部份積加法CSA樹，整個乘法過程共進行2m-1次；部分積加法CSA樹電路由一個m端CSA樹、另一個同樣結構的CSA樹、一m+1端CSA加法樹、一個移位累加器、一k端與非門組成，或者由一個m端CSA樹、另一個同樣結構的CSA樹、一m端CSA加法樹、3端CSA加法器、一個移位累加器、一k端與非門組成，或者由一個m端CSA樹、另一同樣結構的CSA樹、兩個加法器、一個移位累加器、一k端與非門組成，部份積加法CSA樹電路按同樣的節拍、順序將陣列乘法單元送來的1-m個k比特高位部份積、低位部份積，或者連同它們之間進位同時相加，輸出最高k比特乘積到寄存器RC，整個乘法過程共進行2m-1次；寄存器RC按同樣節拍、順序接收部份積加法CSA樹送來的高位的k比特乘積，左移k比特後準備下次接收低位的乘積，整個乘法過程共進行2m次；由2m-1個上述單乘法、2m-2個加法器CSA、2m-2個部份和鎖存器、2m-3個進位鎖存器、2m-3個與門、2m-1個加法單元組成更高速並行乘法裝置；以該乘法器為基礎組成的除法器由兩個操作數寄存器(被除數、除數)、兩個結果寄存器(商、餘數)、一個輔助寄存器、w(w＝2k，下同)個乘法器、w個試商發生器、w個減法器、兩2k端比較器、一計數器、一比較器、一減1器組成。
2.根據權利要求1所述的高速乘法器，其特徵在於寄存器RA[1]的輸出按每組k比特由高到低順序連接到操作數輸入電路[3]中m個被乘數寄存器Ra[7]、[9]、[11]，寄存器RB[2]的輸出連接到寄存器Rb[8]的輸入，後者又連到寄存器Rb[10]的輸入端，直到連完m個寄存器Rb[12]，按時鐘節拍由高到低順序每次輸出k比特數到陣列乘法單元MUUINT[4]的每個由n2個與門組成的m個k比特積產生單元MA[13]、[14]、[15]，一拍執行n2個乘，輸出連到m個高位CSA[16]、[17]、[18]用以產生高位部份積，再連到m個低位CSA[19]、[20]、[21]用以產生低位部份積，高位CSA的輸出連到m端CSA樹HCSA[25]，低位CSA連到另一同樣結構的CSA樹LCSA[27]，分別下一拍內相加，低位CSA[19]、[20]、[21]的進位連到m個進位鎖存器CL[22]、[23]、[24]，後者輸出與LCSA[27]輸出共連到m+1端CSA加法器CCSA[26]輸入，其值與LCSA[27]的輸出同一拍於CCSA[26]相加，CCSA[26]與CSA樹HCSA[25]連到移位累加器SA[29]兩操作數端，在下一拍先後與移位累加器SA[45]的值累加並左移k比特，SA[29]的接收當前數據位的高端a＊k，比特之處連到k輸入與非門A[28]，常數a受操作數位數m限制，當m＝＜16時，a＝3，當m＝＜256時，a＝4，與非門A[28]檢測輸出條件，其輸出又反饋到SA[29]的控制端，SA[29]輸出連到帶左移功能的乘積寄存器RC[6]，滿足輸出條件時，RC[6]左移k比特接收1位積，否則RC[6]左移k比特不接收乘積。
3.根據權利要求1或2所述的高速乘法器，其特徵在於部分積加法CSA樹電路[3]是m端高CSA樹HCSA[25]的和輸出與低CSA樹LCSA[27]的進位輸出及CSA加法器CCSA[30]的輸出連到CSA加法器CSA[31]的三個輸入端，高、低位部份積之和，進位鎖存器CL[22]、[23]、[24]的值之和分別由高位CSA樹HCAS[25]、低位CSA樹LCSA[27]、進位CSA樹CCSA[30]於同一拍內於得到，HCSA[25]的進位輸出與CCSA[31]的進位輸出連到加法器ADD[32]的兩操作數端，其輸出與CSA[31]、LCSA[27]的和輸出共同連到移位累加器SA[34]的操作數端，HCSA[25]的和、LCSA[27]的進位、CCSA[30]的和於CSA加法器CSA[31]內相加，進位與HCAS25的進位在同一拍於加法器ADD[32]相加，其輸出、CSA[31]與LCSA[27]的和輸出於下一拍與SA[34]的值累加，SA[34]接收當前數據位的高端a＊k比特之處連到k輸入與非門A[33]，檢測輸由條件，其輸出反饋到它的控制輸入端，SA[34]連到連到帶左移功能的乘積寄存器RC[6]，滿足輸出條件時，RC[6]左移k比特後接收1位積。
4.根據權利要求1或2所述的高速乘法器，其特徵在於操作數輸入電路[3]將兩個相乘的n比特操作數通過兩個寄存器RA[1]，RB[2]並行送入k比特陣列乘法單元MUL[35]、[36]、[37]的兩輸入端，其高位積輸出連到m端CSA樹CSA-H[38]，k低位積連到另一個同樣結構的CSA樹CSA-L[39]，一拍執行m個kxk，其高、低位積的和分別由高位CSA-H[38]和低位CSA-L[39]得到，CSA-H[38]和輸出與CSA-L[39]進位輸出連到加法器AD-1[40]的兩輸入端，後者與CSA-H[38]進位輸出連到加法器AD-2[41]的兩輸入端，CSA-H[38]的和與低位CSA-L[39]的進位在一拍內於加法器AD-1[40]相加，相加的進位和CSA-H[38]的進位在同一拍於加法器AD-2[41]相加，CSA-L[39]、AD-1[40]的和輸出與AD-2[41]的輸出共連到移位累加器SA[34]，其輸出連到帶左移功能的乘積寄存器RC[6]。
5.根據權利要求3所述的高速乘法器，其特徵在於更高速並行乘法裝置將上述乘法器重複設置2m-1個，其中各內含的陣列乘法單元數不等，分別為1、2、…、m、m-1、…、1，兩操作數A、B各取k比特通過兩寄存器RA[1]、RB[2]送入不同單元一步執行m2個Ai＊Bj，產生最低一位積，將部分積加法CSA樹電路之二所組成的乘法器MU[42]自ADD[32]、CSA[31]、LCSA[27]引出的低位k比特、3個乘法器MU[43]、[46]、[47]中自ADD[32]、CSA[31]、LCSA[27]引出二個k比特輸出以及2m-5個乘法器MU[44]、[45]中自ADD[32]、CSA[31]、LCSA[27]引出的三個k比特輸出連到CSA加法器CSA[51]、[52]的二個、CSA[48]、[49]、[50]的三個輸入端，進行一次k比特加法，產生出次低一位積，將2m-3個CSA加法器CSA[48]、[49]、[50]、[51]和輸出連接到2m-3個部份和鎖存器SL[53]、[54]、[55]、[56]輸入，CSA加法器CSA[49]、[50]、[51]、[52]的進位連接到2m-3個進位鎖存器CL[57]、[58]、[59]、[60]的輸入端，部份和鎖存器SL[53]、[54]、[55]、[56]的輸出端連接到2m-3個加法單元AD[67]、[68]、[69]、[70]的被加數端，進位鎖存器CL[57]、[58]、[59]、[60]的輸出端一方面連接到2m-3個加法單元AD[67]、[68]、[69]、[70]加數端，一方面連接到2m-3個判斷與門[61]、[62]、[63]、[64]的輸入端。判斷與門[62]、[63]、[64]的輸出又連到高一級的部份和鎖存器SL[53]、[54]、[55]、[71]和進位鎖存器CL[57]、[58]、[59]的控制輸入，2m-3個CSA加法器CSA[48]、[49]、[50]、[51]的和輸出又連接到2m-3個判斷與門[61]、[62]、[63]、[64]另外的輸入，判斷與門[61]、[62]、[63]、[64]根據個部份和鎖存器SL[53]、[54]、[55]、[56]及進位鎖存器CL[57]、[58]、[59]、[60]的值是否全″1″，決定是否向高一級進位，2m-3個加法單元AD[67]、[68]、[69]、[70]再進行一次k比特加法，產生除最高一位、最低二位積以外的所有2m-3位乘積，乘法器MU[42]高位輸出k比特連到加法器AD[65]的被加數端，其加數端來自CSA加法器CSA[48]的進位輸出端，AD[65]的和輸出連到鎖存器SL[71]的輸入端，SL[71]輸出連到加法器AD[66]的被加數端，加數來自判斷與門[61]的輸出，如果產生所有低位積的過程中對最高位有進位，AD[66]再次加，得出最高位積。
6.根據權利要求2所述的高速乘法器，其特徵在於將乘法器設置2k個組成除法器，除數寄存器RA[72]和商寄存器RB[73]、2k個試商發生器IN[75]、[76]、[77]產生0--2k-1的2k個試商值，它們的輸出分別連接到2k個乘法器MUL[78]、[79]、[80]的被乘數和乘數端，RB[73]已有商值同2k個試商值輸入2k個乘法器MUL[78]、[79]、[80]，執行2k個乘法，乘法器MUL[78]、[79]、[80]的乘積輸出端和被除數寄存器RD[89]的輸出端分別連到2k個減法器ST[81]、[82]、[83]的被減數和減數端，減得2k個餘數，減法器ST[81]、[82]、[83]差輸出連到2k端比較器MIN[85]的輸入，比較器MIN[85]從2k個餘數中找出最小一個大於或等於零的餘數及它對應的試商值，輸出餘數到與其相連的餘數寄存器RR[84]，輸出一信號和最小大於或等於零餘數對應的試商值到與之相連的除數寄存器RA[72]和商寄存器RB[73]的公共控制輸入端，除數寄存器RA[72]取新一位除數和將試商值存進商寄存器RB[73]，當全部餘數皆小零，商寄存器RB[73]中的值在與之相連的減1器ST1[74]中減1再寫回RB[73]，除數寄存器RA[72]不取新值，比較器MIN[85]又連到計數器ICONT[86]，對找到正或零的餘數次數計數，ICONT[86]連到比較器PCOM[88]的一個輸入，精度寄存器RP[87]連到它的另一個輸入端，比較器PCOM[88]的一個輸出端連到除數寄存器RA[72]和商寄存器RB[73]的公共控制輸入端，當進行到精度位時輸出一停止信號；將除數寄存器RA[72]亦換成商寄存器RB[73]的連接，即RA[72]的輸出連接到試商發生器IN[75]、[76]、IN[77]輸出，輸入連到RB[73]的輸入，除法時同時對除數、商在減1器ST1[74]中減1，則可進行被除數的開平方運算。
7.根據權利要求1所述的高速乘法器，其特徵在於將單乘法器串行設置多個，第一個乘法的乘積寄存器RC[6]輸出直接與第二個的被乘數寄存器RA[1]相連，第二個與第三個按同樣方式，…直到連完，多操作數A、B、C、D…分別存放於第一、二、三、…個乘法器的乘數寄存器RB[2]中，當第一乘積寄存器RC[6]得到A＊B的最高1位時，即啟動第二個乘以C的最高1位，第一個A＊B＊C的最高位出來即運算A＊B＊C＊D，整個過程為乘法級 運算 乘積1A＊B C11C12…C1j…C1m2A＊B＊C C21C22…C2j…C2m3A＊B＊C＊D C31C32…C3j…C3m· … …uA＊B＊C＊D＊… Cu1Cu2…Cuj…Cum。
8.根據權利要求1所述的高速乘法器，其特徵在於單乘法器的操作數寄存器RA[1]、RB[2]的輸入端連接到兩大數寄存器的輸出端，輸入控制邏輯連接到大數寄存器的控制輸入端，單乘法器的乘積寄存器RC[6]的輸出連到第一累加器的輸入端，第一累加器的輸出端連接到帶移位功能的第二累加器的輸入端，此移位累加器的接收當前數據的高端a′＊k比特之處輸出連到一n端與非門，後者輸出又反饋到它的控制輸入端，第二累加器的輸出端連接到大數乘積寄存器的輸入端，可將乘法器用於大整數、任意精度的操作數相乘。
全文摘要
一種高速乘法器把n比特整數相乘化為m個k比特乘法單元並行執行，流水每次從高位到低位得出k比特乘積。乘法速度快，可處理大整數，實現浮點功能並能得到任意精度結果。使用單乘法器構成的大規模多並行乘法裝置，並行一次執行m
文檔編號G06F7/52GK1155117SQ96100319
公開日1997年7月23日 申請日期1996年1月19日 優先權日1996年1月19日
發明者張胤微 申請人:張胤微, 狄宗楷