fpga定点除法器verilog 原码.doc

摘要： 對於整數除法中non restoring和restoring的做法感到有興趣。想要作4-bit，8-bit和16-bit兩個實現後的硬體比較。另外，還有non restoring的餘數correction，及除數為零時的處理。介紹： 下面圖示我在這篇報告的一些定義：X = qd + rem被除數商除數餘數|rem| |d| ulpulp的值是決定商的每個bit值。 另外，non restoring和restoring的除法演算法可以從兩方面著手： (1) Position of the decimal point (2) Sign of operands接下來我將分別介紹一下這兩個除法演算法。Restoring Division Algorithm把x放入register A, d 放在register B, 0在register P,然後開始作n次除法的步驟(n 是商的word length)。每個步驟將包涵：1. 向左平移暫存器 (P,A) 一個bit。2. 暫存器P減掉暫存器B, 並把結果再存回暫存器P。3. 如果結果是負的, 設the low-order bit of A 為0否則為1。4. 結果是負的確定之後, 把P加回B以回復舊的值P。Restoring Division Example：PAOperation00000111014(1110)除於3(11)。 B register always contains 001100001110step 1(1): 平移-00011step 1(2): 減法-000101100step 1(3): P是負的, 設商bit為0000011100step 1(4): 回復00011100step 2(1): 平移-00011step 2(2): 減法000001001step 2(3): P是正的, 設商bit為100001001step 3(1): 平移-00011step 3(2): 減法-000100010step 3(3): P是負的, 設商bit為0000010010step 3(4): 回復00010010step 4(1i): 平移-00011step 4(2): 減法-000010100step 4(3): P是負的, 設商bit為0000100100step 4(4): 回復Non-Restoring Division Algorithm是由restoring變化過來。在觀察restoring algorithm中，碰到餘數是負的時候不作restoring而是繼續平移一個bit下去在作處理。這樣在restoring每一級所必須的加法器將可省去。下面是詳細的步驟和架構圖：PAshiftBSet bit circuitAfter n cycles, A will contain the quotient, P will contain the remainder(Divider)(Remainder)(Quotient)主要的步驟與restoring一模一樣在處理P時才有不同：如果P是負的： a. 向左平移(P,A)這兩個暫存器一個bit。 b. 加B到P。如果P是正的： a. 向左平移(P,A)這兩個暫存器一個bit。 b. 把P減B 商的處理：如果P是負的設LSB(A)為0反之設LSB(A) to 1 Non-Restoring Division ExamplePAoperation00000111014(1110)除於3(11)。 B register always contains 001100001110step 1: 向左平移(P是正的)+00011step 1: P減B (P是正的)111101100step 1: P是負的, 所以設商bit為011101100step 2: 向左平移(P是負的)+00011step 2: 加B到P000001001step 2: P是正的所以設商bit為100001001step 3: 向左平移(P是正的)+11101step 3: P減B (P是正的)111100010step 3: P是負的所以設商bit為011100010step 4: 向左平移(P是負的)+00011step 4: 加B到P111110100step 4: P是負的所以設商bit為0+00111於數是負的所以得作correction00010Method Negative remainderNeed restoreNeed correctionAdd/subtract at each stepRestoring NoYes No Yes Non Restoring Yes No Yes Yes 以下RD將代表Restoring Divider，NRD代表Non-restoring Divider。實作： 我的verilog code主要寫成behavior來實現的。在處理除數為零的方面我是用一個flag來區分結果是否正確，請看粗體部分。Verilog code of Restoring Division：module RD(dividend, divisor, quotient, remainder, zeroflag);parameter size = 16 ; /設定4bit, 8bit or 16bitinput size-1:0dividend;input size-1:0divisor;output size-1:0quotient;output size-1:0remainder;output zeroflag;reg size:0p;reg size-1:0quotient, div, remainder;reg sign;integer i;assign zeroflag = divisor=16h0000 ? 1b1 : 1b0; /zero detectionalways(dividend or divisor)begin quotient = dividend; div = divisor; p = 16h00,1b0; sign = 1b0; for(i=0;isize;i=i+1) begin p = psize-1:0, quotientsize-1; quotient = quotientsize-2:0, 1b0; p = p + 1b0,div + 1b1; case(psize) 1b0: begin quotient0 = 1b1; end 1b1: begin p = p + div; quotient0 = 1b0; end endcase end remainder = psize-1:0;endendmodule在non-restoring部分，最終餘數為負我將需要一個correction來作更正以得到正確的答案。粗體部分為我correction的機制。Verilog code of Non-Restoring Division：module NRD(dividend, divisor, quotient, remainder, zeroflag);parameter size = 16 ; /設定4bit, 8bit or 16bitinput size-1:0dividend;input size-1:0divisor;output size-1:0quotient;output size-1:0remainder;output zeroflag;reg size:0p;reg size-1:0quotient, div, remainder;reg sign;integer i;assign zeroflag = divisor=16h0000 ? 1b1 : 1b0; /zero detectionalways(dividend or divisor)begin quotient = dividend; div = divisor; p = 16h0000,1b0; sign = 1b0; for(i=0;isize;i=i+1) begin p = psize-1:0, quotientsize-1; quotient = quotientsize-2:0, 1b0; if(sign = 1b0) p = p + 1b0,div + 1b1; else p = p + 1b0,div; case(psize) 1b0: begin quotient0 = 1b1; sign = 1b0; end 1b1: begin quotient0 = 1b0; sign = 1b1; end endcase end/correction if(psize = 1b0) remainder = psize-1:0; else begin p = p + 1b0,div; remainder = psize-1:0; end/end of correctionendendmodule結果比較：4-bitareatimingRD26311.72 nsNRD19411.94 nsReduction ratio26.%-1.88%8-bitareatimingRD100035.20 nsNRD64635.28 nsReduction ratio35.4%-0.23%16-bitareatimingRD3980122.42 nsNRD2572129.26 nsReduction ratio35.4%-5.6%AreaTiming由上面的數據跟圖表顯示出，NRD在速度上雖然有比RD還要緩慢的趨勢。在16-bit的除法器更可看出比原來增加5.6%（RD：122.42 ns，NRD：129.26 ns）。不過area方面卻省了35.4%。這是一項很大的優點。其他4-bit與8-bit在速度方面不會差很多（在2%以下），但是area卻分別