在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-），男，河北大名人，硕士研究生，主要从事计算机控制技术方面的研究。