我想在 Xilinx 設備上創建一個將任何 8 位數除以 3 的原理圖，以防萬一。
例如，硬體接受兩個輸入 (111101) 和 (11) 并回傳兩個數字的除法，即 010100。
我不需要擔心余數——只需要商
uj5u.com熱心網友回復：
至少有兩種方法適合硬體實作；
- 倒數乘法
倒數乘法是從 計算的(x*K)>>N，在這種情況下K可能是ceil(512/3) = 171 0b10101011 = 9 * 19, N = 9。因式分解有幫助，因為一個數字很容易同時乘以 9 = 0b1001 和 19 = 0b10011。乘以 9 是通過一次加法和一次自由移位完成的，乘以 19 是通過兩次自由移位（接線）和兩次加法完成的。總成本 == 3 個附加項。
- (非)-恢復師
就像在小學學到的那樣，長除法可以很容易地轉換為 HW 電路。
00101001 = 41
11 -> trial "subtraction" fails, result bit = 0
00101001
11 -> trial subtraction fails, result bit = 0
00101001
11 -> trial subtraction fails = 0
00101001 -> pass = 1
(011)
------
10001 -> pass
11
-----
101 -> fail
11
-----
101 -> pass
11
Result = b0001101 = 13
不需要計算實際的試驗減法，因為除數是一個常數。取而代之的是一個快速的表達Passed = top|(mid & bottom)。同樣，我們可以為每個階段的三個輸出形成邏輯運算式。
從top = 0, mid = input:7,開始bot = input:6，需要迭代 7 個位置，從top, mid,計算 R=Result,Top,Mid bot。
The logical expressions for each stage are then
top mid bot R T M B
--------------------------
0 0 0 0 0 0 R = t mb
0 0 1 0 0 1 T = ~bm tb
0 1 0 0 1 0 M = ~bt ~t~mb
0 1 1 1 0 0 B = next bit from input
1 0 0 1 0 1
1 0 1 1 1 0
1 1 0 x x x
1 1 1 x x x x = don't care as impossible
- 使用 16 位 LUTS 完成的 256x7 LUT
也可以使用 16 位 LUT 的層次結構來實作 1x256 位 LUT。32 位 LUT = 多路復用（位 [4]、LUT0（位 [3:0]）、LUT1（位 [3:0]））；單個 256 項 LUT 將需要 16 個 16 位 LUT 和每位 15 個多路復用器，或者沒有高級構建塊的 1680 個 LogicElements。這假設每個 LE 可以實作任意 16 位 LUT（4 個輸入，1 個輸出），這在 90 年代后期就已經習慣了。多路復用器適合這些限制，因為它只是一個自定義 3 輸入邏輯功能，而 16 位 LUT 是一個自定義 4 輸入邏輯功能。
- 使用記憶體的 256x7 位 LUT
一些 FPGA 確實有專門的 LUT 部分，在這些情況下，256x7 位 LUT 可能是一個很好的解決方案。最小門數將是 7 個暫存器（ 記憶體），但我希望記憶體訪問會引入大量元素作為驅動程式。
- 通過 Fuz 拆分 LUT
在區域方面，這與長除法相當。它的延遲較小，但扇出較大。
比較
使用典型 FPGA 單元的面積估計類似于使用加法方法的 9 7 13 單元，使用長除法可能是 7x3。
--------------- -----------------
| Method | Area |
--------------- -----------------
| 1. reciprocal | ~30 |
| 2. division | 21 |
| 3. 16-bit LUT | 1680 |
| 4. 256x8-LUT | 7-100 Memory |
| 5. Fuz 2xLUT | 22 |
--------------- -----------------
免責宣告：我預計在過去的 20 年中，邏輯合成器會取得一些進步——人們可能會使用 System-C 生成一個好的分頻器。甚至有可能手動布置邏輯單元和連接——在 Altera 中我沒有這樣的運氣，邏輯、布局和布線是從 Verilog 或 VHDL 自動合成的，通常會產生令人尷尬的結果。
uj5u.com熱心網友回復：
一個好的折衷辦法可能是使用一堆查找表。偽代碼如下所示：
# look up table for the high part
# returns 7 bit quotient, 2 bit remainder
# in case you have 8 bit luts, you can save
# one LUT by replacing the high bit with x[2]&x[3]
lut_hi(x[4]) =
0000 => 0000000:00
0001 => 0000101:01
0010 => 0001010:10
0011 => 0010000:00
0100 => 0010101:01
0101 => 0011010:10
0110 => 0100000:00
0111 => 0100101:01
1000 => 0101010:10
1001 => 0110000:00
1010 => 0110101:01
1011 => 0111010:10
1100 => 1000000:00
1101 => 1000101:01
1110 => 1001010:10
1111 => 1010000:00
# look up table for the low part
# returns 3 bit quotient, 2 bit remainder
# you can once again save a bit by replacing
# the high bit with x[2]&x[3]
lut_lo(x[4]) =
0000 => 000:00
0001 => 000:01
0010 => 000:10
0011 => 001:00
0100 => 001:01
0101 => 001:10
0110 => 010:00
0111 => 010:01
1000 => 010:10
1001 => 011:00
1010 => 011:01
1011 => 011:10
1100 => 100:00
1101 => 100:01
1110 => 100:10
1111 => 101:00
# combine two remainders into
remainders(a[2], b[2]) =
return a[1]&b[1] | (a[0]|b[0])&(a[1]|b[1])
# divide by 3: look up the two halves, sum them, apply carry
div3(x[8]) =
q_lo:r_lo = lut_lo(x[0:3])
q_hi:r_hi = lut_hi(x[7:4])
return q_lo q_hi remainders(r_lo, r_hi)
這段代碼的作業原理是將數字分成兩個半位元組，將每個半位元組除以 3，然后將商相加。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/472515.html
下一篇：我應該如何正確學習GNU匯編？