Giáo trình kỹ thuật số - Phần 1 Đại số Boolean và vi mạch số - 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ả.
Nội dung trích xuất từ tài liệu:
Giáo trình kỹ thuật số - Phần 1 Đại số Boolean và vi mạch số - Chương 3BomonKTDT-§HGTVT Ch−¬ng 3 Tèi thiÓu ho¸ hµm BooleanI. 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 1F = ( 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 U3BTuy 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 1Tõ 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Òuso 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 21PTH-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ñam¹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¶ngthê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 ®Çura. 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Óuho¸ 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 tronghai c¸ch c¬ b¶n lµ: + BiÕn ®æi ®¹i sè + ThuËt to¸n2. 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Ýchng−ê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 U7C22BomonKTDT-§HGTVT3. 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ã nbiÕ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µnhphÇ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 ...