數(shù)字IC手撕代碼-有限狀態(tài)機(jī)FSM-飲料機(jī)

2022-04-22 19:29 作者:不吃蔥的酸菜魚 0人讀過 | 我要投稿

????????大家好我是酸菜魚，這個(gè)系列著重講解數(shù)字ic或FPGA實(shí)習(xí)面試及秋招面試的高頻手撕代碼題。

往期專欄：

數(shù)字ic手撕代碼-導(dǎo)覽目錄 - 嗶哩嗶哩 (bilibili.com)

數(shù)字ic手撕代碼-格雷碼的編碼與解碼 - 嗶哩嗶哩 (bilibili.com)

數(shù)字IC手撕代碼-序列檢測(cè)（移位寄存器寫法） - 嗶哩嗶哩 (bilibili.com)

專欄眾多，不一一列舉，詳情請(qǐng)看導(dǎo)覽目錄...?

有限狀態(tài)機(jī)介紹

????????有限狀態(tài)機(jī)（Finite state machine）是為研究有限內(nèi)存的計(jì)算過程和某些語言類而抽象出的一種計(jì)算模型。有限狀態(tài)自動(dòng)機(jī)擁有有限數(shù)量的狀態(tài)，每個(gè)狀態(tài)可以遷移到零個(gè)或多個(gè)狀態(tài)，輸入字串決定執(zhí)行哪個(gè)狀態(tài)的遷移。有限狀態(tài)自動(dòng)機(jī)可以表示為一個(gè)有向圖，也就是我們常說的在寫FSM之前要先畫狀態(tài)轉(zhuǎn)移圖。

有限狀態(tài)機(jī)寫法? ?

有限狀態(tài)機(jī)常見的有三種寫法：

※ 一段式寫法：將下一個(gè)狀態(tài)計(jì)算、狀態(tài)跳轉(zhuǎn)和信號(hào)輸出在一個(gè)進(jìn)程中完成。

※ 二段式寫法：將狀態(tài)跳轉(zhuǎn)在一個(gè)進(jìn)程中完成，將下一個(gè)狀態(tài)計(jì)算和信號(hào)輸出在一個(gè)進(jìn)程中完成。

※ 三段式寫法：將下一個(gè)狀態(tài)計(jì)算、狀態(tài)跳轉(zhuǎn)和信號(hào)輸出分別在三個(gè)進(jìn)程中完成。

上面所說的進(jìn)程也就是用一個(gè)過程語句塊（always）描述。

????????這里建議在寫狀態(tài)機(jī)的時(shí)候，都采用三段式寫法，原因很簡(jiǎn)單，在寫只有幾個(gè)狀態(tài)的FSM時(shí)候，一段式也好兩段式也好，都可以快速的寫出來而且思路清晰。但是實(shí)際工程中的狀態(tài)機(jī)經(jīng)常會(huì)出現(xiàn)有十幾個(gè)狀態(tài)相互跳轉(zhuǎn)，甚至狀態(tài)機(jī)嵌套的情況，這時(shí)候一段、兩段式的狀態(tài)機(jī)書寫的思路就不是特別清晰，更重要的代碼維護(hù)性不強(qiáng)。所以本文只講解三段式狀態(tài)機(jī)的寫法。

三段式狀態(tài)機(jī)基本結(jié)構(gòu)

三段式的狀態(tài)機(jī)分為兩種：Mealy型和Moore型。它們的區(qū)別在于摩爾型（Moore）輸出只和狀態(tài)有關(guān)而與輸入無關(guān)，米莉型（Mealy）輸出不僅和狀態(tài)有關(guān)而且和輸入有關(guān)系。

※ 根據(jù)狀態(tài)的個(gè)數(shù)確定狀態(tài)機(jī)編碼。

※ 狀態(tài)機(jī)第一段：時(shí)序邏輯，非阻塞賦值，傳遞狀態(tài)機(jī)的狀態(tài)（state<=next_state）

※ 狀態(tài)機(jī)第二段：組合邏輯，阻塞賦值，根據(jù)當(dāng)前的狀態(tài)和輸入，確定下一個(gè)狀態(tài)機(jī)的狀態(tài)。

※ 狀態(tài)機(jī)第三段：時(shí)序或組合邏輯，非阻塞賦值，根據(jù)當(dāng)前狀態(tài)和當(dāng)前輸入（Mealy型狀態(tài)機(jī)）或者當(dāng)前狀態(tài)（Moore型狀態(tài)機(jī)），確定輸出信號(hào)。

下面以一個(gè)飲料機(jī)為例子來寫一個(gè)三段式狀態(tài)機(jī)：

問：請(qǐng)用FSM設(shè)計(jì)一個(gè)飲料機(jī)，畫出狀態(tài)轉(zhuǎn)移圖并編寫代碼實(shí)現(xiàn)。（其中，投幣可以是1元，也可以是五角，當(dāng)投幣滿2元就可以出一瓶飲料，飲料機(jī)應(yīng)該還具有找零功能）。

????????第一步畫狀態(tài)轉(zhuǎn)移圖，我們得先確定有幾種狀態(tài)，狀態(tài)之間的轉(zhuǎn)換關(guān)系是怎么樣的，然后再畫出狀態(tài)轉(zhuǎn)移圖。

首先分析有幾種狀態(tài)：

IDLE狀態(tài)：即飲料機(jī)的初始狀態(tài)，此時(shí)沒有往飲料機(jī)里投一毛錢。

GET05狀態(tài)：飲料機(jī)里有五角錢。

GET10狀態(tài)：飲料機(jī)里有一塊錢，可能是投兩次五角到達(dá)該狀態(tài)，也可以是投一次一元到達(dá)該狀態(tài)。

GET15狀態(tài)：飲料機(jī)里有一塊五，可能是投三次五角、一次五角一次一塊、一次一塊一次五角到達(dá)該狀態(tài)。

上面總共說了四種狀態(tài)，用兩比特即可完全描述狀態(tài)。

????還有沒有別的狀態(tài)？沒有了！飲料機(jī)不會(huì)有兩塊的狀態(tài)！比如在GET15狀態(tài)，飲料機(jī)里有一塊五，投入一塊，總投入兩塊五，此時(shí)飲料機(jī)會(huì)給一瓶飲料并找零五角，飲料機(jī)回到初始狀態(tài)。如果投入五角，則總投入兩塊，此時(shí)飲料機(jī)會(huì)給一瓶飲料且不找零。如果是在GET10狀態(tài)，投入一塊，飲料機(jī)也會(huì)回到初始狀態(tài)并給一瓶飲料不找零。綜上，我們畫出狀態(tài)轉(zhuǎn)移圖。