關(guān)于除法電路

　　除法，這個(gè)小學(xué)4年紀(jì)就開始學(xué)習(xí)和使用的方法卻一直是我這個(gè)ASIC工程師心中的痛。我一直在思考如何能找到一個(gè)簡(jiǎn)單(硬件資源少)而快捷(時(shí)鐘排數(shù)少)的通用除法電路。

　　其實(shí)簡(jiǎn)單的說(shuō)除法可以用迭代的減法來(lái)實(shí)現(xiàn)，但是對(duì)于硬件，這恐怕要花很多時(shí)間。我也一直沒有找到實(shí)現(xiàn)任意除法的好方法。但是對(duì)于某些除數(shù)固定的除法還是有一些辦法的。

　　1)最容易想到的就是ROM查找表，但是ROM畢竟不是我們的目標(biāo)，雖然ROM有時(shí)是不錯(cuò)的方法。

　　2)我開始仔細(xì)考慮這個(gè)問(wèn)題是在做264解碼時(shí)必須要處理QP的問(wèn)題。這是一個(gè)除以6的計(jì)算，由于被除數(shù)不會(huì)大于52(6bit)，所以我簡(jiǎn)化了一個(gè)組合邏輯來(lái)實(shí)現(xiàn)。代碼如下：

　　always@(idata)

　　begin

　　case(idata[5:3])

　　3'b000: begin

　　oquotient[3:1] = 3'b000;

　　if (idata[2:1]==2'b11)

　　begin

　　oquotient[0] = 1'b1;

　　end

　　else

　　begin

　　oquotient[0] = 1'b0;

　　end

　　end

　　3'b001: begin

　　oquotient[3:2] = 2'b00;

　　if (idata[2]==1'b1)

　　begin

　　oquotient[1:0] = 2'b10;

　　end

　　else

　　begin

　　oquotient[1:0] = 2'b01;

　　end

　　end

　　3'b010: begin

　　oquotient[3:1] = 3'b001;

　　if (idata[2:1]!=2'b00)

　　begin

　　oquotient[0] = 1'b1;

　　end

　　else

　　begin

　　oquotient[0] = 1'b0;

　　end

　　end

　　3'b011: begin

　　oquotient[3:1] = 3'b010;

　　if (idata[2:1]==2'b11)

　　begin

　　oquotient[0] = 1'b1;

　　end

　　else

　　begin

　　oquotient[0] = 1'b0;

　　end

　　end

　　3'b100: begin

　　oquotient[3:2] = 2'b01;

　　if (idata[2]==1'b1)

　　begin

　　oquotient[1:0] = 2'b10;

　　end

　　else

　　begin

　　oquotient[1:0] = 2'b01;

　　end

　　end

　　3'b101: begin

　　oquotient[3:1] = 3'b011;

　　if (idata[2:1]!=2'b00)

　　begin

　　oquotient[0] = 1'b1;

　　end

　　else

　　begin

　　oquotient[0] = 1'b0;

　　end

　　end

　　3'b110: begin

　　oquotient[3:1] = 3'b100;

　　if (idata[2:1]==2'b11)

　　begin

　　oquotient[0] = 1'b1;

　　end

　　else

　　begin

　　oquotient[0] = 1'b0;

　　end

　　end

　　3'b111: begin

　　oquotient[3:2] = 2'b10;

　　if (idata[2]==1'b1)

　　begin

　　oquotient[1:0] = 2'b10;

　　end

　　else

　　begin

　　oquotient[1:0] = 2'b01;

　　end

　　end

　　default: oquotient[3:0] = 4'd0;

　　endcase

　　end

　　//always@(idata)

　　//begin

　　// case(idata[3:1])

　　// 3'b000: rem_temp[1:0] = 2'b00;

　　// 3'b001: rem_temp[1:0] = 2'b01;

　　// 3'b010: rem_temp[1:0] = 2'b10;

　　// 3'b011: rem_temp[1:0] = 2'b00;

　　// 3'b100: rem_temp[1:0] = 2'b01;

　　// 3'b101: rem_temp[1:0] = 2'b10;

　　// 3'b110: rem_temp[1:0] = 2'b00;

　　// 3'b111: rem_temp[1:0] = 2'b01;

　　// default:rem_temp[1:0] = 2'b00;

　　// endcase

　　//end

　　//

　　//always@(idataor rem_temp)

　　//begin

　　// oremainder[0] = idata[0];

　　// case(idata[5:4])

　　// 2'b00,2'b11: oremainder[2:1] = rem_temp[1:0];

　　// 2'b01: oremainder[2:1] = {(~(rem_temp[1] | rem_temp[0])),rem_temp[1]};

　　// 2'b10: oremainder[2:1] = {rem_temp[0],(~(rem_temp[1] | rem_temp[0]))};

　　// default: oremainder[2:1] = rem_temp[1:0];

　　// endcase

　　//end

　　可見這個(gè)邏輯并不是很大，求商的邏輯不過(guò)是一個(gè)3bit的case里面套一級(jí)選擇(if)，F(xiàn)PGA里不過(guò)就是一個(gè)ALU。時(shí)序也很好，百兆的鐘都沒有問(wèn)題。我由此想到了，對(duì)于除數(shù)固定，被除數(shù)有一定范圍限制的除法，還是可以用一定簡(jiǎn)化了邏輯實(shí)現(xiàn)的。

　　3)以下我們討論的除法就由此先做一個(gè)前提的約束：被除數(shù)是8bit，除數(shù)我們將分別討論3、5、7、11等質(zhì)數(shù)的情況，其它的和數(shù)的除法可以分解成質(zhì)數(shù)。

　　4) 除數(shù)為3(二進(jìn)制2‘b11)

　　我最早的想法其實(shí)很簡(jiǎn)單，除以3是很困難的，但是除以4對(duì)于硬件確實(shí)非常簡(jiǎn)單的。所以也許可以通過(guò)對(duì)1/4進(jìn)行一些調(diào)整來(lái)達(dá)到1/3的目的。這顯然是要在1/4上加一點(diǎn)什么，加什么呢?我突然想到了無(wú)窮級(jí)數(shù)：

　　1/4 1/16 1/64 .........

　　其無(wú)窮級(jí)數(shù)求和和剛好是1/3。這似乎就簡(jiǎn)單了。不就是1/4 +1/16 +1/64 + .........

　　有一件事情是可能的，我們不能求無(wú)窮的加和，但是如果我們只要整數(shù)位，那也許就不需要無(wú)窮的加完。

　　temp[14：0] = {number[7:0],6'd0} + {number[7:0],4'd0} + {number[7:0],2'd0} + number[7:0];

　　result1[7:0] = temp[14:8] + ((number[7]==1'b1 && number[6:0]!=7'd0)? temp[7] : temp[7]&temp[6]);

　　number是8bit被除數(shù)，temp是number若干(這里這用了前4個(gè))移位值的和，但是我們明白，這是不精確的，所以對(duì)此和進(jìn)行一些調(diào)整。調(diào)整的方向一定是加一點(diǎn)什么(因?yàn)槲覀兩偌恿撕芏鄶?shù))，result1就是這個(gè)調(diào)整的邏輯。

　　從整體上看看這個(gè)邏輯：4個(gè)14位數(shù)的加法，一個(gè)選擇邏輯和單bit加。邏輯不算太小(14bit加法電路還是不小的)，但是也不算太大(畢竟就是4個(gè)加法)。時(shí)序由加法電路來(lái)限制，綜合的好應(yīng)該到百兆是沒有問(wèn)題的。

　　5)除數(shù)為5(3'b101)

　　1/5顯然和1/4比較近。我們?nèi)匀豢梢员容^方便的寫出這個(gè)無(wú)窮級(jí)數(shù)來(lái)：

　　1 - 1/4 + 1/16 - 1/64 ...........

　　這個(gè)的和是4/5不是1/5，但是再除個(gè)4就好了(這很方便的)。

　　temp[13:0]={number[7:0],6'd0} - {number[7:0],4'd0} + {number[7:0],2'd0} - number[7:0] + number[7:2] - number[7:4];

　　result1[7:0] = temp[13:6] + temp[5];

　　result2[5:0] = result1[7:2];

　　temp是number的6個(gè)移位值的和，result1是調(diào)整后的值，result2是result/4的商。這個(gè)邏輯怎么要加6個(gè)值的和呢?其實(shí)就是近似問(wèn)題，如果加的個(gè)數(shù)少，那么后面那個(gè)調(diào)整電路就會(huì)復(fù)雜些。

　　6)除數(shù)為7(3'b111)

　　這個(gè)和1/3其實(shí)是類似的，我就不贅述了。

　　7)除數(shù)為11(4'b1011)

　　這個(gè)有點(diǎn)煩，和11近的2^n是8或16，這個(gè)級(jí)數(shù)似乎不好找。但是我一覺醒來(lái)突然明白了一個(gè)事情：任何一個(gè)小數(shù)都是可以化為2進(jìn)制表示的，而其2進(jìn)制表示其實(shí)就是一個(gè)2^n的數(shù)列的和，只不過(guò)是換了一種形式吧了。

　　于是1/11就是0.0001011101 | 0001011101 | 0001011101 | ...........

　　temp[14:0] = {number[7:0],6'd0} + {number[7:0],4'd0} + {number[7:0],3'd0} + {number[7:0],2'd0} + number[7:0] + number[7:4];

　　result1[7:0] = temp[14:10] + (temp[9]&temp[8]&temp[7]&temp[6]);

　　精度仍然只取了前6個(gè)有效的(是1)的數(shù)，然后在result1上做了一些補(bǔ)足的調(diào)整。

　　8)總結(jié)：其實(shí)到這里我們就已經(jīng)清除了一件事----所有除數(shù)固定的除法都可以用上述確定的過(guò)程來(lái)實(shí)現(xiàn)。具體說(shuō)就是：第一，將除數(shù)n變成乘以1/n，然后用2進(jìn)制來(lái)表示這個(gè)1/n。第二，根據(jù)被除數(shù)的位數(shù)來(lái)選取合適的1/n的有效位數(shù)。第三，再根據(jù)具體的結(jié)果做一些調(diào)整。

　　1/N取多少有效位合適，取決與被除數(shù)的范圍(被除數(shù)較大，就要多取幾位)、邏輯大小的控制(加法越多，可能你的門數(shù)和時(shí)序多要付出代價(jià))、一級(jí)最后那個(gè)調(diào)整的復(fù)雜程度(總不能太復(fù)雜吧)。

　　好了，到這里就先告一段落吧，但是我仍然沒有從根本上真正解決任意除法的問(wèn)題。我心中的通看來(lái)還要持續(xù)。不知有誰(shuí)能最終來(lái)替我排解。