Lab2 21522554. Môn Thực hành môn kiến trúc máy tính | Đại học Trường Đại học Công nghệ thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh.

lOMoAR cPSD| 59285474
BÁO CÁO THỰC HÀNH 2
THIẾT KẾ LUẬN LÝ SỐ
Họ tên: Nguyễn Đình Sơn MSSV: 21522554 Lớp: CE118.N23.MTCL.2
LAB 2: THIẾT KẾ MÁY TRẠNG THÁI HỮU HẠN LÝ THUYẾT
Finite State Machine (FSM) hay Máy trạng thái hữu hạn, là một phương pháp thiết kế
mạch bằng cách mô hình hóa mạch tuần tự bằng một mô hình toán học, sau đó sẽ hiện
thực mô hình toán học này xuống phần cứng.
FSM gồm có 3 thành phần cơ bản như sau:
1. Mạch tạo trạng thái kế tiếp (Next state logic) là mạch tổ hợp phụ thuộc vào ngõ
vào FSM và giá trị trạng thái hiện tại lấy từ bộ nhớ trạng thái (state memory)
2. Bộ nhớ trạng thái (state memory) là phần tử lưu trạng thái hiện tại của FSM nó
có thể là Flip-Flop, Latch, ... lấy ngõ vào từ mạch tạo trạng thái kế tiếp. Bộ nhớ
trạng thái thường được sử dụng trong các thiết kế đồng bộ là FF hoạt động theo
xung clock. Một tín hiệu reset có thể phải sử dụng để khởi động FSM đến một
giá trị ban đầu. Reset không cần sử dụng đối với các FSM luôn hoạt động đúng
dù giá trị ban đầu của FF là bao nhiêu.
3. Mạch tạo ngõ ra (output logic) là mạch tổ hợp tạo giá trị ngõ ra tương ứng với
trạng thái hiện tại của FSM. Mạch này lấy ngõ vào là giá trị trạng thái hiện tại và
có thể tổ hợp thêm ngõ vào của FSM Phân loại lOMoAR cPSD| 59285474
FSM được chia làm 2 loại:
1. FSM Moore là loại có mạch tạo ngõ ra không phụ thuộc trực tiếp vào ngõ vào FSM
2. FSM Mealy là loại có mạch tạo ngõ ra phụ thuộc trực tiếp vào ngõ vào FSM Hình 2. FSM Moore Hình 3: FSM Mealy
Sơ đồ trạng thái là một cách biểu diễn chức năng của một FSM hướng đồ thị trực quan
và dễ hiểu đối với những FSM đơn giản. Ví dụ: lOMoAR cPSD| 59285474
Cấu tạo của một sơ đồ trạng thái bao gồm: -
Các trạng thái (hay còn gọi là các nút): Mỗi trạng thái được biểu diễn bởi một
hình tròn bao quanh tên của trạng thái hoặc chuỗi bit mã hóa cho trạng thái. -
Các đường chuyển trạng thái (hay còn gọi là các cạnh): Việc chuyển trạng thái
được biểu diễn bằng các mũi tên kết nối từ trạng thái này tới trạng thái khác kèm theo
điều kiện chuyển trạng thái. Điểm xuất phát của mỗi mũi tên được gọi là trạng thái hiện
tại, điểm kết thúc của mỗi mũi tên được gọi là trạng thái kế tiếp. Điều kiện chuyển trạng
thái thường là điều kiện của các ngõ vào hoặc thậm chí là không có điều kiện. Việc
chuyển trạng thái diễn ra khi ngõ vào clock tích cực. -
Ngõ ra: Có 2 cách để biểu diễn ngõ ra trên sơ đồ trạng thái tùy thuộc vào loại
FSM. Nếu là Moore FSM thì ngõ ra sẽ nằm bên dưới trạng thái (hình 2.4a), còn nếu là
Mealy FSM thì ngõ ra sẽ nằm bên cạnh của các điều kiện chuyển trạng thái (hình 2.4b).
Sơ đồ trạng thái vừa tìm hiểu cho chúng ta một cái nhìn trực quan và phù hợp với suy
nghĩ của con người về việc chuyển trạng thái diễn ra như thế nào. Nhưng khi số lượng
trạng thái, số lượng ngõ vào và số lượng ngõ ra tăng lên thì phương pháp biểu diễn này
trở nên phức tạp. Để khắc phục được những nhược điểm này, một phương pháp mới –
bảng trạng thái được sử dụng.
Bảng trạng thái là một cách nhìn trực quan khác được sử dụng để biểu diễn chức năng
của một FSM. Khi số lượng trạng thái tăng lên thì bảng trạng thái sẽ mở rộng thêm về
số lượng các hàng, khi số lượng ngõ vào hoặc ngõ ra tăng lên thì chỉ cần tăng thêm số
cột. Việc tăng số lượng hàng và cột thì không ảnh hưởng nhiều đến việc học hiểu chức năng FSM bởi con người. lOMoAR cPSD| 59285474
Bảng trạng thái là hoàn toàn tương đương với sơ đồ trạng thái, chúng ta có thể ánh xạ
1:1 từ sơ đồ trạng thái thành bảng trạng thái. Ví dụ chúng ta có thể ánh xạ sơ đồ trạng
thái trong hình 2.4a thành bảng trạng thái như trong bảng 2.1
Đối với Mealy FSM thì bảng trạng thái có hơi chút khác biệt. Sơ đồ trạng thái trong hình
2.4a có thể được ánh xạ thành bảng trạng thái như trong bảng 2.2 hoặc bảng 2.3
Rút gọn trạng thái: số lượng trạng thái của một FSM là một con số có thể thay đổi tùy
thuộc vào người thiết kế để thỏa hiệp giữa số lượng các bit trạng thái và độ phức tạp của
hàm số được sử dụng để xác định trạng thái kế tiếp và ngõ ra. Điều này có nghĩa là có
thể có nhiều FSM cùng chung chức năng nhưng khác nhau về số lượng trạng thái trong lOMoAR cPSD| 59285474
mỗi FSM. Sự thỏa hiệp về số lượng các bit trạng thái và tính phức tạp của khối luận lý tổ
hợp là một vấn đề phụ thuộc nhiều yếu tố, có thể là ràng buộc về diện tích, tốc độ, công suất tiêu thụ, …
Về góc độ kĩ thuật, chúng ta bỏ qua sự thỏa hiệp về số lượng các bit trạng thái và độ
phức tạp của hàm số được sử dụng để xác định trạng thái kế tiếp và ngõ ra. Thay vào đó,
chúng ta sẽ tập trung vào tìm kiếm một FSM có số lượng các bit trạng thái nhỏ nhất, điều
này đồng nghĩa với việc chúng ta sẽ đi tìm một FSM có diện tích nhỏ nhất khi chúng ta
thực hiện FSM xuống phần cứng.
Hai trạng thái được xem là tương đương chỉ khi hai trạng thái này chung trạng thái kế
tiếp và ngõ ra với mọi ngõ vào. Khi đã tìm được các trạng thái tương đương, chúng ta có
thể kết hợp hai trạng thái nầy thành 1 trạng thái duy nhất để giảm số lượng trạng thái
trong một FSM. Có 2 phương pháp rút gọn trạng thái là Phân hoạch trạng thái và Bảng kéo theo. Mã hóa trạng thái:
Sơ đồ trạng thái và bảng trạng thái mà chúng ta đã tìm hiểu trước đó chỉ mô tả chức năng
của một FSM mà chưa mô tả chức năng của một FSM mà chưa mô tả được cấu trúc của
một mạch tuần tự hiện thực FSM đó, một trong những câu hỏi đầu tiên là: Số lượng
flipflop là bao nhiêu? Đáp án của câu hỏi này nằm ở cách chúng ta mã hóa các trạng thái
như thế nào để có thể lưu trữ được trong các flipflop. Một vài phương pháp mã hóa trạng
thái phổ biến, bao gồm: - Mã hóa theo số nhị phân
- Mã hóa theo ưu tiên liền kề - Mã hóa theo mã hot-one - Mã hóa theo ngõ ra
Bảng chuyển đổi: Là một sự mở rộng của bảng kích thích. Trong khi bảng kích thích
biểu diễn giá trị cần thiết của các ngõ vào flipflop để có được một sự chuyển trạng thái
mong muốn của một flipflop thì bảng chuyển đổi sẽ mở rộng bằng cách biểu diễn giá trị
cần thiết của các ngõ vào của tất cả các flipflop để có được tất cả sự chuyển trạng thái
mong muốn của toàn bộ mạch
Quy trình thiết kế mạch tuần tự: lOMoAR cPSD| 59285474 THỰC HÀNH MÁY MOORE lOMoAR cPSD| 59285474
Số cuối MSSV là 4 trừ 2 thành 2 chuyển thành 3 bit là 010 Nhận biết dãy 3 bit 010 Các trạng thái: S0: dãy trống S1: dãy có 0 cuối S2: dãy có 01 cuối S3: dãy có 010 cuối
Sơ đồ trạng thái: lOMoAR cPSD| 59285474
Mã hóa trạng thái: S0 00 S1 01 S2 10 S3 11
Bảng chuyển trạng thái: Q1Q0 Q1nextQ0next D1D0 Y A = 0 A = 1 A = 0 A = 1 00 01 00 01 00 0 01 01 10 01 10 0 10 11 00 11 00 0 11 01 10 01 10 1 (A là input, Y là output) Bìa K: D1: A/Q1Q0 00 01 11 10 0 1 1 1 1 D0: lOMoAR cPSD| 59285474 A/Q1Q0 00 01 11 10 0 1 1 1 1 1 Y: Q1/Q0 0 1 0 1 1
Từ bảng chuyển trạng thái và bìa K, ta có được phương trình của D và Y: D1 = AQ0 + A’Q1Q0’ D0 = A’ Y = Q1Q0 Vẽ mạch:
Mô phỏng bằng waveform: lOMoAR cPSD| 59285474
Khi mạch khởi động, mạch chưa nhận được bất kỳ input nào nên ở trạng thái S0(00), output bằng 0.
Lần đầu clock tích cực, mạch nhận được input là 1 nên vẫn giữ nguyên trạng thái S0, output bằng 0.
Lần thứ 2 clock tích cực, mạch nhận được input là 0 nên chuyển trạng thái từ S0 sang S1(01), output bằng 0.
Lần thứ 3 clock tích cực, mạch nhận được input là 0 nên trạng thái S1 được giữ nguyên, output bằng 0.
Lần thứ 4 clock tích cực, mạch nhận được input là 1 nên chuyển trạng thái từ S1 sang S2(10), output bằng 0.
Lần thứ 5 clock tích cực, mạch nhận được input là 0 nên chuyển trạng thái từ S2 sang
S3(11), và trong khoảng thời gian từ khi clock tích cực lần thứ năm đến lần tiếp theo
clock tích cực thì output bằng 1, tức là mạch đã phát hiện được chuỗi 010.
Lần thứ 6 clock tích cực, mạch nhận được input là 1 nên chuyển trạng thái từ S3 về S2, output bằng 0.
Lần thứ 7 clock tích cực, mạch nhận được input là 1 nên chuyển trạng thái từ S2 về S0, output bằng 0.
Lần thứ 11 clock tích cực, mạch nhận được input là 0 nên chuyển trạng thái từ S3 về S1, ouput bằng 0.
Có thể thấy mạch đã có thể mô phỏng đúng tất cả 4 trạng thái, 8 trường hợp chuyển trạng
thái và 4 output ứng với mỗi trạng thái. Mạch có khả năng phát hiện được chuỗi 010. Nạp vào kit DE2:
Link video: https://drive.google.com/file/d/1P41mfbq9XvPfZ6HmBzN7Xls-bSSB7gyJ/ view?usp=share_link
Lần lượt thử 8 trường hợp chuyển trạng thái:
- S0 với input 0 mạch chuyển sang S1.
- S0 với input 1 mạch giữ nguyên S0.
- S1 với input 0 mạch giữ nguyên S1.
- S1 với input 1 mạch chuyển sang S2.
- S2 với input 0 mạch chuyển sang S3.
- S2 với input 1 mạch chuyển sang S0.
- S3 với input 0 mạch chuyển sang S1.
- S3 với input 1 mạch chuyển sang S2. lOMoAR cPSD| 59285474
Tại trạng thái S3, mạch có output là 1 còn ở các trạng thái còn lại, mạch có output là 0.
Có thể thấy khi nạp kit, mạch chạy đúng như mô phỏng. MÁY MEALY Số cuối MSSV là 4 Nhận biết dãy 4 bit 0100 Các trạng thái: S0: dãy trống S1: dãy có 0 cuối S2: dãy có 01 cuối S3: dãy có 010 cuối
Sơ đồ trạng thái:
Mã hóa trạng thái: lOMoAR cPSD| 59285474 S0 00 S1 01 S2 10 S3 11
Bảng chuyển trạng thái: Q1Q0 Q1nextQ0next D1D0 Y A = 0 A = 1 A = 0 A = 1 A = 0 A = 1 00 01 00 01 00 0 0 01 01 10 01 10 0 0 10 11 00 11 00 0 0 11 01 10 01 10 1 0 (A là input, Y là output) Bìa K: D1: A/Q1Q0 00 01 11 10 0 1 1 1 1 D0: A/Q1Q0 00 01 11 10 0 1 1 1 1 1 Y: A/Q1Q0 00 01 11 10 0 1 1 lOMoAR cPSD| 59285474
Từ bảng chuyển trạng thái, ta có được phương trình của D và Y: D1 = AQ0 + A’Q1Q0’ D0 = A’ Y = A’Q1Q0 Vẽ mạch:
Mô phỏng bằng waveform:
Khi mạch khởi động và chưa tích cực clock lần nào, mạch ở trạng thái S0(00), input lần
lượt là 0 và 1 nên output là 0.
Lần đầu clock tích cực, mạch nhận được input là 1 nên output bằng 0 và mạch vẫn giữ
nguyên trạng thái S0, sau đó input chuyển về 0 nên output vẫn bằng 0.
Lần thứ 2 clock tích cực, mạch nhận được input là 0 nên output bằng 0 và mạch chuyển
trạng thái từ S0 sang S1(01).
Lần thứ 3 clock tích cực, mạch nhận được input là 0 nên output bằng 0 và trạng thái S1
được giữ nguyên, sau đó input chuyển sang 1 nên output vẫn là 0. lOMoAR cPSD| 59285474
Lần thứ 4 clock tích cực, mạch nhận được input là 1 nên output bằng 0 và mạch chuyển
trạng thái từ S1 sang S2(10), sau đó input chuyển sang 0 nên ouput vẫn là 0.
Lần thứ 5 clock tích cực, mạch nhận được input là 0 nên chuyển trạng thái từ S2 sang
S3(11), lúc này mạch ở trạng thái S3 và có input là 0 nên lập tức output được chuyển
thành 1 cho đến lần tiếp theo clock tích cực miễn là input vẫn còn bằng 0. Trường hợp
mạch ở trạng thái S3 và vẫn chưa đến lần tiếp theo clock tích cực, nếu mạch nhận được
input là 1 thì lập tức output chuyển về 0. (Xem ở lần 8 clock tích cực)
Lần thứ 6 clock tích cực, mạch nhận được input là 0 nên output bằng 0 và mạch chuyển
trạng thái từ S3 sang S1, sau đó input chuyển sang 1 và mạch vẫn có output là 0.
Lần thứ 9 clock tích cực, mạch nhận được input là 1 nên output bằng 0 và mạch chuyển
trạng thái từ S3 sang S2, sau đó input chuyển sang 0 và mạch vẫn có output là 0, và input
chuyển lại về 1 mạch vẫn có output là 0.
Lần thứ 10 clock tích cực, mạch nhận được input là 1 nên output bằng 0 và mạch chuyển
trạng thái từ S2 sang S0, sau đó input chuyển sang 0 và mạch vẫn có output là 0.
Có thể thấy mạch đã có thể mô phỏng đúng tất cả 4 trạng thái, 8 trường hợp chuyển trạng
thái và 8 output ứng với mỗi trường hợp chuyển. Mạch có khả năng phát hiện được chuỗi 0100. Nạp vào kit DE2: Link video:
https://drive.google.com/file/d/1YFq09GKxTiOetSb5T5Rw6Y8WHgpcA0p-/view? usp=share_link
Lần lượt thử 8 trường hợp chuyển trạng thái, ứng với mỗi lần chuyển ta có output:
- S0 với input 0 mạch có output là 0 và trạng thái chuyển sang S1.
- S0 với input 1 mạch có output là 0 và trạng thái giữ nguyên S0.
- S1 với input 0 mạch có output là 0 và trạng thái giữ nguyên S1.
- S1 với input 1 mạch có output là 0 và trạng thái chuyển sang S2.
- S2 với input 0 mạch có output là 0 và trạng thái chuyển sang S3.
- S2 với input 1 mạch có output là 0 và trạng thái chuyển sang S0.
- S3 với input 0 mạch có output là 1 và trạng thái chuyển sang S1.
- S3 với input 1 mạch có output là 0 và trạng thái chuyển sang S2.
Có thể thấy khi nạp kit, mạch chạy đúng như mô phỏng.