ÿþW O J S K O W A A K A D E M I A T E C H N I C Z N A
i m . J a r o s B a w a D b r o w s k i e g o
Z A K AA D A W I O N I K I I U Z B R O J E N I A L O T N I C Z E G O
P r z e d m i o t :
P O D S T A W Y A U T O M A T Y K I I A U T O M A T Y Z A C J I
( s t u d i a I s t o p n i a )
W I C Z E N I E R A C H U N K O W E
P R O J E K T P R O S T E G O U K AA D U K O M B I N A C Y J N E G O
W a r s z a w a 2 0 1 3
W I C Z E N I E R A C H U N K O W E
T e m a t :
P r o j e k t p r o s t e g o u k Ba d u k o m b i n a c y j n e g o
1 . W I A D O M O ZC I O G Ó L N E
1 . 1 . P o j c i a p o d s t a w o w e
S y s t e m d w ó j k o w y ( b i n a r n y ) j e s t s p o s o b e m z a p i s u l i c z b z a p o m o c
s y m b o l i 0 i 1 . O g ó l n y z a p i s l i c z b w s y s t e m i e b i n a r n y m o p i s u j e
z a l e |n o [:
0
L 2 =ð ×ð 2 i
åðb i
i =ðn -ð1
R e p r e z e n t a c j a d z i e s i t n a s t a n o w i w y g o d n i e j s z f o r m z a p i s u l i c z b y
b i n a r n e j . J e [l i z m i e n n e j x i p r z y p i s z e m y 1 , a z m i e n n e j x i p r z y p i s z e m y
0 , t o w p r o s t y s p o s ó b u z y s k u j e s i r e p r e z e n t a c j e b i n a r n .
U k Ba d e m p r z e Bc z a j c y m n a z y w a m y u r z d z e n i e s t e r u j c e ,
z b u d o w a n e z e l e m e n t ó w , k t ó r e m o g z n a j d o w a s i w d w ó c h r ó |n y c h
s t a n a c h , o k r e [l o n y c h j a k o s t a n s p o c z y n k o w y i s t a n w z b u d z o n y .
E l e m e n t y p r z e Bc z a j c e , z k t ó r y c h z b u d o w a n y j e s t u k Ba d p r z e Bc z a j c y ,
Bc z l u b p r z e r y w a j p r z e p By w e n e r g i i w o b w o d z i e , n p . : p r z e k a zn i k i
i p r z e Bc z n i k i e l e k t r y c z n e z a Bc z a j p r z e p By w e n e r g i i e l e k t r y c z n e j ,
r o z d z i e l a c z e p n e u m a t y c z n e z m i e n i a j k i e r u n e k p r z e p By w u s p r |o n e g o
p o w i e t r z a , n a t o m i a s t r o z d z i e l a c z e h y d r a u l i c z n e s t e r u j k i e r u n k i e m
p r z e p By w u p By n u h y d r a u l i c z n e g o .
F u n k c j p r z e Bc z a j c f ( x 1 , x 2 , & , x n ) n a z y w a m y t a k i e
o d w z o r o w a n i e , k t ó r e d l a k o m b i n a c j i a r g u m e n t ó w x 1 , x 2 , & , x n
p r z y j m u j c y c h w a r t o [c i 0 l u b 1 p r z y p o r z d k o w u j e r o z w i z a n i e z e
z b i o r u { 0 , 1 } . C z y n n i k j e d y n k i ( k o n s t y t u a n t a z e r a ) M i j e s t t a k f u n k c j
p r z e Bc z a j c , k t ó r a p r z y j m u j e w a r t o [ 0 t y l k o d l a k o m b i n a c j i
w a r t o [c i z m i e n n y c h , w y r a |o n e j w p o s t a c i s u m y .
Z u p e Bn i e n o r m a l n p o s t a c i s u m y ( p o s t a c i k a n o n i c z n
d y s j u n k c y j n ) f u n k c j i p r z e Bc z a j c e j n a z y w a m y s u m t y c h c z y n n i k ó w
j e d y n k i ( k o n s t y t u a n t j e d y n k i ) , k t ó r e s r ó w n e 1 d l a t y c h s a m y c h
k o m b i n a c j i w a r t o [c i a r g u m e n t ó w c o z a d a n a f u n k c j a . P o s t a o g ó l n
w y r a |a p o n i |s z a z a l e |n o [:
2
2 n
F =ð ×ð f i
åðm i
i =ð1
g d z i e : f i i l o c z y n a r g u m e n t ó w ;
n l i c z b a a r g u m e n t ó w .
Z u p e Bn i e n o r m a l n p o s t a c i i l o c z y n u ( p o s t a c i k a n o n i c z n
k o n i u n k c y j n ) f u n k c j i p r z e Bc z a j c e j n a z y w a m y s u m t y c h c z y n n i k ó w
z e r a ( k o n s t y t u a n t z e r a ) , k t ó r e s r ó w n e 0 d l a t y c h s a m y c h k o m b i n a c j i
w a r t o [c i a r g u m e n t ó w c o z a d a n a f u n k c j a . P o s t a o g ó l n w y r a |a
z a l e |n o [:
2 n
F ' =ð +ð f i )ð
Õð(ðM i
i =ð1
F a k t o r y z a c j a ( m i n i m a l i z a c j a ) m a n a c e l u u z y s k a n i e n a j m n i e j s z e j
z Bo |o n o [c i u k Ba d u . R e a l i z u j e s i t o p o p r z e z r e z y g n a c j z p o s t a c i
n o r m a l n e j f u n k c j i . W y k o r z y s t u j e s i t u t a j p r a w a r o z d z i e l n o [c i l u b
p r a w a d e M o r g a n a .
1 . 2 . A l g e b r a B o o l e a
A l g e b r a B o o l e a j e s t s y s t e m e m u m o |l i w i a j c y m o p i s u k Ba d ó w
p r z e Bc z a j c y c h . W n o t a c j i f o r m a l n e j a l g e b r B o o l e a z a p i s u j e m y j a k o
u p o r z d k o w a n p i t k A = ( X , 0 , 1 , + , ×ð) , g d z i e :
X = { x 1 , x 2 , & , x n } z b i ó r a r g u m e n t ó w p r z y j m u j c y c h w a r t o [c i 0
l u b 1 ;
0 e l e m e n t n e u t r a l n y o p e r a c j i d y s j u n k c j i ( s u m y ) ;
1 e l e m e n t n e u t r a l n y o p e r a c j i k o n i u n k c j i ( i l o c z y n u ) ;
+ s y m b o l o p e r a c j i d y s j u n k c j i ;
×ð s y m b o l o p e r a c j i k o n i u n k c j i .
P o d o k o n a n i u z a Bo |e D:
"ðx i Îð X d l a i =ð 1 , . . . , n
"ðx i Îð X $ð x i Îð X d l a i =ð 1 , . . . , n
s p e Bn i o n e s n a s t p u j c e a k s j o m a t y a l g e b r y B o o l e a :
3
g d z i e : x i - z a n e g o w a n y a r g u m e n t x i ;
x i - p o d w ó j n i e z a n e g o w a n y a r g u m e n t x i .
1 . 3 . W a |n i e j s z e f u n k c j e p r z e Bc z a j c e
F u n k c j p r z e Bc z a j c f ( x 1 , x 2 , & , x n ) n z m i e n n y c h n a z y w a s i
o d w z o r o w a n i e :
n
f : D ®ð{ð0 , 1 }ð
n
g d z i e : D Ìð {ð0 , 1 }ð u p o r z d k o w a n a p i t k a ( { 0 , 1 } , 0 , 1 , ×ð, + ) j e s t
a l g e b r B o o l e a
J e [l i D n = { 0 , 1 } n t o f u n k c j p r z e Bc z a j c n a z y w a m y z u p e Bn l u b w
p e Bn i o k r e [l o n . W p r z y p a d k u , g d y i s t n i e j k o m b i n a c j e a r g u m e n t ó w ,
d l a k t ó r y c h f u n k c j a n i e j e s t o k r e [l o n a , t z n . m o |e p r z y j w a r t o [ 0
l u b 1 ( o z n a c z a s i s y m b o l e m Æð) , t o n a z y w a m y j n i e z u p e Bn .
P o n i |e j p r z y t o c z o n o k i l k a n a j w a |n i e j s z y c h f u n k c j i p r z e Bc z a j c y c h
n a z y w a n y c h r ó w n i e | f u n k c j a m i B o o l e a :
f (ðx 1 )ð =ð x 1 -ð z m i e n n a x 1
f (ðx 1 )ð =ð x 1 -ð n e g a c j a z m i e n n e j x 1
f (ðx 1 , x 2 )ð =ð x 1 ×ð x 2 -ð k o n i u n k c j a , i l o c z y n z m i e n n y c h x 1 i x 2 (ð" i " )ð
f (ðx 1 , x 2 )ð =ð x 1 +ð x 2 -ð d y s j u n k c j a , s u m a z m i e n n y c h x 1 i x 2 (ð" l u b " )ð
f (ðx 1 , x 2 )ð =ð x 1 x 2 ×ð x 1 x 2 -ð s u m a m o d u l o 2 , r ó |ó |n i s y m e t r y c z n a (ð" a l b o " )ð
f (ðx 1 , x 2 )ð =ð x 1 x 2 -ð o p e r a c j a P i e r c e ' a (ð" N O R " )ð
f (ðx 1 , x 2 )ð =ð x 1 +ð x 2 -ð o p e r a c j a S h e f f e r a (ð" N A N D " )ð
4
o r a z w a r t o [c i t y c h f u n k c j i d l a k o m b i n a c j i a r g u m e n t ó w x 1 i x 2 :
1 . 4 . R e a l i z a c j a f u n k c j i p r z e Bc z a j c y c h
Z e w z g l d u n a z a s a d d z i a Ba n i a e l e m e n t y d o s y n t e z y u k Ba d ó w
p r z e Bc z a j c y c h m o |n a p o d z i e l i n a e l e k t r y c z n e e l e m e n t y s t y k o w e ,
e l e k t r y c z n e e l e m e n t y b e z s t y k o w e i e l e m e n t y p By n o w e .
U k Ba d y p r z e Bc z a j c e z e l e k t r y c z n y m i e l e m e n t a m i s t y k o w y m i
W s y n t e z i e u k Ba d ó w p r z e Bc z a j c y c h z e l e m e n t a m i s t y k o w y m i
w y k o r z y s t u j e s i p r z e k a zn i k i , s t y c z n i k i i Bc z n i k i .
a ) b ) c ) d )
R y s . 1 . R e a l i z a c j a f u n k c j i p r z e Bc z a j c y c h z w y k o r z y s t a n i e m e l e m e n t ó w
s t y k o w y c h
5
S p o s ó b r e a l i z a c j i p o d s t a w o w y c h f u n k c j i l o g i c z n y c h p r z e d s t a w i o n o
n a r y s . 1 . S t y k n o r m a l n i e o t w a r t y ( N O ) p r z e d s t a w i o n y n a r y s . 1 a
o d p o w i a d a f u n k c j i p o w t ó r z e n i a , n a t o m i a s t s t y k n o r m a l n i e z a m k n i t y
( N Z ) z r y s . 1 b r e a l i z u j e f u n k c j n e g a c j i . P r z e z p o Bc z e n i e s z e r e g o w e
s t y k ó w n o r m a l n i e o t w a r t y c h r e a l i z u j e s i f u n k c j e i l o c z y n u ( k o n i u n k c j i ) ,
a p r z e z i c h p o Bc z e n i e r ó w n o l e g Be f u n k c j e s u m y ( d y s j u n k c j i ) , c o
p r z e d s t a w i o n o n a r y s . 1 c i r y s . 1 d .
U k Ba d y p r z e Bc z a j c e z e l e k t r y c z n y m i e l e m e n t a m i b e z s t y k o w y m i
D o e l e k t r y c z n y c h e l e m e n t ó w b e z s t y k o w y c h z a l i c z a m y e l e m e n t y
m a g n e t y c z n e , d i o d y , l a m p y e l e k t r o n o w e , t r a n z y s t o r y , e l e m e n t y s c a l o n e .
O b e c n i e w y k o r z y s t y w a n e s w y Bc z n i e b r a m k i l o g i c z n e w p o s t a c i
u k Ba d ó w s c a l o n y c h o r ó |n e j s k a l i i n t e g r a c j i :
U k Ba d y p r z e Bc z a j c e z e l e m e n t a m i p By n o w y m i
W u k Ba d a c h p r z e Bc z a j c y c h z e l e m e n t a m i p By n o w y m i n o [n i k i e m
i n f o r m a c j i j e s t s y g n a B p n e u m a t y c z n y l u b h y d r a u l i c z n y . Z e w z g l d u n a
z a s a d d z i a Ba n i a , e l e m e n t y p By n o w e d z i e l i s i n a e l e m e n t y s t r u m i e n i o w e
i r o z d z i e l c z e . S p o s ó b r e a l i z a c j i f u n k c j i p r z e Bc z a j c e j z w y k o r z y s t a n i e m
r o z d z i e l a c z a t r ó j d r o g o w e g o , d w u p o Bo |e n i o w e g o , p r z e d s t a w i o n o n a
r y s . 2 . W y k o r z y s t u j c r o z d z i e l a c z t e g o t y p u , p o p r z e z o d p o w i e d n i e
p o Bc z e n i e w e j [, m o |n a z r e a l i z o w a p o d s t a w o w e f u n k c j e l o g i c z n e .
R y s . 2 . S p o s ó b r e a l i z a c j i f u n k c j i l o g i c z n y c h z w y k o r z y s t a n i e m p n e u m a t y c z n e g o
r o z d z i e l a c z a 3 / 2 : a ) p o s t a o g ó l n a , b ) p o t w i e r d z e n i e , c ) n e g a c j a , d ) s u m a l o g i c z n a ,
e ) i l o c z y n l o g i c z n y , f ) o b j a [n i e n i e s y m b o l i .
6
2 . U K AA D Y K O M B I N A C Y J N E
2 . 1 . S p o s o b y o p i s u u k Ba d ó w k o m b i n a c y j n y c h
O p i s s Bo w n y j e s t n a j c z s t s z f o r m z a d a w a n i a u k Ba d ó w
p r z e Bc z a j c y c h , k t ó r y p o l e g a n a p r z y p o r z d k o w a n i u s y g n a Bo m
w e j [c i o w y m X s y g n a Bó w w y j [c i o w y c h Y . T a b l i c a z a l e |n o [c i w p o s t a c i
c i g ó w z e r o - j e d y n k o w y c h j e s t p r o s t s z f o r m o p i s u u k Ba d u . O k r e [l a
o n a w a r t o [c i s y g n a Bó w X i o d p o w i a d a j c e i m s y g n a By Y ( r y s . 3 ) .
P r z e b i e g c z a s o w y p o k a z u j e z a l e |n o [c i p o m i d z y s y g n a Ba m i
w e j [c i o w y m i i w y j [c i o w y m i , z a z w y c z a j w s k a l i m i e r z o n e j t a k t a m i .
T a k t j e s t o d s t p e m c z a s u m i d z y k o l e j n y m i z m i a n a m i s y g n a Bó w .
T a b l i c a k o l e j n o [c i Bc z e D j e s t u p r o s z c z o n f o r m a p r z e b i e g u c z a s o w e g o .
a )
b )
c )
d )
e )
R y s . 3 . S p o s o b y o p i s u f u n k c j i p r z e Bc z a j c y c h : a ) t a b l i c a z a l e |n o [c i , b ) p r z e b i e g i
c z a s o w e , c ) t a b l i c a k o l e j n o [c i , d ) t a b l i c a K a r n a u g h a , e ) z a l e |n o [ m a t e m a t y c z n a .
W t a b l i c y K a r n a u g h a ( t a b l i c a V e i t c h a ) w a r t o [c i s y g n a Bó w
w y j [c i o w y c h Y u m i e s z c z a n e s w t a b l i c y o w s p ó Br z d n y c h o k r e [l o n y c h
7
p r z e z s y g n a By w e j [c i o w e X . T a b l i c e t e g o t y p u s z c z e g ó l n i e p r z y d a t n e s
p o d c z a s u p r a s z c z a n i a f u n k c j i p r z e Bc z a j c y c h .
C z s t o w y k o r z y s t y w a n f o r m a o p i s u u k Ba d ó w p r z e Bc z a j c y c h j e s t
z a l e |n o [ m a t e m a t y c z n a . Z a l e |n o [ T a j a m o |e m i e p o s t a z u p e Bn i e
n o r m a l n ( p o s t a k a n o n i c z n ) l u b u p r o s z c z o n .
S p o s o b y o p i s u w y k o r z y s t u j c e p o s t a k a n o n i c z n f u n k c j i
p r z e Bc z a j c e j p r z e d s t a w i o n o p o n i |e j :
·ð z u p e Bn i e n o r m a l n a p o s t a s u m y ( p o s t a k a n o n i c z n a
d y s j u n k c y j n a ) y =ð x 3 x 2 x 1 +ð x 3 x 2 x 1 +ð x 3 x 2 x 1 +ð x 3 x 2 x 1
i j e j z a p i s
y =ð
åð(ð0 , 4 , 5 , 7 )ð ;
s k r ó c o n y
x 3 x 2 x 1
·ð z u p e Bn i e n o r m a l n a p o s t a i l o c z y n u ( p o s t a k a n o n i c z n a
k o n i u n k c y j n a )
y =ð(ðx 3 +ð x 2 +ð x 1 )ð(ðx 3 +ð x 2 +ð x 1 )ð(ðx 3 +ð x 2 +ð x 1 )ð(ðx 3 +ð x 2 +ð x 1 )ð i j e j z a p i s
y =ð
Õð(ð1 , 2 , 3 , 6 )ðx 3 x 2 x 1
s k r ó c o n y
.
2 . 2 . M i n i m a l i z a c j a f u n k c j i p r z e Bc z a j c y c h
C e l e m m i n i m a l i z a c j i f u n k c j i p r z e Bc z a j c y c h j e s t z m n i e j s z e n i e
l i c z b y e l e m e n t ó w , a t y m s a m y m k o s z t ó w u r z d z e n i a . D o d a t k o w o
m n i e j s z a l i c z b a p o Bc z e D i e l e m e n t ó w z w i k s z a t r w a Bo [ i
n i e z a w o d n o [ u r z d z e n i a . I s t n i e j e w i e l e s p o s o b ó w m i n i m a l i z a c j i
f u n k c j i p r z e Bc z a j c y c h , d o k t ó r y c h n a l e |:
·ð m e t o d a p r z e k s z t a Bc e D f o r m a l n y c h ;
·ð m i n i m a l i z a c j a z w y k o r z y s t a n i e m t a b l i c y K a r n a u g h a ;
·ð m e t o d a Q u i n e a M c C l u s k e y a ;
·ð m e t o d a w s p ó Bc z y n n i k ó w n i e o z n a c z o n y c h ;
·ð m e t o d a h a r w a r d z k a
·ð m e t o d a t a b l i c n i e z g o d n o [c i
·ð m e t o d a r e d u k c j i q u a s i i m p l i k a n t ó w .
M e t o d a p r z e k s z t a Bc e D f o r m a l n y c h
M e t o d a p r z e k s z t a Bc e D f o r m a l n y c h s t o s o w a n a j e s t w p r z y p a d k u , g d y
f u n k c j a d a n a j e s t w p o s t a c i w y r a |e n i a a l g e b r a i c z n e g o . W y k o r z y s t u j e s i
w t e d y a k s j o m a t y i p r a w a a l g e b r y B o o l e a . W p r z y p a d k u , g d y
u p r a s z c z a n y u k Ba d k o m b i n a c y j n y z a d a n y j e s t w p o s t a c i s c h e m a t u
l o g i c z n e g o , r e a l i z o w a n p r z e z u k Ba d f u n k c j w y z n a c z a s i n a d r o d z e
a n a l i z y .
W c e l u z o b r a z o w a n i a t e j m e t o d y d o k o n a m y m i n i m a l i z a c j a f u n k c j i
p o s t a c i :
y =ð x 1 x 2 x 3 x 4 +ð x 1 x 2 x 3 x 4 +ð x 1 x 2 x 3 x 4 +ð x 1 x 2 x 3 x 4 +ð x 1 x 2 x 3 x 4 +ð x 1 x 2 x 3 x 4
8
W y Bc z a j c x 1 u z y s k u j e m y :
y =ð x 1 (ðx 2 x 3 x 4 +ð x 2 x 3 x 4 +ð x 2 x 3 x 4 +ð x 2 x 3 x 4 +ð x 2 x 3 x 4 +ð x 2 x 3 x 4 )ð
W k o l e j n y m k r o k u w y Bc z a j c p r z e d n a w i a s o t r z y m u j e m y :
(ðx 2 +ð x 2 )ð
y =ð x 1 [ð(ðx 2 +ð x 2 )ð(ðx 3 x 4 +ð x 3 x 4 +ð x 3 x 4 )ð]ð
K o r z y s t a j c z p r a w a d o p e Bn i e n i a
(ðx +ð x =ð1 )ð p o m i j a m y c z Bo n (ðx 2 +ð x 2 )ð, a n a s t p n i e
w y Bc z a m y
x 4
y =ð x 1 [ð(ðx 3 +ð x 3 )ðx 4 +ð x 3 x 4 ]ð
( 1 )
P o n o w n i e k o r z y s t a j c z p r a w a d o p e Bn i e n i a , a n a s t p n i e p r a w a
d z i a Ba n i a n a e l e m e n t a c h n e u t r a l n y c h ( x + 1 = 1 ) , o t r z y m u j e m y :
x 3 +ð x 3 =ð x 3 +ð1 ( 2 )
P o p o d s t a w i e n i u z a l e |n o [c i ( 2 ) d o r ó w n a n i a ( 1 ) o t r z y m u j e m y
f u n k c j :
y =ð x 1 [ð(ðx 3 +ð1 )ðx 4 +ð x 3 x 4 ]ð
P r z e g r u p o w u j c w y r a z y , o t r z y m u j e m y :
y =ð x 1 [ð(ðx 4 +ð x 4 )ðx 3 +ð x 4 ]ð
W c e l u w y z n a c z e n i a z m i n i m a l i z o w a n e j f u n k c j i p o n o w n i e
k o r z y s t a m y z p r a w a d o p e Bn i e n i a x 4 +ð x 4 =ð1 , o t r z y m u j c k o Dc o w
f u n k c j w p o s t a c i :
y =ð x 1 (ðx 3 +ð x 4 )ð=ð x 1 x 3 +ð x 1 x 4
M e t o d a t a b l i c y K a r n a u g h a
M e t o d a t a b l i c y K a r n a u g h a n a l e |y d o g r u p y n a j s z y b s z y c h m e t o d
m i n i m a l i z a c j i f u n k c j i p r z e Bc z a j c y c h m a Be j l i c z b y z m i e n n y c h c o
w y n i k a z d u |e j k o m p l i k a c j i s a m e g o z a p i s u n a s t p u j c e j w r a z z e
w z r o s t e m i l o [c i z m i e n n y c h :
9
U p r a s z c z a j c f u n k c j p r z e Bc z a j c p r z y w y k o r z y s t a n i u t a b l i c y
K a r n a u g h a , n a l e |y p a m i t a o n a s t p u j c y c h p r o b l e m a c h :
a . w i e r s z e i k o l u m n y t a b l i c y K a r n a u g h a o p i s a n e s w k o d z i e
G r e y a , t z n . k a |d y k o l e j n y w i e r s z i k o l u m n a r ó |n i s i o d
s i e b i e o n e g a c j j e d n e j z m i e n n e j ;
b . z a k r e [l a j c j e d y n k i ( z e r a ) , t w o r z y s i g r u p y l i c z c e 2 , 4 , 8 ,
1 6 , & e l e m e n t ó w ;
c . z a w s z e z a k r e [l a s i g r u p y z n a j w i k s z m o |l i w i l o [c i
j e d y n e k ( z e r ) , p r z y c z y m n a l e |y p a m i t a o m o |l i w o [c i
s k l e j e n i a z e s o b k r a w d z i r ó w n o l e g By c h t a b l i c y ;
d . g r u p y m o g p o s i a d a c z [c i w s p ó l n e ;
e . l i c z b a g r u p j e d y n e k ( z e r ) o d p o w i a d a l i c z b i e s k Ba d n i k ó w
s u m y ( i l o c z y n u ) p o s z u k i w a n e j f u n k c j i ;
f . w p r z y p a d k u k i e d y i s t n i e j e m o |l i w o [ z a k r e [l e n i a g r u p n a
k i l k a s p o s o b ó w , a r b i t r a l n i e w y b i e r a s i j e d e n z n i c h ;
g . d a n a g r u p a r e p r e z e n t u j e i l o c z y n ( s u m ) t y c h z m i e n n y c h ,
k t ó r e n i e z m i e n i a j s w o j e j w a r t o [c i ;
h . w p r z y p a d k u , g d y f u n k c j a p r z e Bc z a j c a p o s i a d a e l e m e n t y o
w a r t o [c i n i e o k r e [l o n e j e l e m e n t y t e w p i s u j e m y d o t a b e l i ,
w p r o w a d z a j c d l a n i c h s p e c j a l n e o z n a c z e n i e , n p . a
n a s t p n i e w y k o r z y s t u j e m y l u b p o m i j a m y , w z a l e |n o [c i o d
p o t r z e b y p r z y t w o r z e n i u g r u p ( p a t r z p u n k t b ) .
D l a p r z y k Ba d u z m i n i m a l i z u j e m y f u n k c j o p i s a n z a l e |n o [c i :
y =ð x 1 x 2 x 3 x 4 +ð x 1 x 2 x 3 x 4 +ð x 1 x 2 x 3 x 4 +ð x 1 x 2 x 3 x 4 +ð x 1 x 2 x 3 x 4 +ð x 1 x 2 x 3 x 4
S t o s u j c z a s a d a . t w o r z y m y t a b l i c e K a r n a u g h a , w y p e Bn i a j c j
j e d y n k a m i d l a e l e m e n t ó w f u n k c j i , a p o z o s t a Be p o l a u z u p e Bn i a m y z e r a m i :
W k o l e j n y m k r o k u t w o r z y m y d w i e g r u p y z a w i e r a j c e p o c z t e r y
e l e m e n t y ( w e d Bu g z a s a d b . , c . , d . ) :
1 0
P o s t p u j c w e d Bu g w y t y c z n y c h e , f i g . o d c z y t u j e m y
z m i n i m a l i z o w a n p o s t a f u n k c j i p r z e Bc z a j c e j . W c z t e r o e l e m e n t o w e j
g r u p i e G 1 w a r t o [c i z m i e n n y c h i n i e u l e g a j z m i a n i e , p o n i e w a |
x 1 x 4
z a k r e [l o n o g r u p j e d y n e k . F u n k c j a t a p r z y j m u j e p o s t a i l o c z y n u
. D l a g r u p y G 2 n i e z m i e n n e w a r t o [c i p r z y j m u j p a r a m e t r y i ,
G 1 =ð x 1 x 4 x 1 x 3
w i c g r u p a t a p r z y j m u j e p o s t a . P o z s u m o w a n i u z g r u p G 1
G 2 =ð x 1 x 3
o t r z y m a m y o s t a t e c z n i e p o s z u k i w a n p r z e z n a s f u n k c j w p o s t a c i
d y s j u n k c y j n e j :
y =ð x 1 x 3 +ð x 1 x 4
W c e l u w y z n a c z e n i a z m i n i m a l i z o w a n e j f u n k c j i w p o s t a c i
k o n i u n k c y j n e j n a l e |y z a c z o d p o c z t k u w y p i s y w a n i e t a b l i c y l u b t e |
s k o r z y s t a z t a b l i c y w y p i s a n e j d l a p o s t a c i d y s j u n k c y j n e j , z a k r e [l a j c w
t y m p r z y p a d k u g r u p y z e r :
P o s t p u j c w e d Bu g w y t y c z n y c h e . , f . , i g . o t r z y m u j e m y n a s t p u j c e
g r u p y ( p o n i e w a | j e d y n y m n i e z m i e n n y m p a r a m e t r e m w g r u p i e
G 1 =ð x 1
j e s t x 1 i p r z y j m u j e o n w a r t o [ j e d e n ) o r a z . P o p o m n o |e n i u o b u
G 2 =ð x 3 x 4
g r u p o t r z y m a m y z m i n i m a l i z o w a n f u n k c j w p o s t a c i k o n i u n k c y j n e j :
1 1
y =ð x 1 (ðx 3 +ð x 4 )ð
M e t o d a Q u i n e a M c C l u s k e y a
M e t o d a Q u i n e a M c C l u s k e y a j e s t z w y k l e s t o s o w a n a w p r z y p a d k u
m i n i m a l i z a c j i f u n k c j i w i e l u z m i e n n y c h , p o n i e w a | w r a z z e w z r o s t e m i c h
l i c z b y w z r a s t a t e | j e j e f e k t y w n o [ w s t o s u n k u d o p o z o s t a By c h m e t o d . W
c e l u m i n i m a l i z a c j i f u n k c j i p r z e Bc z a j c e j t m e t o d p o s t p u j e m y w
n a s t p u j c y s p o s ó b :
a . m i n i m a l i z a c j r o z p o c z y n a m y o d z a p i s a n i a e l e m e n t ó w f u n k c j i
p r z e Bc z a j c e j , d l a k t ó r y c h f u n k c j a t a p r z y j m u j e w a r t o [ j e d e n
( z e r o ) ;
b . w k o l e j n y m k r o k u u p o r z d k o w u j e m y e l e m e n t y p o p r z e z
z a p i s a n i e i c h w g r u p a c h z a w i e r a j c y c h i d e n t y c z n e i l o [c i
j e d y n e k ( z e r ) , p r z y c z y m k a |d a k o l e j n a g r u p a p o w i n n a
z a w i e r a w i c e j j e d y n e k ( z e r ) o d p o p r z e d n i e j ;
c . w c e l u z n a l e z i e n i a i m p l i k a n t ó w p r o s t y c h p o r ó w n u j e m y k a |d y
e l e m e n t w g r u p i e z k a |d y m e l e m e n t e m w g r u p i e s s i e d n i e j
z a w i e r a j c e j j e d n j e d y n k ( z e r o ) w i c e j ;
d . j e |e l i e l e m e n t y r ó |n i s i m i e d z y s o b t y l k o j e d n y m i n d e k s e m ,
z a z n a c z a m y j e o b a a w m i e j s c u t e g o i n d e k s u w s t a w i a m y k r e s k
i p r z e p i s u j e m y n o w o p o w s t a By e l e m e n t d o n a s t p n e j k o l u m n y ;
e . p r o c e d u r d . p o w t a r z a m y z k a |d n o w k o l u m n a | d o
p o z o s t a n i a e l e m e n t ó w n i e m o |l i w y c h d o u p r o s z c z e n i a , g d z i e
e l e m e n t y n i e o z n a c z o n e s t a n o w i p o s z u k i w a n e i m p l i k a n t y
p r o s t e ;
f . t w o r z y m y t a b e l , w k t ó r e j w p i e r w s z y m w i e r s z u w p i s u j e m y
k o l e j n e e l e m e n t y f u n k c j i p r z e Bc z a j c e j , a w k o l u m n i e
i m p l i k a n t y p r o s t e ;
g . j e |e l i e l e m e n t f u n k c j i s p e Bn i a i m p l i k a n t , t o n a i c h p r z e c i c i u w
t a b e l i w s t a w i a m y x ;
h . z m i n i m a l i z o w a n f u n k c j p r z e Bc z a j c t w o r z y m y z
i m p l i k a n t ó w p r o s t y c h , k t ó r e p o k r y w a j w s z y s t k i e e l e m e n t y
z a d a n e j f u n k c j i p r z e Bc z a j c e j ;
i . w p r z y p a d k u g d y w f u n k c j i w y s t p u j e l e m e n t y z w a r t o [c i
n i e o k r e [l o n w y k o r z y s t u j e m y j e p r z y p o s z u k i w a n i u
i m p l i k a n t ó w p r o s t y c h , a p o m i j a m y p r z y t w o r z e n i u t a b e l i ( p a t r z
f ) .
D l a p r z y k Ba d u z m i n i m a l i z u j e m y w c z e [n i e j s z f u n k c j p o s t a c i :
y =ð
åð(ð0 , 2 , 4 , 6 , 1 2 , 1 4 )ð
x 1 x 2 x 3 x 4
1 2
Z a p i s u j e m y e l e m e n t y f u n k c j i p r z e Bc z a j c e j , d l a k t ó r e j p r z y j m u j e
o n a w a r t o [ j e d e n w p o s t a c i b i n a r n e j ( p o d p u n k t a ) :
W p i s a n e e l e m e n t y s o r t u j e m y i z a p i s u j e m y w g r u p a c h ( p o d p u n k t
b . ) :
P r z e s z u k u j e m y g r u p y w c e l u z n a l e z i e n i a i m p l i k a n t ó w p r o s t y c h
( p o d p u n k t c . i d . ) . N a p r z y k Ba d e l e m e n t y 1 i 2 r ó |n i s i s o b t y l k o
j e d n y m i n d e k s e m o t r z y m a m y w t e d y n o w y w y r a z w p o s t a c i 0 - 0 0 ,
k t ó r y n a s t p n i e z a p i s u j e m y d o n o w e j k o l u m n y , z a z n a c z a j c
j e d n o c z e [n i e e l e m e n t y 1 i 2 :
P r o c e d u r d . p o w t a r z a m y z n o w o o t r z y m a n k o l u m n e l e m e n t ó w ,
o t r z y m u j c :
1 3
P o n i e w a | w o s t a t n i e j k o l u m n i e z n a j d u j s i j u | t y l k o i m p l i k a n t y
p r o s t e , w y p i s u j e m y j e Bc z n i e z p o z o s t a By m i n i e o z n a c z o n y m i
e l e m e n t a m i ( n p . e l e m e n t 1 3 ) , o t r z y m u j c :
P o w y z n a c z e n i u i m p l i k a n t ó w w y p e Bn i a m y t a b e l p o s t p u j c
w e d Bu g k r o k ó w f . , g . i h .
D l a w y b r a n y c h i m p l i k a n t ó w z m i n i m a l i z o w a n a f u n k c j a p r z y j m u j e
p o s t a k o Dc o w :
y =ð x 1 (ðx 3 +ð x 4 )ð=ð x 1 x 3 +ð x 1 x 4
2 . 3 . S y n t e z a u k Ba d ó w k o m b i n a c y j n y c h
W y r ó |n i a m y t r z y p o d s t a w o w e r o d z a j e s y n t e z y u k Ba d ó w
k o m b i n a c y j n y c h :
·ð s y n t e z a b s t r a k c y j n , k t ó r a p o l e g a n a u s t a l e n i u l i c z b y
s t a n ó w w e j [ i w y j [ o r a z z w i z k ó w z a c h o d z c y c h
p o m i d z y n i m i p r z y w y k o r z y s t a n i u o p i s u s Bo w n e g o ,
w y k r e s u c z a s o w e g o , t a b l i c y Bc z e D, i t p . ;
·ð s y n t e z s t r u k t u r a l n , k t ó r e j c e l e m j e s t w y k r e [l e n i e
s c h e m a t u l o g i c z n e g o . R e a l i z u j e s i t o p o u p r z e d n i m
z a k o d o w a n i u s y g n a Bó w w e j [c i o w y c h i w y j [c i o w y c h o r a z
m i n i m a l i z a c j i f u n k c j i w y j [c i o w e j ;
·ð s y n t e z t e c h n i c z n , k t ó r a p o l e g a n a w y k r e [l e n i u s c h e m a t u
m o n t a |o w e g o z w y k o r z y s t a n i e m w y b r a n y c h e l e m e n t ó w
o o d p o w i e d n i c h c h a r a k t e r y s t y k a c h s t a t y c z n y c h i
d y n a m i c z n y c h .
3 . L i t e r a t u r a
1 . J a n u s z K O W A L P o d s t a w y a u t o m a t y k i T 1 , U c z e l n i a n e
W y d a w n i c t w a N a u k o w o - D y d a k t y c z n e A G H , K r a k ó w 2 0 0 4 ,
S y g n a t u r a : 6 0 3 7 8
2 . T a d e u s z K a c z o r e k T e o r i a s t e r o w a n i a . T o m I U k Ba d y l i n i o w e c i g Be
i d y s k r e t n e . P a Ds t w o w e W y d a w n i c t w o N a u k o w e , W a r s z a w a 1 9 7 7
1 4
Wyszukiwarka
Podobne podstrony:
WODOCIĄGI (ćw proj ) Przykładowe schematy obliczeniowe sieci wodociągowejWODOCIĄGI (ćw proj ) Rury KWH WehoPipe (zestawienie produkowanych średnic)Ogolne zasady proj sieci wod kanAd egz Proj&ProgMATLAB cw Skryptycad2 cw 5 6cw formularzCw 2 zespol2 HIPSCw 9 Wzmacniacz mocyCw 1metrologia cw 1 protokolwięcej podobnych podstron