---
title: Analysis of Clocked Sequential Circuits|第十二週
tags: 數位系統與實驗
---

在前一個章節中我們是有一個想要達成的目標，然後設計出電路來；而這裡我們則是給一個電路，然後要分析他做了甚麼事情。

# Parity Checker

## Error detection & Parity bit

傳送資料的時候，可以用一個很簡單的方式達成資料的校驗，就是「奇偶校驗」。
而實現的方法，就是在資料的最尾端加上 1 個 bit 代表這串數據中「 1 的個數」有幾個，這個最尾端的 bit 就是[「同位位元 Parity bit」](https://zh.wikipedia.org/zh-tw/%E5%A5%87%E5%81%B6%E6%A0%A1%E9%AA%8C%E4%BD%8D)。


你可以有兩種表達方式，如上圖：

- Even Parity：
- 最尾端的 bit 會讓整體 1 的個數變成偶數
- Odd Parity：
- 最尾端的 bit 會讓整體 1 的個數變成奇數

例如左邊第一個的 00000000，因為他已經是偶數了，所以 Parity bit 就是 0。

### 實際使用的可能方式如下

將接收到的資料全部 XOR 起來後，將得到的值跟最後一個 bit 做比較，如果一樣的話代表傳輸成功，不一樣的話就是傳輸失敗。
[參見 wiki](https://en.wikipedia.org/wiki/Parity_bit#Error_detection)

## 設計一個 Odd-Parity Checker

如果我們想要設計一個可以檢查 Odd-Parity 正確性的電路，例如下圖


我希望有個一個一個讀入 X，然後輸出的 Z 會告訴我們現在的 1 的個數是否是奇數個。

例如下面的時序圖(Falling Edge)：


## 狀態 State

那麼這時候，畫出狀態圖 State Graph 就是一個很好的辦法：


或者我們也可以畫出狀態表 State table；首先先畫出 State 的變化關係：


然後再把該 State 的值填入，在這裡就是 Z 值：


這時候觀察一下 Present Output，也就是「當前 State」的輸出，你會發現：

- 如果 X = 1，則 Q^+^ 跟 Present Output 是顛倒的
- 如果 X = 0，則 Q^+^ 跟 Present Output 是一樣的

這不就是 TFF 在做的事情嗎，於是我們就可以用 TFF 來達成我們的目的。


---

# Find the output sequence

接下來我們要學會如何分析有時序的序列電路 Analyze the Clocked Sequential Circuits，也就是畫出輸出值的序列。

下面也順便介紹計概提到的 Moore Machine 跟 Mealy Machine。

# Moore Machine 例子

:::info
Moore Machine：輸出只跟「當前狀態 Present State」有關
:::

首先我們有一個電路：


## 時序圖

開始分析的方法，我們先從時序圖下手：

上面假設一開始 ABX 都是 0，然後你可以根據各個 DFF 前面的邏輯閘將結果依序產生出來。
例如第一個 CLK，AB 都是 0，X 也是 0，所以我們可以知道

$$
A^{+} = D_{A} = B'\oplus X = 1\\
B^{+} = D_{B} = A+X=0\\
Z = A\oplus B = 1\\
$$


從過程可以發現，Z 的結果只跟 AB，也就是當前的 State 有關係，所以可以知道這是一個 Moore Machine

# Mealy Machine 例子

我們換一個更複雜的電路，這裡我們用 JK FF：


而我們的 Z 長得像下面這樣


$$
Z=XB'+XA+X'A'B
$$

## 時序圖

此時我們一樣來分析時序圖；在一開始，AB 都是 0，X 是 1，根據上面的邏輯，可以看到由上數來第 1 個 AND 閘輸出會是 1，所以 Z 是 1 沒有錯。


首先看向第 1 個 Falling，首先根據 JK 的邏輯，可以知道 AB 在這個 CLK 之後會變成 1 跟 0；所以 X 是 1、A 是 0、B 是 1，根據上面的邏輯閘，Z 的輸出會是 0。

但是這時候，可以看到 X 之後又等於 0，我們這裡假設延遲沒有很高，所以這個時刻 X = 0，A = 0，B = 1，根據上面的邏輯，可以知道 Z 會等於 1。

### Glitches 或 Spikes

所以可以看到 Z 在那段時間有個小小的凹陷；在後面的第 3 個 CLK 也可以看到 Z 有個小小的突起，這些突然的改變叫做 Glitches 或 Spikes。

那麼這些東西好嗎？

## 在意的點

從 Mealy Machine 的時序圖可以看到可能會有一些小小的突然變化，但是呢，這些變化只會在 CLK Falling 後出現。

**所以我們 Mealy 在意的是 CLK 改變之前 Z 的狀態**

從上圖也可以知道，在 CLK 改變之前的 Z 值依序為 1 1 0 0 1，這也跟他的邏輯式子告訴我們的結論是一樣的。

雖然這個電路會有 Glitches 或 Spikes 的存在，但是不會影響我們電路想要的結果的正確性。

---

# Construct the State Table

現在換要如何建立狀態表格。

# Moore Machine 例子

這是跟剛剛一樣的電路：


## 寫出式子

找出表格的第一步，就是把他們的式子寫下來，並畫出卡諾圖：

$$
A^{+} = D_{A} = B'\oplus X = 1\\
B^{+} = D_{B} = A+X=0\\
Z = A\oplus B = 1\\
$$

然後就可以建立好狀態表格了。
例如第一列是 AB 都是 0，那麼就會對應到上面兩個卡諾圖的第一列。


## 建立狀態圖 State Graph

有了上面的狀態表格後，我們來定義狀態的名稱。下面給個定義的例子：


我們給 AB = 00 定義為 S~0~，AB = 01 定義為 S~1~，以此類推。
這樣我們就得可以畫出我們的狀態圖了：


# Mealy Machine 例子

這是跟剛剛一樣的電路：


而我們的 Z 長得像下面這樣


## 寫出式子

所以一樣，先找出每個式子：

$$
J_{A} = XB\\
K_{A} = X\\
J_{B} = X\\
K_{B} = XA\\
A^{+} = J_{A}A' + K_{A}'A = XBA'+X'A\\
B^{+} = J_{B}B' + K_{B}'B = XB' + X'B + A'B\\
Z=XB'+XA+X'A'B\\
$$

然後一樣畫出卡諾圖；最後有了卡諾圖，一樣可以畫出狀態表格：



## 狀態圖

有了狀態表格後，剩下的就是自己定義狀態了：


然後就可以畫出下面的狀態圖：


可以看到跟 Moore 的畫法不一樣的是，在狀態跟狀態之間的連線，表示法變成了「a/b」，其中 a 代表的是輸入的值，b 代表的是輸出的值。
而 moore 因為跟輸入沒有直接的關係，所以才只有一個值，代表輸出。

# Multiple Inputs and Outputs

如果覺得上面的還不過癮的話，下面有多變數的例子：


可以看到這是一個兩個輸入和兩個輸出的例子。


---

# General Model

## Moore Machines

下面是普遍的模型樣子。可以看到輸出 Z 前面的 Combinational Subcircuit 的輸入就只有「當前的輸入 Q」。


## Mealy Machines

下面是普遍的模型樣子。可以看到輸出 Z 的 Combinational Subcircuit 是跟輸入的 Combinational Subcircuit 在一起的，代表輸出除了跟「當前的狀態」有關係之外，也跟「當時的輸入」有關係。


:::warning
小小結論：
可以發現，FF 的右手邊都是「當前的狀態 Current State」，而左邊 Combinational Subcircuit 產生的結果是「新的狀態 Next State」。
因此左邊的電路又叫做「Transitional Logic」或「Next State Logic」，而右邊的電路可以叫做「Output Logic」；
然後雖然 Mealy 的兩個看起來是合在一起的，但是其實你一樣可以把「Next State Logic」跟「Output Logic」分開來畫。
:::