三段式状态机_对数字电路中状态机设计抽象层面的思考

没有什么控制逻辑是一个状态机解决不了的，如果不行，那就来两个。

检测序列是面试官最爱的状态机题目了，不啰嗦了。甚至有个变形的题目：如果判断一个不停输入的序列是否可以被某个数整除？本质还是状态转换，只是这时候状态不是序列组合而是模几的一个状态，通过下一个数x2或x2+1转到下一个状态。

状态机在数字逻辑电路设计中的作用怎么强调都不为过。关于状态机的参考资料也一抓一大把，不再赘述。今天我来谈谈对数字电路中状态机设计抽象层面的思考。抽象的层次够了，万物皆可比较。 顺带提一句，《可重构计算》里把ASIC归入冯诺伊曼体系的一个特例，我认为是没有问题的。确实，抽象到一定级别了，ASIC和CPU其实是一回事，硬件和软件的界限也没那么明显。

什么时候用状态机？当我需要一个控制信号，这个信号并不能直接根据当前的输入得到，而后面要输出这个控制信号又得依赖以前的状态。显然，一个状态机至少有两个状态（为什么？一个状态的话就没有状态转移，任何控制信号均直接依赖输入可得）。

比如说，简单的valid, ready握手。假设我要转发某个数据接收电路里产生的数据，为了不造成上游的堵塞，我先把它接收下来（即给上游ready），然后需要传给下游的电路，这就是一个简单的转发器。

那发送数据的valid信号不仅依赖于上游的valid信号和下游的ready信号，还依赖于这些信号的发生时机。于是我们有了两个状态：IDLE和等待下游ready到来的状态。那下游ready信号如果一直是高呢？那就一直在IDLE好了。写成标准状态机模式是这样的：

typedef enum {IDLE, WAIT} state_t;

state_t state_d, state_q;
logic down_valid, up_ready;

always_ff @(posedge clk or negedge rst_n)
begin
  if (rst_n) begin
    state_q <= IDLE;
  end
  else begin
    state_q <= state_d;
  end
end

always_comb
begin
  state_d = state_q;
  down_valid = 1'b0;
  up_ready = 1'b0;
  case (state_q)
    IDLE: begin
      up_ready = 1'b1;
      if (up_valid) begin
        down_valid = 1'b1;
        if (!down_ready) begin
          state_d = WAIT;
        end
      end
    end
    WAIT: begin
      down_valid = 1'b1;
      if (down_ready) begin
        state_d = IDLE;
      end
    end
  endcase
end

这就是传说中的“两段式写法”了，个人比较推荐这种写法，明了易懂，一段式、三段式都是其变形。三段式就是把里面的信号单独再抽出来写一段，一段式则是把组合部分全部揉进时序逻辑段中（当然有些组合信号还得拿出来单独写）。

我们看到这里面只有两个状态，状态机综合出来的状态也只有一比特，那么我肯定可以只用一个DFF来实现这个状态机，我们换个写法：

logic lock_down_valid_d, lock_down_valid_q;
logic down_valid, up_ready;

always_ff @(posedge clk or negedge rst_n)
begin
  if (rst_n) begin
    lock_down_valid_q <= 1'b0;
  end
  else begin
    lock_down_valid_q <= lock_down_valid_d;
  end
end

always_comb
begin
  lock_down_valid_d = lock_down_valid_q;
  down_valid = 1'b0;
  up_ready = 1'b1;
  if (lock_down_valid_q) begin
    down_valid = 1'b1;
    up_ready = 1'b0;
    if (down_ready) begin
      lock_down_valid_d = 1'b0;
    end
  end
  else if (up_valid) begin
    down_valid = 1'b1;
    if (!down_ready) begin
      lock_down_valid_d = 1'b1;
    end
  end
end

其实这段逻辑本质上和上面的两段式状态机写法是一模一样的。

小样，披了件马甲，我就不认识你了？

lock_down_valid_q就是state_q本尊，二者综合出来的电路完全相同，用formal工具都可以比通过的。

所以从本质上讲，可以用状态机实现的电路，我可以将其状态打散成单独的状态bit，分别实现。理论上一个状态机最少多少个状态，我就可以用多少比特的单独的状态来实现，状态转移则是蕴含在各个单独状态的实现逻辑之中。 这在理论上是可行的，实际则不容易把握，不直观且容易出错。 再说了，单独的状态bit不就是one-hot的状态机嘛，同样的电路两种形式而已。

有的同学发现了，上面电路实现的功能用一个entry的FIFO（支持pass-through的FIFO）就能实现：

assign down_valid = ~fifo_empty | (~fifo_full & up_valid);
assign fifo_pop = down_ready & ~fifo_empty;
assign fifo_push = up_valid & ~fifo_full;
assign up_ready = ~fifo_full;

似乎就不用状态机了？我们说，不管形式是怎么样的，哪怕是一个FIFO，它实现的仍然是状态机的功能。只不过把状态机的逻辑转移到FIFO里面去了。一个entry的FIFO的fifo_full即是~fifo_empty，此时是不是fifo_full这个DFF即是lock_down_valid_q或state_q本尊了？从down_valid和up_ready信号的生成逻辑即可推出此结论，算是人工formal了。（FIFO附带把数据也存上了，前面的状态机实现要单独写存数据的时序电路）。FIFO如果不用DFF能做得到吗？做不到。该时序逻辑做的事情组合逻辑永远完不成。而使用时序逻辑的控制电路就是状态机。还是那句：

小样，披了件马甲，我就不认识你了？

掌握状态机的本质，可以让你的数字电路设计如鱼得水，得心应手。