乘法的基本觀念： 5.1 乘法基本概念 被乘數（multiplicand）乘以乘數（multiplier）等於乘積（product）。

Presentation on theme: "乘法的基本觀念： 5.1 乘法基本概念 被乘數（multiplicand）乘以乘數（multiplier）等於乘積（product）。"— Presentation transcript:

1 乘法的基本觀念： 5.1 乘法基本概念 被乘數（multiplicand）乘以乘數（multiplier）等於乘積（product）。
5.1 乘法基本概念 乘法的基本觀念： 被乘數（multiplicand）乘以乘數（multiplier）等於乘積（product）。 乘積： 被乘數連續被左移（left shift）與累加（add-up）起來的結果。

2 5.1 乘法基本概念 二進位無號整數的乘法演算過程：

3 乘法運算的過程： 5.1 乘法基本概念 由乘數的最右邊位元向最左邊位元逐一進行「處理」。 判斷目前處理的位元值是0或1：
5.1 乘法基本概念 乘法運算的過程： 由乘數的最右邊位元向最左邊位元逐一進行「處理」。 判斷目前處理的位元值是0或1： 0 ：不改變部分乘積值，只把被乘數左移一位。 1：將當時的被乘數值加入部分乘積，同時也要繼續將被乘數左移一位。 完成所有被乘數加法之後的結果稱為最終乘積。

4 5.1 乘法基本概念 乘法運算的過程：

5 5.2 基本乘法器設計 基本乘法過程解析 第一版乘法器的演算法 第一版基本乘法器的硬體實現 第二版基本乘法器設計

6 基本乘法過程解析 1001×1011的處理過程 ：

7 基本乘法器演算過程的三個動作及各所需之硬體：
基本乘法過程解析 基本乘法器演算過程的三個動作及各所需之硬體： 累加： 假設乘數與被乘數的長度都是n位元，則可用一個2n位元的加法器來計算部分乘積與被乘數左移值相加的結果。 通常存放在一個2n位元的AC暫存器（Accumulator）中。

8 基本乘法過程解析 被乘數的左移： 雖然一開始被乘數的長度是n，但由於每次左移後都會多一位，所以可用一個2n位元的左移暫存器來存放並左移被乘數。 稱為BR暫存器 。

9 5.2.1 基本乘法過程解析 乘數的右移： 右移出去的位元不再使用，所以僅需一個n位元的右移暫存器。 稱為QR暫存器 。
基本乘法過程解析 乘數的右移： 右移出去的位元不再使用，所以僅需一個n位元的右移暫存器。 稱為QR暫存器 。 額外再一個 位元SC暫存器 ，用來存放仍需處理的位元數。

10 基本乘法器運作重點： 5.2.1 基本乘法過程解析 當Qn位元為1時，則將BR暫存器值加入AC暫存器，再將BR暫存器左移、QR暫存器右移。
基本乘法過程解析 基本乘法器運作重點： 當Qn位元為1時，則將BR暫存器值加入AC暫存器，再將BR暫存器左移、QR暫存器右移。 當Qn位元為0時，只需將BR暫存器左移及QR暫存器右移即可。 每完成一個處理位元的相關運算，就將SC暫存器內的值減1；直到SC暫存器值為0時，乘法演算法便告完成。

11 5.2 基本乘法器設計 基本乘法過程解析 第一版乘法器的演算法 第一版基本乘法器的硬體實現 第二版基本乘法器設計

12 第一版乘法演算法（First Version of the Multiplication Algorithm）：
第一版乘法器的演算法 第一版乘法演算法（First Version of the Multiplication Algorithm）： 基本乘法演算法 步驟1： 起始設定；BR←被乘數、QR←乘數、AC←0、SC←n； 步驟2： 檢查Qn： [1] 當Qn=0，部分乘積保持不變； [2] 當Qn=1，被乘數BR加至部分乘積，即AC←AC+BR； 步驟3： 被乘數左移1位，即shl(BR)； 乘數右移1位，即shr(QR)； 步驟4： 仍需處理的位元數減1，即SC←SC-1； 步驟5： 檢查SC是否為0；是則結束，否則回到步驟2；

13 第一版乘法器的演算法 第一版乘法演算法運算流程：

14 【例題】使用基本乘法演算法計算兩個4位元數的乘積：2×7。
第一版乘法器的演算法 【例題】使用基本乘法演算法計算兩個4位元數的乘積：2×7。 【解答】 已知兩個數為4位元數值，則2=0010、7=0111； 由基本乘法器硬體架構得知 被乘數 × 乘數 = 乘積 (BR) (QR) (AC) 因此初始值AC= 、BR= 、QR=0111、SC=100

15 【解答】 5.2.2 第一版乘法器的演算法 執行步驟 AC BR QR Qn SC 00000000 00000010 0111 1 100
第一版乘法器的演算法 【解答】 執行步驟 AC BR QR Qn SC 0111 1 100 AC←AC＋BR shl(BR) shr(QR) SC←SC-1 0011 011 0001 010 0000 001 000

16 5.2 基本乘法器設計 基本乘法過程解析 第一版乘法器的演算法 第一版基本乘法器的硬體實現 第二版基本乘法器設計

17 n位元 × n位元乘法器硬體設計： 5.2.3 第一版基本乘法器的硬體實現 加法器： 2n位元BR暫存器：
第一版基本乘法器的硬體實現 n位元 × n位元乘法器硬體設計： 加法器： 長度2n位元的漣波或進位前瞻加法器。 2n位元BR暫存器： 存放被乘數。 除了當作加法器的輸入來源外，同時也能在每個「處理位元」的處理過程中左移1位。

18 n位元 × n位元乘法器硬體設計： 5.2.3 第一版基本乘法器的硬體實現 n位元QR暫存器： 2n位元AC暫存器 ： 位元SC暫存器：
第一版基本乘法器的硬體實現 n位元 × n位元乘法器硬體設計： n位元QR暫存器： 用來存放乘數。 可在每次乘數最右位元的處理過程中向右移一位。 2n位元AC暫存器 ： 存放部分乘積。 同時為加法器的輸入與輸出。 位元SC暫存器： 存放待處理位元數。

19 第一版基本乘法器的硬體實現 基本乘法器硬體架構： 32位元 × 32位元基本乘法器硬體架構

20 5.2 基本乘法器設計 基本乘法過程解析 第一版乘法器的演算法 第一版基本乘法器的硬體實現 第二版基本乘法器設計

21 第一版乘法器的分析與檢討： 5.2.4 第二版基本乘法器設計 第一版乘法演算法乘法計算過程中會發生的幾個現象：
第二版基本乘法器設計 第一版乘法器的分析與檢討： 第一版乘法演算法乘法計算過程中會發生的幾個現象： 乘數被處理完的位元利用右移逐一捨棄，於是不斷空出最左邊的位元空間。 部分乘積每次最多只會有n個位元參與加法運算。

22 第一版乘法器的分析與檢討： 5.2.4 第二版基本乘法器設計 第一版乘法演算法乘法計算過程中會發生的幾個現象：
第二版基本乘法器設計 第一版乘法器的分析與檢討： 第一版乘法演算法乘法計算過程中會發生的幾個現象： 在完成第i次的加法之後，其最右i個位元也不再需要參與後續的運算。 被乘數左移的目的，只是要讓自己的最右位元對應到部分乘積的較高一位元，也就是從右邊數來第2個位元，以針對下一個處理位元進行運算。

23 第二版基本乘法器設計 部分乘積右移： 在每次完成處理位元的運算後隨即把部分乘積右移1位，並將移出的位元放到適當的位置保存起來，那麼被乘數就不需要再左移，只要用一個長度為n的暫存器來儲存，就能維持加法運算的正確性。

24 「被乘數左移」與「部分乘積右移」之比較：
第二版基本乘法器設計 「被乘數左移」與「部分乘積右移」之比較： 被乘數左移法乘法運算 部分乘積右移法乘法運算

25 新版本乘法演算法特點： 5.2.4 第二版基本乘法器設計 利用右移後的局部部分乘積與被乘數相加的方 法完成。 被乘數長度維持為n 。
第二版基本乘法器設計 新版本乘法演算法特點： 利用右移後的局部部分乘積與被乘數相加的方 法完成。 被乘數長度維持為n 。 只需要長度為n的加法器。 部分乘積的右半部可與乘數共用一個暫存器，節省1個n位元暫存器的成本。

26 第二版基本乘法器設計 共用暫存器： 部分乘積與乘數可共用暫存器

27 第二版基本乘法器設計 改進後的演算法即為移位／加法的改良式乘法演算法，又稱為第二版乘法演算法（Second Version of the Multiplication Algorithm）。 改良式n  n乘法器之硬體需有： 具備完整功能的 n位元加法器： 計算部分乘積與被乘數相加的結果，包括進位值。 只執行無號數相加。

28 5.2.4 第二版基本乘法器設計 n位元的BR暫存器： 2n位元可右移AC暫存器： 儲存被乘數。 儲存部分乘積與乘數。
第二版基本乘法器設計 n位元的BR暫存器： 儲存被乘數。 2n位元可右移AC暫存器： 儲存部分乘積與乘數。 等分為Low（右半部）、High（左半部）兩個部分，長度各為n位元： ACLow：扮演乘數所需的QR暫存器。 ACHigh：部分乘積所需要的n位元暫存器。

29 5.2.4 第二版基本乘法器設計 一個單位元的邏輯判斷電路： 長度至少為 的SC暫存器：
第二版基本乘法器設計 一個單位元的邏輯判斷電路： 根據Qn位元的值決定是否要將BR暫存器內的值加至AC暫存器。 長度至少為 的SC暫存器： 用來存放應處理的位元數（乘數的長度）。

30 第二版乘法演算法： 5.2.4 第二版基本乘法器設計 步驟1： 起始設定；BR←被乘數、AC←乘數、SC←n； 步驟2： 檢查Qn：
第二版基本乘法器設計 第二版乘法演算法： 改良式（第二版）乘法演算法 步驟1： 起始設定；BR←被乘數、AC←乘數、SC←n； 步驟2： 檢查Qn： [1] 當Qn=0，部分乘積保持不變，清除加法器進位輸出； [2] 當Qn=1，被乘數BR加至部分乘積的左半部， 即ACHigh←ACHigh＋BR； 步驟3： 部分乘積及乘數均右移1位元，即shr(AC)； 同時將加法器進位輸出移入AC之最高位元； 步驟4：待處理的位元數減1，即SC←SC－1； 步驟5： 檢查SC是否為0；是則結束，否則回到步驟2；

31 第二版基本乘法器設計 改良式乘法演算法的運算流程：

32 【例題】使用改良式乘法演算法計算兩個4位元（無號）數的乘積：11×3。
第二版基本乘法器設計 【例題】使用改良式乘法演算法計算兩個4位元（無號）數的乘積：11×3。 【解答】 已知兩個數長度皆為4位元，則11=1011、3=0011；由基本乘法器硬體架構得知 被乘數 × 乘數 = 乘積 (BR) (QR) (AC) 因此初始值BR=1011、AC= （即ACHigh=0000、ACLow=QR=0011）、SC=100

33 第二版基本乘法器設計 【解答】

34 第二版基本乘法器設計 第二版乘法器的硬體實現： 32位元 × 32位元第二版乘法器硬體架構

35 布斯乘法演算法（Booth’s Multiplication Algorithm）
5.3 進階乘法器設計 布斯乘法演算法（Booth’s Multiplication Algorithm） 陣列乘法器設計

36 5.3.1 布斯乘法演算法 （Booth’s Multiplication Algorithm）
問題的分析： 對於兩種移位／加法的基本乘法器而言： 只能用於無號整數的乘法運算。 若要利用被乘數與乘數的正負組合來得到其最終乘積，運算程序與硬體結構都太過複雜。 當處理位元為1，需要用到加法與移位兩種運算。 必須設法降低加法運算次數，才能加速乘法的運算速度。

37 5.3.1 布斯乘法演算法 （Booth’s Multiplication Algorithm）
改進的方法： 用1個減法與1個加法來取代連串的i個加法運算

38 5.3.1 布斯乘法演算法 （Booth’s Multiplication Algorithm）
主要針對乘數中連續多個 ‘1’ 的位元串來進行處理。 若出現如「111…111」連續i個1的位元串： 在最低位執行一次減法，並在最高位的更高一位執行一次加法，就可以取代這i次的加法運算。 減法運算可能使部分乘積產生負數，因此布斯演算法（乘法器）必須能處理有號數。

39 5.3.1 布斯乘法演算法 （Booth’s Multiplication Algorithm）
處理位元有三種可能的情況： 1：先相加再將部分乘積右移。 0 ：只將部分乘積右移。 -1 ：執行一次減法後將部分乘積右移。 利用算術右移完成部分乘積的右移。

40 5.3.1 布斯乘法演算法 （Booth’s Multiplication Algorithm）
以乘數的連續兩位元來判斷在位元j應執行何種運算： bit(j) bit(j1) 執行 × 1 加上乘數 減去乘數

41 5.3.1 布斯乘法演算法 （Booth’s Multiplication Algorithm）
布斯乘法實例解析： 用傳統方法執行乘法運算；乘數有多少個1就要進行多少次加法。 改用布斯法之後，只用1個減法跟1個加法就可以處理乘數的連續三個1

42 5.3.1 布斯乘法演算法 （Booth’s Multiplication Algorithm）
「n位元  n位元」的布斯乘法器硬體設計： 完整功能的n位元加減法器： 用來計算部分乘積與被乘數相加的結果，包括進位值。 n位元的BR暫存器： 儲存被乘數。

43 5.3.1 布斯乘法演算法 （Booth’s Multiplication Algorithm）
一個2n位元、可進行「算術右移」的AC暫存器： 儲存部分乘積與乘數。 分為High（左半部）、Low（右半部）兩個部分： ACHigh：n位元暫存器，用來存部分乘積。 ACLow：n位元暫存器，用來取代QR。一開始儲存完整的乘數，運算結束時則存放最終乘積的較低n位元。

44 5.3.1 布斯乘法演算法 （Booth’s Multiplication Algorithm）
長度至少為 的SC暫存器： 存放待處理的位元數。 單位元的暫存器Qn+1 ： 存放移出位元。 2位元輸入的邏輯判斷電路： 依照Qn與Qn+1這兩個位元值的組合來決定接下來要做什麼動作。

45 5.3.1 布斯乘法演算法 （Booth’s Multiplication Algorithm）
布斯演算法： 布斯乘法演算法 步驟1： 起始設定；BR←被乘數、AC←乘數、SC←n、Qn+1←0； 步驟2： 檢查QnQn+1： [1] 當QnQn+1=00，部分乘積保持不變； [2] 當QnQn+1=01，被乘數BR加至部分乘積的左邊n個位元， 即ACHighACHigh + BR； [3] 當QnQn+1=10，部分乘積的左半部減去被乘數BR， 即ACHighACHigh  BR； [4] 當QnQn+1=11，部分乘積保持不變； 步驟3：將AC（含部分乘積及乘數）算術右移1位元，即ashr(AC)； 步驟4：待處理的位元數減1，即SC←SC  1； 步驟5： 檢查SC是否為0；是則結束，否則回到步驟2；

46 5.3.1 布斯乘法演算法 （Booth’s Multiplication Algorithm）
布斯演算法的演算流程：

47 5.3.1 布斯乘法演算法 （Booth’s Multiplication Algorithm）
【例題】利用布斯乘法演算法計算兩個4位元有號數的乘積：2×(3)。 【解答】 已知兩數皆為4位元數值，則令n = 4，且2=0010、(-3)=1101。 根據乘法演算法： 被乘數 × 乘數 = 乘積 (BR) (ACLow) (AC) 因此初始值BR=0010、AC= 、SC=100、Qn+1=0

48 5.3.1 布斯乘法演算法 （Booth’s Multiplication Algorithm）
【解答】

49 5.3.1 布斯乘法演算法 （Booth’s Multiplication Algorithm）
布斯演算法效能分析： 最好情況： 當乘數每個位元皆為1時。若乘數為n位元，速度可達第二版乘法器的n倍。 最壞情況： 當乘數所有位元皆為0與1交替出現時。若乘數為n位元，加減法運算共做了n次。效能只有第二版乘法演算法的一半。

50 5.3.1 布斯乘法演算法 （Booth’s Multiplication Algorithm）
平均情況： 倘若以一般乘數隨機出現位元值1的情況來看，布斯法並無法達到「減少加減法運算次數」的目的，其效能僅僅與第二版乘法器相當；唯一改進的就是它多了處理有號數乘法的能力。

51 5.3.1 布斯乘法演算法 （Booth’s Multiplication Algorithm）
「二次編碼」技巧： 在進行連續 ‘1’ 之最高位的更高一位加1運算前，先考慮它與再更高位是否會形成另外一個1的連續串列，然後比照前法予以處理。 任何情況下，最多只需要次 的加減法運算，效能永遠不會比第二版乘法器差。

52 5.3.1 布斯乘法演算法 （Booth’s Multiplication Algorithm）
「二次編碼」技巧： 兩種會造成最壞情況的乘數，在經過二次編碼的技巧處理後，都能將所需的加減次數控制在乘數長度的一半加1以內

53 布斯乘法演算法（Booth’s Multiplication Algorithm）
5.3 進階乘法器設計 布斯乘法演算法（Booth’s Multiplication Algorithm） 陣列乘法器設計

54 陣列乘法器設計 加法是乘法效能的關鍵： 不管是第一、第二版，還是布斯乘法器，其整個過程都是依據乘數的位元值，逐一完成每一個處理位元的相關運算（加、減、或移位）。 進位計算為加法器在執行效率上的最大瓶頸。

55 進位保留加法器（carry-save adder，CSA）：
陣列乘法器設計 進位保留加法器（carry-save adder，CSA）： 當兩數相加時，假使把每一位的進位都「保留」起來，不立即加到較高一位去，那麼因為不需要等較低位數傳來的進位，所以兩數所有相對位元就可以同時進行加法運算。

56 陣列乘法器設計 若各用一個全加器來計算每個位數的加法，由於全加器除了兩個正常輸入外，另有一個進位輸入端，當我們保留所有位數的進位後（不傳給較高一位），此輸入端就都空下來了。假使將第三個數的相對位元從所有全加器的進位輸入端輸入，那麼就能執行三數相加的運算。至於這三組輸入位元相加的結果，就用一個和（Sum）與一個（被保留下來的）進位值（C_out）兩數來表示；而且因為所有位元的全加器皆同步執行，所以這個計算的過程只需要一個全加器的執行週期 。

57 利用全加器有3個輸入端及2個輸出端的特性，可以用4個全加器同時執行三個4位元數的相加。這樣的架構就構成快速加法器的其中一層
陣列乘法器設計 CSA實例： 利用全加器有3個輸入端及2個輸出端的特性，可以用4個全加器同時執行三個4位元數的相加。這樣的架構就構成快速加法器的其中一層

58 陣列乘法器設計 CSA實例： 所有全加器同時各產生1個和位元與1個進位位元，組成一個（保留進位後的）和與一個進位值；由於進位輸出是要加到更高一位的，因此必須左移一位後（此處右端補0），才是它真正的值

59 陣列乘法器設計 多個數相加的陣列加法器： 利用前述的進位保留加法器來將三數相加的階段，只能得到「保留進位後的和」與「進位輸出」兩個新的數；這兩個數必須再完成一階段的加法運算，才能得到最終的和。

60 陣列乘法器設計 由於每個進位輸出位元都必須要加入到更高一位，所以我們必須將C_out左移一位，並在最低位補0，因此C_out的位元數將比三個輸入值多1位。而左移後的C_out與Sum兩數只要再用一個「足夠位數」的完整加法器來相加，就可算出A+B+C的結果。 只需要兩階段：一個全加器週期與一個完整（漣波或進位前瞻）加法器的計算時間，就可以算出三個數字的總和。

61 陣列乘法器設計 四數相加的陣列加法器： 四組4位元進位保留加法器設計

62 陣列乘法器設計 四數相加實際的執行過程：

63 陣列乘法器設計 將快速加法應用到陣列乘法器： 演算實例：

64 陣列乘法器設計 陣列乘法器實作： 對於m位元的被乘數與n位元的被乘數相乘，可先用個AND邏輯閘將乘數的n個位元分別與被乘數的每個位元做AND運算，以產生n個m位元長度的數來參與相加運算，每個數若非為0，就是相當於被乘數左移一定位數的結果。進一步設計的便是 (n-1) 階層、每個階層有m個全加器的n數累加器，整個就構成 (n-1) 階段陣列乘法器。但依據進位保留的設計概念，後半部的設計應分成 (n-2) 階進位保留加法器與1階完整加法器，在此我們先採漣波進位加法器。總計這個 (n-1) 階段陣列乘法器共需使用個AND邏輯閘與m (n-1) 個全加器來完成。

65 陣列乘法器設計 (5位元數) × (5位元數) 的陣列乘法器：

66 【例題】設計一個可將三組4位元數相加的進位保留加法器，並舉1001＋0011＋0111為例，說明電路進行計算的過程。
陣列乘法器設計 【例題】設計一個可將三組4位元數相加的進位保留加法器，並舉1001＋0011＋0111為例，說明電路進行計算的過程。

67 陣列乘法器設計 【解答】 下面為三組4位元數值的進位保留加法器之方塊圖：

68 陣列乘法器設計 【解答】 當進位保留加法器輸入1001、0011、0111後，電路執行過程如下 ：

69 5.4 基本除法器設計 除法基本原理 基本除法演算法與硬體實現

70 除法基本原理 除法（division）： 被除數（dividend）除以除數（divisor）可得到商數（quotient），而未能被整除、剩餘的數則稱為餘數（remainder）。 被除數÷除數＝商數 …… 餘數 一連串的位元比較、移位、與減法算術，且是由最高位開始往較低位運算。

71 除法實例： 5.4.1 除法基本原理 假設被除數為8位元的01001110，除數為4位元的1001。
除法基本原理 除法實例： 假設被除數為8位元的 ，除數為4位元的1001。 由於除數為4位元，所以從被除數的最高4個位元開始與之進行比較。 第一次比較的結果，被除數的4個最高位元值0100小於除數1001，所以商的最高可能位元（對應到被除數的第4高位元）為0。

72 除法基本原理 將被除數部分多考慮一位（相當於左移一位），取較高的5位元來跟除數比較。這次值不小於除數，所以商可以取1，但其所在位數則降為對應到被除數第5高的位元。 時應從被除數參加比較的這個5位元數中，減去除數的值，而所得的結果稱為部分餘數（partial remainder）。

73 除法基本原理 重複利用同樣的方式，將上一步驟所得到的部分餘數與剩餘的3個位元，從高位到最低位一起繼續與除數做比較、移位與減法的運算處理，直到被除數的所有位元皆被處理過，即可得出除法運算後的商與餘數。

74 除法基本原理 除法實例：

75 5.4 基本除法器設計 除法基本原理 基本除法演算法與硬體實現

76 基本除法器的硬體實現 ： 5.4.2 基本除法演算法與硬體實現 加減法器： AC暫存器： BR右移暫存器：
基本除法演算法與硬體實現 基本除法器的硬體實現 ： 加減法器： 計算部分餘數減去除數的結果，同時還可用來計算部分餘數回復的結果。 AC暫存器： 放置加減法的結果。 BR右移暫存器： 存放除數。

77 基本除法演算法與硬體實現 QR左移暫存器： 存放商數。 SC暫存器： 存放待處理的位元數。

78 基本除法器演算法 ： 5.4.2 基本除法演算法與硬體實現
基本除法演算法與硬體實現 基本除法器演算法 ： 基本除法演算法 步驟1： 起始設定；BR←除數左移m-n位元、AC←被除數、QR←0、SC←m-n+1； 步驟2： 測試部分餘數與除數之大小，將部分餘數減去除數，即AC←AC-BR； 步驟3： 檢查AC值； 3a： 當AC>=0 商數左移1位元，即shl QR； 設定商數最右位元為1，即QR0=1； 3b： 當AC<0 表示部分餘數小於除數，除數加回部分餘數， 即AC←AC+BR； 設定商數最右位元為0，即QR0=0； 步驟4： 除數右移1位元，即shr BR（最左的MSB位元補0）； 步驟5： 處理的位元數減1，即SC←SC-1； 步驟6： 檢查SC是否為0；是則結束，否則回到步驟2；

79 基本除法演算法與硬體實現 基本除法演算法的運算流程：

80 【例題】使用基本除法演算法計算8位元數78除以4位元數9：求78÷9 。
基本除法演算法與硬體實現 【例題】使用基本除法演算法計算8位元數78除以4位元數9：求78÷9 。 【解答】 已知被除數為78= 、除數為9=1001； 由基本除法器硬體架構得知 被除數 ÷ 除數 = 商...餘數 (AC) (BR) (QR) (AC) 因此初始值AC= 、BR= 、QR=00000、SC=101

81 基本除法演算法與硬體實現 【解答】

82 基本除法演算法與硬體實現 【解答】

83 m位元被除數與n位元除數基本除法器的硬體設計：
基本除法演算法與硬體實現 m位元被除數與n位元除數基本除法器的硬體設計： 完整的 m位元ALU： 代替m位元的加減法器。 m位元的AC暫存器： 存放部分餘數。

84 5.4.2 基本除法演算法與硬體實現 m位元的BR暫存器： (m-n+1) 位元的QR暫存器： 位元的SC暫存器： 存放除數。
基本除法演算法與硬體實現 m位元的BR暫存器： 存放除數。 除了當作加減法器的輸入來源，並在每次位元的處理過程中右移。 (m-n+1) 位元的QR暫存器： 存放商數。 每次位元的處理過程中依所得的商數位元左移。 位元的SC暫存器： 存放待處理的位元數。

85 基本除法演算法與硬體實現 基本的除法硬體架構： 基本的除法硬體架構

86 5.5 改良的除法器設計 基本除法演算法與硬體實現 非回復式除法演算法

87 移位／加減法的基本除法演算法： 5.5.1 基本除法演算法與硬體實現
基本除法演算法與硬體實現 移位／加減法的基本除法演算法： 又稱第一版除法演算法（First Version of the Division Algorithm）。 除數（BR）需要向右移位（shr）、商數（QR）要向左移位（shl）。 使用「部分餘數與除數右移後的值相加減」的觀念來完成。

88 改良式基本除法演算法： 5.5.1 基本除法演算法與硬體實現
基本除法演算法與硬體實現 改良式基本除法演算法： 第二版除法演算法（Second Version of the Division Algorithm）。 將「部分餘數與除數右移後的值相加減」改為「部分餘數左移後的值與除數相加減」。 可將部分餘數暫存器的低位部分與商數暫存器共用，節省暫存器使用成本。

89 改良式基本除法演算法： 5.5.1 基本除法演算法與硬體實現 步驟1： 起始設定；BR←除數左移mn位元、AC←被除數、SC←mn+1；
基本除法演算法與硬體實現 改良式基本除法演算法： 改良式基本除法演算法 步驟1： 起始設定；BR←除數左移mn位元、AC←被除數、SC←mn+1； 步驟2： 測試部分餘數與除數之大小，將部分餘數減去除數，即AC←ACBR； 步驟3： 檢查AC值； 3a： 當AC>=0 部分餘數左移1位元，即shl AC； 設定AC最右位元為1，即AC0=1； 3b： 當AC<0 表示部分餘數小於除數，將除數加回部分餘數的左半部， 即AC←AC＋BR； 設定AC最右位元為0，即AC0=0； 步驟4： 處理的位元數減1，即SC←SC－1； 步驟5： 檢查SC是否為0；是則結束，否則回到步驟2；

90 基本除法演算法與硬體實現 改良式基本除法器演算法的運算流程：

91 【例題】使用改良式基本除法演算法計算8位元數78除以4位元數9：78÷9 。
基本除法演算法與硬體實現 【例題】使用改良式基本除法演算法計算8位元數78除以4位元數9：78÷9 。 【解答】 已知被除數為78= 、除數為9=1001； 由基本除法器硬體架構得知 被除數 ÷ 除數 = 商...餘數 (AC) (BR) (QR) (AC) 因此初始值BR= 、AC= 、QR=00000、SC=101

92 基本除法演算法與硬體實現 【解答】

93 基本除法演算法與硬體實現 【解答】

94 m位元被除數與n位元除數的改良式基本除法器硬體設計：
基本除法演算法與硬體實現 m位元被除數與n位元除數的改良式基本除法器硬體設計： n+1位元加減法器。 n位元的BR暫存器： 存放除數。 當作加減法器的減數或加數輸入來源。

95 5.5.1 基本除法演算法與硬體實現 m+1位元的AC暫存器： 位元的SC暫存器： 存放部分餘數兼儲存商數。
基本除法演算法與硬體實現 m+1位元的AC暫存器： 存放部分餘數兼儲存商數。 在每次位元的處理過程中左移AC暫存器 。 位元的SC暫存器： 存放待處理的位元數。

96 基本除法演算法與硬體實現 改良式基本除法器硬體架構： 改良式基本除法硬體架構

97 5.5 改良的除法器設計 基本除法演算法與硬體實現 非回復式除法演算法

98 回復式除法演算法： 5.5.2 非回復式除法演算法 在除法的計算過程中，最重要的部分就是確定商的位元值。
非回復式除法演算法 回復式除法演算法： 在除法的計算過程中，最重要的部分就是確定商的位元值。 電腦的硬體需要透過部分餘數減去除數，即AC←AC-BR的方式來分辨部分餘數與除數的大小。 當AC<0 ： 部分餘數小於除數，利用AC←AC+BR來回復為原來的部分餘數。

99 非回復式（non-restoring method）：
非回復式除法演算法 非回復式（non-restoring method）： 若可以直接求得下一階段所需要的部分餘數值，就不必多做那次回復的加法。 非回復式的運算處理： AC←AC+BR；shl AC（相當於×2）； AC←ACBR AC←2×(AC+BR)BR AC←2×AC+BR shl(AC)；AC←AC+BR

100 非回復式除法演算法： 5.5.2 非回復式除法演算法 步驟1： 起始設定；BR←除數左移mn位、AC←被除數、SC←mn+1；
非回復式除法演算法 非回復式除法演算法： 非回復式除法演算法 步驟1： 起始設定；BR←除數左移mn位、AC←被除數、SC←mn+1； 步驟2： 測試部分餘數與除數之大小，將部分餘數減去除數，即AC←ACBR； 步驟3： 檢查AC值； 3a： 當AC>=0 部分餘數（包含在低位的商數）左移1位元，即shl AC； 設定商數最右位元為1，即AC0=1； 處理的位元數減1，即SC←SC1； 檢查SC是否為0；是則結束，否則回到步驟2； 3b：當AC<0，表示部分餘數小於除數，同樣有兩種情況： 若SC>1， 表示乘數還有待處理位元，進行非回復式運算， 即shl AC；AC←AC＋BR； 設定商數最右位元為0，即AC0=0； 處理的位元數減1，即SC←SC－1； 回到步驟3； 若SC=1， 已處理到除數的最右位元，進行回復式運算， 即AC←AC＋BR； 商數左移1位元，即shl AC； 結束；

101 非回復式除法演算法 非回復式除法演算法運算流程：

102 浮點數表示法（Floating Point Representation） IEEE 754表示法
5.6 浮點數的表示 帶小數的數字與定點表示法 浮點數表示法（Floating Point Representation） IEEE 754表示法

103 帶小數的數字若要用電腦的資料來表示，可有兩種方法：
帶小數的數字與定點表示法 帶小數的數字若要用電腦的資料來表示，可有兩種方法： 定點表示法（fixed-point representation） 浮點表示法（floating-point representation） 以浮點表示法來儲存的數字稱為浮點數。

104 定點表示法： 5.6.1 帶小數的數字與定點表示法 將數字分為兩部份： 例： 優點 缺點 整數（integer）
帶小數的數字與定點表示法 定點表示法： 將數字分為兩部份： 整數（integer） 小數（decimal fraction） 例： 9.2510＝ 優點 絕大部分的數字皆能被記錄起來。 缺點 無法利用少許幾個位數來表示非常大或是非常小的數字。

105 浮點數表示法（Floating Point Representation） IEEE 754表示法
5.6 浮點數的表示 帶小數的數字與定點表示法 浮點數表示法（Floating Point Representation） IEEE 754表示法

106 5.6.2 浮點數表示法 （Floating Point Representation）
利用科學表示法來表示的浮點數可由3個部分組成： 符號位元（sign bit） 指數部分（exponential part） 假數部分（mantissa）

107 5.6.2 浮點數表示法 （Floating Point Representation）
浮點數一般化的表示方式： S：符號位元，0為正、1為負 F：分數部分 E：指數部分

108 5.6.2 浮點數表示法 （Floating Point Representation）
指數和有效數之位元數： 增加有效數的位數可以提高精確度。 增加指數的位數可以擴大表述數字的範圍。 同時增加有效數與指數的位數，會提高浮點數的儲存與計算成本。

109 5.6.2 浮點數表示法 （Floating Point Representation）
浮點數正規化（normalize）： 將浮點數分數部分最高位數的1移位到小數點的左邊，因此整數部分一定是1 （除了數值0之外）

110 浮點數表示法（Floating Point Representation） IEEE 754表示法
5.6 浮點數的表示 帶小數的數字與定點表示法 浮點數表示法（Floating Point Representation） IEEE 754表示法

111 IEEE 754浮點數表示法已廣泛使用在許多PC或工作站CPU中。
由美國電機與電子工程師協會（Institute of Electrical and Electronics Engineers，IEEE）在1985年制定的標準規格。 IEEE 754浮點數表示法已廣泛使用在許多PC或工作站CPU中。

112 IEEE 754表示法格式： 5.6.3 IEEE 754表示法 單精度（single precision）
倍精度（double precision）

113 單精度表示法： 5.6.3 IEEE 754表示法 使用32位元： 符號位元用來表示正負號之用。
符號位元佔1位元、指數部分佔8位元、有效數部分佔23位元。 符號位元用來表示正負號之用。 S=0表示浮點數為正；S=1表示浮點數為負。 指數表示方式是利用偏移表示法（biased representation）。 減去偏移值（bias value）127得到指數大小。

114 IEEE 754表示法 單精度表示法： IEEE 754表示法中單精度格式

115 倍精度表示法： 5.6.3 IEEE 754表示法 使用64位元 ： 偏移值為1023。
符號位元佔1位元、指數部分佔11位元、有效數部分佔52位元。 偏移值為1023。

116 IEEE 754表示法 倍精度表示法： IEEE 754表示法中倍精度格式

117 兩種精度可表示的數值範圍： 5.6.3 IEEE 754表示法 單精度： 若採用了IEEE754表示法的單精度格式，其可表示的數值範圍為：
最大正數：0| | | 值等於： 最小正數：0| | | 最大負數：1| | | 最小負數：1| | |

118 IEEE 754表示法 兩種精度可表示的數值範圍： 單精度表示數值的範圍為： 正數範圍： ~ 負數範圍： ~

119 IEEE 754表示法 兩種精度可表示的數值範圍： 倍精度表示數值的範圍為： 正數範圍： ~ 負數範圍： ~

120 溢位與欠位 ： 5.6.3 IEEE 754表示法 溢位： 欠位： 浮點數運算結果超過最大正數或最小負數範圍，因而無法表示。
浮點數運算結果介於最大負數與最小正數之間的範圍內，因而無法表示。 IEEE 754表示法單精度數值表示範圍

121 例外數值的編碼： 5.6.3 IEEE 754表示法 單精度 倍精度 表示意義 指數 有效數 零（0） ≠0 反正規化數 1~254 *
零（0） ≠0 反正規化數 1~254 * 1~2046 標準浮點數值 255 2047 （正或負）無限數 非數 IEEE 754浮點數表示法的標準數值與例外數值編碼

122 例外數值的編碼： 5.6.3 IEEE 754表示法 反正規化數（Denormalized Numbers） 無限數（Infinity）
非數（NaN）

123 IEEE 754表示法 反正規化數： 在IEEE 754表示法規範中，當浮點數運算所產生數值的絕對值非常小，發生欠位現象時（正規化後指數值已小於-126），其結果會被反正規化。

124 IEEE 754表示法 無限數 當浮點數計算結果的數值太大或太小，以至溢位而無法表示時，就用無限數符號來表示這些數值。無限數有正、負之分，各表示太大的浮點數、以及太小的浮點數。浮點數的加、減、乘、除法計算，如除以0的情況，都可能產生正無限數或負無限數。所以最大的指數便是用來表示這些符號。

125 IEEE 754表示法 、 非數： NaN指的是非數（not a number），是一個編碼在IEEE 754表示法格式內的符號。NaN符號的目的即是允許程式設計師將某些測試或決策計算，延遲到適當的地方再處理。NaN產生的原因是不當計算或執行。 運算 產生原因 加減法 乘法 除法 、 開根號 當X<0時

126 捨位處理： 三種捨位方式： 5.6.3 IEEE 754表示法 不管是單精度或倍精度的表示法，其有效數欄位分別只有23位元及52位元。
開根號、倒數的計算結果都有可能產生無限的位元，所以捨去成有限位元是需要的。 三種捨位方式： 直接捨位（directed chopping） 較少誤差捨入（Round to Nearest） 范紐曼捨入（Von Neumann rounding）

127 直接捨位： 5.6.3 IEEE 754表示法 捨位至正無限（round toward +∞）
將浮點數近似成大於該浮點數的相鄰數。 捨位至負無限（round toward -∞） 將浮點數近似成小於浮點數的相鄰數 捨位至零（round toward 0） 浮點數「向零」取近似值。

128 IEEE 754表示法 較少誤差捨入： IEEE 754表示法預設的捨位模式，取與浮點數相近的代表數（representable value）為近似值。 代表數：擁有較少誤差的數值，類似於十進位數的四捨五入。

129 IEEE 754表示法 較少誤差捨入： 爭議情況： 若有2個相鄰浮點數的代表數其誤差皆為相同，這時近似的過程便會用選取的方式。IEEE 754定義的選取方式是挑選有效欄最右位元為0（即偶數）的那個代表數為近似值。

130 IEEE 754表示法 范紐曼捨入： 有效位元最右位元的較低位元中，有任何一個位元為1，就把最低有效位元的值設為1；但假使這些較低位元的值都是0，則有效位元的部分保持不變。

131 對於浮點數的加／減法運算，必須處理小數點的移位與正規化假數欄位的捨位，才能完成正確的運算。
5.7 浮點數加／減法器設計 對於浮點數的加／減法運算，必須處理小數點的移位與正規化假數欄位的捨位，才能完成正確的運算。

132 5.7 浮點數加／減法器設計 浮點數相加／減之演算法 浮點數加／減法的硬體設計

133 浮點數加／減法運算處理步驟： 5.7.1 浮點數相加／減之演算法 步驟一：指數次方比較 步驟二：假數移位運算 步驟三：假數加減運算
浮點數相加／減之演算法 浮點數加／減法運算處理步驟： 步驟一：指數次方比較 根據兩個浮點數的指數值做比較，取指數值較大之數為基準，計算出數值較小之數的假數右位移量。 步驟二：假數移位運算 依上一步驟所計算出來的位移量，對指數值較小之數做右移處理。 步驟三：假數加減運算 至此兩個符點數的指數值已相同，因此進一步將兩個假數做加／減法運算處理。

134 浮點數加／減法運算處理步驟： 5.7.1 浮點數相加／減之演算法 步驟四：假數正規化處理 步驟五：假數捨位處理
浮點數相加／減之演算法 浮點數加／減法運算處理步驟： 步驟四：假數正規化處理 根據兩個假數加／減運算後的結果，進一步將該浮點數做正規化處理，包括假數部分的位移與指數值的修正。 步驟五：假數捨位處理 根據浮點數表示法的假數格式，做有效的捨位處理，因此可能造成運算結果的誤差。

135 浮點數相加／減之演算法 浮點數加／減運算流程：

136 【例題】試利用IEEE 754單精度浮點數表式法完成兩十進位數1.25 + 3.125的和 。
浮點數相加／減之演算法 【例題】試利用IEEE 754單精度浮點數表式法完成兩十進位數 的和 。

137 【解答】 5.7.1 浮點數相加／減之演算法 依據IEEE 754單精度浮點數表式法，1.25與 3.125可表示成
浮點數相加／減之演算法 【解答】 依據IEEE 754單精度浮點數表式法，1.25與 3.125可表示成 => => 依據浮點數加減法運算流程，處理步驟如下： 步驟一： <<指數次方比較>> – = 1 步驟二： <<假數移位運算>> =>

138 浮點數相加／減之演算法 【解答】 步驟三： <<假數加減運算>> = 步驟四： <<假數正規化處理>> => = 步驟五： <<假數捨位處理>> => 最後得 => 4.375

139 5.7 浮點數加／減法器設計 浮點數相加／減之演算法 浮點數加／減法的硬體設計

140 浮點數加／減演算法五個步驟的硬體設計： 5.7.2 浮點數加／減法的硬體設計 步驟一：指數次方比較 步驟二：假數移位運算
浮點數加／減法的硬體設計 浮點數加／減演算法五個步驟的硬體設計： 步驟一：指數次方比較 只需要設計一個指數位元數長度的加／減法器，另以一個暫存器儲存指數差值即可。 步驟二：假數移位運算 必須包含三個2對1的多工器與一個位移暫存器來對假數做有效的位移處理。 步驟三：假數加減運算 只需要設計一個足夠長度的加／減法器來處理兩個假數的加／減法運算。

141 浮點數加／減演算法五個步驟的硬體設計： 5.7.2 浮點數加／減法的硬體設計 步驟四：假數正規化處理 步驟五：假數捨位處理
浮點數加／減法的硬體設計 浮點數加／減演算法五個步驟的硬體設計： 步驟四：假數正規化處理 必須存在二個2對1的多工器來選擇資料來源、一個位移暫存器來做浮點數正規化的處理、與一個暫存器以儲存指數次方的數值。 步驟五：假數捨位處理 只需一個暫存器做適當的假數捨位處理即可。

142 浮點數加／減法的硬體設計 浮點數加／減法器設計：

143 5.8 浮點數乘／除法器設計 浮點數的乘／除演算法 浮點數乘／除法的硬體實現

144 浮點數乘／除法運算不需要處理小數點的移位，只需要處理正規化假數欄位以及捨位 。
浮點數的乘／除演算法 浮點數乘／除法運算不需要處理小數點的移位，只需要處理正規化假數欄位以及捨位 。 浮點數乘／除法運算處理步驟： 步驟一：指數次方加減法運算 根據兩個符點數的乘／除法運算，兩個指數值執行加減運算。 步驟二：假數乘除運算 兩個假數直接執行乘／除法運算處理。

145 浮點數乘／除法運算處理步驟： 5.8.1 浮點數的乘／除演算法 步驟三：假數正規化處理 步驟四：假數捨位處理
浮點數的乘／除演算法 浮點數乘／除法運算處理步驟： 步驟三：假數正規化處理 根據兩個假數乘／除法運算後的結果，進一步對結果假數做浮點數正規化的處理，並調整指數次方的數值。 步驟四：假數捨位處理 根據浮點數表示法的假數格式，做有效的捨位處理，但可能因此造成運算的誤差。

146 浮點數的乘／除演算法 浮點數乘／除法運算流程：

147 【例題】試利用IEEE 754單精度浮點數表示法完成1.25 × 3.125運算。
浮點數的乘／除演算法 【例題】試利用IEEE 754單精度浮點數表示法完成1.25 × 3.125運算。

148 【解答】 5.8.1 浮點數的乘／除演算法 依據IEEE 754單精度浮點數表式法，1.25與 3.125可表示成
浮點數的乘／除演算法 【解答】 依據IEEE 754單精度浮點數表式法，1.25與 3.125可表示成 => => 依據浮點數乘／除法運算流程，處理步驟如下： 步驟一：<<指數次方加法運算>> ( – ) + ( – ) = 1 步驟二：<<假數乘法運算>> × =

149 【解答】 5.8.1 浮點數的乘／除演算法 步驟三：<<假數正規化處理>>
浮點數的乘／除演算法 【解答】 步驟三：<<假數正規化處理>> => = 步驟四：<<假數捨位處理>> => 最後得 =>

150 5.8 浮點數乘／除法器設計 浮點數的乘／除演算法 浮點數乘／除法的硬體實現

151 浮點數的乘／除演算法四個步驟之硬體設計：
浮點數乘／除法的硬體實現 浮點數的乘／除演算法四個步驟之硬體設計： 步驟一：指數次方加減法運算 只需要一個指數長度的加／減法器來處理兩個指數的加減法運算，以及一個暫存器來儲存所得的指數值。 步驟二：假數乘除運算 只需要設計一個足夠長度的乘／除法器來處理兩個假數的乘／除法運算。

152 浮點數的乘／除演算法四個步驟之硬體設計：
浮點數乘／除法的硬體實現 浮點數的乘／除演算法四個步驟之硬體設計： 步驟三：假數正規化處理 必須包含二個2對1的多工器來選擇資料來源、以及一個位移暫存器，配合前述的（指數加減結果）暫存器來做浮點數正規化的處理。 步驟四：假數捨位處理 只需一個暫存器做適當的假數捨位處理即可。