Giáo trình Điện tử số (Mạch logic) | Học viện Công Nghệ Bưu Chính Viễn Thông

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG ĐIỆN TỬ SỐ
(Dùng cho sinh viên hệ đào tạo đại học từ xa) L u hành n i b HÀN I-2006
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG ĐIỆN TỬ SỐ Biên soạn :
ThS. TRẦN THỊ THÚY HÀ LỜI GIỚI THIỆU Cùng v i s ti n b
c a khoa h c và công ngh , các thi t b đi n t đang và s ti p t c đ c
ng d ng ngày càng r ng rãi và mang l i hi u qu
cao trong h u h t các lĩnh v c kinh t kỹ thu t
cũng nh đ i s ng xã h i. Vi c x
lý tín hi u trong các thi t b đi n t hi n đ i đ u d
a trên c s nguyên lý s . B i v y vi c hi u sâu s c v đi n t
s là đi u không th thi u đ
c đ i v i kỹ s đi n t hi n nay. Nhu c u hi u bi t v kỹ thu t s
không ph i ch riêng đ i v i các kỹ s đi n t mà còn đ i v i
nhi u cán b kỹ thu t chuyên ngành khác có s d ng các thi t b đi n t .
Tài li u này gi i thi u m t cách h th ng các ph n t
c b n trong các m ch đi n t s k t
h p v i các m ch đi n hình, gi i thích các khái ni m c b n v c ng đi n t s , các ph ng pháp
phân tích và thi t k m ch logic c b n.
Tài li u bao g m các ki n th c c b n v m ch c ng logic, c s đ i s logic, m ch logic t
h p, các trig , m ch logic tu n t , các m ch phát xung và t o d ng xung, các b nh thông d ng.
Đặc bi t là trong tài li u này có b
xung thêm ph n logic l p trình và ngôn ng mô t ph n c ng
VHDL. Đây là ngôn ng ph
bi n hi n nay dùng đ t o mô hình cho các h th ng kỹ thu t s . T t c g m 9 ch ng. Tr c và sau m i ch
ng đ u có ph n gi i thi u và ph n tóm t t đ giúp ng i h c d n m b t ki n th
c h n. Các câu h i ôn t p đ ng i h c ki m tra m c đ n m ki n th c sau khi h c m i ch
ng. Trên c s các ki n th c căn b n, tài li u đã c
g ng ti p c n các v n đ
hi n đ i, đ ng th i liên h v i th c t kỹ thu t. Tài li u g m có 9 ch ng đ c b c c nh sau: Ch ng 1: H đ m
Ch ng 2: Đ i s Boole và các ph ng pháp bi u di n hàm
Ch ng 3: C ng logic TTL và CMOS Ch ng 4: M ch logic t h p. Ch ng 5: M ch logic tu n t .
Ch ng 6: M ch phát xung và t o d ng xung. Ch ng 7: B nh bán d n. Ch ng 8: Logic l p trình.
Ch ng 9 : Ngôn ng mô t ph n c ng VHDL.
Do th i gian có h n nên tài li u này không tránh kh i thi u sót, r t mong ng i đ c góp ý.
Các ý ki n xin g i v Khoa Kỹ thu t Đi n t 1- H c vi n Công ngh B u chính vi n thông. Xin trân tr ng c m n. 1
Ch ơng 1: Hệ đếm CHƯƠNG 1: HỆ ĐẾM GI I THIỆU Khi nói đ n s đ m, ng i ta th
ng nghĩ ngay đ n h th p phân v i 10 ch s đ c ký
hi u t 0 đ n 9. Máy tính hi n đ i không s d ng s th p phân, thay vào đó là s nh phân v i hai
ký hi u là 0 và 1. Khi bi u di n các s nh phân r t l n, ng
i ta thay nó bằng các s bát phân
(Octal) và th p l c phân (HexaDecimal). Đ m s l ng c a các đ i l
ng là m t nhu c u c a lao đ ng, s n xu t. Ng ng m t quá
trình đ m, ta đ c m t bi u di n s . Các ph
ng pháp đ m và bi u di n s đ c g i là h đ m.
H đ m không ch đ
c dùng đ bi u di n s mà còn là công c x lý.
Có r t nhi u h đ m, ch ng h n nh h La Mã, La Tinh ... H đ m v a có tính đa d ng v a có tính đ
ng nh t và ph bi n. M i h đ m có u đi m riêng c a nó nên trong kĩ thu t s s s d ng m t s h đ b khuy t cho nhau.
Trong ch ng này không ch trình bày các h th p phân, h nh phân, h bát phân, h th p
l c phân và còn nghiên c u cách chuy n đ i gi a các h đ m. Ch
ng này cũng đ c p đ n s nh
phân có d u và khái ni m v d u ph y đ ng. N I DUNG 1.1. BI U DIỄN S
Nguyên t c chung c a bi u di n là dùng m t s h u h n các ký hi u ghép v i nhau theo qui
c v v trí. Các ký hi u này th
ng đ c g i là ch s . Do đó, ng
i ta còn g i h đ m là h u th ng s . S ký hi u đ
c dùng là c s c a h ký hi u là r. Giá tr bi di n c a các ch khác m b t
nhau đ c phân bi t thông qua tr ng s c a h . Tr ng s c a m t h đ
kǶ s bằng ri, v i i là m t s nguyên d ng hoặc âm.
B ng 1.1 là li t kê tên g i, s
ký hi u và c s c a m t vài h đ m thông d ng. Tên h đ m S ký hi u C s (r) H nh phân (Binary) 0,1 2 H bát phân (Octal) 0, 1, 2, 3,4,5,6,7 8 H th p phân (Decimal) 0,1,2,3,4,5,6,7,8,9 10 H th p l c phân (Hexadecimal)
0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F 16 B ng 1.1
Ng i ta cũng có th g i h đ m theo c s
c a chúng. Ví d : H nh phân = H c s 2, H th p phân = H c s 10... 2
Ch ơng 1: Hệ đếm
i đây, ta s trình bày tóm t t m t s h đ m thông d ng. 1.1.1 H th p phân
Các ký hi u c a h nh đã nêu
b ng 1.1. Khi ghép các ký hi u v i nhau ta s đ c m t
bi u di n. Ví d : 1265,34 là bi u di n s trong h th p phân: − −
1265.34 =1×103 +2×102 + 6×101 + 5×100 + 3×10 1 + 4×10 2 n
Trong phân tích trên, 10 là tr ng s c a h ; các h s nhân chính là ký hi u c a h . Nh
0 y, giá trị biểu diễn của một số trong hệ thập phân sẽ bằng tổng các tích của ký hiệu (có trong
biểu diễn) với trọng số t ơng ứng. M t cách t ng quát: − N n 1 0 − −1 − −m
10 = dn 1 × 10 −1 + ...+ d1 × 10 + d0 × 10 + d 1×10
+ ...+ d m ×10 −m i = ∑di ×10 n −1
trong đó, N10 : bi u di n b t kì theo h 10,
d : các h s nhân (ký hi u b t kì c a h ), n : s ch s ph n nguyên, m : s ch s ph n phân s .
Ưu đi m c a h th p phân là tính truy n th ng đ i v i con ng i. Đây là h mà con ng i t. Ngoài
0 nh n bi t nh ra, nh có nhi u ký hi u nên kh năng bi u di n c a h r t l n, cách bi u th i gian vi t và di n g n, t n ít đ c.
Nh c đi m chính c a h là do có nhi u ký hi u nên vi c th hi n bằng thi t b kỹ thu t s khó khăn và ph c t p. Bi u di n s t ng quát:
V i c s b t kì r và d bằng h s a tuǶ ý ta s có công th c bi u di n s chung cho t t c các h đ m: 1 = a∑ + a N
n−1 × r n −1 + ...+ a1 × r
0 × r 0 + a −1 × r −1 −m
+ ...+ a−m × r = −m a × ri n −1 i Trong m t s tr
ng h p, ta ph i thêm ch s đ tránh nh m l n gi a bi u di n c a các h . Ví d : 3610 , 368 , 3616 . 1.1.2 H nh phân
1.1.2.1. Tổ ch c hệ nhị phân
H nh phân (Binary number system) còn g i là h c s hai, g m ch hai ký hi u 0 và 1, c
s c a h là 2, tr ng s c a h là 2n. Cách đ m trong h nh phân cũng t ng t nh h th p phân.
Kh i đ u t giá tr 0, sau đó ta c ng liên ti p thêm 1 vào k t qu đ m l n tr c. Nguyên t c c ng
nh phân là : 0 + 0 = 0, 1 + 0 = 1, 1 + 1 = 10 (102 = 210). 3
Ch ơng 1: Hệ đếm Trong h nh phân, m
i ch s ch l y 2 giá tr hoặc 0 hoặc 1 và đ c g i t t là "bit". Nh
v y, bit là s nh phân 1 ch s . S bit t o thành đ
dài bi u di n c a m t s nh phân. M t s nh
phân có đ dài 8 bit đ
c gi 1 byte. S nh phân hai byte g i là m t t (word). Bit t n cùng bên
ph i g i là bit bé nh t (LSB – Least Significant Bit) và bit t n cùng bên trái g i là bit l n nh t (MSB - Most Significant Bit).
Bi u di n nh phân d ng t ng quát : − − − − − b N 2 = b n 1b n 2 ....b1b 0 .b 1 2 ....b m Trong đó, b là h s nhân c a h . Các ch s c a h s
đ ng th i cũng bằng lũy th a c a tr ng s t ng ng. Ví d : 1 1 0. 0 0 → s nh phân phân s 1 2 2 2 2 0 2 −1 2−2 → tr ng s t ng ng.
Các giá tr 210 = 1024 đ c g i là 1Kbit, 220 = 1048576 - Mêga Bit ...
Ta có d ng t ng quát c a bi u di n nh phân nh sau: N
= b n−1 × 2 n −1 ×2−1 2
+ ... + b1 × 21 + b 0 × 2 0 + b −1
+ . . + b −m × 2−m −m = ∑b i × 2i n −1
Trong đó, b là h s nhân l y các giá tr 0 hoặc 1.
1.1.2.2. Các phép tính trong hệ nhị phân a. Phép c ng
Qui t c c ng hai s nh phân 1 bit đã nêu trên. b. Phép tr
Qui t c tr hai bit nh phân cho nhau nh sau :
0 - 0 = 0 ; 1 - 1 = 0 ; 1 - 0 = 1 ; 10 - 1 = 1 (m n 1)
Khi tr nhi u bit nh phân, n u c n thi t ta m n bit k ti p có tr ng s cao h n. L n tr k ti p l i ph i tr thêm 1. c. Phép nhân
Qui t c nhân hai bit nh phân nh sau:
0 x 0 = 0 , 0 x 1 = 0 , 1 x 0 = 0 , 1 x 1 = 1
Phép nhân hai s nh phân cũng đ
c th c hi n gi ng nh trong h th p phân.
Chú ý : Phép nhân có th thay bằng phép d ch và c ng liên ti p. d. Phép chia
Phép chia nh phân cũng t
ng t nh phép chia hai s th p phân.
u điểm chính c a h nh phân là ch có hai ký hi u nên r t d th hi n bằng các thi t b c ,
đi n. Các máy vi tính và các h th ng s đ u d a trên c s ho t đ ng nh phân (2 tr ng thái). Do 4
Ch ơng 1: Hệ đếm
đó, h nh phân đ c xem là ngôn ng
c a các m ch logic, các thi t b tính toán hi n đ i - ngôn ng máy.
Nh ợc điểm c a h
là bi u di n dài, m t nhi u th i gian vi t, đ c.
1.1.3 H bát phân và th p l c phân
1.1.3.1 Hệ bát phân
1. T ch c c a h : Nhằm kh c ph c nh c đi m c a h nh phân, ng i ta thi t l p các h
đ m có nhi u ký hi u h n, nh ng l i có quan h chuy n đ i đ c v i h nh phân. M t trong s
đó là h bát phân (hay h Octal, h c s 8).
H này g m 8 ký hi u : 0, 1, 2, 3, 4, 5, 6 và 7. C s c a h là 8. Vi c l a ch n c s 8 là
xu t phát t ch 8 = 23. Do đó, m i ch s bát phân có th thay th cho 3 bit nh phân. D ng bi u di n t ng quát c a h bát phân nh sau: N 8
= O n−1 × 8 n −1 +...+ O0 ×80 + O−1 ×8−1 + ... + O −m ×8−m −m = ∑O i ×8i n −1
L u ý rằng, h th p phân cũng đ m t ng t và có gi i r ng h n h bát phân, nh ng không th tìm đ
c quan h 10 = 2n (v i n nguyên).
2. Các phép tính trong h bát phân a. Phép cộng
Phép c ng trong h bát phân đ c th
c hi n t ng t nh s trong h th p phân. Tuy nhiên, n
khi k t qu c a vi c c ng hai hoặc nhi u ch
cùng tr ng s l h n hoặc bằng 8 ph i nh lên
ch s có tr ng s l n h n k ti p. b. Phép trừ
Phép tr cũng đ c ti n hành nh trong h thâp phân. Chú ý rằng khi m n 1 ch s có tr ng s l n h n
thì ch c n c ng thêm 8 ch không ph i c ng thêm 10.
Các phép tính trong h bát phân ít đ c s d ng. Do đó, phép nhân và phép chia dành l i nh m t bài t p cho ng i h c.
1.1.3.2 Hệ thập lục phân
1.Tổ ch c c a hệ
H th p l c phân (hay h Hexadecimal, h c s 16). H g m 16 ký hi u là 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.
Trong đó, A = 1010 , B = 1110 , C = 1210 , D = 1310 , E = 1410 , F = 1510 .
C s c a h là 16, xu t phát t y u t 16 = 24. V y, ta có th dùng m t t nh phân 4 bit
(t 0000 đ n 1111) đ bi u th các ký hi u th p l c phân. D ng bi u di n t ng quát: 5
Ch ơng 1: Hệ đếm N −m 16 − − − = Hn 1
×16n−1 +. . + H0 ×160 + H 1 ×16−1 + . . + H m ×16 −m i = ∑H i ×16 n −1
2. Các phép tính trong h c s 16 a. Phép cộng
Khi t ng hai ch s l n h n 15, ta l y t ng chia cho 16. S d đ c vi t xu ng ch s t ng và s th
ng đ c nh lên ch s k ti p. N u các ch s là A, B, C, D, E, F thì tr c h t, ta ph i
đ i chúng v giá tr th p phân t ng ng r i m i c ng. b. Phép trừ Khi tr m t s
bé h n cho m t s l n h n ta cũng m n 1 c t k
ti p bên trái, nghĩa là c ng thêm 16 r i m i tr . c. Phép nhân
Mu n th c hi n phép nhân trong h 16 ta ph i đ i các s trong m i th a s v th p phân,
nhân hai s v i nhau. Sau đó, đ i k t qu v h 16. 1.2. CHUY N Đ I C S GI ACÁCHỆĐ M 1.2.1. Chuy n đ i t h c s 10 sang các h khác
Đ th c hi n vi c đ i m
t s th p phân đ y đ sang các h
khác ta ph i chia ra hai ph n: ph n nguyên và phân s .
Đối với phần nguyên: ta chia liên ti p ph n nguyên c a s th p phân cho c s c a h c n c tr t t
chuy n đ n, s d sau m i l n chia vi t đ o ng khi k t là k t qu c n tìm. Phép chia d ng l i
qu l n chia cu i cùng bằng 0. Ví d : Đ i s 5710 sang s nh phân. B c chia đ c d 1 57/2 28 1 LSB 2 28/2 14 0 3 14/2 7 0 4 7/2 3 1 5 3/2 1 1 6 1/2 0 1 MSB Vi t đ o ng c tr t t , ta có : 5710 = 1110012
Đối với phần phân số : ta nhân liên ti p ph n phân s c a s th p phân v i c s c a h c n chuy n đ
n, ph n nguyên thu đ c sau m i l n nhân, vi t tu n t là k t qu c n tìm. Phép nhân d ng l i khi ph n phân s tri t tiêu.
Ví d : Đ i s 57,3437510 sang s nh phân. 6
Ch ơng 1: Hệ đếm Ph n nguyên ta v a th c hi n
ví d a), do đó ch c n đ i ph n phân s 0,375. B c Nhân K t qu Ph n nguyên 1 0,375 x 2 0.75 0 2 0,75 x 2 1.5 1 3 0,5 x 2 1.0 1 4 0,0 x 2 0 0 K t qu : 0,37510 = 0,01102
S d ng ph n nguyên đã có
ví d 1) ta có : 57,37510 = 111001.01102
1.2.2. Đ i m t bi u di n trong h b t kì sang h th p phân
Mu n th c hi n phép bi n đ i, ta dùng công th c : − − − N −1 10
= an 1 × r n −1 + ....+ a0 × r 0 + a 1 × r
+ ... + a m × r −m Th c hi n l y t ng v ph i s có k t qu
c n tìm. Trong bi u th c trên, ai và r là h s và c s h có bi u di n. 1.2.3. Đ i các s t h nh phân sang h c s 8 và 16
Vì 8 = 23 và 16 = 24 nên ta ch c n dùng m t s nh phân 3 bit là đ ghi 8 ký hi u c a h c s
8 và t nh phân 4 bit cho h c s 16.
Do đó, mu n đ i m t s nh d u phân sang h 0 s 8 và 16 ta chia s nh phân c n đ i, k t bit
phân s sang trái và ph i thành bằng 5888 ng
hoặc 4 bit. Sau đó thay các nhóm bit đã phân ký hi u t ng ng c a h c n nhóm 3 5889 i t i. Ví d :
a. Đổi số 110111,01112 sang số hệ cơ số 8
Tính t d u phân s , ta chia s này thành các nhóm 3 bit nh sau : 110 111 , 011100 ↓ ↓ ↓ ↓ 6 7 3 4
K t qu : 110111,01112 = 67,348. ( Ta đã thêm 2 s 0 đ ti n bi n đ i).
b. Đổi số nhị phân 111110110,011012 sang số hệ cơ số 16
Ta phân nhóm và thay th nh sau : 0001 1111 0110 0110 1000 ↓ ↓ ↓ ↓ ↓ 1 F 6 6 8
K t qu : 111110110,011012 = 1F6,6816 7
Ch ơng 1: Hệ đếm 1.3 S NHỊ PHÂN CÓ D U 1.3.1 Bi u di n s nh phân có d u
Có ba ph ng pháp th hi n s nh
phân có d u sau đây.
1. Sử dụng một bit dấu. Trong ph
ng pháp này ta dùng m t bit ph
, đ ng tr c các bit tr
s đ bi u di n d u, ‘0’ ch d u d
ng (+), ‘1’ ch d u âm (-).
2. Sử dụng phép bù 1. Gi nguyên bit d u và l y bù 1 các bit tr s
(bù 1 bằng đ o c a các bit c n đ c l y bù).
3. Sử dụng phép bù 2 Là ph ng pháp ph
bi n nh t. S d n ng th hi n bằng s nh phân không bù (bit d u bằng u
0), còn s âm đ c bi u di qua bù 2 (bit d
bằng 1). Bù 2 bằng bù 1 c ng 1.
Có th bi u di n s âm theo ph ng pháp bù 2 xen k : b t đ gi
u t bit LSB, d ch v bên trái, i.
nguyên các bit cho đ n gặp bit 1 đ u tiên và l y bù các bit còn l Bit d u gi nguyên.
1.3.2 Các phép c ng và tr s nh phân có d u Nh đã nói
trên, phép bù 1 và bù 2 th
ng đ c áp d ng đ th c hi n các phép tính nh phân v i s có d u.
1. Biểu diễn theo bit dấu a. Phép cộng
Hai s cùng d u: c ng hai ph n tr s v i nhau, còn d u là d u chung.
Hai s khác d u và s âm có tr s nh h n: c ng tr s c a s d ng v i bù 1 c a s âm.
Bit tràn đ c c ng thêm vào k t qu trung gian. D u là d u d ng.
Hai s khác d u và s âm có tr s l n h n: c ng tr s c a s d ng v i bù 1 c a s âm.
L y bù 1 c a t ng trung gian. D u là d u âm.
b. Phép trừ. N u l u ý rằng, - (-) = + thì trình t th c hi n phép tr trong tr ng h p này cũng gi ng phép c ng.
2. Cộng và trừ các số theo biểu diễn bù 1 a. Cộng Hai s d
ng: c ng nh c ng nh phân thông th ng, k c bit d u. Hai s âm: bi u di n chúng c
d ng bù 1 và c ng nh c ng nh phân, k c bit d u. Bit tràn c vi t d
ng vào k t qu . Chú ý, k t qu đ i d ng bù 1. Hai s khác d u và s d ng l n h n: cng s d ng v i bù 1 c a s âm. Bit tràn đ c c ng vào k t qu .
Hai s khác d u và s âm l n h n: c ng s d ng v
i bù 1 c a s âm. K t qu không có bit tràn và d ng bù 1. b. Trừ Đ th c hi n phép tr
, ta l y bù 1 c a s tr , sau đó th c hi n các b c nh phép c ng. 8
Ch ơng 1: Hệ đếm
0 Cộng và trừ nhị phân theo biểu diễn bù 2 a. Cộng Hai s d ng: c ng nh c ng nh phân thông th ng. K t qu là d ng.
Hai s âm: l y bù 2 c hai s h ng và c ng, k t qu d ng bù 2. Hai s khác d u và s d ng l n h n: l y s d
ng c ng v i bù 2 c a s âm. K t qu bao
g m c bit d u, bit tràn b đi.
Hai s khác d u và s âm l n h n: s d ng đ
c c ng v i bù 2 c a s âm, k t qu d ng bù 2 c a s d ng t ng ng. Bit d u là 1. b. Phép trừ
Phép tr hai s có d u là các tr ng h p riêng c a phép c ng. Ví d , khi l y +9 tr đi +6 là 0 ng ng v i +9 c ng v i -6. 1.4. D UPH YĐ NG
1.4.1 Bi u di n theo d u ph y đ ng G m hai ph n: s
mũ E (ph n đặc tính) và ph n đ nh tr M (tr
ng phân s ). E có th có đ
dài t 5 đ n 20 bit, M t
8 đ n 200 bit ph thu c vào t ng
ng d ng và đ dài t máy tính. Thông
th ng dùng 1 s bit đ bi u di n E và các bit còn l i cho M v i đi u ki n: 1/2≤M ≤ 1 E và M có th đ c bi u di n
d ng bù 2. Giá tr c a chúng đ
c hi u ch nh đ đ m b o m
i quan h trên đây đ c g i là chu n hóa.
1.4.2 Các phép tính v i bi u di n d u ph y đ ng Gi ng nh
các phép tính c a hàm mũ. Gi s có hai s
theo d u ph y đ ng đã chu n hóa: E X = 2 ( x ( Mx )
và Y = 2 Ey My ) thì:
Tích: Z = X.Y = 2 E +E ( x y M x .M y ) = 2 EZ Mz
Th ng: W = X / Y = 2 E −E ( x y M x / M y ) = 2 Ew Mw
Mu n l y t ng và hi u, c n đ a các s h ng v cùng s
mũ, sau đó s mũ c a t ng và hi u
s l y s mũ chung, còn đ nh tr c a t
ng và hi u s bằng t ng và hi u các đ nh tr . TÓMT T Trong ch
ng này chúng ta gi i 0 m th ng đ c s d ng trong h ng pháp thi u v m t s
h chuy n đ i gi a các h đ m
th ng s : h nh phân, h bát phân, h th p l c phân. Và ph đó.
Ngoài ra còn gi i thi u các phép tính s h c trong các h đó. 9
Ch ơng 1: Hệ đếm CÂUH IÔNT P
0 Đ nh nghĩa th nào là bit, byte?
1 Đ i s nh phân sau sang d ng bát phân: 0101 1111 0100 1110 0 57514 1 57515 2 57516 3 57517
3. Th c hi n phép tính hai s th p l c phân sau: 132,4416 + 215,0216. 0 347,46 1 357,46 2 347,56 3 357,67
4. Th c hi n phép c ng hai s có d u sau theo ph ng pháp bù 1: 0000 11012 + 1000 10112 0 0000 0101 1 0000 0100 2 0000 0011 3 0000 0010
5. Th c hi n phép c ng hai s có d u sau theo ph ng pháp bù 2: 0000 11012 – 1001 10002 0 1000 1110 1 1000 1011 2 1000 1100 3 1000 1110 0 Hai byte có bao nhiêu bit? 0 16 1 8 2 32 3 64 10
Ch ơng 2: Đại số Boole và các ph ơng pháp biểu diễn hàm
CHƯƠNG 2: ĐẠI SỐ BOOLE VÀ CÁC PHƯƠNG PHÁP BIỂU DIỄN HÀM GI I THIỆU CHUNG
Trong m ch s , các tín hi u th ng cho
hai m c đi n áp, ví d 0 V và 5 V. Nh ng linh ki n đi n t dùng trong m ch s làm vi c
m t trong hai tr ng thái, ví d transistor l ng c c làm vi c
ch đ khóa (t t), hoặc thông.. Do v y, đ
mô t ho t đ ng c a các m ch s , ng i ta dùng h nh phân (Binary), hai
tr ng thái c a các linh ki n trong m ch đ
c mã hóa t ng ng thành 1 và 0. M t b
môn đ i s đ c phát tri n t cu i th kỷ 19 mang tên chính ng i sáng l p ra nó,
đ i s Boole, còn đ c g i là đ i s
logic r t thích h p cho vi c mô t m ch s . Đ i s Boole là công c
toán h c quan tr ng đ thi t k và phân tích m ch s . Các kỹ s , các nhà chuyên môn
trong lĩnh v c đi n t , tin h c, thông tin, đi u khi n.. đ u c n ph i n m v ng công c này đ có th
đi sâu vào m i lĩnh vc liên quan đ n kỹ thu t s .
84 năm sau, đ i s Boole đã đ
c Shannon phát tri n thành lý thuy t chuyển mạch. Nh
các công trình c a Shannon, v
sau này, các nhà kỹ thu t đã dùng đ i s
Boole đ phân tích và
thi t k các m ch vi tính. Tr ng thái "đúng", "sai" trong bài toán logic đ c thay th bằng tr ng
thái "đóng", "ngắt" c a m t chuyển mạch (CM). M i quan h nhân qu
trong bài toán logic đ c thay b i m i quan h
gi a dòng đi n trong m ch v
i tr ng thái các CM g n trên đo n m ch y. M i quan h này s đ c th
hi n bằng m t hàm toán h c, có tên là hàm chuyển mạch. Khi đó,
các tr ng thái c a CM : "đóng" = 1 và "ng t" = 0. Hình 2-1 mô t đi u v a nói. đây, tr ng thái c a CM đ
c kí hi u bằng ch cái A.
V th c ch t, hàm chuy n m ch là m t tr ng h p c
th c a hàm logic. Do đó, đ i s Boole ng v i tr ng h p
này cũng đ c g i là đ i s chuy n m ch. Mặc dù v y, trong CM tr ng m t s tài li u ng i ta v n th
ng g i nó là đ i s logic hay thái Ng t: 0 i s Boole. A= 0
Ngày nay, đ i s Boole không ch gi i h n trong lĩnh v c kĩ
thu t chuy n m ch mà còn là công c phân tích và thi t k các m
ch s , đặc bi t là lĩnh v c máy tính. C u ki n làm chuy n m ch đ CM tr ng
c thay bằng Diode, Transistor, các m ch tích h p, băng t ... Ho thái Đóng:
t đ ng c a các c u ki n này cũng đ c đặc tr ng bằng hai tr ng A=1
thái: thông hay t t, d n đi n hay không d n đi n... Do đó, hai
giá tr h nh phân v n đ c dùng đ mô t tr ng thái c a chúng.
0 i s logic ch có 3 hàm c b n nh t, đó là hàm "Và", hàm
"Hoặc" và hàm "Đ o". Đặc đi m n i b t c a đ i s logic là c hàm
l n bi n ch l y hai giá tr hoặc 1 hoặc 0. 11
Ch ơng 2: Đại số Boole và các ph ơng pháp biểu diễn hàm
Trong ch ng này, ta s đ c p đ n các tiên đ , đ nh lý, các cách bi u bi n hàm Boole và m t s ph
ng pháp rút g n hàm. Ngoài ra, ch ng này cũng xét các lo i c ng logic và các tham s chính c a chúng. N I DUNG 2.1Đ IS BOOLE
2.1.1. Các đ nh lý c b n: STT Tên g i D ng tích D ng t ng 1 Đ ng nh t X.1=X X+0=X 2 Ph n t 0, 1 X.0=0 X+1=1 3 Bù X.X = 0 X + X =1 4 B t bi n X.X=X X+X=X 5 H p th X+X.Y=X X.(X+Y)=X 6 Ph đ nh đúp X = X 7 Đ nh lý
(X.Y.Z...) = X + Y + Z +... (X + Y + Z +...) = X.Y.Z... DeMorgan
5888 ng 2.1. M t s đ nh lý thông d ng trong đ i s chuy n m ch
2.1.2 Các đ nh lu t c b n: 5888
Hoán v : X.Y = Y.X , X + Y = Y + X 5889
K t h p: X. ( Y.Z ) = ( X.Y ).Z , X + (Y + Z ) = ( X + Y )+ Z 5890
Phân ph i: X. ( Y + Z ) = X.Y + X.Z , (X + Y ). (X + Z ) = X + Y.Z
2.2 CÁC PHƯ NG PHÁP BI U DIỄN HÀM BOOLE Nh đã nói
trên, hàm logic đ c th hi n bằng nh ng bi u th c đ i s nh các môn toán h c khác. Đây là ph
ng pháp t ng quát nh t đ bi u di n hàm logic. Ngoài ra, m t s ph ng
pháp khác cũng đ c dùng đ bi u di n lo i hàm này. M i ph
ng pháp đ u có u đi m và ng d ng riêng c a nó. D
i đây là n i dung c a m t s ph ng pháp thông d ng.
2.2.1 B ng trạng thái
Li t kê giá tr (tr ng thái) m i bi n theo t ng c t và là giá tr hàm theo m t c t riêng (th ng
bên ph i b ng). B ng tr ng thái còn đ c g i là bảng sự
thật hay bảng chân lý. 12
Ch ơng 2: Đại số Boole và các ph ơng pháp biểu diễn hàm m A B C f m0 0 0 0 0 m1 0 0 1 0 m2 0 1 0 0 m3 0 1 1 0 m4 1 0 0 0 m5 1 0 1 0 m6 1 1 0 0 m7 1 1 1 1
23 ng 2.2. B ng tr ng thái hàm 3 bi n
Đ i v i hàm n bi n s có 2n t h p đ c l p. Các t h p này đ c kí hi u bằng ch mi, v i i
= 0 đ n 2n -1 (xem b ng 2-2) và có tên g i là các hạng tích hay còn g i là mintex. Vì m i h ng tích có th
l y 2 giá tr là 0 hoặc 1, nên n u có n bi n thì s hàm mà b ng
tr ng thái có th thi t l p đ c s là: N = 22n 2.2.2 Ph
ng pháp b ng Các nô (Karnaugh)
T ch c c a b ng Các nô: Các t
h p bi n đ c vi t theo m t dòng (th ng là phía trên) và m t c t (th ng là bên trái). Nh
v y, m t hàm logic có n bi n s có 2n ô. M i ô th hi n m t
h ng tích hay m t h ng t ng, các h ng tích trong hai ô kế cận ch khác nhau m t bi n.
Tính tu n hoàn c a b ng Các nô: Không nh ng các ô kế cận khác nhau một biến mà các ô đầu
dòng và cuối dòng, đầu cột và cuối cột cũng ch khác nhau một biến (k c 4 góc vuông c a 5888
ng). B i v y các ô này cũng gọi là kế cận.
Mu n thi t l p b ng Các nô c a m t hàm đã cho d
i d ng chu n t ng các tích, ta ch vi c
ghi giá tr 1 vào các ô ng v i h ng tích có mặt trong bi u di n, các ô còn l i s l y giá tr 0 (theo
đ nh lý DeMorgan). N u hàm cho d
i d ng tích các t ng, cách làm cũng t ng t , nh ng các ô
ng v i h ng t ng có trong bi u di n l i l y giá tr 0 và các ô khác l y giá tr 1. 2.2.3 Ph ng pháp đại s
Có 2 d ng bi u di n là d ng tuyển (tổng các tích) và d ng hội (tích các tổng).
+ D ng tuy n: M i s h ng là m t hạng tích hay mintex, th
ng kí hi u bằng ch "mi".
+ D ng h i: M i th a s là hạng tổng hay maxtex, th
ng đ c kí hi u bằng ch "Mi".
N u trong t t c m i h ng tích hay h ng t ng có đ mặt các bi n, thì d ng t ng các tích hay tích các t ng t ng ng đ
c g i là d ng chuẩn. D ng chu n là duy nh t.
T ng quát, hàm logic n bi n có th bi u di n ch bằng m t d ng t ng các tích: ( − ) ∑ a f X n 1 ,..., X 0 = 2 n −1 i mi i =0 13
Ch ơng 2: Đại số Boole và các ph ơng pháp biểu diễn hàm
hoặc bằng ch m t d ng tích các t ng: ( − ) ∏ ( )
f X n 1 ,..., X 0 = 2 n −1 a i + mi i =0
đây, ai ch l y hai giá tr
0 hoặc 1. Đ i v i m t hàm thì mintex và maxtex là bù c a nhau.
2.3 CÁC PHƯ NG PHÁP RÚT GỌN HÀM
2.3.1. Ph ng pháp đại s
D a vào các đ nh lý đã h c đ đ a bi u th c v d ng t i gi n.
Ví d : Hãy đ a hàm logic v d ng t i gi n:
f = AB+ AC + BC = + =
Áp d ng đ nh lý, A + A 1, X XY X ta có:
f = AB+ AC + BC(A + A )
= AB+ABC +AC + ABC = AB+ AC V y n u trong t
ng các tích, xu t hi n m t bi n và đ o c a bi n đó trong hai s h ng khác
nhau, các th a s còn l i trong hai s
h ng đó t o thành th a s c a m t s h ng th ba thì s
h ng th ba đó là th a và có th b đi. 2.3.2 Ph ng pháp b ng Các nô Ph
ng pháp này th ng đ c dùng đ rút g n các hàm có s bi n không v t quá 5. Các b c t i thi u hóa: 1. G p các ô k
c n có giá tr ‘1’ (hoặc ‘0’) l i thành t ng nhóm 2, 4, ...., 2i ô. S ô trong m i nhóm càng l n k t qu
thu đ c càng t i gi n. M t ô có th đ c g p nhi u l n trong các
nhóm khác nhau. N u g p theo các ô có giá tr
‘0’ ta s thu đ c bi u th c bù c a hàm.
2. Thay m i nhóm bằng m t h ng tích m i, trong đó gi
l i các bi n gi ng nhau theo dòng và c t. 3. C ng các h ng tích m
i l i, ta có hàm đã t i gi n.
Ví d : Hãy dùng b ng Các nô đ gi n c hàm : ( ) ∑( ) = A BC 00 01 11 10 f A,B,C 1,2,3,4,5 0 1 1 1 0 L i gi i: 1 1 1 0 0 f1 = B f 2 = AC Hình 2-2 14
Ch ơng 2: Đại số Boole và các ph ơng pháp biểu diễn hàm + Xây d ng b ng KN t
ng ng v i hàm đã cho.
+ G p các ô có giá tr 1 k c n l i v i nhau thành hai nhóm (hình 2-2) L i gi i ph i tìm :
f = f1 + f 2 = B + AC N u g
p các ô có giá tr 0 l i theo hai nhóm, ta thu đ c bi u th c hàm bù f : f = AB+BC 2.3.3. Ph
ng pháp Quine Mc. Cluskey Ph ng pháp này có th t i thi u hóa đ
c hàm nhi u bi n và có th ti n hành công vi c nh máy tính. Các b c t i thi u hóa:
1. L p b ng li t kê các h ng tích d
i d ng nh phân theo t ng nhóm v i s bit 1 gi ng
nhau và x p chúng theo s bit 1 tăng d n.
2. G p 2 h ng tích c a m i cặp nhóm ch
khác nhau 1 bit đ t o các nhóm m i. Trong m i nhóm m i, gi l i các bi n gi
ng nhau, bi n b đi thay bằng m t d u ngang (-).
Lặp l i cho đ n khi trong các nhóm t o thành không còn kh năng g p n a. M i l n rút g n, ta đánh d u #
vào các h ng ghép cặp đ
c. Các h ng không đánh d u trong m i l n rút g n s
đ c t p h p l i đ l a ch n bi u th c t i gi n.
Ví d . Hãy tìm bi u th c t i gi n cho hàm:
f ( A, B, C, D ) = ∑(10, 11, 12, 13, 14, 15) Gi i: B c 1: L p b ng (b ng 2.3a): B ng a B ng b H ng tích Nh phân Rút g n l n đ u. Rút g n l n th 2. đã s p x p ABCD ABCD ABCD 10 1010 101- # (10,11) 11-- (12,13,14,15) 12 1100 1-10 # (10,14) 1-1- (10,11,14,15) 11 1011 110- # (12,13) 13 1101 11-0 # (12,14) 14 1110 1-11 # (11,15) 15 1111 11-1 # (13,15) 111- # (14,15) B ng 2.3
B c 2: Th c hi n nhóm các h ng tích (b ng 2.3b). 15
Ch ơng 2: Đại số Boole và các ph ơng pháp biểu diễn hàm
Ti p t c l p b ng l a ch n đ tìm hàm ti gi n (B ng 2.4): A BCD 10 11 12 13 14 15 11-- x x x x 1-1- x x x x B ng 2.4
T b ng 2-4, ta nh n th y rằng 4 c
t có duy nh t m t d u "x" ng v i hai h ng 11-- và 1-1-.
f ( A, B, C, D ) = AB + AC
Do đó, bi u th c t i gi n là :
2.4 C NG LOGIC VÀ CÁC THAM S CHÍNH
C ng logic c s là m ch đi n th c hi n ba phép tính c b n trong đ i s logic, v y ta s có ba lo i
c ng logic c s là AND, OR và NOT. 2.4.1 C ng logic c b n
2.4.1.1 Cổng AND C ng AND th c hi n hàm logic
f = f (A, B ) = A.B hoặc nhi u bi n:
f ( A, B, C, D,... ) = A.B.C.D... A A f & B f B A A B B C f & C f D D E E a) Theo tiêu chu n ANSI b) Theo tiêu chu n IEEE
Hình 2-4a,b. Ký hiệu của cổng AND.
Nguyên lý ho t đ ng c a c ng AND:
B ng tr ng thái 2.5a,b là nguyên lí ho t đ ng c a c ng AND (2 l i vào). 16
Ch ơng 2: Đại số Boole và các ph ơng pháp biểu diễn hàm A B f A B f 0 0 0 L L L 0 1 0 L H L 1 0 0 H L L 1 1 1 H H H a) Ghi theo giá tr logic b) Ghi theo m c logic
23 ng 2.5a,b. B ng tr ng thái mô t ho t đ ng c a c ng AND 2 l i vào. Theo qui c, logic 1 đ
c thay bằng m c đi n th cao, vi t t t là H (High) còn logic 0
đ c thay bằng m c đi n th th p, vi t t t là L (Low) (b ng 2-5b). C ng AND có n l i vào s có
2n h ng tích (dòng) trong b ng tr ng thái.
Khi tác đ ng t i l i vào các chu i xung s xác đ nh, đ u ra cũng s xu t hi n m t chu i
xung nh ch hình 2-4. Đ th này th
ng đ c g i là đồ thị dạng xung, đồ thị dạng sóng hay đồ
thị thời gian. 23 1 1 0 0 0 1 1 1 0 L i vào A L i ra f 0 0 1 1 1 0 0 1 0 0 L i vào B 0 0 1 0 0 0 0 1 0 0 t t t 0 t 2 t3 t4 t5 t6 t 1 t7 t8 t9 10
Hình 2-4. Đ th d ng xung vào, ra c a c ng AND
T đ th , ta nh n th y rằng, ch t i các th i đi m t2 đ n t3 và t7 đ n t8 trên c hai l i vào
23 u có logic 1 nên l i ra cũng l y logic 1. ng v i các kho ng th i gian còn l i vì hoặc c hai l i vào
bằng 0, hoặc m t trong hai l i vào bằng 0 nên l i ra l y logic 0. Ho t đ ng c a c ng AND
nhi u l i vào cũng x y ra t ng t .
Có th gi i thích d dàng m t vài ng d ng c a c ng AND qua đ th d ng xung.
Ví d : Dùng c ng AND đ t o "c a" th i gian. Trong ng d ng này, trên hai l i vào c a c ng AND
đ c đ a t i 2 chu i tín hi u s X, Y có t n s khác nhau. Gi s t n s c a X l n h n t n s c a Y. Trên đ u ra c
ng AND ch t n t i tín hi u X, gián đo n theo t ng chu kì c a Y. Nh vây, chu i s Y ch gi vai trò đóng,
ng t c ng AND và th ng đ c g i là tín hi u "c a". Ho t đ ng c a m ch đ c mô t bằng hình 2-5. 17