Bài Giảng Kỹ Thuật Số Chương 4
GV: Nguyễn Trọng Hải Trang
104
4.6. MÁY TRẠNG THÁI
Hệ tuần tự còn có tên gọi khác là máy trạng thái (State Machine), tên này
thường sử dụng khi dùng một hệ tuần tự để điều khiển 1 hệ thống số thực hiện
một thủ tục hoặc một thuật toán từng bước một. Có thể đònh nghóa các máy
trạng thái bằng các giản đồ trạng thái, hoặc một kiểu lưu đồ đặc biệt được gọi là
lưu đồ máy trạng thái hay lưu đồ SM (State Machine) dùng để mô tả đặc tính
làm việc của một máy trạng thái
Trong thiết kế số, thường sử dụng từ máy trạng thái để chỉ các mạch đồng bộ
như mạch đếm… ở đó các giá trò ra thay đổi từ một trạng thái nhò phân này sang
một trạng thái nhò phân khác khi mạch được cung cấp xung clock.
SM có hai loại: Moore và Mealy.
4.6.1. Máy trạng thái kiểu MOORE
Sơ đồ khối máy trạng thái kiểu Moore và một mạch counter nhò phân 2bit là một
ví dụ cho máy trạng thái kiểu Moore
+
1
Q
Q1
Mạng tổ
hợp
X
1
X
2
X
m
Q
1
Q
2
Q
k
D1
CK
Q2
D2
CK
Qk
Dk
CK
Clock
Hệ tổ
hợp
(cho


4.7. LƯU ĐỒ MÁY TRẠNG THÁI
Các lưu đồ SM còn được gọi là lưu đồ ASM (Algorithmic State Machine). Lưu
đồ SM cho nhiều thuận lợi trong việc dễ hiểu hơn hoạt động của một hệ thống
số bằng cách quan sát thay vì là giản đồ trạng thái tương đương. Có thể chuyển
một lưu đồ SM cho trước thành nhiều dạng tương đương, và mỗi dạng dẫn trực
tiếp đến một cài đặt phần cứng.
Ba thành phần chính của một lưu đồ SM

Logic
trạng thái
kế
Bộ nhớ
trạng thái

Ngõ CK

Logic ra

1
Z
n
CK
Q2
D2
CK
Qk
Dk
CK
Clock
+
1
Q
+
2
Q
+
k
Q
D1
Mã trạng
thái
tên trạng
thái
(a) Hộp trạng thái
điều kiện
nhánh
đúng
1

qua khối SM. Khi trên đường đi có gặp một hộp xuất theo điều kiện thì các giá
trò ra tương ứng sẽ trở thành đúng. Một đường dẫn qua khối SM từ ngõ vào đến
ngõ ra được gọi là đường dẫn nối ghép (link path)
Ví dụ, một khối SM
khi vào trạng thái S
1
, các giá trò ra Z
1
và Z
2
= 1. Nếu giá trò vào X
1
và X
2
đều

2
3
n
n đường ra
nhánh a
nhánh b
Bài Giảng Kỹ Thuật Số Chương 4
GV: Nguyễn Trọng Hải Trang
107
kế qua đường ra 1, ngược lại nếu X
1
=1 và X
3
= 0, giá trò ra Z
5
= 1 và đi vào
trạng thái kế qua đường ra 3
Tổng quát thì một khối SM có thể được vẽ bằng nhiều dạng khác nhau. Hai khối
SM sau là tương đương.
0
0
1
0
1
Z
1

S
1

X
3
Z
2
0 1
0
1
S
2

S
3
Z
1

S
1
X
2 Một khối SM có thể có nhiều đường song song mà dẫn đến cùng một đường ra,
và hơn một đường trong các đường này có thể tích cực đồng thời. Ngoài ra cũng
có thể biểu diễn bằng một khối SM nối tiếp tương đương. Trong khối nối tiếp
này có thể có một đường dẫn nối ghép tích cực duy nhất giữa ngỏ vào và ra. Với
bất cứ tổ hợp nào của các giá trò vào, các giá trò ra sẽ giống như trong dạng song
song tương đương.
Ví dụ,


3
(a) dạng song song

Z
1
X
1
Z
2
X
2
Z
3
X
3
Z
3
(b) dạng nối tiếp

Bài Giảng Kỹ Thuật Số Chương 4
GV: Nguyễn Trọng Hải Trang
109
Có thể chuyển một giản đồ trạng thái của máy tuần tự sang lưu đồ SM tương
đương một cách dễ dàng.
Ví dụ, Giản đồ trạng thái S
0
Z
a
S
1
Z
b
S
2

Z
c

1/0
0/0
1/0
0/Z
1
0/0

1/Z
2

Z
a
X


1

link 3

clock
trạng thái
X
S
0
S
1
S
2
S
2
S
0
S
0
Z
a
Z
b
Z
c
Z
1
Z
2
Bài Giảng Kỹ Thuật Số Chương 4

2

Ở giản đồ đònh thì cho lưu đồ SM, với chuỗi vào X=1,1,1,0,0,0. Tất cả các thay
đổi trạng thái xảy ra ngay sau cạnh lên của xung nhòp. Vì các giá trò Moore phụ
thuộc vào trạng thái và chỉ có thể thay đổi tức thời sau 1 thay đổi trạng thái hoặc
một thay đổi giá trò vào. Nói chung, tất cả các giá trò ra sẽ có giá trò đúng của
chúng ở cạnh tích cực của xung nhòp
Ví dụ, Lập lưu đồ SM cho bộ chia nhò phân song song cho các số nhò phân
dương, số bò chia (dividend) 6 bit cho số chia (divisor) 3 bit để có được thương 3
bit.
Minh họa quá trình chia

Phép chia có thể thực hiện bằng phép toán trừ và dòch. để xây dựng bộ chia sẽ
sử dụng thanh ghi số bò chia 7 bit và thanh ghi số chia 3 bit như sau


khiển
Sh
Su
C (so sánh)
clock

V

Chỉ báo tràn trên
start
100010 110
110 101
101
000
1010
110
100
Bài Giảng Kỹ Thuật Số Chương 4
GV: Nguyễn Trọng Hải Trang
111
chia để cho không mất 1 bit khi dòch trái số bò chia. Thay vì dùng 1 thanh ghi để
chứa thương số, có thể đưa thương số từng bit một vào đầu bên phải của thanh
ghi số bò chia khi dòch trái số bò chia
Nếu ban đầu x
7
x
6
x
5
x

muốn. Bất cứ lúc nào C=1, tín hiệu trừ được tạo ra và bit thương số được đặt lên
Giản đồ trạng thái của mạch điều khiển Ban đầu số bit chia 6 bit và số chia 3 bit được đưa vào các thanh ghi thích hợp.
Mạch vẫn ở trạng thái dừng Stop (S
0
) cho đến khi có tín hiệu Start. Nếu giá trò
ban đầu của C=1, thương số sẽ cần 4 bit trở lên. Vì không gian chỉ cung cấp cho
thương số 3 bit, điều kiện này làm tràn trên do đó bộ chia dừng và bộ chỉ tràn sẽ
đặt lên 1 bằng ngõ ra tràn trên.
Bình thường giá trò ban đầu của C=0, vì vậy dòch sẽ xảy ra đầu tiên và mạch sẽ
đi vào trạng thái S
1
. Rồi nếu C=1 thì xảy ra trừ. Sau khi hoàn tất trừ C sẽ luôn
luôn bằng 0 vì vậy xung nhòp kế sẽ tạo ra dòch. Quá trình này tiếp tục cho đến
khi xảy ra 3 lần dòch và điều khiển ổ trong trạng thái S
3
. Rồi phép trứ cuối cùng
xảy ra nếu cần, và điều khiển quay về trạng thái dừng. Với vd này sẽ giả sừ là
khi tín hiệu bắt đầu (start) xảy ra nó sẽ là 1 trong thời gian 1 clock và rồi giữ là

GV: Nguyễn Trọng Hải Trang
112
Từ đó suy ra lưu đồ SM như sau

S
0
là trạng thái bắt đầu, nếu Start=1, tín hiệu so sánh C được kiểm tra, nếu C=1,
thương số lớn hơn 3 bit, vì vậy báo tràn V=1 được tạo ra và không có sự thay đổi
xảy ra. Nếu C=0, Sh=1, ở xung nhòp kế số bò chia được dòch sang trái và trạng

Start
C
V
0

1

1

0
Sh
S
1
C
Su
0

1

Sh
S
2
C
Su
0
1
Sh
S
3
C


Ví dụ, nhân 13 x 11 được làm lại sau đây chỉ vò trí các bit trong các thanh ghi ở
mỗi thời điểm xung nhòp

Nội dung ban đầu của t.ghi tích
lũy (cộng số bò nhân vì M=1)
000001011
1101
M(11)
(13)
Sau khi cộng
Sau khi dòch phải
Cộng số bò nhân vì M=1
011011011
001101101
1101

M=1
Sau khi cộng
Sau khi dòch phải
100111101
010011110

M=0

P
C
C
Thanh ghi tích so
á

Số nhân
P
C
Sh
M=1: cộng &dòch
M=0: dòch

Ad: tín hiệu cộng
Sh: tín hiệu dòch
P
C
: xung clock
M: bit bộ nhân
N: tín hiệu start
C: số nhớ
Bài Giảng Kỹ Thuật Số Chương 4
GV: Nguyễn Trọng Hải Trang
114
Giản đồ trạng thái cho điều khiển bộ nhân, SV giải thích tương tự như mạch chia
xuất K=1 trước khi lần dòch cuối cùng xảy ra. Lưu đồ SM cho điều khiển bộ
nhân tương ứng với giản đồ trạng thái hình (c)

S
0
S
2
S
6
S
4
S
7
S
1
S
3
S
5
MN/Ad
-/Sh
M/Ad
-/Sh
M/Ad
- /Sh
M/Ad
-/Sh
N’/0
M’N/Sh
M’N/Sh

S
0
M’N/Sh
MN/Ad
N’/0
K/Sh
K’/Sh
M’K’/Sh
(c) Giản đồ trạng thái cuối
của điều khiển cộng dòch
M’K/Sh
M/Ad
Bài Giảng Kỹ Thuật Số Chương 4
GV: Nguyễn Trọng Hải Trang
115

Ad
Sh
K
M
Ad
Sh
M
S
1
S
2
0
1
10
1 0
10
10
Bài Giảng Kỹ Thuật Số Chương 4
GV: Nguyễn Trọng Hải Trang
116
4.8. BỘ NHỚ BÁN DẪN
Bộ nhớ bán dẫn chia làm hai loại chính
• Bộ nhớ bảng (table memory)
• Bộ nhớ hàm (function memory)

Với m là độ rộng từ dữ liệu, n là số đòa chỉ
Tính theo byte (K/8) cho các độ rộng từ dữ liệu là 8 hay 16 bit
Bộ nhớ bán dẫn
Bộ nhớ bảng
Bộ nhớ hàm
RAM
ROM
Tónh
Động
MROM
PROM
EPROM
EPROM
PLD
PLA
PAL
PPAL
EPPAL
EEPPAL
LCA EPLD
PEEL
(Pro.
elec.
erasable
logic
GAL
(generic
array
logic)
Bài Giảng Kỹ Thuật Số Chương 4

1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
d
01
d
11

d
21
d
31
d
41
d

2
D
3
D
4
D
5
D
6
D
7

Bộ nhớ hàm
• Chứa các hàm logic (Boolean) thay vì là các bảng. Mỗi biến của bảng chân
trò có thể được biểu diễn bằng hàm logic.
Viết dưới dạng tích chuẩn thì hàm logic của biến d
0
ở ví dụ trên là
0210002110 21070
d = a .a .a d +a .a .d + +a a a d
= m
0
d
00
+ m
1
d
10
+…+m
7

4.9. ROM - THIẾT KẾ HỆ THỐNG SỐ DÙNG ROM
4.9.1. ROM
ROM là một mạch tổ hợp có n ngõ vào và m ngõ ra. Các ngõ vào được gọi là
đòa chỉ (address input) và thường được đặt là A
0
A
1
…A
n-1
. Các ngõ ra được gọi là
các ngõ ra dữ liệu (data output) và thường đượpc đặt tên là D
0
D
1
D
2
…D
m-1
Hình 1-2. Cấu trúc cơ bản của một ROM 2
n
x m

0
A
1
A
2
A
n-1
D
0
D
1
D
2
D
m-1
address
input
(n đường)
address
output
(m đường)
Input Output
A
2
A
1
A
0
D
3

1
1
1
0
0
0
0
1
1
1
0
1
0
0
1
0
1
0
1
1
0
1
0
0
0
1
1
1
1
0

B0:
C0:
D0:
E0:
F0:
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
01
02
03
04
05
06
07
08

15
18
1B
1E
21
24
27
2A
2D
00
04
08
0C
10
14
18
1C
20
24
28
2C
30
34
38
3C
00
05
0A
0F
14

Cơ chế sử dụng ROM để lưu trữ thì thay đổi ứng với các công nghệ của ROM
khác nhau. Trong phần lớn các ROM, sự xuất hiện hoặc vắng mặt của một
diode hay transistor sẽ phân biệt giữa 0 và 1
Cấu trúc với giải mã 1 chiều 256 x 8 ROM
A
0
A
1
A
2
A
7

D
0
D
1
D
2
D
7
Y
(Số bị nhân)
Tích số
A
3
AMỗi đường ra bộ giải mã được gọi là đường từ (word line) bởi vì nó chọn một
hàng hoặc một từ của bảng chứa trong ROM
Mỗi đường thẳng đứng trong hình được gọi là đường bit (bit line) bởi vì nó tương
ứng với một bit ra của ROM
Nhận xét: có diode tương ứng mức 0, không có diode tương ứng mức 1
Các MOS ROM thường dùng transistor thay vì là diode ở mỗi vò trí mà bit sẽ
được lưu trữ.
Cấu trúc với giải mã 2 chiều
Nếu xây dựng một ROM 128x1 dùng cấu trúc ở phần trước phải sử dụng một bộ
giải mã 7 sang 128, nghóa là phải sử dụng đến một lượng lớn 128 các cổng
NAND 7 ngõ vào, nếu thiết kế cho ROM với hàng triệu bits hoặc nhiều hơn sẽ
không có bộ giải mã 20 sang 1048576. Thay vào đó người ta sẽ sử dụng cấu trúc
khác được gọi là giải mã hai chiều (two-dimentional decoding)
D1A0
A

B
3 bit đòa chỉ cao A
6
A
5
A
4
sẽ chọn hàng, mỗi hàng chứa 16 bit bắt đầu tại đòa chỉ
A
6
A
5
A
4
0000. Khi đặt đòa chỉ cho ROM, 16bit ở hàng được chọn đưa vào bộ MUX và
4 bit đòa chỉ thấp sẽ chọn bit data mong muốn.
Ngoài việc giảm tính phức tạp việc giải mã, giải mã 2 chiều có một thuận lợi khác
là ROM có một kích thước vật lý gần vuông, điều này quan trọng cho việc chế tạo
và đóng gói IC
Với ROM có nhiều ngõ ra dữ liệu, các dãy lưu trữ tương ứng với mỗi ngõ ra dữ liệu
có thể được làm hẹp hơn để đạt được bố trí chip gần với hình vuông hơn.
Ví dụ, Một bố trí của ROM 32K x 8


A
9

A
13

A
14
512 x 64
array

512 x 64
array

512 x 64
array

512 x 64
array

512 x 64
array 512 x 64
array


MUX

A
0

A
1

A
2

A
3

A
4

A
5

A2
A
4
A

B
C
G1
G2A


Bảng các kiểu ROM thương mại
Kiểu Công nghệ Chu kỳ đọc Chu kỳ ghi Chú thích
Mask ROM
Mask ROM

PROM

EPROM
EEPROM
NMOS, CMOS
Bipolar

Bipolar

NMOS, CMOS
NMOS
25 – 500ns
<100ns

<100ns

25-500ns
50-500ns
4 tuần
4 tuần

5 phút

5 phút
10ms/bytes

Enable (OE: cho phép xuất) để cho phép các ngõ ra
Nhiều ứng dụng ROM đặc biệt là ứng dụng lưu trữ chương trình sẽ có nhiều
ROM được nối chung vào 1 BUS, mỗi lần chỉ có 1 ROM lái BUS. Phần lớn các
ROM có ngõ vào chip select (CS: chọn chip) để làm đơn giản việc thiết kế các
hệ thống. Ngoài OE còn cần phải có CS để cho phép ngõ ra 3 trạng thái
Tuy nhiên trong nhiều ROM, CS cũng làm việc như ngõ vào cắt nguồn cấp điện
(power down input), CS ở mức không tích cực thì không cấp nguồn cho các
decoder nội, các driver và các MUX của ROM. Ở chế độ chờ này (standby
mode) 1 ROM tiêu thụ ít hơn 10% công suất so với chế độ hoạt động (active
mode).
2764
10
9
8
7
6
5
4
3
25
24
21
23
2
20
22
27
1
11
12

O7
27128
10
9
8
7
6
5
4
3
25
24
21
23
2
26
20
22
27
1
11
12
13
15
16
17
18
19
A0
A1

5
4
3
25
24
21
23
2
26
27
20
22
1
11
12
13
15
16
17
18
19
A0
A1
A2
A3
A4
A5
A6
A7
A84.9.5. Thiết kế hệ tuần tự dùng ROM
Có thể thiết kế dễ dàng một hệ tuần tự dùng ROM kết hợp với các FF.
Mô hình tổng quát của hệ tuần tự dùng ROM và các D-FF có xung nhòp

Phần tổ hợp của hệ tuần tự có thể dùng ROM để thực hiện các hàm ra (Z
1
, Z
2
, …,
Z
n
) và các hàm trạng thái kế (Q
1
+
, Q
2
+

n-1
CS

OE

Q1
Z
2
ROM
X
1
X
2
X
m
Q
1
Q
2
Q
k
Z
1
Z
n
CK
Q2
D2
CK
Qk

2
t
1
t
0
t
3
t
2
t
1
t
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
1

1
1
1
0
1
1
1
1
0
0
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1

reset A B C 1 0
t
1
0
1
B
C
D
E
F
G
1
0
0
1
t
2
00
01
10
11
D
E
F
G
H
I
J
K
L

A
A
A
A
A
A
A
A
A
-
-
-
-
-
-
0
0
0
0
0
1
1
1
1
1
-
-
-
-
-

2
D
E
H
H
H
M
0
1
1
0
t
3
H
M
A
A
A
-
0
1
1
-
Có thể dùng một cách khác để suy ra bảng trên bằng cách bắt đầu bằng giản đồ
trạng thái.
Giản đồ trạng thái có dạng hình cây. Mỗi đường bắt đầu ở trạng thái reset biểu
diễn một trong 10 chuỗi vào có thể có

Z
0 1
t
0
A 000 010 011 1 0
t
1
B
C
010
011
101
100
100
100
1
0
0
1
t
2
D
E
101
100
111
111
111
110
0

0/1
1/0
0/0
1/1
0/1
1/0
0/1
1/0
0/1
1/0
1/1
0/0
1/0
Reset
t
2
t
3
0/0 1/1
0/0 0/0 0/1
0/0 1/1
0/1 0/0 0/1
Bài Giảng Kỹ Thuật Số Chương 4
GV: Nguyễn Trọng Hải Trang
126
Cài đặt bộ chuyển đổi mã này dùng ROM và các D-FF. Vì có 7 trạng thái nên
cần 3 DFF. Như vậy cần ROM có 4 input (2
4
word) và 4 output . Dùng gán nhò
phân trực tiếp, xây dựng bảng chuyển trạng thái cho trạng thái kế của các D-FF

)

(a) Bảng trạng thái (b) bảng chuyển trạng thái
T. thái
h.tại
T. thái kế
X=0 X=1
G.trò ra h.tại Z
X=0 X=1
Q
1
Q
2
Q
3
Q
1
+
Q
2
+
Q
3
+

X=0 X=1
Z
X=0 X=1
A B C 1 0 A 000 001 010 1 0
B

0
D
E
011
100
101
101
101
110
0
1
1
0
H
M
A
A
A

0
1
1

H
M
101
110
000
000
000

0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1

0
1
0
1
1
1
0
0
1
0
1
x
0
0
1
1
0
1
x
x
0
0
1
1
1
0
0
x
0
1

0
0
0
1
0
0
x
x Bài Giảng Kỹ Thuật Số Chương 4
GV: Nguyễn Trọng Hải Trang
127
Cài đặt mạng tuần tự dùng ROM
4.10. PLD tổ hợp (Combinational PLD)
5.3.1. Dãy logic lập trình được (PLA)
PLA thực hiện cùng chức năng cơ bản như ROM. Một PLA với n input và m
output có thể cài đặt m hàm của n biến. Tổ chức nội của PLA thì khác với tổ
chức nột của ROM
Cấu trúc PLA (PLA nxm với p số hạng tích)


1
Q
1
Q
2
Q
3
Z

D1
CK
Q2
D2
CK
Q3
Dk
CK
Clock Dãy
AND Dãy
OR
n
input
p đường word
(số hạng tích)


Bảng PLA cho PLA ở trên
a b c d F
1
F
2
F
3
0
1
1
-
-
-
1
1
0
0
-
1
-
-
0
1
1
1
1
1
-
-

dãy OR là cố đònh. Cấu trúc cơ bản của PAL thì giống như PLA
Một đoạn PAL
a'
a'bd
d
b
a'
a'bd
b d
F3
a'bd
c
a'bd
c
ab'c'
ab'c'
bc
bc
F3