在8位微程序控制的模型計算機中Booth算法的實現

王曉東，富 坤，耿恒山，秘海曉，孫曉麗

（河北工業大學計算機科學與軟件學院，天津 300401）

在8位微程序控制的模型計算機中Booth算法的實現

王曉東，富 坤，耿恒山，秘海曉，孫曉麗

（河北工業大學計算機科學與軟件學院，天津 300401）

描述了在8位微程序控制的模型計算機中，通過編程實現了Booth算法的運算過程。對Booth算法進行了分析，繪出了實現Booth算法的流程圖，編寫了匯編語言程序，在8位微程序控制的模型計算機中實現了Booth算法，達到了預期的結果。

乘法；Booth算法；模型計算機；補碼

計算機組成原理是計算機專業的核心課程之一。該課程中的部分運算方法詳細闡述了數據的表示和運算，解決了計算機中最基本的問題，能使學習者認識到計算機在自動解題過程中數據信息的加工處理流程，從而進一步加深對計算機硬件組成及整體工作原理的理解。其中乘法又是很重要的一部分，由于補碼相對于原碼的優勢，機器大都采用補碼做加減運算，進而在乘法運算中使補碼乘法得到普遍應用。Booth算法是補碼算法中最常用的一種算法，因此有必要深入學習該算法的原理和實現流程。本實驗是在8位微程序控制的模型計算機上實現補碼的1位乘法，這有助于鞏固和加深課程中所學知識，熟練掌握對實驗板的操作，以及掌握復雜指令在計算機中的工作流程［1－2］。

1 Booth算法簡介

Booth算法也就是補碼1位乘的比較法。被乘數為［X］補，乘數為［Y］補，［P］補為乘積，按執行順序得出每一步的部分積。

2 8位微程序控制的模型計算機

8位微程序控制的模型計算機作為組成實驗設備，該實驗平臺由微程序控制模塊、時序電路模塊、存儲器模塊和運算器模塊等部分構成。通過輸入微指令，配合時序電路，實現對數據的運算、存儲等功能。8位微程序控制的模型計算機是較早的一種8位組成原理實驗設備，且各模塊界限又是統一整體［5－6］，通過實驗環節，進一步融合貫通所學內容，理解計算機內部各個模塊的工作過程及其原理，以及復雜指令在計算機中的工作流程。

3 在8位微程序控制的模型計算機中實現Booth算法

3.1 實現方法

8位微程序控制的模型計算機中寄存器由2片74LS670芯片組成，構成4個8位寄存器A，B，C，D，筆者使用到其中的A，B和C 3個寄存器，各種運算操作由寄存器A和寄存器B配合完成，寄存器C作為計數器。靜態存儲器由HM6116芯片構成，被乘數、乘數和部分積以及其他一些數據都存放在存儲器中，需要時調入到寄存器中。每一步操作開始時進行乘數最后2位的判斷，基于該實驗平臺所支持的指令系統，并考慮到指令長度和冗余程度，本實驗采取對后2位進行逐位判斷的方式進行判斷，進而得出 ［X］補或［－X］補還是部分積直接移位。由于該實驗平臺上的存儲單元為8位，部分積分為高位部分和低位部分，分別存儲在2個存儲單元中，部分積移位時，配合相應指令將部分積高位部分的最低位取出，該位數據替換到右移1位后的低位部分的最高位，接著將部分積的高位部分右移1位，完成整體部分積的右移操作。

3.2 Booth算法控制流程

乘法運算前寄存器A被清零，作為初始部分積高位部分。寄存器B也相應清零。被乘數補碼存儲在寄存器A中，乘數的補碼末尾補0（作為附加位）后存放在寄存器B中，寄存器（計數器）C存放乘數的位數n。乘法開始后，根據寄存器B末2位Bn，Bn＋1的狀態決定部分積與被乘數相加還是相減，或是自身值不變直接根據補碼規則進行算術移位，這樣重復n次，最后根據寄存器B的末2位狀態決定部分積是與被乘數相加還是相減，或者部分積的值不變，所得結果不必移位，即最終結果［7］。補碼乘法乘積的符號位在運算中自然形成，見圖1。

圖1 Booth算法控制流程圖Fig.1 Control flow graph of Booth algorithm

3.3 Booth算法所需的硬件配置

Booth算法運算基本硬件配置圖見圖2。

圖2中部分積高8位部分、低位以及乘數部分和被乘數都是存儲在靜態存儲器HM6116芯片中，當需要進行運算時調入到寄存器，寄存器A，B分別為74LS670芯片中寄存單元，寄存器A中為部分積高位，調入到寄存器B中的數據由部分積低位，由部分的末2位判斷得到，然后2個寄存器中數據送入ALU即74LS181進行運算，結果存儲到原地址中，借助ALU和移位門完成右移操作。

3.4 操作步驟

本實驗以X＝－0.110101，Y＝0.101101為例，則［X］補＝11.001011，［Y］補＝0.101101，［－X］補＝0.110101。此例題采用雙符號位，按照Booth算法計算，計算過程見表1。

表1 Booth算法計算過程Tab.1 Calculation process of Booth algorithm

圖2 Booth算法運算基本硬件配置Fig.2 Basic hardware configuration of Booth algorithm operation

在該實驗平臺上，按照機器執行順序的具體操作步驟如下。

1）預置地址

根據該實驗操作流程，將開關K8置于輸入位置，合上開關K6進行單指令運行，按A3鍵進行總清；將初始地址00000001置于數據開關上，按A2鍵輸入首地址［8］。

2）輸入數據

將部分積、被乘數、乘數以及輔助運算數據存入靜態存儲器HM6116中。如1）預置存儲數據的首地址，將要輸入的數據置于數據開關上，按A1鍵，這時輸入的內容和單元的地址同時由數據燈和地址燈顯示；如果下一個字節數據緊接上一個單元存放，則回到2），2）中將輸入的數據置于數據開關處繼續，直至程序全部輸入完畢，見表2。表2中數據10000000，00000010等用于配合“與”指令提取對位數據。

3）輸入程序

本實驗平臺的指令系統有30條指令，結合這些指令實現該算法。根據上文控制流程描述的過程，按照2）中輸入數據的方式順序輸入程序。

本實驗程序所實現的過程如下。

1）部分積進行加法運算。利用訪問內存的LDA指令將低位及乘數提取到寄存器B中，再取出00000001放入寄存器A中，運用ANA指令運算得出只包含低位及乘數的最低位的8位二進制數，最低位分為0和1兩種，結合JZ指令，在這2種情況下進一步判斷低位及乘數的次低位，從而得出01，10或是00（11），按照所得結果從內存中取出相應數據，和部分積高位做加法運算，并存儲到原部分積高位部分的地址中。

表2 內存中數據存儲結構Tab.2 Data storage structure in memory

2）判斷是否循環結束。寄存器C中存儲的數據是循環次數，做完1次加法運算后，用JZ指令對寄存器C中數據進行1次判斷，如果是0則表明循環操作結束，跳出循環至判斷溢出部分，否則數據減1并存回寄存器C中，繼續執行移位操作。

3）實現部分積右移。由于部分積存在于2個8位內存單元，因此對部分積進行移位操作分2部分進行。

①部分積低位右移。得到部分積高8位的最低位，將其存入寄存器B中的最高位位置，再從內存將部分積低位及乘數提取到寄存器A中，對寄存器A中數據進行算術右移并和寄存器B中數據進行“與”運算，完成部分積低位部分右移1位操作，將數據存回原內存單元；

②部分積高位右移。部分積的高位部分右移需要考慮到符號位，最高位符號位在移位時保持自身不變，取出部分積高位部分的最高位，將其放入寄存器B中最高位位置，這時寄存器A中的部分積高位部分右移1位并和寄存器B中數據進行“與”操作完成右移1位，存回原來內存單元中，從而完成部分積整體右移。再跳轉到開頭循環執行。表3為本實驗所用到的指令［9］。

4）判斷溢出

執行完以上操作后，對最后結果判斷是否溢出，通過判斷部分積的最高2位是否為相同數值即可得出結果，不同證明結果溢出跳轉到停機，相同則輸出結果。

5）檢查內存

用1）中方法，將要檢查的單元地址00000001預置好，將K8置于檢查處，合上開關K6，按A1鍵，這時被檢查單元地址和內容分別由地址燈和數據燈顯示，再按A1鍵順序檢查下一個單元內容，或者重新預置要檢查的地址，重復上述操作直到檢查完畢。

6）輸出結果

首先按1）所述步驟，預置程序入口地址，將K8置于執行程序位置，合上單微指開關K7和單指令開關K6，模型機為連續運行狀態，按A1鍵順序執行，最終在數據燈上顯示乘積結果。

表3 指令表Tab.3 Instruction list

4 結 語

闡述了在8位微程序控制的模型計算機中Booth算法的實現過程，通過分析Booth算法運算規則，結合該實驗平臺自身特點和指令系統，設計并給出了詳細的操作步驟。本實驗作為組成原理課程的加深和延續，起到鞏固所學知識的作用，加深了對計算機工作原理的理解，鍛煉培養了實踐能力和創新能力。

［1］耿恒山.計算機組成原理［M］.北京：機械工業出版社，2009.

［2］唐朔飛.計算機組成原理［M］.北京：高等教育出版社，2008.

［3］陳蘇豫.用BOOTH 算法改進的計算機定點乘法運算［J］.晉中學院學報（Journal of Jinzhong University），2008，25（3）：91-93.

［4］孫啟良.二進制補碼一位乘法規律的推導［J］.電腦知識與技術（Computer Knowledge and Technology），2009，5（25）：7 278-7 280.

［5］譚小蘭，陳 多，陳華光.8位模型機的設計與實現［J］.湖南工程學院學報（自然科學版）（Journal of Hunan Institute of Engineering（Natural Science Edition）），2011，21（1）：71-73.

［6］李 英，湯作華，趙 勇.對 NJS-Ⅱ型計算機組成實驗儀的改進［J］.華東地質學院學報（Journal of East China Geological Institute），2002，25（2）：171-173.

［7］王曉蘭，吳秀敏，方運潭.JZYL-Ⅱ型計算機組成原理實驗平臺研制與開發［J］.實驗室研究與探索（Research and Exploration in Laboratory），2009，28（9）：80-82.

［8］李俊紅，解建軍.定點補碼乘法的一種實現方案［J］.河北師范大學學報（自然科學版）（Journal of Hebei Normal University（Natural Science Edition）），2000，24（3）：312-313.

［9］劉乃文.馮·諾依曼機原理的教學研究與應用［J］.計算機工程與設計（Computer Engineering and Design），2006，27（10）：1 831-1 834.

［10］柏 磊，龍 濤.基于單片機的數制轉換算法設計［J］.河北工業科技（Hebei Journal of Industrial Science and Technology），2010，27（4）：229-231.

Implementation of Booth algorithm in the 8-bit microprogram controlled model computer

WANG Xiao-dong，FU Kun，GENG Heng-shan，MI Hai-xiao，SUN Xiao-li
（School of Computer Science and Engineering，Hebei University of Technology，Tianjin 300401，China）

This paper describes the implementation of Booth algorithm in a 8-bit microprogram controlled model computer.Through analyzing the Booth algorithm by using the flow chart and program assembly language，it is found that the Booth algorithm can be applied to 8-bit microprogram controlled model computer.

multiplication；Booth algorithm；model computer；complement

TP301

A

1008-1542（2012）05-0443-05

2012-06-01；

2012-09-06；責任編輯：陳書欣

國家自然科學基金青年基金資助項目（31100711）

王曉東（1987-），男，河北大名人，碩士研究生，主要從事計算機控制技術方面的研究。