【我的計組生活5'b00000】P0課下作業簡析

大家好，我們又見面了~~

寄語：很慶幸開啟了【我的計組生活】系列重製計劃，把這一學期經歷的記錄下來，或許對後人或正在看的你有所幫助。之前發的推送由於時間等原因，有些分享給人誤解，也有些圖片看不清等問題。重製版對這些進行了更多的優化，希望大家喜歡~

我們擁有什麼：2020 計組實驗課設的個人項目開源，部分上機題目，以及若干支線技能。在此特別提醒：部分項目你可以看別人的實現思路，但項目開源後會增加抄襲風險，如果有幸被請去課程組喝茶，後果自負 哦 ~

*注意：如有錯誤或可以改進的地方請與筆者聯繫 ~

噹噹噹噹！快醒醒，都 2021 寒假了，難道還有人在看計組？

確實，不只有人在學，某項目組即將開工，（由於 NDA 限制，不能透露更多）

重回金秋，我們將一切歸 0，一起學習（回憶）計組課程~

本期使用的軟體：Logisim、CircuitVerse（可在線使用）

（廢話不多說， 直接上乾貨）

P0課下作業簡析

CRC校驗(P0.Q1)提交要求

使用 Logisim 搭建一個除數為四位，原數據幀為 8 位的 CRC 校驗碼計算電路。具體模塊埠定義如下：

信號名方向描述A[7:0]I8位原數據幀B[3:0]I4位除數C[10:0]O8位原數據幀+3位校驗碼

必須嚴格按照模塊的埠定義

題目分析

1. CRC校驗碼簡介

CRC校驗是數據通信領域中最常用的一種查錯校驗方式，它對數據進行多項式計算，並將得到的結果附在幀的後面，接收設備也執行類似的算法，以保證數據傳輸的正確性和完整性。

在了解這種校驗碼怎麼計算之前，我們需要先了解一種特殊的除法:「模二除法」。它與算術除法類似，但在做減法時既不向上借位，也不比較除數和被除數相同位數值的大小；它的運算法則為1-1=0，0-1=1，1-0=1，0-0=0，例如1100-1001=0101。對於模二除法，我們以被除數為1011，除數為10為例，運算過程如下：

如果你細心的話，可以發現，模二除法中的減法和異或的操作是完全相同的，所以模二除法可以用異或來完成。

知道了模二除法的計算過程，CRC校驗碼的計算就很簡單了。我們只需要將原幀補上( 除數位數-1 )個0作為被除數，然後進行模二除法即可。舉個例子，我們要發送的幀A為10011，發送端和接收端共同選定的除數B為1110。因為B是4位二進位數，我們需要在A的後面補上3個0，從而得到A』=10011000。我們將A』作被除數，B作除數，進行」模二除法」。

最後得到的餘數是一個三位數(注意如果不是三位，也要在前面補零來湊齊三位)，這就是要求的校驗碼。我們將得到的校驗碼110拼接在原數據幀的後面，就得到了要發送的新幀A』』=10011110。這樣就完成了CRC校驗碼的生成。

2. 實現方法

校驗碼即原數據後補上除數位數個0，對除數做模二除法的餘數，所以本題的 核心 在於：做模二除法。模二除法即若當前位為1，則當前位商為1，餘數為對應位數異或。

查看上面的案例，知道可能需要循環。不過，在硬體當中實現位循環操作是一個比較難實現的任務。

logisim 實現1（Author : lyx）

lyx 同學的模塊分的很細緻，比 lxl 習慣要好。計組後期的實驗中涉及 CPU 的模塊設計，儘量要求同學們的設計符合 高內聚低耦合 的特徵，大家會在 P4 的單周期 CPU 中看到這個概念，這裡不過多透露了~

①Swap

②Divisor element

解析：當前的第一位為judge，若其為1則當前位的商為1，求出相應餘數；若為0，則直接輸出4bits 被除數。

③CRC

logisim 實現2（Author : lxl）

①CRC

②XOR

解析：邏輯實現和lyx同學的類似，但 lxl 同學更喜歡把模塊可以堆在一起的堆在一起。在模2除法當中，判斷首位是否是1，lxl 直接讓被除數和 1000（十進位數字8）比較，算是更加粗暴的方式，但不是典型的範例。

Tips：布線時更多的使用 Tunnel，簡化布線，畫自己能一眼看懂的電路圖。

實現GRF(P0.Q2)提交要求

使用 logisim 搭建一個GRF。

GRF中包含32個32位寄存器，分別對應0~31號寄存器，其中0號寄存器讀取的結果恆為0。具體模塊埠定義如下：

模塊功能定義如下：

題目分析

按照需求搭建電路即可，注意儘量使用 Tunnel 的使用來優化可讀性。另外，也可以在VS Code中對文件 XML 代碼進行更改，讀者們可以自己嘗試一波。

logisim 實現1（Author : lyx）

grf

setZero

single

part4

part5

wholePart

解析：分層製作模塊，即四個 single 構成 part4、四個 part4 構成 part5、最後組成wholePart，再加入最終模塊。寫入和讀取均用獨熱編碼的方式操作。

logisim 實現2（Author : lxl）

grf

32bits register (like robots huh?)

In/out

Whole Part

解析：同樣為分層製作模塊，同第1題一樣，lxl 同學更喜歡把模塊堆在一個圖片裡，由於是用代碼改的模塊，因此在操作上不至於很複雜。每個寄存器對應一個地址，寫入和讀取操作只需要尋址正確即可。

logisim 實現3（Author : lxl）

解析：這個是 lxl 在 P3 logisim單周期CPU 時重構的 GRF，較為符合設想的實現規則。實際上如何實現不重要，真正重要的是當遇到 bug 的時候自己能否快速找到，在實現的時候可以多看看討論區，比如 DMX 使用的時候別忘記三態。

代碼生成： [ 來自ROIFE's BLOG：https://roife.github.io/ ]

Logisim 的文件實際上是 XML 代碼，由3 種標籤組成:

<circuit> 是電路或子電路的標籤, 用於標記整個電路。

<wire> 標籤用於連線，通過 x-y 屬性定位。

<comp> 標籤擁有 loc 和 name 屬性, 用於調用庫元件。

可以通過代碼生成 XML 來實現構造重複性電路，例如本例要求的 32 個寄存器。

Logisim導航(P0.Q3)提交要求

計小組要去機房上機考試，需要去B機房，但是目前他在A機房。他現在的時間很充裕，就決定生成一串隨機序列，告訴他下一步行走的方向，直到走到B機房。他希望用 logisim 搭建一個可以導航的 Moore 型有限狀態機，來通過序列告訴他是否到達B機房。

題目要求：

計小組只能往東南西北四個方向行走，且若能行走，則每次 只能行走一格。若下一步不存在機房讓計小組行走，那麼計小組會撞到牆壁並且 hit置高一周期，此時計小組仍 保持原地 不會移動，等待下一周期再進行運動。（如果下一步依舊撞牆， 則hit仍然置高；若下一步不會撞牆，則計小組將會繼續行進，hit在此周期置 0）

計小組走到B機房後，「到達」信號需要置位，並保持一周期。到達B機房後計小組將會在下一周期回到原點，（下一周期的輸入將被忽略掉）等待下下周期的輸入，繼續測試他的序列。

計小組遵循上北下南左西右東的方向完成操作。

計小組在時鐘上升沿的時候就已經知道自己下一步的方向並且瞬移過去，並且立即做出判斷。

埠定義：

信號名方向描述dir[1:0]I表示行走的方向：00：向北走 01：向東走 10：向南走 11：向西走clkI時鐘信號resetI異步復位信號arriveO是否到達hitO是否撞上牆壁

模塊名：navigation

必須嚴格按照模塊的埠定義

測試電路：

注意：請保證模塊的appearance與下圖完全一致，否則有可能造成評測錯誤

題目分析

從這裡開始我們要接觸狀態機的題目了，狀態機大家都知道分 Moore 或 Mealy 型狀態機。本題的描述感覺很不清楚，說是 Moore型 的狀態機，卻含有瞬移、立刻轉換的詞語，會讓人誤解為Mealy型狀態機。這個題目在評測的時候還開啟了數據重測。不過記住，不管如何，多看評論區總是好的。

這裡給出 lyx 同學的編碼方式，lyx採用了 5 種狀態編碼，而 lxl 只採用了 2 位的編碼方式。不論是如何編碼，都應該進行狀態構建。首先對不同的位置進行編碼，對應計小組每一個位置均為一個狀態題中5種狀態（採用3位編碼）。如下圖構建五個狀態：

則對應二進位編碼即為狀態的碼，對應狀態轉換表為：

狀態\方向00/北01/東10/南11/西000/0/arrive = 0001/hit = 0000/hit = 1000/hit = 1000/hit = 1001/1/arrive = 0011/hit = 0010/hit = 0000/hit = 0001/hit = 1010/2/arrive = 0100/hit = 0010/hit = 1010/hit = 1001/hit = 0011/3/arrive = 0011/hit = 1100/hit = 0001/hit = 0011/hit = 1100/4/arrive = 1000000000000

其餘的就是要通過打表等操作完成上面這些狀態轉換了，Logisim 有很好的 Combinational Analysis 功能，可以幫助我們更好的打表。這個在步驟在上機的時候也要很快，並且保證不出錯。

logisim 實現1（Author : lyx）

stateChang

arriveCheck

navigation

解析：lyx 沒有把 Hit 一起存在狀態寄存器中，導致整體看上去邏輯混亂，在最終模塊中未標明的兩個模塊分別為 stateChange 和 arriveCheck 模塊。

logisim 實現2（Author : lxl）

解析：如果使用 2bit 組合時序電路，由於只有兩個狀態，lxl 費盡心思嘗試了如何才能把返回原點的那個周期的輸入忽略，最終終於搭配邏輯門成功實現，lxl 還是忘不了把所有模塊放在一起的習慣，雖然這個習慣顯得個人的圖很簡潔，但實際工程化是極不好的。

Logisim中的FSM(P0.Q4)正則表達式匹配

正則表達式是對字符串操作的一種邏輯公式，它通常被用來檢索、替換符合某個模式的文本。它的規則比較複雜，我們現在只講解其中比較簡單的幾種規則。

[...]是指要匹配中括號中的字符(注意是字符不是字符串),比如[xyz]就是要匹配x y z這三個字符中的任意一個。

{...}是指要求匹配」{「前的那個字符幾次，比如a{2}是指要匹配a兩次，a{2,4}是指要匹配a 2至4次,a{,4}指要匹配a 0至4次，a{2,}指要匹配a 2至無窮次。所以[cd]{1,2}就是要求匹配(c或d)一次或兩次,即cc、dd、cd、dc、c、d都是能匹配的。

(...)是指將()內的字符串視為一個整體，比如(ab){1,2}對應的就是ab或abab。

我們也可以將多條表達式組合起來，如a{2}b{2}就是指匹配a兩次後再匹配b兩次,即匹配aabb。

提交要求

使用Logisim搭建一個Mealy型有限狀態機 檢測串行輸入字符串中的能匹配正則表達式b{1,2}[ac]{2}的子串並輸出。具體模塊埠定義如下：

模塊功能定義如下：

必須嚴格按照模塊的埠定義

文件內模塊名: fsm

注意: 每當匹配到一個子串時，需要輸出一次1。例如對字符串bacbacac,模塊應當在第1個c輸入和第2個c輸入時輸出1,而在其他時刻保持輸出為0。

注意：有限狀態機的設計是Mealy型有限狀態機。

測試電路如下：(code部分是你需要搭建的電路)

注意:請保證模塊的appearance與下圖完全一致，否則有可能造成評測錯誤

題目分析

已知目標為構建 Mealy 型 有限狀態機，模塊核心還是在於狀態和狀態轉換的構建。首先識別正則表達式：目標字符串為b{a或c}{a或c}或bb{a或c}{a或c}。下面 構建狀態 如下：

狀態編號S0S1S2S3S4/true實際意義初始狀態輸入第1個b輸入第2個b輸入a或c第2次輸入a或c對應二進位碼000001010011100

狀態轉化表如下：

狀態\輸入'a'/00'b'/01'c'/10others/11S0S0S1S0S0S1S3S2S3S0S2S3S2S3S0S3S4S1S4S0S4/trueS0S1S0S0

logisim 實現1（Author : lyx）

logisim 實現2（Author : lxl）

lxl 這個版本依然是 2 位的狀態表示，看起來簡潔，其實不符合工程方式。當然了，如果你對自己模塊化能力很有把握，也可以嘗試這種做法。

思考

這道題本身的狀態轉換沒啥問題，只是對於 clr 信號的處理非常的不舒服，但也是合情合理。

同步復位要求：時鐘上升沿到來時 如果 clr 信號是 1，才進行復位。

區別於異步復位，清零需要時鐘上升沿和 clr 信號共同作用，而不是只看 clr 信號；又或是組成的電路不是時鐘上升沿也可以觸發清零。

因此不能使用內置於寄存器內的 reset，而是需要自己搭建，於是發生了以下的故事。（《數字設計和計算機體系結構》上有）

好啦，這是 重製版的第 1 期【我的計組生活】，同時身份也轉換成了經歷過計組課設的學生了（雖然我的計組分甚是慘澹，或許作為一個過來人可以提供的更多吧~~

老規矩，有錯誤一定要聯繫作者更改，可以在後臺直接進行留言~

希望能有幫助到你哦！！不介意的童鞋可以來一波贊和在看，甚至是不是還可以來一波打賞~

PS廣告：各位看見了沒，很多圖片引用自大番薯的石頭屋，大番薯很強，強烈推薦給大家 ~~

【我的祭祖生活0X00】From 大番薯的石頭屋