HDLBits刷题笔记

以下是在做HDLBits时的一些刷题笔记，截取一些重要内容并加上自己的理解，方便以后翻阅查找

Circuits

Fsm1

到状态机了，这在FPGA设计部分是核心的核心，一定要好好学！好好学！好好学！

我们之前的笔记提到过，想要利用HDL这种并行处理语言完成顺序的逻辑功能是有两个成熟的方法论的。一个是状态机（State Machine），另一个是流水线（Pipeline）。这两种方法论在数学上的表达区别就是状态机的状态state一定是可以组成环形的，而流水线的阶段stage首尾不会相连，如下就是二者在逻辑拓扑上的区别：

基本上就是状态机是一个不断循环的机器，而流水线就是一条顺序的数据处理线，不会有循环结构出现。由于这篇笔记的重点不是流水线，就先简单介绍一下流水线，之后的大篇幅都留给状态机就好。流水线其实可以非常简单，一个寄存器就可以看作一个简单的一阶流水线，例如如下代码：

reg [7:0]r;
reg [7:0]r_buf;
always@(posedge clk)beginr_buf <= r;
end

大家不要看这个代码简单，其实在项目中用得很多，而且一般的项目就是用一阶或二阶寄存器组成流水线，用来寄存数据或者优化时序。

当然，如果你学过微机原理，应该听过CPU为了加快数据处理速率会有高阶流水线。没错，CPU里流水线的概念和FPGA里的完全一致，我们甚至可以用FPGA实现一个CPU流水线，进而完成CPU的功能。如果大家好奇，可以在网上找一找OpenMIPS的书籍和资料，里面就用FPGA实现了一个简单的五级流水线CPU。

通过上述两个简单的例子，大家应该也能看出流水线的核心就是输出的处理和流动，它主要就是关注如何更快地处理一件事。简而言之，流水线是一个加速器。在技术实现上，流水线可以将一个复杂的组合电路分开，并在模块之间通过寄存器存储，这样，多个数据就可以在同一时间处于该任务的不同处理阶段，极大地提高了数据处理的吞吐率。在本质上，流水线就是将一个复杂的组合逻辑路分解成小阶段stages，并在每个阶段之间插入寄存器。而流水线的常见工作场景就是那些需要高速数据处理甚至需要优化时序的场景（高速场景下时序收敛会变困难），例如：1.高速的通信领域需要流水线优化时序;2.数字信号处理或者复杂的算数运算实现；3.图像和视频处理；4.CPU指令处理流水线。

好了，关于流水线就记这么多笔记，因为一般来说对于通用的FPGA编程，流水线最常见的作用就是添加几个寄存器用来优化时序。至于想要学习像DSP、图像视频处理、CPU这类细分领域的流水线，就要学习专业领域的内容了，通用性并不强。

接下来就都是关于状态机的内容了。状态机的重要程度要比流水线高得多，原因就是状态机是一套非常通用的方法论，你也许不需要在高速场景下编程，所以可能用不到流水线；但只要你想实现任何稍微复杂点的任务或功能，无论是在高速还是低速，抑或是通信或者IC等不同领域，你都离不开状态机，它在FPGA编程中几乎无处不在。 先说一下什么是状态机。状态机，全称有限状态机（Finite State Machine, FSM），描述了一个设备在有限数量的状态之间转换的行为。我们刚刚了解了流水线，那就接着话茬，如果说流水线是一个加速器，那么状态机就是一个控制器，关注的是“何时”做什么事。

状态机的核心作用是根据当前的状态和外部输入，来决定下一步的操作和要转换到的状态。它本质上是一个时序控制器，非常适合用于实现任何涉及多个步骤、需要决策或遵循特定顺序的任务。对于任何状态机，都有三个重要的组成：一定数量的状态、状态间跳转的条件以及状态机的输出。对于如何状态机输出方式的不同，可以进一步细分为Moore型与Mealy型状态机，如下是二者的根本区别：

状态机类型	Moore型	Mealy型
输出决定因素	输出仅取决于当前的状态	输出取决于当前状态和当前的输入

到现在为止就是有关状态机的主要理论知识。但是还不够，我们需要用Verilog代码实现呀！假设我们现在要完成一个最最简单的状态机，那就是去检测2’b10序列，只要检测到2’b10序列，我们就输出一个1。在这个例子中我们选用Mealy型状态机。那么写的思路是怎样的呢？状态机状态机，那我们需要状态呀，我可以定义IDLE(初始状态)和GOT_1（检测到1’b1）两个状态，这部分可以用parameter来实现。状态机初始化在IDEL状态，只要检测到1，我们就进入GOT_1状态。而到了GOT_1状态，我们就立刻检查输入，如果输入是0，我们就检测到了10序列，反之我们重新进入IDEL状态。将上述语言转化为代码就是如下效果：

module fsm_1_segment(input  wire clk,input  wire rst,input  wire din,output reg  dout
);parameter IDLE = 1'b0, GOT_1 = 1'b1; //状态定义reg current_state;always @(posedge clk or posedge rst) beginif (rst) begincurrent_state <= IDLE;dout          <= 1'b0;end else begin// 默认输出为0dout <= 1'b0;case (current_state)IDLE:if (din)current_state <= GOT_1;// else, current_state保持不变GOT_1:if (!din) begindout          <= 1'b1; // 检测到'0'，立即输出1current_state <= IDLE;  // 同时返回IDLEend elsecurrent_state <= GOT_1; // 如果是'1'，保持在GOT_1endcaseendend
endmodule

这种最直接在一个时序always块中实现状态机的写法就称为一段式状态机，其实在这个简单例子的情况下看上去逻辑还算清晰。但如果仔细阅读代码你就会发现两个问题：第一个问题是由于整个块是写在时序always块中的，所以dout也被综合成寄存器，这样就导致我们的输出不及时。我们举个例子，例如现在已经处于GOT_1状态，并且我输入了一个0，在这个时钟周期内我们是不会输出1的，需要等到下一个时钟周期dout才会被更新。或许这就是你想要的结果，但是在这个例子中我希望状态机能够及时响应我的输出，也就是说dout应该放在组合逻辑中进行赋值。

第二个问题是always块的复杂程度，我们这个简单的例子状态和输出变量比较少，但是如果状态多起来呢？状态跳转复杂起来呢？输入输出量多起来呢？全挤在一个时序always块中也不是个办法，那就尝试分离。怎么分离呢？我们可以想象，如果状态机的规模一旦变大，一段式状态机里就会全是各种状态跳转以及输出内容的条件判断，这些条件判断其实就是靠组合逻辑的各种逻辑门完成的,而我们时序always块中真正的寄存器其实就是current_state这个变量。所以一个简单的想法应运而生，我们试着把耦合在这个时序always块中的组合逻辑抽离出来，重新写在一个always@(*)中。当然也顺便把dout也写在这个组合逻辑块中，为了加快状态机的反应速度，于是有了下面的写法：

module fsm_2_segment(input  wire clk,input  wire rst,input  wire din,output reg  dout
);parameter IDLE = 1'b0, GOT_1 = 1'b1;reg current_state, next_state;// --- 第一段: 状态寄存器 (时序逻辑) ---always @(posedge clk or posedge rst) beginif (rst)current_state <= IDLE;elsecurrent_state <= next_state;end// --- 第二段: 状态跳转与输出逻辑 (组合逻辑) ---always @(*) begin// 必须赋默认值，防止生成锁存器next_state = current_state;dout       = 1'b0;case (current_state)IDLE:if (din)next_state = GOT_1;GOT_1:if (!din) begindout       = 1'b1; // 检测到'0'，输出1next_state = IDLE;end elsenext_state = GOT_1;endcaseend
endmodule

千万不要忘了之前的知识，虽然current_state和next_state在定义时都是reg类型，但是current_state是在时序always块中赋值，会被综合成一个真正的寄存器；而next_state写在always@(*)中，仍然是一个组合逻辑，只会被综合成线网和逻辑门的组合。

上面这种把状态寄存器的更新与状态跳转和输出逻辑分离的状态机写法就被成为二段式状态机。这样做略微提升了代码的可读性，但是你仔细想想就会发现这样做并没有解决根本问题，因为状态跳转和输出逻辑才是状态机中占行数最多的部分，这两部分现在仍然挤在一个always(*)块中。一段式状态机会有一个臃肿的时序always块，而二段式状态机产生了一个臃肿的alway@(*)块。那么可以再优化一点吗？当然可以，我们接着把状态跳转和输出逻辑拆成独立的两个alway@(*)进行赋值就好了，所以有了如下写法：

module fsm_3_segment(input  wire clk,input  wire rst,input  wire din,output reg  dout
);parameter IDLE = 1'b0, GOT_1 = 1'b1;reg current_state, next_state;// --- 第一段: 状态寄存器 (时序逻辑) ---always @(posedge clk or posedge rst) beginif (rst)current_state <= IDLE;elsecurrent_state <= next_state;end// --- 第二段: 下一状态逻辑 (组合逻辑) ---always @(*) beginnext_state = current_state; // 默认保持当前状态case (current_state)IDLE:if (din)next_state = GOT_1;GOT_1:if (!din)next_state = IDLE;endcaseend// --- 第三段: 输出逻辑 (组合逻辑) --- 与二段式状态机波形相同always @(*) begindout = 1'b0; // 默认输出为0if (current_state == GOT_1 && !din)dout = 1'b1;end/* --- 第三段：输出逻辑（时序逻辑）--- 与一段式状态机波形相同always @(posedge clk or posedge rst) beginif(rst)dout <= 1'b0;else if (current_state == GOT_1 && !din)dout <= 1'b1;end*/
endmodule

这样做就清晰多了，这种将状态寄存器、下一状态逻辑、输出逻辑分成三个独立部分的写法可维护性强了不少，被称为三段式状态机。大家观察不难发现，三段式状态机的输出其实既可以写成时序逻辑（慢一拍输出，和一段式状态机一样），也可以写成组合逻辑（当前时钟周期输出，和二段式状态机一样），这样的灵活度大大提高，即三段式完全可以替代一段式和二段式状态机，但一段式和二段式状态机相互之间不能替代。一般来说，在公司里做落地项目的，都是使用三段式状态机写法。学习或者不太严谨的项目中，那就无所谓了，但是还是建议使用三段式状态机。

我们这里给出三种状态机写法的区别：

状态机类型	状态改变	下一状态判断逻辑	输出逻辑
一段式	时序逻辑	（耦合在时序逻辑中的）组合逻辑	时序逻辑
二段式	时序逻辑	组合逻辑	组合逻辑
三段式	时序逻辑	组合逻辑	时序逻辑或者组合逻辑（取决于需要）

接下来给出三段式状态机的基本模板，其实挺公式化的，用用就记住了：

/*预备工作：状态定义+reg类型的两个state（注意位宽一致）*/
parameter IDLE = 2'00,STATE_0 = 2'01,STATE_1 = 2'10,...;
localparam PL_STATE_BITS = $(IDLE); //参数化保持位宽一致
reg[PL_STATE_BITS-1:0] current_state, next_state;/*第一段：状态更新 时序逻辑*/
always @(posedge clk or posedge rst) begin //可选同步和异步复位if (rst)current_state <= IDLE;elsecurrent_state <= next_state;
end/*第二段：条件跳转 组合逻辑*/
//这部分推荐使用case+if的组合
always @(*) beginnext_state = current_state; case (current_state)IDLE:if (...)next_state = ...;STATE_0:if (...)next_state = ...;endcase
end/*第三段：输出控制类型一 组合逻辑 当前时钟周期立刻输出*/
//这部分写法自由，也常用case+if的组合，当输出逻辑判断简单或输出情况很少时也常用assign + ?:的组合。但是一定注意对于assign，out_comb是wire类型；对于always，out_comb是reg类型。
always @(*) beginout_comb = 1'b0; // 默认输出为0if (current_state == ...)out_comb = ...;
end/*第三段：输出控制类型二 时序逻辑 下一时钟周期输出*/
always @(posedge clk or posedge rst)begin //可选同步和异步复位if (rst)out_ff <= ...;else if (current_state == ...)out_ff <= ...;
end

之后没啥意外就都用三段式状态机的写法了，养成一个好习惯。

现在我们知道了如何用Verilog实现一个状态机了，现在需要具体化一点，那就是如何用代码分别实现Moore型和Mealy型状态机，还是刚刚那个检测10序列的例子，如下是Moore型状态机：

module fsm_3_segment_moore(input  wire clk,input  wire rst,input  wire din,output wire dout // Moore型输出用wire更直观，可以用assign语句
);// 1. 状态定义: 增加了一个SUCCESS状态parameter IDLE    = 2'b00;parameter GOT_1   = 2'b01;parameter SUCCESS = 2'b10; // 新增状态，用于产生输出// 状态寄存器需要2位来表示3个状态reg [1:0] current_state, next_state;// --- 第一段: 状态寄存器 (时序逻辑) ---// 这部分结构完全不变，只是寄存器位宽变了always @(posedge clk or posedge rst) beginif (rst)current_state <= IDLE;elsecurrent_state <= next_state;end// --- 第二段: 下一状态逻辑 (组合逻辑) ---// 这部分逻辑需要修改以包含新的SUCCESS状态always @(*) beginnext_state = current_state; // 默认保持当前状态case (current_state)IDLE:if (din)next_state = GOT_1;GOT_1:if (!din)// 当检测到"10"中的'0'时，跳转到SUCCESS状态next_state = SUCCESS;else// 如果是"11"，则保持在GOT_1，因为这个'1'可以是新序列的开始next_state = GOT_1;SUCCESS:// 在成功状态停留一个周期后，必须离开// 如果当前输入是'1'，它可以是新序列的开始if (din)next_state = GOT_1;elsenext_state = IDLE;endcaseend// --- 第三段: 输出逻辑 (组合逻辑) ---// *** 这是从Mealy到Moore最核心的改变 ***// 输出只依赖于 current_state，与 din 无关。// 使用连续赋值语句 assign 会更简洁清晰assign dout = (current_state == SUCCESS);/*// 如果想继续使用always块的写法：always @(*) beginif (current_state == SUCCESS)dout = 1'b1;elsedout = 1'b0;end*/
endmodule

至于Mealy型状态机刚刚说到三段式状态机的时候就已经给出代码了。对比一下不难看出，Mealy型状态机由于输出可以受输入直接影响，所以在检测到1的时候就可以直接在组合逻辑中判断新输入的数据是否是0；Moore型状态机由于输出是不能受输入数据直接影响的，所以为了检测10序列必须多出一个状态用来确定10序列是否成功输入，进而影响输出。所以Mealy型状态机的优点就是快一些，完成同样的功能条件下，比Moore型状态机需要的状态数更少。但问题也很明显,Mealy状态机输出信号是异步的并且是组合逻辑，容易产生毛刺。至于Moore型状态机，他的输出完全在时序逻辑的控制下，所以虽然反应比Mealy类型慢，但是输出却稳定得多。于是，我们得到以下两种状态机的区别：

状态机类型	Moore型	Mealy型
输出决定因素	输出仅取决于当前的状态	输出取决于当前状态和当前的输入
输出时序	输出信号与时钟同步，通常在状态转换完成后才更新，因此输出是稳定的，不会出现毛刺	输出信号是异步的，对输入的任何变化都会立即做出反应，可能产生毛刺
状态数量	为了在不同输入下产生不同输出，可能需要更多的状态	通常可以用更少的状态来实现相同的功能
响应速度	对输入的响应会延迟一个时钟周期，因为输出需要等待下一个状态的到来	对输入的响应速度更快，可以在当前时钟周期内立即改变输出
硬件实现	通常更容易设计和调试，因为输出是可预测且稳定的	设计上可能更复杂，需要仔细处理时序问题，以避免由于输入信号的不稳定而导致错误的输出

围绕状态机控制能力强的特点，我们可以总结出以下常见应用场合：1.用户接口和通用事件处理（例如，实现一个自动售货机代码）；2.通信协议实现（ I2C、SPI、UART、CAN等协议实现）；3.控制单元和仲裁器(CPU的控制单元、DDR内存控制器、总线仲裁器);4.复杂算法的任务流程管理。等等。

有了这些知识储备，这一题的答案也就迎刃而解了，如下：

这一题还是比较简单，因为题目直接把A和B两个状态显式地给了出来，下一题就给出需要自己确定状态数了。

Fsm1s

这一记录一下主要是想要补充一个知识点，然后吐槽一下模板里的代码。先说补充的点吧，那就是状态机的表述方式，主要有四种方法：自然语言描述、状态转移表、状态转移图和HDL代码。

还是拿上面那个简单的2’b10序列检测状态机例子说明，用自然语言描述就是：如果Mealy状态机，一共使用IDLE(初始状态)和GOT_1（检测到1’b1）两个状态。状态机初始化在IDEL状态，只要检测到1，我们就进入GOT_1状态，反之保持IDEL状态。而到了GOT_1状态，我们就立刻检查输入，如果输入是0，我们就检测到了10序列，反之我们重新进入IDEL状 态。如果使用Moore状态机，一共使用IDEL、GOT_1和SUCCESS三个状态。状态机初始化在IDEL状态，只要检测到1，我们就进入GOT_1状态，反之保持IDEL状态。在GOT_1状态下如果输入1，就进入SUCCESS状态，反之保持GOT_1状态。在SUCCESS状态下，如果输入1，就回到GOT_1状态，反之回到IDEL状态。同时，只有在SUCCESS状态下才输出1。

其实我们如果想要从零开始写一个状态机，一般都是（在心中）先用自然语言想清楚的。但是自然语言描述的状态机不简洁，也不容易转化成代码，进而有了两种方法进一步对自然语言抽象，首先就是状态转移表，主要以现态、输入、次态和输出四部分内容为表头，首先是Mealy型状态机：

其次是Moore型状态机：

表的大小取决于状态的数量和输入的类型数量。

状态转移表其实很适合那些喜欢用表格来表达逻辑关系的人，如果你喜欢使用图像来思考，也可以使用状态转移图，以下是两种状态机的状态转移图：

对于Mealy型状态机，由于其输出受输入直接影响，所以输出写在了状态转移箭头旁边（输入/输出）；而对于Moore型状态机，由于其输出只受状态影响，所以其输出写在了表示状态的圆圈内。

最后是状态机的代码表示，上一题已经给过了，这里不再啰嗦。

一般来说对于简单的状态机，可以直接从自然语言转化成代码；但是对于相对复杂的状态机，就需要先从自然语言转换到状态转移图（表），以此为踏板再转化成代码。

再说回本题，本题的提示是有问题的，我们来看看槽点：

这是HDLBits给的模板，乍一看是一个一段式状态机，那我们先按一段式状态机的思路来写。但你看看这个模板，就会发现，如果真是一段式状态机，那么就不需要next_state这个变量，一个present_state足以胜任；其次，即便真的需要next_state这个变量，提示中22行present_state = next_state; 竟然用了阻塞赋值！这是一个明显的错误,我们这里先按一段式状态机的思路来把代码写下来：

但是仿真的波形错误了：

从波形就可以看出来，我们的输出比案例慢了一个时钟周期，所以显然答案希望我们使用组合逻辑给out赋值，但是又只有二段式或者三段式状态机才能在输出时用组合逻辑。这不纯纯矛盾？？？很疑惑的我被整无奈了。。。所以就用三段式的组合逻辑输出重新写了一下，于是得到答案：

Fsm2

这一题引入了两位输入，但是换汤不换药：

Fsm3onehot

这题提出了一个很重要的编码概念：one-hot编码，即独热码。独热码是一种用N位寄存器来表示N个状态的编码方法。其核心思想是，在任何时刻，这N位寄存器中有且仅有一位为高电平（1），其余所有位都为低电平（0）。显然独热码是非常消耗硬件资源的，如下是其和二进制编码的区别：

从上表可以看出：

• 二进制编码：使用了最少的触发器。log_2(4)=2 个触发器。
• 独热码：使用了与状态数量相等的触发器，即4个。

那我们为什么我们还是要使用独热码呢？因为独热码有以下优点：

• 解码逻辑极其简单，速度快 (High Speed)

  这是独热码最核心、最突出的优点。由于每一位直接对应一个状态，判断当前是否处于某个特定状态变得异常简单。对于独热码，判断是否在S2状态，只需检查 current_state[2] 是否为1；而对于二进制编码，判断是否在S2状态（编码10），则需要检查 current_state == 2’b10，这在硬件上需要一个与门 (current_state[1] && !current_state[0])。当状态数量增多时，二进制码的解码逻辑会变得越来越复杂，组合逻辑路径变长，从而限制了状态机的最高运行时钟频率。而独热码的解码逻辑始终只是检查一位，因此组合逻辑路径非常短，非常有利于高速设计。

• 状态转换逻辑更简单

  在计算下一个状态时，逻辑也常常被简化。因为每个状态的转换只涉及“熄灭”当前位和“点亮”下一位，这使得生成下一状态的组合逻辑也可能更简单、更快。

• 安全性与可预测性

  由于任何时候只允许一位为1，系统很容易检测到非法状态（例如，同时有两位为1，或者全为0）。这为设计增加了一层内在的错误检测机制，有助于设计一个更鲁棒的系统。

那么独热码的缺点也很明显：

• 消耗更多的触发器
  这是独热码最显著的缺点。N个状态需要N个触发器，而二进制编码只需要log_2(N)
• 状态数量受限
  对于状态数量非常庞大的状态机，使用独热码会急剧增加寄存器的数量，可能导致资源紧张。

说白了，使用独热码的本质就是用面积换性能。

说回这一题，题目的意思并不是让你直接编程一个one-hot状态机，而是为了检查你是否理解了one-hot编码每次只有一位会为1的精髓。说白了，这一题对于状态A、B、C、D的one_hot编码就是4’b0001、4’b0010、4’b0100、4’b1000;而模板代码中给的A=0、B=1…其实只是状态A、B、C、D的索引,并不是独热码本身。也就是说，如果state处于A状态，那么state[ A]就为1，state[ B ]以及其他位就是0。本题就是希望你使用独热码的这一特点利用简单的逻辑计算来确定下一状态，本质上就是一个真值表的问题，答案如下：

刚好下一题的答案就是用one-hot编码进行编写，如下：

Exams/ece241 2013 q4

这一题的题干提出了一个任务需求，而我们需要将这个需求用状态机的语言描述出来最后再用代码实现。如下是问题的译文：

简而言之就是我们需要做一个蓄水池的控制器，控制依据就是静态水位和动态水位的变化情况。根据静态水位，我们分了三个挡位；而根据动态水位是增高还是降低，我们给了一个dfr控制。所以我有了一个简单想法：那就是分为4个状态，即4个水位高度，然后根据这个状态直接控制fr的输出，至于dfr则需要进一步判断上一个水位的状态再来输出。

我们其实还需要补充一些假设,这些在题目中没有明确说明：第一，水位的变化是连续的，例如，水位如果是已经是最低，那么水位只会往上涨到次低位，不可能在下个时钟突然变成最高位；第二，水位的变化就是离散的，只有四个离散水位，不存在中间值；第三，dfr复位的值为1，而且在一个完整的state状态下需要保持住赋值状态。

最后分析一下输出，显然fr和我假设的四个状态是一一对应的，是静态的，所以直接使用组合逻辑输出就好；而dfr不同，他需要你记住上一个状态，拥有记忆功能，所以需要使用时序逻辑进行输出。进而得到我的答案：

module top_module (input clk,input reset,input [3:1] s,output fr3,output fr2,output fr1,output dfr
); parameter 	PS_HIGH = 4'b1000,PS_MEDH = 4'b0100,PS_MEDL = 4'b0010,PS_LOW  = 4'b0001;localparam PL_STATE_BITS = $bits(PS_HIGH);reg [PL_STATE_BITS-1:0]current_state,next_state;always@(posedge clk)beginif(reset)begincurrent_state <= PS_LOW;end else begincurrent_state <= next_state; endendalways@(*)begin/*状态机的写法思路*/next_state = current_state;       case(current_state)PS_HIGH:if(s == 3'b011) beginnext_state <= PS_MEDH; endPS_MEDH:if(s == 3'b111)beginnext_state <= PS_HIGH; end else if(s == 3'b001)beginnext_state <= PS_MEDL; endPS_MEDL:if(s == 3'b000)beginnext_state <= PS_LOW; end else if(s == 3'b011) beginnext_state <= PS_MEDH; endPS_LOW:if(s == 3'b001)beginnext_state <= PS_MEDL; endendcase/*这样写不是状态机的思路，但也可以完成功能if(s == 3'b000)beginnext_state <= PS_LOW; end else if(s == 3'b001)beginnext_state <= PS_MEDL; end else if(s == 3'b011) beginnext_state <= PS_MEDH; end else if(s == 3'b111)beginnext_state <= PS_HIGH; end*/end/*静态输出 不需要有记忆功能，所以使用组合逻辑*/reg[3-1:0]r_fr;always@(*)beginr_fr = 3'b000; case(current_state)PS_HIGH: r_fr = 3'b000;PS_MEDH :r_fr = 3'b001;PS_MEDL :r_fr = 3'b011;PS_LOW  :r_fr = 3'b111;endcaseendassign {fr3,fr2,fr1} = r_fr;/*动态输出 需要有记忆功能，所以使用时序逻辑*/always@(posedge clk)beginif(reset)begindfr <= 1'b1;end else begincase(current_state)PS_HIGH :if(next_state == PS_MEDH) dfr = 1'b1;else dfr = dfr;PS_MEDH :if(next_state == PS_MEDL) dfr = 1'b1;else if(next_state == PS_HIGH) dfr = 1'b0;else dfr = dfr;PS_MEDL :if(next_state == PS_LOW) dfr = 1'b1;else if(next_state == PS_MEDH) dfr = 1'b0;else dfr = dfr;PS_LOW  :if(next_state == PS_MEDL) dfr = 1'b0;else dfr = dfr;endcaseend end
endmodule

值得分析一下的是示例的答案：

看上去很简洁，主要原因是示例中状态的设置更巧妙。我们来分析一下，示例中的状态分为了六种，刚好对应了fr和dfr组合起来的六种输出。用自然语言描述就是，A1代表水位最低且dfr输出为1，B1代表水位次低且dfr输出为0，B2代表水位次低且dfr输出为1，…。于是，在这种情况下，fr的输出和dfr就能统一在一起了。那么dfr输出需要的记忆功能呢？其实在这个例子中这个记忆功能就被融和到了状态转化的组合逻辑always块中。

从这个例子可以看出，状态机设计的灵魂就是状态的选取。状态数量的选取以及每个状态所需完成的功能会深深影响整个状态机设计的复杂程度。示例的思路其实是从输出结果出发，有几个输出结果就定义几个状态；而我在编写的时候是从实际情况出发的，也就是比较符合人的直观思维。其实，这两种思路是都是可以的，到底是正着思考（从实际出发）还是倒着思考（从结果出发）取决于具体问题，很多时候也需要将两个思维结合起来设计状态机。

Lemmings1

这一题我们就仿照上一题示例的思路来确定状态机的状态数。我们从输出出发，输出情况一共就两种，即向左走和向右走，所以我们就定义两种状态，于是得到下面的答案：

当然上面的状态转移里的逻辑表达式还可以利用公式A+A·B=A进行简化，简化完就是示例中的答案：

Lemmings2

这一题还是先从输出出发，输出一共有三种，那么我们就先按照三种状态来分析，即左走、右走和下落。但是如果你直接这样去写就会发现很难完成“当地面恢复时下落状态会回到下落前的行走状态”这个功能，说白了，这部分也是需要记忆功能的。例如，如果我们从下落状态恢复到左走或右走状态，就需要引入别的控制变量来记忆这个方向信息，我们试着这么写一下，得到答案：

答案中的flag变量就是要额外引入的控制变量。现在我们试着正着考虑实际情况，下落本身的状态也是可以包含方向信息的，Lemming在下落过程中可以朝向左边，也可以朝向右边。于是我们可以进一步引入向左下落和向右下落两个状态，这样状态本身就把方向记忆住了，不需要引入额外控制信号了，于是答案如下：

显然对于这一题，通过正向思考设计状态机会更简单一些。

Lemmings3

这一题又加上了挖掘这一状态，同上一个问题，挖掘时也需要记忆之前走路的方向，所以我们需要给挖掘两个状态位，否则就需要引入别的控制变量，答案如下：

module top_module(input clk,input areset,    // Freshly brainwashed Lemmings walk left.input bump_left,input bump_right,input ground,input dig,output walk_left,output walk_right,output aaah,output digging ); parameter 	LEFT = 3'd1,RIGHT = 3'd2,FALL_LEFT = 3'd3,FALL_RIGHT = 3'd4,DIGGING_LEFT = 3'd5,DIGGING_RIGHT = 3'd6;reg [2:0] current_state,next_state;always@(posedge clk,posedge areset)beginif(areset)begincurrent_state <= LEFT; end else begincurrent_state <= next_state; endend    always@(*)beginnext_state = current_state;case(current_state)LEFT: if(!ground) next_state = FALL_LEFT;else if(dig) next_state = DIGGING_LEFT;else if(bump_left) next_state = RIGHT;else next_state = LEFT;RIGHT:if(!ground) next_state = FALL_RIGHT;else if(dig) next_state = DIGGING_RIGHT;else if(bump_right) next_state = LEFT;else next_state = RIGHT;FALL_LEFT:if(ground) next_state = LEFT;else next_state = FALL_LEFT;FALL_RIGHT:if(ground) next_state = RIGHT;else next_state = FALL_RIGHT;DIGGING_LEFT:if(!ground) next_state = FALL_LEFT;else next_state = DIGGING_LEFT; DIGGING_RIGHT:if(!ground) next_state = FALL_RIGHT;else next_state = DIGGING_RIGHT; endcaseendassign walk_left = current_state == LEFT;assign walk_right = current_state == RIGHT;assign aaah = current_state == FALL_LEFT || current_state == FALL_RIGHT;assign digging = current_state == DIGGING_LEFT || current_state == DIGGING_RIGHT;endmodule

Lemmings4

这一题需要根据角色下落的时间来判断接触到地面后会不会死亡。其实还是两种思路，一种是加入FALL_LEFT_0,…,FALL_LEFT_19这么多个下落状态来记忆下落周期，但是显然状态机的状态数太多，并不合理；另一种思路就是引入额外控制变量，用来记忆下落时间。所以答案如下：

module top_module(input clk,input areset,    // Freshly brainwashed Lemmings walk left.input bump_left,input bump_right,input ground,input dig,output walk_left,output walk_right,output aaah,output digging ); parameter 	LEFT = 3'd1,RIGHT = 3'd2,FALL_LEFT = 3'd3,FALL_RIGHT = 3'd4,DIGGING_LEFT = 3'd5,DIGGING_RIGHT = 3'd6,DEAD = 3'd7;reg [2:0] current_state,next_state;always@(posedge clk,posedge areset)beginif(areset)begincurrent_state <= LEFT; end else begincurrent_state <= next_state; endend    reg [7:0]cnt;//用于记录时间下落时间always@(posedge clk,posedge areset)beginif(areset)begincnt <= '0; end else if(aaah)begin //下落时cnt <= cnt + 1; end else begin //只要不在下落就归零cnt <= '0; endendwire dead_flag = cnt >= 20;always@(*)beginnext_state = current_state;case(current_state)LEFT: if(!ground) next_state = FALL_LEFT;else if(dig) next_state = DIGGING_LEFT;else if(bump_left) next_state = RIGHT;else next_state = LEFT;RIGHT:if(!ground) next_state = FALL_RIGHT;else if(dig) next_state = DIGGING_RIGHT;else if(bump_right) next_state = LEFT;else next_state = RIGHT;FALL_LEFT:if(ground && dead_flag) next_state = DEAD;else if(ground && !dead_flag) next_state = LEFT;else next_state = FALL_LEFT;FALL_RIGHT:if(ground && dead_flag) next_state = DEAD;else if(ground && !dead_flag) next_state = RIGHT;else next_state = FALL_RIGHT;DIGGING_LEFT:if(!ground) next_state = FALL_LEFT;else next_state = DIGGING_LEFT; DIGGING_RIGHT:if(!ground) next_state = FALL_RIGHT;else next_state = DIGGING_RIGHT; DEAD:next_state = DEAD;endcaseendalways@(*)beginwalk_left 	= 1'b0;walk_right	= 1'b0;	aaah		= 1'b0;digging		= 1'b0;        if(current_state == DEAD)beginwalk_left 	= 1'b0;walk_right	= 1'b0;	aaah		= 1'b0;digging		= 1'b0;end else beginwalk_left = current_state == LEFT;walk_right = current_state == RIGHT;aaah = current_state == FALL_LEFT || current_state == FALL_RIGHT;digging = current_state == DIGGING_LEFT || current_state == DIGGING_RIGHT;endendendmodule

Fsm onehot

这一题与Fsm3onehot类似，是希望你充分利用One-hot编码的特点根据逻辑运算获得的状态转移逻辑和输出逻辑编写，答案如下：

Fsm ps2

本题就是在设计一个数据流的解析器。在通信类项目中数据流的解析任务非常常见，基本也都是通过状态机来实现，一般来说，数据流解析都有这么几个关键问题：怎么确定数据包的包头和包尾？怎么确定数据包是否需要被丢弃（或者说怎么确定数据包解析成功）？需要进一步提取一个数据包内的哪些内容（例如TCP包中的源地址目的地址等）？

对于本题，其实就是确定一个三字节长度的数据包，只有一个指明包头的控制位in[3]。简要来说，本题要完成的功能就是只要第一个in[3]被置为1，则认为是包头，随后紧跟的两个字节就是包的其他内容（无论此时in[3]是否再次被置为1）；多出两个字节的内容不再认为是有效数据，除非in[3]再次被置为1。

本题有两种思路，第一种是借助计数器。此时状态机只要三个状态，即空闲、包身和完成状态，通过计数器来确定包尾，答案如下：

当然，由于本题的数据是连续的，并且只有三个字节，我们也完全不需要计数器，因为计数功能完全可以通过添加更多状态数来实现，此时答案如下：

注意，本题的Hint建议使用4个状态，但是我们上面已经证明只要引入额外的控制变量也可以使用三个状态实现功能。其次，Hint中画的状态转移图其实和我们刚刚第二种方法是一模一样的:

Fsm ps2data

这一题需要注意的就是数据的捕获是在不同的时钟周期下，意味着必须使用时序always块让out_bytes拥有记忆功能，答案如下：

Fsm serial

这一题的数据位数比较多，就不能简单通过增添状态来写状态机了，必须引入计数器来控制。由于现在多了一个结束位，并且要考虑丢包情况，所以选用状态就要比Fsm ps2中多两个，如下为本题答案：

Fsm serialdata

这一题的关键就是怎么捕获数据，我先使用for循环实现，答案如下：

module top_module(input clk,input in,input reset,    // Synchronous resetoutput [7:0] out_byte,output done
); //parameter 	IDEL = 3'd0,DATA = 3'd1,END = 3'd2,DROP = 3'd3,DONE = 3'd4;reg [2:0]current_state,next_state;always@(posedge clk)beginif(reset) current_state <= IDEL;else current_state <= next_state;endreg[3:0]cnt;always@(posedge clk)beginif(reset) begincnt <= '0; end else if(current_state == DATA)begincnt <= cnt + 1; end else begincnt <= '0; endendalways@(*)begincase(current_state)IDEL: next_state = !in ? DATA: IDEL;DATA: next_state = cnt == 8-1 ? END:DATA;END:  next_state = in ? DONE : DROP;DROP: next_state = in ? IDEL : DROP;DONE: next_state = !in ? DATA: IDEL;endcaseendassign done = current_state == DONE;always@(posedge clk)beginif(reset)beginout_byte <= '0; end else if(current_state == DATA)beginfor(int i=0;i <= 8-1 ;i++)beginout_byte[i] <= (cnt == i) ? in : out_byte[i];  //这一步很关键，注意每一位的自保持endend else beginout_byte <= out_byte;endendendmodule

但其实这样写就麻烦了，最简单的方式是利用向量移位来完成（Hint中的提醒），改进后答案如下：

module top_module(input clk,input in,input reset,    // Synchronous resetoutput [7:0] out_byte,output done
); //parameter 	IDEL = 3'd0,DATA = 3'd1,END = 3'd2,DROP = 3'd3,DONE = 3'd4;reg [2:0]current_state,next_state;always@(posedge clk)beginif(reset) current_state <= IDEL;else current_state <= next_state;endreg[3:0]cnt;always@(posedge clk)beginif(reset) begincnt <= '0; end else if(current_state == DATA)begincnt <= cnt + 1; end else begincnt <= '0; endendalways@(*)begincase(current_state)IDEL: next_state = !in ? DATA: IDEL;DATA: next_state = cnt == 8-1 ? END:DATA;END:  next_state = in ? DONE : DROP;DROP: next_state = in ? IDEL : DROP;DONE: next_state = !in ? DATA: IDEL;endcaseendassign done = current_state == DONE;always@(posedge clk)beginif(reset)beginout_byte <= '0; end else if(current_state == DATA)beginout_byte <= {in,out_byte[7:1]}; //注意使用右移end else beginout_byte <= out_byte;endendendmodule

向量的移位是处理串行数据捕获的最常用方式

Fsm serialdp

这一题加上了校验位，我采用的方法是给状态机加上校验状态。至于校验模块这一题已经给了，我们直接例化就好，但是需要注意模块的reset信号赋值时机，答案如下：

module top_module(input clk,input in,input reset,    		// Synchronous resetoutput [7:0] out_byte,output done
); //parameter 	IDEL = 3'd0,DATA = 3'd1,END = 3'd2,CHECK = 3'd3,DROP = 3'd4,DONE = 3'd5;reg [2:0]current_state,next_state;always@(posedge clk)beginif(reset) current_state <= IDEL;else current_state <= next_state;endreg[3:0]cnt;always@(posedge clk)beginif(reset) begincnt <= '0; end else if(current_state == DATA)begincnt <= cnt + 1; end else begincnt <= '0; endendalways@(*)begincase(current_state)IDEL: next_state = !in ? DATA: IDEL;DATA: next_state = cnt == 8-1 ? CHECK:DATA; //8位数据CHECK: next_state = odd != in ? END : DROP;	//第九位是奇偶校验END:  next_state = in ? DONE : DROP;DROP: next_state = in ? IDEL : DROP;DONE: next_state = !in ? DATA: IDEL;endcaseendassign done = current_state == DONE;always@(posedge clk)beginif(reset)beginout_byte <= '0; end else if(current_state == DATA)beginout_byte <= {in,out_byte[7:1]}; //注意使用右移end else beginout_byte <= out_byte;endendwire parity_rst = !in & (current_state == IDEL || current_state == DONE); //起始位设置reset信号wire odd;parity parity_u(.clk(clk),.reset(parity_rst),.in(in),.odd(odd));endmodule

当然不使用例子给的校验模块反而更简单，直接利用异或运算获取向量里1的奇偶个数，答案如下：

module top_module(input clk,input in,input reset,    		// Synchronous resetoutput [7:0] out_byte,output done
); //parameter 	IDEL = 3'd0,DATA = 3'd1,END = 3'd2,CHECK = 3'd3,DROP = 3'd4,DONE = 3'd5;reg [2:0]current_state,next_state;always@(posedge clk)beginif(reset) current_state <= IDEL;else current_state <= next_state;endreg[3:0]cnt;always@(posedge clk)beginif(reset) begincnt <= '0; end else if(current_state == DATA)begincnt <= cnt + 1; end else begincnt <= '0; endendalways@(*)begincase(current_state)IDEL: next_state = !in ? DATA: IDEL;DATA: next_state = cnt == 8-1 ? CHECK:DATA; //8位数据CHECK: next_state = ^out_byte != in ? END : DROP;	//第九位是奇偶校验END:  next_state = in ? DONE : DROP;DROP: next_state = in ? IDEL : DROP;DONE: next_state = !in ? DATA: IDEL;endcaseendassign done = current_state == DONE;always@(posedge clk)beginif(reset)beginout_byte <= '0; end else if(current_state == DATA)beginout_byte <= {in,out_byte[7:1]}; //注意使用右移end else beginout_byte <= out_byte;endend
endmodule

Fsm hdlc

本题是一个序列检测器，对于序列检测器，一般的方法就是根据序列长度选取状态数目，而不是借助计数器。所以本题答案如下：

module top_module(input clk,input reset,    // Synchronous resetinput in,output disc,output flag,output err);parameter IDEL = 4'd0,G_1X1= 4'd1,G_1X2= 4'd2,G_1X3= 4'd3,G_1X4= 4'd4,G_1X5= 4'd5,G_1X6= 4'd6,DISC = 4'd7,FLAG = 4'd8,ERR  = 4'd9;reg[4-1:0]current_state,next_state;always@(posedge clk)beginif(reset)current_state <= IDEL;else current_state <= next_state;endalways@(*)beginnext_state = current_state;case(current_state)IDEL :next_state = in ? G_1X1:IDEL;G_1X1:next_state = in ? G_1X2:IDEL;G_1X2:next_state = in ? G_1X3:IDEL;G_1X3:next_state = in ? G_1X4:IDEL;G_1X4:next_state = in ? G_1X5:IDEL;G_1X5:next_state = in ? G_1X6:DISC;G_1X6:next_state = in ? ERR:FLAG;DISC: next_state = in ? G_1X1:IDEL;FLAG: next_state = in ? G_1X1:IDEL;ERR:  next_state = in ? ERR :IDEL;endcaseendassign disc = current_state == DISC;assign flag = current_state == FLAG;assign err = current_state == ERR;endmodule

未完待续

本篇文章截止到Circuits — Finite State Machine — Sequence recognition（Fsm hdlc）。