Bài giảng Kỹ thuật số ứng dụng

94 trang phuongnguyen 50

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Kỹ thuật số ứng dụng", để 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:

bai_giang_ky_thuat_so_ung_dung.pdf

Nội dung text: Bài giảng Kỹ thuật số ứng dụng

TRѬӠNG ĈҤI HӐC BÁCH KHOA ĈÀ NҸNG KHOA Ĉ,ӊN TӰ VIӈN THÔNG oOo BÀI GIҦNG .Ӻ THUҰT SӔӬNG DӨNG Ĉà Nҹng, 08 / 2006
Chѭѫng 1. Ĉҥi sӕ Boole Trang 1 Chѭѫng 1 ĈҤI SӔ BOOLE 1.1. HӊĈӂM NHӎ PHÂN VÀ MÃ 1.1.1. HӋ thӕng sӕÿӃm 1. Khái niӋm và phân loҥi hӋÿӃm +ӋÿӃm là tұp hӧp các phѭѫng pháp gӑi và biӇu diӉn các con sӕ bҵng các kí hiӋu có giá trӏ sӕ Oѭӧng xác ÿӏnh gӑi là các chӳ sӕ. Có thӇ chia các hӋÿӃm làm hai loҥi: hӋÿӃm theo vӏ trí và hӋÿӃm không theo vӏ trí. a. H͏ÿ͇m theo v͓ trí: +ӋÿӃm theo vӏ trí là hӋÿӃm mà trong ÿó giá trӏ sӕ lѭӧng cӫa chӳ sӕ còn phө thuӝc vào vӏ trí cӫa nó ÿӭng trong con sӕ cө thӇ. Ví dͭ: HӋ thұp phân là mӝt hӋÿӃm theo vӏ trí. Sӕ 1991 trong hӋ thұp phân ÿѭӧc biӇu diӉn bҵng 2 chӳ sӕ “1” và “9”, nhѭng do vӏ trí ÿӭng cӫa các chӳ sӕ này trong con sӕ là khác nhau nên sӁ mang các giá trӏ sӕ lѭӧng khác nhau, chҷng hҥn chӳ sӕ “1” ӣ vӏ trí hàng ÿѫn vӏ biӇu diӉn cho giá trӏ sӕ Oѭӧng là 1 song chӳ sӕ “1” ӣ vӏ trí hàng nghìn lҥi biӇu diӉn cho giá trӏ sӕ lѭӧng là 1000, hay chӳ sӕ “9” khi ӣ hàng chөc biӇu diӉn giá trӏ là 90 còn khi ӣ hàng trăm lҥi biӇu diӉn cho giá trӏ là 900. b. H͏ÿ͇m không theo v͓ trí: +ӋÿӃm không theo vӏ trí là hӋÿӃm mà trong ÿó giá trӏ sӕ lѭӧng cӫa chӳ sӕ không phө thuӝc vào Yӏ trí cӫa nó ÿӭng trong con sӕ. +ӋÿӃm La Mã là mӝt hӋÿӃm không theo vӏ trí. HӋÿӃm này sӱ dөng các ký tӵ “I”, “V”, “X” ÿӇ biӇu diӉn các con sӕ, trong ÿó “I” biӇu diӉn cho giá trӏ sӕ lѭӧng 1, “V” biӉu diӉn cho giá trӏ sӕ Oѭӧng 5, “X” biӇu diӉn cho giá trӏ sӕ lѭӧng 10 mà không phө thuӝc vào vӏ trí các chӳ sӕ này ÿӭng trong con sӕ cө thӇ. Các hӋÿӃm không theo vӏ trí sӁ không ÿѭӧc ÿӅ cұp ÿӃn trong giáo trình này. 2. Cѫ sӕ cӫa hӋÿӃm 0ӝt sӕ A bҩt kǤ có thӇ biӇu diӉn bҵng dãy sau: A= am-1am-2 a0a-1 a-n Trong ÿó ai là các chӳ sӕ, ( i = - n ¸ m -1); i là các hàng sӕ, i nhӓ: hàng trҿ, i lӟn: hàng già. Giá trӏ sӕ lѭӧng cӫa các chӳ sӕ ai sӁ nhұn mӝt giá trӏ nào ÿó sao cho thӓa mãn bҩt ÿҷng thӭc sau: 0 £ ai £ N -1 (ai nguyên) N ÿѭӧc gӑi là cѫ sӕ cӫa hӋÿӃm. &ѫ sӕ cӫa mӝt hӋÿӃm là sӕ lѭӧng ký tӵ phân biӋt ÿѭӧc sӱ Gөng trong mӝt hӋÿӃm. Các hӋ thӕng sӕÿӃm ÿѭӧc phân biӋt vӟi nhau bҵng mӝt cѫ sӕ N cӫa hӋ ÿӃm ÿó. Mӛi ký tӵ biӇu diӉn mӝt chӳ sӕ.
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 2 Trong ÿӡi sӕng hҵng ngày chúng ta quen sӱ dөng hӋÿӃm thұp phân (decimal) vӟi N=10. Trong KӋ thӕng sӕ còn sӱ dөng nhӳng hӋÿӃm khác là hӋÿӃm nhӏ phân (binary) vӟi N=2, hӋÿӃm bát phân (octal) vӟi N=8 và hӋÿӃm thұp lөc phân (hexadecimal) vӟi N=16. - HӋ nhӏ phân : N =2 Þ ai = 0, 1. - HӋ thұp phân : N =10 Þ ai = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. - HӋ bát phân : N =8 Þ ai = 0, 1, 2, 3, 4, 5, 6, 7. - HӋ thұp lөc phân : N =16 Þ ai = 0, 1, 2, 8, 9, A, B, C,D, E, F. Khi ÿã xuҩt hiӋn cѫ sӕ N, ta có thӇ biӇu diӉn sӕ A dѭӟi dҥng mӝt ÿa thӭc theo cѫ sӕ N, ÿѭӧc ký hiӋu là 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) = å ai N (1.1) i=-n 9ͣi N=10 (h͏ th̵p phân): m-1 m-2 0 -n A(10) = am-1.10 + am-2.10 + + a0.10 + + a-n.10 3 2 1 0 -1 -2 -3 1999,959(10) =1.10 + 9.10 + 9.10 + 9.10 + 9.10 + 5.10 + 9.10 9ͣi N=2 (h͏ nh͓ phân): m-1 m-2 0 -n A(2) = am-1.2 + am-2.2 + + a0.2 +a-n2 3 2 1 0 1101(2) = 1.2 +1.2 + 0.2 + 1.2 = 13(10) 9ͣi N=16 (h͏ th̵p lͭc phân): m-1 m-2 0 -1 -n A(16) = am-1.16 + am-2.16 + + a0.16 + a-116 + + a-n16 2 1 0 3FF(16) = 3.16 + 15.16 + 15.16 = 1023(10) 9ͣi N=8 (h͏ bát phân): m-1 m-2 0 -1 -n A(8) = am-1.8 + am-2.8 + + a0.8 + a-1.8 + + a-n.8 2 1 0 376(8) = 3.8 + 7.8 + 6.8 = 254(10) Nhѭ vұy, biӇu thӭc (1.1) cho phép ÿәi các sӕӣ bҩt kǤ hӋ nào sang hӋ thұp phân (hӋ 10). 3. Ĉәi cѫ sӕ a. Ĉ͝i tͳ c˯ s͙ d sang c˯ s͙ 10 ĈӇ chuyӇn ÿәi mӝt sӕӣ hӋÿӃm cѫ sӕ d sang hӋÿӃm cѫ sӕ 10 ngѭӡi ta khai triӇn con sӕ trong cѫ Vӕ d dѭӟi dҥng ÿa thӭc theo cѫ sӕ cӫa nó (theo biӇu thӭc 1.1). Ví dͭ 1.1 Ĉәi sӕ 1101(2)ӣ hӋ nhӏ phân sang hӋ thұp phân nhѭ sau: 3 2 1 0 1011(2) = 1.2 + 0.2 + 1.2 + 1.2 = 11(10) b. Ĉ͝i tͳ c˯ s͙ 10 sang c˯ s͙ d ĈӇ chuyӇn ÿәi mӝt sӕ tӯ cѫ sӕ 10 sang cѫ sӕ d (d = 2, 8, 16) ngѭӡi ta lҩy con sӕ trong cѫ sӕ 10 chia liên tiӃp cho d ÿӃn khi thѭѫng sӕ bҵng không thì dӯng lҥi. KӃt quҧ chuyӇn ÿәi có ÿѭӧc trong KӋÿӃm cѫ sӕ d là tұp hӧp các sӕ dѭ cӫa phép chia ÿѭӧc viӃt theo thӭ tӵ ngѭӧc lҥi, nghƭa là sӕ dѭ ÿҫu tiên có trӑng sӕ nhӓ nhҩt. (xem ví dө 1.2)
Chѭѫng 1. Ĉҥi sӕ Boole Trang 3 Ví dͭ 1.2: 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 .Ӄt luұn: Gӑi d1, d2, ,dn lҫn lѭӧt là dѭ sӕ cӫa phép chia sӕ thұp phân cho cѫ sӕ d ӣ lҫn thӭ 1, 2, 3, 4, , n thì kӃt quҧ chuyӇn ÿәi mӝt sӕ tӯ hӋÿӃm cѫ sӕ 10 (thұp phân) sang hӋÿӃm cѫ sӕ d sӁ là: dndn-1dn-2 d1, nghƭa là dѭ sӕ sau cùng cӫa phép chia là bít có trӑng sӕ cao nhҩt (MSB), còn dѭ sӕÿҫu tiên là bít có trӑng sӕ nhӓ nhҩt (LSB). Trong các ví dө trên, cѫ sӕ cӫa hӋÿӃm ÿѭӧc ghi ӣ dҥng chӍ sӕ bên dѭӟi. Ngoài ra cǊng có thӇ ký Wӵ chӳÿӇ phân biӋt nhѭ sau: B - HӋ nhӏ phân (Binary) O - HӋ bát phân (Octal) D - HӋ thұp phân (Decmal) H - HӋ thұp lөc phân (Hexadecimal) Ví dͭ: 1010B có nghƭa là 1010(2) 37FH có nghƭa là 37F(16) & Quy t̷c chuy͋n ÿ͝i giͷa các h͏ÿ͇m c˯ s͙ 2, 8, 16 ? 1.1.2. HӋÿӃm nhӏ phân 1. Khái niӋm +ӋÿӃm nhӏ phân, còn gӑi là hӋÿӃm cѫ sӕ 2, là hӋÿӃm trong ÿó ngѭӡi ta chӍ sӱ dөng hai kí hiӋu 0 và 1 ÿӇ biӇu diӉn tҩt cҧ các sӕ. Hai ký hiӋu ÿó gӑi chung là bit hoһc digit, nó ÿһc trѭng cho mҥch ÿLӋn tӱ có hai trҥng thái әn ÿӏnh hay còn gӑi là 2 trҥng thái bӅn cӫa FLIP- FLOP (ký hiӋu là FF). Trong hӋÿӃm nhӏ phân ngѭӡi ta quy ѭӟc nhѭ sau: - Mӝt nhóm 4 bít gӑi là 1 nibble. - Mӝt nhóm 8 bít gӑi là 1 byte. - Nhóm nhiӅu bytes gӑi là tӯ (word), có thӇ có tӯ 2 bytes (16 bít), tӯ 4 bytes (32 bít), Xét sӕ nhӏ phân 4 bít: a3a2a1a0. BiӇu diӉn dѭӟi dҥng ÿa thӭc theo cѫ sӕ cӫa nó là: 3 2 1 0 a3a2a1a0 (2) = a3.2 + a2.2 + a1.2 + a0.2 Trong ÿó: - 23, 22, 21, 20 (hay 8, 4, 2, 1) ÿѭӧc gӑi là các trӑng sӕ. - a0 ÿѭӧc gӑi là bit có trӑng sӕ nhӓ nhҩt, hay còn gӑi bit có ý nghƭa nhӓ nhҩt (LSB - Least Significant Bit), còn gӑi là bít trҿ nhҩt. - a3 ÿѭӧc gӑi là bit có trӑng sӕ lӟn nhҩt, hay còn gӑi là bít có ý nghƭa lӟn nhҩt (MSB - Most Significant Bit), còn gӑi là bít già nhҩt.
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 4 Nhѭ vұy, vӟi sӕ nhӏ phân 4 bit a3a2a1a0 trong ÿó mӛi chӳ sӕ ai (i tӯ 0 ÿӃn 3) chӍ nhұn ÿѭӧc hai giá trӏ {0,1} ta có 24 = 16 tә hӧp nhӏ phân phân biӋt. %ҧng sau ÿây liӋt kê các tә hӧp mã nhӏ phân 4 bít cùng các giá trӏ sӕ thұp phân, sӕ bát phân và sӕ thұp lөc phân tѭѫng ӭng. 6ӕ thұp phân a3a2a1a0 Sӕ bát phân Sӕ thұp lөc phân 0 0000 00 0 1 0001 01 1 2 0010 02 2 3 0011 03 3 4 0100 04 4 5 0101 05 5 6 0110 06 6 7 0111 07 7 8 1000 10 8 9 1001 11 9 10 1010 12 A 11 1011 13 B 12 1100 14 C 13 1101 15 D 14 1110 16 E 15 1111 17 F %̫ng 1.1. Các t͝ hͫp mã nh͓ phân 4 bít 6ӵ chuyӇn ÿәi giӳa các hӋ thӕng sӕ ÿӃm khác nhau giӳ vai trò quan trӑng trong máy tính sӕ. Chúng ta biӃt rҵng 23 = 8 và 24 = 16, tӯ bҧng mã trên có thӇ nhұn thҩy mӛi chӳ sӕ trong hӋ bát phân Wѭѫng ÿѭѫng vӟi mӝt nhóm ba chӳ sӕ (3 bít) trong hӋ nhӏ phân, mӛi chӳ sӕ trong hӋ thұp lөc phân Wѭѫng ÿѭѫng vӟi mӝt nhóm bӕn chӳ sӕ (4 bít) trong hӋ nhӏ phân. Do ÿó, khi biӇu diӉn sӕ nhӏ phân nhiӅu bit trên máy tính ÿӇ tránh sai sót ngѭӡi ta thѭӡng biӇu diӉn thông qua sӕ thұp phân hoһc thұp Oөc phân hoһc bát phân. Ví dͭ 1.3: Xét viӋc biӇu diӉn sӕ nhӏ phân 1011111011111110(2). 1 3 7 3 7 6 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 B E F E 9ұy, có thӇ biӇu diӉn : 137376(8) theo hӋ bát phân hoһc : BEFE(H) theo hӋ thұp lөc phân. & Vͣi s͙ nh͓ phân n bít có bao nhiêu t͝ hͫp nh͓ phân khác nhau? Xét tr˱ͥng hͫp s͙ nh͓ phân 8 bít (n=8) a7a6a5a4a3a2a1a0 có bao nhiêu t͝ hͫp nh͓ phân (tͳ mã nh͓ phân) khác nhau? 2. Các phép tính trên sӕ nhӏ phân a. Phép c͡ng
Chѭѫng 1. Ĉҥi sӕ Boole Trang 5 ĈӇ 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í dͭ 1.4: + 3 ® + 0011 2 ® 0010 2 0 5 ® 0101 = 1.2 + 1.2 = 5(10) b. Phé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í dͭ 1.5: - 7 ® - 0111 5 ® 0101 3 2 1 0 2 ® 0010 = 0.2 + 0.2 + 1.2 + 0.2 = 2(10) c. Phép nhân 0 . 0 = 0 0 . 1 = 0 1 . 0 = 0 1 . 1 = 1 Ví dͭ 1.6: 7 ® 0111 x x 5 ® 0101 35 0111 0000 0111 0000 5 1 0 0100011 = 1.2 + 1.2 + 1.2 = 35(10) d. Phép chia 0 : 1 = 0 1 : 1 = 1 /˱u ý: Khi chia s͙ chia ph̫i khác 0 Ví dͭ 1.7: 10 5 ® 1010 101 2 101 10(2) = 2(10) 00 0
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 6 1.1.3. Khái niӋm vӅ mã 1. Ĉҥi cѭѫng Trong ÿӡi sӕng hàng ngà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 máy tính và các hӋ thӕng sӕ chӍ xӱ lý các dӳ liӋu nhӏ phân. Do ÿó, mӝt vҩn ÿӅÿһt ra là làm thӃ nào tҥo ra mӝt giao diӋn dӉ dàng giӳa ngѭӡi và máy tính, nghƭa là máy tính thӵc hiӋn ÿѭӧc nhӳng bài toán do con ngѭӡi ÿһt ra. Vì các máy tính sӕ hiӋn nay chӍ hiӇu các sӕ 0 và sӕ 1, nên bҩt kǤ thông tin nào dѭӟi dҥng các chӳ Vӕ, chӳ cái hoһc các ký tӵ phҧi ÿѭӧc biӃn ÿәi thành dҥng sӕ nhӏ phân trѭӟc khi nó có thӇÿѭӧc xӱ lý bҵng các mҥch sӕ. ĈӇ thӵc hiӋn ÿLӅu ÿó, ngѭӡi ta ÿһt ra vҩn ÿӅ vӅ mã hóa dӳ liӋu. Nhѭ vұy, mã hóa là quá trình biӃn ÿәi nhӳng ký hiӋu quen thuӝc cӫa con ngѭӡi sang nhӳng ký hiӋu quen thuӝc vӟi máy tính. Nhӳng sӕ liӋu ÿã mã hóa này ÿѭӧc nhұp vào máy tính, máy tính tính toán xӱ lý và sau ÿó máy tính thӵc hiӋn quá trình ngѭӧc lҥi là giҧi mã ÿӇ chuyӇn ÿәi các bít thông tin nhӏ phân thành các ký hiӋu quen thuӝc vӟi con ngѭӡi mà con ngѭӡi có thӇ hiӇu ÿѭӧc. Các lƭnh vӵc mã hóa bao gӗm: - Mã hóa sӕ thұp phân - Mã hóa ký tӵ - Mã hóa tұp lӋnh - Mã hóa tiӃng nói - Mã hóa hình ҧnh v v Phҫn tiӃp theo chúng ta khҧo sát lƭnh vӵc mã hóa ÿѫn giҧn nhҩt là mã hóa sӕ thұp phân bҵng cách sӱ dөng các tӯ mã nhӏ phân. ViӋc mã hóa ký tӵ, tұp lӋnh, tiӃng nói, hình ҧnh ÿӅu dӵa trên cѫ Vӣ mã hóa sӕ thұp phân. 2. Mã hóa sӕ thұp phân a. Khái ni͏m ĈӇ mã hóa sӕ thұp phân ngѭӡi ta sӱ dөng các sӕ nhӏ phân 4 bit (a3a2a1a0) theo quy tҳc sau: 0® 0000 ; 5 ® 0101 1® 0001 ; 6 ® 0110 2® 0010 ; 7 ® 0101 3® 0011 ; 8 ® 1000 4® 0100 ; 9 ® 1001 Các sӕ nhӏ phân dùng ÿӇ mã hóa các sӕ thұp phân ÿѭӧc gӑi là các sӕ BCD (Binary Coded Decimal: Sӕ thұp phân ÿѭӧc mã hóa bҵng sӕ nhӏ phân). b. Phân lo̩i Khi sӱ dөng sӕ nhӏ phân 4 bit ÿӇ mã hóa các sӕ thұp phân tѭѫng ӭng vӟi 24 = 16 tә hӧp mã nhӏ phân phân biӋt. Do viӋc chӑn 10 tә hӧp trong 16 tә hӧp ÿӇ mã hóa các ký hiӋu thұp phân tӯ 0 ÿӃn 9 mà trong thӵc tӃ xuҩt hiӋn nhiӅu loҥi mã BCD khác nhau. 0һc dù tӗn tҥi nhiӅu loҥi mã BCD khác nhau, nhѭng có thӇ chia làm hai loҥi chính: Mã BCD có tr͕ng s͙ và Mã BCD không có tr͕ng s͙.
Chѭѫng 1. Ĉҥi sӕ Boole Trang 7 b1. Mã BCD có trӑng sӕ là loҥi mã cho phép phân tích thành ÿa thӭc theo trӑng sӕ cӫa nó. Mã BCD có trӑng sӕÿѭӧc chia làm 2 loҥi là: mã BCD tӵ nhiên và mã BCD sӕ hӑc. Mã BCD t͹ nhiên là loҥi mã mà trong ÿó các trӑng sӕ thѭӡng ÿѭӧc sҳp xӃp theo thӭ tӵ tăng Gҫn. Ví dө: Mã BCD 8421, BCD 5421. Mã BCD s͙ h͕c là loҥi mã mà trong ÿó có tәng các trӑng sӕ luôn luôn bҵng 9.Ví dө: BCD 2421, BCD 5121, BCD 8 4-2-1 Ĉһc trѭng cӫa mã BCD sӕ hӑc là có tính chҩt ÿӕi xӭng qua mӝt ÿѭӡng trung gian. Do Yұy, ÿӇ tìm tӯ mã BCD cӫa mӝt sӕ thұp phân nào ÿó ta lҩy bù (ÿҧo) tӯ mã BCD cӫa sӕ bù 9 Wѭѫng ӭng. Ví dͭ xét mã BCD 2421. Ĉây là mã BCD sӕ hӑc (tәng các trӑng sӕ bҵng 9), trong ÿó sӕ 3 (thұp phân) có tӯ mã là 0011, sӕ 6 (thұp phân) là bù 9 cӫa 3. Do vұy, có thӇ suy ra tӯ mã cӫa 6 Eҵng cách lҩy bù tӯ mã cӫa 3, nghƭa là lҩy bù 0011, ta sӁ có tӯ mã cӫa 6 là 1100. b2. Mã BCD không có trӑng sӕ là loҥi mã không cho phép phân tích thành ÿa thӭc theo trӑng Vӕ cӫa nó. Các mã BCD không có trӑng sӕ là: Mã Gray, Mã Gray thӯa 3. Ĉһc trѭng cӫa mã Gray là bӝ mã trong ÿó hai tӯ mã nhӏ phân ÿӭng kӃ tiӃp nhau bao giӡ cǊng chӍ khác nhau 1 bit. Ví dө: Mã Gray: 2 ® 0011 Còn vӟi mã BCD 8421: 3 ® 0010 3 ® 0011 4® 0110 4 ® 0100 Các bҧng dѭӟi ÿây trình bày mӝt sӕ loҥi mã thông dөng. %ҧng 1.2: Các mã BCD t͹ nhiên. BCD 8421 BCD 5421 BCD quá 3 6ӕ 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
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 8 %ҧng 1.3: Các mã BCD s͙ h͕c BCD 2421 BCD 5121 BCD 84-2-1 6ӕ 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 1 1 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 %ҧng 1.4: BCD t͹ nhiên và mã Gray. BCD 8421 BCD quá 3 Mã Gray Gray quá 3 6ӕ thұp a a a A c c c c G G G G g g g g 3 2 1 3 2 1 0 3 2 1 0 3 2 1 0 phân 0 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 Chú ý: Mã Gray ÿѭӧc suy ra tӯ mã BCD 8421 bҵng cách: các bit 0,1 ÿӭng sau bit 0 (ӣ mã BCD 8421) khi chuyӇn sang mã Gray ÿѭӧc giӳ nguyên, còn các bit 0,1 ÿӭng sau bit 1 (ӣ mã BCD 8421) khi chuyӇn sang mã Gray thì ÿҧo bít, nghƭa là tӯ bit 1 thành bit 0 và bit 0 thành bit 1. 1.2. CÁC TIÊN Ĉӄ VÀ ĈӎNH LÝ ĈҤI SӔ BOOLE Trong các mҥch sӕ, các tín hiӋu thѭӡng ÿѭӧc cho ӣ 2 mӭc ÿLӋn áp, ví dө: 0V và 5V. Nhӳng linh kiӋn ÿLӋn tӱ dùng trong mҥch sӕ làm viӋc ӣ mӝt trong hai trҥng thái, ví dө Transistor lѭӥng cӵc (BJT) làm viӋc ӣ hai chӃÿӝ là tҳt hoһc dүn bão hoà Do vұy, ÿӇ mô tҧ các mҥch sӕ ngѭӡi ta dùng KӋ nhӏ phân (binary), hai trҥng thái cӫa các linh kiӋn trong mҥch sӕ ÿѭӧc mã hoá tѭѫng ӭng là 0 hoһc 1. 0ӝt bӝ môn ÿҥi sӕ phát triӇn tӯ cuӕi thӃ kӹ 19 mang tên ngѭӡi sáng lұp ra nó: ÿҥi sӕ Boole, còn ÿѭӧc gӑi là ÿҥi sӕ logic, thích hӧp cho viӋc mô tҧ mҥch sӕ. Ĉҥi sӕ Boole là công cө toán hӑc quan
Chѭѫng 1. Ĉҥi sӕ Boole Trang 9 trӑng ÿӇ phân tích và thiӃt kӃ các mҥch sӕ, ÿѭӧc dùng làm chìa khoá ÿӇÿi sâu vào mӑi lƭnh vӵc liên quan ÿӃn kӻ thuұt sӕ. 1.2.1. Các tiên ÿӅ cӫa ÿҥi sӕ Boole Cho mӝt tұp hӧp B hӳu hҥn trong ÿó ta trang bӏ các phép toán + (cӝng logic), x (nhân logic), - (bù logic/nghӏch ÿҧo logic) và hai phҫn tӱ 0 và 1 lұp thành mӝt cҩu trúc ÿҥi sӕ Boole (ÿӑc là Bun). " x,y Î B thì: x+y Î B, x*y Î B và thӓa mãn 5 tiên ÿӅ sau: 1. Tiên ÿӅ giao hoán "x,y Î B: x + y = y + x 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 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) 4. Tiên ÿӅ vӅ phҫn tӱ trung hòa Trong tұp B tӗn tҥi hai phҫn tӱ trung hòa là phҫn tӱ ÿѫn vӏ và phҫn tӱ không. Phҫn tӱÿѫn vӏ ký hiӋu là 1, phҫn tӱ không ký hiӋu là 0. "x Î B: x + 1 = 1 x . 1 = x x + 0 = x x . 0 = 0 5. Tiên ÿӅ vӅ phҫn tӱ bù "x Î B, bao giӡ cǊng tӗn tҥi phҫn tӱ bù tѭѫng ӭng, ký hiӋu x , sao cho luôn thӓa mãn: x + x = 1 và x. x = 0 1Ӄu B = B* = {0,1} (B* chӍ gӗm 2 phҫn tӱ 0 và 1) và thӓa mãn 5 tiên ÿӅ trên thì cǊng lұp thành Fҩu trúc ÿҥi sӕ Boole nhѭng là cҩu trúc ÿҥi sӕ Boole nhӓ nhҩt. 1.2.2. Các ÿӏnh lý cѫ bҧn cӫa ÿҥi sӕ Boole 1. Vҩn ÿӅÿӕi ngүu trong ÿҥi sӕ Boole Hai mӋnh ÿӅ (hai biӇu thӭc, hai ÿӏnh lý) ÿѭӧc gӑi là ÿӕi ngүu vӟi nhau nӃu trong mӋnh ÿӅ này ngѭӡi ta thay phép toán cӝng thành phép toán nhân và ngѭӧc lҥi, thay 0 bҵng 1 và ngѭӧc lҥi, thì sӁ 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 là ÿúng thì mӋnh ÿӅ còn lҥi là ÿúng. Dѭӟi ÿây là ví dө vӅ các cһp mӋnh ÿӅÿӕi ngүu vӟi nhau. Ví dͭ 1.8: x.(y+z) = (x.y) + (x.z) Hai m͏nh ÿ͉ này là ÿ͙i ng̳u x + (y.z) = (x+y).(x+z) Ví dͭ 1.9: x + x = 1 Hai m͏nh ÿ͉ này là ÿ͙i ng̳u x. x = 0
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 10 2. Các ÿӏnh lý cѫ bҧn a. Ĉ͓nh lí 1 (Ĉ͓nh lý v͉ ph̯n t͵ bù là duy nh̭t) "x, y Î B, ta có: x + y =1ïü ý Þ y = x là duy nhҩt (x và y là 2 phҫn tӱ bù cӫa nhau) x.y = 0 þï Phҫn tӱ bù cӫa mӝt phҫn tӱ bҩt kǤ là duy nhҩt. b. Ĉ͓nh lí 2 (Ĉlý v͉ s͹ÿ͛ng nh̭t cͯa phép c͡ng và phép nhân logic) "x Î B, ta có: x + x +. . . . . + x = x x. x. x. . . . . . x = x c. Ĉ͓nh lý 3 (Ĉ͓nh lý v͉ phͯÿ͓nh hai l̯n) "x Î B, ta có: x = x d. Ĉ͓nh lí 4 (Ĉ͓nh lý De Morgan) "x, y, z Î B, ta có: x + y + z = x.y.z x.y.z = x + y + z +Ӌ quҧ: "x, y, z Î B, ta có: x + y + z = x + y + z = x.y.z x. y. z = x.y.z = x + y + z e. Ĉ͓nh lí 5 (Ĉ͓nh lý dán) "x, y Î B, ta có: x. ( x + y) = x.y x+ (x .y) = x + y f. Ĉ͓nh lí 6 (Ĉ͓nh lý nu͙t) "x, y Î B, ta có: x + x. y = x x.(x + y) = x g. Ĉ͓nh lí 7 (Quy t̷c tính ÿ͙i vͣi h̹ng) 9ӟi 0, 1 Î B, ta có: 0 = 1 1 = 0
Chѭѫng 1. Ĉҥi sӕ Boole Trang 11 1.3. HÀM BOOLE VÀ CÁC PHѬѪNG PHÁP BIӆU DIӈN 1.3.1. Hàm Boole 1. Ĉӏnh nghƭa Hàm Boole là mӝt ánh xҥ tӯÿҥi sӕ Boole vào chính nó. Nghƭa là "x, y Î B ÿѭӧc gӑi là các biӃn Boole thì hàm Boole, ký hiӋu là f, ÿѭӧc hình thành trên cѫ sӣ liên kӃt các biӃn Boole bҵng các phép toán + (cӝng logic), x / . (nhân logic), nghӏch ÿҧo logic (-). Hàm Boole ÿѫn giҧn nhҩt là hàm Boole theo 1 biӃn Boole, ÿѭӧc cho nhѭ sau: f(x) = x, f(x) = x , f(x) = a (a là hҵng sӕ ) Trong trѭӡng hӧp tәng quát, ta có hàm Boole theo n biӃn Boole ÿѭӧc ký hiӋu nhѭ sau: f(x1, x2, , xn) 2. Các tính chҩt cӫa hàm Boole 1Ӄu f(x1, x2, , xn) là mӝt hàm Boole thì: - a.f(x1, x2, , xn) cǊng là mӝt hàm Boole. -f (x1, x2, , xn) cǊng là mӝt hàm Boole. 1Ӄu f1(x1, x2, , xn) và f2(x1, x2, , xn) là nhӳng hàm Boole thì: - f1(x1, x2, , xn) + f2(x1, x2, , xn) cǊng là mӝt hàm Boole. - f1(x1, x2, , xn).f2(x1, x2, , xn) cǊng là mӝt hàm Boole. 9ұy, mӝt hàm Boole f cǊng ÿѭӧc hình thành trên cѫ sӣ liên kӃt các hàm Boole bҵng các phép toán + (cӝng logic), x (.) (nhân logic) hoһc nghӏch ÿҧo logic (-). 3. Giá trӏ cӫa hàm Boole Giҧ sӱ f(x1, x2, , xn) là mӝt hàm Boole theo n biӃn Boole. Trong f ngѭӡi ta thay các biӃn xi bҵng các giá trӏ cө thӇ ai (i = 1, n ) thì giá trӏ f (a1, a2, , an) ÿѭӧc gӑi là giá trӏ cӫa hàm Boole theo n biӃn. Ví dͭ 1.10: Xét hàm f(x1, x2 ) = x1 + x2 Xét trong tұp B = B* ={0,1}, ta có các trѭӡng hӧp sau (lѭu ý ÿây là phép cӝng logic hay còn gӑi phép toán HOҺC / phép OR): - x1 = 0, x2 = 0 ® f(0,0) = 0 + 0 = 0 - x1 = 0, x2 = 1 ® f(0,1) = 0 + 1 = 1 x1 x2 f(x1, x2) = x1+ x2 - x1 = 1, x2 = 0 ® f(1,0) = 1 + 0 = 1 0 0 0 - x1 = 1, x2 = 1 ® f(1,1) = 1 + 1 = 1 0 1 1 Ta lұp ÿѭӧc bҧng giá trӏ cӫa hàm trên. 1 0 1 1 1 1 Ví dͭ 1.11: Xét hàm cho bӣi biӇu thӭc sau: f(x1, x2, x3) = x1 + x2.x3 Xét tұp B = B* = {0,1}. Hoàn toàn tѭѫng tӵ ta lұp ÿѭӧc bҧng giá trӏ cӫa hàm:
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 12 x1 x2 x3 f (x1, x2, x3) = 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 1.3.2. Các phѭѫng pháp biӇu diӉn hàm Boole 1. Phѭѫng pháp biӇu diӉn hàm bҵng bҧng giá trӏ Phѭѫng pháp này gӗm mӝt bҧng ÿѭӧc chia làm hai phҫn: - Mӝt phҫn dành cho biӃn ÿӇ ghi các tә hӧp giá trӏ có thӇ có cӫa biӃn vào. - Mӝt phҫn dành cho hàm ÿӇ ghi các giá trӏ cӫa hàm ra tѭѫng ӭng vӟi các tә hӧp biӃn vào. Bҧng giá trӏ còn ÿѭӧc gӑi là bҧng chân trӏ hay bҧng chân lý (TRUE TABLE). Nhѭ vұy vӟi mӝt hàm Boole n biӃn bҧng chân lý sӁ có: - (n+1) Fӝt: n cӝt tѭѫng ӭng vӟi n biӃn vào, 1 cӝt tѭѫng ӭng vӟi giá trӏ ra cӫa hàm. - 2n hàng: 2n giá trӏ khác nhau cӫa tә hӧp n biӃn. Ví dͭ 1.12: Hàm 3 biӃn f(x1, x2, x3) có thӇÿѭӧc cho bҵng bҧng giá trӏ nhѭ sau: 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 2. Phѭѫng pháp giҧi tích Ĉây là phѭѫng pháp biӇu diӉn hàm logic bҵng các biӇu thӭc ÿҥi sӕ. Phѭѫng pháp này có 2 dҥng: Wәng cӫa các tích sӕ hoһc tích cӫa các tәng sӕ. 'ҥng tәng cӫa các tích sӕ gӑi là dҥng chính tҳc thӭ nhҩt (Dҥng chính tҳc 1). 'ҥng tích cӫa các tәng sӕ gӑi là dҥng chính tҳc thӭ hai (Dҥng chính tҳc 2). Hai dҥng chính tҳc này là ÿӕi ngүu nhau. 'ҥng tәng các tích sӕ còn gӑi là dҥng chu̱n t̷c tuy͋n (CTT), dҥng tích các tәng sӕ còn gӑi là Gҥng chu̱n t̷c h͡i (CTH). a. D̩ng chính t̷c 1(D̩ng t͝ng cͯa các tích s͙) Xét các hàm Boole mӝt biӃn ÿѫn giҧn: f(x) = x, f(x) = x , f(x) = a (a là hҵng sӕ). Ĉây là nhӳng trѭӡng hӧp có thӇ có ÿӕi vӟi hàm Boole 1 biӃn.
Chѭѫng 1. Ĉҥi sӕ Boole Trang 13 Chúng ta sͅÿi chͱng minh bi͋u thͱc t͝ng quát cͯa hàm logic 1 bi͇n s͙ÿ͙i vͣi d̩ng chính t̷c 1. Sau ÿó áp dͭng bi͋u thͱc t͝ng quát cͯa hàm 1 bi͇n ÿ͋ tìm bi͋u thͱc t͝ng quát cͯa hàm 2 bi͇n vͣi vi͏c xem 1 bi͇n là K̹ng s͙. Cu͙i cùng, chúng ta suy ra bi͋u thͱc t͝ng quát cͯa hàm logic n bi͇n cho tr˱ͥng hͫp d̩ng chính W̷c 1 (t͝ng các tích s͙). Xét f(x) = x: Ta có: x =0. x + 1.x P̿t khác: ìf ()1 = 1 f ()x = x Þ í îf ()0 = 0 Suy ra: f(x) = x có th͋ bi͋u di͍n: f(x) = x = f(0). x + f (1).x trong ÿó: f (0), f (1) ÿ˱ͫc g͕i là các giá tr͓ cͯa hàm Boole theo m͡t bi͇n. Xét f(x) = x : Ta có: x = 1. x + 0. x 0̿t khác: ìf ()1 = 0 f ()x = x Þ í îf ()0 =1 Suy ra: f(x) = x có th͋ bi͋u di͍n: f(x) = x = f(0). x + f(1).x Xét f(x) = a (a là h̹ng s͙): Ta có: a = a.1 = a.(x + x ) = a. x + a.x 0̿t khác: ìf ()1 = Į f ()x = Į Þ í îf ()0 = Į Suy ra f(x) = a có th͋ bi͋u di͍n: f(x) = a = f(0). x + f(1).x .Ӄt luұn: Dù f(x) = x, f(x) = x hay f(x) = a, ta ÿӅu có biӇu thӭc tәng quát cӫa hàm mӝt biӃn viӃt theo dҥng chính tҳc thӭ nhҩt nhѭ sau: f(x) = f(0). x + f(1).x 9ұy f(x) = f(0). x + f(1).x, trong ÿó f(0), f(1) là giá trӏ cӫa hàm Boole theo mӝt biӃn, ÿѭӧc gӑi là biӇu thӭc tәng quát cӫa hàm 1 biӃn viӃt ӣ G̩ng chính t̷c thͱ nh̭t (d̩ng t͝ng cͯa các tích). BiӇu thӭc tәng quát cӫa hàm hai biӃn f(x 1 , x 2 ): BiӇu thӭc tәng quát cӫa hàm 2 biӃn viӃt theo dҥng chính tҳc thӭ nhҩt cǊng hoàn toàn dӵa trên cách biӇu diӉn cӫa dҥng chính tҳc thӭ nhҩt cӫa hàm 1 biӃn, trong ÿó xem mӝt biӃn là hҵng sӕ. &ͭ th͋ là: n͇u xem x2 là h̹ng s͙, x1 là bi͇n s͙ và áp dͭng bi͋u thͱc t͝ng quát cͯa d̩ng chính t̷c thͱ nh̭t cho hàm 1 bi͇n, ta có: f(x1,x2) = f(0,x2). x 1 + f(1,x2).x1 Bây giͥ, các hàm f(0,x2) và f(1,x2) trͧ thành các hàm 1 bi͇n s͙ theo x2. Ti͇p tͭc áp dͭng bi͋u thͱc t͝ng quát cͯa d̩ng chính t̷c thͱ nh̭t cho hàm 1 bi͇n, ta có:
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 14 f(0,x2) = f(0,0). x 2 + f(0,1).x2 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 Ĉây chính là biӇu thӭc tәng quát cӫa dҥng chính tҳc thӭ nhҩt (dҥng tәng cӫa các tích sӕ) viӃt cho hàm Boole hai biӃn sӕ f(x1,x2). BiӇu thӭc tәng quát này có thӇ biӇu diӉn bҵng công thӭc sau: 22-1 Į1 Į2 f(x1,x2) = å f(Į1,Į2 )x1 x 2 e=0 Trong ÿó e là sӕ thұp phân tѭѫng ӭng vӟi mã nhӏ phân (a1,a2) và: x nӃu a = 1 Į 1 1 1 = x1 x 1 nӃu a1 = 0 x2 nӃu a2 = 1 Į 2 x 2 = x 2 nӃu a2 = 0 BiӇu thӭc tәng quát cho hàm Boole n biӃn: Tӯ biӇu thӭc tәng quát viӃt ӣ dҥng chính tҳc thӭ nhҩt cӫa hàm Boole 2 biӃn, ta có thӇ tәng quát hoá cho hàm Boole n biӃn f(x1,x2, ,xn) nhѭ sau: 2n -1 Į1 Į2 Įn f(x1,x2, ,xn) = åf(Į1,Į2 , ,Įn )x1 x 2 x n e=0 trong ÿó e là sӕ thұp phân tѭѫng ӭng vӟi mã nhӏ phân (a1,a2, ,an); và: x i nӃ u ai = 1 Į i xi = x i nӃu ai = 0 (vӟi i = 1, 2, 3, ,n) Ví dͭ 1.13: ViӃt biӇu thӭc cӫa hàm 3 biӃn theo dҥng chính tҳc 1: 23 -1 a1 a2 a3 f(x1,x2,x3) = å f (a1,a2,a3).x1 .x2 .x3 e=0 %ҧng dѭӟi ÿây cho ta giá trӏ cӫa sӕ thұp phân e và tә hӧp mã nhӏ phân (a1,a2,a3) tѭѫng ӭng: e a1 a2 a3 0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0 0 5 1 0 1 6 1 1 0 7 1 1 1
Chѭѫng 1. Ĉҥi sӕ Boole Trang 15 BiӇu thӭc cӫa hàm 3 biӃn viӃt theo dҥng tәng các tích nhѭ sau: 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 9̵y d̩ng chính t̷c thͱ nh̭t là d̩ng t͝ng cͯa các tích s͙ mà trong m͟i tích s͙ chͱa ÿ̯y ÿͯ các bi͇n Boole d˱ͣi d̩ng th̵t ho̿c d̩ng bù (ngh͓ch ÿ̫o). b. D̩ng chính t̷c 2 (tích cͯa các t͝ng s͙): 'ҥng chính tҳc 2 là dҥng ÿӕi ngүu cӫa dҥng chính tҳc 1 nên biӇu thӭc tәng quát cӫa dҥng chính tҳc 2 cho n biӃnÿѭӧc viӃt nhѭ sau: 2n -1 a1 a2 an f(x1, x2, , xn) = Õ [f(a1,a2,a3) + x1 + x2 + + xn )] e=0 trong ÿó e là sӕ thұp phân tѭѫng ӭng vӟi mã nhӏ phân (a1,a2, ,an); và: Į i x i nӃu ai = 1 xi = xi nӃu ai = 0 (vӟi i = 1, 2, 3, ,n) Ví dͭ 1.14: BiӇu thӭc cӫa hàm Boole 2 biӃn ӣ dҥng tích các tәng sӕ (dҥng chính tҳc 2) ÿѭӧc viӃt nhѭ sau: 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] Ví dͭ 1.15: BiӇu thӭc cӫa hàm Boole 3 biӃn ӣ dҥng chính tҳc 2: 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] 9̵y, d̩ng chính t̷c thͱ hai là d̩ng tích cͯa các t͝ng s͙ mà trong ÿó m͟i t͝ng s͙ này chͱa ÿ̯y ÿͯ các bi͇n Boole d˱ͣi d̩ng th̵t ho̿c d̩ng bù. Ví dͭ 1.16: Hãy viӃt biӇu thӭc biӇu diӉn cho hàm Boole 2 biӃn f(x1,x2) ӣ dҥng chính tҳc 1, vӟi bҧng giá trӏ Fӫa hàm ÿѭӧc cho nhѭ sau: x1 x2 f(x1,x2) 0 0 0 0 1 1 1 0 1 1 1 1 ViӃt dѭӟi dҥng chính tҳc 1 ta có: f(x1,x2) = f(0,0). x 1 x 2 + f(0,1). x 1.x2 + f(1,0).x1. x 2 + f(1,1).x1.x2
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 16 = 0. x 1 x 2 + 1. x 1.x2 + 1.x1. x 2 + 1.x1.x2 = x 1.x2 + x1. x 2 + x1.x2 Nhұn xét: · '̩ng chính t̷c thͱ nh̭t, t͝ng cͯa các tích s͙, là d̩ng li͏t kê ṱt c̫ các t͝ hͫp nh͓ phân các bi͇n vào sao cho t˱˯ng ͱng vͣi nhͷng t͝ hͫp ÿó giá tr͓ cͯa hàm ra b̹ng 1 ® ch͑ c̯n li͏t kê nhͷng t͝ hͫp bi͇n làm cho giá tr͓ hàm ra b̹ng 1. · Khi li͏t kê n͇u bi͇n t˱˯ng ͱng b̹ng 1 ÿ˱ͫc vi͇t ͧ d̩ng th̵t (xi), n͇u bi͇n t˱˯ng ͱng E̹ng 0 ÿ˱ͫc vi͇t ͧ d̩ng bù ( x i). Ví dͭ 1.17: ViӃt biӇu thӭc biӇu diӉn hàm f(x1,x2,x3) ӣ dҥng chính tҳc 2 vӟi bҧng giá trӏ cӫa hàm ra ÿѭӧc cho nhѭ sau: x3 x2 x1 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 ViӃt dѭӟi dҥng chính tҳc 2 (tích các tәng sӕ): 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) Áp dөng tiên ÿӅ vӅ phҫn tӱ trung hòa 0 và 1 ta có: x + 1 = 1, x . 1 = x x + 0 = x, x . 0 = 0 nên suy ra biӇu thӭc trên có thӇ viӃt gӑn lҥi: f(x1,x2,x3) = (x1+x2+x3).(x1+x2+ x 3).(x1+ x 2+x3) Nhұn xét: · '̩ng chính t̷c thͱ hai là d̩ng li͏t kê ṱt c̫ các t͝ hͫp nh͓ phân các bi͇n vào sao cho W˱˯ng ͱng vͣi nhͷng t͝ hͫp ÿó giá tr͓ cͯa hàm ra b̹ng 0 ® ch͑ c̯n li͏t kê nhͷng t͝ Kͫp bi͇n làm cho giá tr͓ hàm ra b̹ng 0. · Khi li͏t kê n͇u bi͇n t˱˯ng ͱng b̹ng 0 ÿ˱ͫc vi͇t ͧ d̩ng th̵t (xi), n͇u bi͇n t˱˯ng ͱng E̹ng 1 ÿ˱ͫc vi͇t ͧ d̩ng bù ( x i). Ví dөÿѫn giҧn sau giúp SV hiӇu rõ hѫn vӅ cách thành lұp bҧng giá trӏ cӫa hàm, tìm hàm mҥch và thiӃt kӃ mҥch.
Chѭѫng 1. Ĉҥi sӕ Boole Trang 17 Ví dͭ 1.18 Hãy thiӃt kӃ mҥch ÿLӋn sao cho khi công tҳc 1 ÿóng thì ÿèn ÿӓ, khi công tҳc 2 ÿóng ÿèn ÿӓ, khi Fҧ hai công tҳc ÿóng ÿèn ÿӓ ? /ӡi giҧi: Ĉҫu tiên, ta qui ÿӏnh trҥng thái cӫa các công tҳc và bóng ÿèn: - Công tҳc hӣ : 0 Ĉèn tҳt : 0 - Công tҳc ÿóng : 1 Ĉèn ÿӓ : 1 %ҧng trҥng thái mô tҧ hoҥt ÿӝng cӫa mҥch nhѭ sau: Công tҳc 1 Công tҳc 2 Trҥng thái ÿèn x1 x2 f(x1,x2) 0 0 0 0 1 1 1 0 1 1 1 1 7ӯ bҧng trҥng thái có thӇ viӃt biӇu thӭc cӫa hàm f(x1,x2) theo dҥng chính tҳc 1 hoһc chính tҳc 2. - Theo dҥng chính tҳc 1 ta có: f(x1, x2) = x 1.x2 + x1. x 2 + x1.x2 = x 1.x2 + x1( x 2 + x2) = x 1.x2 + x1 = x1 + x2 - Theo dҥng chính tҳc 2 ta có: f(x1, x2) = (0+x1+x2) = x1 + x2 Tӯ biӇu thӭc mô tҧ trҥng thái ÿӓ/tҳt cӫa ÿèn f(x1,x2) thҩy rҵng có thӇ thӵc hiӋn mҥch bҵng phҫn Wӱ logic HOҺC có 2 ngõ vào (cәng OR 2 ngõ vào). Bài t̵p áp dͭng: M͡t h͡i ÿ͛ng giám kh̫o g͛m 3 thành viên. M͟i thành viên có th͋ l͹a ch͕n Ĉ͚NG Ý ho̿c KHÔNG Ĉ͚NG Ý. K͇t qu̫ g͕i là Ĉ̨T khi ÿa s͙ các thành viên trong h͡i ÿ͛ng giám kh̫o Ĉ͚NG Ý, ng˱ͫc l̩i là KHÔNG Ĉ̨T. Hãy thi͇t k͇ m̩ch gi̫i quy͇t bài toán trên. 3. BiӇu diӉn hàm bҵng bҧng Karnaugh (bìa Karnaugh) Ĉây là cách biӇu diӉn lҥi cӫa phѭѫng pháp bҧng dѭӟi dҥng bҧng gӗm các ô vuông nhѭ hình bên. Trên bҧng này ngѭӡi ta bӕ trí các biӃn vào theo hàng hoһc theo cӝt cӫa Eҧng. Trong trѭӡng hӧp sӕ lѭӧng biӃn vào là chҹn, ngѭӡi ta bӕ trí sӕ lѭӧng biӃn vào theo hàng ngang bҵng sӕ lѭӧng biӃn vào theo cӝt dӑc cӫa bҧng. Trong trѭӡng hӧp sӕ lѭӧng biӃn vào là lҿ, ngѭӡi ta bӕ trí sӕ lѭӧng biӃn vào theo hàng ngang nhiӅu hѫn sӕ lѭӧng biӃn vào theo cӝt dӑc 1 biӃn hoһc ngѭӧc lҥi. Các tә hӧp giá trӏ cӫa biӃn vào theo hàng ngang hoһc theo cӝt dӑc cӫa bҧng ÿѭӧc bӕ trí sao cho khi ta ÿi tӯ mӝt ô sang mӝt ô lân cұn vӟi nó chӍ làm thay ÿәi mӝt giá trӏ cӫa biӃn, nhѭ vұy thӭ tӵ Eӕ trí hay sҳp xӃp các tә hӧp giá trӏ cӫa biӃn vào theo hàng ngang hoһc theo cӝt dӑc cӫa bҧng Karnaugh hoàn toàn tuân thӫ theo mã Gray.
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 18 Giá trӏ ghi trong mӛi ô vuông này chính là giá trӏ cӫa hàm ra tѭѫng ӭng vӟi các tә hӧp giá trӏ cӫa biӃn vào. Ӣ nhӳng ô mà giá trӏ hàm là không xác ÿӏnh (có thӇ bҵng 0 hay bҵng 1), có nghƭa là giá trӏ Fӫa hàm là tùy ý (hay tùy ÿӏnh), ngѭӡi ta kí hiӋu bҵng chӳ X. 1Ӄu hàm có n biӃn vào sӁ có 2n ô vuông. Phѭѫng pháp biӇu diӉn hàm bҵng bҧng Karnaugh chӍ thích hӧp cho hàm có tӕi ÿa 6 biӃn, nӃu Yѭӧt quá viӋc biӇu diӉn sӁ rҩt rҳc rӕi. 'ѭӟi ÿây là bҧng Karnaugh cho các trѭӡng hӧp hàm 2 biӃn, 3 biӃn, 4 biӃn và 5 biӃn: f(x1,x2) f x1 x1x2 x2 0 1 x3 00 01 11 10 0 0 1 1 f f x1=0 x1=1 x1x2 x2x3 x3x4 00 01 11 10 x4x5 00 01 11 10 10 11 01 00 00 00 01 01 11 11 10 10 1.4. TӔI THIӆU HÓA HÀM BOOLE 1.4.1. Ĉҥi cѭѫng Trong thiӃt bӏ máy tính ngѭӡi ta thѭӡng thiӃt kӃ gӗm nhiӅu modul (khâu) và mӛi modul này ÿѭӧc ÿһc trѭng bҵng mӝt phѭѫng trình logic. Trong ÿó, mӭc ÿӝ phӭc tҥp và ÿӝәn ÿӏnh cӫa sѫÿӗ tùy thuӝc vào phѭѫng trình logic biӇu diӉn chúng ӣ dҥng tӕi thiӇu hay chѭa. ĈӇ thӵc hiӋn ÿѭӧc ÿLӅu ÿó, khi thiӃt kӃ mҥch sӕ ngѭӡi ta ÿһt ra vҩn ÿӅ tӕi thiӇu hóa các hàm logic, nghƭa là phѭѫng trình logic biӇu diӉn sao cho thӵc sӵ gӑn nhҩt (sӕ lѭӧng các phép tính và sӕ lѭӧng các sӕÿѭӧc biӇu diӉn Gѭӟi dҥng thұt hoһc bù là ít nhҩt). Các kӻ thuұt ÿӇÿҥt ÿѭӧc sӵ thӵc hiӋn hàm Boole mӝt cách ÿѫn giҧn nhҩt phө thuӝc vào nhiӅu \Ӄu tӕ mà chúng ta cҫn cân nhҳc: 0͡t là s͙ l˱ͫng các phép tính và s͙ l˱ͫng các s͙ (sӕ lѭӧng literal) ÿѭӧc biӇu diӉn dѭӟi dҥng thұt hoһc bù là ít nhҩt, ÿLӅu này ÿӗng nghƭa vӟi viӋc sӕ lѭӧng dây nӕi và sӕ lѭӧng ÿҫu vào cӫa mҥch là ít nhҩt. Hai là s͙ l˱ͫng c͝ng cҫn thiӃt ÿӇ thӵc hiӋn mҥch phҧi ít nhҩt, chính sӕ lѭӧng cәng xác ÿӏnh kích thѭӟc cӫa mҥch. Mӝt thiӃt kӃÿѫn giҧn nhҩt phҧi ӭng vӟi sӕ lѭӧng cәng ít nhҩt chӭ không phҧi sӕ Oѭӧng literal ít nhҩt. Ba là s͙ mͱc logic cӫa các cәng. Giҧm sӕ mӭc logic sӁ giҧm trӉ tәng cӝng cӫa mҥch vì tín hiӋu VӁ qua ít cәng hѫn. Tuy nhiên nӃu chú trӑng ÿӃn vҩn ÿӅ giҧm trӉ sӁ phҧi trҧ giá sӕ lѭӧng cәng tăng lên. %ӣi vұy trong thӵc tӃ không phҧi lúc nào cǊng ÿҥt ÿѭӧc lӡi giҧi tӕi ѭu cho bài toán tӕi thiӇu hóa.
Chѭѫng 1. Ĉҥi sӕ Boole Trang 19 Các bѭӟc tiӃn hành tӕi thiӇu hóa: · Dùng các phép tӕi thiӇu ÿӇ tӕi thiӇu hóa các hàm sӕ logic. · Rút ra nhӳng thӯa sӕ chung nhҵm mөc ÿích tӕi thiӇu hóa thêm mӝt bѭӟc nӳa các phѭѫng trình logic. 1.4.2. Các phѭѫng pháp tӕi thiӇu hóa Có nhi͉u ph˱˯ng pháp th͹c hi͏n t͙i thi͋u hoá hàm Boole và có th͋ÿ˱a v͉ 2 nhóm là bi͇n ÿ͝i ÿ̩i s͙ và dùng thu̵t toán. Ph˱˯ng pháp bi͇n ÿ͝i ÿ̩i s͙ (ph˱˯ng pháp gi̫i tích) d͹a vào các tiên ÿ͉, ÿ͓nh lý, tính ch̭t Fͯa hàm Boole ÿ͋ th͹c hi͏n t͙i thi͋u hoá. ͦ nhóm thu̵t toán có 2 ph˱˯ng pháp th˱ͥng ÿ˱ͫc dùng là: ph˱˯ng pháp b̫ng Karnaugh (còn g͕i là bìa Karnaugh – bìa K) dùng cho các hàm có tͳ 6 bi͇n trͧ xu͙ng, và ph˱˯ng pháp Quine-Mc.Cluskey có th͋ s͵ Gͭng cho hàm có s͙ bi͇n b̭t kǤ cǊng nh˱ cho phép th͹c hi͏n t͹ÿ͡ng theo ch˱˯ng trình ÿ˱ͫc vi͇t trên máy tính. Trong phҫn này chӍ giӟi thiӋu 2 phѭѫng pháp ÿҥi diӋn cho 2 nhóm: · Phѭѫng pháp bi͇n ÿ͝i ÿ̩i s͙ (nhóm biӃn ÿәi ÿҥi sӕ). · Phѭѫng pháp E̫ng Karnaugh (nhóm thuұt toán). 1. Phѭѫng pháp biӃn ÿәi ÿҥi sӕ Ĉây là phѭѫng pháp tӕi thiӇu hóa hàm Boole (phѭѫng trình logic) dӵa vào các tiên ÿӅ, ÿӏnh lý, tính chҩt cӫa ÿҥi sӕ Boole. Ví dͭ 1.19 Tӕi thiӇu hoá hàm f(x1,x2) = x 1x2 + x1 x 2 + x1x2 f(x1,x2) =x 1x2 + x1 x 2 + x1x2 = (x 1 + x1).x2 + x1 x 2 = x2 + x1 x 2 = x2 + x1 Ví dͭ 1.20 Tӕi thiӇu hoá hàm 3 biӃn sau 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 Ví dͭ 1.21 Rút gӑn biӇu thӭc: f = AB + C + AC + B Áp dөng ÿӏnh lý De Morgan ta có: f = AB.C + AC + B = (A + B).C + AC + B = AC + BC + AC + B = AC + AC + B + C = (A +1).C + AC + B = C + CA+ B = A + B + C ® ĈӇ thӵc hiӋn mҥch này có thӇ dùng cәng OR 3 ngõ vào.
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 20 2. Phѭѫng pháp bҧng Karnaugh ĈӇ tӕi thiӇu hóa hàm Boole bҵng phѭѫng pháp bҧng Karnaugh phҧi tuân thӫ theo qui tҳc vӅ ô kӃ Fұn: ³Hai ô ÿ˱ͫc g͕i là k͇ c̵n nhau là hai ô mà khi ta tͳ ô này sang ô kia ch͑ làm thay ÿ͝i giá tr͓ cͯa 1 bi͇n.´ Quy tҳc chung cӫa phѭѫng pháp rút gӑn bҵng bҧng Karnaugh là gom (kӃt hӧp) các ô kӃ cұn lҥi Yӟi nhau nhѭ sau: Khi gom 2 ô kӃ cұn sӁ loҥi ÿѭӧc 1 biӃn (2=21 loҥi 1 biӃn). Khi gom 4 ô kӃ cұn vòng tròn sӁ loҥi ÿѭӧc 2 biӃn (4=22 loҥi 2 biӃn). Khi gom 8 ô kӃ cұn vòng tròn sӁ loҥi ÿѭӧc 3 biӃn (8=23 loҥi 3 biӃn). n 7͝ng quát, khi gom 2 ô k͇ c̵n vòng tròn sͅ lo̩i ÿ˱ͫc n bi͇n. Nhͷng bi͇n b͓ lo̩i là nhͷng bi͇n khi ta ÿi vòng qua các ô k͇ c̵n mà giá tr͓ cͯa chúng thay ÿ͝i. Nhӳng ÿLӅu cҫn lѭu ý: Vòng gom ÿѭӧc gӑi là hӧp lӋ khi trong vòng gom ÿó có ít nhҩt 1 ô chѭa thuӝc vòng gom nào. Các ô kӃ cұn muӕn gom ÿѭӧc phҧi là kӃ cұn vòng tròn nghƭa là ô kӃ cұn cuӕi cǊng là ô kӃ cұn ÿҫu tiên. ViӋc kӃt hӧp nhӳng ô kӃ cұn vӟi nhau còn tùy thuӝc vào phѭѫng pháp biӇu diӉn hàm Boole theo Gҥng chính tҳc 1 hoһc chính tҳc 2, cө thӇ là: · 1͇u bi͋u di͍n hàm theo d̩ng chính t̷c 1 (t͝ng các tích s͙) ta chӍ quan tâm nhӳng ô kӃ Fұn có giá trӏ bҵng 1 và tùy ÿӏnh. KӃt quҧ mӛi vòng gom lúc này sӁ là mӝt tích rút gӑn. .Ӄt quҧ cӫa hàm biӇu diӉn theo dҥng chính tҳc 1 sӁ là tәng tҩt cҧ các tích sӕ rút gӑn cӫa Wҩt cҧ các vòng gom. · 1͇u bi͋u di͍n hàm theo d̩ng chính t̷c 2 (tích các t͝ng s͙) ta chӍ quan tâm nhӳng ô kӃ Fұn có giá trӏ bҵng 0 và tùy ÿӏnh. KӃt quҧ mӛi vòng gom lúc này sӁ là mӝt tәng rút gӑn. .Ӄt quҧ cӫa hàm biӇu diӉn theo dҥng chính tҳc 2 sӁ là tích tҩt cҧ các tәng sӕ rút gӑn cӫa Wҩt cҧ các vòng gom. Ta quan tâm nhӳng ô tùy ÿӏnh (X) sao cho nhӳng ô này kӃt hӧp vӟi nhӳng ô có giá trӏ bҵng 1 (nӃu biӇu diӉn theo dҥng chính tҳc 1) hoһc bҵng 0 (nӃu biӇu diӉn theo dҥng chính tҳc 2) làm cho sӕ Oѭӧng ô kӃ cұn là 2n lӟn nhҩt. /ѭu ý các ô tùy ÿӏnh (X) chӍ là nhӳng ô thêm vào vòng gom ÿӇ rút Jӑn hѫn các biӃn mà thôi. Các vòng gom bҳt buӝc phҧi phӫ hӃt tҩt cҧ các ô có giá trӏ bҵng 1 có trong bҧng (nӃu tӕi thiӇu theo dҥng chính tҳc 1), tѭѫng tӵ các vòng gom bҳt buӝc phҧi phӫ hӃt tҩt cҧ các ô có giá trӏ bҵng 0 có trong bҧng (nӃu tӕi thiӇu theo dҥng chính tҳc 2) thì kӃt quҧ tӕi thiӇu hoá mӟi hӧp lӋ. Các trѭӡng hӧp ÿһc biӋt: 1Ӄu tҩt cҧ các ô cӫa bҧng Karnaugh ÿӅu bҵng 1 và tuǤÿӏnh (X) nghƭa là tҩt cҧ các ô ÿӅu kӃ cұn ® giá trӏ cӫa hàm bҵng 1. 1Ӄu tҩt cҧ các ô cӫa bҧng Karnaugh ÿӅu bҵng 0 và tuǤÿӏnh (X) nghƭa là tҩt cҧ các ô ÿӅu kӃ cұn ® giá trӏ cӫa hàm bҵng 0.
Chѭѫng 1. Ĉҥi sӕ Boole Trang 21 Ví dͭ 1.22: Tӕi thiӇu hóa hàm sau f(x1,x2) x1 x2 0 1 0 0 1 7ӕi thiӇu hoá theo chính tҳc 2: 1 1 1 f(x1,x2) = x1 + x2 Ví dͭ 1.23: f(x1,x2,x3) Vòng gom 1: x1 x1,x2 x3 00 01 11 10 0 0 0 1 1 Vòng gom 2: x2.x3 1 0 1 1 1 7͙i thi͋u theo chính t̷c 1: Ta chӍ quan tâm ÿӃn nhӳng ô có giá trӏ bҵng 1 và tùy ÿӏnh (X), nhѭ Yұy sӁ có 2 vòng gom ÿӇ phӫ hӃt các ô có giá trӏ bҵng 1: vòng gom 1 gӗm 4 ô kӃ cұn, và vòng gom 2 gӗm 2 ô kӃ cұn (hình vӁ). Ĉӕi vӟi vòng gom 1: Có 4 ô = 22 nên loҥi ÿѭӧc 2 biӃn. Khi ÿi vòng qua 4 ô kӃ cұn trong vòng gom chӍ có giá trӏ cӫa biӃn x1 không ÿәi (luôn bҵng 1), còn giá trӏ cӫa biӃn x2 thay ÿәi (tӯ 1®0) và giá trӏ cӫa biӃn x3 thay ÿәi (tӯ 0®1) nên các biӃn x2 và x3 bӏ loҥi, chӍ còn lҥi biӃn x1 trong kӃt quҧ Fӫa vòng gom 1. Vì x1=1 nên kӃt quҧ cӫa vòng gom 1 theo dҥng chính tҳc 1 sӁ có x1 viӃt ӣ dҥng thұt: x1 Ĉӕi vӟi vòng gom 2: Có 2 ô = 21 nên sӁ loҥi ÿѭӧc 1 biӃn. Khi ÿi vòng qua 2 ô kӃ cұn trong vòng gom giá trӏ cӫa biӃn x2 và x3 không ÿәi, còn giá trӏ cӫa biӃn x1 thay ÿәi (tӯ 0®1) nên các biӃn x2 và x3ÿѭӧc giӳ lҥi, chӍ có biӃn x1 bӏ loҥi. Vì x2=1 và x3=1 nên kӃt quҧ cӫa vòng gom 2 theo dҥng chính Wҳc 1 sӁ có x2 và x3 viӃt ӣ dҥng thұt: x2.x3 .Ӄt hӧp 2 vòng gom ta có kӃt quҧ tӕi giҧn theo chính tҳc 1: f(x1,x2,x3) = x1 + x2.x3 7͙i thi͋u theo chính t̷c 2: Ta quan tâm ÿӃn nhӳng ô có giá trӏ bҵng 0 và tùy ÿӏnh (X), nhѭ vұy FǊng có 2 vòng gom (hình vӁ), mӛi vòng gom ÿӅu gӗm 2 ô kӃ cұn. 1 Ĉӕi vӟi vòng gom 1: Có 2 ô = 2 nên loҥi ÿѭӧc 1 biӃn, biӃn bӏ loҥi là x2 (vì có giá trӏ thay ÿәi tӯ 0®1). Vì x1=0 và x3=0 nên kӃt quҧ cӫa vòng gom 1 theo dҥng chính tҳc 2 sӁ có x1 và x3ӣ dҥng thұt: x1+ x3. 1 Ĉӕi vӟi vòng gom 2: Có 2 ô = 2 nên loҥi ÿѭӧc 1 biӃn, biӃn bӏ loҥi là x3 (vì có giá trӏ thay ÿәi tӯ 0®1). Vì x1=0 và x2=0 nên kӃt quҧ cӫa vòng gom 2 theo dҥng chính tҳc 2 sӁ có x1 và x2ӣ dҥng thұt: x1+x2. f(x1,x2,x3) x1,x2 Vòng gom 1: x1 + x3 x3 00 01 11 10 0 0 0 1 1 1 0 1 1 1 Vòng gom 2: x1 + x2 .Ӄt hӧp 2 vòng gom có kӃt quҧ cӫa hàm f viӃt theo dҥng chính tҳc 2 nhѭ sau:
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 22 f (x1,x2,x3) = (x1+x3).(x1+x2) = x 1.x1 + x1.x2 + x1.x3 + x2.x3 = x1 + x1.x2 + x1.x3 + x2.x3 = x1(1+ x2 + x3) + x2.x3 = x1 + x2.x3 Nhұn xét: Trong ví dө này, hàm ra viӃt theo dҥng chính tҳc 1 và hàm ra viӃt theo dҥng chính tҳc 2 là giӕng nhau. Tuy nhiên có trѭӡng hӧp hàm ra cӫa hai dҥng chính tҳc 1 và 2 là khác nhau, nhѭng giá trӏ cӫa hàm ra ӭng vӟi mӝt tә hӧp biӃn ÿҫu vào là duy nhҩt trong cҧ 2 dҥng chính tҳc. Chú ý: Ngѭӡi ta thѭӡng cho hàm Boole dѭӟi dҥng biӇu thӭc rút gӑn. Vì có 2 cách biӇu diӉn hàm Boole theo dҥng chính tҳc 1 hoһc 2 nên sӁ có 2 cách cho giá trӏ cӫa hàm Boole ӭng vӟi 2 dҥng chính tҳc ÿó: '̩ng chính t̷c 1: T͝ng các tích s͙. f(x1,x2,x3) = S (3,4,7) + d(5,6) Trong ÿó ký hiӋu d chӍ giá trӏ các ô này là tùy ÿӏnh (d: Don’t care) f(x1,x2,x3) x1,x2 x3 00 01 11 10 0 0 0 X 1 1 0 1 1 X Lúc ÿó bҧng Karnaugh sӁÿѭӧc cho nhѭ hình trên. Tӯ biӇu thӭc rút gӑn cӫa hàm ta thҩy tҥi các ô ӭng vӟi tә hӧp nhӏ phân các biӃn vào có giá trӏ là 3, 4, 7 hàm ra có giá trӏ bҵng 1; tҥi các ô ӭng vӟi Wә hӧp nhӏ phân các biӃn vào có giá trӏ là 5, 6 hàm ra có giá trӏ là tùy ÿӏnh; hàm ra có giá trӏ bҵng 0 ӣ nhӳng ô còn lҥi ӭng vӟi tә hӧp các biӃn vào có giá trӏ là 0, 1, 2. '̩ng chính t̷c 2: Tích các t͝ng s͙. Phѭѫng trình trên cǊng tѭѫng ÿѭѫng vӟi cách cho hàm nhѭ sau: f(x1,x2,x3) = P (0, 1, 2) + d(5, 6) Ví dͭ 1.24: Tӕi thiӇu hóa hàm 4 biӃn cho dѭӟi dҥng biӇu thӭc sau: f(x1,x2,x3,x4) = S (2,6,10,11,12,13) + d(0,1,4,7,8,9,14,15) f(x1,x2,x3,x4) f(x1,x2,x3,x4) x4x3 x4x3 x x x2x1 00 01 11 10 2 1 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 Vòng gom 1 Vòng gom 2 Thӵc hiӋn tӕi thiӇu hóa theo dҥng chính tҳc 1: tӯ bҧn ÿӗ Karnaugh ta có 2 vòng gom, vòng gom 1 Jӗm 8 ô kӃ cұn và vòng gom 2 gӗm 8 ô kӃ cұn. KӃt quҧ tӕi thiӇu hóa nhѭ sau: Vòng gom 1: x 1 Vòng gom 2: x4 9ұy: f(x1,x2,x3,x4) = x 1 + x4
Chѭѫng 2. Các phҫn tӱ logic cѫ bҧn - Cәng logic Trang 23 Chѭѫng 2 CÁC PHҪN TӰ LOGIC CѪ BҦN 2.1. KHÁI NIӊM Vӄ MҤCH SӔ 2.1.1. Mҥch tѭѫng tӵ 0ҥch tѭѫng tӵ (còn gӑi là mҥch Analog) là mҥch dùng ÿӇ xӱ lý các tín hiӋu tѭѫng tӵ. Tín hiӋu Wѭѫng tӵ là tín hiӋu có biên ÿӝ biӃn thiên liên tөc theo thӡi gian. ViӋc xӱ lý bao gӗm các vҩn ÿӅ: ChӍnh lѭu, khuӃch ÿҥi, ÿLӅu chӃ, tách sóng Nhѭӧc ÿLӇm cӫa mҥch tѭѫng tӵ: - Khҧ năng chӕng nhiӉu thҩp (nhiӉu dӉ xâm nhұp). - ViӋc phân tích thiӃt kӃ mҥch phӭc tҥp. ĈӇ khҳc phөc nhӳng nhѭӧc ÿLӇm này ngѭӡi ta sӱ dөng mҥch sӕ. 2.1.2. Mҥch sӕ 0ҥch sӕ (còn gӑi là mҥch Digital) là mҥch dùng ÿӇ xӱ lý tín hiӋu sӕ. Tín hiӋu sӕ là tín hiӋu có biên ÿӝ biӃn thiên không liên tөc theo thӡi gian hay còn gӑi là tín hiӋu gián ÿRҥn, ÿѭӧc biӇu diӉn Gѭӟi dҥng sóng xung vӟi 2 mӭc ÿLӋn thӃ cao và thҩp mà tѭѫng ӭng vӟi hai mӭc ÿLӋn thӃ này là hai Pӭc logic 1 và 0 cӫa mҥch sӕ. ViӋc xӱ lý trong mҥch sӕ bao gӗm các vҩn ÿӅ nhѭ: - Lӑc sӕ. - ĈLӅu chӃ sӕ / Giҧi ÿLӅu chӃ sӕ. - Mã hóa / Giҧi mã Ѭu ÿLӇm cӫa mҥch sӕ so vӟi mҥch tѭѫng tӵ : - Ĉӝ chӕng nhiӉu cao (nhiӉu khó xâm nhұp). - Phân tích thiӃt kӃ mҥch sӕ tѭѫng ÿӕi ÿѫn giҧn. Vì vұy, hiӋn nay mҥch sӕÿѭӧc sӱ dөng khá phә biӃn trong tҩt cҧ các lƭnh vӵc nhѭ: Ĉo lѭӡng sӕ, truyӅn hình sӕ, ÿLӅu khiӇn sӕ. . . 2.1.3. Hӑ logic dѭѫng/âm Trҥng thái logic cӫa mҥch sӕ có thӇ biӇu diӉn bҵng mҥch ÿLӋn ÿѫn giҧn nhѭ trên hình 2.1: Hoҥt ÿӝng cӫa mҥch ÿLӋn này nhѭ sau: - K Mӣ : Ĉèn Tҳt K - K Ĉóng : Ĉèn Sáng Ĉ Trҥng thái Ĉóng/Mӣ cӫa khóa K hoһc trҥng thái Sáng/Tҳt cӫa vi ÿèn Ĉ cǊng ÿѭӧc ÿһc trѭng cho hai trҥng thái logic cӫa mҥch sӕ. Hình 2.1
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 24 &Ǌng có thӇ thay khóa K bҵng khóa ÿLӋn tӱ dùng BJT nhѭ sau (hình 2.2): +Vcc -Vcc Rc V0 Rc V0 RB V RB i Q Vi Q a) b) Hình 2.2. Bi͋u di͍n tr̩ng thái logic cͯa m̩ch s͙ b̹ng khóa ÿL͏n t͵ dùng BJT Giҧi thích các sѫÿӗ mҥch: Hình 2.2a: - Khi Vi = 0 : BJT tҳt ® V0 = +Vcc - Khi Vi = Vcc : BJT dүn bão hòa ® V0 = Vces = 0,2 (V) » 0 (V). Hình 2.2b: - Khi Vi = 0 : BJT tҳt ® V0 = -Vcc - Khi Vi = -Vcc : BJT dүn bão hòa ® V0 = Vces = -Vecs = - 0,2 (V) » 0 (V). 9ұy, trong cҧ 2 sѫ ÿӗ mӭc ÿLӋn thӃ vào/ra cӫa khoá ÿLӋn tӱ dùng BJT cǊng tѭѫng ӭng vӟi 2 trҥng thái logic cӫa mҥch sӕ. Ngѭӡi ta phân biӋt ra hai hӑ logic tùy thuӝc vào mӭc ÿLӋn áp: - NӃu chӑn : Vlogic 1 > Vlogic 0 ® Kӑ logic dѭѫng - NӃu chӑn : Vlogic 1 < Vlogic 0 ® Kӑ logic âm Logic dѭѫng và logic âm là nhӳng hӑ logic tӓ, ngoài ra còn có hӑ logic mӡ (Fuzzy Logic) hiӋn ÿang ÿѭӧc ӭng dөng khá phә biӃn trong các thiӃt bӏÿLӋn tӱ và các hӋ thӕng ÿLӅu khiӇn tӵÿӝng. 2.2. CӘNG LOGIC (LOGIC GATE) 2.2.1. Khái niӋm &әng logic là mӝt trong các thành phҫn cѫ bҧn ÿӇ xây dӵng mҥch sӕ. Cәng logic ÿѭӧc chӃ tҥo trên cѫ sӣ các linh kiӋn bán dүn nhѭ Diode, BJT, FET ÿӇ hoҥt ÿӝng theo bҧng trҥng thái cho trѭӟc. Có ba cách phân loҥi cәng logic: - Phân loҥi cәng theo chӭc năng: BUFFER, NOT, AND, OR, NAND, NOR, XOR, XNOR - Phân loҥi cәng theo phѭѫng pháp chӃ tҥo: Diode, BJT, MOSFET - Phân loҥi cәng theo ngõ ra: Totem-pole, Open-Collector, Tri-states 2.2.2. Phân loҥi cәng logic theo chӭc năng 1. Cәng ĈӊM (BUFFER)
Chѭѫng 2. Các phҫn tӱ logic cѫ bҧn - Cәng logic Trang 25 &әng ÿӋm (BUFFER) hay còn gӑi là cәng không ÿҧo là cәng có mӝt ngõ vào và mӝt ngõ ra vӟi ký hiӋu và bҧng trҥng thái hoҥt ÿӝng nhѭ hình vӁ. Phѭѫng trình logic mô tҧ hoҥt ÿӝng cӫa cәng ÿӋm: y = x %ҧng trҥng thái x y x y 0 0 1 1 Hình 2.3. Ký hi͏u và b̫ng tr̩ng thái cͯa c͝ng ÿ͏m Trong ÿó: - x là ngõ vào có trӣ kháng vào Zv vô cùng lӟn ® do ÿó dòng vào cӫa cәng ÿӋm rҩt nhӓ. - y là ngõ ra có trӣ kháng ra Zra nhӓ ® cәng ÿӋm có khҧ năng cung cҩp dòng ngõ ra lӟn. Chính vì vұy ngѭӡi ta sӱ dөng cәng ÿӋm theo 2 ý nghƭa sau: - Dùng ÿӇ phӕi hӧp trӣ kháng. - Dùng ÿӇ cách ly và nâng dòng cho tҧi. 9Ӆ phѭѫng diӋn mҥch ÿLӋn có thӇ xem cәng ÿӋm (cәng không ÿҧo) giӕng nhѭ mҥch khuyӃch ÿҥi C chung (ÿӗng pha). 2.Cәng ĈҦO (NOT) &әng ĈҦO (còn gӑi là cәng NOT) là cәng logic có 1 ngõ vào và 1 ngõ ra, vӟi ký hiӋu và bҧng trҥng thái hoҥt ÿӝng nhѭ hình vӁ: %ҧng trҥng thái: x y x y 0 1 1 0 Hình 2.4. Ký hi͏u và b̫ng tr̩ng thái ho̩t ÿ͡ng cͯa c͝ng ÿ̫o Phѭѫng trình logic mô tҧ hoҥt ÿӝng cӫa cәng ĈҦO: y = x &әng ÿҧo giӳ chӭc năng nhѭ mӝt cәng ÿӋm, nhѭng ngѭӡi ta gӑi là ÿӋm ÿҧo vì tín hiӋu ngõ ra ngѭӧc mӭc logic (ngѭӧc pha) vӟi tín hiӋu ngõ vào. Trong thӵc tӃ ta có thӇ ghép hai cәng ĈҦO nӕi tҫng vӟi nhau ÿӇ thӵc hiӋn chӭc năng cӫa cәng ĈӊM (cәng không ÿҧo): x x x x = x Hình 2.5. S͵ dͭng 2 c͝ng Ĉ̪O t̩o ra c͝ng Ĉ͎M 9Ӆ phѭѫng diӋn mҥch ÿLӋn, cәng ĈҦO giӕng nhѭ tҫng khuyӃch ÿҥi E chung.
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 26 3. Cәng VÀ (AND) &әng AND là cәng logic thӵc hiӋn chӭc năng cӫa phép toán nhân logic các tín hiӋu vào. Cәng AND 2 ngõ vào có 2 ngõ vào 1 ngõ ra ký hiӋu nhѭ hình vӁ: Phѭѫng trình logic mô tҧ hoҥt ÿӝng cӫa cәng AND: x1 y y = x1.x2 %ҧng trҥng thái hoҥt ÿӝng cӫa cәng AND 2 ngõ vào: x2 x1 x2 y Hình 2.6. C͝ng AND 0 0 0 0 1 0 1 0 0 1 1 1 7ӯ bҧng trҥng thái này có nhұn xét: Ngõ ra y chӍ bҵng 1 (mӭc logic 1) khi cҧ 2 ngõ vào ÿӅu bҵng 1, ngõ ra y bҵng 0 (mӭc logic 0) khi có mӝt ngõ vào bҩt kǤ (x1 hoһc x2) bҵng 0. Xét trѭӡng hӧp tәng quát cho cәng AND có n ngõ vào x1, x2 xn: ì0 $xi = 0 x1 yAND= í y î1 "xi = 1 (i = 1,n) xn 9̵y, ÿ̿c ÿL͋m cͯa c͝ng AND là: ngõ ra y ch͑ b̹ng 1 khi ṱt c̫ các ngõ vào ÿ͉u b̹ng 1, ngõ ra y b̹ng 0 khi Hình 2.7. C͝ng AND vͣi n ngõ vào có ít nh̭t m͡t ngõ vào b̹ng 0. 6ӱ dөng cәng AND ÿӇÿóng mӣ tín hiӋu: Cho cәng AND có hai ngõ vào x1 và x2. Ta chӑn: - x1ÿóng vai trò ngõ vào ÿLӅu khiӇn (control). - x2ÿóng vai trò ngõ vào dӳ liӋu (data). Xét các trѭӡng hӧp cө thӇ sau ÿây: - Khi x1= 0: y = 0 bҩt chҩp trҥng thái cӫa x2, ta nói F͝ng AND khóa lҥi không cho dӳ liӋu ÿѭa vào ngõ vào x2 qua cәng AND ÿӃn ngõ ra. ìx = 0 Þ y = 0 ï 2 - Khi x1 = 1 Þ y = x íx =1Þ y =1 2 îï 2 Ta nói F͝ng AND mͧ cho dӳ liӋu ÿѭa vào ngõ vào x2 qua cәng AND ÿӃn ngõ ra. 9ұy, có thӇ sӱ dөng mӝt ngõ vào bҩt kǤ cӫa cәng AND ÿóng vai trò tín hiӋu ÿLӅu khiӇn cho phép hoһc không cho phép luӗng dӳ liӋu ÿi qua cәng AND. 6ӱ dөng cәng AND ÿӇ tҥo ra cәng logic khác: 1Ӄu sӱ dөng 2 tә hӧp ÿҫu và cuӕi trong bҧng giá trӏ cӫa cәng AND và nӕi cәng AND theo sѫÿӗ nhѭ hình 3.8 thì có thӇ sӱ dөng cәng AND ÿӇ tҥo ra cәng ÿӋm. Trong thӵc tӃ, có thӇ tұn dөng hӃt các cәng chѭa dùng trong IC ÿӇ thӵc hiӋn chӭc năng cӫa các Fәng logic khác.
Chѭѫng 2. Các phҫn tӱ logic cѫ bҧn - Cәng logic Trang 27 x1 y +x = 0 ĺ x1= x2= 0 ĺ y = 0 +x = 1 ĺ x1= x2= 1 ĺ y = 1 ĺ y = x x2 Hình 2.8. S͵ dͭng c͝ng AND t̩o ra c͝ng ÿ͏m. 4. Cәng HOҺC (OR) &әng OR là cәng thӵc hiӋn chӭc năng cӫa phép toán cӝng logic các tín hiӋu vào. Trên hình vӁ là ký hiӋu cӫa cәng OR 2 ngõ vào: Phѭѫng trình logic cәng OR 2 ngõ vào: y = x1 + x2 x1 x1 y y x2 x2 Ký hiӋu Châu Âu Ký hiӋu theo Mӻ, Nhұt, Úc Hình 2.9a C͝ng OR 2 ngõ vào %ҧng trҥng thái mô tҧ hoҥt ÿӝng: x1 x2 y = x1+x2 00 0 01 1 10 1 11 1 Xét trѭӡng hӧp tәng quát ÿӕi vӟi cәng OR có n ngõ vào. x1 Phѭѫng trình logic: y xn ì1 $xi = 1 yOR = í 0 x 0 (i 1,n) î " i = = Hình 2.9b C͝ng OR n ngõ vào Ĉ̿c ÿL͋m cͯa c͝ng OR là: Tín hi͏u ngõ ra ch͑ b̹ng 0 khi và ch͑ khi ṱt c̫ các ngõ vào ÿ͉u E̹ng 0, ng˱ͫc l̩i tín hi͏u ngõ ra b̹ng 1 khi ch͑ c̯n có ít nh̭t m͡t ngõ vào b̹ng 1. 6ӱ dөng cәng OR ÿӇÿóng mӣ tín hiӋu: Xét cәng OR có 2 ngõ vào x1, x2. NӃu chӑn x1 là ngõ vào ÿLӅu khiӇn (control), x2 ngõ vào dӳ liӋu (data), ta có các trѭӡng hӧp cө thӇ sau ÿây: - x1= 1: y = 1, y luôn bҵng 1 bҩt chҩp x2 ® Ta nói F͝ng OR khóa không cho dӳ liӋu ÿi qua.
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 28 ìx = 0 Þ y = 0 ï 2 - x1= 0: Þ y = x ® Ta nói F͝ng OR mͧ cho dӳ liӋu tӯ ngõ vào x2 qua íx =1Þ y =1 2 îï 2 Fәng ÿӃn ngõ ra y. 6ӱ dөng cәng OR ÿӇ thӵc hiӋn chӭc năng cәng logic khác: 6ӱ dөng hai tә hӧp giá trӏÿҫu và cuӕi cӫa bҧng trҥng thái cӫa cәng OR và nӕi mҥch cәng OR nhѭ sѫÿӗ: - x = 0, x1 = x2 = 0 Þ y = 0 - x = 1, x1 = x2 = 1 Þ y = 1 Þ y = x: cәng OR ÿóng vai trò nhѭ cәng ÿӋm. x1 x y x2 Hình 2.10. S͵ dͭng c͝ng OR làm c͝ng ÿ͏m 5. Cәng NAND Ĉây là cәng thӵc hiӋn phép toán nhân ÿҧo, vӅ sѫÿӗ logic cәng NAND gӗm 1 cәng AND mҳc Qӕi tҫng vӟi 1 cәng NOT, ký hiӋu và bҧng trҥng thái cәng NAND ÿѭӧc cho nhѭ trên hình: x1 y x1 x2 y x2 0 0 1 0 1 1 x1 1 0 1 y x2 1 1 0 Hình 2.11. C͝ng NAND: Ký hi͏u, s˯ÿ͛ logic t˱˯ng ÿ˱˯ng và b̫ng tr̩ng thái Phѭѫng trình logic mô tҧ hoҥt ÿӝng cӫa cәng NAND 2 ngõ vào: y = x1.x2 x Xét trѭӡng hӧp tәng quát: Cәng NAND có n ngõ vào. 1 y xn ì1 $x = 0 y = i NAND í Hình 2.12.C͝ng NAND n ngõ vào î0 "xi = 1 (i = 1,n) 9̵y, ÿ̿c ÿL͋m cͯa c͝ng NAND là: tín hi͏u ngõ ra ch͑ b̹ng 0 khi ṱt c̫ các ngõ vào ÿ͉u b̹ng 1, và tín hi͏u ngõ ra sͅ b̹ng 1 khi ch͑ c̯n ít nh̭t m͡t ngõ vào b̹ng 0. 6ӱ dөng cәng NAND ÿӇÿóng mӣ tín hiӋu: Xét cәng NAND có hai ngõ vào. Chӑn x1 là ngõ vào ÿLӅu khiӇn (control), x2 là ngõ vào dӳ liӋu (data), lҫn lѭӧt xét các trѭӡng hӧp sau: - x1= 0: y = 1 (y luôn bҵng 1 bҩt chҩp giá trӏ cӫa x2) ta nói F͝ng NAND khóa. ìx = 0 Þ y =1 ï 2 - x1= 1: Þ y = x ® &͝ng NAND mͧ cho dӳ liӋu vào ngõ vào x2ÿӃn íx =1Þ y = 0 2 îï 2 ngõ ra ÿӗng thӡi ÿҧo mӭc tín hiӋu ngõ vào x2, lúc này cәng NAND ÿóng vai trò là cәng ĈҦO.
Chѭѫng 2. Các phҫn tӱ logic cѫ bҧn - Cәng logic Trang 29 6ӱ dөng cәng NAND ÿӇ tҥo các cәng logic khác: - dùng cәng NAND tҥo cәng NOT: x x 1 y x y x2 y = x1x2 = x1 + x2 = x Hình 2.13a.Dùng c͝ng NAND t̩o c͝ng NOT - dùng cәng NAND tҥo cәng BUFFER (cәng ÿӋm): x x1 x y x y x2 y = x = x Hình 2.13b.Dùng c͝ng NAND t̩o c͝ng Ĉ͎M (BUFFER) - dùng cәng NAND tҥo cәng AND: x1 x1 y y x1.x2 y = x1 x2 = x1.x2 x2 x2 Hình 2.13c. S͵ dͭng c͝ng NAND t̩o c͝ng AND - dùng cәng NAND tҥo cәng OR: x1 x x1 1 y y x2 x2 x2 y = x1.x2 = x1 + x2 = x1 + x2 Hình 2.13d. Dùng c͝ng NAND t̩o c͝ng OR
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 30 6. Cәng NOR &әng NOR, còn gӑi là cәng Hoһc-Không, là cәng thӵc hiӋn chӭc năng cӫa phép toán cӝng ÿҧo logic, là cәng có hai ngõ vào và mӝt ngõ ra có ký hiӋu nhѭ hình vӁ: Phѭѫng trình logic mô tҧ hoҥt ÿӝng cӫa cәng : y = x1 + x 2 x1 x1 y y x2 x2 Ký hiӋu theo Châu Âu Ký hiӋu theo Mӻ, Nhұt Hình 2.14. Ký hi͏u c͝ng NOR %ҧng trҥng thái mô tҧ hoҥt ÿӝng cӫa cәng NOR : x1 x2 y 0 0 1 0 1 0 1 0 0 1 1 0 Xét trѭӡng hӧp tәng quát cho cәng NOR có n ngõ vào. ì0 $xi = 1 x1 yNOR= í y î1 "xi = 0 (i = 1,n) 9̵y ÿ̿c ÿL͋m cͯa c͝ng NOR là: Tín hi͏u ngõ ra ch͑ xn E̹ng 1 khi ṱt c̫ các ngõ vào ÿ͉u b̹ng 0, tín hi͏u ngõ ra sͅ b̹ng 0 khi có ít nh̭t m͡t ngõ vào b̹ng 1. Hình 2.15. C͝ng NOR n ngõ vào 6ӱ dөng cәng NOR ÿӇÿóng mӣ tín hiӋu: Xét cәng NOR có 2 ngõ vào, chӑn x1 là ngõ vào ÿLӅu khiӇn, x2 là ngõ vào dӳ liӋu. Ta có: - x1= 1: y = 0 (y luôn bҵng 0 bҩt chҩp x2), ta nói F͝ng NOR khóa không cho dӳ liӋu ÿi qua. ìx = 0Þ y =1 ï 2 - x1= 0: Þ y = x ® ta nói F͝ng NOR mͧ cho dӳ liӋu tӯ ngõ vào x2 qua íx =1Þ y = 0 2 îï 2 Fәng NOR ÿӃn ngõ ra ÿӗng thӡi ÿҧo mӭc tín hiӋu ngõ vào x2, lúc này cәng NOR ÿóng vai trò là cәng ĈҦO. 6ӱ dөng cәng NOR ÿӇ thӵc hiӋn chӭc năng cәng logic khác: - Dùng cәng NOR làm cәng NOT: x x1 y x2 x y y = x1 + x2 = x1.x2 = x Hình 2.16a. S͵ dͭng c͝ng NOR t̩o c͝ng NOT
Chѭѫng 2. Các phҫn tӱ logic cѫ bҧn - Cәng logic Trang 31 - Dùng cәng NOR làm cәng OR : x x1 x + x 1 1 2 y y x2 x2 y = x1 + x2 = x1 + x2 Hình 2.16b. S͵ dͭng c͝ng NOR t̩o c͝ng OR - Dùng cәng NOR làm cәng BUFFER : x x 1 x y x y x2 y = x = x Hình 2.16c. S͵ dͭng c͝ng NOR t̩o c͝ng BUFFER - Dùng cәng NOR làm cәng AND : x1 x1 x1 y y x2 x2 x2 y = x1 + x2 = x1.x2 = x1.x2 Hình 2.16d. S͵ dͭng c͝ng NOR làm c͝ng AND - Dùng cәng NOR làm cәng NAND: x1 x x1 1 y1 y y x2 x2 x2 y = y1 = x1 + x2 = x1 + x 2 = x1.x2 Hình 2.16e. S͵ dͭng c͝ng NOR làm c͝ng NAND
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 32 7. Cәng XOR (EX - OR) Ĉây là cәng logic thӵc hiӋn chӭc năng cӫa mҥch cӝng modulo 2 (cӝng không nhӟ), là cәng có hai ngõ vào và mӝt ngõ ra có ký hiӋu và bҧng trҥng thái nhѭ hình vӁ. Phѭѫng trình logic mô tҧ hoҥt ÿӝng cӫa cәng XOR : yXOR = x1 x 2 + x1 .x2 = x1Å x2 x1 x2 y x1 0 0 0 y 0 1 1 x2 1 0 1 1 1 0 Hình 2.17. C͝ng XOR &әng XOR ÿѭӧc dùng ÿӇ so sánh hai tín hiӋu vào: - NӃu hai tín hiӋu vào là bҵng nhau thì tín hiӋu ngõ ra bҵng 0 - NӃu hai tín hiӋu vào là khác nhau thì tín hiӋu ngõ ra bҵng 1. Các tính chҩt cӫa phép toá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) 4. x1 Å (x2. x3) = (x1Åx3).(x1Åx2) 5. x Å 0 = x x Å 1 = x Mӣ rӝng: NӃu x Åx = x thì x Åx =x và x Åx =x x Å x = 0 1 2 3 1 3 2 2 3 1 x Å x = 1 8. Cәng XNOR (EX – NOR) Ĉây là cәng logic thӵc hiӋn chӭc năng cӫa mҥch cӝng ÿҧo modulo 2 (cӝng không nhӟ), là cәng có hai ngõ vào và mӝt ngõ ra có ký hiӋu và bҧng trҥng thái nhѭ trên hình vӁ. Phѭѫng trình logic mô tҧ hoҥt ÿӝng cӫa cәng: y = x1 x2 + x1x 2 = x1 Å x2 x1 x2 y x1 0 0 1 y 0 1 0 1 0 0 x2 Hình 2.19. C͝ng XNOR 1 1 1 2.2.3. Các thông sӕ kӻ thuұt cӫa cәng logic 1. Công suҩt tiêu tán Ptt 0ӝt phҫn tӱ logic khi làm viӋc phҧi trҧi qua các giai ÿRҥn sau:
Chѭѫng 2. Các phҫn tӱ logic cѫ bҧn - Cәng logic Trang 33 - Ӣ trҥng thái tҳt. - ChuyӇn tӯ trҥng thái tҳt sang trҥng thái dүn. - Ӣ trҥng thái dүn. - ChuyӇn tӯ trҥng thái dүn sang tҳt. Ӣ mӛi giai ÿRҥn, phҫn tӱ logic ÿӅu tiêu thөӣ nguӗn mӝt công suҩt. Ĉӕi vӟi các phҫn tӱ logic dùng BJT, tiêu biӇu là hӑ TTL: tiêu thө công suҩt cӫa nguӗn chӫ yӃu khi ӣ trҥng thái tƭnh (ÿang dүn hoһc ÿang tҳt). Ĉӕi vӟi cҧ vi mҥch (IC – Integrated Circuit) công suҩt tiêu tán ÿѭӧc tính: Ptt = IC.VCC Ĉӕi vӟi vi mҥch hӑ CMOS: chӍ tiêu thө công suҩt chӫ yӃu trong trҥng thái ÿӝng (trong thӡi gian chuyӇn mҥch). Công suҩt tiêu tán: 2 Ptt = CL. f .VDD Trong ÿó: CL là ÿLӋn dung cӫa tҧi (ÿLӋn dung tҧi) f là tҫn sӕ làm viӋc cӫa vi mҥch VDD là ÿLӋn áp nguӗn cung cҩp Nhѭ vұy ta thҩy ÿӕi vӟi vi mҥch CMOS tҫn sӕ hoҥt ÿӝng (tҫn sӕ chuyӇn mҥch) càng lӟn công suҩt tiêu tán càng tăng. 2. Fanout (HӋ sӕ mҳc mҥch ngõ ra) Fanout là hӋ sӕ mҳc mҥch ӣ ngõ ra hay còn gӑi là khҧ năng tҧi cӫa mӝt phҫn tӱ logic. *ӑi N là Fanout cӫa mӝt phҫn tӱ logic, thì nó ÿѭӧc ÿӏnh nghƭa nhѭ sau: Sӕ ngõ vào logic Fӵc ÿҥi ÿѭӧc nӕi ÿӃn mӝt ngõ ra cӫa phҫn tӱ logic cùng hӑ mà mҥch vүn hoҥt ÿӝng bình thѭӡng. 3. Fanin (HӋ sӕ mҳc mҥch ngõ vào) Hình 2.41. Khái ni͏m v͉ Fanout *ӑi M là Fanin cӫa 1 phҫn tӱ logic thì M ÿѭӧc ÿӏnh nghƭa nhѭ sau: Ĉó chính là “Vӕ ngõ vào logic cӵc ÿҥi cӫa mӝt phҫn tӱ logic”. Ĉӕi vӟi cá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 là 4 ngõ vào. Ĉӕi vӟi cá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 là 6 ngõ vào. Ĉӕi vӟi hӑ logic CMOS thì có fanin nhiӅu hѫn nhѭng cǊng không quá 8 ngõ vào. 4. TrӉ truyӅn ÿҥt TrӉ truyӅn ÿҥt là khoҧng thӡi gian ÿӇÿҫu ra cӫa mҥch có ÿáp ӭng ÿӕi vӟi sӵ thay ÿәi mӭc logic Fӫa ÿҫu vào. TrӉ truyӅn ÿҥt là tiêu chuҭn ÿӇÿánh giá tӕc ÿӝ làm viӋc cӫa mҥch. Tӕc ÿӝ làm viӋc cӫa mҥch Wѭѫng ӭng vӟi tҫn sӕ mà mҥch vүn còn hoҥt ÿӝng ÿúng. Nhѭ vұy, trӉ truyӅn ÿҥt càng nhӓ càng tӕt hay tӕc ÿӝ làm viӋc càng lӟn càng tӕt. Ĉӕi vӟi hҫu hӃt các vi mҥch sӕ hiӋn nay, trӉ truyӅn ÿҥt là rҩt nhӓ, cӥ vài nano giây (ns). Mӝt vài loҥi mҥch logic có thӡi gian trӉ lӟn cӥ vài trăm nano giây. Khi mҳc liên tiӃp nhiӅu mҥch logic thì trӉ truyӅn ÿҥt cӫa toàn mҥch sӁ bҵng tәng các trӉ truyӅn ÿҥt cӫa mӛi tҫng.
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 34 2.3. FLIP – FLOP (FF) 2.3.1. Khái niӋm Flip-Flop (viӃt tҳt là FF) là mҥch dao ÿӝng ÿa hài hai trҥng thái bӅn, ÿѭӧc xây dӵng trên cѫ sӣ các cәng logic và hoҥt ÿӝng theo mӝt bҧng trҥng thái cho trѭӟc. 2.3.2. Phân loҥi Có hai cách phân loҥi các Flip-Flop: - Phân loҥi theo tín hiӋu ÿLӅu khiӇn ÿӗng bӝ. - Phân loҥi theo chӭc năng. 1. Phân loҥi FF theo tín hiӋu ÿLӅu khiӇn ÿӗng bӝ *ӗm có hai loҥi: - Không có tín hiӋu ÿLӅu khiӇn ÿӗng bӝ (FF không ÿӗng bӝ). - Có tín hiӋu ÿLӅu khiӇn ÿӗng bӝ (FF ÿӗng bӝ). a. FF không ÿ͛ng b͡ 'ҥng 1: RSFF không ÿӗng bӝ dùng cәng NOR (sѫÿӗ hình 2.43) Q SR Q R 1 0 0 Q0 0 1 0 1 0 1 S Q 1 1 X 2 Hình 2.43. RSFF không ÿ͛ng b͡ s͵ dͭng c͝ng NOR và b̫ng tr̩ng thái '͹a vào b̫ng chân tr͓ cͯa c͝ng NOR ÿ͋ gi̫i thích ho̩t ÿ͡ng cͯa s˯ÿ͛ m̩ch này: - S = 0, R = 1 Þ Q = 0. Q=0 hӗi tiӃp vӅ cәng NOR 2 nên cәng NOR 2 có hai ngõ vào bҵng 0 ÞQ = 1. Vұy, Q = 0 và Q = 1. - S = 1, R = 0 Þ Q = 0. Q = 0 hӗi tiӃp vӅ cәng NOR 1 nên cәng NOR 1 có hai ngõ vào bҵng 0 Þ Q = 1. Vұy, Q = 1 và Q = 0. - Giҧ sӱ ban ÿҫu: S = 0, R = 1 Þ Q = 0 và Q = 1. 1Ӄu tín hiӋu ngõ vào thay ÿәi thành: S = 0, R = 0 (R chuyӇn tӯ 1 ® 0) ta có: + S = 0 và Q = 0 Þ Q = 1 + R = 0 vàQ = 1 Þ Q = 0 Þ RSFF giӳ nguyên trҥng thái cǊ trѭӟc ÿó. - Giҧ sӱ ban ÿҫu: S = 1, R = 0 Þ Q = 1 và Q = 0. 1Ӄu tín hiӋu ngõ vào thay ÿәi thành: R = 0, S = 0 (S chuyӇn tӯ 1 ® 0) ta có: + R = 0 và Q = 0 Þ Q = 1 + S = 0 và Q = 1 Þ Q = 0 Þ RSFF giӳ nguyên trҥng thái cǊ trѭӟc ÿó.
Chѭѫng 2. Các phҫn tӱ logic cѫ bҧn – Flip Flop Trang 35 'ҥng 2: RSFF không ÿӗng bӝ dùng cәng NAND (sѫÿӗ hình 2.44) Q S 1 S R Q 0 0 X 0 1 1 1 0 0 R 2 Q 1 1 Q0 Hình 2.44. RSFF không ÿ͛ng b͡ s͵ dͭng c͝ng NAND và b̫ng tr̩ng thái 'ӵa vào bҧng chân trӏ cӫa cәng NAND ÿӇ giҧi thích hoҥt ÿӝng cӫa mҥch này: ì0 "xi =1 y = í î1 $xi = 0 Ta có: - S = 0, R = 1 Þ Q = 1. Q = 1 hӗi tiӃp vӅ cәng NAND 2 nên cәng NAND 2 có hai ngõ vào Eҵng 1 vұy Q = 0. - S = 0, R = 1 Þ Q = 1. Q = 1 hӗi tiӃp vӅ cәng NAND 1 nên cәng NAND 1 có hai ngõ vào Eҵng 1 vұy Q = 0. - S = R = 0 Þ Q = Q = 1 ÿây là trҥng thái cҩm. - S = R = 1: Giҧ sӱ trҥng thái trѭӟc ÿó có Q = 1, Q = 0 Þ hӗi tiӃp vӅ cәng NAND 1 nên cәng NAND 1 có mӝt ngõ vào bҵng 0 vұy Q = 1 Þ RSFF giӳ nguyên trҥng thái cǊ. Nhѭ vұy gӑi là FF không ÿӗng bӝ bӣi vì chӍ cҫn mӝt trong hai ngõ vào S hay R thay ÿәi thì ngõ ra cǊng thay ÿәi theo. 9Ӆ mһt kí hiӋu, các RSFF không ÿӗng bӝÿѭӧc ký hiӋu nhѭ sau: R Q S Q S R a) b) Hình 2.45. Ký hi͏u các FF không ÿ͛ng b͡ a. R,S tác ÿ͡ng mͱc 1 - b. R,S tác ÿ͡ng mͱc 0
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 36 b. FF ÿ͛ng b͡ Xét sѫÿӗ RSFF ÿӗng bӝ vӟi sѫÿӗ mҥch, ký hiӋu và bҧng trҥng thái hoҥt ÿӝng nhѭ hình 2.46. Trong ÿó: Ck là tín hiӋu ÿLӅu khiӇn ÿӗng bӝ hay tín hiӋu ÿӗng hӗ (Clock). Khҧo sát hoҥt ÿӝng cӫa Pҥch: S 3 Q S 1 Ck S Q Ck R 2 Q R Q R 4 Hình 2.46. RSFF ÿ͛ng b͡: S˯ÿ͛ logic và ký hi͏u - Ck = 0: cәng NAND 3 và 4 khóa không cho dӳ liӋu ÿѭa vào. Vì cәng NAND 3 và 4 ÿӅu có ít nhҩt mӝt ngõ vào Ck = 0 Þ S = R =1 Þ Q = Q0 : RSFF giӳ nguyên trҥng thái cǊ. - Ck = 1: cәng NAND 3 và 4 mӣ. Ngõ ra Q sӁ thay ÿәi tùy thuӝc vào trҥng thái cӫa S và R. + S = 0, R = 0 Þ S =1, R =1 Þ Q = Q0 S R Ck Q 0 + S = 0, R = 1 Þ S =1, R = 0 Þ Q = 0 X X 0 Q 0 0 1 Q0 + S = 1, R = 0 Þ S = 0, R = 1 Þ Q = 1 0 1 1 0 + S = 1, R = 1 Þ S = 0, R = 0 Þ Q = X 1 0 1 1 Trong trѭӡng hӧp này tín hiӋu ÿӗng bӝ Ck tác ÿӝng mӭc 1. Trong 1 1 1 X trѭӡng hӧp Ck tác ÿӝng mӭc 0 thì ta mҳc thêm cәng ÿҧo nhѭ sau (hình 2.47): S 3 Q S 1 S Q Ck Ck R Q R 2 Q R 4 Hình 2.47 Tùy thuӝc vào mӭc tích cӵc cӫa tín hiӋu ÿӗng bӝ Ck, chúng ta có các loҥi tín hiӋu ÿLӅu khiӇn: - Ck ÿLӅu khiӇn theo mӭc 1. - Ck ÿLӅu khiӇn theo mӭc 0. - Ck ÿLӅu khiӇn theo sѭӡn lên (sѭӡn trѭӟc). - Ck ÿLӅu khiӇn theo sѭӡn xuӕng (sѭӡn sau). a. Mͱc 1 b. Mͱc 0 c. S˱ͥn lên d. S˱ͥn xu͙ng Hình 2.48. Các lo̩i tín hi͏u ÿL͉u khi͋n Ck khác nhau
Chѭѫng 2. Các phҫn tӱ logic cѫ bҧn – Flip Flop Trang 37 Xét FF có Ck ÿLӅu khiӇn theo sѭӡn lên (sѭӡn trѭӟc): Sѭӡn lên và mӭc logic 1 có mӕi quan hӋ vӟi nhau, vì vұy mҥch tҥo sѭӡn lên là mҥch cҧi tiӃn cӫa Pҥch tác ÿӝng theo mӭc logic 1. 6ѭӡn lên thӵc chҩt là mӝt xung dѭѫng có thӡi gian tӗn tҥi rҩt ngҳn. ĈӇ cҧi tiӃn các FF tác ÿӝng theo mӭc logic 1 thành FF tác ÿӝng theo sѭӡn lên ta mҳc vào trѭӟc FF ÿó mӝt mҥch tҥo sѭӡn lên nhѭ hình vӁ. Ck 0ҥch S Ck t Wҥo sѭӡn lên R 0 Xung sau khi qua t Pҥch tҥo sѭӡn lên 0 Hình 2.49. S˯ÿ͛ kh͙i FF tác ÿ͡ng theo s˱ͥn lên và d̩ng sóng Ӣ mҥch tҥo sѭӡn ngѭӡi ta lӧi dөng thӡi gian trӉ cӫa tín hiӋu khi ÿi qua phҫn tӱ logic. Ĉӕi vӟi Pҥch tҥo sѭӡn ngѭӡi ta lӧi dөng thӡi gian trӉ cӫa tín hiӋu khi ÿi qua cәng NOT. Ck Ck x t 1 y 0 x2 x2 t 0 S x1 t Ck 0 R y Hình 2.50 t 0 Xét sѫÿӗ mҥch tҥo sѭӡn lên và dҥng sóng nhѭ hình 2.50 : Mҥch tҥo sѭӡn lên gӗm mӝt cәng AND 2 ngõ vào và mӝt cәng NOT. Tín hiӋu x1 tӯ cәng NOT ÿѭӧc ÿѭa ÿӃn cәng AND cùng vӟi tín hiӋu x2ÿi trӵc tiӃp (x2 = Ck). Do tính chҩt trӉ cӫa tín hiӋu Ck khi ÿi qua cәng NOT nên x1 bӏ trӉ mӝt khoҧng thӡi gian, vì vұy tín hiӋu ngõ ra cӫa cәng AND có dҥng mӝt xung dѭѫng rҩt hҽp vӟi thӡi gian tӗn tҥi chính bҵng thӡi gian trӉ (trӉ truyӅn ÿҥt) cӫa cәng NOT. Xung dѭѫng hҽp này ÿѭӧc ÿѭa ÿӃn ngõ vào ÿӗng bӝ cӫa FF ÿLӅu khiӇn theo mӭc logic 1. Tҥi các thӡi ÿLӇm có sѭӡn lên cӫa tín hiӋu xung nhӏp Ck sӁ xuҩt hiӋn mӝt xung dѭѫng tác ÿӝng vào ngõ vào ÿӗng bӝ cӫa FF ÿLӅu khiӇn ngõ ra Q thay ÿәi trҥng thái theo các ngõ vào. Sѫÿӗ mҥch FF có tín hiӋu Ck ÿLӅu khiӇn theo sѭӡn lên nhѭ hình 2.51.
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 38 S 3 Q S 1 Ck y R 2 Q R 4 Hình 2.51. FF có tín hi͏u Ck ÿL͉u khi͋n theo s˱ͥn lên Xét FF có Ck ÿLӅu khiӇn theo sѭӡn xuӕng (sѭӡn sau): 0ҥch tҥo sѭӡn xuӕng là mҥch cҧi tiӃn tác ÿӝng mӭc logic 0. Sѫÿӗ mҥch và dҥng sóng ÿѭӧc cho ӣ hình 2.52. Trên hình 2.53 là ký hiӋu trên sѫÿӗ mҥch và sѫÿӗ thӵc hiӋn Flip-Flop tác ÿӝng theo Vѭӡn xuӕng. a) Ck b) Ck x1 y t 0 x2 x2 t 0 Hình 2.52. M̩ch t̩o s˱ͥn xu͙ng x1 a. S˯ÿ͛ m̩ch t b. D̩ng sóng 0 y 0 t S a) 3 Q S 1 Ck y R 2 Q R 4 b) S Q Hình 2.53 Ck a. S˯ÿ͛ m̩ch th͹c hi͏n R Q b. Ký hi͏u (Sinh viên t͹ gi̫i thích ho̩t ÿ͡ng cͯa các m̩ch này).
Chѭѫng 2. Các phҫn tӱ logic cѫ bҧn – Flip Flop Trang 39 Ý nghƭa cӫa tín hiӋu ÿӗng bӝ Ck: Ĉӕi vӟi các FF ÿӗng bӝ, các ngõ ra chӍ thay ÿәi trҥng thái theo ngõ vào DATA khi xung Ck tӗn tҥi Pӭc 1 (ÿӕi vӟi FF tác ÿӝng mӭc 1), hoһc xung Ck tӗn tҥi mӭc 0 (ÿӕi vӟi FF tác ÿӝng mӭc 0), hoһc xung Ck ӣ sѭӡn lên (ÿӕi vӟi FF tác ÿӝng sѭӡn lên), xung Ck ӣ sѭӡn xuӕng (ÿӕi vӟi FF tác ÿӝng Vѭӡn xuӕng), còn tҩt cҧ các trѭӡng hӧp khác cӫa Ck thì ngõ ra không thay ÿәi trҥng thái theo các ngõ vào mһc dù lúc ÿó các ngõ vào có thay ÿәi trҥng thái. 2. Phân loҥi FF theo chӭc năng a. RSFF Ĉó là FF có các ngõ vào và ngõ ra ký hiӋu nhѭ hình vӁ. Trong ÿó: S Q - S, R : các ngõ vào dӳ liӋu. Ck - Q, Q : các ngõ ra. R Q - Ck : tín hiӋu xung ÿӗng bӝ *ӑi Sn và Rn là trҥng thái ngõ vào Data ӣ xung Ck thӭ n. Hình 2.55. Ký hi͏u RSFF Qn , Qn+1 là trҥng thái cӫa ngõ ra Q ӣ xung Ck thӭ n và thӭ (n+1). Lúc ÿó ta có bҧng trҥng thái mô tҧ hoҥt ÿӝng cӫa RSFF: Sn Rn Qn+1 Ý nghƭa 0 0 Qn Giӳ nguyên trҥng thái trѭӟc ÿó 0 1 0 Xóa ngõ ra Q 1 0 1 ThiӃt lұp ngõ ra Q 1 1 X Trҥng thái cҩm /ѭu ý rҵng trҥng thái khi cҧ 2 ngõ vào S = R = 1 lúc ÿó cҧ 2 ngõ ra có cùng mӭc logic, ÿây là trҥng thái cҩm cӫa RSFF (thѭӡng ÿѭӧc ký hiӋu X). %ҦNG ĈҪU VÀO KÍCH CӪA FLIP-FLOP: TiӃp theo chúng ta sӁÿi xây dӵng bҧng ÿҫu vào kích cӫa RSFF. %̫ng ÿ̯u vào kích g͛m 2 ph̯n, ph̯n bên trái li͏t kê ra các yêu c̯u c̯n chuy͋n ÿ͝i cͯa FF, và ph̯n bên ph̫i là các ÿL͉u ki͏n tín hi͏u ÿ̯u vào kích c̯n ÿ̫m b̫o ÿ͋ÿ̩t ÿ˱ͫc các s͹ chuy͋n ÿ͝i ̭y. NӃu các ÿLӅu kiӋn ÿҫu vào ÿѭӧc ÿҧm bҧo thì FF sӁ chuyӇn ÿәi theo ÿúng yêu cҫu. Thӵc chҩt bҧng ÿҫu vào kích cӫa FF là sӵ khai triӇn bҧng trҥng thái cӫa FF. Ta viӃt lҥi bҧng trҥng thái cӫa RSFF ӣ dҥng khai triӇn nhѭ sau: Sn Rn Qn Qn+1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 X 1 1 1 X
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 40 Trong bҧng này, tín hiӋu ngõ ra ӣ trҥng thái tiӃp theo (Qn+1) sӁ phө thuӝc vào tín hiӋu các ngõ vào data (S, R) và tín hiӋu ngõ ӣ ra trҥng thái hiӋn tҥi (Qn). Tӯ bҧng khai triӇn trên ta xây dӵng ÿѭӧc bҧng ÿҫu vào kích cho RSFF: Qn Qn+1 Sn Rn 0 0 0 X 0 1 1 0 1 0 0 1 1 1 X 0 &Ǌng tӯ bҧng trҥng thái khai triӇn ta có thӇ tìm ÿѭӧc phѭѫng trình logic cӫa RSFF bҵng cách lұp Vѫÿӗ Karnaugh nhѭ sau: Qn+1 SnRn Q n 00 01 11 10 0 0 0 X 1 1 1 0 X 1 7ӯ bҧng Karnaugh này ta có phѭѫng trình logic cӫa RSFF: n n Qn +1 = S + RnQ Vì ÿLӅu kiӋn cӫa RSFF là S.R= 0 nên ta có phѭѫng trình logic cӫa RSFF ÿѭӧc viӃt ÿҫy ÿӫ nhѭ sau: n n Qn +1 = S + RnQ SR=0 'ҥng sóng minh hӑa hoҥt ÿӝng cӫa RSFF trên hình 2.56: Ck 1 2 3 4 5 t 0 S t 0 R t 0 Q t 0 Hình 2.56. Ĉ͛ th͓ thͥi gian d̩ng sóng RSFF
Chѭѫng 2. Các phҫn tӱ logic cѫ bҧn – Flip Flop Trang 41 b. TFF TFF là FF có ngõ vào và ngõ ra ký hiӋu và bҧng trҥng thái hoҥt ÿӝng nhѭ hình vӁ (hình 2.57): Trong ÿó: - T: ngõ vào dӳ liӋu - Q, Q : các ngõ ra - Ck: tín hiӋu xung ÿӗng bӝ. n n+1 T Q T Q n Ck 0 Q n Q 1 Q Hình 2.57. Ký hiӋu và bҧng trҥng thái hoҥt ÿӝng cӫa TFF *ӑi Tn là trҥng thái cӫa ngõ vào DATA T ӣ xung Ck thӭ n. *ӑi Qn , Qn+1 là trҥng thái cӫa ngõ ra ӣ xung Ck thӭ n và (n+1). Lúc ÿó ta có bҧng trҥng thái hoҥt ÿӝng khai triӇn cӫa TFF. 7ӯ bҧng trҥng thái này ta có nhұn xét: + Khi T=0: mӛi khi có xung Ck tác ÿӝng ngõ ra Q giӳ nguyên trҥng thái cǊ trѭӟc ÿó. + Khi T=1: mӛi khi có xung Ck tác ÿӝng ngõ ra Q ÿҧo trҥng thái so vӟi trҥng thái trѭӟc ÿó. Tn Qn Qn+1 0 0 0 0 1 1 1 0 1 1 1 0 7ӯ bҧng trҥng thái khai triӇn cӫa TFF ta tìm ÿѭӧc bҧng ÿҫu vào kích cӫa TFF nhѭ sau: Qn Qn+1 Tn 0 0 0 0 1 1 1 0 1 1 1 0 Phѭѫng trình logic cӫa TFF: Qn+1 = Tn .Qn + Tn .Qn (dҥng chính tҳc 1) Hoһc: Qn+1 = (Tn + Qn )(Tn + Qn ) (dҥng chính tҳc 2). ViӃt gӑn hѫn: Q n+1 = T n Å Q n (SV có th͋ l̵p Karnaugh và t͙i thi͋u hóa ÿ͋ tìm ph˱˯ng trinh logic cͯa TFF). Trên hình 2.58 minh hӑa ÿӗ thӏ thӡi gian dҥng sóng cӫa TFF. - Tín hiӋu ra Q ÿҫu tiên luôn luôn ӣ mӭc logic 0
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 42 - Tín hiӋu Ck(1) ÿLӅu khiӇn theo sѭӡn xuӕng nhìn tín hiӋu T dѭӟi mӭc logic 1. Theo bҧng trҥng thái : T0 = 1 và Q0 = 0 Þ Q1 = Q0 = 1. - Tín hiӋu Ck(2) ÿLӅu khiӇn theo sѭӡn xuӕng nhìn tín hiӋu T dѭӟi mӭc logic 0. Theo bҧng trҥng thái : T1 = 0 và Q1 = 1 Þ Q2 = Q1 = 1 (Giӳ nguyên trҥng thái trѭӟc ÿó). - Tín hiӋu Ck(3) ÿLӅu khiӇn theo sѭӡn xuӕng nhìn tín hiӋu T dѭӟi mӭc logic 1. Theo bҧng trҥng thái: T2 = 1 và Q2 = 1 Þ Q3 = Q2 = 0. Ck 1 2 3 t 0 T t 0 Q t 0 Hình 2.58 Trѭӡng hӧp ngõ vào T luôn luôn bҵng 1 (luôn ӣ mӭc logic 1): Ck 1 2 3 4 5 t 0 T t 0 Q t 0 Hình 2.59. D̩ng sóng ngõ ra khi T=1 Khi T=1 thì dҥng sóng ngõ ra Q ÿѭӧc cho trên hình vӁ. Ta có nhұn xét rҵng chu kǤ cӫa ngõ ra Q Eҵng 2 lҫn chu kǤ tín hiӋu xung Ck nên tҫn sӕ cӫa ngõ ra là: f f = CK Q 2 9ұy, khi T=1 thì TFF giӳ vai trò mҥch chia tҫn sӕ xung vào Ck. 7әng quát: Ghép nӕi tiӃp n TFF vӟi nhau sao cho ngõ ra cӫa TFF trѭӟc sӁ nӕi vӟi ngõ vào cӫa TFF ÿӭng sau (Cki+1 nӕi vӟi Qi ) và lúc bây giӡ tҩt cҧ các ngõ vào DATA T ӣ tҩt cҧ các TFF ÿӅu giӳ mӭc logic 1, lúc ÿó tҫn sӕ tín hiӋu ngõ ra sӁ là: f f = CK Qn 2 n Yӟi Qn là tín hiӋu ngõ ra cӫa TFF thӭ n; fCK là tҫn sӕ xung clock ӣ ngõ vào ÿӗng bӝ TFF ÿҫu tiên.
Chѭѫng 2. Các phҫn tӱ logic cѫ bҧn – Flip Flop Trang 43 c. DFF DFF là FF có ngõ vào và ngõ ra ký hiӋu nhѭ hình 2.60. %ҧng trҥng thái D Q n+1 Dn Q Ck 0 0 Q 1 1 Hình 2.60. Ký hi͏u DFF Trong ÿó: D là ngõ vào dӳ liӋu. Q, Q : các ngõ ra. Ck: tín hiӋu xung ÿӗng bӝ. *ӑi Dn là trҥng thaïi cӫa ngõ vào DATA D ӣ xung Ck thӭ n. *ӑi Qn, Qn+1 là trҥng thái cӫa ngõ ra ӣ xung Ck thӭ n và (n+1). Khai triӇn bҧng trҥng thái cӫa DFF ÿӇ tìm bҧng ÿҫu vào kích cӫa DFF, ta có: Dn Qn Qn+1 0 0 0 0 1 0 1 0 1 1 1 1 %ҧng ÿҫu vào kích cӫa DFF: Qn Qn+1 Dn 0 0 0 0 1 1 1 0 0 1 1 1 Phѭѫng trình logic cӫa DFF: Qn+1 = Dn Trên hình 2.61 là ÿӗ thӏ thӡi gian dҥng sóng cӫa DFF: Ck 1 2 3 4 5 t 0 D t 0 Q t Hình 2.61. Ĉ͛ th͓ thͥi gian d̩ng sóng cͯa DFF
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 44 Gi̫i thích d̩ng sóng cͯa tín hi͏u trên hình 2.61: - Tín hiӋu ra Q ÿҫu tiên luôn luôn ӣ mӭc logic 0, Q0 = 0 - Tín hiӋu Ck(1) ÿLӅu khiӇn theo sѭӡn xuӕng nhìn tín hiӋu D dѭӟi mӭc logic 1. Theo bҧng trҥng thái ta có: D0 = 1 Þ Q1 = 1 - Tín hiӋu Ck(2) ÿLӅu khiӇn theo sѭӡn xuӕng nhìn tín hiӋu D dѭӟi mӭc logic 0. Theo bҧng trҥng thái ta có :D1 = 0 Þ Q2 = 0 v v D Q DFF ÿóng vai trò mҥch chia tҫn sӕ: Ck Trên hình 2.62 là sѫÿӗ mҥch DFF thӵc hiӋn chӭc năng chia tҫn Q Vӕ. Ӣ mҥch này ngõ ra Q ÿѭӧc nӕi ngѭӧc trӣ vӅ ngõ vào D. - Tín hiӋu ra Q0 ÿҫu tiên luôn ӣ mӭc logic 0: Q0 = 0 Þ Q0 = D1 = 1 Hình 2.62. - Tín hiӋu Ck(1) ÿLӅu khiӇn theo sѭӡn xuӕng nhìn tín hiӋu D1 Gѭӟi mӭc logic 1. D1 = 1 Þ Q1 = 1 Þ Q1 = D2= 0. - Tín hiӋu Ck(2) ÿLӅu khiӇn theo sѭӡn xuӕng nhìn tín hiӋu D2 dѭӟi mӭc logic 0. D2 = 0 Þ Q2 = 0 Þ Q2 = D3 = 1. - Tín hiӋu Ck(3) ÿLӅu khiӇn theo sѭӡn xuӕng nhìn tín hiӋu D3 dѭӟi mӭc logic 1. D3 = 1 Þ Q3 = 1 Þ Q3 = D4 = 0. - Tín hiӋu Ck(4) ÿLӅu khiӇn theo sѭӡn xuӕng nhìn tín hiӋu D4 dѭӟi mӭc logic 0. Þ Q4 = 0 v v Ck 1 2 3 4 5 t 0 D t 0 Q t 0 Hình 2.63. Ĉ͛ th͓ thͥi gian d̩ng sóng m̩ch hình 3.62 Nhұn xét vӅ tҫn sӕ ngõ ra: f f = CK Þ DFF giӳ vai trò nhѭ mҥch chia tҫn sӕ. Q 2 Ӭng dөng cӫa DFF: - Dùng DFF ÿӇ chia tҫn sӕ. - Dùng DFF ÿӇ lѭu trӳ dӳ liӋu ÿӇ chӃ tҥo các bӝ nhӟ và thanh ghi. - Dùng DFF ÿӇ chӕt dӳ liӋu.
Chѭѫng 2. Các phҫn tӱ logic cѫ bҧn – Flip Flop Trang 45 d. JKFF JKFF là FF có ngõ vào và ngõ ra ký hiӋu nhѭ hình vӁ : Trong ÿó: J Q - J, K là các ngõ vào dӳ liӋu. - Q, Q là các ngõ ra. Ck - Ck là tín hiӋu xung ÿӗng bӝ. K Q *ӑi Jn , Kn là trҥng thái ngõ vào J,K ӣ xung Ck thӭ n. n n+1 *ӑi Q , Q là trҥng thái ngõ ra Q ӣ xung Ck thӭ n và (n+1). Hình 2.65. JKFF Lúc ÿó ta có bҧng trҥng thái mô tҧ hoҥt ÿӝng cӫa JKFF: J K Qn+1 0 0 Qn 0 1 0 1 0 1 1 1 Q n Phѭѫng trình logic cӫa JKFF: Qn+1 = Jn Qn + Kn .Qn 7ӯ bҧng trҥng thái ta thҩy JKFF khҳc phөc ÿѭӧc trҥng thái cҩm cӫa RSFF, khi J=K=1 ngõ ra ӣ trҥng thái kӃ tiӃp ÿҧo mӭc logic so vӟi ngõ ra ӣ trҥng thái hiӋn tҥi. ĈӇ tìm bҧng ÿҫu vào kích cӫa JKFF ta khai triӇn bҧng trҥng thái nhѭ sau: Jn Kn Qn Qn+1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 7ӯ bҧng khai triӇn trên ta xây dӵng ÿѭӧc bҧng ÿҫu vào kích cho JKFF nhѭ sau: Qn Qn+1 Sn Rn 0 0 0 X 0 1 1 X 1 0 X 1 1 1 X 0
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 46 Ĉӗ thӏ thӡi gian dҥng sóng cӫa JKFF: Ck 1 2 3 4 5 t 0 J t 0 K t 0 Q t 0 Hình 2.66. Ĉ͛ th͓ thͥi gian d̩ng sóng JKFF Nhұn xét quan trӑng:JKFF là mҥch ÿLӋn có chӭc năng thiӃt lұp trҥng thái 0, trҥng thái 1, chuyӇn ÿәi trҥng thái và duy trì trҥng thái căn cӭ vào các tín hiӋu ÿҫu vào J, K và xung nhӏp ÿӗng Eӝ Ck. Nhѭ vұy có thӇ nói JKFF là mӝt FF rҩt vҥn năng. Trong thӵc tӃ, chúng ta có thӇ dùng JKFF ÿӇ thӵc hiӋn chӭc năng cӫa các FF khác: JKFF thay thӃ cho RSFF, JKFF thӵc hiӋn chӭc năng cӫa TFF và DFF, các sѫÿӗ thӵc hiӋn ÿѭӧc trình bày trên hình 2.67: S J Q T J Q D J Q Ck Ck Ck K Q R K Q K Q Hình 2.67. Dùng JKFF th͹c hi͏n chͱc năng cͯa RSFF, TFF, DFF Trên cѫ sӣ khҧo sát vӅ 4 loҥi FF phân chia theo chӭc năng, chúng ta có thӇ xây dӵng mӝt bҧng ÿҫu vào kích tәng hӧp cho cҧ 4 loҥi FF nhѭ sau: Qn Qn+1 Sn Rn Jn Kn Tn Dn 0 0 0 X 0 X 0 0 0 1 1 0 1 X 1 1 1 0 0 1 X 1 1 0 1 1 X 0 X 0 0 1
Chѭѫng 2. Các phҫn tӱ logic cѫ bҧn – Flip Flop Trang 47 2.3.3. Sӵ chuyӇn ÿәi lүn nhau giӳa các loҥi FF Ĉa sӕ FF trên thӏ trѭӡng là loҥi JK, D trong khi kӻ thuұt sӕ yêu cҫu tҩt cҧ các loҥi FF. NӃu biӃt cách chuyӇn ÿәi giӳa các loҥi FF vӟi nhau thì có thӇ phát huy tác dөng cӫa loҥi FF sҹn có. Trên thӵc tӃ, có thӇ chuyӇn ÿәi qua lҥi giӳa các loҥi FF khác nhau. Có 2 phѭѫng pháp ÿӇ thӵc hiӋn chuyӇn ÿәi giӳa các loҥi FF: - phѭѫng pháp biӃn ÿәi trӵc tiӃp. - phѭѫng pháp dùng bҧng ÿҫu vào kích và bҧng Karnaugh. 1. Phѭѫng pháp biӃn ÿәi trӵc tiӃp: Ĉây là phѭѫng pháp sӱ dөng các ÿӏnh lý, tiên ÿӅ cӫa ÿҥi sӕ Boole ÿӇ tìm phѭѫng trình logic tín hiӋu kích thích ÿӕi vӟi FF xuҩt phát. Sѫÿӗ khӕi thӵc hiӋn phѭѫng pháp này nhѭ sau (hình 3.68): FF ÿích Logic FF Q Ĉҫu vào chuyӇn ÿәi xuҩt phát Q Hình 2.68 Ck TFF chuyӇn ÿәi thành DFF, RSFF, JKFF: - TFF ® RSFF: RSFF có pt: Qn+1 = Sn + Rn Qn (1) Sn Rn = 0 (ÿLӅu kiӋn cӫa RSFF) TFF có pt: Qn+1 = Tn Å Qn (2) So sánh (1) và (2) ta có: S n + Rn Qn = Tn Å Qn Theo tính chҩt cӫa phép toán XOR, ta có: n n n n n n n n n n n n n T = Q Å(S + R Q ) = Q (S + R Q ) + Q (S + R Q ) = Qn Sn Rn + Sn Qn = Qn Sn Rn + Sn Qn + Sn Rn = Qn Rn + Sn Qn 9ұy: Tn = Qn Rn + Sn Qn 6ѫÿӗ mҥch thӵc hiӋn: R T Q S Ck Q Hình 2.69. Chuy͋n ÿ͝i TFF thành RSFF - TFF® DFF:
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 48 DFF có phѭѫng trình logic: Qn+1 = Dn TFF có phѭѫng trình logic: Qn+1 = Tn Å Qn Ĉӗng nhҩt 2 phѭѫng trình: Dn = Tn Å Qn Theo tính chҩt cӫa phép XOR ta suy ra: Tn = Dn Å Qn Sѫÿӗ mҥch thӵc hiӋn: T Q D Ck Ck Q Hình 2.70. Chuy͋n ÿ͝i TFF thành DFF - TFF® DFF: Thӵc hiӋn biӃn ÿәi hoàn toàn tѭѫng tӵ (nhѭ trѭӡng hӧp chuyӇn ÿәi tӯ TFF sang RSFF) ta có logic chuyӇn ÿәi: Tn = KnQn + Jn Qn Sѫÿӗ mҥch chuyӇn ÿәi tӯ TFF sang JKFF K T Q J Ck Q Hình 2.71. Chuy͋n ÿ͝i TFF thành JKFF DFF chuyӇn ÿәi thành TFF, RSFF, JKFF: - DFF® TFF: DFF có phѭѫng trình logic: Qn+1 = Dn TFF có phѭѫng trình logic: Qn+1 = Tn Å Qn Ĉӗng nhҩt 2 phѭѫng trình ta có: Dn = Tn Å Qn Sѫÿӗ mҥch thӵc hiӋn chuyӇn ÿәi (hình 2.72): D Q T Ck Ck Q Hình 2.72. Chuy͋n ÿ͝i DFF thành TFF - DFF® RSFF: RSFF có phѭѫng trình logic: Qn+1 = Sn + Rn Qn Ĉӗng nhҩt vӟi phѭѫng trình cӫa DFF ta có: Dn = Sn + Rn Qn Sѫÿӗ mҥch thӵc hiӋn chuyӇn ÿәi:
Chѭѫng 2. Các phҫn tӱ logic cѫ bҧn – Flip Flop Trang 49 R D Q S Ck Q Hình 2.73. Chuy͋n ÿ͝i tͳ DFF sang RSFF - DFF® JKFF: Hoàn toàn tѭѫng tӵ ta có logic chuyӇn ÿәi tӯ DFF sang JKFF: Dn = Jn Qn + Kn Qn Sѫÿӗ mҥch chuyӇn ÿәi trên hình 2.74: K D Q J Ck Q Hình 2.74. Chuy͋n ÿ͝i DFF thành JKFF RSFF chuyӇn ÿәi thành TFF, DFF, JKFF: RSFF có pt: Qn+1 = Sn + Rn Qn Sn Rn = 0 (ÿLӅu kiӋn cӫa RSFF) Khi thӵc hiӋn chuyӇn ÿәi tӯ RSFF sang các FF khác cҫn kiӇm tra ÿLӅu kiӋn ràng buӝc cӫa RSFF ÿó là: RnSn = 0. - RSFF® TFF: TFF có phѭѫng trình logic: Qn+1 = Tn Å Qn Ĉӗng nhҩt vӟi phѭѫng trình cӫa RSFF ta có: Sn + Rn Qn = Tn Å Qn = Tn Qn + Tn Qn Tӯ biӇu thӭc này, nӃu ta ÿӗng nhҩt: Sn = Tn Qn R n = Tn thì suy ra: Sn Rn = Tn Qn .Tn = Tn Qn ¹ 0 nên không thӓa mãn ÿLӅu kiӋn cӫa RSFF. Thӵc hiӋn biӃn ÿәi tiӃp: Sn + Rn Qn = Tn Qn + Tn Qn = Tn Qn + Tn Qn + Qn Qn Sn + Rn Qn = Tn Qn + (Tn + Qn )Qn = Tn Qn + TnQn Qn
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 50 Ĉӗng nhҩt 2 vӃ ta có: Sn = Tn Qn R Q Rn = Tn Qn T n n thӓa mãn ÿLӅu kiӋn: R S = 0. Ck 6ѫÿӗ thӵc hiӋn: hình 2.75. S Q Hình 2.75. Chuy͋n ÿ͝i RSFF sang TFF - RSFF® DFF: Qn+1 = Dn Ĉӗng nhҩt 2 phѭѫng trình: Sn + Rn Qn = Dn Thӵc hiӋn biӃn ÿәi: Sn + Rn Qn = Dn = Dn (Qn + Qn ) = Dn Qn+ Dn Qn (a) Mһt khác biӇu thӭc cӫa RSFF có thӇ biӃn ÿәi nhѭ sau: Sn + Rn Qn = Sn(Qn + Qn ) + Rn Qn = SnQn + Sn Qn + Rn Qn = SnQn (Rn + Rn ) + Sn Qn + Rn Qn = SnQn Rn + Sn Qn + Rn Qn = Rn Qn (1 + Sn) + Sn Qn = Rn Qn + Sn Qn (b) Tӯ (a) và (b) ta có: Dn Qn + Dn Qn = Rn Qn + Sn Qn Ĉӗng nhҩt 2 vӃ suy ra: D R Q Sn = Dn Ck Rn = Dn S Q thӓa mãn ÿLӅu kiӋn RnSn = 0. 6ѫÿӗ thӵc hiӋn: hình 2.76. Hình 2.76. RSFF® DFF - RSFF® JKFF: Ĉӗng nhҩt 2 phѭѫng trình logic cӫa RSFF và JKFF ta có: Qn+1 = Sn + Rn Qn = Jn Qn + Kn Qn n n n n n n n n n = J Qn + Kn Q + Q Qn = J Qn + ( Kn + Qn )Q = J Qn + K Q Q So sánh ta có: S n = Jn Qn K R Q Rn = KnQn thӓa mãn ÿLӅu kiӋn cӫa RSFF. Ck J 6ѫÿӗ thӵc hiӋn: hình 2.77. S Q Hình 2.77. RSFF® JKFF
Chѭѫng 2. Các phҫn tӱ logic cѫ bҧn – Flip Flop Trang 51 JKFF chuyӇn ÿәi thành TFF, DFF, RSFF: Nhѭÿã trình bày ӣ trên, JKFF là mӝt FF vҥn năng, có thӇ dùng JKFF ÿӇ thay thӃ cho RSFF hoһc dùng JKFF thӵc hiӋn chӭc năng DFF, TFF. Sѫÿӗ thӵc hiӋn các mҥch này nhѭӣ hình 2.67. Phҫn này tұp trung chӭng minh các biӇu thӭc logic chuyӇn ÿәi tӯ JKFF sang các FF khác. JKFF có phѭѫng trình logic: Qn+1 = Jn Qn + Kn Qn - JKFF® TFF: TFF có phѭѫng trình logic: Qn+1 = Tn Å Qn = Tn Qn + Tn Qn So sánh vӟi phѭѫng trình cӫa JKFF ta suy ra logic chuyӇn ÿәi: Jn = Tn Kn = Tn - JKFF® DFF: DFF có phѭѫng trình logic: Qn+1 = Dn ViӃt lҥi biӇu thӭc này ta có: Qn+1=Dn=Dn (Qn + Qn ) = DnQn+ Dn Qn So sánh vӟi biӇu thӭc cӫa JKFF ta có logic chuyӇn ÿәi: Jn = Dn Kn = Dn - JKFF® RSFF: Ĉӕi vӟi RSFF có phѭѫng trình logic ÿã tìm ÿѭӧc ӣ công thӭc (b): Qn+1 = Sn + Rn Qn = Sn Qn + Rn Qn (b) So sánh vӟi phѭѫng trình logic cӫa JKFF ta có logic chuyӇn ÿәi: Jn = Sn Kn = Rn 2. Phѭѫng pháp dùng bҧng ÿҫu vào kích và bҧng Karnaugh: Trong phѭѫng pháp này, các ÿҫu vào dӳ liӋu (data) hay ÿҫu vào kích cӫa FF ban ÿҫu là hàm ra Yӟi các biӃn là trҥng thái ngõ ra Qn và các ÿҫu vào data cӫa FF cҫn chuyӇn ÿәi. ĈӇ thӵc hiӋn chuyӇn ÿәi ta dӵa vào bҧng tín hiӋu ÿҫu vào kích cӫa các FF và lұp bҧng Karnaugh, thӵc hiӋn tӕi giҧn ÿӇ tìm logic chuyӇn ÿәi. Bҧng tín hiӋu ÿҫu vào kích tәng hӧp nhѭ sau: Qn Qn+1 Sn Rn Jn Kn Tn Dn 0 0 0 X 0 X 0 0 0 1 1 0 1 X 1 1 1 0 0 1 X 1 1 0 1 1 X 0 X 0 0 1 Xét các trѭӡng hӧp cө thӇ: - chuyӇn ÿәi tӯ JKFF ® TFF : J = f (T,Qn) và K = f (T,Qn) - chuyӇn ÿәi tӯ JKFF ® DFF : J = f (D,Qn) và K = f (D,Qn) - chuyӇn ÿәi tӯ JKFF ® RSFF : J = f (S,R,Qn) và K = f (S,R,Qn) - chuyӇn ÿәi tӯ RSFF ® TFF : R = f (T,Qn) và S = f (T,Qn) - chuyӇn ÿәi tӯ RSFF ® DFF : R = f (D,Qn) và S = f (D,Qn) - chuyӇn ÿәi tӯ RSFF ® JKFF : R = f (J, K,Qn) và S = f (J,K,Qn)
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 52 - chuyӇn ÿәi tӯ TFF ® DFF : T = f (D,Qn) - chuyӇn ÿәi tӯ TFF ® RSFF : T = f (R,S,Qn) - chuyӇn ÿәi tӯ TFF ® JKFF : T = f (J,K,Qn) - chuyӇn ÿәi tӯ DFF ® TFF : D = f (T,Qn) - chuyӇn ÿәi tӯ DFF ® RSFF : D = f (R,S,Qn) - chuyӇn ÿәi tӯ DFF ® JKFF : D = f (J,K,Qn) Ví dө 1: ChuyӇn ÿәi tӯ JKFF ® DFF dùng phѭѫng pháp bҧng. Ta có các hàm cҫn tìm: J = f (D, Qn) và K = f (D, Qn) 'ӵa vào bҧng ÿҫu vào kích tәng hӧp ta lұp bҧng Karnaugh: J K D D Qn 0 1 Qn 0 1 0 0 1 0 X X 1 X X 1 1 0 J = D K = D 7ӕi giҧn theo dҥng chính tҳc 1 ta có: J = D và K = D . Ví dө 2: ChuyӇn ÿәi tӯ JKFF ® RSFF dùng phѭѫng pháp bҧng. Ta có các hàm cҫn tìm: J = f (S,R,Qn) K = f (S,R,Qn) 'ӵa vào bҧng ÿҫu vào kích tәng hӧp lұp bҧng Karnaugh (xem bҧng). 7ӕi giҧn theo dҥng chính tҳc 1 ta có: J = S và K = R. J K SR SR Qn 00 01 11 10 Qn 00 01 11 10 0 0 0 X 1 0 X X X X 1 X X X X 1 0 1 X 0 J = S K = R
Chѭѫng 3. HӋ tә hӧp Trang 53 Chѭѫng 3 +ӊ TӘ HӦP 3.1.KHÁI NIӊM CHUNG Các cәng logic AND, OR, NOR, NAND là các phҫn tӱ logic cѫ bҧn còn ÿѭӧc gӑi là hӋ tә hӧp ÿѫn giҧn. Nhѭ vұy, hӋ tә hӧp là hӋ có các ngõ ra là các hàm logic theo ngõ vào, ÿLӅu này nghƭa là khi mӝt trong các ngõ vào thay ÿәi trҥng thái lұp tӭc làm cho ngõ ra thay ÿәi trҥng thái ngay (nӃu Eӓ qua thӡi gian trӉ cӫa các phҫn tӱ logic) mà không chӏu ҧnh hѭӣng cӫa trҥng thái ngõ ra trѭӟc ÿó. Xét mӝt hӋ tә hӧp có n ngõ vào và có m ngõ ra (hình 3.1), ta có: y1 = f(x1, x2, , xn ) x1 y y2 = f(x1, x2, , xn ) 1 x2 +Ӌ tә y2 Kӧp ym = f(x1, x2, , xn ) ym xn Hình 3.1 Nhѭ vұy, sӵ thay ÿәi cӫa ngõ ra yj (j = 1 ¸ m) theo các biӃn vào xi (i = 1 ¸ n) là tuǤ thuӝc vào Eҧng trҥng thái mô tҧ hoҥt ÿӝng cӫa hӋ tә hӧp. Ĉһc ÿLӇm cѫ bҧn cӫa hӋ tә hӧp là tín hiӋu ra tҥi mӛi thӡi ÿLӇm chӍ phө thuӝc vào giá trӏ các tín hiӋu vào ӣ thӡi ÿLӇm ÿó mà không phө thuӝc vào giá trӏ các tín hiӋu ngõ ra ӣ thӡi ÿLӇm trѭӟc ÿó. Trình tӵÿӇ thiӃt kӃ hӋ tә hӧp theo các bѭӟc sau: 1. Tӯ yêu cҫu thӵc tӃ ta lұp bҧng trҥng thái mô tҧ hoҥt ÿӝng cӫa mҥch (hӋ tә hӧp). 2. Dùng các phѭѫng pháp tӕi thiӇu ÿӇ tӕi thiӇu hoá các hàm logic. 3. Thành lұp sѫÿӗ logic (Dӵa vào phѭѫng trình logic ÿã tӕi giҧn). 4. Thành lұp sѫÿӗ hӋ tә hӧp. Các mҥch tә hӧp thông dөng: - Mҥch mã hoá - giҧi mã - Mҥch chӑn kênh - phân ÿѭӡng - 0ҥch sӕ hӑc v v 3.2. MҤCH MÃ HOÁ & MҤCH GIҦI MÃ 3.2.1. Khái niӋm: 0ҥch mã hoá (ENCODER) là mҥch có nhiӋm vө biӃn ÿәi nhӳng ký hiӋu quen thuӝc vӟi con ngѭӡi sang nhӳng ký hiӋu không quen thuӝc con ngѭӡi. Ngѭӧc lҥi, mҥch giҧi mã (DECODER) là Pҥch làm nhiӋm vө biӃn ÿәi nhӳng ký hiӋu không quen thuӝc vӟi con ngѭӡi sang nhӳng ký hiӋu quen thuӝc vӟi con ngѭӡi.
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 54 3.2.2. Mҥch mã hoá (Encoder) 1. Mҥch mã hoá nhӏ phân Xét mҥch mã hóa nhӏ phân tӯ 8 sang 3 (8 ngõ vào và 3 ngõ ra). Sѫÿӗ khӕi cӫa mҥch ÿѭӧc cho trên hình 3.2. x0 C x2 8 ® 3 B A x7 Hình 3.2 S˯ÿ͛ kh͙i m̩ch mã hóa nh͓ phân tͳ 8 sang 3 Trong ÿó: - x0, x1, , x7 là 8 ÿѭӡng tín hiӋu vào - A, B, C là 3 ngõ ra. 0ҥch mã hóa nhӏ phân thӵc hiӋn biӃn ÿәi tín hiӋu ngõ vào thành mӝt tӯ mã nhӏ phân tѭѫng ӭng ӣ ngõ ra, cө thӇ nhѭ sau: 0 ® 000 3 ® 011 6 ® 100 1 ® 001 4 ® 100 7 ® 111 2 ® 010 5 ® 101 Chӑn mӭc tác ÿӝng (mӭc tích cӵc) ӣ ngõ vào là mӭc logic 1, ta có bҧng trҥng thái mô tҧ hoҥt ÿӝng cӫa mҥch : x0 x1 x2 x3 x4 x5 x6 x7 C B A 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 Giҧi thích bҧng trҥng thái: Khi mӝt ngõ vào ӣ trҥng thái tích cӵc (mӭc logic 1) và các ngõ vào còn lҥi không ÿѭӧc tích cӵc (mӭc logic 0) thì ngõ ra xuҩt hiӋn tӯ mã tѭѫng ӭng. Cө thӇ là: khi ngõ vào x0 = 1 và các ngõ vào còn lҥi bҵng 0 thì tӯ mã ӣ ngõ ra là 000, khi ngõ vào x1 = 1 và các ngõ vào còn lҥi bҵng 0 thì tӯ mã nhӏ phân ӣ ngõ ra là 001, v v Phѭѫng trình logic tӕi giҧn: A = x1 + x3 + x5 + x7 B = x2 + x3 + x6 + x7 C= x4 + x5 + x6 + x7
Chѭѫng 3. HӋ tә hӧp Trang 55 6ѫÿӗ logic thӵc hiӋn mҥch mã hóa nhӏ phân tӯ 8 sang 3 (hình 3.3): x1 x2 x3 x4 x5 x6 x7 C B A Hình 3.3 M̩ch mã hóa nh͓ phân tͳ 8 sang 3 NӃu chӑn mӭc tác ÿӝng tích cӵc ӣ ngõ vào là mӭc logic 0, bҧng trҥng thái mô tҧ hoҥt ÿӝng cӫa Pҥch lúc này nhѭ sau: x0 x1 x2 x3 x4 x5 x6 x7 C B A 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 Phѭѫng trình logic tӕi giҧn : A = x 1 + x 3 + x 5 + x 7 = x1x 3x 5x 7 B = x 2 + x 3 + x 6 + x 7 = x 2x3x 6x 7 C = x 4 + x 5 + x 6 + x 7 = x 4x5x 6x7 6ѫÿӗ mҥch thӵc hiӋn cho trên hình 3.5 x1 x2 x3 x4 x5 x6 x7 C B A Hình 3.5 M̩ch mã hóa nh͓ phân 8 sang 3 ngõ vào tích c͹c mͱc 0
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 56 2. Mҥch mã hoá thұp phân x 0 D x 1 C 10 ® 4 B A x9 Hình 3.6 S˯ÿ͛ kh͙i m̩ch mã hóa tͳ 10 sang 4 %ҧng trҥng thái mô tҧ hoҥt ÿӝng cӫa mҥch : x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 D C B A 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 Phѭѫng trình logic ÿã tӕi giҧn: A = x1 + x3 + x5 + x7 + x9 B = x2 + x3 + x6 + x7 C = x4 + x5 + x6 + x7 D = x8 + x9 BiӇu diӉn bҵng sѫÿӗ logic (hình 3.7) x1 x2 x3 x4 x5 x6 x7 x8 x9 DC C B A Hình 3.7 S˯ÿ͛ m̩ch mã hóa th̵p phân tͳ 10 ® 4
Chѭѫng 3. HӋ tә hӧp Trang 57 3. Mҥch mã hoá ѭu tiên Trong hai mҥch mã hoá ÿã xét ӣ trên, tín hiӋu ÿҫu vào tӗn tҥi ÿӝc lұp tӭc là không có tình huӕng có 2 tín hiӋu trӣ lên ÿӗng thӡi tác ÿӝng ӣ mӭc logic 1 (nӃu ta chӑn mӭc tích cӵc ӣ ngõ vào là mӭc logic 1), thӵc tӃÿây là tình huӕng hoàn toàn có thӇ xҧy ra, do ÿó cҫn phҧi ÿһt ra vҩn ÿӅѭu tiên. 9ҩn ÿӅѭu tiên: Khi có nhiӅu tín hiӋu vào ÿӗng thӡi tác ÿӝng, tín hiӋu nào có mӭc ѭu tiên cao Kѫn ӣ thӡi ÿLӇm ÿang xét sӁÿѭӧc ѭu tiên tác ÿӝng, tӭc là nӃu ngõ vào có ÿӝѭu tiên cao hѫn bҵng 1 trong khi nhӳng ngõ vào có ÿӝѭu tiên thҩp hѫn nӃu bҵng 1 thì mҥch sӁ tҥo ra tӯ mã nhӏ phân ӭng Yӟi ngõ vào có ÿӝѭu tiên cao nhҩt. Xét mҥch mã hoá ѭu tiên 4 ® 2 (4 ngõ vào, 2 ngõ ra) (hình 3.9). %̫ng tr̩ng thái x0 B x1 x0 x1 x2 x3 B A 4 ® 2 x2 A 1 0 0 0 0 0 x3 x 1 0 0 0 1 x x 1 1 0 Hình 3.9 0 x x x 1 1 1 7ӯ bҧng trҥng thái có thӇ viӃt ÿѭӧc phѭѫng trình logic các ngõ ra A và B: A = x . = x .x + x 1 x2.x3 + x3 1 2 3 B = x2.x3 + x3 = x2 + x3 x1 x2 x3 B A Hình 3.10 S˯ÿ͛ logic m̩ch mã hóa ˱u tiên 4 ® 2 6ѫÿӗ logic: hình 3.10. Mӝt sӕ vi mҥch mã hóa ѭu tiên thông dөng: 74LS147, 74LS148. 3.2.3. Mҥch giҧi mã (Decoder) 1. Mҥch giҧi mã nhӏ phân Xét mҥch giҧi mã nhӏ phân 2 ® 4 (2 ngõ vào, 4 ngõ ra) nhѭ trên hình 3.11 Chӑn mӭc tích cӵc ӣ ngõ ra là mӭc logic 1.
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 58 %ҧng trҥng thái y0 B A y y y y B 0 1 2 3 y1 0 0 1 0 0 0 2 ® 4 y A 2 0 1 0 1 0 0 y3 1 0 0 0 1 0 1 1 0 0 0 1 Hình 3.11 M̩ch gi̫i mã 2 sang 4 Phѭѫng trình logic tӕi giҧn và sѫÿӗ mҥch thӵc hiӋn y0 = B.A y1 = B.A y2 = B.A y3 = A.B Trѭӡng hӧp chӑn mӭc tích cӵc ӣ ngõ ra là mӭc logic 0 (mӭc logic thҩp) ta có sѫÿӗ khӕi mҥch giҧi mã ÿѭӧc cho trên hình 3.14. y0 %̫ng tr̩ng thái B y 1 B A y0 y1 y2 y3 2® 4 y2 0 0 0 1 1 1 A 0 1 1 0 1 1 y3 1 0 1 1 0 1 Hình 3.14. Mͱc tích c͹c ngõ ra là mͱc th̭p 1 1 1 1 1 0 Phѭѫng trình logic: y0 = B + A = B.A y1 = B + A = B.A y2 = B + A = BA y3 = B + A = B.A
Chѭѫng 3. HӋ tә hӧp Trang 59 6ѫÿӗ mҥch thӵc hiӋn: B A x1 x2 y0 y1 y2 y3 Hình 3.15. M̩ch gi̫i mã 2 ® 4 vͣi ngõ ra mͱc tích c͹c th̭p 2. Mҥch giҧi mã LED 7 ÿRҥn Ĉèn LED 7 ÿRҥn có cҩu tҥo gӗm 7 ÿRҥn LED, mӛi ÿRҥn là 1 ÿèn LED. TuǤ theo cách nӕi các Kathode (Catӕt) hoһc các Anode (Anӕt) cӫa các LED trong ÿèn, mà ngѭӡi ta phân thành hai loҥi: - LED 7 ÿRҥn loҥi Anode chung: A a f b g e c d a b c d e f g Hình 3.20. LED 7 ÿRҥn loҥi Anode chung - LED 7 ÿRҥn loҥi Kathode chung : a b c d e f g K Hình 3.21. LED 7 ÿR̩n lo̩i Kathode chung
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 60 Ӭng vӟi mӛi loҥi LED khác nhau ta có mӝt mҥch giҧi mã riêng. Sѫÿӗ khӕi cӫa mҥch giҧi mã LED 7 ÿRҥn nhѭ sau: a A b 0ҥch c B giҧi mã d LED C e 7 ÿRҥn f (4®7) D g Hình 3.22. S˯ÿ͛ kh͙i m̩ch gi̫i mã LED 7ÿR̩n Giҧi mã LED 7 ÿRҥn loҥi Anode chung: Ĉӕi vӟi LED bҧy ÿRҥn loҥi anode chung, vì các anode cӫa các ÿRҥn led ÿѭӧc nӕi chung vӟi nhau và ÿѭa lên mӭc logic 1 (5V), nên muӕn ÿRҥn led nào tҳt ta nӕi kathode tѭѫng ӭng lên mӭc logic 1 (5V) và ngѭӧc lҥi muӕn ÿRҥn led nào sáng ta nӕi kathode tѭѫng ӭng xuӕng mass (mӭc logic 0). Ví dͭ: ĈӇ hiӇn thӏ sӕ 0 ta nӕi kathode cӫa ÿèn g lên mӭc logic 1 ÿӇÿèn g tҳt, và nӕi các kathode Fӫa ÿèn a, b, c, d, e, f xuӕng mass nên ta thҩy sӕ 0. Lúc ÿó bҧng trҥng thái mô tҧ hoҥt ÿӝng cӫa mҥch giҧi mã LED bҧy ÿRҥn loҥi Anode chung nhѭ sau: D B C A a b c d e f g Sӕ hiӇn thӏ 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 2 0 0 1 1 0 0 0 0 1 1 0 3 0 1 0 0 1 0 0 1 1 0 0 4 0 1 0 1 0 1 0 0 1 0 0 5 0 1 1 0 0 1 0 0 0 0 0 6 0 1 1 1 0 0 0 1 1 1 1 7 1 0 0 0 0 0 0 0 0 0 0 8 1 0 0 1 0 0 0 0 1 0 0 9 1 0 1 0 X X X X X X X X 1 0 1 1 X X X X X X X X 1 1 0 0 X X X X X X X X 1 1 0 1 X X X X X X X X 1 1 1 0 X X X X X X X X 1 1 1 1 X X X X X X X X Dùng bҧng Karnaugh ÿӇ tӕi thiӇu hóa mҥch trên. Phѭѫng trình tӕi thiӇu hóa có thӇ viӃt ӣ dҥng chính tҳc 1 (tәng cӫa các tích sӕ) hoһc dҥng chính tҳc 2 (tích cӫa các tәng sӕ):
Chѭѫng 3. HӋ tә hӧp Trang 61 Phѭѫng trình logic cӫa ngõ ra a: a '̩ng chính t̷c 2: DC BA a = B.D.(C + A)(C + A) = BCDA + BDCA 00 01 11 10 00 0 1 x 0 '̩ng chính t̷c 1: 01 1 0 x 0 a = CBA + DCBA 11 0 0 x x /˱u ý: Trên b̫ng Karnaugh chúng ta ÿã th͹c hi͏n t͙i thi͋u hóa theo 10 0 0 x x G̩ng chính t̷c 2. Phѭѫng trình logic cӫa ngõ ra b: b DC '̩ng chính t̷c 2: BA 00 01 11 10 b = .C(A + B)(A + B) = C(AB + AB) 00 0 0 x 0 = C(A Å B) 01 0 1 x 0 '̩ng chính t̷c 1: 11 0 0 x x b = CBA + CBA = C(A Å B) 10 0 1 x x Phѭѫng trình logic cӫa ngõ ra c: c DC '̩ng chính t̷c 2: BA 00 01 11 10 c = BAC 00 0 0 x 0 '̩ng chính t̷c 1: 01 0 0 x 0 c = DCBA 11 0 0 x x 10 1 0 x x Phѭѫng trình logic cӫa ngõ ra d: d '̩ng chính t̷c 2: DC BA 00 01 11 10 d = D(A + B + C)(B + C + D)(A + B)(A + C) 00 0 1 x 0 = ABCD + ABCD + ABCD 01 1 0 x 0 '̩ng chính t̷c 1: 11 0 1 x x d = CBA + DCBA + CBA 10 0 0 x x Ph˱˯ng trình logic cͯa ngõ ra e: '̩ng chính t̷c 2: e DC BA 00 01 11 10 e = .(B + A)(C+ A) 00 0 1 x 0 '̩ng chính t̷c 1: 01 1 1 x 1 e = CB + A 11 1 1 x x 10 0 0 x x
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 62 Ph˱˯ng trình logic cͯa ngõ ra f: '̩ng chính t̷c 2: f f = DC (A + B)(B+ C)(A + B + C)D BA 00 01 11 10 = ABD + ACD + BCD 00 0 0 x 0 '̩ng chính t̷c 1: 01 1 0 x 0 f = BA + DCA + DCB 11 1 1 x x 10 1 0 x x Ph˱˯ng trình logic cͯa ngõ ra g: g DC '̩ng chính t̷c 2: BA 00 01 11 10 g = D(A + B)(C + B)(B + C) 00 1 0 x 0 = BCD + DCBA 01 1 0 x 0 '̩ng chính t̷c 1: 11 0 1 x x g = DCBA + DCB 10 0 0 x x Xét mҥch giҧi mã ÿèn led 7 ÿRҥn loҥi Kathode chung: Chӑn mӭc tích cӵc ӣ ngõ ra là mӭc logic 1. Vì Kathode cӫa các ÿRҥn led ÿѭӧc nӕi chung và ÿѭӧc nӕi xuӕng mӭc logic 0 (0V-mass) nên muӕn ÿRҥn led nào tҳt ta ÿѭa Anode tѭѫng ӭng xuӕng Pӭc logic 0 (0V-mass). Ví dө: ĈӇ hiӇn thӏ sӕ 0 ta nӕi Anode cӫa ÿRҥn led g xuӕng mӭc logic 0 ÿӇÿRҥn g tҳt, ÿӗng thӡi các kathode cӫa ÿRҥn a, b, c, d, e, f ÿѭӧc nӕi lên nguӗn nên các ÿRҥn này sӁ sáng do ÿó ta thҩy sӕ 0. Lúc ÿó bҧng trҥng thái mô tҧ hoҥt ÿӝng cӫa mҥch nhѭ sau: D B C A a b c d e f g 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 0 1 1 0 1 0 0 1 1 1 1 1 1 0 0 1 0 1 0 0 0 1 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 0 1 0 X X X X X X X 1 0 1 1 X X X X X X X 1 1 0 0 X X X X X X X 1 1 0 1 X X X X X X X 1 1 1 0 X X X X X X X 1 1 1 1 X X X X X X X 7ѭѫng tӵ nhѭ trѭӡng hӧp trên, ta cǊng dùng bҧng Karnaugh ÿӇ tӕi thiӇu hóa hàm mҥch và ÿi tìm phѭѫng trình logic tӕi giҧn các ngõ ra cӫa các ÿRҥn led: (Lѭu ý trong nhӳng bҧng ÿӗ Karnaugh sau ta th͹c hi͏n t͙i thi͋u hóa theo d̩ng chính t̷c 1)
Chѭѫng 3. HӋ tә hӧp Trang 63 Ph˱˯ng trình logic cͯa ngõ ra a: a DC '̩ng chính t̷c 1: BA 00 01 11 10 a = D + B + AC + AC 00 1 0 x 1 '̩ng chính t̷c 2: 01 0 1 x 1 a =(A + B + C + D)(A + B + C) 11 1 1 x x = AD + B + AC + AC 10 1 1 x x Ph˱˯ng trình logic cͯa ngõ ra b: b '̩ng chính t̷c 1: DC BA 00 01 11 10 b = C + BA + B A = C + A Å B 00 1 1 x 1 '̩ng chính t̷c 2: 01 1 0 x 1 b = (C +B + A )( C + B +A) 11 1 1 x x =C + AB+ AB = C + A Å B 10 1 0 x x Ph˱˯ng trình logic cͯa ngõ ra c: c '̩ng chính t̷c 1: DC BA 00 01 11 10 c = B + A + C 00 1 1 x 1 '̩ng chính t̷c 2: 01 1 1 x 1 c = C + B + A 11 1 1 x x 10 0 1 x x Ph˱˯ng trình logic cͯa ngõ ra d: d '̩ng chính t̷c 1: DC BA 00 01 11 10 d = D+BA + C A +B C + ABC 00 1 0 x 1 '̩ng chính t̷c 2: 01 0 1 x 1 d = (A + B + C)(A + B + C)(A + B + C + D) 11 1 0 x x =(C + AB + AB)(A + B + C + D) 10 1 1 x x =(C + A Å B)(A + B + C + D) Ph˱˯ng trình logic cͯa ngõ ra e: e DC '̩ng chính t̷c 1: BA 00 01 11 10 e = A .B + C A 00 1 0 x 1 '̩ng chính t̷c 2: 01 0 0 x 0 e = A ( C + B) = A C + A .B 11 0 0 x x 10 1 1 x x
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 64 Ph˱˯ng trình logic cͯa ngõ ra f: '̩ng chính t̷c 1: f DC BA 00 01 11 10 f = D+ C B + B A + CA 00 1 1 x 1 '̩ng chính t̷c 2: 01 0 1 x 1 f = ( B + A )( D+C+ A )(C+ B ) 11 0 0 x x = D + B C + A C + A B 10 0 1 x x Ph˱˯ng trình logic cͯa ngõ ra g: g DC BA '̩ng chính t̷c 1: 00 01 11 10 g =D+CB +B A +BC 00 0 1 x 1 '̩ng chính t̷c 2: 01 0 1 x 1 g =(C + B + A )(B+C+D) 11 1 0 x x 10 1 1 x x 3.3. MҤCH CHӐN KÊNH - PHÂN ĈѬӠNG 3.3.1. Ĉҥi cѭѫng 0ҥch chӑn kênh còn gӑi là mҥch hӧp kênh (ghép kênh) là mҥch có chӭc năng chӑn lҫn lѭӧt 1 trong N kênh vào ÿӇÿѭa ÿӃn ngõ ra duy nhҩt (ngõ ra duy nhҩt ÿó gӑi là ÿѭӡng truyӅn chung). Do ÿó, mҥch chӑn kênh còn gӑi là mҥch chuyӇn dӳ liӋu song song ӣ ngõ vào thành dӳ liӋu nӕi tiӃp ӣ ngõ ra, ÿѭӧc gӑi là Multiplex (viӃt tҳt là MUX). 0ҥch chӑn kênh thӵc hiӋn chӭc năng ӣÿҫu phát còn mҥch phân ÿѭӡng thӵc hiӋn chӭc năng ӣ ÿҫu thu. Mҥch phân ÿѭӡng còn gӑi là mҥch tách kênh (phân kênh, giҧi ÿa hӧp), mҥch này có nhiӋm Yө tách N nguӗn dӳ liӋu khác nhau ӣ cùng mӝt ÿҫu vào ÿӇ rӁ ra N ngõ ra khác nhau. Do ÿó, mҥch phân ÿѭӡng còn gӑi là mҥch chuyӉn dӳ liӋu nӕi tiӃp ӣ ngõ vào thành dӳ liӋu song song ӣ ngõ ra, ÿѭӧc gӑi là Demultiplex (viӃt tҳt là DEMUX). 3.3.2. Mҥch chӑn kênh Xét mҥch chӑn kênh ÿѫn giҧn có 4 ngõ vào và 1 ngõ ra nhѭ x1 hình 3.23a. x2 y Trong ÿó: x3 4 ® 1 x4 + x1, x2, x3, x4 : Các kênh dӳ liӋu vào. + Ngõ ra y : Ĉѭӡng truyӅn chung. + c1, c2 : Các ngõ vào ÿLӅu khiӇn c1 c 2 9ұy mҥch này giӕng nhѭ 1 chuyӇn mҥch (hình 3.23b): Hình 3.23a. M̩ch ch͕n kênh x1 x2 y x3 x4 Hình 3.23b
Chѭѫng 3. HӋ tә hӧp Trang 65 ĈӇ thay ÿәi lҫn lѭӧt tӯ x1 ® x4 cҫn phҧi ÿLӅu khiӇn, do ÿó ÿӕi vӟi mҥch chӑn kênh ÿӇ chӑn lҫn Oѭӧt tӯ 1 trong 4 kênh vào cҫn có các ngõ vào ÿLӅu khiӇn c1, c2. NӃu có N kênh vào thì cҫn có n ngõ vào ÿLӅu khiӇn thӓa mãn quan hӋ: N=2n. Nói cách khác: Sӕ tә hӧp ngõ vào ÿLӅu khi͋n b̹ng s͙ O˱ͫng các kênh vào. ViӋc chӑn dӳ liӋu tӯ 1 trong 4 ngõ vào ÿӇÿѭa ÿӃn ÿѭӡng truyӅn chung là tùy thuӝc vào tә hӧp tín hiӋu ÿLӅu khiӇn tác ÿӝng ÿӃn hai ngõ vào ÿLӅu khiӇn c1, c2. + c1 = 0, c2 = 0 ® y = x1 (x1ÿѭӧc nӕi tӟi ngõ ra y). + c1 = 0, c2 = 1 ® y = x2 (x2ÿѭӧc nӕi tӟi ngõ ra y). + c1 = 1, c2 = 0 ® y = x3 (x3ÿѭӧc nӕi tӟi ngõ ra y). + c1 = 1, c2 = 1 ® y = x4 (x4ÿѭӧc nӕi tӟi ngõ ra y). 9ұy tín hiӋu ÿLӅu khiӇn phҧi liên tөc ÿӇ dӳ liӋu tӯ các kênh ÿѭӧc c1 c2 y liên tөc ÿѭa ÿӃn ngõ ra. Tӯÿó ta lұp ÿѭӧc bҧng trҥng thái mô tҧ hoҥt 0 0 x ÿӝng cӫa mҥch chӑn kênh. 1 0 1 c2 Phѭѫng trình logic mô tҧ hoҥt ÿӝng cӫa mҥch : 1 0 c3 y = c1 c2 .x1 + c1 c2.x2 + c1 c2 .x3 + c1.c2.x4 1 1 c4 6ѫÿӗ logic cӫa mҥch: c1 c2 x1 x1 1 x2 x2 2 y x3 x3 3 x4 x4 4 Hình 3.24. S˯ÿ͛ logic m̩ch ch͕n kênh tͳ 4® 1 Bây giӡ, xét mҥch chӑn kênh có 4 ngõ vào và 1 ngõ ra, nhѭng lҥi có 4 ngõ ÿLӅu khiӇn. Lúc này, ta không dӵa vào tә hӧp tín hiӋu tác ÿӝng lên ngõ vào ÿLӅu khiӇn, mà chӍ xét ÿӃn mӭc tích cӵc ӣ ngõ vào ÿLӅu khiӇn. Ta sӁ chӑn mӝt trong hai mӭc logic 1 hoһc mӭc logic 0 làm mӭc tích cӵc, nӃu 1 ngõ vào trong sӕ 4 ngõ vào ÿLӅu khiӇn tӗn tҥi mӭc logic tích cӵc (mӭc 1 hoһc mӭc 0) thì kênh dӳ liӋu vào có cùng chӍ sӕ vӟi ngõ vào ÿLӅu khiӇn ÿó sӁÿѭӧc kӃt nӕi vӟi ngõ ra. Trên hình 3.25 biӇu diӉn mҥch chӑn kênh vӟi sӕ lѭӧng ngõ vào ÿLӅu khiӇn bҵng sӕ lѭӧng kênh vào.
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 66 NӃu chӑn mӭc tích cӵc cӫa các ngõ vào ÿLӅu khiӇn là mӭc logic 1, ta có bҧng trҥng thái mô tҧ hoҥt ÿӝng cӫa mҥch nhѭ sau: x1 x2 y x3 4 ® 1 x4 c1 c2 c3 c4 Hình 3.25. M̩ch ch͕n kênh vͣi s͙ l˱ͫng ngõ vào ÿL͉u khi͋n b̹ng s͙ kênh vào c1 c2 c3 c4 y 1 0 0 0 x1 0 1 0 0x2 0 0 1 0 x3 0 0 0 1 x4 Phѭѫng trình logic: y = c1. x1 + c2. x2 + c3. x3 + c4. x4 Ý nghƭa trong th͹c t͇ cͯa m̩ch: + c1, c2, c3, c4 : Có th͋ hi͋u là các ÿ͓a ch͑ (ngu͛n và ÿích). + x1, x2, x3, x4 : Thông tin c̯n truy͉n ÿi. 3.3.3. Mҥch phân ÿѭӡng Xét mҥch phân ÿѭӡng ÿѫn giҧn có 1 ngõ vào và 4 ngõ ra ký hiӋu nhѭ sau : y1 y1 x y2 1 4 y2 ® y3 x y3 y4 y4 c2 c1 Hình 3.26. M̩ch phân ÿ˱ͥng ÿ˯n gi̫n tͳ 1 ® 4 Trong ÿó: + x là kênh dӳ liӋu vào. + y1, y2, y3, y4 các ngõ ra dӳ liӋu; c1, c2 các ngõ vào ÿLӅu khiӇn. Ta có thӇ thҩy mҥch này thӵc hiӋn chӭc năng nhѭ 1 chuyӇn mҥch (hình vӁ 3.26). Tùy thuӝc vào tә hӧp tín hiӋu ÿLӅu khiӇn tác dөng vào mҥch mà lҫn lѭӧt tín hiӋu tӯ ngõ vào x sӁ chuyӉn ÿӃn ngõ ra y1, y2, y3, y4 mӝt cách tѭѫng ӭng. Lúc ÿó bҧng trҥng thái mô tҧ hoҥt ÿӝng cӫa mҥch : c1 c2 y1 y2 y3 y4 0 0 x 0 0 0 0 1 0 x 0 0 1 0 0 0 x 0 1 1 0 0 0 x
Chѭѫng 3. HӋ tә hӧp Trang 67 Phѭѫng trình logic các ngõ ra: y1 = c1 c2 .x y2 = c1 c2.x y 3 = c 1 c2 .x y4 = c1 c2.x 6ѫÿӗ logic ÿѭӧc cho trên hình 3.27: c1 c2 y1 1 y2 x 2 y3 3 y4 4 Hình 3.27. S˯ÿ͛ logic th͹c hi͏n m̩ch phân ÿ˱ͥng Trong trѭӡng hӧp tәng quát, mҥch phân ÿѭӡng có 1 ngõ vào và 2n ngõ ra: ÿӇ tách N = 2n nguӗn dӳ liӋu khác nhau cҫn có n ngõ vào ÿLӅu khiӇn, lúc ÿó sӕ tә hӧp ngõ vào ÿLӅu khiӇn bҵng sӕ Oѭӧng ngõ ra. Tuy nhiên trong thӵc tӃ, ta còn gһp mҥch phân ÿѭӡng có sӕ y1 Oѭӧng ngõ vào ÿLӅu khiӇn bҵng sӕ ngõ ra (hình 3.28). Lúc ÿó chӍ x y2 xét ÿӃn mӭc tích cӵc ӣ ngõ vào ÿLӅu khiӇn, ngѭӡi ta chӑn mӝt 1 ® 4 y3 trong hai mӭc logic 1 hoһc mӭc logic 0 làm mӭc tích cӵc. y4 Giҧ sӱ chӑn mӭc logic 1 là mӭc tích cӵc: nӃu 1 ngõ vào trong sӕ 4 ngõ vào ÿLӅu khiӇn tӗn tҥi mӭc logic 1 (mӭc tích cӵc), thì ngõ ra c c c c1 Gӳ liӋu tѭѫng ӭng có cùng chӍ sӕ vӟi ngõ vào ÿLӅu khiӇn ÿó sӁ 4 3 2 ÿѭӧc nӕi vӟi ngõ vào dӳ liӋu chung x. Hình 3.28 Ví dө: c1 = 1 ® x = y1 c2 = 1 ® x = y2 c3 = 1 ® x = y3 c4 = 1 ® x = y4
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 68 Lúc ÿó bҧng trҥng thái hoҥt ÿӝng cӫa mҥch: c1 c2 c3 c4 y1 y2 y3 y4 1 0 0 0 X 0 0 0 0 1 0 0 0 X 0 0 0 0 1 0 0 0 X 0 0 0 0 1 0 0 0 X Phѭѫng trình logic và sѫÿӗ logic ÿѭӧc cho trên hình 3.29: y1 = c1 x y 2 = c2 x y3 = c3 x y 4 = c4 x Giҧi thích hoҥt ÿӝng cӫa mҥch: + Khi c1=1, c2= c3 = c4 = 0 chӍ có cәng AND(1) thông cho dӳ liӋu tӯ x nӕi ÿӃn ÿҫu ra y1. + Khi c2=1, c1= c3 = c4 = 0 chӍ có cәng AND(2) thông cho dӳ liӋu tӯ x nӕi ÿӃn ÿҫu ra y2. + Khi c3=1, c2 = c1= c4 = 0 chӍ có cәng AND(3) thông cho dӳ liӋu tӯ x nӕi ÿӃn ÿҫu ra y3. + Khi c4=1, c2= c3 = c1= 0 chӍ có cәng AND(4) thông cho dӳ liӋu tӯ x nӕi ÿӃn ÿҫu ra y4. Vì mҥch chӑn kênh ÿѭӧc thӵc hiӋn ӣÿҫu phát và mҥch phân ÿѭӡng ÿѭӧc thӵc hiӋn ӣÿҫu thu nên ÿӇÿҧm bҧo dӳ liӋu ÿѭӧc chuyӇn ÿúng kênh thì mҥch chӑn kênh và mҥch phân ÿѭӡng phҧi ÿӗng Eӝ vӟi nhau. c3 c1 c2 c4 y 1 1 y2 x 2 y3 3 y4 4 Hình 3.29. M̩ch phân ÿ˱ͥng s͙ l˱ͫng ngõ vào ÿL͉u khi͋n b̹ng s͙ ngõ ra 3.4. MҤCH SӔ HӐC 3.4.1. Ĉҥi cѭѫng 0ҥch sӕ hӑc là mҥch có chӭc năng thӵc hiӋn các phép toán sӕ hӑc +, -, x, / các sӕ nhӏ phân. Ĉây là cѫ sӣÿӇ xây dӵng ÿѫn vӏ luұn lý và sӕ hӑc (ALU) trong mp (micro Processor) hoһc CPU (Centre Processing Unit). 3.4.2. Bӝ cӝng (Adder)
Chѭѫng 3. HӋ tә hӧp Trang 69 1. Bӝ bán tәng (HA-Half Adder) a s Bӝ bán tәng thӵc hiӋn cӝng 2 sӕ nhӏ phân mӝt bít. HA Quy tҳc cӝng nhѭ sau: b c 0 + 0 = 0 nhӟ 0 0 + 1 = 1 nhӟ 0 Hình 3.36. M̩ch c͡ng 1 bít 1 + 0 = 1 nhӟ 0 1 + 1 = 0 nhӟ 1 (a) (b) (s) (c) Trong ÿó a, b là sӕ cӝng, s là tәng, c là sӕ nhӟ. %ҧng trҥng thái mô tҧ hoҥt ÿӝng cӫa mҥch và phѭѫng trình logic: s = a. b + a .b = aÅ b a b s c c = a.b 0 0 0 0 0ҥch cӝng này chӍ cho phép cӝng hai sӕ nhӏ phân 1 bit mà 0 1 1 0 không thӵc hiӋn cӝng hai sӕ nhӏ phân nhiӅu bit. 1 0 1 0 1 1 0 1 a 1 3 S 2 b 1 3 C 2 Hình 3.37. S˯ÿ͛ m̩ch c͡ng bán ph̯n 2.Bӝ tәng (Bӝ cӝng toàn phҫn - FA: Full Adder) 9Ӆ phѭѫng diӋn mҥch có sѫÿӗ khӕi nhѭ sau: Trong ÿó: an Sn an bn Cn-1 Sn Cn FA 0 0 0 0 0 bn 0 1 0 1 0 Cn 1 0 0 1 0 Cn-1 1 1 0 0 1 0 0 1 1 0 Hình 3.38. B͡ c͡ng toàn ph̯n 0 1 1 0 1 1 0 1 0 1 + Cn-1 : Sӕ nhӟ cӫa lҫn cӝng trѭӟc ÿó. 1 1 1 1 1 + Cn : Sӕ nhӟ cӫa lҫn cӝng hiӋn tҥi. + Sn : Tәng hiӋn tҥi. 7ӯ bҧng trҥng thái mô tҧ hoҥt ÿӝng cӫa mҥch ta viӃt ÿѭӧc phѭѫng trình logic: Sn = f (an, bn, Cn-1 ) Cn = f (an, bn, Cn-1 ) /ұp bҧng Karnaugh và tӕi thiӇu hóa, ta có:
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 70 Cn Sn anbn anbn 00 01 11 10 00 01 11 10 Cn-1 Cn-1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 0 1 1 1 Cn = anCn-1 + bnCn-1 + anbn Sn = an bnCn-1 + anbn Cn-1 + a b C a b C n n n-1 + n n n-1 Cn = anbn + Cn-1 (an + bn ) Sn = an Å bn Å Cn-1 Có thӇ thӵc hiӋn trӵc tiӃp (sѫÿӗ 3.39) hoһc sӱ dөng 2 bӝ HA ÿӇ thӵc hiӋn FA (sѫÿӗ 3.40): an bn Cn-1 1 Sn 3 2 1 3 2 1 1 Cn 3 3 2 1 2 3 2 Hình 3.39. M̩ch c͡ng toàn ph̯n tr͹c ti͇p an 1 3 2 1 1 Cn bn 3 3 2 1 2 3 2 Cn-1 1 Sn 3 2 Hình 3.40. Th͹c hi͏n m̩ch c͡ng toàn ph̯n tͳ b͡ bán t͝ng 3.4.3. Bӝ trӯ (Subtractor) 1. Bӝ bán trӯ (Bӝ trӯ bán phҫn - HS: Half subtractor) Bӝ bán trӯ thӵc hiӋn trӯ 2 sӕ nhӏ phân 1 bit. Quy tҳc trӯ nhѭ sau: 0 - 0 = 0 mѭӧn 0 0 - 1 = 1 mѭӧn 1 a D HS 1 - 0 = 1 mѭӧn 0 b B 1 - 1 = 0 mѭӧn 0 (a) (b) (D) (B) Hình 3.41 M̩ch trͳ bán ph̯n Trong ÿó a là sӕ bӏ trӯ, b là sӕ trӯ, D là hiӋu, B là sӕ mѭӧn.
Chѭѫng 3. HӋ tә hӧp Trang 71 %ҧng trҥng thái mô tҧ hoҥt ÿӝng : a a b D B 1 D b 3 0 0 0 0 2 0 1 1 1 1 B 1 0 1 0 3 1 1 0 0 2 Phѭѫng trình logic : Hình 3.42. S˯ÿ͛ logic D = a. b + a .b = a Å b B= a .b 0ҥch trӯ này chӍ cho phép trӯ hai sӕ nhӏ phân 1 bit mà không thӵc hiӋn viӋc trӯ hai sӕ nhӏ phân nhiӅu bit. 2. Bӝ trӯ toàn phҫn (FS - Full Subtractor) Mҥch có sѫÿӗ khӕi và bҧng trҥng thái mô tҧ hoҥt ÿӝng nhѭ sau: Trong ÿó: Bn-1 : Sӕ mѭӧn cӫa lҫn trӯ trѭӟc ÿó. Bn : Sӕ mѭӧn cӫa lҫn trӯ hiӋn tҥi. Dn : HiӋu sӕ hiӋn tҥi. an bn Bn-1 Dn Bn an Dn 0 0 0 0 0 FS 0 1 0 1 1 bn 1 0 0 1 0 Bn 1 1 0 0 0 Bn-1 0 0 1 1 1 0 1 1 0 1 Hình 3.43. M̩ch trͳ toàn ph̯n 1 0 1 0 0 1 1 1 1 1 /ұp bҧng Karnaugh và tӕi thiӇu hóa, ta có: Dn anbn B B 00 01 11 10 n anbn n-1 00 01 11 10 0 0 1 0 1 Bn-1 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 Dn = an bn Bn-1 + anbn Bn-1 + Bn = an Bn-1 + bn Bn-1 + anbn an bn Bn-1 + anbn Bn-1 Bn = anbn + Bn-1 (an + bn ) Dn = an Å bn Å Bn-1
Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 72 Có 2 cách thӵc hiӋn bӝ trӯ toàn phҫn theo biӇu thӭc logic ÿã tìm ÿѭӧc: hoһc thӵc hiӋn trӵc tiӃp (hình 3.44) hoһc sӱ dөng HS ÿӇ thӵc hiӋn FS (hình 3.45). an bn Bn-1 1 Dn 3 2 1 3 2 1 1 Bn 3 3 2 1 2 3 2 Hình 3.44. Th͹c hi͏n m̩ch trͳ toàn ph̯n tr͹c ti͇p 1 3 2 bn 1 1 Dn 3 1 3 2 3 2 an 2 Bn-1 1 Bn 3 2 Hình 3.45. Th͹c hi͏n FS trên c˯ sͧ HS 7ӯ bӝ cӝng toàn phҫn, ta xây dӵng mҥch cӝng hai sӕ nhӏ phân nhiӅu bit bҵng 2 phѭѫng pháp: Ph˱˯ng Pháp N͙i Ti͇p và Ph˱˯ng Pháp Song Song. Phѭѫng pháp nӕi tiӃp: Thanh ghi A Thanh ghi S a3 a2 a1 a0 s3 s2 s1 s0 Ck FA Thanh ghi B b3 b2 b1 b0 C-1 C3 Pr DFF clr Hình 3.46. M̩ch c͡ng 2 s͙ nh͓ phân nhi͉u bit theo theo ki͋u n͙i ti͇p
Chѭѫng 3. HӋ tә hӧp Trang 73 Thanh ghi A chӭa sӕ A : a3, a2, a1, a0 Thanh ghi B chӭa sӕ B : b3, b2, b1, b0 Thanh ghi S chӭa tәng S : s3, s2, s1, s0 Nhѭӧc ÿLӇm cӫa phѭѫng pháp này là thӡi gian thӵc hiӋn lâu. Phѭѫng pháp song song: ĈӇ tăng thӡi gian thӵc hiӋn phép cӝng, ngѭӡi ta dùng phѭѫng pháp cӝng song song (hình 3.47). Do tín hiӋu ÿLӅu khiӇn Ck (ÿLӅu khiӇn cӝng) ÿӗng thӡi nên thӡi gian thӵc hiӋn phép cӝng nhanh Kѫn phѭѫng pháp nӕi tiӃp, song do sӕ nhӟ vүn phҧi chuyӇn nӕi tiӃp nên ҧnh hѭӣng tӕc ÿӝ xӱ lý. b3 a3 b2 a2 b1 a1 b0 a0 FA3 FA2 FA1 FA0 c3 s3 c2 s2 c1 s1 c0 s0 Hình 3.47. M̩ch c͡ng song song, s͙ nhͣ chuy͋n n͙i ti͇p 0ҥch cӝng nhӟ nhanh - Mҥch cӝng vӟi sӕ nhӟ nhìn thҩy trѭӟc: Ngѭӡi ta cҧi tiӃn mҥch trên thành mҥch cӝng song song vӟi sӕ nhӟ nhìn thҩy trѭӟc còn gӑi là Pҥch cӝng nhӟ nhanh (Fast Carry, Carry Look Ahead). Bҵng cách dӵa vào sӵ phân tích mҥch cӝng toàn phҫn nhѭ sau: Ta có: Sn = ( an Å bn ) Å Cn-1 Cn = an. bn + ( an Å bn )Cn-1 Ta âàût: Pn = an Å bn Gn = an. bn Suy ra: Sn = Pn Å Cn-1 Cn = Gn + Pn .Cn-1 Khi n= 0 (LSB): S0 = P0 Å C-1 C0 = G0 + P0 .C-1 Khi n=1: S1 = P1 Å C0 = P1 Å ( G0 + P0 .C-1 ) C1 = G1 + P1 .C0 = G1 + P1 .(G0 + P0 .C-1 ) Khi n=2: S2 = P2 Å C1 = P2 Å [G1 + P1 .(G0 + P0 .C-1 )] C2 = G2 + P2 .C1 = G2 + P2 .[G1 + P1.(G0 + P0 .C-1 )] Khi n=3: S3 = P3 Å C2 = P3 Å {G2 + P2 .[G1 + P1.(G0 + P0 .C-1 )]} C3 = G3 + P3 .C2 =G3 + P3 .{G2 + P2.[G1 + P1.(G0 + P0 .C-1) ] }