FSM乘法器简介

基于有限状态机的乘法器设计与实现乘法器是运算器不可或缺的重要组成单元，而运算器是微处理器的重要组成部分，所以研究高性能微处理器芯片离不开乘法器的研究。如今，我们的生活离不开手机、平板电脑等便携设备，而其中的嵌入式芯片对乘法器的性能同样十分依赖。人们对便携设备即要求高性能，又要求较长的待机时间，这就要求在芯片设计时既要考虑性能的提高又要合理控制功耗。1.乘法器乘法器的设计模型基于“移位-相加”算法以4bit乘法器为例，A=a3a2a1a0，B=𝑏3𝑏2𝑏1𝑏0，两者的积为8bit的数M=m7m6m5m4m3m2m1m0。乘法器的运算过程可概括为：产生部分积；对部分积求和；通过进位传递过程完成最终结果的计算。对于最后一步，一般不做研究，因为在部分积的求和过程中，各种性能良好的加法器已经被应用其中。对于乘法运算过程的优化工作主要是在前两步进行。1.1.什么是乘法器乘法器的运算速度（运算延迟时间）——时间上设计电路的芯片面积（所使用的逻辑器件数量）——空间上电路运行产生的功耗1.2评估乘法器性能的参数1.2评估乘法器性能的参数在乘法器设计中，Booth算法被认为是乘法器设计的里程碑。Booth算法通过分析乘数编码产生部分积，整体上减少了部分积的数目，提高了部分积求和速度。但是，当乘数的位数较长时，Booth算法中编码的阶数增加，导致逻辑电路的设计变的十分复杂，整个运算过程的延迟也明显增加。因此，Booth算法不适宜于应用在较高阶的乘法器设计中。1.3booth算法行旁路乘法器，就是将2选1多路选择器引入阵列乘法器的设计中，在每一个全加器下增加了一个多路选择器，乘数中的各个数据位作为选择器的输出控制信号，当乘数中的某一位为零时，避免了一次加法操作，也减少了加法器的数量。1.4行旁路乘法器使用时序电路实现指令控制或者进行复杂运算时，一般会按照时钟周期逐条执行指令，很多时候一条指令可能需要多个时钟周期才能完成。而有限状态机从一个状态到另一个状态的状态变换只需一个时钟周期就可以完成，并且在一个状态中状态机可以完成许多并行运算和控制操作。因此，在运算规律比较简单并且变化状态比较有限的情况下，使用有限状态机实现的硬件系统比使用时序电路完成相同的功能在速度上会有较高的优势。有限状态机（FiniteStateMachine，简称FSM）是一种具有离散输入和输出系统的数学模型，是数字逻辑电路以及数字系统的重要组成部分，尤其应用于数字系统核心部件的设计，以实现高效率高可靠性的逻辑控制。可以将状态机理解为寄存器和触发器的集合，寄存器用于存储所有状态，触发器用于实现状态之间的转移。2有限状态机（FSM）有限状态机的三要素输入：状态机中各状态之间转移的条件。例如，四位乘法器中，乘数共有16种可能的情况，分别用0000~1111表示，这16种数值将作为状态机各个状态之间的跳转条件。状态：也称状态变量。例如，可以将寄存器的变化序列作为状态。在状态机设计中还包含了“陷阱”状态，当输入非法数据时，电路进入“陷阱”状态，很快就能恢复到正常状态。这也体现了状态机设计的稳定性和安全性。输出：当到达某一个特定状态时发生的事件。2.1FSM的组成状态转换图状态转移列表HDL语言描述时序图算法状态机图，也称ASM图（类似于流程图）2.2FSM的描述方式逻辑抽象，画出状态转换图：把一个实际逻辑关系表示为时序逻辑函数，用状态转换表或者状态转换图来描述状态化简：合并等价状态，得到最简化的状态转换图。状态分配：即状态编码（格雷码、独热码等）选定触发器的类型，计算出状态方程、驱动方程和输出方程根据方程画出逻辑图2.3设计FSM的一般步骤将有限状态机引入乘法器设计，主要是因为：需要一种电路，能够随时记住自己所处的状态，而且只在时钟信号的跳变时刻来临，并且满足触发条件时，进行状态之间的跳转，不满足条件，则停留在当前的状态。而有限状态机的工作机制就是状态之间的转移。利用有限状态机能产生复杂的以时钟跳变沿为前提的同步时序逻辑，并能提供操作逻辑系统的开关阵列所需要的复杂控制时序。有限状态机和时钟信号的共同控制能使系统中所有数据的流动和处理按照同一时钟节拍有序进行，有效地避免竞争冒险现象对逻辑运算的破坏，解决了时延问题。2.4引入FSM的原因有限状态机的设计离不开状态转换图：极小化状态转换图，目的是减少不必要的状态，节约资源，开关的活动减少在状态编码的过程中，对状态进行最优分配，减少状态间的活动次数总体来说，减少了开关的活动频率，减少了功耗2.4引入FSM的原因行旁路乘法器：行旁路乘法器采用跳跃进位加法器和全加器相结合完成部分积的相加运算，同时在每一行的部分积中加入了旁路设计，即将2选1多路选择器连接在每一个加法器上。多路选择器的两条输入数据分别是与其连接的全加器的其中一条输入数据，以及全加器的输出数据。该设计的优势在于，当乘数中的某一位为零时，不必计算上一级部分积与该零行的加法运算，而是直接将上一级部分积输出到下一级加法器中，因而提高了整个乘法过程的运算速度。本文的FSM乘法器是基于行旁路乘法器设计的。3FSM乘法器具体来说，FSM乘法器就是，将行旁路乘法器的乘法运算过程中与乘数对应的部分积表示为状态机中的状态，并用状态转换图完成对乘法过程的描述。借助状态机良好的时序逻辑控制能力，FSM乘法器可以快速准确的完成乘法运算，并且由于使用的逻辑器件相对较少，FSM乘法器的功耗也有所降低。3.1FSM乘法器设计输入：状态机的外部输入包括时钟信号、复位信号、被乘数和乘数。其中时钟信号用来控制整个运算过程中的时序，复位信号用来重置整个运算。被乘数与乘数都为4位信号，用来表示数值0~15。状态：在FSM乘法器中，将每一种乘数（0000~1111）对应的乘积作为状态机的内部状态。在每一个状态内部，当乘数位𝑏𝑖为0时，第i行对应的部分积不再参与任何运算。输出：有限状态机根据输入信号经过状态转换到达终态时，对应的输出数据即是一次乘法运算的结果。当一次乘法运算结束之后，即进入终止状态后，赋予电路Reset复位信号，可将电路回归到初始状态，等待下次数据的输入。3.1FSM乘法器设计以四位乘法器为例，状态机的状态设置为𝑆0～𝑆16，其中𝑆0为状态机的初态。𝑃0～𝑃15为状态机状态转移时的输出数据。FSM乘法器由两个算法完成，状态转换算法和控制信号输出算法。3.2FSM乘法器算法设计状态转换算法:1：IF复位信号为“1”THEN2：DO将S0赋予当前状态；3：ELSIF时钟信号为“1”THEN4：DO将下一状态设置为当前状态5：ENDIF3.2FSM乘法器算法设计控制信号输出算法: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作为当前状态；10：将P15赋值Y；3.2FSM乘法器算法设计采用时序逻辑电路设计的乘法器仿真图3.3仿真实验结果3.3仿真实验结果采用有限状态机设计的乘法器仿真图由仿真图可知，采用时序电路设计的乘法器仿真过程中出现“毛刺”，而采用状态机设计的乘法器有效避免了“毛刺”的产生。信号在FPGA器件内部通过连线和逻辑单元时，都有一定的延时。延时的大小与连线的长短和逻辑单元的数目有关，同时还受器件的制造工艺、工作电压、温度等条件的影响。信号的高低电平转换也需要一定的过渡时间。由于存在这两方面因素，多路信号的电平值发生变化时，在信号变化的瞬间，组合逻辑的输出有先后顺序，并不是同时变化，往往会出现一些不正确的尖峰信号，这些尖峰信号称为“毛刺”。如果一个组合逻辑电路中有“毛刺”出现，就说明该电路存在“冒险”。因此，应避免产生“毛刺”。3.4结果分析3.4结果分析两种乘法器对比乘法器设计逻辑器件数量功耗（mW）运算延迟（ns）行旁路乘法器50/51364.3813.931FSM乘法器26/51364.2112.420整个乘法运算过程是一个时序逻辑过程，但是当乘数的每一个数据位进入电路时，所进行的部分积的运算是一个组合逻辑过程，组合逻辑的输出有先有后，信号不是同时进行变化，所以容易产生毛刺。采用有限状态机设计的乘法器，每一个乘数的数据位决定了一个部分积，这个部分积的产生是同时产生的，不存在组合逻辑中的先后问题，所以有效地避免了毛刺的产生。同时，由于逻辑器件之间的开关活动数量减少，也使整个乘法运算过程中的功耗减少。4.总结5未来研究方向并行行旁路乘法器的FSM实现，对乘数进行编码，改善乘法器的结构当做高位数乘法时，随着乘数位数增加，部分积的数量也增加，从而增加了逻辑器件的数量。设计带多路选择器的阵列乘法器并用FSM实现，能够有效进行高位数乘法并控制功耗。谢谢！