有限状态机的分析

1、有限状态机的分析有限状态机的分析状态最简化状态最简化最少的状态需要最少的状态位最少的状态需要最少的状态位最少的位需要最少的逻辑方程最少的位需要最少的逻辑方程状态最简化方法状态最简化方法行匹配法行匹配法蕴含表方法蕴含表方法状态分配策略状态分配策略顺序编码顺序编码随机编码随机编码单点编码单点编码面向输出的编码面向输出的编码启发式编码启发式编码有限状态机的划分有限状态机的划分VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz1VIII - Working with Seque

2、ntial Logic Copyright 2004, Gaetano Borriello and Randy H. Katz2通用有限状态机设计过程通用有限状态机设计过程n(1) (1) 定义输入和输出定义输入和输出n(2) (2) 定义状态机可能的状态定义状态机可能的状态q状态化简状态化简n(3) (3) 用二进制对状态和输出进行编码用二进制对状态和输出进行编码q状态分配或状态编码状态分配或状态编码q输出编码输出编码q可能的输入编码可能的输入编码n(4) (4) 选择适当的逻辑实现状态和输出选择适当的逻辑实现状态和输出q组合逻辑的实现和优化组合逻辑的实现和优化q步骤步骤2 2和和3 3对最

3、终的逻辑将产生很大的影响对最终的逻辑将产生很大的影响例：简单的自动售货机例：简单的自动售货机自动售货机在收到自动售货机在收到1515美分之后就会给出一件商品，这台机器具有美分之后就会给出一件商品，这台机器具有能够接收能够接收5 5美分和美分和1 1角硬币的单个投币口，每次投入一枚硬币，其角硬币的单个投币口，每次投入一枚硬币，其中机械传感器用来指示插入投币口是中机械传感器用来指示插入投币口是5 5美分还是美分还是1 1角，控制器的输角，控制器的输出导致一件商品交到顾客手中出导致一件商品交到顾客手中两个假设简化设计：两个假设简化设计：不找零不找零在每次使用前，机器都会复位在每次使用前，机器都会复位

4、VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz3自动售货机自动售货机FSMNDResetClockOpen硬币传感器硬币传感器商品释放机制商品释放机制1 1、理解问题、理解问题假设：投入假设：投入5 5美分，在美分，在单个周期内单个周期内N N为真；投为真；投入入1 1角，在单个周期内角，在单个周期内D D为真；在上一次复位之为真；在上一次复位之后，若收到后，若收到1515美分或更美分或更多，则状态机多，则状态机OpenOpen为真，为真，并保持一个周期并保持一个周

5、期例：简单的自动售货机例：简单的自动售货机2 2、有限状态机抽象表达、有限状态机抽象表达列出最终能给出商品的输入顺序列出最终能给出商品的输入顺序: :3 3个个5 5美分：美分：N N，N N，N N2 2个个5 5美分，再美分，再1 1角：角：N N，N N，D D1 1角，角，5 5分：分：D D，N N5 5分，分，1 1角：角：N N，D D2 2个个1 1角：角：D D，D D画状态图画状态图: :输入输入: N, D, reset, clk: N, D, reset, clk输出商品输出商品: open: open假设假设: :假设信号假设信号N N和和D D从来不会同时为真从来不

6、会同时为真省略了自环省略了自环 N=D=0 (no coin)N=D=0 (no coin)只将只将openopen信号为真时列出信号为真时列出VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz4S0ResetS2DS6openDS4openDS1NS3NS5openNS8openDS7openN例：简单的自动售货机例：简单的自动售货机3 3、状态最简化：、状态最简化：状态状态S4S4S8S8具有等价，可合并成一个状态具有等价，可合并成一个状态每个状态表示接受到钱的数量

7、每个状态表示接受到钱的数量VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz5最简化的符号状态转换表最简化的符号状态转换表presentinputsnextoutputstateDNstateopen 000 0001 501010011 500 5001100101501110001000115010150111515100Reset50NNN + D100D15openD状态图状态图状态转换表状态转换表例：简单的自动售货机例：简单的自动售货机4 4、进行状态分配、进

8、行状态分配 4 4个状态，采用个状态，采用2 2位状态编码：位状态编码： 0 0（0000）、）、 5 5（0101）、）、 1010（1010）、）、 1515（1111）VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz6当前状态当前状态输入输入 次态次态 输出输出tQ1 Q0DND1 D0open 0000 000010101010011 0100 010011001011011 1000 100011101011011 11 111状态分配后的状态转换表状态分配

9、后的状态转换表简单的自动售货机简单的自动售货机(VERILOG)module autosell (clk, reset, D, N,open); input clk, reset, D,N; output open; parameter cell0= 2b00，cell5 = 2b01, cell10= 2b10, cell15 = 2b11;reg 2:1 state;reg 2:1 next_state;always (posedge clk) if (reset) state = cell0; else state = next_state;always (N or D or state

10、) case (state) cell0: begin if (N) next_state = cell5;else if (D) next_state = cell10; else state = cell0; endVIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz7cell5: begin if (N) next_state = cell10;else if (D) next_state = cell15; else state = cell10; endcell

11、10: begin if (N) next_state = cell15;else if (D) next_state = cell15; else state = cell10; endcell15:next_state = cell15; endcaseassign open=(state= cell15); endmodule例：简单的自动售货机例：简单的自动售货机逻辑电路逻辑电路VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz8D1 = Q1 + D + Q0

12、 ND0 = Q0 N + Q0 N + Q1 N + Q1 DOPEN = Q1 Q000110111XX1X1111Q1D1Q0ND01101011XX1X0111Q1D0Q0ND00100010XX1X0010Q1OpenQ0ND5 5、实现、实现例：简单的自动售货机例：简单的自动售货机单点编码单点编码VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz9present state inputsnext stateoutputQ3Q2 Q1Q0DND3D2 D1D0

13、open0 00100000100100100100100011-0 01000001000101000101000011-0 10000010000110000101000011-1 000-10001D0 = Q0 D ND1 = Q0 N + Q1 D ND2 = Q0 D + Q1 N + Q2 D ND3 = Q1 D + Q2 D + Q2 N + Q3OPEN = Q3状态简化的等价状态状态简化的等价状态等价状态等价状态: :设设S Si i、S Sj j为两个原始状态，当它们满足以下条件时等效。为两个原始状态，当它们满足以下条件时等效。对于所有的输入组合对于所有的输入组合 输出

14、相同输出相同 它们的次态属于下列情况之一它们的次态属于下列情况之一 A A次态相同。次态相同。S Si i、S Sj j的次态均为的次态均为S Sk k B B次态交错或为各自的现态。次态交错或为各自的现态。 交错：交错：S Si i的次态为的次态为S Sj j，S Sj j 的次态为的次态为S Si i 。 为各自的现态：或为各自的现态：或S Si i的次态为的次态为S Si i，S Sj j的次态为的次态为S Sj j 。等效类等效类：由若干等效状态构成的集合。等效类中任意两个状态均等效。若存在关：由若干等效状态构成的集合。等效类中任意两个状态均等效。若存在关系，系，(S(S1 1，S S

15、2 2 ) )，(S(S2 2，S S3 3 ) (S) (S1 1，S S3 3 ) )，则，则 S S1 1、S S2 2、S S3 3 属于同一等效类。属于同一等效类。 记记作作 (S(S1 1，S S2 2 ) )，(S(S2 2，S S3 3 ) | S) | S1 1、S S2 2、S S3 3 | |。最大等效类：最大等效类：一个等效类不是其他等效类的子集，则该等效类为最大等效类。一个等效类不是其他等效类的子集，则该等效类为最大等效类。VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello an

16、d Randy H. Katz10状态简化：对原始状态表进行简化，消去多余状态，求得最小化状态表。状态简化：对原始状态表进行简化，消去多余状态，求得最小化状态表。状态简化目标状态简化目标 识别和结合有等价行为的状态识别和结合有等价行为的状态状态化简方法状态化简方法行匹配法：一种良好的人工推导方法，但行匹配法：一种良好的人工推导方法，但并不是总能得到最简状态表并不是总能得到最简状态表蕴含表法：容易用软件实现，并确实能找蕴含表法：容易用软件实现，并确实能找到可能的最优解到可能的最优解可同时应用这两种方法：可同时应用这两种方法： 行匹配法能快速化简，减少状态数目。行匹配法能快速化简，减少状态数目。接

17、下来用蕴含表法，由于只针对更少的状接下来用蕴含表法，由于只针对更少的状态，因此能迅速找到行匹配法遗漏的等价态，因此能迅速找到行匹配法遗漏的等价状态状态VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz11行匹配算法概述行匹配算法概述算法概述算法概述（由状态转换表开始对状态进行化简）（由状态转换表开始对状态进行化简）1. 1. 对状态进行分组，每组中的状态具有相同的对状态进行分组，每组中的状态具有相同的输出输出2. 2. 检查转换表，查看各组中的状态是否对于所检查转换表，

18、查看各组中的状态是否对于所有的输入组合都进入等价的次态，若等价可将它有的输入组合都进入等价的次态，若等价可将它们合并成一个状态，并重新命名。们合并成一个状态，并重新命名。3.3.然后将所有的状态转换过程都指向这些新状态然后将所有的状态转换过程都指向这些新状态4.4.重复以上过程，直到再也没有状态可以合并重复以上过程，直到再也没有状态可以合并VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz12行匹配法例子行匹配法例子仅通过观察状态表就能判断状态等效仅通过观察状态表就能判

19、断状态等效VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz13化简后的状态表化简后的状态表行匹配法化简例子行匹配法化简例子4 4比特序列检查器比特序列检查器初始状态图初始状态图该状态机具有单一输入该状态机具有单一输入X X和输出和输出Z Z，如果每次接收的，如果每次接收的4 4比特输入为比特输入为01100110或或10101010中的中的一个，则输出为一个，则输出为1 1。状态机每次接收比特输入后回到复位状态。状态机每次接收比特输入后回到复位状态。假设用米利型机实现

20、：假设用米利型机实现：只有在之前的比特输入匹配指定串中的任意一个，输出才为只有在之前的比特输入匹配指定串中的任意一个，输出才为状态机只在每位比特一组输入后才决定是否输出状态机只在每位比特一组输入后才决定是否输出VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz14q原始状态图原始状态图状态表和行匹配法状态表和行匹配法状态表：每个状态对应一行，每列对应不同的输入组合的次态和状态表：每个状态对应一行，每列对应不同的输入组合的次态和输出输出VIII - Working wit

21、h Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz15行匹配法行匹配法检查状态转换表中的每一行，寻找具有相同次态和输出的状态检查状态转换表中的每一行，寻找具有相同次态和输出的状态VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz16nS10S10和和S12S12具有相同次具有相同次态和输出的状态，可以态和输出的状态，可以合并成新状态名合并成新状态名S10S10nS7S7，S8S8，

22、S9S9， S11S11，S13S13，S14 S14 均具有相同均具有相同的次态和输出，可能合的次态和输出，可能合并成新状态并成新状态S7S7行匹配法迭代行匹配法迭代合并后的新状态表合并后的新状态表 再对再对S3S3，S6S6进行合并，用进行合并，用S3S3表示表示 对对S4S4，S5S5进行合并，用进行合并，用S4S4表示表示VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz17n合并后的新状态合并后的新状态表，不能再用行匹表，不能再用行匹配法进行合并配法进行合并n

23、将将1515个状态化简个状态化简为仅为仅7 7个状态个状态行匹配法化简得到的状态图行匹配法化简得到的状态图行匹配法的局限性行匹配法的局限性 并不是总能得到最简化并不是总能得到最简化的状态的状态VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz18蕴含表方法蕴含表方法蕴含表化简的步骤为：蕴含表化简的步骤为：作隐含表、寻找等效对、作隐含表、寻找等效对、求出最大等效类、作出最小化状态表。求出最大等效类、作出最小化状态表。 作初始蕴含表作初始蕴含表 蕴含表为直角三角型网格，表中

24、的方格用状态名称标注。横蕴含表为直角三角型网格，表中的方格用状态名称标注。横向从左到右的状态顺序依次为第一个到倒数第二个状态，纵向从向从左到右的状态顺序依次为第一个到倒数第二个状态，纵向从上到下的状态顺序为第二到最后一个状态，每个方格代表一个状上到下的状态顺序为第二到最后一个状态，每个方格代表一个状态对态对 寻找等效对寻找等效对 进行两轮比较，先进行顺序比较，再进行关联比较进行两轮比较，先进行顺序比较，再进行关联比较VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz19

25、蕴含表化简蕴含表化简是一种更系统的方法，它寻找能够合并成单一状态的是一种更系统的方法，它寻找能够合并成单一状态的所有状态所有状态蕴含表方法蕴含表方法 顺序比较：对照原始状态表，对所有状态进行检查比较。若状态对等顺序比较：对照原始状态表，对所有状态进行检查比较。若状态对等效，在方格中打效，在方格中打 “ ”；若不等效，在方格中打；若不等效，在方格中打 “ ”；与其他状；与其他状态对相关，有待进一步检查，在方格中填上待检查状态对。态对相关，有待进一步检查，在方格中填上待检查状态对。 关联比较：确定待检查状态对是否等效，由此确定原状态对是否等效。关联比较：确定待检查状态对是否等效，由此确定原状态对是

26、否等效。若方格内有一状态对不等效，则用若方格内有一状态对不等效，则用 “”标志。标志。 求出最大等效类求出最大等效类 利用等效状态的传递性，通过合并求出最大等效类。原始状态表中的利用等效状态的传递性，通过合并求出最大等效类。原始状态表中的每个状态都应该属于一个最大等效对。每个状态都应该属于一个最大等效对。 作出最小化状态表作出最小化状态表 将每个最大等效类中的全部状态合并为一个状态，可得与原始状态表将每个最大等效类中的全部状态合并为一个状态，可得与原始状态表等价的最小化状态表。等价的最小化状态表。VIII - Working with Sequential Logic Copyright 20

27、04, Gaetano Borriello and Randy H. Katz20蕴含表方法化简实例蕴含表方法化简实例VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz21现态次态 / 输出x = 0 x = 1 ABCDEFGC / 0F / 0F / 0D / 0C / 0C / 0C / 1B / 1A / 1G / 0E / 0E / 1G / 0D / 0对表中状态进行顺序比较，根据等对表中状态进行顺序比较，根据等效状态判别标准进行判别。效状态判别标准进行判别

28、。状态状态C C、F F输出相同，输出相同，x=0 x=0时次态交错，时次态交错， x =1x =1时次态相同，故时次态相同，故C C、F F为等效对，在为等效对，在相应方格中打相应方格中打 “ ” 状态状态 A A、F F不满足等效条件，不满足等效条件，在相应方格中打在相应方格中打“”。状态。状态A A、E E满足输出相同条件，当满足输出相同条件，当x=0 x=0时时次态相同，但当次态相同，但当x=1x=1时次态分别时次态分别为为B B、E E，当前无法判定，当前无法判定B B、E E 是是否等效，因此在方格中填入否等效，因此在方格中填入BEBE。 经比较后，还有经比较后，还有A A、B B

29、；A A、E E；B B、E E；D D、G G共共4 4个状态对尚未确个状态对尚未确定是否等效，因此应进行关联定是否等效，因此应进行关联比较。比较。 状态状态A A、B B对应的方格中次态对应的方格中次态对为对为C C、F F，由顺序比较已知，由顺序比较已知C C、F F等效，故等效，故A A、B B等效，在对应的等效，在对应的方格中打方格中打“ ”。检查。检查A A、E E状态对，出现循环关系：状态对，出现循环关系：AEBECFAEBECF。已知。已知C C、F F等效，等效，故故B B、E E等效。等效。BEBE又与又与AEAE构成循构成循环，故环，故A A、E E等效，在对应的方等效，

30、在对应的方格中打格中打 “ ”。 构造初始蕴含表构造初始蕴含表 寻找等效对寻找等效对VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz22由造出的初始蕴含表可知，由造出的初始蕴含表可知，7 7 个状态共有个状态共有 4 4 个等效对个等效对 ( A( A，B )B )、( A( A，E )E )、( B( B，E )E )、( C( C，F )F )。 求出最大等效类求出最大等效类由所得由所得 4 4 个等效对可知，个等效对可知，( A( A，B )B )、( A( A

31、，E )E )、( B( B，E ) E ) 构成最大等效类构成最大等效类 A A，B B，E E 。 ( C( C，F ) F ) 不包含在其他等效类中，也是一个最大等效类。状态不包含在其他等效类中，也是一个最大等效类。状态 D D、G G 不和其他状态等效，故各自构成最大等效类。不和其他状态等效，故各自构成最大等效类。原始状态表中原始状态表中 7 7 个状态构成个状态构成 4 4 个最大等效类，个最大等效类，分别为：分别为： 现态次态 / 输出 x = 0 x = 1 abcdb / 0b / 0c / 0b / 1a / 1d / 0a / 0c / 0 A，B，E 、 C，F 、 D

32、、 G a b c d 作出最小化状态表作出最小化状态表将将4 4个最大等效类分别用个最大等效类分别用 a a、b b、c c、d d 表示，表示，代入原始状态表，可得化简后的最小化状态表。代入原始状态表，可得化简后的最小化状态表。用蕴含表化简用蕴含表化简 由状态转由状态转移表构造移表构造初始蕴含初始蕴含表表VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz23 寻找等效寻找等效由造出的初始蕴含表可知，由造出的初始蕴含表可知，1 1 个等效对个等效对 ( D( D，E

33、)E ) 求出最大等效类求出最大等效类 (D(D，E)E)用用D D表示表示 作出最小化状态作出最小化状态表表蕴含表方法化简实例蕴含表方法化简实例VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz24输入输入 次态次态 输出输出序列序列当前状态当前状态 X=0 X=1 X=0 X=1ResetS0S1 S2 0 00S1S3 S4 0 01S2S5 S6 0 000S3S0 S0 0 001S4S0 S0 1 010S5S0 S0 0 011S6S0 S0 1 03 3

34、比特序列检测器，当检测到比特序列检测器，当检测到010010或或110110时输出为时输出为1 1根据要求列出初始状态表根据要求列出初始状态表 由状由状态转移态转移表构造表构造初始蕴初始蕴含表含表 寻找等效寻找等效蕴含表方法化简实例蕴含表方法化简实例VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz25 求出最大等效类求出最大等效类 (S1，S2)用用S1表示表示(S3，S5)用用S3表示表示(S4，S6)用用S4表示表示 作出最小化状态作出最小化状态表表Input N

35、ext State OutputSequencePresent StateX=0X=1X=0X=1ResetS0S1S1000 + 1S1S3S400X0S3S0S000X1S4S0S010S0S1S3S4X/01/01/00/10/0X/0更复杂状态图的化简更复杂状态图的化简多输入状态图和转换表多输入状态图和转换表VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz26符号状态转换表符号状态转换表 present next state output state00011

36、011 S0S0S1S2S31 S1S0S3S1S40 S2S1S3S2S41 S3S1S0S4S50 S4S0S1S2S51 S5S1S4S0S50inputs here1001110000011110100111001000110011100110110100S01S21S41S10S30S5001S0-S1 S1-S3 S2-S2 S3-S4 S0-S0 S1-S1 S2-S2 S3-S5 S0-S1 S3-S0 S1-S4 S4-S5 S0-S1 S3-S4 S1-S0 S4-S5 S1-S0 S3-S1 S2-S2S4-S5 S4-S0S5-S5 S1-S1 S0-S4 S1 S2

37、S3 S4 S5S0S1S2S3S4 由状态转移表构由状态转移表构造初始蕴含表造初始蕴含表 寻找等效寻找等效更复杂状态图的化简VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz27minimized state table(S0=S4) (S3=S5)present next state output state00011011 S0S0 S1S2S31 S1S0 S3S1S30 S2S1S3S2S01 S3S1S0S0 S30 求出最大等效类求出最大等效类 (S0，S

38、4)用用S0表示表示(S3，S5)用用S3表示表示present next state output state00011011 S0S0S1S2S31 S1S0S3S1S40 S2S1S3S2S41 S3S1S0S4S50 S4S0S1S2S51 S5S1S4S0S50 作出最小化状态表作出最小化状态表状态分配状态分配状态分配是选择二进制位向量分配给每个符号状态状态分配是选择二进制位向量分配给每个符号状态如果如果m m个状态用个状态用n n位来对状态进行编码，则可能的分配方案有位来对状态进行编码，则可能的分配方案有2 2n n!/(2!/(2n n m)! m)! 简单的按照二进制顺序来进行

39、状态分配，设计者仅需要保证每简单的按照二进制顺序来进行状态分配，设计者仅需要保证每个状态对应唯一的编码，以保证组合逻辑能区分各个状态个状态对应唯一的编码，以保证组合逻辑能区分各个状态单点编码是用单点编码是用m m位状态位编码位状态位编码m m个状态，每个状态的单点编码只个状态，每个状态的单点编码只有在对应的位上为有在对应的位上为1 1，在其它位上均为，在其它位上均为0 0启发式编码能实现良好的状态分配，但不能保证是好的电路实启发式编码能实现良好的状态分配，但不能保证是好的电路实现现VIII - Working with Sequential Logic Copyright 2004, Gaet

40、ano Borriello and Randy H. Katz28 实现时序逻辑网络所需门的数量严重依赖于如何将编码后实现时序逻辑网络所需门的数量严重依赖于如何将编码后的逻辑值分配给符号状态，最优的分配方案的唯一途径是尝试的逻辑值分配给符号状态，最优的分配方案的唯一途径是尝试所有的分配方案所有的分配方案状态分配策略状态分配策略可能的策略可能的策略顺序编码顺序编码随机编码随机编码单点编码单点编码面向输出的编码面向输出的编码启发式编码启发式编码不能保证结果是最优的不能保证结果是最优的 另一个复杂的问题另一个复杂的问题VIII - Working with Sequential Logic Copy

41、right 2004, Gaetano Borriello and Randy H. Katz29顺序编码顺序编码简单的将符号状态名字替换成为规则的编码，简单的将符号状态名字替换成为规则的编码，设计者仅需要保证每个状态对应唯一的编码，设计者仅需要保证每个状态对应唯一的编码，以保证组合逻辑能够区分各个状态以保证组合逻辑能够区分各个状态VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz30单点编码单点编码简单简单容易编码、容易诊断和修改容易编码、容易诊断和修改小规模的逻辑函

42、数小规模的逻辑函数每个状态位对应方程中所含或项的数目和状态图中指向该状态的所有弧对应项每个状态位对应方程中所含或项的数目和状态图中指向该状态的所有弧对应项的总数相同的总数相同适合于适合于FPGAFPGA实现实现大量的触发器可用大量的触发器可用对大的状态机不实用对大的状态机不实用太多的状态需要太多的太多的状态需要太多的flip-flopsflip-flops对大的有限状态机划分成小块可用单点编码对大的有限状态机划分成小块可用单点编码对单点编码进行一些改变对单点编码进行一些改变one-hot + all-0one-hot + all-0VIII - Working with Sequential

43、Logic Copyright 2004, Gaetano Borriello and Randy H. Katz31 用用m m位状态位编码位状态位编码m m个状态，每个状态的单点编码只有在对应个状态，每个状态的单点编码只有在对应的位上为的位上为1 1，在其它位上均为，在其它位上均为0 0随机编码随机编码这是更简单的策略，随机选择可能的编码进这是更简单的策略，随机选择可能的编码进行分配，它仅需要保证每个状态对应唯一的行分配，它仅需要保证每个状态对应唯一的编码，以保证组合逻辑能够区分各个状态编码，以保证组合逻辑能够区分各个状态VIII - Working with Sequential Log

44、ic Copyright 2004, Gaetano Borriello and Randy H. Katz32VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz33面向输出的编码面向输出的编码n对于摩尔型，输出直接与状态位有关，但如果设对于摩尔型，输出直接与状态位有关，但如果设计者直接实现摩尔型输出计者直接实现摩尔型输出( (即触发器的输出就是状即触发器的输出就是状态机的输出），则可以使用输出来区别状态态机的输出），则可以使用输出来区别状态n同步米利型输出也是通过触发

45、器的输出直接实现，同步米利型输出也是通过触发器的输出直接实现，因此也可以这样用因此也可以这样用n对于整个状态机都使用面向输出的编码方式并不对于整个状态机都使用面向输出的编码方式并不是很好的策略，明智的使用部分输出作为编码，是很好的策略，明智的使用部分输出作为编码，也许能减少状态位的数量也许能减少状态位的数量启发式方法启发式方法该方法试图缩短相关状态间的布尔空间的距离。如状态该方法试图缩短相关状态间的布尔空间的距离。如状态Y Y用状用状态态X X转换而来，则它们的状态编码中的不同比特位应尽量少转换而来，则它们的状态编码中的不同比特位应尽量少状态图：类似于卡诺图，提供观察状态分配的相邻性的方法状态

46、图：类似于卡诺图，提供观察状态分配的相邻性的方法。VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz34 状态图中的方格按状态图中的方格按照状态位的二进制值照状态位的二进制值进行索引，给出该编进行索引，给出该编码的状态便放在图中码的状态便放在图中对应的的方格里（最对应的的方格里（最多能处理多能处理2 26 6个状态）个状态）最少位变化启发式方法最少位变化启发式方法目的是使所有状态间的转换中发生变化的位数最少目的是使所有状态间的转换中发生变化的位数最少第二种分配方案：第二

47、种分配方案： 分配分配S0S0，由于复位逻辑工作，通常将全，由于复位逻辑工作，通常将全0 0分配给起始状态分配给起始状态 接下来分配接下来分配S1S1、S2S2，将它们放在，将它们放在S0S0邻近位置邻近位置 然后将然后将S3S3放在放在S1S1、S2S2之间之间 最后将最后将S4S4放在放在S3S3附近附近VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz35基于次态和输入基于次态和输入/输出的启发式方法输出的启发式方法最高优先级：在给定的输入转换条件下，具有相同次态的状态应最高优先级：在给定的输入转换条件下，具有相同次态的状态应该在状态图中放到邻近的位置该在状态图中放到邻近的位置中等优先级：具有相同现态的次态应放在状态图中邻近的位置中等优先级：具有相同现态的次态应放在状态图中邻近的位置最低优先级：在给定输入的情况下，具有相同输出的状态应该放最低优先级：在给定输入的情况下，具有相同输出