개요 l 모든입력과출력조건이동일한경우에는가능한한논리회로를간단하게구성 à 논리회로간소화혹은최적화 부울식의간소화 : term 을감소하거나 literal 를감소한다. term 은게이트의수, literal 은게이트의입력수를나타낸다. l 논리회로의동작속도향상, 소비전력감소등효율

Similar documents
개요 l 모든입력과출력조건이동일한경우에는가능한한논리회로를간단하게구성 à 논리회로간소화혹은최적화 부울식의간소화 : term 을감소하거나 literal 를감소한다. term 은게이트의수, literal 은게이트의입력수를나타낸다. l 논리회로의동작속도향상, 소비전력감소등효율

6 장부울함수의간소화

6장 부울 함수의 간소화

Microsoft PowerPoint - 제06장.ppt [호환 모드]

PowerPoint Presentation

3. 다음은카르노맵의표이다. 논리식을간략화한것은? < 나 > 4. 다음카르노맵을간략화시킨결과는? < >

PowerPoint Presentation

PowerPoint Presentation

Microsoft PowerPoint - 제05장.ppt [호환 모드]

Microsoft PowerPoint - dc_ch3 [호환 모드]

5.1 부울대수 ã 부울대수 (oolen lger) 를근거로한스위칭이론 (swithing theory) 은논리설계에있어서이론적인근거가되는수학적체계. ã 부울대수 - 부울상수와부울변수로구성, 0과 1의두개값을가짐 - 논리레벨의여러정의 논리 0 Flse Off Low No

5 장부울대수

歯02-BooleanFunction.PDF

<BFACBDC0B9AEC1A6C7AEC0CC5F F E687770>

<BFACBDC0B9AEC1A6C7AEC0CC5F F E687770>

ºÎ·ÏB

7장 조합 논리 회로

동기순차회로 p 조합논리회로 combinational logic circuit) v 출력이현재의입력에의해서만결정되는논리회로 p 순차논리회로 sequential logic circuit) v 현재의입력과이전의출력상태에의해서출력이결정 v 동기순차논리회로와비동기순차논리회로로

Microsoft PowerPoint - dc_ch2 [호환 모드]

기본서(상)해답Ⅰ(001~016)-OK

2 장수의체계 1. 10진수 2. 2진수 3. 8진수와 16진수 4. 진법변환 5. 2진정수연산과보수 6. 2진부동소수점수의표현 한국기술교육대학교전기전자통신공학부전자전공 1

Microsoft PowerPoint - Appendix_SNU_Combinational Digital Logic Circuits.ppt

Microsoft Word - 제6장 Beyond Simple Logic Gate.doc

untitled

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770>

31. 을전개한식에서 의계수는? 를전개한식이 일 때, 의값은? 을전개했을때, 의계수와상수항의합을구하면? 을전개했을때, 의 계수는? 를전개했을때, 상수항을 구하여라. 37

歯15-ROMPLD.PDF

비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2

(001~006)개념RPM3-2(부속)

OCW_C언어 기초

목차 7 장조합논리회로 1. 가 / 감산기 2. 비교기 3. 디코더 4. 인코더 5. 멀티플렉서 6. 디멀티플렉서 7. 코드변환기 8. 패리티발생기 / 검출기 한국기술교육대학교전기전자통신공학부 1

PowerPoint 프레젠테이션

중간고사

1 1 장. 함수와극한 1.1 함수를표현하는네가지방법 1.2 수학적모형 : 필수함수의목록 1.3 기존함수로부터새로운함수구하기 1.4 접선문제와속도문제 1.5 함수의극한 1.6 극한법칙을이용한극한계산 1.7 극한의엄밀한정의 1.8 연속

Microsoft PowerPoint - 1-2장 디지털_데이터 .ppt

( )EBS문제집-수리

논리회로설계 3 장 성공회대학교 IT 융합학부 1

0 cm (++x)=0 x= R QR Q =R =Q = cm =Q =-=(cm) =R =x cm (x+) = +(x+) x= x= (cm) =+=0 (cm) =+=8 (cm) + =0+_8= (cm) cm + = + = _= (cm) 7+x= x= +y= y=8,, Q

10-2 삼각형의닮음조건 p270 AD BE C ABC DE ABC 중 2 비상 10, 11 단원도형의닮음 (& 활용 ) - 2 -

4장 논리 게이트

확률과통계.indd

(001~042)개념RPM3-2(정답)

Microsoft PowerPoint - Java7.pptx

프로그래밍개론및실습 2015 년 2 학기프로그래밍개론및실습과목으로본내용은강의교재인생능출판사, 두근두근 C 언어수업, 천인국지음을발췌수정하였음


Microsoft PowerPoint - additional01.ppt [호환 모드]

8장 조합논리 회로의 응용

완벽한개념정립 _ 행렬의참, 거짓 수학전문가 NAMU 선생 1. 행렬의참, 거짓개념정리 1. 교환법칙과관련한내용, 는항상성립하지만 는항상성립하지는않는다. < 참인명제 > (1),, (2) ( ) 인경우에는 가성립한다.,,, (3) 다음과같은관계식을만족하는두행렬 A,B에

Microsoft PowerPoint - ch07 - 포인터 pm0415

수없기때문에간단한부분으로나눠서구현하고, 이를다시합침으로써전체를구현하게 된다. 실험에서는이미구현된 4-Bit ALU인 74LS181 Chip을사용한다. 이 Chip은 4-bit의 Data input A, B와 Selection input 4 bit, Carry In 1

STATICS Page: 7-1 Tel: (02) Fax: (02) Instructor: Nam-Hoi, Park Date: / / Ch.7 트러스 (Truss) * 트러스의분류 트러스 ( 차원 ): 1. 평면트러스 (planar tru

Microsoft Word - logic2005.doc

Ⅴ.피타코라스2(P )

Microsoft PowerPoint - 26.pptx

A n s w e r % ml g/cm 1.8 kg B E A C LNGLPGLNG LPG 15 << 13 A<

chap6_basic_association_analysis PART2 ver2

5_03.hwp

13일등예감수학1-1정답(077~120)

Check 0-9, 9,, - 6, 6, 6, =0.04, (-0.) = , =64 8 8, -8 (-6) =6 (-6) 6, -6 7, , -0. 8, -8 6, '7 ' '

제 2 교시 2019 학년도 3 월고 1 전국연합학력평가문제지수학영역 1 5 지선다형 1. 의값은? [2점] 일차방정식 의해는? [2 점 ] 두수, 의최대공약수는? [2 점 ] 일차함수 의그래프에서

ÀÎÅͳÝ-°ø°£µµÇüÇØ

예제 1.1 ( 관계연산자 ) >> A=1:9, B=9-A A = B = >> tf = A>4 % 4 보다큰 A 의원소들을찾을경우 tf = >> tf = (A==B) % A

PowerPoint Template

반도체메모리 메모리 (memory) 분류 순차액세스메모리 랜덤액세스메모리 RAM ROM DRAM SRAM Mask ROM Field PROM 반도체메모리의분류 Fuse-link PROM EPROM EEPROM - 2 -

VENUS Express 사용자 매뉴얼

<C3D1C1A4B8AE B0E6BFECC0C720BCF B9AE2E687770>

ÃÖ»óÀ§5³ª-Á¤´ä(01~23)

PowerPoint 프레젠테이션

<B4EBC7D0BCF6C7D02DBBEFB0A2C7D4BCF62E687770>

Microsoft PowerPoint - 부호기와 복호기.PPT

Microsoft PowerPoint - Analyze

파이널생명과학1해설OK

1. 조합 (combinational) 논리회로에대해설명한것은? < 가 > 가출력신호가입력신호에의해서만결정되는논리회로이다. 나플립플롭과같은기억소자를갖고있는논리회로이다. 다출력신호가입력신호와현재의논리회로의상태에의해결정되는논리회로이다. 라기억능력을가진논리회로이다.

Python과 함께 배우는 신호 해석 제 5 강. 복소수 연산 및 Python을 이용한 복소수 연산 (제 2 장. 복소수 기초)

금오공대 컴퓨터공학전공 강의자료

<3235B0AD20BCF6BFADC0C720B1D8C7D120C2FC20B0C5C1FE20322E687770>

슬라이드 1

Microsoft PowerPoint - chap04-연산자.pptx

2005년 6월 고1 전국연합학력평가

, _ = A _ A _ 0.H =. 00=. -> 0=. 0= =: 0 :=;^!;.0H =.0 000=0. -> 00= 0. 00= =: 0 0 :=;()$; P. 0, 0,, 00, 00, 0, 0, 0, 0 P. 0.HH= = 0.H =0. 0=. -> =0.


untitled

2015 개정교육과정에따른정보과평가기준개발연구 연구책임자 공동연구자 연구협력관

<3130C0E5>

<C6EDC1FDBABB2DB5F0C0DAC0CEBAD0BEDF2E687770>

SB-600 ( ) Kr SB-600 1

untitled

<30352D30312D3120BFB5B9AEB0E8BEE0C0C720C0CCC7D82E687770>

歯mp3사용설명서

2 A A Cs A C C A A B A B 15 A C 30 A B A C B. 1m 1m A. 1 C.1m P k A B u k GPS GPS GPS GPS 4 2

Microsoft PowerPoint Relations.pptx

?

Index

6 강남구 청담지구 청담동 46, 삼성동 52 일대 46,592-46,592 7 강남구 대치지구 대치동 922번지 일대 58,440-58,440 8 강남구 개포지구 개포동 157일대 20,070-20,070 9 강남구 개포지구중심 포이동 238 일대 25,070-25,

27집최종10.22

황룡사 복원 기본계획 Ⅵ. 사역 및 주변 정비계획 가. 사역주변 정비구상 문화유적지구 조성 1. 정비방향의 설정 황룡사 복원과 함께 주변 임해전지(안압지) 海殿址(雁鴨池)와 분황사 등의 문화유적과 네트워크로 연계되는 종합적 정비계획안을 수립한다. 주차장과 광장 등 주변

1

02장.배열과 클래스

[ 마이크로프로세서 1] 2 주차 3 차시. 포인터와구조체 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Functi

Microsoft PowerPoint - chap06-2pointer.ppt

Transcription:

6 장부울함수의간소화

개요 l 모든입력과출력조건이동일한경우에는가능한한논리회로를간단하게구성 à 논리회로간소화혹은최적화 부울식의간소화 : term 을감소하거나 literal 를감소한다. term 은게이트의수, literal 은게이트의입력수를나타낸다. l 논리회로의동작속도향상, 소비전력감소등효율적인논리회로구성가능 l 논리회로를간소화하는방법 논리회로자체를간소화하는방법 논리회로를부울함수로표현한후부울함수를간소화 부울대수의기본정리를이용하는방법 연속적인부울정리사용으로 trial and error () 드모르강의정리와합의곱을반복적으로수행 -> SOP 형식을유도 (2) SOP 에서공통인수를찾고이를소거 카르노맵 (karnaugh map) 방법 도식적인방법으로 6 개정도의입력변수까지사용 2

6. 부울대수식의기본정리이용 예 ) 부울함수 F = wx'(y'+xz) + wx'(x+y'z) 를간소화한후논리회로비교 F = wx'(y'+xz) + wx'(x+y'z)= wx'y' + wx'xz + wx'x + wx'y'z = wx'y' + wx'y'z = wx'y'(+z) = wx'y' å Z(a,b,c) = m(2,3,7) = m 2 + m 3 + m 7 = a'bc' + a'bc + abc ß sum of minterms 3 input AND 3개, 3 input OR 개 = a'bc' + a'bc + a'bc + abc = a'b(c'+c) + bc(a'+a) = a'b + bc <- sum of products, 2 input AND 2개, 2 input OR 개 3

6.2 카르노맵 진리표를그림모양으로나타낸것이며벤다이어그램 (venn diagram) 을확장한것 여러형태의사각형으로된그림으로진리표의각항 ( 최소항또는최대항 ) 들은카르노맵의각한칸의사각형에나타냄 카르노맵의각칸에서수평또는수직방향으로인접한칸 (adjacent term) 은한변수의논리상태만서로다르다. 카르노맵에서인접항을 2,4,8,6 의단위로묶음으로써부울변수를,2,3,4, 개씩감소한다. l 카르노맵에서의간소화과정. 논리회로를부울함수로표시 - 기본적으로 SOM(POM) 으로표현 2. 진리표로나타낸다. 3. 카르노맵에진리표의각값을적합한칸에기입 4.SOP 로최소화할때는 '' 로구성되는최대인접항으로묶고 POS 로최소화할때는 '0' 으로구성되는최대인접항으로묶는다. ( 최대인접항의개수는,2,4,8,6,.. 로형성된다.) 5. 각항들은중복되어묶일수있다. 6. 모든최소항은한번이상은묶여야한다. 7. 큰항의묶음에서남아있는변수들로간소화된부울식을구한다. 정규 (x) 및반전 (x') 인변수가묶음내에존재하면그변수는식으로부터소거 모든칸에나타나는같은변수는최종식에남는다 보다큰 (0) 의묶음은더많은수의변수를소거시킨다. '' 로묶은함수는정규형이므로 SOP 로바로구하여진다. '0' 으로묶은함수는보수형이므로그결과를반전하여 POS 형의정규함수를구한다. 4

카르노맵 2 변수의카르노맵 l l 2개의 2진변수에대한 4개의최소항구성각최소항은하나씩 4개의사각형에배치 xy 중복묶임 3 변수의카르노맵 l 3 개의 2 진변수에대한 8 개의최소항구성 xy'+xy =x(y'+y)=x x'y+xy =y(x'+x) =y xy'z+xyz =xz(y'+y) =xz 2 개항의묶음 (looping) - 인접한 (0) 의쌍을묶어정규입력과반전입력형태의 개변수소거 x+x = x'y'z'+xy'z'+x'yz'+xyz' =y'z'(x+x')+yz'(x'+x)=z'(y'+y) = z' 5

(A,B,C) 3 변수카르노맵표현방법 A 가 MSB 각사각형에최소항의인덱스만표현 6

3 변수카르노맵 예 ) F = x'y'z + x'yz' + x'yz + xy'z 을카르노맵을이용하여간소화하여라. SOP - '' 묶음 F = x'y + y'z POS 형 - '0' 묶음 F' = y'z' + xy F = (y'z' + xy) ' = (y+z)(x'+y') 예 ) 다음진리표에대한논리식의최소화된논리도를그려라. x y z 0 0 0 0 0 0 0 0 0 0 0 0 0 F 0 0 0 카르노맵 간소화된부울식 y'z' y'z yz yz' F = z' + xy' x' 0 0 논리도 x 0 7

3 변수카르노맵예 F(A,B,C)= å (,2,3,5,7) = C+A'B a b c f 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 a bc 00 0 0 0 f(a,b,c)= å (3,5,6,7) = ab+bc+ac abc 항 - 세번중복하여묶임 8

4 변수의카르노맵 l 4 변수카르노맵 4 개의변수에대한 2 4 =6 개의최소항구성 yz' xz wx'y' 9

4 변수카르노맵예 F = C F = B F = A + C F = AB + AB + CD + CD F = B + D F = AB + AD + AC + BC 0

4 변수카르노맵요약 CD AB 00 0 0 00 0 0 CD AB 00 0 0 00 0 0 F = ABC + ABC + BCD + BCD F = ABC + ABC + BD + CD CD AB 00 0 0 00 0 0 F = AC + AC + D 4변수맵에서 term의변수감소는 single = 4변수 (minterm) two s = 3변수 four s = 2변수 eight s = 변수 sixteen s = 0 변수 ( 상수 )

선택적카르노맵 부울식의해가 2 개이상인경우 같은간소화의결과 f = xy + x y + xz f = xy + x y + yz F = AB + ABD + ACD F = AB + ABD + BCD 2

논리식의카르노맵작성 v 논리식에서생략된부분을찾아서 Minterm 으로변경 f ( x, y, z) = xyz + xy + x y = xyz + xy( z + z) + x y( z + z) = xyz + xyz + xyz + = å m(0,, 2, 3, 7) x yz + x yz f ( x, y, z) = x + yz f ( w, x, y, z) = wx + wxy + wyz + wyz + wxyz = wx( y + y)( z + z) + wxy( z + z) + w( x + = å m(, 3, 5, 6, 7,2,3,4,5) x) yz + w( x + x) yz + wxyz yz wx 00 0 0 00 0 0 f ( w, x, y, z) = wx + wz + xy 3

예제 6-4 다음논리식을카르노맵으로작성하고간소화. F ( A, B, C, D) = A + B + ABCD A B ABCD 최소항으로바꾸지않고간략화의반대방법으로카르노맵작성 CD AB 00 0 00 0 0 F = A + B + CD 0 4

5 변수카르노맵 5 변수카르노맵 l2 5 = 32 개의최소항 : m 0 ~m 3 5

- 다음 5 변수논리함수를카르노맵을이용하여간소화 å F( A, B, C, D, E) = m(4, 5, 6, 7, 9,,3,5,6,8, 27, 28,3) A=0 A= DE BC 00 0 0 00 0 0 00 0 0 F ( A, B, C, D, E) = ABC + ABE + ABCE + ABCDE + BDE F(v,w,x,y,z) = y å m(5,7,8,9,2,3,5,8,23,24,25,26,28,29,3) v y F = wy' + xyz w x w x + v'xz + vx'yz' z z 6

6 변수카르노맵 6 변수카르노맵 l2 6 = 64 개의최소항 : m 0 ~m 63 7

예제 6-7 F( A, B, C, D, E, F) = å m(, 3, 6, 8, 9,3,4,7,9, 24, 25, 29,32, 33 34, 35, 38, 40, 46, 49, 5, 53, 55, 56, 6, 63) F = ABDF + CDEF + CDF F = ABDF + CDEF + CDF + ACEF + BDEF + ABCD F = ACEF + BDEF + ABCD 8

6.3 Don't Care l 출력이완전히정의되지않는경우의함수에대하여사용한다. l 입력변수의조합들에대한출력값은어떠한입력값이라도무관 (don't care) 하게된다. ( 예 ) BCD 코드에서 00 ~ 은정의되지않는값 l 부울함수를더간단하게하는데사용한다. l don't care 항은 d 로표시하고 K-map 에서도이를사용한다. don't care 가있는논리함수의표현 ( 예 ) 함수 F 를 SOM 과 don't care 혹은 POM 과 don't care 로표현하고최소화 F(w, x, y, z) = (0,7,8,0,5) + d(,2,9,,3) = (3,4,5,6,2,4) d(,2,9,,3) < 곱의합형 > F = x'z' + xyz 중첩항 (redundant term) < 합의곱형 > F'=xy' +xz' +x'z F=(x'+y)(x'+z)(x+z') d(2) 는 로포함, 나머지는 0 로포함 모든 은한번씩은포함 (cover) 되어져야함 d(,9,,3) 은 0 로포함, d(2) 는 로포함 모든 0 은한번씩은포함 (cover) 되어져야함 9

예제 : 다음식과같이무관항이있을경우카르노맵을이용하여간소화 F( A, B, C, D) = å m(0,2,3,4,5,) + å d(,7,9,5) å F( A, B, C, D) = m(,2,3,4,6,8,0) + d(0,2,4) å å m(0,2,3,4,8,9,) +å F( A, B, C, D) = d(,5,6,7,0,2) CD AB 00 0 0 00 x 0 0 x x x F = AB + CD + AC F = D + AB F = A + B 20

6.4 Quine-McClusky 논리간소화 l 테이블방법 (tabulation method, Q-M 방법 ) 입력변수가많을경우표를이용하여논리간소화 Tabulation 방법의단계 () Find PI(Prime Implicant)s - candidate (2) Select PI - include minimum number of terms Prime Implicant : 2 의맥급수로묶을수있는최대인접항으로결합된 product term Essential Prime Implicant (EPI) : 한개혹은그이상의 minterms 을포함 (cover) 하는유일한 PI 가있다면그 PI 를 EPI 라한다. K-map 논리화 : EPI 는반드시포함하고나머지 minterm 를 cover 하는최소수의 PI 를포함한다. 2

Find PI Quine-McClusky 과정. Step : Grouping - 최소항을 의개수로분류 2. Step 2 : matching - 모든상하그룹에서모든최소항들을각각비교하여 개의변수만이다르다면그 2 개의최소항을결합하고이때 개의변수가삭제된다. 결합된항은로표시. 3. Step 3 : step 2 의결과에서모든상하그룹에서같은자리에소거된변수가있는항끼리비교하여 개의변수만이다르다면그 2 개항을결합하고 개의변수가소거된다. 결합된항은로표시. 4. step 3 의과정을변수항의결합이발생하지않을때까지한다. 5. 위과정에서남은항과매칭되지않은모든항들은 PI 가된다. 22

Tabulation 방법예 PI 찾기 F= m(0,,2,8,0,,4,5) 를 QM 으로최소화 y 0 w x z grouping matching * PI's w'x'y', x'z', wy * All PI's are EPI. 23

Q-M 방법예 F(w,x,y,z)= m(,4,6,7,8,9,0,,5) 를 QM 으로최소화 Find PI's 매칭시 0진수값으로실행두값을비교하여,2,4,8,6 의차이가있을때결합단, 아래그룹의값이더커야한다. 24

Select PI's PI 선택 () 행에찾아진모든 PI를기입 ( 포함하는최소항을같이기입 ) (2) 열에모든최소항기입 (3) 각 PI가 cover하는최소항을각해당란에 X로표시 (4) 단한개의 X로표시된최소항을가지는 PI를한다. ß EPI (5) (4) 의 EPI가 cover하는모든최소항을마지막행에표시 (6) (5) 의되지않는최소항을포함하는 PI를최소개가되도록선택 (7) (4) 와 (6) 을포함하여논리식을작성 F = x'y'z + w'xz' + wx' + xyz 25

Don't care 를포함한 Q-M 방법 F(w, x, y, z) = (2,3,7,9,,3) + d(,0,5) l PI 찾기 d 를포함하여 PI 를찾는다 l PI selection 포함되어져야할최소항에는 d 를불포함 F = x'y +yz +wz 26

예제 6-8 다음식을 QM 방법을이용하여간소화하여라. F(A,B,C,D) = m(0,,2,3,5,7,8,0,2,3,5) Column Column 2 Column 3 index decimal A B C D index decimal A B C D decimal A B C D 0 (0) 0 0 0 0 2 3 () (2) (8) (3) (5) (0) (2) (7) (3) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 (5) 0 2 3 (0,) (0,2) (0,8) (,3) (,5) (2,3) (2,0) (8,0) (8,2) (3,7) (5,7) (5,3) (2,3) (7,5) (3,5) 0 0 0-0 0-0 - 0 0 0 0 0-0 - 0 0 0 - - 0 0 0-0 - 0 0 0-0 - - 0 0 - - - (0,,2,3) (0,2,,3) (0,2,8,0) (0,8,2,0) (,3,5,7) (,5,3,7) (5,7,3,5) (5,3,7,5) 0 0 - - 0 0 - - - 0-0 - 0-0 0 - - 0 - - - - - - A B B D A D BD AC D ABC 27

() 모든 PI A B + BD + AD + BD + ACD + ABC IMPLICANTS 0 2 3 5 7 8 0 2 3 5 AB BD AD BD ACD ABC F(A,B,C,D) = F(A,B,C,D) = F(A,B,C,D) = F(A,B,C,D) = 0 0 - - X X X X - 0-0 X X X (X) 0 - - X X X X - - X X X (X) 0 0 X X (6) 카버된최소항 0 - X X Essential X X X X X (X) X (X) 4 가지해가능 BD + BD + BD + BD + BD + BD + BD + BD + AB + AD + AB + AD + ACD ACD ABC ABC (7) 나머지 PI선택 (4) EPI:BD,B D CD AB 00 0 0 00 0 0 (2) 모든최소항 (5) EPI cover 항 (3) 각 PI cover 항 28

f 예제 6- 무관항을가진다음식을 QM 방법을이용하여간소화 å m( 0,, 4, 6, 8,4,5) +å ( a, b, c, d) = d( 2, 3, 9) Column Column 2 Column 3 index decimal a b c d index decimal a b c d index decimal a b c d 0 (0) 0 0 0 0 2 () (2*) (4) (8) (3*) (6) (9*) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (0,) (0,2*) (0,4) (0,8) (,3*) (,9*) (2*,3*) (2*,6) (4,6) (8,9*) 0 0 0-0 0-0 0-0 0-0 0 0 0 0 - - 0 0 0 0-0 - 0 0-0 0 0-2 (6,4) - 0 0 (0,,2*,3*) (0,2*,4,6) (0,8,,9*) 없음 0 0 - - 0 - - 0-0 0-3 (4) 0 4 (5) 3 (4,5) - 2 없음 PI 를찾는과정에서는무관항포함 29

IMPLICANTS 0 4 6 8 4 5 ab ad bc bcd abc PI 를선택하는과정에서는무관항불포함 0 0 - - X X X 0 - - 0 X (X) X - 0 0 - X X (X) - 0 X X - X (X) Essential X X (X) X (X) X (X) f = ad + bc + abc cd ab 00 00 0 0 X X 0 0 X 30

예제 6-2 QM 방법을이용하여 POS 형태로간소화하여라. å m( 0,, 4, 6, 8,4,5) + å å m( 5, 7,0,,2,3) + å f ( a, b, c, d) = d( 2, 3, 9) f ( a, b, c, d) = d( 2, 3, 9) Column Column 2 Column 3 index decimal a b c d index decimal a b c d index decimal a b c d (2*) 0 0 0 (2*,3*) (2*,0) 0 0 - - 0 0 (2*,0,3*,) - 0-2 3 (3*) (5) (9*) (0) (2) (7) () (3) 0 0 0 0 0 0 0 0 0 0 0 0 0 2 (3*,7) (3*,) (5,7) (5,3) (9*,) (9*,3) (0,) (2,3) 0 - - 0 0 - - 0 0 - - 0 0-0 - 2 없음 f =a bd + abc + b c è f = (a+b +d )(a +b +c)(b+c ) 3

6.5 여러개의출력함수 v 두개의시스템으로분리되어있는것을하나의시스템으로통합하는것이가능하고, 공유가능한게이트가있을때공유하여시스템을구성하면경제적으로좋은시스템이될수있을것이다. 2 개로분리된시스템하나로통합된시스템 32

예제 6-4 다음과같은 2 개의논리함수를하나의시스템으로통합 å F( X, Y, Z) = m(0, 2, 6, 7) å G( X, Y, Z) = m(, 3, 6, 7) YZ X 00 0 0 0 YZ X 00 0 0 0 X Z F = X Z + XY G = XZ + XY X X Z X 33

v 예제 6-7 다음 3 개함수를동시에간소화하시오. å å å F( W, X, Y, Z) = m(0,2,6,0,,4,5) G( W, X, Y, Z) = m(0,3,6,7,8,9,2,3,4,5) H ( W, X, Y, Z) = m(0,3,4,5,7,0,,2,3,4,5) 세함수끼리서로독립된부분과두개의함수에서같은영역중크게묶을수있는영역을먼저찾는다. YZ WX 00 0 0 00 YZ WX 00 0 0 00 YZ WX 00 0 0 00 0 0 0 0 F 0 G 0 H 34

v 나머지중에서공통된부분과독립된부분을찾는다. YZ WX 00 0 0 00 YZ WX 00 0 0 00 0 0 0 0 F G H F ( W, X, Y, Z) = WY + Y Z + W XY Z G ( W, X, Y, Z) = WY + XY + W XY + W XY Z H ( W, X, Y, Z) = XY + WY + W XY + W XY Z 35

무관항을갖는경우 å m(2,3,4,6,9,,2) + å å m(2,6,0,,2) + å F( W, X, Y, Z) = d(0,,4,5) G( W, X, Y, Z) = d(0,,4,5) v 서로독립된영역을찾은후, 선택되지않는부분을찾아서나머지를묶는다. YZ YZ WX 00 0 0 WX 00 0 0 00 x x 00 x x F 0 x x G 0 x x 0 0 YZ WX 00 0 0 00 x x 0 x x 0 YZ WX 00 0 0 00 0 x x x x 0 F = XY + XZ + WY Z G = WY + WX Z + WY Z 36

6.6 논리회로의간소화 간소화 : 부울식의간소화와논리게이트의간소화 NOR 게이트와 NAND 게이트 만능 (universal ) 게이트 l NAND 게이트 부울함수 AND-NOT(AND 게이트의출력을반전 ), NOT-OR(OR 게이트의모든입력을반전 ) 의두가지로표현 x y F x y F x y F l NOR 게이트 부울함수 OR-NOT(OR 게이트의출력을반전 ), NOT-AND(AND 게이트의모든입력을반전 ) 의두가지로표현 x y F x y F x y F 37

l Universal 게이트 NOT : NAND 혹은 NOR 만으로 NOT 구현 x F x F x F l AND : NAND 혹은 NOR 만으로 AND 구현 l x x F y y OR : NAND 혹은 NOR 만으로 OR 구현 F x y F x y F 38

NAND 게이트의논리회로구성 Two stage logic SOP(SOM) 혹은 POS(POM) 으로표현 l à 모든디지털회로는이단논리로표현가능 부울함수를 SOP 로표시하는방법 첫번째방법은함수값이 인최소항을 SOP 로표시 두번째방법은함수값이 0 인최소항을 SOP 로표시한후보수화 l 함수를 2 단계 NAND 게이트로표시하는방법. 함수값이 인최소항을구해 SOP 형식을직접적으로 NAND 게이트로변환 ( 동일한 2 단논리 ) 함수값이 0 인최소항을구해보수를한후 SOP 의 NAND 게이트로표시, 마지막단에 NOT 로사용되는 NAND 사용 (3 단논리 ) l 함수를 2 단계 NOR 게이트로표시하는방법. 함수값이 0 인최대항을구해 POS 형식을직접적으로 NOR 게이트로변환.( 동일한 2 단논리 ) 함수값이 인최대항을구해보수를한후 POS 의 NOR 게이트로표시, 마지막단에 NOT 로사용되는 NOR 사용 (3 단논리 ) 39

SOP : NAND-NAND 논리 2 단 AND-OR 회로는 2 단 NAND-NAND 논리로변환 예 ) 부울함수 F=wx+x'y+yz 를곱의합형인논리회로로표시하고, NAND 게이트로구현하라. w x w x y F y F z z w x w x y F y F z z 40

예제 6-8 다음카르노맵을 NAND 게이트만으로표현하여라. cd ab 00 0 0 00 0 0 f = abc + acd + bd 이논리식을이중부정을하여드모르강의정리를적용하여변형 f = abc + acd + bd = abc + acd + bd = abc acd bd 4

Another Method a + b + c = abc 42

Another Method 2 2 입력 NAND 게이트만으로나타내기위해이논리식을변형. f = abc + acd + bd = c( ab + ad) + bd = c( ab + ad) + bd = c( ab + ad) bd = c( ab ad) bd a b + ad = ab + ad = ab ad 43

다단 2 입력 NAND 게이트논리회로 f = abc + acd + bd = c( ab + ad) + bd 모든 AND 게이트의뒤에 NOT 을두개붙인다. 44

예제 6-9 다음식을 2 입력 NAND 게이트만으로표현 F = CD + ABC + AC + BC F = C( D + AB) + C( A + B) AND 게이트뒤에 NOT 을두개씩붙인다. 45

POS : NOR-NOR 논리 2단 OR - AND 회로는 2단 NOR-NOR 논리로변환예 ) 부울함수를 POS 논리회로를구성하고 NOR 게이트로만구현하라. F = (w+x)(x'+y)(y+z) w x y F z w x w x y F y F z z 46

예제 6-20 SOP 로나타낸논리식을 NOR 게이트만으로표현 l f = bd + a c d + ab c POS 를구하기위하여 0 으로묶어서 f 를 SOP 식으로먼저표현 cd ab 00 0 0 00 0 0 0 0 0 f = cd + bc + abd + abd 이것을부정하게되면 f 가되며, 드모르강의정리를적용하여다음과같은 POS 식을구한다. 0 0 0 0 0 f = cd + bc + abd + abd = cd bc abd abd = ( c + d)( b + c)( a + b + d)( a + b + d) OR 게이트의출력을이중부정 47

예제 6-2 A B C D F 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 NOR 게이트만으로된논리도구하기 CD AB 00 0 0 00 0 0 0 0 0 0 0 0 0 F = ( A + C + D)( B + D)( A + B + C) 48

2 입력 NOR 게이트만으로나타내기위해논리식구하기 F = ( A + C + D)( B + D)( A + B + C) = ((( A + C) + D)(( A + B) + C))( B + D) 각 OR 출력에 NOT 을 2 개붙인다 49

게이트간소화 가능한한 IC 개수를줄여서 x = AB + CD 로표현되는식의회로를구현하려고한다. TTL IC 를가지고회로를구성하여라. 2 개논리게이트사용 개논리게이트사용 50

사용별게이트의표현선택 회로설계에있어대치논리게이트를적절히사용하여회로해석을쉽게한다. - 동작시킬회로의최종출력이 Active High 이냐 Active Low 에따라선택 - 그림 (b) : 출력 Z 는 A=B= 또는 C=D= 인경우에 High - 그림 (c) : 출력 Z 는 A 또는 B 가 Low 이고, C 또는 D 가 Low 일때만 Low 출력 Bubble 위치반전을나타내는버블은출력에버블이있으면그다음입력에버블이있도록연결버블이없는출력에는없는입력을연결 5

6.7 XOR 게이트와 XNOR 게이트 l l 비교연산을수행하는게이트 교환법칙과결합법칙성립 XOR 게이트 l l A B이면 출력, A=B이면 0 출력부울함수 : F = x Å y = x' y + x y' XNOR 게이트 l l A B이면 0 출력, A=B이면 출력부울함수 : F = x y = x' y' + x y XOR 과 XNOR 는서로보수함수 l F' =( x' y + x y')' = (x+y')(x'+y) = xx'+xy+x'y'+yy' = xy+x'y' ç XNOR 52

XOR 사용예 ( 예 ) x x 0 와 y y 0 는각각 2 비트 2 진수이다. 이두수가서로같은값을가질때출력이 HIGH 가되는논리회로를설계하라. 진리표작성하면각입력의같은자리수가같을때출력이 ( 예 ) 간소화시 XOR 나 XNOR 를이용한예 z = ABCD + AB'C'D + A'D' = AD(BC + B'C') + A'D' = AD(B C) + A'D' 3 변수 XOR 부울식 F(x,y,z)= x Å y Å z = m(,2,4,7) = x'y'z +x'yz' +xy'z' + xyz ß 의개수가홀수개 ß 홀함수 ( odd function) 3 변수 XNOR 부울식? ß 짝함수 ( even function) K-map 53

4 입력 XOR/XNOR 맵 4 입력 XOR 홀함수 ( odd function) 짝함수 ( even function) 4 입력 XNOR 4 입력 XOR 논리식 F = W XYZ + W XY Z + W XY Z + W XYZ + W XY Z + W XYZ + WXYZ + WXY Z = W X ( YZ + Y Z) + W X ( Y Z + YZ) + W X ( Y Z + YZ) + WX ( YZ + Y Z) = W X ( Y Å Z) + W X ( Y Å Z) + W X ( Y Å Z) + WX ( Y Å Z) = ( Y Å Z)( W X + WX ) + ( Y Å Z)( W X + W X ) = ( Y Å Z)( W Å X ) + ( Y Å Z)( W Å X ) = W Å X ÅY Å Z 54