Giáo trình Hệ số đếm và mã

112 trang huongle 2280

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Hệ số đếm và mã", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_he_so_dem_va_ma.pdf

Nội dung text: Giáo trình Hệ số đếm và mã

ĐẠI HỌC CÔNG NGHỆ THÔNG TIN GIÁO TRÌNH HỆ SỐ ĐẾM VÀ MÃ KHOA CÔNG NGHỆ PHẦN MỀM THÀNH PHỐ HỒ CHÍ MINH - 2010
Chæång 1. Hãû thäúng säú âãúm vaì khaïi niãûm vãö maî Trang 1 Chæång 1 HÃÛ THÄÚNG SÄÚ ÂÃÚM VAÌ KHAÏI NIÃÛM VÃÖ MAÎ 1.1. HÃÛ THÄÚNG SÄÚ ÂÃÚM 1.1.1. Hãû âãúm 1.1.1.1. Khaïi niãûm Hãû âãúm laì táûp håüp caïc phæång phaïp goüi vaì biãøu diãùn caïc con säú bàòng caïc kê hiãûu coï giaï trë säú læåüng xaïc âënh goüi laì chæî säú. 1.1.1.2. Phán loaûi Chia laìm hai loaûi: a. Hãû âãúm theo vë trê: Laì hãû âãúm maì trong âoï giaï trë säú læåüng cuía chæî säú coìn phuû thuäüc vaìo vë trê cuía noï âæïïng trong con säú. Vê duû: 1991 (Hãû tháûp phán) 1111 (Hãû nhë phán) b. Hãû âãúm khäng theo vë trê: Laì hãû âãúm maì trong âoï giaï trë säú læåüng cuía chæî säú khäng phuû thuäüc vaìo vë trê cuía noï tæång æïng (âæïng) trong con säú. Vê duû: Hãû âãúm La maî I, II, III . . . . . 1.1.2. Cå säú cuía hãû âãúm Mäüt säú A báút kyì coï thãø biãøu diãùn bàòng daîy sau: A= am-1am-2. . . . .a0a-1 . . . . . . . . .a-n Trong âoï: ai (i = − n ÷ m −1 ) laì caïc chæî säú; i: caïc haìng säú, i nhoí: haìng treí, i låïn: haìng giaì. Giaï trë säú læåüng cuía caïc chæî säú ai seî nháûn mäüt giaï trë naìo âoï cuía con säú N sao cho thoía maîn báút âàóng thæïc sau: 0 ≤ ai ≤ N −1 Vaì ai nguyãn, thç N âæåüc goüi laì cå säú cuía hãû âãúm.
Baìi giaíng Kyî Thuáût Säú Trang 2 Vê duû: N =10 ⇒ a i = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. N =8 ⇒ a i = 0, 1, 2, 3, 4, 5, 6, 7. N =16 ⇒ a i = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C,D, E, F. N =2 ⇒ a i = 0, 1. Khi âaî xuáút hiãûn cå säú N, ta coï thãø biãøu diãùn säú A dæåïi daûng mäüt âa thæïc theo cå säú N, kyï hiãûu laì A(N) : m-1 m-2 0 -1 -n A(N) = am-1 .N + am-2 .N +. . + a0 .N + a-1 .N + . . + a-n .N Hay: m −1 i A(N) = ∑ a i N i =−n Våïi N=10: m-1 m-1 0 -n A(10) = am-1 .10 + am-1 .10 +. . . . .+ a0 .10 +. . .+ a-n .10 Vê duû: 1999,999 =1.103 +9.102 +9.101 +9.10-1 +9.10-2 +9.10-3 Våïi N=2: m-1 -n A(2) =am-1.2 + . . .+a-n2 Vê duû: 1111.110 = 1.23 +1.22 + 1.21 + 1.20 + 1.2-1 + 1.2-2 + 0.2-3 Våïi N=16: m-1 m-2 0 -1 -n A(16) = am-1.16 + am-216 +. . .+ a0.16 + +a-116 +. . .+ a-n16 Vê duû: 3FFH = 3.162 + 15.161 + 15.160 1.1.3. Âäøi cå säú 1.1.3.1. Âäøi tæì cå säú d sang cå säú 10 Vãö phæång phaïp, ngæåìi ta khai triãøn con säú trong cå säú d dæåïi daûng âa thæïc theo cå säú cuía noï. Vê duû: A(2) = 1101, âäøi sang tháûp phán laì: 3 2 1 0 1101(2) = 1.2 + 1.2 + 0.2 + 1.2 =13(10) 1.1.3.2. Âäøi cå säú 10 sang cå säú d Vãö nguyãn tàõc, ngæåìi ta láúy con säú trong cå säú chia liãn tiãúp cho cå säú d âãún khi thæång säú bàòng khäng thç thäi.
Chæång 1. Hãû thäúng säú âãúm vaì khaïi niãûm vãö maî Trang 3 Vê duû: 13 2 1 6 2 1023 16 0 3 2 15 63 16 1 1 2 15 3 16 1 0 3 0 A(10)=13 → A(2)=1101 A(10)=1023 → A(16)=3FFH Kãút luáûn: Goüi d1, d2, . . . . ,dn láön læåüt laì dæ säú cuía pheïp chia säú tháûp phán cho cå säú d láön thæï 1, 2, 3, 4, . . . . ., n thç kãút quaí seî laì dndn-1dn-2 d1, nghéa laì dæ säú sau cuìng laì bêt coï troüng säú cao nháút (MSB), coìn dæ säú âáöu tiãn laì bêt coï troüng säú nhoí nháút (LSB). 1.2. HÃÛ ÂÃÚM NHË PHÁN VAÌ KHAÏI NIÃÛM VÃÖ MAÎ 1.2.1. Hãû âãúm nhë phán 1.2.1.1. Khaïi niãûm Hãû âãúm nhë phán coìn goüi laì hãû âãúm cå säú 2 laì hãû âãúm maì trong âoï ngæåìi ta chè sæí duûng hai kê hiãûu 0 vaì 1 âãø biãøu diãùn táút caí caïc säú. Hai kyï hiãûu âoï goüi chung laì bit hoàûc digit vaì noï âàûc træng cho maûch âiãûn tæí coï hai traûng thaïi äøn âënh hay coìn goüi laì 2 traûng thaïi bãön FLIP- FLOP (kyï hiãûu laì FF). Mäüt nhoïm 4 bêt goüi laì nibble. Mäüt nhoïm 8 bêt goüi laì byte. Nhoïm nhiãöu bytes goüi laì tæì (word). Xeït säú nhë phán 4 bêt: a3 a2a1a0. Biãøu diãùn dæåïi daûng âa thæïc theo cå säú cuía noï laì: 3 2 1 0 a3 a2a1a0 = a3.2 + a2 . 2 + a1.2 + a0.2 Trong âoï: - 20, 21, 22, 23 (hay 1, 2, 4, 8) âæåüc goüi laì caïc troüng säú. - a0 âæåüc goüi laì bit coï troüng säú nhoí nháút, hay coìn goüi bit coï yï nghéa nhoí nháút (LSB: Least Significant Bit) .
Baìi giaíng Kyî Thuáût Säú Trang 4 - a3 âæåüc goüi laì bit coï troüng säú låïn nháút, hay coìn goüi laì bêt coï yï nghéa låïn nháút (MSB: Most Significant Bit). Nhæ váûy, våïi säú nhë phán 4 bit a3 a2a1a0 maì trong âoï mäùi chæî säú ai chè nháûn âæåüc hai giaï trë {0,1}, luïc âoï ta coï 24 = 16 täø håüp nhë phán. Säú tháûp phán a3 a2a1a0 Säú tháûp luûc phán 0 0000 0 1 0001 1 2 0010 2 3 0011 3 4 0100 4 5 0101 5 6 0110 6 7 0111 7 8 1000 8 9 1001 9 10 1010 A 11 1011 B 12 1100 C 13 1101 D 14 1110 E 15 1111 F Chuï yï: Khi biãøu diãùn säú nhë phán nhiãöu bit trãn maïy tênh thç thæåìng âãø traïnh sai soït, ngæåìi ta thæåìng biãøu diãùn thäng qua säú tháûp phán hoàûc tháûp luûc phán, baït phán. Vê duû: 1 3 7 3 7 6 1 01 1 1 1101111111 0 B E F E Coï thãø biãøu diãùn : 137376( 8 ) hoàûc 0BEFE(H).
Chæång 1. Hãû thäúng säú âãúm vaì khaïi niãûm vãö maî Trang 5 1.2.1.2. Caïc pheïp tênh trãn säú nhë phán a. Pheïp cäüng Âãø cäüng hai säú nhë phán, ngæåìi ta dæûa trãn qui tàõc cäüng nhæ sau: 0 + 0 = 0 nhåï 0 0 + 1 = 1 nhåï 0 1 + 0 = 1 nhåï 0 1 + 1 = 0 nhåï 1 Vê duû: 3 → 0011 + + 2 → 0010 5 → 0101 b. Pheïp træì 0 - 0 = 0 mæåün 0 0 - 1 = 1 mæån 1 1 - 0 = 1 mæåün 0 1 - 1 = 0 mæåün 0 Vê duû: 7 → 0111 - - 5 → 0101 2 1 0 2 → 0010 = 1.2 + 0.2 + 1.2 = 2 c. Pheïp nhán 0 . 0 = 0 0 . 1 = 0 1 . 0 = 0 1 . 1 = 1 Vê duû: 7 → 0111 x x 5 → 0101 35 0111 0000 0111 0000 0100011 = 1.25 + 1.21 + 1.20 = 35
Baìi giaíng Kyî Thuáût Säú Trang 6 d. Pheïp chia 0 : 0 = 0 1 : 1 = 1 Vê duû: 10 5 → 1010 101 2 101 10 = 2 00 0 ÆÏng duûng thanh ghi dëch thæûc hiãûn pheïp toaïn nhán hai, chia hai: Dëch tra ïi (nhán hai) 0 0 0 0 0 0 1 1 1 Thanh ghi ban âáöu 0 0 0 0 0 1 1 1 0 Dëch phaíi (chia hai) 0 0 0 0 0 0 1 1 dæ 1 Thanh ghi sau khi nhán 2 Thanh ghi sau khi chia 2 1.2.2. Khaïi niãûm vãö maî 1.2.2.1. Âaûi cæång Trong âåìi säúng haìng ngaìy, con ngæåìi giao tiãúp våïi nhau thäng qua mäüt hãû thäúng ngän ngæî qui æåïc, nhæng trong maïy tênh chè xæí lyï caïc dæî liãûu nhë phán. Do âoï, mäüt váún âãö âàût ra laì laìm thãú naìo taûo ra mäüt giao diãûn dãù daìng giæîa ngæåìi vaì maïy tênh, nghéa laì maïy tênh thæûc hiãûn âæåüc nhæîng baìi toaïn do con ngæåìi âàût ra. Âãø thæûc hiãûn âiãöu âoï, ngæåìi ta âàût ra váún âãö vãö maî hoïa dæî liãûu. Nhæ váûy, maî hoïa laì quaï trçnh biãún âäøi nhæîng kyï hiãûu quen thuäüc cuía con ngæåìi sang nhæîng kyï hiãûu quen thuäüc våïi maïy tênh. Caïc lénh væûc maî hoïa gäöm : - Säú tháûp phán - Kyï tæû - Tápû lãûnh - Tiãúng noïi - Hçnh aính - v v
Chæång 1. Hãû thäúng säú âãúm vaì khaïi niãûm vãö maî Trang 7 1.2.2.2. Maî hoïa säú tháûp phán a. Khaïi niãûm Trong thæûc tãú âãø maî hoïa säú tháûp phán, ngæåìi ta sæí duûng caïc säú nhë phán 4 bit. Vê duû: 0 0000 ; 5 0101 1 0001 ; 6 0110 2 0010 ; 7 0101 3 0011 ; 8 1000 4 0100 ; 9 1001 Viãûc sæí duûng caïc säú nhë phán âãø maî hoïa caïc säú tháûp phán goüi laì caïc säú BCD (Binary Code Decimal: Säú tháûp phán âæåüc maî hoïa bàòìng säú nhë phán). b. Phán loaûi Khi sæí duûng säú nhë phán 4 bit âãø maî hoïa caïc säú tháûp phán tæång æïng våïi 24 = 16 täø håüp maî nhë phán phán biãût. Do viãûc choün 10 täø håüp trong 16 täø håüp âãø maî hoïa caïc kyï hiãûu tháûp phán tæì 0 âãún 9 maì trong thæûc tãú xuáút hiãûn nhiãöu loaûi maî BCD khaïc nhau. Màûc duì täön taûi nhiãöu loaûi maî BCD khaïc nhau, nhæng trong thæûc tãú ngæåìi ta chia laìm hai loaûi chênh: BCD coï troüng säú vaì BCD khäng coï troüng säú. b1. Maî BCD coï troüng säú: gäöm coï maî BCD tæû nhiãn, maî BCD säú hoüc. Maî BCD tæû nhiãn âoï laì loaûi maî maì trong âoï caïc troüng säú thæåìng âæåüc sàõp xãúp theo thæï tæû tàng dáön. Vê duû: Maî BCD 8421 , maî BCD 5421 Maî BCD säú hoüc laì loaûi maî maì trong âoï coï täøng caïc troüng säú luän luän bàòng 9. Vê duû: Loaûi maî: BCD 2421, BCD 5121, BCD 8 4-2-1 Suy ra maî BCD säú hoüc coï âàûc træng: Âãø tçm tæì maî tháûp phán cuía mäüt säú tháûp phán naìo âoï ta láúy buì (âaío) tæì maî nhë phán cuía säú buì 9 tæång æïng.
Baìi giaíng Kyî Thuáût Säú Trang 8 Vê duû: 3 → 0011 Maì säú 6 laì buì 9 cuía 3: 6 → 1100 Láúy nghëch âaío ta coï: 0011 = 3 Váûy, âàûc træng cuía maî BCD säú hoüc laì coï tênh cháút âäúi xæïng qua mäüt âæåìng trung gian. b2. Maî BCD khäng coï troüng säú: laì loaûi maî khäng cho pheïp phán têch thaình âa thæïc theo cå säú cuía noï. Vê duû: Maî Gray, Maî Gray thæìa 3. Âàûc træng cuía maî Gray laì loaûi bäü maî maì trong âoï hai tæì maî nhë phán âæïng kãú tiãúp nhau bao giåì cuîng chè khaïc nhau 1 bit. Vê duû: Maî Gray: 2 → 0011 Coìn âäúi våïi maî BCD 8421: 3 → 0010 3 → 0011 4 → 0110 4 → 0100 Caïc baíng dæåïi âáy trçnh baìy mäüt säú loaûi maî thäng duûng: Baíng 1: Caïc maî BCD tæû nhiãn. BCD 8421 BCD 5421 BCD quaï 3 Säú tháûp a3 a2 a1 a0 b3 b2 b1 b0 c3 c2 c1 c0 phán 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 1 2 0 0 1 1 0 0 1 1 0 1 1 0 3 0 1 0 0 0 1 0 0 0 1 1 1 4 0 1 0 1 1 0 0 0 1 0 0 0 5 0 1 1 0 1 0 0 1 1 0 0 1 6 0 1 1 1 1 0 1 0 1 0 1 0 7 1 0 0 0 1 0 1 1 1 0 1 1 8 1 0 0 1 1 1 0 0 1 1 0 0 9
Chæång 1. Hãû thäúng säú âãúm vaì khaïi niãûm vãö maî Trang 9 Baíng 2: Caïc maî BCD säú hoüc BCD 2421 BCD 5121 BCD 84-2-1 Säú tháûp a3 a2 a1 a0 b3 B2 b1 b0 c3 c2 c1 c0 phán 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 1 0 2 0 0 1 1 0 0 1 1 0 1 0 1 3 0 1 0 0 0 1 0 0 0 1 0 0 4 1 0 1 1 1 0 0 0 1 0 1 1 5 1 1 0 0 1 1 0 0 1 0 1 0 6 1 1 0 1 1 1 0 1 1 0 0 1 7 1 1 1 0 1 1 1 0 1 0 0 0 8 1 1 1 1 1 1 1 1 1 1 1 1 9 Baíng 3: BCD tæû nhiãn vaì maî Gray. BCD 8421 BCD quaï 3 Maî Gray Gray quaï 3 Säú tháûp a3 a2 a1 a0 c3 c2 c1 c0 G3 G2 G1 G0 g3 g2 g1 g0 phán 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 2 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 3 0 1 0 0 0 1 1 1 0 1 1 0 0 1 0 0 4 0 1 0 1 1 0 0 0 0 1 1 1 1 1 0 0 5 0 1 1 0 1 0 0 1 0 1 0 1 1 1 0 1 6 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 1 7 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 0 8 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 0 9 Chuï yï: Maî Gray âæåüc suy ra tæì maî BCD 8421 bàòng caïch: caïc bit 0,1 âæïng sau bit 0 (åí maî BCD 8421) khi chuyãøn sang maî Gray thç âæåüc giæî nguyãn, coìn caïc bit 0,1 âæïng sau bit 1 (åí maî BCD 8421) khi chuyãøn sang maî Gray thç âæåüc âäøi ngæåüc laûi, nghéa laì tæì bit 1 thaình bit 0 vaì bit 0 thaình bit 1.
Baìi giaíng Kyî Thuáût Säú Trang 10 1.2.2.3. Maûch nháûn daûng säú BCD 8421 : a 3 Maûch nháûn y a2 daûng säú BCD a1 + y = 1 → a3 a2 a1 a0 khäng phaíi säú BCD 8421 + y = 0 → a3 a2 a1 a0 laì säú BCD 8421 Suy ra âãø nháûn daûng mäüt säú nhë phán 4 bit khäng phaíi laì mäüt säú BCD 8421 thç ngoî ra y = 1, nghéa laì: bit a3 luän luän bàòng 1 vaì bit a1 hoàûc a2 bàòng 1. Phæång trçnh logic : y = a3 (a1 + a2 ) = a3a1 + a3 a2 Så âäö logic: a1 a2 y a3 Do viãûc xuáút hiãûn säú BCD nãn coï hai caïch nháûp dæî liãûu vaìo maïy tênh: nháûp säú nhë phán, nháûp bàòng maî BCD. Âãø nháûp säú BCD tháûp phán hai chæî säú thç maïy tênh chia säú tháûp phán thaình caïc âãöcaïc vaì mäùi âãöcaïc âæåüc biãøu diãùn bàòng säú BCD tæång æïng. Vê duû: 11 (tháûp phán) coï thãø âæåüc nháûp vaìo maïy tênh theo 2 caïch: - Säú nhë phán: 1011 - Maî BCD : 0001 0001 1.2.2.4. Caïc pheïp tênh trãn säú BCD a. Pheïp cäüng Säú tháûp phán laì 128 thç: - Säú nhë phán laì: 10000000 - Säú BCD laì: 0001 0010 1000 Do säú BCD chè coï tæì 0 âãún 9 nãn âäúi våïi nhæîng säú tháûp phán låïn hån, noï chia säú tháûp phán thaình nhiãöu âãöcaïc, mäùi âãöcaïc âæåüc biãøu diãùn bàòng säú BCD tæång æïng.
Chæång 1. Hãû thäúng säú âãúm vaì khaïi niãûm vãö maî Trang 11 5 → 0101 7 → 0111 + + + + 3 → 0011 5 → 0101 8 1000 12 1100 + Sä ú hiã ûu chènh 0110 0001 0010 1 2 b. Pheïp træì A - B = A + B 7 → 0111 0111 - - + 5 → 0101 1010 Buì 1 cuía 5 2 0010 10001 + 1 Buì 2 cuía 5 0010 Buì 1 laì bit 0 thaình 1, bit 1 thaình 0. Buì 2 laì buì 1 cäüng thãm 1. Xeït caïc træåìng håüp måí räüng: - Thæûc hiãûn træì 2 säú BCD 1 âãöcaïc maì säú bë træì nhoí hån säú træì. - Måí räüng cho cäüng vaì træì 2 säú BCD nhiãöu âãöcaïc.
Chæång 1. Hãû thäúng säú âãúm vaì khaïi niãûm vãö maî Trang 1 Chæång 1 HÃÛ THÄÚNG SÄÚ ÂÃÚM VAÌ KHAÏI NIÃÛM VÃÖ MAÎ 1.1. HÃÛ THÄÚNG SÄÚ ÂÃÚM 1.1.1. Hãû âãúm 1.1.1.1. Khaïi niãûm Hãû âãúm laì táûp håüp caïc phæång phaïp goüi vaì biãøu diãùn caïc con säú bàòng caïc kê hiãûu coï giaï trë säú læåüng xaïc âënh goüi laì chæî säú. 1.1.1.2. Phán loaûi Chia laìm hai loaûi: a. Hãû âãúm theo vë trê: Laì hãû âãúm maì trong âoï giaï trë säú læåüng cuía chæî säú coìn phuû thuäüc vaìo vë trê cuía noï âæïïng trong con säú. Vê duû: 1991 (Hãû tháûp phán) 1111 (Hãû nhë phán) b. Hãû âãúm khäng theo vë trê: Laì hãû âãúm maì trong âoï giaï trë säú læåüng cuía chæî säú khäng phuû thuäüc vaìo vë trê cuía noï tæång æïng (âæïng) trong con säú. Vê duû: Hãû âãúm La maî I, II, III . . . . . 1.1.2. Cå säú cuía hãû âãúm Mäüt säú A báút kyì coï thãø biãøu diãùn bàòng daîy sau: A= am-1am-2. . . . .a0a-1 . . . . . . . . .a-n Trong âoï: ai (i = − n ÷ m −1 ) laì caïc chæî säú; i: caïc haìng säú, i nhoí: haìng treí, i låïn: haìng giaì. Giaï trë säú læåüng cuía caïc chæî säú ai seî nháûn mäüt giaï trë naìo âoï cuía con säú N sao cho thoía maîn báút âàóng thæïc sau: 0 ≤ ai ≤ N −1 Vaì ai nguyãn, thç N âæåüc goüi laì cå säú cuía hãû âãúm.
Baìi giaíng Kyî Thuáût Säú Trang 2 Vê duû: N =10 ⇒ a i = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. N =8 ⇒ a i = 0, 1, 2, 3, 4, 5, 6, 7. N =16 ⇒ a i = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C,D, E, F. N =2 ⇒ a i = 0, 1. Khi âaî xuáút hiãûn cå säú N, ta coï thãø biãøu diãùn säú A dæåïi daûng mäüt âa thæïc theo cå säú N, kyï hiãûu laì A(N) : m-1 m-2 0 -1 -n A(N) = am-1 .N + am-2 .N +. . + a0 .N + a-1 .N + . . + a-n .N Hay: m −1 i A(N) = ∑ a i N i =−n Våïi N=10: m-1 m-1 0 -n A(10) = am-1 .10 + am-1 .10 +. . . . .+ a0 .10 +. . .+ a-n .10 Vê duû: 1999,999 =1.103 +9.102 +9.101 +9.10-1 +9.10-2 +9.10-3 Våïi N=2: m-1 -n A(2) =am-1.2 + . . .+a-n2 Vê duû: 1111.110 = 1.23 +1.22 + 1.21 + 1.20 + 1.2-1 + 1.2-2 + 0.2-3 Våïi N=16: m-1 m-2 0 -1 -n A(16) = am-1.16 + am-216 +. . .+ a0.16 + +a-116 +. . .+ a-n16 Vê duû: 3FFH = 3.162 + 15.161 + 15.160 1.1.3. Âäøi cå säú 1.1.3.1. Âäøi tæì cå säú d sang cå säú 10 Vãö phæång phaïp, ngæåìi ta khai triãøn con säú trong cå säú d dæåïi daûng âa thæïc theo cå säú cuía noï. Vê duû: A(2) = 1101, âäøi sang tháûp phán laì: 3 2 1 0 1101(2) = 1.2 + 1.2 + 0.2 + 1.2 =13(10) 1.1.3.2. Âäøi cå säú 10 sang cå säú d Vãö nguyãn tàõc, ngæåìi ta láúy con säú trong cå säú chia liãn tiãúp cho cå säú d âãún khi thæång säú bàòng khäng thç thäi.
Chæång 1. Hãû thäúng säú âãúm vaì khaïi niãûm vãö maî Trang 3 Vê duû: 13 2 1 6 2 1023 16 0 3 2 15 63 16 1 1 2 15 3 16 1 0 3 0 A(10)=13 → A(2)=1101 A(10)=1023 → A(16)=3FFH Kãút luáûn: Goüi d1, d2, . . . . ,dn láön læåüt laì dæ säú cuía pheïp chia säú tháûp phán cho cå säú d láön thæï 1, 2, 3, 4, . . . . ., n thç kãút quaí seî laì dndn-1dn-2 d1, nghéa laì dæ säú sau cuìng laì bêt coï troüng säú cao nháút (MSB), coìn dæ säú âáöu tiãn laì bêt coï troüng säú nhoí nháút (LSB). 1.2. HÃÛ ÂÃÚM NHË PHÁN VAÌ KHAÏI NIÃÛM VÃÖ MAÎ 1.2.1. Hãû âãúm nhë phán 1.2.1.1. Khaïi niãûm Hãû âãúm nhë phán coìn goüi laì hãû âãúm cå säú 2 laì hãû âãúm maì trong âoï ngæåìi ta chè sæí duûng hai kê hiãûu 0 vaì 1 âãø biãøu diãùn táút caí caïc säú. Hai kyï hiãûu âoï goüi chung laì bit hoàûc digit vaì noï âàûc træng cho maûch âiãûn tæí coï hai traûng thaïi äøn âënh hay coìn goüi laì 2 traûng thaïi bãön FLIP- FLOP (kyï hiãûu laì FF). Mäüt nhoïm 4 bêt goüi laì nibble. Mäüt nhoïm 8 bêt goüi laì byte. Nhoïm nhiãöu bytes goüi laì tæì (word). Xeït säú nhë phán 4 bêt: a3 a2a1a0. Biãøu diãùn dæåïi daûng âa thæïc theo cå säú cuía noï laì: 3 2 1 0 a3 a2a1a0 = a3.2 + a2 . 2 + a1.2 + a0.2 Trong âoï: - 20, 21, 22, 23 (hay 1, 2, 4, 8) âæåüc goüi laì caïc troüng säú. - a0 âæåüc goüi laì bit coï troüng säú nhoí nháút, hay coìn goüi bit coï yï nghéa nhoí nháút (LSB: Least Significant Bit) .
Baìi giaíng Kyî Thuáût Säú Trang 4 - a3 âæåüc goüi laì bit coï troüng säú låïn nháút, hay coìn goüi laì bêt coï yï nghéa låïn nháút (MSB: Most Significant Bit). Nhæ váûy, våïi säú nhë phán 4 bit a3 a2a1a0 maì trong âoï mäùi chæî säú ai chè nháûn âæåüc hai giaï trë {0,1}, luïc âoï ta coï 24 = 16 täø håüp nhë phán. Säú tháûp phán a3 a2a1a0 Säú tháûp luûc phán 0 0000 0 1 0001 1 2 0010 2 3 0011 3 4 0100 4 5 0101 5 6 0110 6 7 0111 7 8 1000 8 9 1001 9 10 1010 A 11 1011 B 12 1100 C 13 1101 D 14 1110 E 15 1111 F Chuï yï: Khi biãøu diãùn säú nhë phán nhiãöu bit trãn maïy tênh thç thæåìng âãø traïnh sai soït, ngæåìi ta thæåìng biãøu diãùn thäng qua säú tháûp phán hoàûc tháûp luûc phán, baït phán. Vê duû: 1 3 7 3 7 6 1 01 1 1 1101111111 0 B E F E Coï thãø biãøu diãùn : 137376( 8 ) hoàûc 0BEFE(H).
Chæång 1. Hãû thäúng säú âãúm vaì khaïi niãûm vãö maî Trang 5 1.2.1.2. Caïc pheïp tênh trãn säú nhë phán a. Pheïp cäüng Âãø cäüng hai säú nhë phán, ngæåìi ta dæûa trãn qui tàõc cäüng nhæ sau: 0 + 0 = 0 nhåï 0 0 + 1 = 1 nhåï 0 1 + 0 = 1 nhåï 0 1 + 1 = 0 nhåï 1 Vê duû: 3 → 0011 + + 2 → 0010 5 → 0101 b. Pheïp træì 0 - 0 = 0 mæåün 0 0 - 1 = 1 mæån 1 1 - 0 = 1 mæåün 0 1 - 1 = 0 mæåün 0 Vê duû: 7 → 0111 - - 5 → 0101 2 1 0 2 → 0010 = 1.2 + 0.2 + 1.2 = 2 c. Pheïp nhán 0 . 0 = 0 0 . 1 = 0 1 . 0 = 0 1 . 1 = 1 Vê duû: 7 → 0111 x x 5 → 0101 35 0111 0000 0111 0000 0100011 = 1.25 + 1.21 + 1.20 = 35
Baìi giaíng Kyî Thuáût Säú Trang 6 d. Pheïp chia 0 : 0 = 0 1 : 1 = 1 Vê duû: 10 5 → 1010 101 2 101 10 = 2 00 0 ÆÏng duûng thanh ghi dëch thæûc hiãûn pheïp toaïn nhán hai, chia hai: Dëch tra ïi (nhán hai) 0 0 0 0 0 0 1 1 1 Thanh ghi ban âáöu 0 0 0 0 0 1 1 1 0 Dëch phaíi (chia hai) 0 0 0 0 0 0 1 1 dæ 1 Thanh ghi sau khi nhán 2 Thanh ghi sau khi chia 2 1.2.2. Khaïi niãûm vãö maî 1.2.2.1. Âaûi cæång Trong âåìi säúng haìng ngaìy, con ngæåìi giao tiãúp våïi nhau thäng qua mäüt hãû thäúng ngän ngæî qui æåïc, nhæng trong maïy tênh chè xæí lyï caïc dæî liãûu nhë phán. Do âoï, mäüt váún âãö âàût ra laì laìm thãú naìo taûo ra mäüt giao diãûn dãù daìng giæîa ngæåìi vaì maïy tênh, nghéa laì maïy tênh thæûc hiãûn âæåüc nhæîng baìi toaïn do con ngæåìi âàût ra. Âãø thæûc hiãûn âiãöu âoï, ngæåìi ta âàût ra váún âãö vãö maî hoïa dæî liãûu. Nhæ váûy, maî hoïa laì quaï trçnh biãún âäøi nhæîng kyï hiãûu quen thuäüc cuía con ngæåìi sang nhæîng kyï hiãûu quen thuäüc våïi maïy tênh. Caïc lénh væûc maî hoïa gäöm : - Säú tháûp phán - Kyï tæû - Tápû lãûnh - Tiãúng noïi - Hçnh aính - v v
Chæång 1. Hãû thäúng säú âãúm vaì khaïi niãûm vãö maî Trang 7 1.2.2.2. Maî hoïa säú tháûp phán a. Khaïi niãûm Trong thæûc tãú âãø maî hoïa säú tháûp phán, ngæåìi ta sæí duûng caïc säú nhë phán 4 bit. Vê duû: 0 0000 ; 5 0101 1 0001 ; 6 0110 2 0010 ; 7 0101 3 0011 ; 8 1000 4 0100 ; 9 1001 Viãûc sæí duûng caïc säú nhë phán âãø maî hoïa caïc säú tháûp phán goüi laì caïc säú BCD (Binary Code Decimal: Säú tháûp phán âæåüc maî hoïa bàòìng säú nhë phán). b. Phán loaûi Khi sæí duûng säú nhë phán 4 bit âãø maî hoïa caïc säú tháûp phán tæång æïng våïi 24 = 16 täø håüp maî nhë phán phán biãût. Do viãûc choün 10 täø håüp trong 16 täø håüp âãø maî hoïa caïc kyï hiãûu tháûp phán tæì 0 âãún 9 maì trong thæûc tãú xuáút hiãûn nhiãöu loaûi maî BCD khaïc nhau. Màûc duì täön taûi nhiãöu loaûi maî BCD khaïc nhau, nhæng trong thæûc tãú ngæåìi ta chia laìm hai loaûi chênh: BCD coï troüng säú vaì BCD khäng coï troüng säú. b1. Maî BCD coï troüng säú: gäöm coï maî BCD tæû nhiãn, maî BCD säú hoüc. Maî BCD tæû nhiãn âoï laì loaûi maî maì trong âoï caïc troüng säú thæåìng âæåüc sàõp xãúp theo thæï tæû tàng dáön. Vê duû: Maî BCD 8421 , maî BCD 5421 Maî BCD säú hoüc laì loaûi maî maì trong âoï coï täøng caïc troüng säú luän luän bàòng 9. Vê duû: Loaûi maî: BCD 2421, BCD 5121, BCD 8 4-2-1 Suy ra maî BCD säú hoüc coï âàûc træng: Âãø tçm tæì maî tháûp phán cuía mäüt säú tháûp phán naìo âoï ta láúy buì (âaío) tæì maî nhë phán cuía säú buì 9 tæång æïng.
Baìi giaíng Kyî Thuáût Säú Trang 8 Vê duû: 3 → 0011 Maì säú 6 laì buì 9 cuía 3: 6 → 1100 Láúy nghëch âaío ta coï: 0011 = 3 Váûy, âàûc træng cuía maî BCD säú hoüc laì coï tênh cháút âäúi xæïng qua mäüt âæåìng trung gian. b2. Maî BCD khäng coï troüng säú: laì loaûi maî khäng cho pheïp phán têch thaình âa thæïc theo cå säú cuía noï. Vê duû: Maî Gray, Maî Gray thæìa 3. Âàûc træng cuía maî Gray laì loaûi bäü maî maì trong âoï hai tæì maî nhë phán âæïng kãú tiãúp nhau bao giåì cuîng chè khaïc nhau 1 bit. Vê duû: Maî Gray: 2 → 0011 Coìn âäúi våïi maî BCD 8421: 3 → 0010 3 → 0011 4 → 0110 4 → 0100 Caïc baíng dæåïi âáy trçnh baìy mäüt säú loaûi maî thäng duûng: Baíng 1: Caïc maî BCD tæû nhiãn. BCD 8421 BCD 5421 BCD quaï 3 Säú tháûp a3 a2 a1 a0 b3 b2 b1 b0 c3 c2 c1 c0 phán 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 1 2 0 0 1 1 0 0 1 1 0 1 1 0 3 0 1 0 0 0 1 0 0 0 1 1 1 4 0 1 0 1 1 0 0 0 1 0 0 0 5 0 1 1 0 1 0 0 1 1 0 0 1 6 0 1 1 1 1 0 1 0 1 0 1 0 7 1 0 0 0 1 0 1 1 1 0 1 1 8 1 0 0 1 1 1 0 0 1 1 0 0 9
Chæång 1. Hãû thäúng säú âãúm vaì khaïi niãûm vãö maî Trang 9 Baíng 2: Caïc maî BCD säú hoüc BCD 2421 BCD 5121 BCD 84-2-1 Säú tháûp a3 a2 a1 a0 b3 B2 b1 b0 c3 c2 c1 c0 phán 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 1 0 2 0 0 1 1 0 0 1 1 0 1 0 1 3 0 1 0 0 0 1 0 0 0 1 0 0 4 1 0 1 1 1 0 0 0 1 0 1 1 5 1 1 0 0 1 1 0 0 1 0 1 0 6 1 1 0 1 1 1 0 1 1 0 0 1 7 1 1 1 0 1 1 1 0 1 0 0 0 8 1 1 1 1 1 1 1 1 1 1 1 1 9 Baíng 3: BCD tæû nhiãn vaì maî Gray. BCD 8421 BCD quaï 3 Maî Gray Gray quaï 3 Säú tháûp a3 a2 a1 a0 c3 c2 c1 c0 G3 G2 G1 G0 g3 g2 g1 g0 phán 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 2 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 3 0 1 0 0 0 1 1 1 0 1 1 0 0 1 0 0 4 0 1 0 1 1 0 0 0 0 1 1 1 1 1 0 0 5 0 1 1 0 1 0 0 1 0 1 0 1 1 1 0 1 6 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 1 7 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 0 8 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 0 9 Chuï yï: Maî Gray âæåüc suy ra tæì maî BCD 8421 bàòng caïch: caïc bit 0,1 âæïng sau bit 0 (åí maî BCD 8421) khi chuyãøn sang maî Gray thç âæåüc giæî nguyãn, coìn caïc bit 0,1 âæïng sau bit 1 (åí maî BCD 8421) khi chuyãøn sang maî Gray thç âæåüc âäøi ngæåüc laûi, nghéa laì tæì bit 1 thaình bit 0 vaì bit 0 thaình bit 1.
Baìi giaíng Kyî Thuáût Säú Trang 10 1.2.2.3. Maûch nháûn daûng säú BCD 8421 : a 3 Maûch nháûn y a2 daûng säú BCD a1 + y = 1 → a3 a2 a1 a0 khäng phaíi säú BCD 8421 + y = 0 → a3 a2 a1 a0 laì säú BCD 8421 Suy ra âãø nháûn daûng mäüt säú nhë phán 4 bit khäng phaíi laì mäüt säú BCD 8421 thç ngoî ra y = 1, nghéa laì: bit a3 luän luän bàòng 1 vaì bit a1 hoàûc a2 bàòng 1. Phæång trçnh logic : y = a3 (a1 + a2 ) = a3a1 + a3 a2 Så âäö logic: a1 a2 y a3 Do viãûc xuáút hiãûn säú BCD nãn coï hai caïch nháûp dæî liãûu vaìo maïy tênh: nháûp säú nhë phán, nháûp bàòng maî BCD. Âãø nháûp säú BCD tháûp phán hai chæî säú thç maïy tênh chia säú tháûp phán thaình caïc âãöcaïc vaì mäùi âãöcaïc âæåüc biãøu diãùn bàòng säú BCD tæång æïng. Vê duû: 11 (tháûp phán) coï thãø âæåüc nháûp vaìo maïy tênh theo 2 caïch: - Säú nhë phán: 1011 - Maî BCD : 0001 0001 1.2.2.4. Caïc pheïp tênh trãn säú BCD a. Pheïp cäüng Säú tháûp phán laì 128 thç: - Säú nhë phán laì: 10000000 - Säú BCD laì: 0001 0010 1000 Do säú BCD chè coï tæì 0 âãún 9 nãn âäúi våïi nhæîng säú tháûp phán låïn hån, noï chia säú tháûp phán thaình nhiãöu âãöcaïc, mäùi âãöcaïc âæåüc biãøu diãùn bàòng säú BCD tæång æïng.
Chæång 1. Hãû thäúng säú âãúm vaì khaïi niãûm vãö maî Trang 11 5 → 0101 7 → 0111 + + + + 3 → 0011 5 → 0101 8 1000 12 1100 + Sä ú hiã ûu chènh 0110 0001 0010 1 2 b. Pheïp træì A - B = A + B 7 → 0111 0111 - - + 5 → 0101 1010 Buì 1 cuía 5 2 0010 10001 + 1 Buì 2 cuía 5 0010 Buì 1 laì bit 0 thaình 1, bit 1 thaình 0. Buì 2 laì buì 1 cäüng thãm 1. Xeït caïc træåìng håüp måí räüng: - Thæûc hiãûn træì 2 säú BCD 1 âãöcaïc maì säú bë træì nhoí hån säú træì. - Måí räüng cho cäüng vaì træì 2 säú BCD nhiãöu âãöcaïc.
Baìi giaíng Kyî Thuáût Säú Trang 12 Chæång 2 ÂAÛI SÄÚ BOOLE 2.1. CAÏC TIÃN ÂÃÖ VAÌ ÂËNH LYÏ ÂAÛI SÄÚ BOOLE 2.1.1. Caïc tiãn âãö Cho mäüt táûp håüp B hæîu haûn trong âoï ngæåìi ta trang bë caïc pheïp toaïn + (cäüng logic), x (nhán logic), - (buì logic ) vaì hai pháön tæí 0 vaì 1 láûp thaình mäüt cáúu truïc âaûi säú Boole. ∀x,y ∈ B thç: x + y ∈ B, x*y ∈ B thoía maîn 5 tiãn âãö sau: 2.1.1.1. Tiãn âãö giao hoaïn ∀x,y ∈ B: x + y = y + x 2.1.1.2. Tiãn âãö phäúi håüp ∀x,y,z ∈ B: (x + y) + z = x + ( y + z ) = x + y + z (x. y).z = x.(y. z) = x.y.z 2.1.1.3. Tiãn âãö phán phäúi ∀x,y, z ∈ B: x.(y + z ) = x.y + x.z x + (y.z) = (x + y)(x + z) 2.1.1.4. Tiãn âãö vãö pháön tæí trung hoìa Trong táûp B täön taûi hai pháön tæí trung hoìa âoï laì pháön tæí âån vë vaì pháön tæí 0, pháön tæí âån vë kyï hiãûu laì 1, pháön tæí 0 kyï hiãûu laì 0. ∀x ∈ B: x + 1 = 1 x . 1 = x x + 0 = x x . 0 = 0 2.1.1.5. Tiãn âãö vãö pháön tæí buì ∀x ∈ B, bao giåì cuîng täön taûi pháön tæí buì tæång æïng sao cho luän thoía maîn: x + x = 0
Chæång 2. Âaûi säú BOOLE Trang 13 x. x = 0 Nãúu B = B* = {0, 1} vaì thoía maîn 5 tiãn âãö trãn thç cuîng láûp thaình cáúu truïc âaûi säú Boole nhæng laì cáúu truïc âaûi säú Boole nhoí nháút. 2.1.2. Caïc âënh lyï 2.1.2.1 Váún âãö âäúi ngáùu trong âaûi säú Boole Hai mãûnh âãö (hai biãøu thæïc, hai âënh lyï) âæåüc goüi laì âäúi ngáùu våïi nhau nãúu trong mãûnh âãö naìy ngæåìi ta thay pheïp toaïn cäüng thaình pheïp toaïn nhán vaì ngæåüc laûi,thay 0 bàòng 1 vaì ngæåüc laûi thç seî suy ra âæåüc mãûnh âãö kia. Khi hai mãûnh âãö âäúi ngáùu våïi nhau, nãúu 1 trong 2 mãûnh âãö âæåüc chæïng minh laì âuïng thç mãûnh âãö coìn laûi laì âuïng. Vê duû: x.(y + z ) = ( x. y) + ( x. z ) x + (y. z ) = ( x + y )( x + z ) Vê duû: x + x = 1 x. x = 0 2.1.2.2. Caïc âënh lyï a. Âënh lyï vãö pháön tæí buì laì duy nháút ∀x, y ∈ B: x + y = 1⎫ ⎬ ⇒ y = x x.y = 0 ⎭ ∀x ∈ B: x + x +. . . . . + x = x x. x. x. . . . . . x = x b. Âënh lyï De Morgan ∀x, y, z ∈ B, ta coï: x + y + z = x.y.z x.y.z = x + y + z ∀x ∈ B, ta coï: x = x ∀x, y, z ∈ B, ta coï:
Baìi giaíng Kyî Thuáût Säú Trang 14 x + y + z = x + y + z = x.y.z x. y. z = x.y.z =x + y + z ∀x, y ∈ B, ta coï: x. (x + y) = x.y x + (x . y) = x + y ∀x, y ∈ B, ta coï: x + x. y = x x.(x + y) = x Våïi 0, 1 ∈ B, ta coï: 0 = 1 vaì 1 = 0 2.2. HAÌM BOOLE VAÌ CAÏC PHÆÅNG PHAÏP BIÃØU DIÃÙN 2.2.1. Haìm Boole 2.2.1.1. Âënh nghéa Haìm Boole laì mäüt aïnh xaû Boole tæì âaûi säú Boole vaìo chênh noï. Tæïc laì ∀x, y ∈ B âæåüc goüi laì biãún Boole thç haìm Boole, kyï hiãûu laì f, âæåüc hçnh thaình trãn cå såí liãn kãút caïc biãún Boole bàòng caïc pheïp toaïn + (cäüng logic ), x (nhán logic ), hoàûc nghëch âaío logic (-). Haìm Boole âån giaín nháút laì haìm Boole theo 1 biãún Boole. Kyï hiãûu: f(x) = x f(x) = x f(x) = α (α: laì hàòng säú ) Trong træåìng håüp täøng quaït, ta coï haìm Boole theo n biãún Boole âæåüc kyï hiãûu nhæ sau: f(x1, x2,. . . . . ., xn ) 2.2.1.2. Caïc tênh cháút cuía haìm Boole Nãúu f(x1, x2, , xn) laì mäüt haìm Boole thç: + α.f(x1, x2, , xn) cuîng laì mäüt haìm Boole. + f (x1, x2, , xn) cuîng laì mäüt haìm Boole. Nãúu f1(x1, x2, , xn) vaì f2(x1, x2, , xn) laì nhæîng haìm Boole thç: + f1(x1, x2, , xn) + f2(x1, x2, , xn) cuîng laì mäüt haìm Boole. + f1(x1, x2, , xn).f2(x1, x2, , xn) cuîng laì mäüt haìm Boole.
Chæång 2. Âaûi säú BOOLE Trang 15 Váûy, mäüt haìm Boole f cuîng âæåüc hçnh thaình trãn cå såí liãn kãút caïc haìm Boole bàòng caïc pheïp toaïn + (cäüng logic), x (nhán logic) hoàûc nghëch âaío logic (-). 2.2.1.3. Giaï trë cuía haìm Boole Goüi f (x1, x2, , xn) laì mäüt haìm Boole theo biãún Boole. Trong f ngæåìi ta thay caïc biãún xi bàòng caïc giaï trë cuû thãø αi (i = 1, n ) thç haìm f (α1, α2, α3, , αn) âæåüc goüi laì giaï trë cuía haìm Boole theo n biãún. Vê duû: Xeït haìm f(x1, x2 ) = x1 + x2 Xeït B = B* ={0,1} x1 x2 f(x1, x2) ⇒ Nãúu x1 = x2 =0 f(0,0) = 0 0 0 0 ⇒ Nãúu x1 = 0, x2 = 1 f(0,1) = 1 0 1 1 ⇒ Nãúu x1 = 1, x2 = 0 f(1,0) = 1 1 0 1 ⇒ Nãúu x1 = 1, x2 = 1 f(1,1) = 1 1 1 1 Ta láûp âæåüc baíng giaï trë cuía haìm trãn. Vê duû: f (x1, x2, x3 ) = x1 + x2.x3 Xeït B = B* = {0,1 } Baíng giaï trë cuía haìm: x1 x2 x3 f (x1, x2, x3) 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1
Baìi giaíng Kyî Thuáût Säú Trang 16 2.2.2. Caïc phæång phaïp biãøu diãùn haìm Boole 2.2.2.1. Phæång phaïp baíng Laì phæång phaïp thæåìng duìng âãø biãøu diãùn haìm säú noïi chung. Phæång phaïp naìy gäöm mäüt baíng âæåüc chia laìm hai pháön: - Mäüt pháön daình cho biãún âãø ghi caïc täø håüp giaï trë coï thãø coï cuía biãún. - Mäüt pháön daình cho haìm âãø ghi caïc giaï trë cuía haìm ra tæång æïng våïi caïc täø håüp cuía caïc biãún vaìo. 2.2.2.2. Phæång phaïp giaíi têch Laì phæång phaïp biãøu diãùn haìm Boole dæåïi daûng täøng caïc têch säú, hoàûc dæåïi daûng têch cuía caïc täøng säú. Daûng täøng cuía caïc têch säú goüi laì daûng chênh tàõc thæï nháút, coìn daûng têch cuía caïc täøng laì daûng chênh tàõc thæï hai cuía haìm Boole, vaì hai daûng chênh tàõc naìy laì âäúi ngáùu nhau. a. Daûng chênh tàõc 1(Daûng täøng cuía caïc têch säú) Xeït caïc haìm Boole âån giaín sau âáy: f(x) = x, f(x) = x , f(x) = α. Xeït f(x) = x: Ta coï: x =0. x + 1. x màût khaïc: ⎧f()1 = 1 f()x = x ⇒ ⎨ ⎩f()0 = 0 suy ra f(x) = x coï thãø biãøøu diãùn: f(x) = x = f(0). x + f (1).x trong âoï: f (0), f (1) âæåüc goüi laì giaï trë cuía haìm Boole theo mäüt biãún. Xeït f(x) = x : Ta coï: x = 1. x + 0. x Màût khaïc: ⎧f ()1 = 0 f()x = x ⇒ ⎨ ⎩f ()0 = 1 Suy ra: f(x) = x coï thãø biãøu diãùn: f(x) = x = f(0). x + f(1).x
Chæång 2. Âaûi säú BOOLE Trang 17 Xeït f(x) = α: Ta coï: α = α.1 = α(x + x ) = x .α + α.x Màût khaïc: ⎧f()1 = α f()x = α ⇒ ⎨ ⎩f()0 = α Suy ra f(x) = α coï thãø âæåüc biãøu diãùn: f(x) = α = f(0). x + f(1).x Kãút luáûn: Duì laì f(x) = x, f(x) = x hay f(x) = α, ta âãöu coï daûng: f(x) = f(0).x + f(1).x Váûy f(x) = f(0).x + f(1).x trong âoï f (0), f (1) âæåüc goüi laì giaï trë cuía haìm Boole theo mäüt biãún, âæåüc goüi laì daûng chênh tàõc thæï nháút (daûng täøng cuía caïc têch) theo mäüt biãún. Trong træåìng håüp hai biãún f(x1, x2) thç caïch biãøu diãùn cuîng hoaìn toaìn dæûa trãn caïch biãøu diãùn cuía daûng chênh tàõc thæï nháút theo 1 biãún (trong âoï xem mäüt biãún laì hàòng säú). Ta coï: f(x1, x2 ) = f(0, x2). x 1 + f(1,x2).x1 maì: f(0, x2) = f(0,0 ). x 2 + f(0,1).x2 vaì: f(1, x2) = f(1,0). x 2 + f(1,1). x2 Suy ra: f(x1, x2 ) = f(0,0) x 1 x 2 + f(0, 1) x 1x2 + f(1,0 )x1 x 2 + f(1,1)x1x2 2 2 −1 α1 α2 Váûy: f (x1, x2) = ∑ f(α1,α2 )x1 x 2 e=0 trong âoï e laì säú tháûp phán tæång æïng våïi maî (α1, α2) vaì: x nãúu α = 1 α1 1 1 x1 = x 1 nãúu α1 = 0 x2 nãúu α2 = 1 α 2 x 2 = x 2 nãúu α2 = 0
Baìi giaíng Kyî Thuáût Säú Trang 18 Täøng quaït cho n biãún: 2n −1 α1 α2 αn f(x1, x2, , xn) = ∑f(α1,α2 , ,αn )x1 x 2 x n e=0 trong âoï e laì säú tháûp phán tæång æïng våïi maî nhë phán (α1, α2, , αn); vaì: α i xi nãúu αi = 1 x i = x i nãúu αi = 0 Vê duû: 23 −1 α1 α2 α3 f(x1, x2, x3) = ∑ f (α1, α2, α3). x1 . x2 . x3 e=0 f(x1, x2, x3) = f(0,0,0)x 1 x 2 x 3 + f(0,0,1)x 1 x 2 x3 + f(0,1,0)x 1x2 x 3 + f(0,1,1)x 1 x2 x3 + f(1,0,0) x1 x 2 x 3 + f(1,0,1)x1 x 2 x3 + f(1,1,0) x1 x2 x 3 + f(1,1,1) x1 x2 x3 Váûy daûng chênh tàõc thæï nháút laì daûng täøng cuía caïc têch maì trong mäùi têch säú chæïa âáöy âuí caïc biãún Boole dæåïi daûng tháût hoàûc daûng buì (nghëch âaío). b. Daûng chênh tàõc 2 (têch cuía caïc täøng): Âáy laì daûng âäúi ngáùu cuía daûng chênh tàõc 1 nãn biãøu thæïc täøng quaït cuía daûng chênh tàõc thæï hai cho n biãún laì: 2n−1 α1 α2 αn f(x1, x2, , xn) = ∏ [f(α1, α2, α3) + x1 + x2 + + xn )] e=0 trong âoï e laì säú tháûp phán tæång æïng cuía maî nhë phán (α1, α2, , αn); vaì: x nãúu α = 1 α i i i x i = xi nãúu αi = 0 Vê duû: f(x1,x2)=[f(0,0)+x1+x2][f(0,1)+x1+x 2][f(1,0)+x 1+x2][f(1,1)+x 1+x 2]
Chæång 2. Âaûi säú BOOLE Trang 19 f(x1, x2, x3) = [f(0,0,0)+x1+ x2+x3].[f(0,0,1)+x1+x2+x 3]. [f(0,1,0)+x1+x 2+x3].[f(0,1,1)+x1+x 2+x 3]. [f(1,0,0)+x 1+x2+x3].[f(1,0,1)+x 1+x2+x 3]. [f(1,1,0)+x 1+x 2+x3].[f(1,1,1)+x 1+x 2+x 3] Váûy, daûng chênh tàõc thæï hai laì daûng têch cuía caïc täøng säú maì trong âoï mäùi täøng säú naìy chæïa âáöy âuí caïc biãún Boole dæåïi daûng tháût hoàûc daûng buì. Chuï yï: Xeït vê duû 1: f(x1, x2) = x1 + x2 , Viãút dæåïi daûng chênh tàõc 1: f(x1, x2 ) = 0.x 1 x 2 + 1.x 1.x2 + 1.x1.x 2 + 1.x1.x2 = x 1.x2 + x1.x 2 + x1.x2 Tæì vê duû trãn ta tháúy: Daûng chênh tàõc thæï nháút laì daûng liãût kã táút caí caïc täø håüp nhë phán caïc biãún vaìo sao cho tæång æïng våïi nhæîng täø håüp âoï giaï trë cuía haìm ra bàòng 1. Khi liãût kã nãúu biãún tæång æïng bàòng 1 âæåüc viãút åí daûng tháût (x), vaì biãún tæång æïng bàòng 0 âæåüc viãút åí daûng buì (x ). Xeït vê duû 2: f(x1, x2, x3) = x1 + x2.x3 Viãút dæåïi daûng chênh tàõc 2: f(x1, x2, x3) = [0+x1+x2+x3].[0+x1+x2+x 3].[0+x1+x 2+x3]. [1+x1+x 2+x 3].[1+x 1+x2+x3].[1+x 1+x2+x 3]. [1+x 1+x 2+x3].[1+x 1+x 2+x 3] Hay: f(x1, x2, x3) = x1 + x2.x3 = [x1+x2+x3].[x1+x2+x 3].[x1+x 2+x3] Váûy, daûng chênh tàõc thæï hai laì daûng liãût kã táút caí caïc täø håüp nhë phán caïc biãún vaìo sao cho tæång æïng våïi nhæîng täø håüp âoï giaï trë cuía haìm ra bàòng 0. Khi liãût kã nãúu biãún tæång æïng bàòng 0 âæåüc viãút åí daûng tháût (x), vaì biãún tæång æïng bàòng 1 âæåüc viãút åí daûng buì (x ). Xeït vê duû âån giaín sau âãø hiãøu roî hån vãö caïch thaình láûp baíng giaï trë cuía haìm, tçm haìm maûch vaì thiãút kãú maûch: Haîy thiãút kãú maûch âiãûn sao
Baìi giaíng Kyî Thuáût Säú Trang 20 cho khi cäng tàõc 1 âoïng thç âeìn âoí, cäng tàõc 2 âoïng âeìn âoí, caí hai cäng tàõc âoïng âeìn âoí. Giaíi Ta qui âënh: - Cäng tàõc håí : 0 Âeìn tàõt : 0 - Cäng tàõc âoïng : 1 Âeìn âoí : 1 Luïc âoï ta coï baíng traûng thaïi mä taí hoaût âäüng cuía maûch: Cäng tàõc 1 Cäng tàõc 2 Âeìn x1 x2 f(x1,x2) 0 0 0 0 1 1 1 0 1 1 1 1 Viãút theo daûng chênh tàõc 1 ta coï: f(x1, x2) = 0.x 1 x 2 + 1.x 1.x2 + 1.x1.x 2 + 1.x1.x2 = x 1. x2 + x1.x 2 + x1.x2 = x 1. x2 + x1(x 2 + x2) = x 1. x2 + x1 = x1 + x2 Viãút theo daûng chênh tàõc 2 ta coï: f(x1, x2) = [0+x1+x2].[1+x1+x 2].[1+x 1+ x2].[1+x 1+x 2] = [x1+ x2].1.1.1 = x1 + x2 Váûy, duì viãút theo daûng chênh tàõc 1 hay chênh tàõc 2 ta âãöu coï haìm maûch: f(x1, x2) = x1 + x2 2.2.2.3. Phæång phaïp biãøu diãùn bàòng baíng Karnaugh Âáy laì caïch biãøu diãùn laûi cuía phæång phaïp baíng dæåïi daûng baíng gäöm caïc ä vuäng coï daûng nhæ hçnh bãn.
Chæång 2. Âaûi säú BOOLE Trang 21 Trãn baíng naìy ngæåìi ta bäú trê caïc biãún vaìo theo haìng hoàûc theo cäüt cuía baíng. Trong træåìng håüp säú læåüng biãún vaìo laì chàôn, ngæåìi ta bäú trê säú læåüng biãún vaìo theo haìng ngang bàòng säú læåüng biãún vaìo theo cäüt doüc cuía baíng. Trong træåìng håüp säú læåüng biãún vaìo laì leí, ngæåìi ta bäú trê säú læåüng biãún vaìo theo haìng ngang nhiãöu hån säú læåüng biãún vaìo theo cäüt doüc 1 biãún hoàûc ngæåüc laûi. Caïc täø håüp giaï trë cuía biãún vaìo theo haìng ngang hoàûc theo cäüt doüc cuía baíng âæåüc bäú trê sao cho khi ta âi tæì mäüt ä sang mäüt ä lán cáûn våïi noï chè laìm thay âäøi mäüt giaï trë cuía biãún, nhæ váûy thæï tæ û bäú trê hay sàõp xãúp caïc täø håüp giaï trë cuía biãún vaìo theo haìng ngang hoàûc theo cäüt doüc cuía baíng Karnaugh hoaìn toaìn tuán thuí theo maî Gray. Giaï trë ghi trong mäùi ä vuäng naìy chênh laì giaï trë cuía haìm ra tæång æïng våïi caïc täø håüp giaï trë cuía biãún vaìo. ÅÍ nhæîng ä maì giaï trë haìm laì khäng xaïc âënh, coï nghéa laì giaï trë cuía haìm laì tuìy yï (hay tuìy âënh), ngæåìi ta kê hiãûu bàòng chæî x. Nãúu coï n biãún vaìo seî coï 2n ä vuäng. 2.3. TÄÚI THIÃØU HAÌM BOOLE 2.3.1. Âaûi cæång Trong thiãút bë maïy tênh ngæåìi ta thæåìng thiãút kãú gäöm nhiãöu modul (kháu) vaì mäùi modul naìy âæåüc âàûc træng bàòng mäüt phæång trçnh logic. Trong âoï, mæïc âäü phæïc taûp cuía så âäö tuìy thuäüc vaìo phæång trçnh logic biãøu diãùn chuïng. Viãûc âaût âæåüc âäü äøn âënh cao hay khäng laì tuìy thuäüc vaìo phæång trçnh logic biãøu diãùn chuïng åí daûng täúi thiãøu hoïa hay chæa. Âãø thæûc hiãûn âæåüc âiãöu âoï, khi thiãút kãú maûch säú ngæåìi ta âàût ra váún âãö täúi thiãøu hoïa caïc haìm logic. Âiãöu âoï coï nghéa laì phæång trçnh logic biãøu diãùn sao cho thæûc sæû goün nháút (säú læåüng caïc pheïp tênh vaì säú læåüng caïc säú âæåüc biãøu diãùn dæåïi daûng tháût hoàûc buì laì êt nháút). Tuy nhiãn trong thæûc tãú, khäng phaíi luïc naìo cuîng âaût âæåüc låìi giaíi täúi æu cho baìi toaïn täúi thiãøu hoïa.
Baìi giaíng Kyî Thuáût Säú Trang 22 2.3.2. Caïc bæåïc tiãún haình täúi thiãøu hoïa - Duìng caïc pheïp täúi thiãøu âãø täúi thiãøu hoïa caïc haìm säú logic. - Ruït ra nhæîng thæìa säú chung nhàòm muûc âêch täúi thiãøu hoïa thãm mäüt bæåïc næîa caïc phæång trçnh logic. 2.3.3. Caïc phæång phaïp täúi thiãøu hoïa 2.3.3.1. Phæång phaïp giaíi têch Âoï laì phæång phaïp täúi thiãøu hoïa haìm Boole (phæång trçnh logic) dæûa vaìo caïc tiãn âãö, âënh lyï cuía âaûi säú Boole. Vê duû: f(x1, x2) = x 1x2 + x1 x 2 + x1x2 = (x 1 + x1)x2 + x1 x 2 = x2 + x1 x 2 = x2 + x1 Vê duû: f(x1, x2, x3) = x 1x2x3 + x1 x 2 x 3 + x1 x 2x3 + x1x2 x 3 + x1x2x3 = x 1x2x3 + x1 x 2 x 3 + x1 x 2x3 + x1x2 (x 3 + x3) = x 1x2x3 + x1 x 2(x 3 + x3) + x1x2 = x 1x2x3 + x1(x 2 + x2) = x 1x2x3 + x1 = x1 + x2 x3 2.3.3.2. Phæång phaïp baíng Karnaugh a. Täúi thiãøu hoïa haìm Boole bàòng baíng Karnaugh Âãø täúi thiãøu hoïa haìm Boole bàòng phæång phaïp baíng Karnaugh phaíi tuán thuí theo qui tàõc vãö ä kãú cáûn: “Hai ä âæåüc goüi laì kãú cáûn nhau laì hai ä maì khi ta tæì ä naìy sang ä kia chè laìm thay âäøi giaï trë cuía 1 biãún. “ Quy tàõc chung cuía phæång phaïp ruït goün bàòng baíng Karnaugh laì gom (kãút håüp) caïc ä kãú cáûn laûi våïi nhau. Khi gom 2 ä kãú cáûn nhau seî loaûi âæåüc 1 biãún (2 ä =21 loaûi 1 biãún). Khi gom 4 ä kãú cáûn seî loaûi âæåüc 2 biãún (4 ä =22 loaûi 2 biãún). Khi gom 8 ä kãú cáûn seî loaûi âæåüc 3 biãún (8 ä = 23 loaûi 3 biãún ). Täøng quaït, khi gom 2n ä kãú cáûn seî loaûi âæåüc n biãún. Nhæîng biãún bë loaûi laì nhæîng biãún khi ta âi voìng qua caïc ä kãú cáûn maì giaï trë cuía chuïng thay âäøi.
Chæång 2. Âaûi säú BOOLE Trang 23 Nhæîng âiãöu cáön læu y:ï - Voìng gom âæåüc goüi laì håüp lãû khi trong voìng gom âoï coï êt nháút 1 ä chæa thuäüc voìng gom naìo. - Viãûc kãút håüp nhæîng ä kãú cáûn våïi nhau coìn tuìy thuäüc vaìo phæång phaïp biãøu diãùîn haìm Boole theo daûng chênh tàõc 1 hoàûc chênh tàõc 2. Âiãöu naìy coï nghéa laì: nãúu ta biãøu diãùn haìm Boole theo daûng chênh tàõc 1 thç ta chè quan tám nhæîng ä kãú cáûn naìo coï giaï trë bàòng 1 vaì tuìy âënh, ngæåüc laûi nãúu ta biãøu diãùn haìm Boole dæåïi daûng chênh tàõc 2 thç ta chè quan tám nhæîng ä kãú cáûn naìo coï giaï trë bàòng 0 vaì tuìy âënh. Ta quan tám nhæîng ä tuìy âënh sao cho nhæîng ä naìy kãút håüp våïi nhæîng ä coï giaï trë bàòng 1 (nãúu biãøu diãùn theo daûng chênh tàõc 1) hoàûc bàòng 0 (nãúu biãøu diãùn theo daûng chênh tàõc 2) seî laìm cho säú læåüng ä kãú cáûn laì 2n låïn nháút. - Caïc ä kãú cáûn muäún gom âæåüc phaíi laì kãú cáûn voìng troìn nghéa laì ä kãú cáûûn cuäúi cuîng laì ä kãú cáûn âáöu tiãn. c. Caïc vê duû Vê duû 1: Täúi thiãøu hoïa haìm sau bàòng phæång phaïp baíng Karnaugh. f(x ,x ) 1 2 x x 1 2 0 1 Täúi thiãøu hoïa theo daûng chênh tàõc 2: 0 0 1 1 1 1 f(x1,x2) = x1 + x2 Vê duû 2: Täúi thiãøu hoïa haìm sau bàòng phæång phaïp baíng Karnaugh. f(x ,x ,x ) 1 2 3 Voìng gom 1: x x1,x2 1 x3 00 01 11 10 0 0 0 1 1 Voìng gom 2: x2.x3 1 0 1 1 1 Täúi giaín theo daûng chênh tàõc 1: Ta chè quan tám âãún nhæîng ä coï giaï trë bàòng 1 vaì tuìy âënh, nhæ váûy seî coï 2 voìng gom âãø phuí hãút caïc ä coï giaï trë bàòng 1: voìng gom 1 gäöm 4 ä kãú cáûn, vaì voìng gom 2 gäöm 2 ä kãú cáûn (hçnh veî).
Baìi giaíng Kyî Thuáût Säú Trang 24 Âäúi våïi voìng gom 1: Coï 4 ä = 22 nãn seî loaûi âæåüc 2 biãún. Khi âi voìng qua 4 ä kãú cáûn trong voìng gom chè coï giaï trë cuía biãún x1 khäng âäøi (luän bàòng 1), coìn giaï trë cuía biãún x2 thay âäøi (tæì 1→0) vaì giaï trë cuía biãún x3 thay âäøi (tæì 0→1) nãn caïc biãún x2 vaì x3 bë loaûi, chè coìn laûi biãún x1 trong kãút quaí cuía voìng gom 1. Vç x1=1 nãn kãút quaí cuía voìng gom 1 theo daûng chênh tàõc 1 seî coï x1 viãút åí daûng tháût: x1 Âäúi våïi voìng gom 2: Coï 2 ä = 21 nãn seî loaûi âæåüc 1 biãún. Khi âi voìng qua 2 ä kãú cáûn trong voìng gom giaï trë cuía biãún x2 vaì x3 khäng âäøi, coìn giaï trë cuía biãún x1 thay âäøi (tæì 0→1) nãn caïc biãún x2 vaì x3 âæåüc giæî laûi, chè coï biãún x1 bë loaûi. Vç x2=1 vaì x3=1 nãn kãút quaí cuía voìng gom 2 theo daûng chênh tàõc 1 seî coï x2 vaì x3 viãút åí daûng tháût: x2.x3 Kãút håüp 2 voìng gom ta coï kãút quaí täúi giaín theo daûng chênh tàõc 1: f(x1, x2, x3) = x1 + x2.x3 Täúi giaín theo daûng chênh tàõc 2: Ta quan tám âãún nhæîng ä coï giaï trë bàòng 0 vaì tuìy âënh, nhæ váûy cuîng coï 2 voìng gom (hçnh veî), mäùi voìng gom âãöu gäöm 2 ä kãú cáûn. Âäúi våïi voìng gom 1: Coï 2 ä = 21 nãn loaûi âæåüc 1 biãún, biãún bë loaûi laì x2 (vç coï giaï trë thay âäøi tæì 0→1). Vç x1=0 vaì x3=0 nãn kãút quaí cuía voìng gom 1 theo daûng chênh tàõc 2 seî coï x1 vaì x3 åí daûng tháût: x1+ x3. Âäúi våïi voìng gom 2: Coï 2 ä = 21 nãn loaûi âæåüc 1 biãún, biãún bë loaûi laì x3 (vç coï giaï trë thay âäøi tæì 0 → 1). Vç x1=0 vaì x2=0 nãn kãút quaí cuía voìng gom 2 theo daûng chênh tàõc 2 seî coï x1 vaì x2 åí daûng tháût: x1 + x2. f(x1,x2,x3) x1,x2 Voìng gom 1: x1 + x3 x3 00 01 11 10 0 0 0 1 1 Voìng gom 2: x + x 1 0 1 1 1 1 2 Kãút håüp 2 voìng gom coï kãút quaí cuía haìm f viãút theo daûng chênh tàõc 2: f (x1, x2, x3) = (x1+x3).(x1+x2) = x1.x1 + x1.x2 + x1.x3 + x2.x3 = x1 + x1.x2 + x1.x3 + x2.x3
Chæång 2. Âaûi säú BOOLE Trang 25 = x1(1+ x2 + x3) + x2.x3 = x1 + x2.x3 Nháûn xeït: Trong vê duû naìy, haìm ra viãút theo daûng chênh tàõc 1 vaì haìm ra viãút theo daûng chênh tàõc 2 laì giäúng nhau. Tuy nhiãn coï træåìng håüp haìm ra cuía hai daûng chênh tàõc 1 vaì 2 laì khaïc nhau, nhæng giaï trë cuía haìm ra æïng våïi mäüt täø håüp biãún âáöu vaìo laì giäúng nhau trong caí 2 daûng chênh tàõc. Chuï yï: Ngæåìi ta thæåìng cho haìm Boole dæåïi daûng biãøu thæïc ruït goün. Vç coï 2 caïch biãøu diãùn haìm Boole theo daûng chênh tàõc 1 hoàûc 2 nãn seî coï 2 caïch cho giaï trë cuía haìm Boole æïng våïi 2 daûng chênh tàõc âoï: Daûng chênh tàõc 1: Täøng caïc têch säú. f(x1, x2, x3) = Σ(3, 4, 7) + d(5, 6) Trong âoï d: giaï trë caïc ä naìy laì tuìy âënh (d: don’t care) f(x1,x2,x3) x1,x2 x 3 00 01 11 10 0 00X1 1 011X Luïc âoï baíng Karnaugh seî âæåüc cho nhæ hçnh trãn. Tæì biãøu thæïc ruït goün cuía haìm ta tháúy taûi caïc ä æïng våïi täø håüp nhë phán caïc biãún vaìo coï giaï trë laì 3, 4, 7 thç haìm ra coï giaï trë bàòng 1; taûi caïc ä æïng våïi täø håüp nhë phán caïc biãún vaìo coï giaï trë laì 5,6 thç haìm ra coï giaï trë laì tuìy âënh; haìm ra coï giaï trë bàòng 0 åí nhæîng ä coìn laûi æïng våïi täø håüp caïc biãún vaìo coï giaï trë laì 0, 1, 2. Daûng chênh tàõc 2: Têch caïc täøng säú. Phæång trçnh logic trãn cuîng tæång âæång: f(x1, x2, x3) = Π(0, 1, 2) + d(5, 6)
Baìi giaíng Kyî Thuáût Säú Trang 26 Vê duû 3: Täúi thiãøu hoïa haìm 4 biãún sau âáy: f(x ,x ,x ,x ) f(x ,x ,x ,x ) 1 2 3 4 x ,x 1 2 3 4 x ,x 1 2 1 2 x3,x 4 00 01 11 10 x3,x4 00 01 11 10 00 x x 1 x 00 x x 1 x 01 x 0 1 x 01 x 0 1 x 11 0 x X 1 11 0 x x 1 10 1 1 X 1 10 1 1 x 1 Voìng gom 1 Voìng gom 2 Ta thæûc hiãûn täúi thiãøu hoïa theo daûng chênh tàõc 1: Tæì baín âäö Karnaugh ta coï 2 voìng gom, voìng gom 1 gäöm 8 ä kãú cáûn vaì voìng gom 2 gäöm 8 ä kãú cáûn. Kãút quaí täúi thiãøu hoïa nhæ sau: Voìng gom 1: x 4 Voìng gom 2: x1 Váûy: f(x1, x2, x3, x4) = x 4 + x1
Baìi giaíng Kyî Thuáût Säú Trang 12 Chæång 2 ÂAÛI SÄÚ BOOLE 2.1. CAÏC TIÃN ÂÃÖ VAÌ ÂËNH LYÏ ÂAÛI SÄÚ BOOLE 2.1.1. Caïc tiãn âãö Cho mäüt táûp håüp B hæîu haûn trong âoï ngæåìi ta trang bë caïc pheïp toaïn + (cäüng logic), x (nhán logic), - (buì logic ) vaì hai pháön tæí 0 vaì 1 láûp thaình mäüt cáúu truïc âaûi säú Boole. ∀x,y ∈ B thç: x + y ∈ B, x.y ∈ B thoía maîn 5 tiãn âãö sau: 2.1.1.1. Tiãn âãö giao hoaïn ∀x,y ∈ B: x + y = y + x 2.1.1.2. Tiãn âãö phäúi håüp ∀x,y,z ∈ B: (x + y) + z = x + ( y + z ) = x + y + z (x. y).z = x.(y. z) = x.y.z 2.1.1.3. Tiãn âãö phán bố ∀x,y,z ∈ B: x.(y + z ) = x.y + x.z x + (y.z) = (x + y)(x + z) 2.1.1.4. Tiãn âãö vãö pháön tæí trung hoìa Trong táûp B täön taûi hai pháön tæí trung hoìa, âoï laì pháön tæí âån vë vaì pháön tæí kh, pháön tæí âån vë kyï hiãûu laì 1, pháön tæí 0 kyï hiãûu laì 0. ∀x ∈ B: x + 1 = 1 x . 1 = x x + 0 = x x . 0 = 0 2.1.1.5. Tiãn âãö vãö pháön tæí buì ∀x ∈ B, bao giåì cuîng täön taûi pháön tæí buì tæång æïng sao cho luän thoía maîn: x + x = 0
Chæång 2. Âaûi säú BOOLE Trang 13 x. x = 0 Nãúu B = B* = {0, 1} vaì thoía maîn 5 tiãn âãö trãn thç cuîng láûp thaình cáúu truïc âaûi säú Boole nhæng laì cáúu truïc âaûi säú Boole nhoí nháút. 2.1.2. Caïc âënh lyï 2.1.2.1 Váún âãö âäúi ngáùu trong âaûi säú Boole Hai mãûnh âãö (hai biãøu thæïc, hai âënh lyï) âæåüc goüi laì âäúi ngáùu våïi nhau nãúu trong mãûnh âãö naìy ngæåìi ta thay pheïp toaïn cäüng thaình pheïp toaïn nhán vaì ngæåüc laûi,thay 0 bàòng 1 vaì ngæåüc laûi thç seî suy ra âæåüc mãûnh âãö kia. Khi hai mãûnh âãö âäúi ngáùu våïi nhau, nãúu 1 trong 2 mãûnh âãö âæåüc chæïng minh laì âuïng thç mãûnh âãö coìn laûi laì âuïng. Vê duû: x.(y + z ) = ( x. y) + ( x. z ) x + (y. z ) = ( x + y )( x + z ) Vê duû: x + x = 1 x. x = 0 2.1.2.2. Caïc âënh lyï a. Âënh lyï vãö pháön tæí buì laì duy nháút ∀x, y ∈ B: x + y = 1⎫ ⎬ ⇒ y = x x.y = 0 ⎭ ∀x ∈ B: x + x +. . . . . + x = x x. x. x. . . . . . x = x b. Âënh lyï De Morgan ∀x, y, z ∈ B, ta coï: x + y + z = x.y.z x.y.z = x + y + z ∀x ∈ B, ta coï: x = x ∀x, y, z ∈ B, ta coï:
Baìi giaíng Kyî Thuáût Säú Trang 14 x + y + z = x + y + z = x.y.z x. y. z = x.y.z =x + y + z ∀x, y ∈ B, ta coï: x. (x + y) = x.y x + (x . y) = x + y ∀x, y ∈ B, ta coï: x + x. y = x x.(x + y) = x Våïi 0, 1 ∈ B, ta coï: 0 = 1 vaì 1 = 0 2.2. HAÌM BOOLE VAÌ CAÏC PHÆÅNG PHAÏP BIÃØU DIÃÙN 2.2.1. Haìm Boole 2.2.1.1. Âënh nghéa Haìm Boole laì mäüt aïnh xaû Boole tæì âaûi säú Boole vaìo chênh noï. Tæïc laì ∀x, y ∈ B âæåüc goüi laì biãún Boole thç haìm Boole, kyï hiãûu laì f, âæåüc hçnh thaình trãn cå såí liãn kãút caïc biãún Boole bàòng caïc pheïp toaïn + (cäüng logic ), x (nhán logic ), hoàûc nghëch âaío logic (-). Haìm Boole âån giaín nháút laì haìm Boole theo 1 biãún Boole. Kyï hiãûu: f(x) = x f(x) = x f(x) = α (α: laì hàòng säú ) Trong træåìng håüp täøng quaït, ta coï haìm Boole theo n biãún Boole âæåüc kyï hiãûu nhæ sau: f(x1, x2,. . . . . ., xn ) 2.2.1.2. Caïc tênh cháút cuía haìm Boole Nãúu f(x1, x2, , xn) laì mäüt haìm Boole thç: + α.f(x1, x2, , xn) cuîng laì mäüt haìm Boole. + f (x1, x2, , xn) cuîng laì mäüt haìm Boole. Nãúu f1(x1, x2, , xn) vaì f2(x1, x2, , xn) laì nhæîng haìm Boole thç: + f1(x1, x2, , xn) + f2(x1, x2, , xn) cuîng laì mäüt haìm Boole. + f1(x1, x2, , xn).f2(x1, x2, , xn) cuîng laì mäüt haìm Boole.
Chæång 2. Âaûi säú BOOLE Trang 15 Váûy, mäüt haìm Boole f cuîng âæåüc hçnh thaình trãn cå såí liãn kãút caïc haìm Boole bàòng caïc pheïp toaïn + (cäüng logic), x (nhán logic) hoàûc nghëch âaío logic (-). 2.2.1.3. Giaï trë cuía haìm Boole Goüi f (x1, x2, , xn) laì mäüt haìm Boole theo biãún Boole. Trong f ngæåìi ta thay caïc biãún xi bàòng caïc giaï trë cuû thãø αi (i = 1, n ) thç haìm f (α1, α2, α3, , αn) âæåüc goüi laì giaï trë cuía haìm Boole theo n biãún. Vê duû: Xeït haìm f(x1, x2 ) = x1 + x2 Xeït B = B* ={0,1} x1 x2 f(x1, x2) ⇒ Nãúu x1 = x2 =0 f(0,0) = 0 0 0 0 ⇒ Nãúu x1 = 0, x2 = 1 f(0,1) = 1 0 1 1 ⇒ Nãúu x1 = 1, x2 = 0 f(1,0) = 1 1 0 1 ⇒ Nãúu x1 = 1, x2 = 1 f(1,1) = 1 1 1 1 Ta láûp âæåüc baíng giaï trë cuía haìm trãn. Vê duû: f (x1, x2, x3 ) = x1 + x2.x3 Xeït B = B* = {0,1 } Baíng giaï trë cuía haìm: x1 x2 x3 f (x1, x2, x3) 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1
Baìi giaíng Kyî Thuáût Säú Trang 16 2.2.2. Caïc phæång phaïp biãøu diãùn haìm Boole 2.2.2.1. Phæång phaïp baíng Laì phæång phaïp thæåìng duìng âãø biãøu diãùn haìm säú noïi chung. Phæång phaïp naìy gäöm mäüt baíng âæåüc chia laìm hai pháön: - Mäüt pháön daình cho biãún âãø ghi caïc täø håüp giaï trë coï thãø coï cuía biãún. - Mäüt pháön daình cho haìm âãø ghi caïc giaï trë cuía haìm ra tæång æïng våïi caïc täø håüp cuía caïc biãún vaìo. 2.2.2.2. Phæång phaïp giaíi têch Laì phæång phaïp biãøu diãùn haìm Boole dæåïi daûng täøng caïc têch säú, hoàûc dæåïi daûng têch cuía caïc täøng säú. Daûng täøng cuía caïc têch säú goüi laì daûng chênh tàõc thæï nháút, coìn daûng têch cuía caïc täøng laì daûng chênh tàõc thæï hai cuía haìm Boole, vaì hai daûng chênh tàõc naìy laì âäúi ngáùu nhau. a. Daûng chênh tàõc 1(Daûng täøng cuía caïc têch säú) Xeït caïc haìm Boole âån giaín sau âáy: f(x) = x, f(x) = x , f(x) = α. Xeït f(x) = x: Ta coï: x =0. x + 1. x màût khaïc: ⎧f()1 = 1 f()x = x ⇒ ⎨ ⎩f()0 = 0 suy ra f(x) = x coï thãø biãøøu diãùn: f(x) = x = f(0). x + f (1).x trong âoï: f (0), f (1) âæåüc goüi laì giaï trë cuía haìm Boole theo mäüt biãún. Xeït f(x) = x : Ta coï: x = 1. x + 0. x Màût khaïc: ⎧f ()1 = 0 f()x = x ⇒ ⎨ ⎩f ()0 = 1 Suy ra: f(x) = x coï thãø biãøu diãùn: f(x) = x = f(0). x + f(1).x
Chæång 2. Âaûi säú BOOLE Trang 17 Xeït f(x) = α: Ta coï: α = α.1 = α(x + x ) = x .α + α.x Màût khaïc: ⎧f()1 = α f()x = α ⇒ ⎨ ⎩f()0 = α Suy ra f(x) = α coï thãø âæåüc biãøu diãùn: f(x) = α = f(0). x + f(1).x Kãút luáûn: Duì laì f(x) = x, f(x) = x hay f(x) = α, ta âãöu coï daûng: f(x) = f(0).x + f(1).x Váûy f(x) = f(0).x + f(1).x trong âoï f (0), f (1) âæåüc goüi laì giaï trë cuía haìm Boole theo mäüt biãún, âæåüc goüi laì daûng chênh tàõc thæï nháút (daûng täøng cuía caïc têch) theo mäüt biãún. Trong træåìng håüp hai biãún f(x1, x2) thç caïch biãøu diãùn cuîng hoaìn toaìn dæûa trãn caïch biãøu diãùn cuía daûng chênh tàõc thæï nháút theo 1 biãún (trong âoï xem mäüt biãún laì hàòng säú). Ta coï: f(x1, x2 ) = f(0, x2). x 1 + f(1,x2).x1 maì: f(0, x2) = f(0,0 ). x 2 + f(0,1).x2 vaì: f(1, x2) = f(1,0). x 2 + f(1,1). x2 Suy ra: f(x1, x2 ) = f(0,0) x 1 x 2 + f(0, 1) x 1x2 + f(1,0 )x1 x 2 + f(1,1)x1x2 2 2 −1 α1 α2 Váûy: f (x1, x2) = ∑ f(α1,α2 )x1 x 2 e=0 trong âoï e laì säú tháûp phán tæång æïng våïi maî (α1, α2) vaì: x nãúu α = 1 α1 1 1 x1 = x 1 nãúu α1 = 0 x2 nãúu α2 = 1 α 2 x 2 = x 2 nãúu α2 = 0
Baìi giaíng Kyî Thuáût Säú Trang 18 Täøng quaït cho n biãún: 2n −1 α1 α2 αn f(x1, x2, , xn) = ∑f(α1,α2 , ,αn )x1 x 2 x n e=0 trong âoï e laì säú tháûp phán tæång æïng våïi maî nhë phán (α1, α2, , αn); vaì: α i xi nãúu αi = 1 x i = x i nãúu αi = 0 Vê duû: 23 −1 α1 α2 α3 f(x1, x2, x3) = ∑ f (α1, α2, α3). x1 . x2 . x3 e=0 f(x1, x2, x3) = f(0,0,0)x 1 x 2 x 3 + f(0,0,1)x 1 x 2 x3 + f(0,1,0)x 1x2 x 3 + f(0,1,1)x 1 x2 x3 + f(1,0,0) x1 x 2 x 3 + f(1,0,1)x1 x 2 x3 + f(1,1,0) x1 x2 x 3 + f(1,1,1) x1 x2 x3 Váûy daûng chênh tàõc thæï nháút laì daûng täøng cuía caïc têch maì trong mäùi têch säú chæïa âáöy âuí caïc biãún Boole dæåïi daûng tháût hoàûc daûng buì (nghëch âaío). b. Daûng chênh tàõc 2 (têch cuía caïc täøng): Âáy laì daûng âäúi ngáùu cuía daûng chênh tàõc 1 nãn biãøu thæïc täøng quaït cuía daûng chênh tàõc thæï hai cho n biãún laì: 2n−1 α1 α2 αn f(x1, x2, , xn) = ∏ [f(α1, α2, α3) + x1 + x2 + + xn )] e=0 trong âoï e laì säú tháûp phán tæång æïng cuía maî nhë phán (α1, α2, , αn); vaì: x nãúu α = 1 α i i i x i = xi nãúu αi = 0 Vê duû: f(x1,x2)=[f(0,0)+x1+x2][f(0,1)+x1+x 2][f(1,0)+x 1+x2][f(1,1)+x 1+x 2]
Chæång 2. Âaûi säú BOOLE Trang 19 f(x1, x2, x3) = [f(0,0,0)+x1+ x2+x3].[f(0,0,1)+x1+x2+x 3]. [f(0,1,0)+x1+x 2+x3].[f(0,1,1)+x1+x 2+x 3]. [f(1,0,0)+x 1+x2+x3].[f(1,0,1)+x 1+x2+x 3]. [f(1,1,0)+x 1+x 2+x3].[f(1,1,1)+x 1+x 2+x 3] Váûy, daûng chênh tàõc thæï hai laì daûng têch cuía caïc täøng säú maì trong âoï mäùi täøng säú naìy chæïa âáöy âuí caïc biãún Boole dæåïi daûng tháût hoàûc daûng buì. Chuï yï: Xeït vê duû 1: f(x1, x2) = x1 + x2 , Viãút dæåïi daûng chênh tàõc 1: f(x1, x2 ) = 0.x 1 x 2 + 1.x 1.x2 + 1.x1.x 2 + 1.x1.x2 = x 1.x2 + x1.x 2 + x1.x2 Tæì vê duû trãn ta tháúy: Daûng chênh tàõc thæï nháút laì daûng liãût kã táút caí caïc täø håüp nhë phán caïc biãún vaìo sao cho tæång æïng våïi nhæîng täø håüp âoï giaï trë cuía haìm ra bàòng 1. Khi liãût kã nãúu biãún tæång æïng bàòng 1 âæåüc viãút åí daûng tháût (x), vaì biãún tæång æïng bàòng 0 âæåüc viãút åí daûng buì (x ). Xeït vê duû 2: f(x1, x2, x3) = x1 + x2.x3 Viãút dæåïi daûng chênh tàõc 2: f(x1, x2, x3) = [0+x1+x2+x3].[0+x1+x2+x 3].[0+x1+x 2+x3]. [1+x1+x 2+x 3].[1+x 1+x2+x3].[1+x 1+x2+x 3]. [1+x 1+x 2+x3].[1+x 1+x 2+x 3] Hay: f(x1, x2, x3) = x1 + x2.x3 = [x1+x2+x3].[x1+x2+x 3].[x1+x 2+x3] Váûy, daûng chênh tàõc thæï hai laì daûng liãût kã táút caí caïc täø håüp nhë phán caïc biãún vaìo sao cho tæång æïng våïi nhæîng täø håüp âoï giaï trë cuía haìm ra bàòng 0. Khi liãût kã nãúu biãún tæång æïng bàòng 0 âæåüc viãút åí daûng tháût (x), vaì biãún tæång æïng bàòng 1 âæåüc viãút åí daûng buì (x ). Xeït vê duû âån giaín sau âãø hiãøu roî hån vãö caïch thaình láûp baíng giaï trë cuía haìm, tçm haìm maûch vaì thiãút kãú maûch: Haîy thiãút kãú maûch âiãûn sao
Baìi giaíng Kyî Thuáût Säú Trang 20 cho khi cäng tàõc 1 âoïng thç âeìn âoí, cäng tàõc 2 âoïng âeìn âoí, caí hai cäng tàõc âoïng âeìn âoí. Giaíi Ta qui âënh: - Cäng tàõc håí : 0 Âeìn tàõt : 0 - Cäng tàõc âoïng : 1 Âeìn âoí : 1 Luïc âoï ta coï baíng traûng thaïi mä taí hoaût âäüng cuía maûch: Cäng tàõc 1 Cäng tàõc 2 Âeìn x1 x2 f(x1,x2) 0 0 0 0 1 1 1 0 1 1 1 1 Viãút theo daûng chênh tàõc 1 ta coï: f(x1, x2) = 0.x 1 x 2 + 1.x 1.x2 + 1.x1.x 2 + 1.x1.x2 = x 1. x2 + x1.x 2 + x1.x2 = x 1. x2 + x1(x 2 + x2) = x 1. x2 + x1 = x1 + x2 Viãút theo daûng chênh tàõc 2 ta coï: f(x1, x2) = [0+x1+x2].[1+x1+x 2].[1+x 1+ x2].[1+x 1+x 2] = [x1+ x2].1.1.1 = x1 + x2 Váûy, duì viãút theo daûng chênh tàõc 1 hay chênh tàõc 2 ta âãöu coï haìm maûch: f(x1, x2) = x1 + x2 2.2.2.3. Phæång phaïp biãøu diãùn bàòng baíng Karnaugh Âáy laì caïch biãøu diãùn laûi cuía phæång phaïp baíng dæåïi daûng baíng gäöm caïc ä vuäng coï daûng nhæ hçnh bãn.
Chæång 2. Âaûi säú BOOLE Trang 21 Trãn baíng naìy ngæåìi ta bäú trê caïc biãún vaìo theo haìng hoàûc theo cäüt cuía baíng. Trong træåìng håüp säú læåüng biãún vaìo laì chàôn, ngæåìi ta bäú trê säú læåüng biãún vaìo theo haìng ngang bàòng säú læåüng biãún vaìo theo cäüt doüc cuía baíng. Trong træåìng håüp säú læåüng biãún vaìo laì leí, ngæåìi ta bäú trê säú læåüng biãún vaìo theo haìng ngang nhiãöu hån säú læåüng biãún vaìo theo cäüt doüc 1 biãún hoàûc ngæåüc laûi. Caïc täø håüp giaï trë cuía biãún vaìo theo haìng ngang hoàûc theo cäüt doüc cuía baíng âæåüc bäú trê sao cho khi ta âi tæì mäüt ä sang mäüt ä lán cáûn våïi noï chè laìm thay âäøi mäüt giaï trë cuía biãún, nhæ váûy thæï tæ û bäú trê hay sàõp xãúp caïc täø håüp giaï trë cuía biãún vaìo theo haìng ngang hoàûc theo cäüt doüc cuía baíng Karnaugh hoaìn toaìn tuán thuí theo maî Gray. Giaï trë ghi trong mäùi ä vuäng naìy chênh laì giaï trë cuía haìm ra tæång æïng våïi caïc täø håüp giaï trë cuía biãún vaìo. ÅÍ nhæîng ä maì giaï trë haìm laì khäng xaïc âënh, coï nghéa laì giaï trë cuía haìm laì tuìy yï (hay tuìy âënh), ngæåìi ta kê hiãûu bàòng chæî x. Nãúu coï n biãún vaìo seî coï 2n ä vuäng. 2.3. TÄÚI THIÃØU HAÌM BOOLE 2.3.1. Âaûi cæång Trong thiãút bë maïy tênh ngæåìi ta thæåìng thiãút kãú gäöm nhiãöu modul (kháu) vaì mäùi modul naìy âæåüc âàûc træng bàòng mäüt phæång trçnh logic. Trong âoï, mæïc âäü phæïc taûp cuía så âäö tuìy thuäüc vaìo phæång trçnh logic biãøu diãùn chuïng. Viãûc âaût âæåüc âäü äøn âënh cao hay khäng laì tuìy thuäüc vaìo phæång trçnh logic biãøu diãùn chuïng åí daûng täúi thiãøu hoïa hay chæa. Âãø thæûc hiãûn âæåüc âiãöu âoï, khi thiãút kãú maûch säú ngæåìi ta âàût ra váún âãö täúi thiãøu hoïa caïc haìm logic. Âiãöu âoï coï nghéa laì phæång trçnh logic biãøu diãùn sao cho thæûc sæû goün nháút (säú læåüng caïc pheïp tênh vaì säú læåüng caïc säú âæåüc biãøu diãùn dæåïi daûng tháût hoàûc buì laì êt nháút). Tuy nhiãn trong thæûc tãú, khäng phaíi luïc naìo cuîng âaût âæåüc låìi giaíi täúi æu cho baìi toaïn täúi thiãøu hoïa.
Baìi giaíng Kyî Thuáût Säú Trang 22 2.3.2. Caïc bæåïc tiãún haình täúi thiãøu hoïa - Duìng caïc pheïp täúi thiãøu âãø täúi thiãøu hoïa caïc haìm säú logic. - Ruït ra nhæîng thæìa säú chung nhàòm muûc âêch täúi thiãøu hoïa thãm mäüt bæåïc næîa caïc phæång trçnh logic. 2.3.3. Caïc phæång phaïp täúi thiãøu hoïa 2.3.3.1. Phæång phaïp giaíi têch Âoï laì phæång phaïp täúi thiãøu hoïa haìm Boole (phæång trçnh logic) dæûa vaìo caïc tiãn âãö, âënh lyï cuía âaûi säú Boole. Vê duû: f(x1, x2) = x 1x2 + x1 x 2 + x1x2 = (x 1 + x1)x2 + x1 x 2 = x2 + x1 x 2 = x2 + x1 Vê duû: f(x1, x2, x3) = x 1x2x3 + x1 x 2 x 3 + x1 x 2x3 + x1x2 x 3 + x1x2x3 = x 1x2x3 + x1 x 2 x 3 + x1 x 2x3 + x1x2 (x 3 + x3) = x 1x2x3 + x1 x 2(x 3 + x3) + x1x2 = x 1x2x3 + x1(x 2 + x2) = x 1x2x3 + x1 = x1 + x2 x3 2.3.3.2. Phæång phaïp baíng Karnaugh a. Täúi thiãøu hoïa haìm Boole bàòng baíng Karnaugh Âãø täúi thiãøu hoïa haìm Boole bàòng phæång phaïp baíng Karnaugh phaíi tuán thuí theo qui tàõc vãö ä kãú cáûn: “Hai ä âæåüc goüi laì kãú cáûn nhau laì hai ä maì khi ta tæì ä naìy sang ä kia chè laìm thay âäøi giaï trë cuía 1 biãún. “ Quy tàõc chung cuía phæång phaïp ruït goün bàòng baíng Karnaugh laì gom (kãút håüp) caïc ä kãú cáûn laûi våïi nhau. Khi gom 2 ä kãú cáûn nhau seî loaûi âæåüc 1 biãún (2 ä =21 loaûi 1 biãún). Khi gom 4 ä kãú cáûn seî loaûi âæåüc 2 biãún (4 ä =22 loaûi 2 biãún). Khi gom 8 ä kãú cáûn seî loaûi âæåüc 3 biãún (8 ä = 23 loaûi 3 biãún ). Täøng quaït, khi gom 2n ä kãú cáûn seî loaûi âæåüc n biãún. Nhæîng biãún bë loaûi laì nhæîng biãún khi ta âi voìng qua caïc ä kãú cáûn maì giaï trë cuía chuïng thay âäøi.
Chæång 2. Âaûi säú BOOLE Trang 23 Nhæîng âiãöu cáön læu y:ï - Voìng gom âæåüc goüi laì håüp lãû khi trong voìng gom âoï coï êt nháút 1 ä chæa thuäüc voìng gom naìo. - Viãûc kãút håüp nhæîng ä kãú cáûn våïi nhau coìn tuìy thuäüc vaìo phæång phaïp biãøu diãùîn haìm Boole theo daûng chênh tàõc 1 hoàûc chênh tàõc 2. Âiãöu naìy coï nghéa laì: nãúu ta biãøu diãùn haìm Boole theo daûng chênh tàõc 1 thç ta chè quan tám nhæîng ä kãú cáûn naìo coï giaï trë bàòng 1 vaì tuìy âënh, ngæåüc laûi nãúu ta biãøu diãùn haìm Boole dæåïi daûng chênh tàõc 2 thç ta chè quan tám nhæîng ä kãú cáûn naìo coï giaï trë bàòng 0 vaì tuìy âënh. Ta quan tám nhæîng ä tuìy âënh sao cho nhæîng ä naìy kãút håüp våïi nhæîng ä coï giaï trë bàòng 1 (nãúu biãøu diãùn theo daûng chênh tàõc 1) hoàûc bàòng 0 (nãúu biãøu diãùn theo daûng chênh tàõc 2) seî laìm cho säú læåüng ä kãú cáûn laì 2n låïn nháút. - Caïc ä kãú cáûn muäún gom âæåüc phaíi laì kãú cáûn voìng troìn nghéa laì ä kãú cáûûn cuäúi cuîng laì ä kãú cáûn âáöu tiãn. c. Caïc vê duû Vê duû 1: Täúi thiãøu hoïa haìm sau bàòng phæång phaïp baíng Karnaugh. f(x ,x ) 1 2 x x 1 2 0 1 Täúi thiãøu hoïa theo daûng chênh tàõc 2: 0 0 1 1 1 1 f(x1,x2) = x1 + x2 Vê duû 2: Täúi thiãøu hoïa haìm sau bàòng phæång phaïp baíng Karnaugh. f(x ,x ,x ) 1 2 3 Voìng gom 1: x x1,x2 1 x3 00 01 11 10 0 0 0 1 1 Voìng gom 2: x2.x3 1 0 1 1 1 Täúi giaín theo daûng chênh tàõc 1: Ta chè quan tám âãún nhæîng ä coï giaï trë bàòng 1 vaì tuìy âënh, nhæ váûy seî coï 2 voìng gom âãø phuí hãút caïc ä coï giaï trë bàòng 1: voìng gom 1 gäöm 4 ä kãú cáûn, vaì voìng gom 2 gäöm 2 ä kãú cáûn (hçnh veî).
Baìi giaíng Kyî Thuáût Säú Trang 24 Âäúi våïi voìng gom 1: Coï 4 ä = 22 nãn seî loaûi âæåüc 2 biãún. Khi âi voìng qua 4 ä kãú cáûn trong voìng gom chè coï giaï trë cuía biãún x1 khäng âäøi (luän bàòng 1), coìn giaï trë cuía biãún x2 thay âäøi (tæì 1→0) vaì giaï trë cuía biãún x3 thay âäøi (tæì 0→1) nãn caïc biãún x2 vaì x3 bë loaûi, chè coìn laûi biãún x1 trong kãút quaí cuía voìng gom 1. Vç x1=1 nãn kãút quaí cuía voìng gom 1 theo daûng chênh tàõc 1 seî coï x1 viãút åí daûng tháût: x1 Âäúi våïi voìng gom 2: Coï 2 ä = 21 nãn seî loaûi âæåüc 1 biãún. Khi âi voìng qua 2 ä kãú cáûn trong voìng gom giaï trë cuía biãún x2 vaì x3 khäng âäøi, coìn giaï trë cuía biãún x1 thay âäøi (tæì 0→1) nãn caïc biãún x2 vaì x3 âæåüc giæî laûi, chè coï biãún x1 bë loaûi. Vç x2=1 vaì x3=1 nãn kãút quaí cuía voìng gom 2 theo daûng chênh tàõc 1 seî coï x2 vaì x3 viãút åí daûng tháût: x2.x3 Kãút håüp 2 voìng gom ta coï kãút quaí täúi giaín theo daûng chênh tàõc 1: f(x1, x2, x3) = x1 + x2.x3 Täúi giaín theo daûng chênh tàõc 2: Ta quan tám âãún nhæîng ä coï giaï trë bàòng 0 vaì tuìy âënh, nhæ váûy cuîng coï 2 voìng gom (hçnh veî), mäùi voìng gom âãöu gäöm 2 ä kãú cáûn. Âäúi våïi voìng gom 1: Coï 2 ä = 21 nãn loaûi âæåüc 1 biãún, biãún bë loaûi laì x2 (vç coï giaï trë thay âäøi tæì 0→1). Vç x1=0 vaì x3=0 nãn kãút quaí cuía voìng gom 1 theo daûng chênh tàõc 2 seî coï x1 vaì x3 åí daûng tháût: x1+ x3. Âäúi våïi voìng gom 2: Coï 2 ä = 21 nãn loaûi âæåüc 1 biãún, biãún bë loaûi laì x3 (vç coï giaï trë thay âäøi tæì 0 → 1). Vç x1=0 vaì x2=0 nãn kãút quaí cuía voìng gom 2 theo daûng chênh tàõc 2 seî coï x1 vaì x2 åí daûng tháût: x1 + x2. f(x1,x2,x3) x1,x2 Voìng gom 1: x1 + x3 x3 00 01 11 10 0 0 0 1 1 Voìng gom 2: x + x 1 0 1 1 1 1 2 Kãút håüp 2 voìng gom coï kãút quaí cuía haìm f viãút theo daûng chênh tàõc 2: f (x1, x2, x3) = (x1+x3).(x1+x2) = x1.x1 + x1.x2 + x1.x3 + x2.x3 = x1 + x1.x2 + x1.x3 + x2.x3
Chæång 2. Âaûi säú BOOLE Trang 25 = x1(1+ x2 + x3) + x2.x3 = x1 + x2.x3 Nháûn xeït: Trong vê duû naìy, haìm ra viãút theo daûng chênh tàõc 1 vaì haìm ra viãút theo daûng chênh tàõc 2 laì giäúng nhau. Tuy nhiãn coï træåìng håüp haìm ra cuía hai daûng chênh tàõc 1 vaì 2 laì khaïc nhau, nhæng giaï trë cuía haìm ra æïng våïi mäüt täø håüp biãún âáöu vaìo laì giäúng nhau trong caí 2 daûng chênh tàõc. Chuï yï: Ngæåìi ta thæåìng cho haìm Boole dæåïi daûng biãøu thæïc ruït goün. Vç coï 2 caïch biãøu diãùn haìm Boole theo daûng chênh tàõc 1 hoàûc 2 nãn seî coï 2 caïch cho giaï trë cuía haìm Boole æïng våïi 2 daûng chênh tàõc âoï: Daûng chênh tàõc 1: Täøng caïc têch säú. f(x1, x2, x3) = Σ(3, 4, 7) + d(5, 6) Trong âoï d: giaï trë caïc ä naìy laì tuìy âënh (d: don’t care) f(x1,x2,x3) x1,x2 x 3 00 01 11 10 0 00X1 1 011X Luïc âoï baíng Karnaugh seî âæåüc cho nhæ hçnh trãn. Tæì biãøu thæïc ruït goün cuía haìm ta tháúy taûi caïc ä æïng våïi täø håüp nhë phán caïc biãún vaìo coï giaï trë laì 3, 4, 7 thç haìm ra coï giaï trë bàòng 1; taûi caïc ä æïng våïi täø håüp nhë phán caïc biãún vaìo coï giaï trë laì 5,6 thç haìm ra coï giaï trë laì tuìy âënh; haìm ra coï giaï trë bàòng 0 åí nhæîng ä coìn laûi æïng våïi täø håüp caïc biãún vaìo coï giaï trë laì 0, 1, 2. Daûng chênh tàõc 2: Têch caïc täøng säú. Phæång trçnh logic trãn cuîng tæång âæång: f(x1, x2, x3) = Π(0, 1, 2) + d(5, 6)
Baìi giaíng Kyî Thuáût Säú Trang 26 Vê duû 3: Täúi thiãøu hoïa haìm 4 biãún sau âáy: f(x ,x ,x ,x ) f(x ,x ,x ,x ) 1 2 3 4 x ,x 1 2 3 4 x ,x 1 2 1 2 x3,x 4 00 01 11 10 x3,x4 00 01 11 10 00 x x 1 x 00 x x 1 x 01 x 0 1 x 01 x 0 1 x 11 0 x X 1 11 0 x x 1 10 1 1 X 1 10 1 1 x 1 Voìng gom 1 Voìng gom 2 Ta thæûc hiãûn täúi thiãøu hoïa theo daûng chênh tàõc 1: Tæì baín âäö Karnaugh ta coï 2 voìng gom, voìng gom 1 gäöm 8 ä kãú cáûn vaì voìng gom 2 gäöm 8 ä kãú cáûn. Kãút quaí täúi thiãøu hoïa nhæ sau: Voìng gom 1: x 4 Voìng gom 2: x1 Váûy: f(x1, x2, x3, x4) = x 4 + x1
Chæång 3. Caïc pháön tæí logic cå baín Trang 27 Chæång 3 CAÏC PHÁÖN TÆÍ LOGIC CÅ BAÍN 3.1. KHAÏI NIÃÛM VÃÖ MAÛCH SÄÚ 3.1.1. Maûch tæång tæû Maûch tæång tæû (coìn goüi laì maûch Analog) laì maûch duìng âãø xæí lyï caïc tên hiãûu tæång tæû. Tên hiãûu tæång tæû laì tên hiãûu coï biãn âäü biãún thiãn liãn tuûc theo thåìi gian. Viãûc xæí lyï bao gäöm caïc váún âãö: Chènh læu, khuãúch âaûi, âiãöu chãú, taïch soïng. Nhæåüc âiãøm cuía maûch tæång tæû : - Âäü chäúng nhiãùu tháúp (nhiãùu dãù xám nháûp). - Phán têch thiãút kãú maûch phæïc taûp. Âãø khàõc phuûc nhæîîng nhæåüc âiãøm naìy ngæåìi ta sæí duûng maûch säú. 3.1.2. Maûch säú Maûch säú (coìn goüi laì maûch Digital) laì maûch duìng âãø xæí lyïï tên hiãûu säú. Tên hiãûu säú laì tên hiãûu coï biãn âäü biãún thiãn khäng liãn tuûc theo thåìi gian hay coìn goüi laì tên hiãûu giaïn âoaûn, noï âæåüc biãøu diãùn dæåïi daûng soïng xung våïi 2 mæïc âiãûn thãú cao vaì tháúp maì tæång æïng våïi hai mæïc âiãûn thãú naìy laì hai mæïc logic cuía maûch säú. Viãûc xæí lyï åí âáy bao gäöm caïc váún âãö: - Loüc säú. - Âiãöu chãú säú /Giaíi âiãöu chãú säú. - Maî hoïa . . . . Æu âiãøm cuía maûch säú so våïi maûch tæång tæû : - Âäü chäúng nhiãùu cao (nhiãùu khoï xám nháûp). - Phán têch thiãút kãú machû säú tæång âäúi âån giaín. Vç váûy, hiãûn nay maûch säú âæåüc sæí duûng khaï phäø biãún trong táút caí caïc lénh væûc nhæ : Âo læåìng säú, truyãön hçnh säú, âiãöu khiãøn säú. . .
Baìi giaíng Kyî Thuáût Säú Trang 28 3.1.3. Hoü logic dæång/ám K Traûng thaïi logic cuía maûch säú coï thãø biãøu diãùn Â v bàòng maûch âiãûn âån giaín nhæ trãn hçnh 3.1: i - K Måí : Âeìn tàõt Hçnh 3.1 - K Âoïng: Âeìn saïng Traûng thaïi Âoïng/Måí cuía khoïa K hoàûc traûng thaïi Saïng/Tàõt cuía âeìn Â cuîng âæåüc âàûc træng cho traûng thaïi logic cuía maûch säú. Nãúu thay khoïa K bàòng khoïa âiãûn tæí duìng BJT nhæ trãn hçnh 3.2: +Vcc -Vcc Rc Rc v0 v0 RB vi RB Q vi Q a) b) Hçnh 3.2. Biãøu diãùn traûng thaïi logic cuía maûch säú bàòng khoïa âiãûn tæí duìng BJT Hçnh 3.2a: - Khi vi = 0 → BJT tàõt → v0 = +Vcc - Khi vi > 0 → BJT dáùn baîo hoìa → v0 = v ces = 0,2 (V). Hçnh 3.2b: - Khi vi = 0 → BJT tàõt → v0 = -Vcc Ics - Khi vi Vlogic 0 → hoü logic dæång Vlogic 1 = 5v ⎪⎫ ⎬ ⇒ Vlogic 1 〉Vlogic 0 : Logic dæång. Vlogic 0 = 0v⎭⎪
Chæång 3. Caïc pháön tæí logic cå baín Trang 29 - Choün : Vlogic 1 < Vlogic 0 → hoü logic ám Vlogic 1 = - 5v ⎪⎫ ⎬ ⇒ Vlogic 1 〈Vlogic 0 : Logic ám. Vlogic 0 = - 0,2v⎭⎪ Logic dæång vaì logic ám laì nhæîng hoü logic toí, ngoaìi ra coìn nhæîng hoü logic måì. 3.2. CÄØNG LOGIC 3.2.1. Khaïi niãûm Cäøng logic laì mäüt trong caïc thaình pháön cå baín âãø xáy dæûng maûch säú. Noï âæåüc thiãút kãú trãn cå såí caïc pháön tæí linh kiãûn baïn dáùn nhæ Diode, BJT, FET âãø hoaût âäüng theo baíng traûng thaïi cho træåïc. 3.2.2 Phán loaûi Coï ba caïch phán loaûi cäøng logic: - Phán loaûi cäøng theo chæïc nàng. - Phán loaûi cäøng theo phæång phaïp chãú taûo. - Phán loaûi cäøng theo ngoî ra. 3.2.2.1. Phán loaûi cäøng theo chæïc nàng a. Cäøng khäng âaío (BUFFER) Cäøng khäng âaío hay coìn goüi laì cäøng âãûm (BUFFER) laì cäøng coï mäüt ngoî vaìo vaì mäüt ngoî ra våïi kyï hiãûu vaì baíng traûng thaïi hoaût âäüng nhæ hçnh veî. +Baíng traûng thaïi: x y x y 0 0 11 Hçnh 3.3. Kyï hiãûu vaì baíng traûng thaïi cuía cäøng khäng âaío Phæång trçnh logic mä taí hoaût âäüng cuía cäøng: y = x
Baìi giaíng Kyî Thuáût Säú Trang 30 Trong âoï: - Våïi x laì ngoî vaìo coï tråí khaïng vaìo Zv vä cuìng låïn → do âoï cäøng khäng âaío (hay cäøng âãûm) khäng coï khaí nàng huït doìng låïn åí ngoî vaìo. - Våïi ngoî ra y coï tråí khaïng ra Zra nhoí → cäøng âãûm coï khaí nàng cung cáúp doìng ngoî ra låïn. Chênh vç váûy ngæåìi ta sæí duûng cäøng khäng âaío giæî vai troì, chæïc nàng laì cäøng âãûm theo 2 yï nghéa sau: - Duìng âãø phäúi håüp tråí khaïng. - Duìng âãø caïch ly vaì náng doìng cho taíi. b.Cäøng âaío (NOT) Cäøng ÂAÍO (coìn goüi laì cäøng NOT) laì cäøng logic coï 1 ngoî vaìo vaì 1 ngoî ra, våïi kyï hiãûu vaì baíng traûng thaïi hoaût âäüng nhæ hçnh veî: Baíng traûng thaïi: x y x y 0 1 10 Hçnh 3.4. Kyï hiãûu vaì baíng traûng thaïi cäøng ÂAÍO Phæång trçnh logic mä taí hoaût âäüng cuía cäøng ÂAÍO: y = x Cäøng âaío giæî chæïc nàng nhæ mäüt cäøng âãûm, nhæng ngæåìi ta goüi laì âãûm âaío vç tên hiãûu ngoî ra ngæåüc pha våïi tên hiãûu ngoî vaìo. Gheïp hai cäøng âaío ta âæåüc cäøng khäng âaío (hçnh 3.5): x xx x = x Hçnh 3.5. Sæí duûng 2 cäøng ÂAÍO taûo ra cäøng ÂÃÛM
Chæång 3. Caïc pháön tæí logic cå baín Trang 31 c. Cäøng VAÌì (AND) Cäøng AND laì cäøng logic thæûc hiãûn chæïc nàng cuía pheïp toaïn nhán logic våïi 2 ngoî vaìo vaì 1 ngoî ra kyï hiãûu nhæ hçnh veî: Phæång trçnh logic mä taí hoaût âäüng cuía cäøng AND: y = x1.x2 Baíng traûng thaïi hoaût âäüng cuía cäøng AND 2 ngoî vaìo: x1 x1 x2 y y 0 0 0 x2 0 1 0 1 0 0 Hçnh 3.6. Cäøng AND 1 1 1 Tæì baíng traûng thaïi naìy ta coï nháûn xeït: Ngoî ra y chè bàòng 1 (mæïc logic 1) khi caí 2 ngoî vaìo âãöu bàòng 1, ngoî ra y bàòng 0 (mæïc logic 0) khi coï mäüt ngoî vaìo báút kyì (x1 hoàûc x2) åí mæïc logic 0. Xeït træåìng håüp täøng quaït cho cäøng AND coï n ngoî vaìo x1, x2 xn: ⎧0 ∃xi = 0 yAND= ⎨ ⎩1 ∀xi = 1 (i = 1,n) x Váûy, âàûc âiãøm cuía cäøng AND laì: ngoî 1 y ra y chè bàòng 1 khi táút caí caïc ngoî vaìo x âãöu bàòng 1, ngoî ra y bàòng 0 khi coï êt n nháút mäüt ngoî vaìo bàòng 0. Hçnh 3.7. Cäøng AND våïi n ngoî vaìo Sæí duûng cäøng AND âãø âoïng måí tên hiãûu: Xeït cäøng AND coï hai ngoî vaìo x1 vaì x2. Ta choün: - x1 âoïng vai troì ngoî vaìo âiãöu khiãøn (control). - x2 âoïng vai troì ngoî vaìo dæî liãûu (data). Xeït caïc træåìng håüp cuû thãø sau âáy: - x1= 0: → y = 0 báút cháúp traûng thaïi cuía x2, ta noïi cäøng AND khoïa laûi khäng cho dæî liãûu âæa vaìo ngoî vaìo x2 qua cäøng AND âãún ngoî ra.
Baìi giaíng Kyî Thuáût Säú Trang 32 ⎧x2 = 0 ⇒ y = 0 - x1 =1 ⎨ ⇒ y = x2 ⎩x2 = 1 ⇒ y = 1 Ta noïi cäøng AND måí cho dæî liãûu âæa vaìo ngoî vaìo x2 qua cäøng AND âãún ngoî ra. Sæí duûng cäøng AND âãø taûo ra cäøng logic khaïc: Nãúu ta sæí duûng 2 täø håüp âáöu vaì cuäúi trong baíng giaï trë cuía cäøng AND vaì näúi cäøng AND theo så âäö sau: x1 y +x = 0 → x1= x2= 0 → y = 0 x2 +x = 1 → x1= x2= 1 → y = 1 → y = x Hçnh 3.8. Sæí duûng cäøng AND taûo ra cäøng âãûm. thç chuïng ta coï thãø sæí duûng cäøng AND âãø taûo ra cäøng âãûm. Trong thæûc tãú, coï thãø táûn duûng hãút caïc cäøng chæa duìng trong IC âãø thæûc hiãûn chæïc nàng cuía caïc cäøng logic khaïc. d. Cäøng Hoàûc (OR) Laì cäøng thæûc hiãûn chæïc nàng cuía pheïp toaïn cäüng logic, cäøng OR coï 2 ngoî vaìo vaì 1 ngoî ra coï kyï hiãûu nhæ hçnh veî: x1 x1 y y x 2 x2 Kyï hiãûu Cháu Áu Kyï hiãûu theo Myî, Nháût, UÏc Hçnh 3.9. Cäøng OR 2 ngoî vaìo Phæång trçnh logic mä taí hoaût âäüng cuía cäøng OR: y = x1 + x2 Baíng traûng thaïi mä taí hoaût âäüng cuía cäøng OR:
Chæång 3. Caïc pháön tæí logic cå baín Trang 33 x1 x2 y 0 0 0 0 1 1 1 0 1 1 1 1 Xeït træåìng håüp täøng quaït âäúi våïi cäøng OR coï n ngoî vaìo. Phæång trçnh logic: x 1 y ⎧1 ∃x i = 1 yOR = ⎨ xn ⎩0 ∀x i = 0 (i = 1,n) Hçnh 3.9. Cäøng OR n ngoî vaìo Âàûc âiãøm cuía cäøng OR laì: Tên hiãûu ngoî ra chè bàòng 0 khi vaì chè khi táút caí caïc ngoî vaìo âãöu bàòng 0, ngæåüc laûi tên hiãûu ngoî ra bàòng 1 khi chè cáön coï êt nháút mäüt ngoî vaìo bàòng 1. Sæí duûng cäøng OR âãø âoïng måí tên hiãûu: Xeït cäøng OR coï 2 ngoî vaìo x1, x2. Nãúu choün x1 laì ngoî vaìo âiãöu khiãøn (control input), x2 ngoî vaìo dæî liãûu (data input), ta coï caïc træåìng håüp cuû thãø sau âáy: - x1= 1⇒ y = 1 (y luän bàòng 1 báút cháúp x2) → Ta noïi cäøng OR khoïa khäng cho dæî liãûu âi qua. ⎧x2 = 0 ⇒ y = 0 - x1= 0⇒ ⎨ ⇒ y = x2 → Cäøng OR måí cho dæî liãûu vaìo ⎩x2 = 1⇒ y = 1 ngoî vaìo x2. Sæí duûng cäøng OR âãø thæûc hiãûn chæïc nàng cäøng logic khaïc: Ta sæí duûng hai täø håüp giaï trë âáöu vaì cuäúi cuía baíng traûng thaïi cuía cäøng OR vaì näúi maûch cäøng OR nhæ sau: - x = 0, x1 = x2 = 0 ⇒ y = 0 - x = 1, x1 = x2 = 1 ⇒ y = 1 ⇒ y = x: cäøng OR âoïng vai troì cäøng âãûm. Så âäö maûch thæûc hiãûn trãn hçnh 3.10.
Baìi giaíng Kyî Thuáût Säú Trang 34 x x 1 y x2 Hçnh 3.10. Sæí duûng cäøng OR laìm cäøng âãûm e. Cäøng NAND Âáy laì cäøng thæûc hiãûn pheïp toaïn nhán âaío, vãö så âäö logic cäøng NAND gäöm 1 cäøng AND màõc näúi táöng våïi 1 cäøng NOT, kyï hiãûu vaì baíng traûng thaïi cäøng NAND âæåüc cho nhæ hçnh 3.11: x 1 y x1 x2 y x2 0 0 1 0 1 1 x1 y 1 0 1 x2 1 1 0 Hçnh 3.11. Cäøng NAND: Kyï hiãûu, så âäö logic tæång âæång vaì baíng traûng thaïi Phæång trçnh logic mä taí hoaût âäüng cuía cäøng NAND 2 ngoî vaìo: y = x1.x 2 Xeït træåìng håüp täøng quaït: Cäøng NAND coï n ngoî vaìo. 1 ∃x = 0 x ⎧ i 1 y yNAND = ⎨ ⎩0 ∀xi = 1 (i = 1,n) xn Hçnh 3.12.Cäøng NAND våïi n ngoî vaìo Váûy, âàûc âiãøm cuía cäøng NAND laì: tên hiãûu ngoî ra chè bàòng 0 khi táút caí caïc ngoî vaìo âãöu bàòng 1, vaì tên hiãûu ngoî ra seî bàòng 1 khi chè cáön êt nháút mäüt ngoî vaìo bàòng 0. Sæí duûng cäøng NAND âãø âoïng måí tên hiãûu: Xeït cäøng NAND coï hai ngoî vaìo, vaì choün x1 laì ngoî vaìo âiãöu khiãøn, x2 laì ngoî vaìo dæî liãûu. Khi: - x1= 0 ⇒ y = 1 (y luän bàòng 1 báút cháúp x2) → cäøng NAND khoïa
Chæång 3. Caïc pháön tæí logic cå baín Trang 35 ⎧x2 = 0 ⇒ y =1 - x1= 1 ⇒ ⎨ ⇒ y = x2 → Cäøng NAND måí cho dæî ⎩x2 =1⇒ y = 0 liãûu vaìo ngoî vaìo x2 vaì âãún ngoî ra Sæí duûng cäøng NAND âãø taûo caïc cäøng logic khaïc: - duìng cäøng NAND taûo cäøng NOT: x x 1 y x y x2 y = x1 x2 = x1 + x2 = x Hçnh 3.13a.Duìng cäøng NAND taûo cäøng NOT - duìng cäøng NAND taûo cäøng BUFFER (cäøng âãûm): x x1 x y x y x2 y = x = x Hçnh 3.13b.Duìng cäøng NAND taûo ra cäøng âãûm (BUFFER) - duìng cäøng NAND taûo cäøng AND: x x1 1 y x1.x2 y = x1 x2 = x1.x2 x x2 2 Hçnh 3.13c. Sæí duûng cäøng NAND taûo cäøng AND - duìng cäøng NAND taûo cäøng OR: x 1 x1 x y 1 y x2 x2 x2 y = x1.x2 = x1 + x2 = x1 + x2 Hçnh 3.13d. Sæí duûng cäøng NAND taûo ra cäøng OR
Baìi giaíng Kyî Thuáût Säú Trang 36 f. Cäøng Hoàûc - khäng (NOR) Laì cäøng thæûc hiãûn chæïc nàng cuía pheïp toaïn cäüng âaío logic, laì cäøng coï hai ngoî vaìo vaì mäüt ngoî ra coï kyï hiãûu nhæ hçnh veî: x 1 x y 1 y x2 x2 Kyï hiãûu Cháu Áu Kyï hiãûu theo Myî, Nháût, UÏc Hçnh 3.14. Kyï hiãûu cäøng NOR Phæång trçnh logic mä taí hoaût âäüng cuía cäøng : y = x1 + x 2 Baíng traûng thaïi mä taí hoaût âäüng cuía cäøng NOR : x1 x2 y 0 0 1 0 1 0 1 0 0 1 1 0 Xeït træåìng håüp täøng quaït cho cäøng x1 y NOR coï n ngoî vaìo. x ⎧0 ∃xi = 1 n yNOR= ⎨ Hçnh 3.15. Cäøng NOR n ngoî vaìo ⎩1 ∀xi = 0 (i = 1,n) Váûy âàûc âiãøm cuía cäøng NOR laì: Tên hiãûu ngoî ra chè bàòng 1 khi táút caí caïc ngoî vaìo âãöu bàòng 0, tên hiãûu ngoî ra seî bàòng 0 khi coï êt nháút mäüt ngoî vaìo bàòng 1. Sæí duûng cäøng NOR âãø âoïng måí tên hiãûu: Xeït cäøng NOR coï 2 ngoî vaìo, choün x1 laì ngoî vaìo âiãöu khiãøn, x2 laì ngoî vaìo dæî liãûu. Ta coï: - x1= 1 ⇒ y = 0 (y luän bàòng 0 báút cháúp x2): Ta noïi cäøng NOR khoïa khäng cho dæî liãûu âi qua. ⎧x2 = 0 ⇒ y =1 - x1= 0 ⇒ ⎨ ⇒ y = x2 : Ta noïi cäøng NOR måí cho dæî ⎩x2 =1⇒ y = 0 liãûu vaìo ngoî vaìo x2 qua cäøng NOR âãún ngoî ra y.
Chæång 3. Caïc pháön tæí logic cå baín Trang 37 Sæí duûng cäøng NOR âãø thæûc hiãûn chæïc nàng cäøng logic khaïc: - Duìng cäøng NOR laìm cäøng NOT : x x1 y x y x2 y = x1 + x2 = x1.x2 = x Hçnh 3.16a. Sæí duûng cäøng NOR taûo cäøng NOT - Duìng cäøng NOR laìm cäøng OR : x x1 + x2 x1 1 y y x2 x2 y = x1 + x2 = x1 + x2 Hçnh 3.16b. Sæí duûng cäøng NOR taûo cäøng OR - Duìng cäøng NOR laìm cäøng BUFFER : x x 1 x y x y x2 y = x = x Hçnh 3.16c. Sæí duûng cäøng NOR taûo cäøng BUFFER - Duìng cäøng NOR laìm cäøng AND : x1 x x 1 y 1 y x2 x2 x2 y = x1 + x2 = x1.x2 = x1.x2 Hçnh 3.16d. Sæí duûng cäøng NOR laìm cäøng AND
Baìi giaíng Kyî Thuáût Säú Trang 38 - Duìng cäøng NOR laìm cäøng NAND: x1 x 1 x1 y1 y y x2 x2 x2 y = y1 = x1 + x2 = x1 + x 2 = x1.x2 Hçnh 3.16e. Sæí duûng cäøng NOR laìm cäøng NAND g. Cäøng EX - OR (XOR) Âáy laì cäøng logic thæûc hiãûn chæïc nàng cuía maûch cäüng modulo 2 (cäüng khäng nhåï), laì cäøng coï hai ngoî vaìo vaì mäüt ngoî ra coï kyï hiãûu vaì baíng traûng thaïi nhæ hçnh veî. Phæång trçnh logic mä taí hoaût âäüng cuía cäøng XOR : yXOR = x1 x2 + x1 .x2 = x1 ⊗ x2 x1 x2 y x1 y 0 0 0 0 1 1 x 2 1 0 1 Hçnh 3.17. Cäøng XOR 1 1 0 Cäøng XOR âæåüc duìng âãø so saïnh hai tên hiãûu vaìo: - Nãúu hai tên hiãûu vaìo laì bàòng nhau thç tên hiãûu ngoî ra bàòng 0 - Nãúu hai tên hiãûu vaìo laì khaïc nhau thç tên hiãûu ngoî ra bàòng 1. Caïc tênh cháút cuía pheïp toaïn XOR: 1. x1 ⊗ x2 = x2 ⊗ x1 2. x1 ⊗ x2 ⊗ x3 = (x1 ⊗ x2) ⊗ x3 = x1 ⊗ (x2 ⊗ x3) 3. x1.(x2 ⊗ x3) = (x1.x2) ⊗ (x3.x1) C/m: Ta coï: x1.(x2 ⊗ x3) = x1(x2.x 3 + x 2.x3) =x1x2 x 3 + x1 x 2 x3 + x1 x 1.x3 + x1 x 1.x2 = x1x2 x 3 + x1 x 2 x3 + x1 x 1.x3 + x1 x 1.x2
Chæång 3. Caïc pháön tæí logic cå baín Trang 39 = x1x2(x 3 +x1) + x1 x3(x 2 + x 1 ) = x1x2 x1x3 + x1 x3 x1x2 (x1x2) ⊗ (x1x3) = x1x2 x1x3 + x1x3 x1x2 4. x ⊗ 0 = x x ⊗ 1 =x Måí räüng tênh cháút 4 : Nãúu x1 ⊗ x2 = x3 thç x1 ⊗ x3=x2 x ⊗ x = 0 x ⊗ x = 1 h. Cäøng EX - NOR (XNOR) Âáy laì cäøng logic thæûc hiãûn chæïc nàng cuía maûch cäüng âaío modulo 2 (cäüng khäng nhåï), laì cäøng coï hai ngoî vaìo vaì mäüt ngoî ra coï kyï hiãûu vaì baíng traûng thaïi nhæ trãn hçnh 3.19. Phæång trçnh logic mä taí hoaût âäüng cuía cäøng: y = x1x 2 + x1x 2 = x1 ⊗ x 2 x1 x2 y x1 y 0 0 1 0 1 0 x2 Hçnh 3.19. Cäøng XNOR 1 0 0 1 1 1 Tênh cháút cuía cäøng XNOR: 1. (x1 ⊗ x2 )(x3 ⊗ x4 ) = (x1 ⊗ x2 ) + (x3 ⊗ x4 ) 2. (x1 ⊗ x2 ) + (x3 ⊗ x4 ) = (x1 ⊗ x2 )(x3 ⊗ x4 ) 3. x1 ⊗ x2 = x1 ⊗ x2 = x1 ⊗ x2 4. x1 ⊗ x 2 = x1 ⊗ x 2 5.x1 ⊗ x 2 = x3 ⇔ x1 ⊗ x3 = x 2 3.2.2.2. Phán loaûi cäøng logic theo phæång phaïp chãú taûo
Baìi giaíng Kyî Thuáût Säú Trang 40 a. Cäøng logic duìng Diode a) b) x1 D1 VCC R x2 D2 x1 D1 y y R x2 D2 . Hçnh 3.20. Så âäö maûch cäøng logic duìng diode a.Cäøng OR - b.Cäøng AND Xeït så âäö maûch âån giaín trãn hçnh 3.20. Så âäö hçnh a: - x1 = x2 = 0 ⇒ D1, D2 tàõt Vy =VR = 0 ⇒ y = 0 - x1 = 0, x2= 1 ⇒ D1 tàõt, D2 dáùn Vy =VR = 5V ⇒ y = 1 - x1= 1, x2= 0 ⇒ D1 dáùn, D2 tàõt Vy =VR = 5V ⇒ y = 1 - x1= x2=1 ⇒ D1, D2 dáùn Vy =VR = 5V ⇒ y = 1 Âáy chênh laì cäøng OR âæåüc chãú taûo trãn cå såí diode vaì âiãûn tråí goüi laì hoü DRL (Diode Resistor Logic) hoàûc DL (Diode logic). Så âäö hçnh b: - x1 = x2 = 0 ⇒ D1, D2 dáùn Vy =VR = 0 ⇒ y = 0 - x1 = 0, x2=1 ⇒ D1 dáùn, D2 tàõt Vy =VR = 0 ⇒ y = 0 - x1 = 1, x2=0 ⇒ D1 tàõt, D2 dáùn Vy =VR = 0 ⇒ y = 0 V - x1 = x2=1 ⇒ D1, D2 tàõt Vy =VR = 5 ⇒ y = 1 Âáy chênh laì cäøng AND âæåüc chãú taûo trãn cå såí diode vaì âiãûn tråí goüi laì hoü DRL hoàûc DL. b. Cäøng logic duìng BJT Cäøng NOT (hçnh 3.21a) - x = 0 ⇒ BJT tàõt ⇒ Vy ≈ Vcc = 5V ⇒ y = 1 - x = 1 ⇒ BJT dáùn baîo hoìa ⇒ Vy ≈ Vcc ≈ 0V ⇒ y = 0 Âáy laì cäøng NOT hoü RTL (Resistor Transistor Logic). Cäøng NOR (hçnh 3.21b) - x1 = x2 = 0 ⇒ BJT tàõt ⇒ Vy ≈ Vcc = 5V ⇒ y = 1
Chæång 3. Caïc pháön tæí logic cå baín Trang 41 - x1 = 0, x2=1 ⇒ BJT dáùn baîo hoìa. VCC a) ⇒ Vy ≈Vcc ≈ 0V ⇒ y = 0 Rc - x =1, x = 0 ⇒ BJT dáùn baîo hoìa y 1 2 x Rb Q1 ⇒ Vy ≈ Vcc ≈ 0V ⇒ y = 0 - x1= x2=1 ⇒ BJT dáùn baîo hoìa ⇒ Vy ≈ Vcc ≈ 0V ⇒ y = 0 VCC Âáy chênh laì cäøng NOR hoü RTL (Resistor b) Rc Transistor Logic). y x1 R1 Q1 VCC x2 R2 x1 x2 Rc y Hçnh 3.21.(a,b) R1 Q2 Q1 R2 Hçnh 3.21c. Cäøng NOR duìng 2 BJT Hoü DTR (Diode Transistor Resistor) Trãn hçnh 3.22 laì så âäö maûch cäøng NAND hoü DTR. Giaíi thêch hoaût âäüng cuía maûch : VCC R3 y R1 x2 D2 D4 D3 Q x1 D1 A R2 Hçnh 3.22. Cäøng NAND hoü DTR - Khi x1 = x2 = 0, caïc diode D1, D2 phán cæûc thuáûn →D1, D2 dáùn → VA= 0,7V = Vγ /Diode (Diode ghim âiãûn aïp) maì âiãöu kiãûn âãø D3, D4 dáùn laì: VA ≥ 2Vγ/D + Vγ/BJT = 2.0,7V + 0,6V = 2V. ⇒ D1, D2 dáùn → D3, D4, BJT tàõt ⇒ ngoî ra y = 1.
Baìi giaíng Kyî Thuáût Säú Trang 42 - Khi x1= 0, x2= 1, D1 dáùn, D2 tàõt → VA = 0,7V = Vγ /Diode (Diode ghim âiãûn aïp) ⇒ D3, D4, BJT tàõt ⇒ ngoî ra y = 1. - Khi x1= 1, x2= 0, D1 tàõt, D2 dáùn → VA = 0,7V = Vγ /Diode (Diode ghim âiãûn aïp) ⇒ D3, D4, BJT tàõt ⇒ ngoî ra y = 1. - Khi x1 = x2 = 1, D1, D2 tàõt → VA ≈ Vcc , (VA = Vcc - VR1) ⇒ D3, D4 dáùn, BJT dáùn baîo hoìa ⇒ ngoî ra y = 0. Váûy âáy chênh laì cäøng NAND hoü DTL. Nhiãûm vuû cuía linh kiãûn: Khi tên hiãûu ngoaìi cuía tên hiãûu nhiãùu chäöng cháûp lãn nhau (khoaíng 0,6V), nãúu chè coï mäüt diode D3 thç tên hiãûu nhiãùu seî dãù daìng laìm cho BJT dáùn (VA= 0,7V =Vγ /D3, vaì tên hiãûu nhiãùu 0,6V ≈ Vγ/BJT), nhæng nãúu màõc näúi tiãúp thãm D4 thç maûch coï thãø ngàn tên hiãûu chäöng cháûp lãn âãún ≈ 1,2V. Nhæ váûy D3, D4 coï taïc duûng náng cao khaí nàng chäúng nhiãùu cuía maûch. Ngoaìi ra, R2 laìm tàng täúc âäü chuyãøn âäøi traûng thaïi cuía BJT, vç luïc âáöu khi BJT dáùn seî coï doìng âäø qua R2 taûo mäüt phán aïp cho tiãúp giaïp JE cuía BJT âãù phán cæûc thuáûn laìm cho BJT nhanh choïng dáùn, vaì khi BJT tàõt thç læåüng âiãûn têch seî xaî qua R2 nãn BJT nhanh choïng tàõt. Hoü TTL (Transistor - Transistor -Logic) VCC R1 R3 Q1 x1 D Q1 Q2 x1 x2 R2 x2 x1 x2 c a) . b) Hçnh 3.23. Cäøng NAND hoü TTL a. Så âäö maûch, b.Transistor 2 tiãúp giaïp vaì så âäö tæång âæång Transistor Q1 âæåüc sæí duûng gäöm 2 tiãúp giaïp BE1, BE2 vaì mäüt tiãúp giaïp BC. Tiãúp giaïp BE1, BE2 cuía Q1 thay thãú cho D1, D2 vaì tiãúp giaïp BC thay thãú cho D3 trong så âäö maûch cäøng NAND hoü DTR (hçnh 3.22).
Chæång 3. Caïc pháön tæí logic cå baín Trang 43 Giaíi thêch hoaût âäüng: - x1 = x2 = 0 caïc tiãúp giaïp BE1, BE2 seî âæåüc måí laìm cho âiãûn aïp cæûc nãön cuía BJT Q1 : VB = Vγ = 0,6V. Maì âiãöu kiãûn âãø cho tiãúp giaïp BC, D vaì BJT Q1 dáùn thç âiãûn thãú åí cæûc nãön cuía BJT Q1 phaíi bàòng: VB = Vγ/BC + Vγ/BE1 +Vγ/BE2 = 0,6 + 0,7 + 0,6 = 1,9V Âiãöu âoï chæïng toí khi caïc tiãúp giaïp BE1, BE2 måí thç tiãúp giaïp BC, diode D vaì BJT Q2 tàõt ⇒ y = 1. - x1 = 0, x2 = 1 caïc tiãúp giaïp BE1 måí, BE2 tàõt thç tiãúp giaïp BC, diode D vaì BJT Q2 tàõt ⇒ y = 1. - x1 = 1, x2 = 0 caïc tiãúp giaïp BE1 tàõt, BE2 måí thç tiãúp giaïp BC, diode D vaì BJT Q2 tàõt ⇒ y = 1. - x1 = x2 = 1 caïc tiãúp giaïp BE1, BE2 tàõt thç tiãúp giaïp BC, diode D dáùn vaì BJT Q2 dáùn baîo hoìa ⇒ y = 0 Váûy, âáy laì maûch thæûc hiãûn cäøng NAND hoü TTL Âãø náng cao khaí nàng taíi cuía cäøng, ngæåìi ta thæåìng màõc thãm åí ngoî ra mäüt táöng khuãúch âaûi kiãøu C-C nhæ så âäö maûch trãn hçnh 3.24: Vcc R5 R1 R4 Q4 x1 Q2 D y Q1 x2 R 2 R3 Q3 Hçnh 3.24. Âãø náng cao táön säú laìm viãûc cuía cäøng, ngæåìi ta cho caïc BJT laìm viãûc åí chãú âäü khuãúch âaûi, âiãöu âoï coï nghéa laì ngæåìi ta khäúng chãú âãø sao cho caïc tiãúp xuïc Jc cuía BJT bao giåì cuîng åí traûng thaïi phán cæûc ngæåüc.
Baìi giaíng Kyî Thuáût Säú Trang 44 Âãø thæûc hiãûn âæåüc âiãöu âoï, ngæåìi ta thæåìng màõc song song våïi tiãúp giaïp Jc cuía BJT mäüt diode Shottky. Âàûc âiãøm cuía diode Shottky laì tiãúp xuïc cuía noï gäöm mäüt cháút baïn dáùn våïi mäüt kim loaûi, nãn noï khäng têch luîy âiãûn têch, do âoï BJT seî chuyãùn âäøi traûng thaïi nhanh hån. Ngæåìi ta cuîng khäng duìng diode Zener båíi vç tiãúp xuïc cuía diode Zener laì cháút baïn dáùn nãn seî têch træî âiãûn têch dæ. Så âäö maûch caíi tiãún trãn seî veî tæång âæång nhæ sau (hçnh 3.25): Vcc R5 R1 R4 Q 4D x1 Q2 y Q1 x2 R 2 R3 Q3 Hçnh 3.25. Cäøng logic hoü TTL duìng diode Shottky Hoü ECL (Emitter Coupled Logic) VCC = 0V R7 R3 R4 2 Q3 1 1' y1 x1 R1 Q1 Q2 3 Q4 x2 y2 R2 R5 R6 RE -VEE Hçnh 3.26. Cäøng logic hoü ECL (Emitter Coupled Logic) Nhæåüc âiãøm cuía hoü ECL: Ngoî ra coï âiãûn thãú ám nãn noï khäng tæång thêch vãö mæïc logic våïi caïc hoü logic khaïc. Giaíi thêch hoaût âäüng cuía maûch: - Khi x1 = x2 = 0: Q1, Q2 dáùn nãn âiãûn thãú taûi cæûc nãön (2), (3) cuía Q3, Q4 caìng ám (do 1 vaì 1’ ám) nãn Q3, Q4 tàõt ⇒ y1 = 1, y2 = 1.
Chæång 3. Caïc pháön tæí logic cå baín Trang 45 - Khi x1= 0, x2=1: Q1 dáùn, Q2 tàõt nãn âiãûn thãú taûi cæûc nãön (2) cuía Q3 dæång, âiãûn thãú taûi cæûc nãön (3) cuía Q4 caìng ám nãn Q3 dáùn, Q4 tàõt ⇒ y1 = 0, y2 = 1. - Khi x1=1, x2=0: Q1 tàõt, Q2 dáùn nãn âiãûn thãú taûi cæûc nãön (2) cuía Q3 ám, âiãûn thãú taûi cæûc nãön (3) cuía Q4 caìng dæång nãn Q3 dáùn, Q4 tàõt ⇒ y1 = 1, y2 = 0. - Khi x1= x2=1: Q1, Q2 tàõt nãn âiãûn thãú taûi cæûc nãön (2), (3) cuía Q3, Q4 caìng dæång nãn Q3, Q4 dáùn ⇒ y1 = 0, y2 = 0. c.Cäøng logic duìng MOSFET MOSFET (Metal Oxyt Semiconductor Field Effect Transistor), coìn goüi laì IGFET (Isolated Gate FET - Transistor træåìng coï cæûc cäøng caïch ly). MOSFET coï hai loaûi: Loaûi coï kãnh âàût sàôn vaì loaûi coï kãnh caím æïng. D D B B NMOS G PMOS G S S a. MOSFET kãnh âàût sàôn D D B B NMOS G PMOS G S S b. MOSFET kãnh caím æïng Hçnh 3.27. Kyï hiãûu caïc loaûi MOSFET khaïc nhau Duì laì MOSFET coï kãnh âàût sàôn hay kãnh caím æïng âãöu coï thãø phán chia laìm hai loaûi âoï laì: MOSFET kãnh N goüi laì NMOS vaì MOSFET kãnh P goüi laì PMOS. Âàûc âiãøm cuía 2 loaûi naìy khaïc nhau nhæ sau:
Baìi giaíng Kyî Thuáût Säú Trang 46 - PMOS: Tiãu thuû cäng suáút tháúp, täúc âäü chuyãùn âäøi traûng thaïi cháûm. - NMOS: Tiãu thuû cäng suáút låïn hån, täúc âäü chuyãùn âäøi traûng thaïi nhanh hån. Trãn hçnh 3.27 laì kyï hiãûu cuía caïc loaûi MOSFET khaïc nhau. Chuï yï: MOSFET kãnh âàût sàôn coï thãø laìm viãûc åí hai chãú âäü giaìu kãnh vaì ngheìo kãnh trong khi MOSFET kãnh caím æïng chè laìm viãûc åí chãú âäü giaìu kãnh. Duìng NMOS kãnh caím æïng chãú taûo caïc cäøng logic Xeït caïc cäøng logic loaûi NMOS trãn hçnh 3.28. Âiãöu kiãûn âãø cäøng NMOS dáùn: VD > VS, VG > VB Trong táút caí hçnh veî ta coï : Hçnh 3.28a (cäøng NOT) Theo âiãöu kiãûn âãø cäøng NMOS dáùn: VD > VS, VG > VB ⎧R = 200KΩ ⎧R = 1KΩ Q DS(ON ) Q ,Q DS( ON ) 1 ⎨ 7 2 3 ⎨ 7 V R = 10 KΩ R = 10 KΩ cc ⎩ DS(OF) ⎩ DS( OF ) Vcc D1 V D DD B B Q1 S D1 Q1 1 y y Q1 B S D2 S1 y Q2 x1 B D D S2 D2 B Q2 B Q3 x D3 x Q2 1 S2 S S x2 Q3 B x2 S3 a.Cäøng NOT b.Cäøng NOR c.Cäøng NAND Hçnh 3.28 Ta tháúy Q1 coï B näúi mass thoía maîn âiãöu kiãûn nãn Q1 luän luän dáùn. - Khi x=0: Q1 dáùn Q2 tàõt (vç VG2 = VB2 = 0 nãn khäng hçnh thaình âiãûn træåìng giæîa G vaì B → khäng huït âæåüc caïc e- laì haût dáùn thiãøu
Chæång 3. Caïc pháön tæí logic cå baín Trang 47 säú åí vuìng âãú B → khäng hçnh thaình âæåüc kãnh dáùn). Luïc naìy, theo så âäö tæång âæång (hçnh 3.29a) ta coï: R DS(OFF)/Q2 Vy = VDD R DS(ON)/Q1 + R DS(OFF)/Q2 107 K = VDD 200K +107 K ⇒ Vy ≈ VDD ⇒ y = 1 - Khi x = 1 luïc âoï VG/Q2 > VB/Q2 → hçnh thaình mäüt âiãûn træåìng hæåïng tæì G → B, âiãûn træåìng naìy huït caïc âiãûn tæí laì caïc haût dáùn thiãøu säú trong vuìng âãú B di chuyãøn theo chiãöu ngæåüc laûi vãö màût âäúi diãûn, hçnh thaình kãnh dáùn taûm thåìi näúi liãön giæîa G vaì B vaì coï doìng âiãûn iD âi tæì D qua ⇒ Q2 dáùn. Nhæ váûy Q1, Q2 dáùn ta coï så âäö tæång âæång (hçnh 3.29b). Theo så âäö naìy ta coï: VDD R DS(ON)/Q2 RDS(ON)/Q1 Vy = VDD y R DS(ON)/Q1 + R DS(ON)/Q2 1K RDS(OFF)/Q2 = V 200K +1K DD 1 Hçnh 3.29a (x=0) ⇒ Vy ≈ VDD = 0,025V ⇒ y = 0 200 VDD RDS(ON)/Q1 y RDS(ON)/Q2 Hçnh 3.29b(x=1) Váûy maûch åí hçnh 3.28a laì maûch thæûc hiãûn cäøng NOT. Hçnh 3.28c (cäøng NAND)
Baìi giaíng Kyî Thuáût Säú Trang 48 - Khi x1 = x2 = 0 (hçnh 3.30a): Q1 luän dáùn, Q2 vaì Q3 âãöu tàõt luïc âoï theo så âäö tæång âæång ta coï: R DS(OFF)/Q2 + R DS(OFF)/Q3 Vy = VDD R DS(ON)/Q1 + R DS(OFF)/Q2 + R DS(OFF)/Q3 107 K +107 K = VDD ⇒ Vy ≈ VDD ⇒ y = 1. 200K +107 K +107 K VDD RDS(ON)/Q1 y RDS(OFF)/Q2 RDS(OFF)/Q Hçnh 3.30a. (x1=x2=0) V DD RDS(ON)/Q1 y RDS(ON)/Q2 - Khi x1= 1, x2=0 (hçnh 3.30b): Q1, Q2 dáùn vaì Q3 R tàõt luïc âoï theo så âäö tæång âæång ta coï: DS(OFF)/Q3 Hçnh 3.30b (x1=1, x2=0)
Chæång 3. Caïc pháön tæí logic cå baín Trang 49 R DS(ON) / Q2 + R DS(OFF) / Q3 Vy = VDD R DS(ON) / Q1 + R DS(ON) / Q2 + R DS(OFF) / Q3 1K +107 K = VDD 200K +1K +107 K ⇒ Vy ≈ VDD ⇒ y = 1 - Khi x1= 0, x2=1: Q1, Q3 dáùn vaì Q2 tàõt, giaíi thêch VDD hoaìn toaìn tæång tæû ta coï Vy ≈ VDD ⇒ y = 1 RDS(ON)/Q1 y - Khi x =1, x =1 (hçnh 3.30c): Q , Q vaì Q âãöu 1 2 1 2 3 RDS(ON)/Q2 dáùn, luïc âoï theo så âäö tæång âæång ta coï: R DS(ON)/Q2 + R DS(ON)/Q3 RDS(ON)/Q3 Vy = VDD R DS(ON)/Q1 + R DS(ON)/Q2 + R DS(ON)/Q3 Hçnh 3.30c (x =x =1) 1 K +1K 1 2 = V 200K +1K +1K DD ⇒ Vy ≈ 0,05V ⇒ y = 0. Váûy hçnh 3.28c laì maûch thæûc hiãûn cäøng NAND. Hçnh 3.28b (cäøng NOR) Ta láön læåüt xeït caïc træåìng håüp sau: V DD VDD R DS(ON)/Q1 RDS(ON)/Q1 y y RDS(OFF)/Q2 R RDS(OFF)/Q2 DS(OFF)/Q3 RDS(ON)/Q3 Hçnh 3.31a Hçnh 3.31a (x =0, x =1) (x1=x2=0) 1 2 - Khi x1 = x2 = 0 (hçnh 3.31a) : Q1 dáùn, Q2 vaì Q3 âãöu tàõt, luïc âoï theo så âäö tæång âæång ta coï: (RDS(OFF)/Q2 )//(RDS(OFF)/Q3) Vy = VDD R DS(ON)/Q1 +[(RDS(OFF)/Q2 )//(RDS(OFF)/Q3)]
Baìi giaíng Kyî Thuáût Säú Trang 50 107 K//107 K = VDD ⇒ Vy ≈ VDD ⇒ y = 1 200K + (107 K//107 K) - Khi x1=0, x2=1 (hçnh 3.31b): Q1 vaì Q3 dáùn, Q2 tàõt, ta coï: (R DS(OFF)/Q2 )//(R DS(ON)/Q3) Vy = VDD R DS(ON)/Q1 + [(RDS(OFF)/Q2 )//(R DS(ON)/Q3)] 107 K//1K = VDD 200K + (107 K//1K) 1 ⇒ V ≈ V ≈ 0,005V ⇒ y = 0 y 201 DD - Khi x1=1, x2=0: Q1 vaì Q2 dáùn, Q3 tàõt, giaíi thêch tæång tæû ta coï: 1 V ≈ V ≈ 0,005V ⇒ y = 0 y 201 DD - Khi x1=x2=1 (hçnh 3.31c): Q1, Q2, Q3 âãöu dáùn, ta coï: (R DS(ON)/Q2 )//(R DS(ON)/Q3) Vy = VDD R DS(ON)/Q1 +[(R DS(ON)/Q2 )//(R DS(ON)/Q3)] 1K//1K = V 200K + (1K//1K) DD 0,5 ⇒ V ≈ V ⇒ y = 0. y 200 DD Váûy, så âäö maûch trãn hçnh 3.28b chênh laì maûch thæûc hiãûn cäøng NOR. VDD RDS(ON)/Q1 y RDS(ON)/Q3 RDS(ON)/Q2 Hçnh 3.31c (x1=x2=1) Caïc cäøng logic hoü CMOS (Complementation MOS)
Chæång 3. Caïc pháön tæí logic cå baín Trang 51 Âáy laì loaûi cäøng trong âoï caïc transistor âæåüc sæí duûng thuäüc loaûi MOSFET vaì luän coï sæû kãút håüp giæîa PMOS vaì NMOS, vç váûy maì ngæåìi ta goüi laì CMOS. Nhåì cáúu truïc naìy maì vi maûch CMOS coï nhæîng æu âiãøm sau: - Cäng suáút tiãu thuû åí traûng thaïi ténh ráút nhoí. - Täúc âäü chuyãøn âäøi traûng thaïi cao. - Khaí nàng chäúng nhiãùu täút. - Khaí nàng taíi cao. Trãn hçnh 3.32 laì caïc cäøng logic hoü CMOS, chuïng ta seî láön læåüt giaíi thêch hoaût âäüng cuía mäùi så âäö maûch. VDD S S V DD Q2 B B Q3 S D D B Q1 y y D D D2 x B Q1 B Q2 S2 x1 S D3 Q x2 2 B S3 a. Cäøng NOT b. Cäøng NAND Hçnh 3.32. Caïc cäøng logic hoü CMOS Hçnh 3.32a (cäøng NOT) Âiãöu kiãûn âãø cäøng PMOS dáùn : VS > VD, VG VS, VG > VB - Khi x = 0 (hçnh 3.33a): Q1 dáùn, Q2 tàõt , theo så âäö tæång âæång ta coï: 7 R DS(OFF)/Q2 10 K Vy = VDD = 7 VDD R DS(ON)/Q1 + R DS(OFF)/Q2 1K +10 K ⇒ Vy ≈ VDD ⇒ y = 1 - Khi x =1 (hçnh 3.33b) thç Q1 tàõt, Q2 dáùn, ta coï:
Baìi giaíng Kyî Thuáût Säú Trang 52 R DS(ON) / Q2 Vy = VDD R DS(OFF) / Q1 + R DS(ON) / Q2 1K 1 = VDD ⇒ Vy ≈ VDD 1K +107 K 107 vç ráút nhoí so våïi âiãûn thãú baîo hoìa cuía CMOS åí mæïc logic 0⇒ y = 0. VDD VDD RDS(ON)/Q1 RDS(OFF)/Q1 y y RDS(OFF)/Q2 RDS(ON)/Q2 a) b) Hçnh 3.33.Så âäö tæång âæång: a.Khi x=0 b.Khi x=1 Váûy maûch åí hçnh 3.32a laì maûch thæûc hiãûn cäøng NOT Hçnh 3.32b (cäøng NAND) Så âäö tæång âæång cuía maûch cäøng NAND hoü CMOS âæåüc cho trãn hçnh 3.34. - Khi x1=x2= 0: Q4, Q3 dáùn, Q2 vaì Q1 tàõt, ta coï: (R DS(OFF)/Q2 )//(R DS(OFF)/Q1 ) Vy = VDD R DS(OFF)/Q1 + R DS(OFF)/Q2 + [(R DS(ON)/Q4 )//(R DS(ON)/Q3 )] 107 K//107 K = VDD ⇒ Vy ≈ VDD ⇒ y = 1 107 K//107 K + (1K//1K) - Khi x1 = 0, x2 = 1: Q2 Q3 dáùn, Q1 Q 4 tàõt, ta coï : (R DS(OFF)/Q1 )//(R DS(ON)/Q2 ) Vy = VDD R DS(OFF)/Q1 + R DS(OFF)/Q2 + [(R DS(ON)/Q3 )//(R DS(OF)/Q4 )] 107 K +1K = VDD ⇒ Vy ≈ VDD ⇒ y = 1 107 K +1K + (107 K//1K) - Khi x1 = 1, x2 = 0 : Q3vaì Q2 dáùn, Q1, Q4 tàõt: ⇒ Vy ≈ VDD ⇒ y = 1 - Khi x1 = x2 = 1 : Q2, Q1 dáùn, Q3vaì Q4 tàõt, ta coï:
Chæång 3. Caïc pháön tæí logic cå baín Trang 53 (R DS(ON)/Q1)//(R DS(ON)/Q2 ) Vy = VDD R DS(ON)/Q1 + R DS(ON)/Q2 + [(R DS(OFF)/Q4 )//(R DS(OFF)/Q3)] 1K +1K = VDD 1K +1K + (107 K//107 K) ⇒ Vy ≈ 0V ⇒ y = 0 ⇒ Âáy chênh laì maûch thæûc hiãûn cäøng NAND. VDD R DS/Q3 RDS/Q4 y RDS/ Q1 RDS/ Q2 Hçnh 3.34. 3.2.2.3. Phán loaûi cäøng logic theo ngoî ra a. Ngoî ra cäüt chaûm (Totem Pole Output) Xeït cäøng logic hoü TTL våïi så âäö maûch nhæ hçnh 3.35. VCC R4 R5 R1 Q4 Q1 x1 D y Q2 x2 Q3 R2 R3 . Hçnh 3.35. Ngoî ra cäüt chaûm - Khi x1=x2=1: Tiãúp giaïp BE1, BE2 cuía Q1 phán cæûc ngæåüc nãn Q1 tàõt. Âiãûn thãú taûi cæûc nãön cuía Q1 laìm cho tiãúp giaïp BC/Q1 måí, coï doìng
Baìi giaíng Kyî Thuáût Säú Trang 54 âiãûn chaíy qua tiãúp giaïp BC/Q1 âäø vaìo cæûc nãön cuía Q2, Q2 âæåüc phán cæûc thuáûn nãn dáùn baîo hoìa. Do Q2 dáùn baîo hoìa dáùn tåïi Q3 dáùn baîo hoìa. Khi Q2 dáùn baîo hoìa thç âiãûn thãú taûi cæûc C/Q2 VC/Q2= VB/Q4 = Vces/Q2 + Vbes/Q3 = 0,2 + 0,8 = 1V Maì âiãöu kiãûn cáön cho Q4 dáùn laì: VC/Q2=VB/Q4 = Vbe/Q4 + Vγ/D + Vces/Q3 = 0,6 + 0,8 + 0,2= 1,6V Ta tháúy âiãöu kiãûn naìy khäng thoía maîn khi Q2 dáùn baîo hoìa, do âoï khi Q2 dáùn baîo hoìa ⇒ Q4 tàõt ⇒ càõt nguäön VCC ra khoíi maûch. Luïc naìy ta noïi ràòng cäøng seî huït doìng vaìo vaì doìng tæì ngoaìi qua taíi âäø vaìo ngoî ra cuía cäøng âi qua Q3, ngæåìi ta noïi Q3 laì nåi nháûn doìng vaì doìng âäø vaìo Q3 goüi laì doìng ngoî ra mæïc tháúp, kyï hiãûu IOL. Vãö màût thiãút kãú maûch: ta tháúy ràòng doìng taíi It cuîng chênh laì doìng ngoî ra mæïc tháúp IOL vaì laì doìng âäø tæì ngoaìi vaìo qua Q3, doìng naìy phaíi nàòm trong giåïi haûn chëu âæûng doìng cuía Q3 âãø Q3 khäng bë âaïnh thuíng thç maûch seî laìm viãûc bçnh thæåìng. Doìng IOL thay âäøi tuìy thuäüc vaìo cäng nghãû chãú taûo: + TTL : doìng ngoî ra mæïc tháúp IOL låïn nháút 16mA. + TTL/LS : doìng ngoî ra mæïc tháúp IOL låïn nháút 8mA. Âáy laì nhæîng thäng säú ráút quan troüng cáön chuï yï trong quaï trçnh thiãút kãú maûch säú hoü TTL âãø âaím baío âäü an toaìn vaì äøn âënh cuía maûch. - Caïc træåìng håüp coìn laûi (x1= 0,x2 =1; x1=1,x2=0; x1=x2=0): Luïc naìy Q2 vaì ì Q3 tàõt coìn Q4 dáùn ⇒ y = 1. Ta noïi cäøng cáúp doìng ra, doìng naìy âäø tæì nguäön qua Q4 vaì diode D xuäúng cung cáúp cho taíi, ngæåìi ta goüi laì doìng ngoî ra mæïc cao, kyï hiãûu IOH. Âiãûn aïp ngoî ra VY âæåüc tênh phuû thuäüc vaìo doìng taíi IOH: VY = Vlogic1 = Vcc- IOHR5 - Vces/ Q4 - Vγ/D Thäng thæåìng Vlogic1 max = (3,4V → 3,6V ) IOH cuîng chênh laì doìng qua taíi It, nãúu IOH caìng tàng thç Vlogic1 caìng giaím vaì ngæåüc laûi. Song Vlogic1 chè âæåüc pheïp giaím âãún mäüt giaï trë cho pheïp Vlogic1 min = 2,2V Vãö màût thiãút kãú maûch: ta choün Vlogic1 min = 2,4V âãø baío âaím cäøng cáúp doìng ra khi åí mæïc logic 1 khäng âæåüc nhoí hån Vlogic1 min vaì âaím
Chæång 3. Caïc pháön tæí logic cå baín Trang 55 baío cäøng huït doìng vaìo khi åí mæïc logic 0 thç doìng taíi åí mæïc logic 0 khäng âæåüc låïn hån doìng IOL. Nhæåüc âiãøm cuía ngoî ra cäüt chaûm: Khäng cho pheïp näúi chung caïc ngoî ra laûi våïi nhau coï thãø laìm hoíng cäøng. b. Ngoî ra cæûc thu âãø håí (Open Collector Output) Vãö phæång diãûn cáúu taûo gáön giäúng VCC våïi ngoî ra cäüt chaûm nhæng khaïc våïi ngoî R4 VCC' ra cäüt chaûm laì khäng coï Q4, diode D, R5 R1 Q1 R vaì luïc naìy cæûc thu (cæûc C) cuía Q3 âãø håí. x1 y Q2 Do âoï âãø cäøng laìm viãûc trong thæûc tãú x2 Q3 R2 R3 ta näúi ngoî ra cuía cäøng (cæûc C cuía Q3) / lãn nguäön V CC bàòng pháön tæí thuû âäüng R. . / Hçnh 3.36. Ngoî ra cæûc thu âãø håí Nguäön V CC coï thãø cuìng giaï trë våïi VCC hoàûc khaïc tuìy thuäüc vaìo thiãút kãú. Chuïng ta láön læåüt phán têch caïc træåìng håüp hoaût âäüng cuía maûch: - Khi x1=x2=1: Tiãúp giaïp BE1, BE2 phán cæûc ngæåüc, âiãûn thãú taûi cæûc nãön cuía Q1 laìm cho tiãúp giaïp BC/Q1 måí nãn Q2 dáùn baîo hoìa, Q2 dáùn baîo hoìa keïo theo Q3 dáùn baîo hoìa ⇒ y =0, do âoï âiãûn aïp taûi ngoî ra y: VY= Vlogic0 =VC/Q3= Vces/Q3 = 0,2V ≈ 0V Luïc naìy cäøng seî huït doìng vaìo vaì Q3 laì nåi nháûn doìng, ta goüi laì doìng ngoî ra mæïc tháúp IOL. - Caïc træåìng håüp coìn laûi (x1=0,x2=1; x1=1,x2=0; x1=x2=0): Coï êt nháút mäüt tiãúp giaïp BE/Q1 måí, ghim âiãûn thãú taûi cæûc nãön Q1 laìm cho tiãúp giaïp BC/Q1, Q2, Q3 âãöu tàõt, luïc naìy cäøng cáúp doìng ra âäø tæì nguäön V’CC qua âiãûn tråí R cáúp cho taíi åí maûch ngoaìi ⇒ y=1, ngæåìi ta goüi laì doìng ngoî ra mæïc cao IOH. Ta coï: / VY = Vlogic1 = V cc- IOHR
Baìi giaíng Kyî Thuáût Säú Trang 56 Æu âiãøm cuía ngoî ra coï cæûc thu âãø håí: Vcc - Cho pheïp näúi chung caïc ngoî ra laûi våïi R y nhau. x1 - Trong mäüt vaìi træåìng håüp khi näúi chung x2 caïc ngoî ra laûi våïi nhau coï thãø taûo thaình cäøng Hçnh 3.37 logic khaïc. Vê du:û Maûch åí hçnh 3.37 sæí duûng caïc cäøng NOT coï ngoî ra cæûc thu âãø håí, khi näúi chung caïc ngoî ra laûi våïi nhau coï thãø taûo thaình cäøng NOR. c. Ngoî ra ba traûng thaïi (Three States Output) Vãö màût cáúu truïc vaì cáúu taûo hoaìn toaìn giäúng ngoî ra cäüt chaûm, tuy nhiãn coï thãm ngoî vaìo thæï 3 cho pheïp maûch hoaût âäüng kê hiãûu laì E (Enable). - E=1: diode D1 tàõt, maûch laìm viãûc hoaìn toaìn giäúng cäøng NAND ngoî ra cäüt chaûm. Luïc âoï maûch täön taûi mäüt traûng thaïi y = 0 hoàûc y = 1 tuìy thuäüc vaìo caïc traûng thaïi logic cuía 2 ngoî vaìo x1, x2. - E=0: diode tiãúp giaïp BE3 måí, ghim aïp trãn cæûc nãön cuía Q1 laìm cho tiãúp giaïp BC/Q1 tàõt vaì Q2, Q3 cuîng tàõt. Luïc naìy diode D1 dáùn ghim âiãûn thãú åí cæûc C cuía Q2: VC / Q2 = VB/ Q4 = Vγ/D1 = 0,7V ⇒ Q4 tàõt. Nãn cäøng khäng cáúp doìng ra vaì VCC cuîng khäng huït doìng vaìo. Luïc naìy, R4 R5 ngoî ra y chè näúi våïi cäøng vãö phæång R1 diãûn váût lyï nhæng laûi caïch ly vãö Q4 Q1 phæång diãûn âiãûn, tæång âæång våïi x1 D2 y Q2 traûng thaïi tråí khaïng cao. Chênh vç váûy x2 Q3 D1 R2 maì ngæåìi ta goüi laì traûng thaïi thæï ba laì R3 traûng thaïi täøng tråí cao. E . Hçnh 3.38. Ngoî ra 3 traûng thaïi
Chæång 3. Caïc pháön tæí logic cå baín Trang 57 a) b) x x 1 y 1 y x2 x2 E E ⎧E = 1 ⇒ y = x x ⎧E = 1 ⇒ y = Z cao ⎨ 1 2 ⎨ ⎩E = 0 ⇒ y = Z cao ⎩E = 0 ⇒ y = x1 x2 Hçnh 3.39. Cäøng NAND 3 traûng thaïi våïi ngoî vaìo E a. E taïc âäüng mæïc cao - b. E taïc âäüng mæïc tháúp ÆÏng duûng: - Sæí duûng ngoî ra ba traûng thaïi âãø chãú taûo ra cäøng âãûm 2 chiãöu. - Chãú taûo caïc chêp nhåï cuía bäü vi xæí lyï. Giaíi thêch så âäö maûch hçnh 3.40: + E=1: Cäøng âãûm 1 vaì 3 måí, 2 vaì 4 treo lãn täøng tråí cao ⇒ dæîî liãûu âi tæì A→C, B→D. Váûy dæî liãûu xuáút ra. + E=0: Cäøng âãûm 2 vaì 4 måí, 1 vaì 3 treo lãn täøng tråí cao ⇒ dæî liãûu âi tæì C→A, D→B. Váûy dæî liãûu nháûp vaìo. A 1 C 2 3 B D 4 E Hçnh 3.40. ÆÏng duûng cuía ngoî ra 3 traûng thaïi
Baìi giaíng Kyî Thuáût Säú Trang 58 3.2.3. Caïc thäng säú kyî thuáût cuía cäøng logic 3.2.3.1. Cäng suáút tiãu taïn Ptt Mäüt pháön tæí logic khi laìm viãûc phaíi traíi qua caïc giai âoaûn sau: - ÅÍ traûng thaïi tàõt. - Chuyãøn tæì traûng thaïi tàõt sang traûng thaïi dáùn. - ÅÍ traûng thaïi dáùn. - Chuyãøn tæì traûng thaïi dáùn sang tàõt. ÅÍ mäùi giai âoaûn, pháön tæí logic âãöu tiãu thuû åí nguäön mäüt cäng suáút. a. Âäúi våïi caïc pháön tæí logic hoü TTL: tiãu thuû cäng suáút cuía nguäön chuí yãúu khi åí traûng thaïi ténh (âang dáùn hoàûc âang tàõt). - Nãúu goüi Po laì cäng suáút tiãu thuû æïng våïi ngoî ra cuía pháön tæí logic täön taûi åí mæïc logic 0. - Nãúu goüi P1 laì cäng suáút tiãu thuû æïng våïi ngoî ra cuía pháön tæí logic täön taûi åí mæïc logic 1. - Goüi P laì cäng suáút tiãu taïn trung bçnh thç: P0 + P1 P = 2 Âäúi våïi caí IC ngæåìi ta tênh nhæ sau: - Goüi ICL doìng do nguäön cung cáúp khi ngoî ra åí mæïc logic 0. - Goüi ICH doìng do nguäön cung cáúp khi ngoî ra åí mæïc logic 1. I + I - Goüi I laì doìng trung bçnh thç : I = CL CH C C 2 Thç cäng suáút tiãu taïn cho caí IC : Ptt = IC .VCC b. Âäúi våïi hoü CMOS: chè tiãu thuû cäng suáút chuí yãúu trong traûng thaïi âäüng (trong thåìi gian chuyãùn maûch). 2 Cäng suáút tiãu taïn: Ptt = CL . f .VDD CL :âiãûn dung taíi Táön säú hoaût âäüng (táön säú chuyãøn maûch) caìng låïn cäng suáút tiãu taïn caìng tàng. 3.2.3.2. Fanout Laì hãû säú màõc maûch åí ngoî ra hay coìn goüi laì khaí nàng taíi cuía Hçnh 3.41. Khaïi niãûm vãö Fanout mäüt pháön tæí logic.
Chæång 3. Caïc pháön tæí logic cå baín Trang 59 Goüi N laì Fanout cuía mäüt pháön tæí logic, thç noï âæåüc âënh nghéa nhæ sau: Säú ngoî vaìo logic cæûc âaûi âæåüc näúi âãún mäüt ngoî ra cuía pháön tæí logic cuìng hoü maì maûch váùn hoaût âäüng bçnh thæåìng (hçnh 3.41). VCC . Xeït vê duû âäúi våïi hoü DTL: (Hçnh 3.42) R3 R3 - y=1: maûch hoaût âäüng bçnh thæåìng. R1 D1 x1 D1 D3 D4 - y=0: BJT dáùn baîo hoìa, doìng baîo Q x2 D2 hoìa gäöm hai thaình pháön: R2 . IC S = IR3 + N I1 Hçnh 3.42 (våïi N laì säú pháön tæí taíi màõc åí ngoî ra) Màût khaïc: IB=IR1-IR2= const, maì Ics tàng lãn do coï doìng gheïp âäø vaìo ⇒ âiãöu kiãûn dáùn baîo hoìa khäng thoía maîn ⇒ BJT ra khoíi chãú âäü dáùn baîo hoìa vaì âi vaìo chãú âäü khuãúch âaûi, luïc âoï VY tàng lãn nãn ngoî ra khäng coìn âaím baío åí mæïc logic 0 næîa. Váûy, âiãöu kiãûn âãø maûch hoaût âäüng bçnh thæåìng laì: βmin IB − IR3 IR3 + N I1 < β min IB ⇒ N < (*) I1 N: säú låïn nháút thoía maîn âiãöu kiãûn (*) âæåüc goüi laì Fanout cuía pháön tæí logic DTL. 3.2.3.3. Fanin (Hãû säú màõc maûch ngoî vaìo) Goüi M laì Fanin cuía 1 pháön tæí logic thç M âæåüc âënh nghéa nhæ sau: Âoï chênh laì säú ngoî vaìo logic cæûc âaûi cuía mäüt pháön tæí logic. Âäúi våïi caïc pháön tæí logic thæûc hiãûn chæïc nàng cäüng logic, thç säú læåüng M låïn nháút laì 4 ngoî vaìo. Âäúi våïi caïc pháön tæí logic thæûc hiãûn chæïc nàng nhán logic, thç säú læåüng M låïn nháút laì 6 ngoî vaìo. Âäúi våïi hoü logic CMOS thç coï M nhiãöu hån nhæng cuîng khäng quaï 8 ngoî vaìo. 3.2.3.4. Âäü chäúng nhiãùu Âäü äøn âënh nhiãùu laì tiãu chuáøn âaïnh giaï âäü nhaûy cuía maûch logic âäúi våïi taûp ám xung trãn âáöu vaìo.