Bài giảng Thiết kế luận lý - Chương 1: Biểu diễn số đếm, mã vàbiến đổi mã

Nội dung text: Bài giảng Thiết kế luận lý - Chương 1: Biểu diễn số đếm, mã vàbiến đổi mã

1. dce 2012 Giới thiệu môn học • Cán bộ giảng dạy • Nguyễn Quang Huy huynguyen@cse.hcmut.edu.vn • Trang web môn học • Sakai • • Đánh giá: trắc nghiệm/tự luận • Giữa kỳ: 30% • Cuối kỳ: 70% • Bonus ©2012, CE Department 2
2. dce 2012 Tổng quan ©2012, CE Department 4
3. dce 2012 Software ©2012, CE Department 6
4. dce 2012 Biểu diễn số đếm, mã BK TP.HCM và biến đổi mã ©2012, CE Department
5. dce 2012 Số (Digital) và tương tự (Analog) • Trong khoa học và kỹ thuật những quá trình định lượng trong tự nhiên (áp suất, vận tốc, điện áp, dòng điện, ) được biểu diễn qua trung gian các biến • Quan hệ giữa các biến được diễn tả bởi các định luật, công thức • Trong hệ thống, các biến được hiện thực dưới dạng các tín hiệu (signal) vật lý ở đầu vào và đầu ra • Theo thực nghiệm, các tín hiệu vật lý dường như biến đổi một cách liên tục (continously), VD. nhiệt độ trong ngày, dòng điện, v.v • Hệ tương tự là hệ mà ở đó các tín hiệu thay đổi theo cách liên tục (tín hiệu tương tự - analog signal) ©2012, CE Department 10
6. dce 2012 Hệ số và hệ tương tự • Hình vẽ bên minh họa việc xấp xỉ một đường cong liên tục bất kỳ bằng một hàm bao gồm nhiều bậc thang rời rạc (discrete) • Tín hiệu liên tục cũng có thể được rời rạc hóa (discretized) hay lượng tử hóa (digitized)  tín hiệu số (digital signal) • Có thể chuyển đổi giữa tín hiệu số và tín hiệu tương tự  Hệ số là hệ mà ở đó các tín hiệu thay đổi theo cách rời rạc (tín hiệu số)  Các biến được xử lý trong hệ số đều ở dạng rời rạc  các giải thuật xấp xỉ gần đúng ©2012, CE Department 12
7. dce 2012 Hạn chế của hệ số • Thế giới thực phần lớn là tương tự • VD: Nhiệt độ, áp suất, vận tốc, tốc độ dòng chảy, • Các bước xử lý vấn đề – Chuyển đổi từ tín hiệu nhập vào tương tự (Analog Input) sang tín hiệu số (Digital) – Xử lý trên dữ liệu số – Chuyển đổi tín hiệu số ra tín hiệu tương tự (Analog output) ©2012, CE Department 14
8. dce 2012 Hệ thống số đếm • Hệ thống số đếm (hệ đếm) quen thuộc nhất với con người là hệ thập phân (decimal number system) • Hệ thập phân sử dụng 10 ký số (digit) từ 0 đến 9 và biểu diễn giá trị số dưới dạng viết tắt của đa thức cơ số (base) 10 3 7 5 6 = 3 x 103 + 7 x 102 + 5 x 101 + 6 x 100 • Giá trị số được biểu diễn không chỉ phụ thuộc vào các ký số mà còn phụ thuộc vào vị trí xuất hiện của các ký số  hệ số đếm theo vị trí (positional number system) ©2012, CE Department 16
9. dce 2012 Example 3 2 1 0 • (7,239)10 = 7 x 10 + 2 x 10 + 3 x 10 + 9 x 10 3 2 1 0 -1 • (4103.2)5 = 4 x 5 + 1 x 5 + 0 x 5 + 3 x 5 + 2 x 5 = 4 x 125 + 1 x 25 + 0 x 5 + 3 x 1 + 2 x 5-1 = (528.4)10 4 3 2 1 0 • (11011)2 = 1 x 2 + 1 x 2 + 0 x 2 + 1 x 2 + 1 x 2 = (27)10 3 2 1 0 • (B65F)16 = 11 x 16 + 6 x 16 + 5 x 16 + 15 x 16 ©2012, CE Department 18
10. dce 2012 Hệ nhị phân 24 23 22 21 20 2 1 2 2 2 3 1 1 0 1 1 . 1 0 1 MSB LSB 0 1 2 3 4 (11011.101)2 1 * 2 1 * 2 0*2 1 * 2 1* 2 1* 2 1 0*2 2 1*2 3 ©2012, CE Department 20
11. dce 2012 Các hệ đếm khác • Các hệ đếm khác được sử dụng Các hệ đếm thông dụng trong những hệ thống số là Decimal Binary Octal Hexa – Hệ bát phân (Octal system): cơ số 8 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 – Hệ thập lục phân (Hexadecimal 2 0 0 1 0 0 2 2 system): cơ số 16 3 0 0 1 1 0 3 3 4 0 1 0 0 0 4 4 5 0 1 0 1 0 5 5 6 0 1 1 0 0 6 6 7 0 1 1 1 0 7 7 8 1 0 0 0 1 0 8 9 1 0 0 1 1 1 9 1 0 1 0 1 0 1 2 A 1 1 1 0 1 1 1 3 B 1 2 1 1 0 0 1 4 C 1 3 1 1 0 1 1 5 D 1 4 1 1 1 0 1 6 E 1 5 1 1 1 1 1 7 F ©2012, CE Department 22
12. dce 2012 Từ thập phân sang hệ cơ số b N10 = (anan-1an-2 a2a1a0) b n n-1 n-2 0 = an x b + an-1 x b + an-2 x b + + a0 x b N n 1 n 2 n 3 a *b a *b a *b a Q a0 b n n 1 n 2 1 1 Q 1 a *bn 2 a *bn 3 a *bn 4 a Q a b n n 1 n 2 2 2 1 Q 2 a *bn 3 a *bn 4 a *bn 5 a Q a b n n 1 n 2 3 3 2 ©2012, CE Department 24
13. dce 2012 Các vấn đề khác • Chuyển đổi từ hệ thập phân sang hệ bát phân. • Chuyển đổi từ hệ thập phân sang hệ thập lục phân. • Chuyển đổi từ hệ nhị phân sang hệ bát phân • Chuyển đổi từ hệ bát phân sang hệ nhị phân • Chuyển đổi từ hệ nhị phân sang hệ thập lục phân • Chuyển đổi từ hệ thập lục phân sang hệ nhị phân ©2012, CE Department 26
14. dce 2012 Mã & biến đổi mã • Thông tin con người trao đổi với nhau được diễn tả qua trung gian những tập hợp (set) các ký hiệu (symbol) • Mỗi tập hợp ký hiệu tạo thành 1 bảng mẫu tự (alphabet) • Trong tiếng Anh, ta có bảng mẫu tự các chữ cái từ A đến Z. Để tạo ra 1 từ trong tiếng Anh, chỉ cần ghép các chữ cái trong bảng mẫu tự lại với nhau • Tiếng Anh có thể được xem như 1 bộ mã (code) và mỗi từ của tiếng Anh được xem là 1 từ mã (code word) • Mã Morse – sử dụng dấu chấm (.) và dấu (-) • Hệ nhị phân có thể được sử dụng như 1 bảng mẫu tự với 2 chữ cái (nói chính xác hơn là con số - digit) 0 và 1 • Số lượng bit b dùng trong mỗi từ mã phụ thuộc vào tổng số từ mã N cần diễn đạt  N 2 b ©2012, CE Department 28
15. dce 2012 Mã BCD (Binary-Coded Decimal) Số thập phân 5 7 3 Decimal BCD 0 0 0 0 0 1 0 0 0 1 Số BCD 0101 0111 0011 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 Số thập phân 6 0 1 1 0 9 8 4 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 Số BCD 1001 1000 0100 ©2012, CE Department 30
16. dce 2012 Một số mã khác • Mã có trọng số 1 bit 2 bit 3 bit 4 bit – 8421 (BCD) • 2421 0 0 0 0 0 0 0 0 0 0 – 84-2-1 • Excess-3 1 0 1 0 0 1 0 0 0 1 • Mã vòng (cyclic) là mã mà 2 từ 1 1 0 1 1 0 0 1 1 mã kế tiếp nhau chỉ khác nhau 1 0 0 1 0 0 0 1 0 1 bit 1 1 0 0 1 1 0 1 1 1 0 1 1 1 – Mã Gray 1 0 1 0 1 0 1 • Mã chữ số (alphanumeric 1 0 0 0 1 0 0 code) 1 1 0 0 – Mã ASCII 1 1 0 1 • Mã 7-đoạn (seven-segment 1 1 1 1 code) a 1 1 1 0 1 0 1 0 f g b 1 0 1 1 e c 1 0 0 1 d 1 0 0 0 ©2012, CE Department 32
17. dce 2012 Mã phát hiện sai (Error-Detecting Codes) • Xét mã BCD – Truyền đi từ mã 0 0 0 1, giả sử xảy ra sai ở 1 bit. Thông tin nhận được sẽ là 1 trong các từ mã 1 0 0 1, 0 1 0 1, 0 0 1 1, 0 0 0 0 – Phía thu không có khả năng phát hiện sai  Mã BCD không phải là mã phát hiện sai • Bộ mã nào khi xảy ra sai ở một bit bất kỳ trong từ mã làm biến đổi từ mã từ hợp lệ thành không hợp lệ thì gọi là mã phát hiện sai • Bit chẵn lẻ (parity bit) ©2012, CE Department 34
18. dce 2012 Parity • Even-parity chữ C: 1000011 1 1000011 chữ A: 1000001 0 1000001 • Odd-parity chữ C: 1000011 0 1000011 chữ A: 1000001 1 1000001 ©2012, CE Department 36
19. dce 2012 Tổng kết (2) • Biểu diễn các đại lượng nhị phân • Mạch số (digital circuit) / Mạch luận lý (logic circuit) • Mạch số tích hợp (digital integrated circuit - IC) • Truyền song song (parallel) và nối tiếp (serial) • Bộ nhớ (memory) ©2012, CE Department 38
20. dce 2012 Đọc thêm • Phần 1.6, 1.7, 1.8 và 2.7, 2.8, 2.9, 2.10 trong sách Digital System của Ronal Tocci ©2012, CE Department 40