Giáo trình kỹ thuật số - Phần 1 Đại số Boolean và vi mạch số - Chương 3

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

104
lượt xem 13
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tối thiểu hoá hàm Boolean I. Ph-ơng pháp tối thiểu hoá 1. Khái niệm tối thiểu hoá Tối thiểu hoá là tìm dạng biểu diễn đại số đơn giản nhất của hàm. Khi đó sẽ giảm đ-ợc tối đa số cổng để thực hiện hàm. Đây là yêu cầu rất cần quan tâm vì nó giúp cho việc thực hiện mạch đ-ợc đơn giản và hiệu quả.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình kỹ thuật số - Phần 1 Đại số Boolean và vi mạch số - Chương 3

BomonKTDT-§HGTVT Ch−¬ng 3 Tèi thiÓu ho¸ hµm Boolean I. Ph−¬ng ph¸p tèi thiÓu ho¸ 1. Kh¸i niÖm tèi thiÓu ho¸ Tèi thiÓu ho¸ lµ t×m d¹ng biÓu diÔn ®¹i sè ®¬n gi¶n nhÊt cña hµm. Khi ®ã sÏ gi¶m ®−îc tèi ®a sè cæng ®Ó thùc hiÖn hµm. §©y lµ yªu cÇu rÊt cÇn quan t©m v× nã gióp cho viÖc thùc hiÖn m¹ch ®−îc ®¬n gi¶n vµ hiÖu qu¶. VÝ dô: Cho hµm cã d¹ng CTT vµ CTH ®Çy ®ñ nh− sau: F = X 3 .X 2 .X 1 + X 3 .X 2 .X 1 + X 3 .X 2 .X 1 F = ( X 3 + X 2 + X 1 )( X 3 + X 2 + X 1 )( X 3 + X 2 + X 1 )( X 3 + X 2 + X 1 ) Khi ®ã s¬ ®å cæng thùc hiÖn hµm sÏ cã d¹ng: U2B U1A U2C U 4A U1B U2A U3A U1C U3B Tuy nhiªn nÕu sö dông b¶ng ch©n lý cña hµm ta cã: X3 X2 X1 F 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 X 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1 Tõ b¶ng ch©n lý dÔ dµng thÊy F = X2. Râ rµng biÓu thøc nµy ®¬n gi¶n h¬n rÊt nhiÒu so víi biÓu thøc ë trªn, v× thÕ m¹ch lóc nµy còng chØ lµ mét bé ®Öm cho X2 mµ th«i 21
PTH-DTT F X2 Còng cã mét sè yÕu tè kh¸c ngoµi gi¸ thµnh ¶nh h−ëng ®Õn ®é phøc t¹p cña m¹ch cÇn ®−îc quan t©m. Mét trong c¸c yÕu tè lµ thêi gian trÔ truyÒn ®¹t, lµ kho¶ng thêi gian tÝnh tõ lóc cã sù thay ®æi t¹i ®Çu vµo tíi khi cã sù thay ®æi kÕt qu¶ t¹i ®Çu ra. Cµng nhiÒu cæng ®−îc m¾c nèi tiÕp víi nhau th× thêi gian trÔ nµy cµng lín. VÝ dô víi hµm : f = A*B*C + A*B*C+A*D 1) lµ mét d¹ng tèi thiÓu vµ ®Çu ra cã møc trÔ cña cæng AND thªm víi møc trÔ cña cæng OR. Tuy nhiªn, còng víi hµm nµy theo luËt ph©n phèi, ta ®−îc: f = A*(B*C+ B*C +D). 2). Hµm nµy cã thêi gian trÔ lín h¬n hµm tr−íc v× nã gåm møc trÔ cña 3 cæng. Bëi thÕ, dï rÎ h¬n, nã cã thêi gian trÔ lín h¬n. Mét yÕu tè ®¸ng quan t©m kh¸c lµ t¶i cña ®Çu vµo. XÐt 1). tÝn hiÖu A ph¶i ®iÒu khiÓn 3 t¶i (3 cæng), trong khi víi 2). t¶i chØ cã mét cæng. Tíi nay vÉn ch−a cã ph−¬ng ph¸p tèi −u nµo cã thÓ thùc hiÖn viÖc tèi thiÓu ho¸ mét c¸ch tèi −u. ViÖc tèi thiÓu ho¸ hµm logic cã thÓ thùc hiÖn b»ng mét trong hai c¸ch c¬ b¶n lµ: + BiÕn ®æi ®¹i sè + ThuËt to¸n 2. Ph−¬ng ph¸p tèi thiÓu ho¸ hµm logic b»ng biÕn ®æi ®¹i sè Trong tr−êng hîp sè biÕn Ýt vµ hµm ®−îc biÓu diÔn b»ng ph−¬ng ph¸p gi¶i tÝch ng−êi ta cã thÓ thùc hiÖn biÕn ®æi trùc tiÕp hµm theo c¸c tÝnh chÊt cña ®¹i sè VÝ dô: dïng ph−¬ng ph¸p biÕn ®æi ®¹i sè ta thùc hiÖn rót gän hµm f nh− sau: f = A. X + A. X + A. X f = A. X + A. X + A. X + A. X f = X ( A + A) + A( X + X ) f =X+A râ rµng lµ hµm f ®· ®−îc ®¬n gi¶n ®i rÊt nhiÒu thay v× mét hµm phøc t¹p U7A A U6A U7B U3C U8A f A f X X U6B U7C 22
BomonKTDT-§HGTVT 3. Nhãm c¸c ph−¬ng ph¸p tèi thiÓu ho¸ theo thuËt to¸n Mét sè kh¸i niÖm: §Ønh: §Ønh lµ mét tÝch gåm ®Çy ®ñ c¸c biÕn cña hµm ban ®Çu (nÕu hµm cã n biÕn th× ®Ønh lµ tÝch n biÕn) §Ønh 1 lµ ®Ønh mµ t¹i ®ã hµm sè b»ng 1 §Ønh 0 lµ ®Ønh mµ t¹i ®ã hµm sè b»ng 0 §Ønh kh«ng x¸c ®Þnh lµ ®Ønh t¹i ®ã hµm kh«ng x¸c ®Þnh (ký hiÖu lµ X) Th«ng th−êng khi cho mét hµm sè ë d¹ng CTT ng−êi ta cho tËp c¸c ®Ønh 1 vµ c¸c ®Ønh kh«ng x¸c ®Þnh (N) cña hµm ban ®Çu. TÝch cùc tiÓu lµ mét tÝch mµ t¹i ®ã hµm b»ng 1 hoÆc kh«ng x¸c ®Þnh víi thµnh phÇn c¸c biÕn kh«ng bá bít ®−îc n−·. TÝch cùc tiÓu lµ biÓu diÔn cña 1 nhãm 2k ®Ønh. TÝch cùc tiÓu nµy phñ c¸c ®Ønh hay c¸c ®Ønh chøa trong tÝch cùc tiÓu, nghÜa lµ dïng tÝch cùc tiÓu ®Ó biÓu diÔn tèi ®a sè ®Ønh víi sè biÕn Ýt nhÊt. C¬ së to¸n häc cña viÖc t×m tÝch cùc tiÓu lµ ¸p dông phÐp d¸n: A. X + A. X = A TÝch quan träng lµ mét tÝch cùc tiÓu phñ Ýt nhÊt 1 ®Ønh 1. Nã nhÊt thiÕt ph¶i xuÊt hiÖn trong biÓu thøc cuèi cïng cña bµi to¸n. TËp hîp c¸c tÝch quan träng chÝnh lµ phñ tèi thiÓu, kÕt qu¶ cuèi cïng cña bµi to¸n. Chó ý: Khi tiÕn hµnh víi hµm viÕt d−íi d¹ng CTH ®Çy ®ñ th× thay c¸c ®Ønh 1 b»ng ®Ønh 0. C¸c kh¸i niÖm tæng vµ tÝch còng ®æi chç cho nhau. NghÜa lµ: §Ønh lµ tæng ®Çy ®ñ n biÕn BiÓu diÔn hµm b»ng tÝch c¸c tæng Tæng cùc tiÓu Tæng quan träng Phñ tèi thiÓu lµ sè tæng quan träng Ýt nhÊt mµ phñ hÕt ®−îc sè ®Ønh 0 Gi¸ trÞ cña biÕn sÏ gi÷ nguyªn nÕu cã gi¸ trÞ 0 vµ ®¶o nÕu cã gi¸ trÞ 1 Qu¸ tr×nh tèi thiÓu ho¸ gåm c¸c b−íc nh− sau: + BiÓu diÔn hµm sè d−íi d¹ng CTT ®Çy ®ñ víi tËp c¸c ®Ønh 1 vµ ®Ønh kh«ng x¸c ®Þnh hoÆc CTH ®Çy ®ñ víi tËp c¸c ®Ønh 0 vµ ®Ønh kh«ng x¸c ®Þnh + T×m c¸c tÝch cùc tiÓu + T×m c¸c phñ tèi thiÓu + §−a ra c¸ch biÓu diÔn míi cña hµm a. Ph−¬ng ph¸p dïng b¶ng Karnaugh. B¶ng Karnaugh lµ mét b¶ng cã 2n «, mçi « t−¬ng øng víi mét tæ hîp trong b¶ng tr¹ng th¸i vµ chøa c¸c gi¸ trÞ ®Çu ra t−¬ng øng. Mét ®Æc tr−ng cña biÓu ®å nµy lµ lu«n s¾p xÕp sao cho chØ cã sù thay ®æi cña mét biÕn khi chuyÓn tõ « nµy sang « kÒ cËn. Trong b¶ng ta chó ý ®Õn 2 dÊu hoa thÞ, ta sÏ viÕt ®−îc: 23
PTH-DTT L1 A = L1 . R1 .L2.R2 + L1 .R1.L2.R2 Sö dông c¸c ®Þnh lý cña §¹i sè Boolean, cã thÓ viÕt l¹i: A = L1 .L2.R2.( R1 +R1) = L1 .L2.R2. 1 = L1 .L2.R2. Nh− vËy, hµm ®−îc tèi thiÓu ho¸ gåm mét cæng AND 3 ®Çu vµo. Nguyªn lý thiÕt lËp biÓu ®å Karnaugh chÝnh lµ t¹i c¸c « kÒ nhau, gi¸ trÞ “1” ®−îc nhãm l¹i víi nhau. KÝch th−íc cña nhãm lµ luü thõa cña 2 (vÝ dô: 2 «, 4 «, 8 «, 16 «, 32 « ...). VÝ dô 4 « cña cét thø t− trong b¶ng ë h×nh bªn cã thÓ ®−îc nhãm. Nh− vËy, toµn bé nhãm sÏ ®−îc tèi gi¶n thµnh A. B , chÝnh lµ c¸c phÇn tö chung cña c¶ nhãm. C¸c phÇn tö cã gi¸ trÞ kh¸c nhau (C vµ D) sÏ kh«ng xuÊt hiÖn. KÕt qu¶ nµy còng nhËn ®−îc nÕu ta ¸p dông c¸c ®Þnh lý cña ®¹i sè Boolean cho 4 « nµy nh− sau: f = A. B.C.D + A. B .C.D + A. B .C. D = A. B .C .( D +D) + A. B .C.(D+ D ) = A. B .C +A. B .C = A. B .(C+ C ) = A. B 24
BomonKTDT-§HGTVT Chó ý: B¶ng Karnaugh, gièng nh− b¶n ®å thÕ giíi, phÝa bªn ph¶i sÏ tiÕp liÒn phÝa bªn tr¸i, nªn cã thÓ nhãm c¸c « n»m ®èi diÖn nhau. Nguyªn lý nµy còng ®−îc ¸p dông cho bªn trªn vµ bªn d−íi. (tøc lµ chóng ta nhãm theo kiÓu ®èi xøng hoÆc liÒn kÒ) VÝ dô, cã thÓ nhãm 4 « ë 4 gãc cña biÓu ®å nh− h×nh d−íi ®©y Tõ c¸c nhËn xÐt ë trªn ta rót ra ®−îc c¸c b−íc tiÕn hµnh tèi thiÓu ho¸ b»ng b¶ng Karnaugh cho d¹ng CTT lµ: 1, BiÓu diÔn hµm ®· cho trªn b¶ng Karnaugh 2, X¸c ®Þnh c¸c tÝch cùc tiÓu cña hµm (tÝch cùc tiÓu t×m ®−îc b»ng c¸ch d¸n 2k « cã gi¸ trÞ 1 hoÆc X víi k tèi ®a, c¸c « nµy gÇn kÒ hoÆc ®èi xøng nhau) 3, T×m phñ tèi thiÓu lµ chän mét sè Ýt nhÊt c¸c nhãm tÝch cùc tiÓu sao cho phñ hÕt ®−îc c¸c ®Ønh 1 cña hµm Chó ý: . Qu¸ tr×nh hoµn toµn t−¬ng tù khi hµm biÓu diÓn ë d¹ng CTH . Khi lËp b¶ng Karnaugh víi CTT nh÷ng « b»ng 0 nªn ®Ó trèng cßn ë d¹ng CTH th× bá trèng nh÷ng « cã gi¸ trÞ 1. b. Tèi thiÓu ho¸ b»ng ph−¬ng ph¸p Quine - Mc.Cluskey Ph−¬ng ph¸p nµy ®−îc thùc hiÖn cho hµm biÓu diÔn d−íi d¹ng CTT C¸c b−íc tiÕn hµnh: B−íc 1: T×m tÝch cùc tiÓu . X¸c ®Þnh ®Ønh 1 vµ X . S¾p xÕp c¸c tæ hîp biÕn theo sè l−îng ch÷ sè 1 cã trong chóng . So s¸nh mçi tæ hîp thuéc nhãm i víi tæ hîp thuéc nhãm (i + 1). NÕu 2 tæ hîp ®ã chØ kh¸c nhau 1 cét sè th× kÕt hîp 2 tæ hîp ®ã thµnh mét tæ hîp míi, trong ®ã sö dông dÊu – thay cho cét sè kh¸c nhau. §¸nh dÊu vµo 2 tæ hîp võa kÕt hîp . Lo¹i bá c¸c tæ hîp gièng nhau vµ lÆp l¹i b−íc trªn cho ®Õn khi hÕt c¸c tæ hîp cã kh¶ n¨ng kÕt hîp . TËp hîp c¸c tæ hîp trong b¶ng cuèi vµ c¸c tæ hîp kh«ng bÞ ®¸nh dÊu chÝnh lµ tËp c¸c tÝch cùc tiÓu B−íc 2: T×m phñ tèi thiÓu 25
PTH-DTT . LËp b¶ng cã cét lµ c¸c gi¸ trÞ cã ®Ønh lµ 1 (c¸c gi¸ trÞ nµy th−êng ghi theo hÖ ®Õm 10 cho tiÖn theo dâi), hµng lµ c¸c tÝch cùc tiÓu . §¸nh dÊu X vµo « mµ tÝch cùc tiÓu ë hµng phñ ®Ønh ë cét. Cét cã 1 dÊu X chÝnh lµ tÝch quan träng . Lo¹i bá c¸c cét ®· ®−îc phñ trong tÝch quan träng . Lo¹i c¸c tÝch quan träng khái hµng . LËp b¶ng míi vµ tiÕp tôc qu¸ tr×nh ®Õn khi tÊt c¶ c¸c ®Ønh ®Òu ®−îc phñ VÝ dô: Tèi thiÓu ho¸ hµm sau b»ng ph−¬ng ph¸p Quine – Mc. Cluskey nh− sau: ∑ (0,2,5,8,9,10,11) Hµm f = S¾p xÕp l¹i Thùc hiÖn phÐp d¸n HÖ 10 HÖ 2 HÖ 10 HÖ 2 0 0000 0 0000 (0,2) 00-0 (0,2,8,10) -0-0 2 0010 2 0010 (0,8) -000 (0,8,2,10) -0-0 5 0101 8 1000 (2,10) -010 (8,9,10,11) 10- - 8 1000 5 0101 (8,9) 100- (8,10,9,11) 10- - 9 1001 9 1001 (8,10) 10-0 10 1010 10 1010 (9,11) 10-1 11 1011 11 1011 (10,11) 101- VËy kÕt qu¶ cuèi cïng lµ: -0-0 vµ 10- - Hay f = B.D + A B 26