逐位元除法與開根號Bit-by-Bit Division and Square Root

1核心想法：一位一位試The idea: try one bit at a time

回想十進位的直式除法，算 157 ÷ 12：

Recall decimal long division, for 157 ÷ 12:

1. 看 15：12 放得進去 1 次，商寫 1，餘 3。Look at 15: 12 goes in once. Write 1, remainder 3.
2. 把 7 拉下來，變成 37：12 放得進去 3 次，商寫 3，餘 1。Bring down 7 to make 37: 12 goes in 3 times. Write 3, remainder 1.
3. 答案：商 13，餘 1。Answer: quotient 13, remainder 1.

每一步做的事都一樣：拉下一位 → 試試看放不放得進去 → 決定這一位答案 → 更新餘數。

Every step is the same: bring down a digit → see whether the divisor fits → decide this digit → update the remainder.

換成二進位更簡單，因為每一位答案只可能是 0 或 1。只要比大小，夠減就填 1 並減掉，不夠就填 0。硬體只需要一個比較器和一個減法器，每個時脈重複用一次。

Binary is even simpler, because each answer bit can only be 0 or 1. Just compare: if it fits, write 1 and subtract; if not, write 0. The hardware needs one comparator and one subtractor, reused once per clock.

2除法器 div_seqThe divider div_seq

算 quotient = dividend ÷ divisor。有三個參數：

It computes quotient = dividend ÷ divisor, with three parameters:

暫存器各自的角色What each register does

最關鍵的兩行The two key lines

wire [WD:0] rem_next = {rem[WD-1:0], lo[WQ-1]};  // rem × 2 + next bit  餘數 × 2 + 拉下的那一位
wire        fits     = (rem_next >= {1'b0, d});  // fits → this bit is 1  夠減 → 這位商是 1

{A, B} 是把位元接起來。把餘數左移一位再補上新的一位，等於「乘 2 再加上新位」，就像十進位的「3 拉下 7 變成 37」是 3 × 10 + 7。

{A, B} joins bits together. Shifting the remainder left by one and appending the new bit means "times 2, plus the new bit", just as bringing down 7 after 3 gives 37 = 3 × 10 + 7 in decimal.

每個時脈做的事What happens each clock

lo  <= lo << 1;                                 // next bit to the front  下一位移到最前面
rem <= fits ? rem_next - {1'b0, d} : rem_next;  // subtract if it fits  夠減就減
q   <= {q[WQ-2:0], fits};                       // shift in the new bit  商左移，新位補在右邊
cnt <= cnt - 1'b1;

最後一步要寫 quotient <= {q[WQ-2:0], fits} 而不是 quotient <= q。因為 <= 是非阻塞賦值，同一個時脈裡 q 還是舊的值，要自己把最後一位接上。

On the last step the code writes quotient <= {q[WQ-2:0], fits}, not quotient <= q. <= is a non-blocking assignment, so within the same clock q still holds its old value, and the last bit has to be appended by hand.

走一遍：13 ÷ 3Walk-through: 13 ÷ 3

縮小成 WN = 5、WD = 2、WQ = 3。13 = 01101，上面 2 位 01 當初始餘數，下面 3 位 101 放進 lo。除數 3 = 11。

Scale down to WN = 5, WD = 2, WQ = 3. 13 = 01101: the top 2 bits 01 are the initial remainder and the low 3 bits 101 go into lo. The divisor 3 = 11.

商 = 100 = 4，餘 1。驗算：3 × 4 + 1 = 13。

Quotient = 100 = 4, remainder 1. Check: 3 × 4 + 1 = 13.

時序Timing

start : ‾\____________________________   ← one pulse  給一下 start
busy  : __/‾‾‾‾‾‾‾ WQ clocks ‾‾‾‾‾\_____
done  : _________________________/‾\___  ← one clock; quotient valid  只亮 1 個時脈

3什麼是「初始餘數」What the initial remainder is

開始計算時，電路把被除數切成兩段：

At the start, the circuit splits the dividend in two:

rem <= dividend[WN-1:WQ];   // upper part → starting remainder  上半部 → 一開始的餘數
lo  <= dividend[WQ-1:0];    // lower WQ bits → brought down one by one  下半部 → 一位一位拉下來

為什麼可以這樣？回到 157 ÷ 12。第一步看 1，12 放不進去，商是 0、餘數是 1，這步等於白做。所以可以直接把 1 當成起始餘數，從「拉下 5」開始，只要兩步就得到兩位數的商 13。

Why does that work? Back to 157 ÷ 12. The first step looks at 1: 12 doesn't fit, so the digit is 0 and the remainder is 1. That step does nothing useful. So we can start with 1 as the remainder, begin at "bring down 5", and get the two-digit quotient 13 in two steps.

只要上半部小於除數，那些位置的商一定全是 0，可以整段跳過。這讓 88 位元的被除數只需要 36 步，而不是 88 步。

As long as the upper part is smaller than the divisor, every quotient bit in that range is 0 and the whole range can be skipped. That is how an 88-bit dividend needs only 36 steps instead of 88.

4位元寬度怎麼事先決定Choosing bit widths in advance

WN、WD、WQ 都是 parameter，在合成時就固定了。Quartus 會照這個數字做出那麼多個正反器，電路做好之後就像蓋好的房子，房間數量不能再改。所以設計者必須在寫程式時就用紙筆分析好。

WN, WD and WQ are parameters, fixed at synthesis. Quartus builds exactly that many flip-flops. Once built, the circuit is like a finished house: you can't add rooms. So the designer has to work the widths out on paper before writing the code.

先懂定點數 Qm.fFixed-point numbers, Qm.f

FPGA 常用整數表示小數，約定「最後 f 個位元是小數」。例如 Q2.34 是 2 位整數加 34 位小數，共 36 位元，數值 = 整數值 ÷ 2³⁴。相除時：

FPGAs often store fractions as integers, agreeing that "the last f bits are the fraction". Q2.34 means 2 integer bits plus 34 fraction bits, 36 bits in all, with value = integer ÷ 2³⁴. When dividing:

決定的步驟The steps

1. WD：看除數訊號有幾個位元。WD: count the bits of the divisor signal.
2. WN：看被除數訊號有幾個位元。小數位不夠的話，先左移補足。WN: count the bits of the dividend signal. If it lacks fraction bits, shift it left first.
3. 估答案的最大值：分子取最大、分母取最小，算出最壞情況，決定整數部分要幾位。Bound the answer: take the largest numerator and smallest denominator to get the worst case, which sets the integer bits.
4. WQ = 整數位 + 小數位。WQ = integer bits + fraction bits.

例子：光線打到地面的位置Example: where a light ray hits the ground

要算 z × |Tx| ÷ |Tz|：

We need z × |Tx| ÷ |Tz|:

整數要幾位？這個題目裡 z 最大 6、|Tx| 最大 1、|Tz| 最小 1/3，所以答案最大 6 × 1 ÷ (1/3) = 18。18 < 2⁵ = 32，整數 5 位就夠。

How many integer bits? Here z is at most 6, |Tx| at most 1 and |Tz| at least 1/3, so the answer is at most 6 × 1 ÷ (1/3) = 18. Since 18 < 2⁵ = 32, 5 integer bits are enough.

紙筆推導可能漏掉情況，所以最後還要用模擬把所有可能的輸入跑一遍，和電腦的浮點數答案比對。誤差特別大的地方，通常就是某個寬度估錯、溢位了。

Paper analysis can miss cases, so the last step is to simulate every possible input and compare against a floating-point answer. Where the error is unusually large, some width was usually too small and overflowed.

5開根號器 sqrt_seqThe square-root unit sqrt_seq

算 root = ⌊√radicand⌋（無條件捨去）。輸入 W 位元，輸出 N = W/2 位元。

It computes root = ⌊√radicand⌋ (rounded down). The input has W bits and the output N = W/2 bits.

localparam N = W / 2;

N 同時代表三件事：答案有幾個位元、被開方數分成幾組（每組 2 位）、要算幾個時脈。例如 W = 88 時 N = 44。N 用 localparam 是因為它由 W 算出來，外面不能改，避免兩個數被設成互相矛盾。

N means three things at once: the number of answer bits, the number of 2-bit groups in the radicand, and the number of clocks. With W = 88, N = 44. N is a localparam because it is derived from W and can't be overridden, so the two can never disagree.

為什麼一次拉 2 位？Why two bits at a time?

答案多一位，平方就多兩位。3² = 9（1 位）、30² = 900（3 位）、300² = 90000（5 位）。所以被開方數要兩位兩位一組，每組決定答案的一位。

One more digit in the answer means two more digits in its square: 3² = 9 (1 digit), 30² = 900 (3 digits), 300² = 90000 (5 digits). So the radicand is taken in pairs, and each pair decides one answer bit.

為什麼試減 4q + 1？Why subtract 4q + 1?

目前的答案是 q，下一位可以填 0 或 1：

The answer so far is q. The next bit can be 0 or 1:

• 填 0：新答案是 2q（左移一位 = 乘 2）Append 0: the new answer is 2q (shift left = times 2)
• 填 1：新答案是 2q + 1Append 1: the new answer is 2q + 1

兩者的平方差多少？用乘法公式 (a + b)² = a² + 2ab + b²：

How far apart are their squares? Using (a + b)² = a² + 2ab + b²:

(2q + 1)² − (2q)² = 4q² + 4q + 1 − 4q² = 4q + 1

所以「這一位能不能填 1」就是「剩下的餘數夠不夠再減掉 4q + 1」。而 4q + 1 在二進位裡就是 q 後面接上 01，不需要乘法器：

So "can this bit be 1?" is the same as "is the remainder at least 4q + 1?". In binary, 4q + 1 is just q followed by 01, so no multiplier is needed:

wire [N+1:0] rem_next = {rem[N-1:0], x[W-1:W-2]};  // rem × 4 + next two bits  餘數 × 4 + 拉下的兩位
wire [N+1:0] trial    = {q, 2'b01};                // 4q + 1
wire         fits     = (rem_next >= trial);

餘數為什麼乘 4？因為答案變成 2 倍，平方就變 4 倍，舊餘數也要跟著放大 4 倍。左移兩位就是乘 4。

Why multiply the remainder by 4? Doubling the answer quadruples its square, so the old remainder scales by 4 too. Shifting left by two is multiplying by 4.

走一遍：√45Walk-through: √45

W = 6、N = 3。45 = 101101，分成 10 | 11 | 01，餘數從 0 開始。

W = 6, N = 3. 45 = 101101, split into 10 | 11 | 01. The remainder starts at 0.

root = 110 = 6，餘 9。驗算：6² + 9 = 45。

root = 110 = 6, remainder 9. Check: 6² + 9 = 45.

兩個電路怎麼串在一起How the two circuits connect

在光線折射的計算裡，要把法向量變成長度為 1 的單位向量：

In the light-refraction calculation, the surface normal has to be scaled to a unit vector of length 1:

開根號時小數位數也減半：84 位小數 → 42 位小數。三個除法器同時把 x、y、z 分量除以長度。單位向量的分量一定在 −1 到 1 之間，所以 Q2.34 的 2 位整數就夠，初始餘數的條件也一定成立。

A square root also halves the fraction bits: 84 → 42. Three dividers divide the x, y and z components by the length at the same time. Unit-vector components always lie between −1 and 1, so the 2 integer bits of Q2.34 are enough and the initial-remainder condition always holds.

6自己動手算Try it yourself

輸入數字，看電路每一個時脈在做什麼。這裡用 JavaScript 照著 Verilog 的步驟模擬。

Enter numbers and watch what the circuit does on every clock. This is a JavaScript model that follows the Verilog step by step.