FSM乘法器简介

1、基于有限状态机的乘法器设计与实现n乘法器是运算器不可或缺的重要组成单元，而运算器是微处理器的重要组成部分，所以研究高性能微处理器芯片离不开乘法器的研究。n如今，我们的生活离不开手机、平板电脑等便携设备，而其中的嵌入式芯片对乘法器的性能同样十分依赖。n人们对便携设备即要求高性能，又要求较长的待机时间，这就要求在芯片设计时既要考虑性能的提高又要合理控制功耗。1.乘法器n1.1.什么是乘法器n乘法器的运算速度（运算延迟时间）时间上n设计电路的芯片面积（所使用的逻辑器件数量）空间上n电路运行产生的功耗1.2 评估乘法器性能的参数1.2 评估乘法器性能的参数n在乘法器设计中，Booth算法被认为是乘法器

2、设计的里程碑。nBooth算法通过分析乘数编码产生部分积，整体上减少了部分积的数目，提高了部分积求和速度。n但是，当乘数的位数较长时，Booth 算法中编码的阶数增加，导致逻辑电路的设计变的十分复杂，整个运算过程的延迟也明显增加。因此，Booth 算法不适宜于应用在较高阶的乘法器设计中。1.3 booth算法n行旁路乘法器，就是将2选1多路选择器引入阵列乘法器的设计中，在每一个全加器下增加了一个多路选择器，乘数中的各个数据位作为选择器的输出控制信号，当乘数中的某一位为零时，避免了一次加法操作，也减少了加法器的数量。1.4 行旁路乘法器n使用时序电路实现指令控制或者进行复杂运算时，一般会按照时钟

3、周期逐条执行指令，很多时候一条指令可能需要多个时钟周期才能完成。而有限状态机从一个状态到另一个状态的状态变换只需一个时钟周期就可以完成，并且在一个状态中状态机可以完成许多并行运算和控制操作。因此，在运算规律比较简单并且变化状态比较有限的情况下，使用有限状态机实现的硬件系统比使用时序电路完成相同的功能在速度上会有较高的优势。n有限状态机（Finite State Machine，简称 FSM）是一种具有离散输入和输出系统的数学模型，是数字逻辑电路以及数字系统的重要组成部分，尤其应用于数字系统核心部件的设计，以实现高效率高可靠性的逻辑控制。n可以将状态机理解为寄存器寄存器和触发器触发器的集合，寄存

4、器用于存储所有状态状态，触发器用于实现状态之间的转移转移。2 有限状态机（FSM）n有限状态机的三要素n输入输入：状态机中各状态之间转移的条件。例如，四位乘法器中，乘数共有 16 种可能的情况，分别用 00001111 表示，这 16 种数值将作为状态机各个状态之间的跳转条件。n状态状态：也称状态变量。例如，可以将寄存器的变化序列作为状态。在状态机设计中还包含了“陷阱”状态，当输入非法数据时，电路进入“陷阱”状态，很快就能恢复到正常状态。这也体现了状态机设计的稳定性和安全性。n 输出输出：当到达某一个特定状态时发生的事件。2.1 FSM的组成n状态转换图n状态转移列表nHDL 语言描述n时序图

5、n算法状态机图，也称 ASM 图（类似于流程图）2.2 FSM的描述方式n逻辑抽象，画出状态转换图：把一个实际逻辑关系表示为时序逻辑函数，用状态转换表或者状态转换图来描述n状态化简：合并等价状态，得到最简化的状态转换图。n状态分配：即状态编码（格雷码、独热码等）n选定触发器的类型，计算出状态方程、驱动方程和输出方程n根据方程画出逻辑图2.3 设计FSM的一般步骤n将有限状态机引入乘法器设计，主要是因为：需要一种电路，能够随时记住自己所处的状态，而且只在时钟信号的跳变时刻来临，并且满足触发条件时，进行状态之间的跳转，不满足条件，则停留在当前的状态。而有限状态机的工作机制就是状态之间的转移。n利用

6、有限状态机能产生复杂的以时钟跳变沿为前提的同步时序逻辑，并能提供操作逻辑系统的开关阵列所需要的复杂控制时序。有限状态机和时钟信号的共同控制能使系统中所有数据的流动和处理按照同一时钟节拍有序进行，有效地避免竞争冒险现象对逻辑运算的破坏，解决了时延问题。2.4 引入FSM的原因n有限状态机的设计离不开状态转换图：n极小化状态转换图，目的是减少不必要的状态，节约资源，开关的活动减少n在状态编码的过程中，对状态进行最优分配，减少状态间的活动次数n总体来说，减少了开关的活动频率，减少了功耗2.4 引入FSM的原因n行旁路乘法器：行旁路乘法器采用跳跃进位加法器和全加器相结合完成部分积的相加运算，同时在每一

7、行的部分积中加入了旁路设计旁路设计，即将2选选1多多路选择器路选择器连接在每一个加法器上。多路选择器的两条输入数据分别是与其连接的全加器的其中一条输入数据，以及全加器的输出数据。该设计的优势优势在于，当乘数中的某一位为零时，不必计算上一级部分积与该零行的加法运算，而是直接将上一级部分积输出到下一级加法器中，因而提高了整个乘法过程的运算速度。n本文的FSM乘法器是基于行旁路乘法器设计的。3 FSM乘法器n具体来说，FSM乘法器就是，将行旁路乘法器的乘法运算过程中与乘数对应的部分积表示为状态机中的状态，并用状态转换图完成对乘法过程的描述。借助状态机良好的时序逻辑控制能力，FSM 乘法器可以快速准确

8、的完成乘法运算，并且由于使用的逻辑器件相对较少，FSM 乘法器的功耗也有所降低。3.1 FSM乘法器设计n3.1 FSM乘法器设计n3.2 FSM乘法器算法设计状态转换算法:1：IF 复位信号为“1” THEN2：DO 将S0赋予当前状态；3：ELSIF 时钟信号为“1”THEN4：DO 将下一状态设置为当前状态5：END IF3.2 FSM乘法器算法设计控制信号输出算法:1：WHEN 输入为“0000”2： DO 将S1作为当前状态；3： 将P0赋值Y；4：WHEN 输入为“0001”5： DO 将S2作为当前状态；6： 将P1赋值Y；7：8：WHEN 输入为“1111”9： DO 将S15

9、作为当前状态；10： 将P15赋值Y；3.2 FSM乘法器算法设计n采用时序逻辑电路设计的乘法器仿真图3.3 仿真实验结果3.3 仿真实验结果n采用有限状态机设计的乘法器仿真图n由仿真图可知，采用时序电路设计的乘法器仿真过程中出现“毛刺”，而采用状态机设计的乘法器有效避免了“毛刺”的产生。信号在信号在FPGA器件内部通过连线和逻辑器件内部通过连线和逻辑单元单元时，都有一定的延时时，都有一定的延时。延时的大小与连线的长短和逻辑单元的数目有关，同时还受器件的制造工艺、工作电压、温度等条件的影响。信号的高低电平转换也需要一定的信号的高低电平转换也需要一定的过渡过渡时间时间。由于存在这两方面因素，多路

10、信号的电平值发生变化时，在信号变化的瞬间，组合逻辑的输出有先后顺序，并不是同时变化，往往会出现一些不正确的尖峰信号，这些尖峰信号称为“毛刺”。如果一个组合逻辑电路中有“毛刺”出现，就说明该电路存在“冒险”。因此，应避免产生“毛刺”。3.4 结果分析3.4 结果分析n两种乘法器对比乘法器设计乘法器设计逻辑器件数量逻辑器件数量功耗（功耗（mW）运算延迟（运算延迟（ns）行旁路乘法器50/51364.3813.931FSM乘法器26/51364.2112.420n整个乘法运算过程是一个时序逻辑过程，但是当乘数的每一个数据位进入电路时，所进行的部分积的运算是一个组合逻辑过程，组合逻辑的输出有先有后，信号不是同时进行变化，所以容易产生毛刺。n采用有限状态机设计的乘法器，每一个乘数的数据位决定了一个部分积，这个部分积的产生是同时产生的，不存在组合逻辑中的先后问题，所以有效地避免了毛刺的产生。同时，