---
# System prepended metadata

title: Chap 14 Derivation of State Graphs and Tables
tags: [SCLD]

---

---
###### tags: `SCLD`
---

# Chap 14 Derivation of State Graphs and Tables

## 14.1 Design of a Sequence Detector
example: 
design the circuit so that any input sequence ending in 101 will produce an output Z = 1
coincident with the last 1
![](https://i.imgur.com/SykESm6.png)
*the symbol before the slash is the input and the symbol after the slash is the corresponding output*

#### Mealy machine
<!-- partial -->
<!-- <img src="https://i.imgur.com/WXhooFk.png" height="110">
<img src="https://i.imgur.com/YetqZYb.png" height="110"> -->
<!-- complete -->
<img src="https://i.imgur.com/ZW6bi06.png" height="160">

target: S~0~S~1~S~2~ = 101
S~0~: get 1 →store it ; get 0 → again

![](https://i.imgur.com/GekEaDE.png)
S~0~ S~1~ S~2~ 基本上可以隨便代  
(i.e. S~0~ 可以 00 or 01 or whatever 代替)  
出來的電路、SOP 會不一樣，但實質結果是相同的  
![](https://i.imgur.com/NHIP3HM.png)
![](https://i.imgur.com/q3g2yOT.png)
![](https://i.imgur.com/DOucbYQ.png)
    
#### Moore machine
<!-- ![](https://i.imgur.com/TOQeVDt.png)
![](https://i.imgur.com/U3eZ7m6.png) -->
<!-- Mealy: output 跟著弧線
Moore: output 不在弧線上， so S~2~=1 時不可回到 S~1~(whose output is 0) 如 Mealy   -->
![](https://i.imgur.com/95neCTK.png)

![](https://i.imgur.com/FLf5Rhw.png)
![](https://i.imgur.com/kZnFLnu.png)

initial state = 1  
→ ++01++000 underline part Z=1


## 14.2 More Complex Design Problems
#### a Mealy example
The output Z should be 1 if the input sequence ends in either 010 or 1001, and Z should be 0 otherwise.
![](https://i.imgur.com/G4r6GBs.png)

010|
_10|01

1001|
__ 01|0

"|": 接在一起處
<!-- ![](https://i.imgur.com/d2gcU7w.png) -->
<!-- ![](https://i.imgur.com/S4peiBW.png) -->
![](https://i.imgur.com/jfknW9W.png)

#### a Moore example
The output Z is to be 1 if the total number of 1’s received is ++odd++ and at least ++two consecutive 0s++ have been received.  
![](https://i.imgur.com/G1AIn3f.png)
![](https://i.imgur.com/JM6XZ9a.png)
<!-- partial -->
<!-- ![](https://i.imgur.com/femZ8Vr.png) -->
<!-- complete -->
![](https://i.imgur.com/ZPM8KJm.png)

## 14.3 Guidelines for Construction of State Graphs
The circuit examines groups of four consecutive inputs and produces an output Z = 1 if the input sequence 0101 or 1001 occurs. The circuit resets after every four inputs.  
【Mealy】  
![](https://i.imgur.com/GC5i3At.png)
0101 & 1001 可共用  
<!-- partial   -->
![](https://i.imgur.com/rQ6glQN.png)
<!-- complete   -->
![](https://i.imgur.com/RLUx8Lb.png)
錯的 → 進到紅框區 → output 0  
![](https://i.imgur.com/B7QHQqQ.png)
a group of 5 → 下面再多一層 以此類推  

==跳過 example 2, 3==

## 14.4 Serial Data Code Conversion
![](https://i.imgur.com/ZmwxkfF.png)
![](https://i.imgur.com/sXcSuAb.png)
NRZ：non return to zero, 不變  
RZ：return to 0, 變 1 後, 後半變回 0  
NRZI：inverted, 看 1 的奇偶 (i.e. 0 → Q^+^=Q ; 1 → Q^+^=Q') 
Manchester：0 → 後半變 1 ; 1 → 後半變 0  

#### Mealy ver.  
NRZ {→|convert} Manchester  
![](https://i.imgur.com/dbIBn5v.png)  

ideal：忽略延遲  
actual：有延遲，出現 false output  
![](https://i.imgur.com/WQ78XTI.png)   
<!-- clock2 頻率 2 倍 for manchester   -->
clock2 頻率 2 倍 → 所有 output changes 都在 edge 上  
NRZ stable for 2 clock2 period  
clock change but input hasn't → glitch  

![](https://i.imgur.com/l6Yve1B.png)  
![](https://i.imgur.com/aZPkzLX.png)  
S~1~ 完不會有 1 so －  

#### Moore ver.
NRZ {→|convert} Manchester  
![](https://i.imgur.com/Ni6lSW1.png)
![](https://i.imgur.com/Woy2JeW.png)
![](https://i.imgur.com/Wpxqdic.png)


## 14.5 Alphanumeric State Graph Notation
(a) F → forward ; R → reverse  
(b) 考量到 FR=11,00
![](https://i.imgur.com/D56a6N3.png)
![](https://i.imgur.com/RxkSPd9.png) 

從 S~0~ 發出的線  
3 條線 or 在一起，為 1 → 至少一條為 1  
`F + F′R + F′R′ = F + F′ = 1`  
3 條線兩兩 and 在一起，皆為 0 → 小於 2 條為 1  
`F·F′R = 0, F·F′R′ = 0, F′R·F′R′ = 0`  
→ 恰好 1 條為 1

for Mealy：  
X~i~X~j~/Z~p~Z~q~ means if X~i~X~j~ = 11 (other Xs don't care), Z~p~Z~q~ = 11 (others Zs = 0)  
e.g. X1X4′/Z2Z3 means 1--0/0110  



## 14.6 Incompletely Specified State Tables
#### BCD (0~9 in binary i.e. 0000-1001)  
while in last bit:  
if 1s = even → 1  
else → 0
![](https://i.imgur.com/sYt2AoI.png)
![](https://i.imgur.com/KSrkcC7.png)

#### 101 disjoint, output only used in the end
![](https://i.imgur.com/MOxSAJG.png)
![](https://i.imgur.com/WAVaEKf.png)


## Problems
#### 14.16
![](https://i.imgur.com/hZ0Gmhe.png)
![](https://i.imgur.com/JiypuqC.png)
ans  
![](https://i.imgur.com/F5c7rDE.png)

#### 14.31
![](https://i.imgur.com/09Ej0us.png)
![](https://i.imgur.com/JH3T2Vg.png)  
ans  
![](https://i.imgur.com/p20EnfQ.png)

#### 14.33
![](https://i.imgur.com/CWBicSv.png)
ans  
![](https://i.imgur.com/hQl7p0D.png)
![](https://i.imgur.com/9IVDpJP.png)

#### 14.38
![](https://i.imgur.com/ejNtIex.png)
ans  
![](https://i.imgur.com/CQQvYNt.png)

#### 14.43
![](https://i.imgur.com/CZLzYcW.png)
ans  
![](https://i.imgur.com/97RWeo5.png)
![](https://i.imgur.com/0SGmFJV.png)


#### 14.45
![](https://i.imgur.com/tBlGjeg.png)
ans  
![](https://i.imgur.com/zPnf1O8.png)
