NYCU ICLAB POV-2

前言

本周的課程正式進入到循序電路（Sequntial Circuit）的環節。當時大一的時候教授用了"在電路中加入時間觀念"這樣的方式帶過 Sequential Circuit，不過我認為這種說法有點太過抽象，所以我想用我自己的講法給出我對 Sequnential Circuit 的理解。

另外在更新文章之餘，我也會和同學慢慢整理lab的完整檔案還有各家好手的程式碼，如果有時間也可能針對design進行講解，還請期待～

Lecture 02 –- Finite State Machine

電路中的儲存元件

基礎邏輯設計都有介紹到電路當中的儲存結構，如 Latch、Flip-Flop等，基本上都是透過穩定的回授電路實現"儲存"這樣的行為，或者加上一些其他的控制機關做出"Set"、"Reset"等動作，當然這些都是維持通電才能保持狀態的元件，和真正生活上會用來"儲存"資料 USB / SSD 的物理原理有很大的不同。

但我認為最重要的概念是：為什麼我們需要這種暫時儲存資料的單位？

思考一下，其實任何電路功能都可以用組合邏輯的方式就可以實現，比方說做 10 個數字的加減，大可以製作 9 個加法器並提供 10 個接口給那些數字的來源，但這樣會消耗很可觀的元件數目對吧？一個比較合理的電路，應該只會有有限的輸入輸出 pin 腳，這樣就不可能只使用組合邏輯來實現功能了，因為組合邏輯總會在輸入改變時做出改變，一旦輸入電位不穩定，輸出電位也不會穩定。這是什麼意思？以上述例子來說，組合邏輯永遠只能輸出 10 個數字的總和，但循序電路卻可以在某段時間輸出 1+2、某段時間輸出 1+2+3 …甚至循序電路也不需要一次接收 10 個數字那麼多輸入，可以一段時間給它 1、再下一段時間給它 2…

有限狀態機與資料通路（Finite State Machine & Datapath）

循序電路其實就是在原本的組合邏輯中加入可以"儲存"及"維持一段時間"的元件，作為其內部組合邏輯"隱藏"的額外輸入。我們可以把所有的儲存元件抓出來，它們的數量必定是有限的（

n

），所以產生的 0 / 1 組合必定是有限的（

2^{n}

），我們可以把每一個 0 / 1 組合稱為一個狀態（State），由於狀態機的下一個狀態是將現在的狀態經過組合邏輯產生，所以同樣的狀態必定會產生相同的下個狀態（組合邏輯特性），這就是狀態機之所以有限的原因。資料通路（Datapath）就是指那些組合邏輯的部分。

講了很多抽象的東西，總結起來就是
1. 所有儲存單位的值代表著一個 State
2. 由 State 和輸入經過組合邏輯後會產生新的 State 和輸出
3. 儲存單位在某些時刻會把新的 State 更新到自身內部（回到1）

第 3 點中的**"某些時刻"**，其實就是驅動 Latch 和 Flip-Flop 的 clk 訊號

呼叫時序元件

上一篇筆記當中也有大概提到怎麼呼叫時序元件了，以下直接給出範例程式碼













    //calling edge triggered Flip-Flop
reg d,e;
always@(posedge clk)begin
    d <= e;
end
    //calling edge triggered asynchronus reset Flip-Flop
reg d,rst;
always@(posedge clk,negedge rst)begin
    if(!rst)
        d<=0;
    else
        d<=e;
end

這兩種寫法是在合成階段唯二能被 tool 辨識的 Flip-Flop 寫法，其他如同時被 poedge clk 和 negedge clk 觸發的 Flip-Flop、使用initial block 做初始化的 register 等通通都是旁門左道不可合成。

那為什麼我們需要外接訊號來做 asychronus reset 呢？不是因為開機後Flip-Flop 的初始值是 X（Unknown），而是因為實際上電路在運作的任何狀態都有可能被 reset，所以我們不能依賴 reset 訊號來之前的 Flip-Flop 狀態來重啟電路，才把它們設為 X（任何值都要能夠被 reset）。

Set up & Hold

在剛學習到 Flip-Flop 的特性時，我曾經有這樣子的疑問，為什麼使用 clk 控制所有 Flip-Flop 時，某顆 Flip-Flop 在 edge 上切換數值時不會因此剛好擾亂下一顆連接的 Flip-Flop呢（意即資料穿透好幾層Flip-Flop）？

答案是：有可能發生，有可能不會發生，而 tool 會想辦法幫助你讓這種情況不會發生。

電路的訊號傳播需要一定時間的延遲，從輸入穩定到輸出穩定需要時間，反過來說從輸入不穩定到輸出不穩定也需要時間，對於 Flip-Flop 來說，需要輸入在時鐘觸發緣前後一定時間內保持穩定，所以只要滿足兩個原則就可以保證時序電路正常運作。

clk edge 來臨前，任何 FF 的輸入已經穩定下來 （Setup time check）
clk edge 來臨後，任何上一級 FF 改變造成的不穩定輸出不會太快影響到本級 FF 保持穩定 （Hold time check）

抓住這樣的概念跟靜態時序分析當中一些名詞的解釋，就能輕鬆搞清楚~~邏設/計組/VLSI/數電/ICLAB各學過一次的~~ Setup time 和 Hold time 是什麼意思囉！

~~同樣學了很多次的東西們：~~

~~捲積＠訊號與系統/DSP/機率/微方/數電/機器學習/深度學習/ICLAB/影像處理~~
~~Laplace & Fourier Transform＠訊號與系統/DSP/微方/控制~~

與 Flip-Flop 間的組合邏輯有關

T_{p d}

：表示一個邏輯區塊輸入穩定後，達到輸出穩定所需的時間（propagation delay）

T_{c d}

：表示一個邏輯區塊輸入不穩後，達到輸出不穩定的時間。（contamination delay）

與 Flip-Flop 有關

T_{s e t u p}

：clk edge 來臨前，FF 要求輸入達到穩態的時間

T_{h o l d}

：clk edge 來臨後，FF 要求輸入維持穩定的時間

T_{p c q}

：clk edge 來臨後，FF 輸出達到穩定的時間（clk to q propagation delay）

T_{c c q}

：clk edge 來臨後，FF 輸出開始不穩的時間（clk to q contamination delay）

與時鐘有關

Δ t_{s k e w}

：不同的 FF 接收的時鐘訊號不一定完全同步，這個差異（可正可負）就是用這一項表示。

T_{C}

：Cycle time，表示兩個正緣之間的時間長度。

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

有了範例電路和說明圖片，我們就可以來仔細看看常見的 Setup 和 Hold 的公式代表什麼意思了。

T_{C} \geq T_{p c q} + T_{p d} + T_{s e t u p} + Δ t_{s k e w}

從 clk edge 出發、FF1 輸出穩定（

$T_{p c q}$ ）（COMB1輸入穩定）、到 COMB1 輸出穩定前（
$T_{p d}$ ），必須要在下個 clk edge 前的 Setup time 達到穩定

T_{c c q} + T_{c d} - Δ t_{s k e w} \geq T_{h o l d}

從 clk edge 出發、FF1 輸出不穩（

$T_{c c q}$ ）（COMB1輸入不穩）、到 COMB1 輸出不穩前（
$T_{c d}$ ），必須撐過 FF2 的 Hold time，避免干擾到 FF2。

現在我們可以詳細地回答開頭的提問了

Q：某顆 Flip-Flop 在 edge 上切換數值時不會因此剛好擾亂下一顆連接的 Flip-Flop呢？

A：edge 切換後，保持在穩態的 Flip-Flop 輸入需要經過一汙染延遲（Contamination Delay）時間才會變得不穩，只要該 Flip-Flop 能在 Hold time 內不受干擾，就不用擔心此問題。

在這邊也補充一下到了實體布局和繞線階段 tool 會怎麼修 setup 和 hold violation。Setup 可以透過減少共用邏輯、選用高驅動力的元件、複製多個相同邏輯提高驅動力、或甚至做 retiming 來調整 pipeline 架構。Hold 則可以透過加入 buffer 增加延遲，或刻意讓 clk 產生足夠的 skew 保證不會有問題。
ref： https://www.edn.com/ways-to-solve-the-setup-and-hold-time-violation-in-digital-logic/

for & generate

有撰寫過 C++ 程式碼的讀者想必已經用for用到快要爛掉了，~~因為確實好用~~。for的行為在模擬階段和在 C++ 裡面時很像，但合成階段會有很大的不同：for會被 Desgin Compiler 依序一行一行展開，例如。
















integer i;
always @(posedge clk)begin
    for(i = 0;i<4;i=i+1)begin
        image_reg[i]<=image_in[i];
    end
end
/*
The following code are the format analyzed by design copiler
always @(posedge clk)begin
    image_reg[0]<=image_in[0];
    image_reg[1]<=image_in[1];
    image_reg[2]<=image_in[2];
    image_reg[3]<=image_in[3];
    image_reg[4]<=image_in[4];
end
*/

拜這項性質所賜，for 多了非常多神奇的限制，我自己有遇過的就有

不要在不同always內的for共用 integer index，有可能產生 race condition。
不能使用 integer index 存取一個多 bits 變量的部分 bits








reg [2:0]a;
reg [2:0]b_reg[0:7],b_in[0:7];
integer i;
always @(posedge clk)begin
    for(i=0;i<8;i=i+1)begin
        b_reg[i] <= b_in[i][i:0];//[i:0] is illegal
    end
end

只能使用可確定的數字當作中止條件，不然合成會失敗

generate則是另一項特殊的關鍵字，可以用來一次描述多個相同結構的電路。例如現在有一系列的input[i]和output[i]需要用多個相同的example_module連接，這時就可以讓generate登場了。








wire [63:0]in[0:31],out[0:31];
genvar i; //only genvar can iterate through generate
generate
    for(i = 0;i<=31;i = i+1)begin 
        //genvar must be step-incremental with constant upperbound
        example_module em(.in(in[i]),.out(out[i]));
    end
endgenerate

在 generate block 會使用assign/always/module 等關鍵字，複製多個相同的電路；另外 generate block 內迭代的變數必須是 genvar 型別，只能遞增且須有常數上界；generate block 也可以有generate if和generate case等變形，這些就不多做說明了。

Sample Code

以下我提供實際存在我作業內的一些代碼，說明一下我做 Flip-Flop 給值時會用的 Coding Style。

always @(posedge clk) 只做給值->用在複雜的 FSM 或資料暫存器上


























    //decribing the DFF of FSM, only do assignment
always @(posedge clk,negedge rst_n) begin
    if(!rst_n)
        cur_state<=0;
    else
        cur_state<=next_state;
end
    //decribing the Combinational part of FSM
parameter IDLE='d0, INPUT = 'd1, OPERATION = 'd2,OUTPUT = 'd3;
always @(*) begin
    case (cur_state)
        IDLE: if(in_valid) next_state = INPUT;
              else next_state = IDLE;
        INPUT: if(in_valid) next_state = INPUT;
              else next_state = OUTPUT;
        OUTPUT:case (Mode)
            'd0: begin 
                next_state = (output_is_over)?IDLE:OUTPUT;
            end
                'd1: next_state = IDLE;
                'd2: next_state = IDLE;
                default: next_state = 0;
            endcase
        default: next_state = IDLE;
    endcase
end

always @(posedge clk) 加入一些COMB語句->通常用在描述規則簡單的 shift register 上








reg [31:0] Img_reg [13:0];
integer i;
always @(posedge clk) begin
        //the assignment involves some combinational elemets
    Img_reg[0]<={32{in_valid}}&Img;
    for(i=1;i<=13;i = i+1)
        Img_reg[i]<=Img_reg[i-1];
end

Lab02 Cordinates Calculation

Description

本周的 Lab 要撰寫一個座標處理器，依序給定一些座標點和選擇訊號 mode 後要計算圍成四邊形包含的整數座標點、面積、或其中兩點圍成的直線能不能與另外兩點決定的圓相切／交／割。Pin腳如下

Input
xi, yi (8bit 2補數)
mode (2'b0->梯形渲染 2'b1圓與直線 2'b2算梯形面積)
in_valid, rst_n, clk (基礎控制訊號，未來會不斷出現，rst_n出現在最開頭提供asynchronus active low reset，input 和 invalid 則會在 clk negedge 給值)
Output
out_valid (通知 pattern/下級電路本級完成的訊號)
xo, yo (8bits 不同 mode 有不同含意)

in_valid 拉起後，Cycle 1會給 mode 訊號，Cycle 1~4 會依序給 4 組 8bit signed number 的座標點。依據 mode 的不同，需要對座標做不同處理。

Strategy

本次計算 Performance 的方式是

L a t e n c y \times A r e a

，因為 Cycle time 被鎖定在 12ns，所以只要注意 in_valid 落下到 out_valid 升起的Cycle 數目就好。未來會有一些 lab 可以調整 Cycle time。

我自己通常會把 Latency 的最佳化順序設定在最前面，拿這次 Lab 當例子，從 1 cycle 開始，多一個 cycle performance 直接被翻倍計算。之後開始設定 Cycle time時，雖然會有「多一個 Cycle 但換取 Cycle time 減少划不划算？」的問題，但不管怎樣，拿面積換時間通常是個划算的交易。

Mode 0

Mode0 保證 4 個座標點會形成一個矩形，我們則要想辦法判定矩形"圍"住哪些網格，並將這些網格的座標由左下角往右上輸出。

例圖中的橘色網格的左下角座標就是應該要輸出的座標點

邊界條件（例如壓線要不要輸出、最上面一排要不要輸出…）在這個 Mode 其實不是最重要的一環，重要的是怎麼計算每一列列首和列尾的座標點，接著讓輸出從列首累進到列尾，再切換到下個列首列尾就好了。

注意到 y 座標每 +1，x 就會位移一個斜率。斜率可由兩個 8 bits 數字相除得到，我們假設商是

Q

、餘是

R

、只考慮正斜率，從左下的網格迭代每一個行首的公式是。（負斜率也只需要稍作控制就可以用正數除法的結果迭代）

X_{0} = X_{g r i d}

R_{0} = 0

X_{i} = X_{i - 1} + Q + I n d i c a t o r ((R i - 1 + R) > Δ y)

R_{i} \equiv R_{i - 1} + R (m o d Δ y)

值得注意的是，因為測資保證四個座標點都不同（不會退化成三角形），所以我可以在輸出列中間網格時->迭代行首；輸出走到行尾時->迭代行尾來，進一步共用除法器

Tips: 除法元件通常會是電路中最關鍵的部分，面積大、

T_{p d} 大

，非使用不可時請盡量嘗試共用或將它 pipeline

最後，我在看合成訊息時發現到 compiler 幫我除法取餘各用了一個除法器，所以我就自己刻了一顆除法器，下方有範例程式碼。

Mode1

a (x_{0} y_{0})

：決定直線的一個點

b (x_{1} y_{1})

：決定直線的第二個點

c (x_{2} y_{2})

：圓心

d (x_{3} y_{3})

：圓周上某點

測資會稍微限制大小保證輸入在 6bits 有號數可表示的範圍內。若圓與直線相切則 yo 輸出 2，相割則輸出 1，不相交則輸出 0。

我自己有稍微先重新改寫公式，總之要知道直線是否與圓相切，等效於判斷以下兩個運算式的大小關係

{| \begin{array}{cccc} \vec{a c} \\ \vec{a b} \end{array} |}^{2} ? {| \vec{a b} |}^{2} {| \vec{c d} |}^{2}

c 到 ab 直線的距離可由平行四邊形面積除以ab線段長求得，把這個數值和圓半徑比較就能得到結果

這張圖代表我們可以在不同的時間內利用相同的運算單元，橘色代表 4 個 6bits 數字先兩兩互乘再相加的單元，綠色則代表兩個 13bits 數字的乘法，至於為什麼是這樣設計，就留給讀者自行解讀

Mode2

Mode2 保證四個座標點是一個四邊形座標點逆時鐘或順時鐘排序後的結果，所以我們可以利用　Surveyor 公式求面積：

A r e a = | \frac{1}{2} (| \begin{array}{cccc} x_{0} & x_{1} \\ y_{0} & y_{1} \end{array} | + | \begin{array}{cccc} x_{1} & x_{2} \\ y_{1} & y_{2} \end{array} | + | \begin{array}{cccc} x_{2} & x_{3} \\ y_{2} & y_{3} \end{array} | + | \begin{array}{cccc} x_{3} & x_{0} \\ y_{3} & y_{0} \end{array} |) |

同樣地，我們可以利用累加器和一個行列式單元來實現 mode2。

最後，將輸入同時送到 3 個 mode 的輸入端，最後再用一個控制訊號接出來到 out 就可以完成了

Performance

A r e a

：79.5k

u m^{2}

L a t e n c y

：1

c y c l e / p a t t e r n

R a n k i n g

：4/134