논리회로 및 실험 4변수 Karnaugh map April 30, 2010 RTDCS Lab. 유휘재 (listil@naver．com) RTDCS Lab. 송호근 (sriky＠naver.com)

Minterm(최소항) (1) 3변수 최소항의 표현방법 f(x, y, z) = x’yz’ + xy’z’ + xyz’ f(x, y, z) = x’yz’ + y’z = ∑m(1, 2, 5) f(x, y, z) = xy’ + z = ∑m(1, 3, 4, 5, 7) x y Z 최소항 번호 x’y’z’ 1 x’y’z x’yz’ 2 x’yz 3 xy’z’ 4 xy’z 5 xyz’ 6 xyz 7

Minterm(최소항) (2) 3변수 최소항 클래스 설계 논리식의 표현 방법(규칙)을 이용한 문자열 처리 3변수 최소항의 표현 방법 어떤 데이터가 필요한지, 어떤 처리를 해 줄 것인지? 논리식의 표현 방법(규칙)을 이용한 문자열 처리 3변수 논리식은 x, y, z 변수를 이용하는 것으로 가정한다. 합과 곱의 형식으로 표현한다. + 문자를 기준으로 각 항을 분리한다. 첫 번째 문자는 x, y, z 셋 중의 하나가 될 수 있다. 두 번째 이후로는 ’(not)이 붙을 수 있다.

f(x, y, z) = x’yz’ + y’z Minterm(최소항) (3) 2 5 1 = ∑m(1, 2, 5) x’ y z’ 0 1 0 1 0 1 0 0 1 2 5 1 = ∑m(1, 2, 5)

Karnaugh map (1) 3변수 Karnaugh map 표현 방법 논리식에 대한 최소항을 구하고 각 위치에 맞게 mapping시킨다. Karnaugh map은 K-map이라고도 한다. y z x 0 0 0 1 1 1 1 0 m0 m1 m3 m2 1 m4 m5 m7 m6

Karnaugh map (2) Karnaugh map 클래스 설계 Karnaugh map의 표현 방법 어떤 데이터가 필요한지, 어떤 처리를 해 줄 것인지? 이미 구현되어 있는 다른 클래스와 중복되는 부분이 있는지? 필요한 기능 중에서 이미 구현된 것이 있으면 그것을 가져다 쓰는 것이 효율적이다.

응용 프로그램 4변수 Karnaugh map 구현하기 앞서 공부한 minterm 를 활용한다. [실습] 입력받은 논리식을 분석하여 Karnaugh map으로 출력하도록 하는 기능을 구현하시오. 필요한 데이터: map 데이터 (array) 필요한 기능: (1) 최소항 데이터를 map의 적당한 위치에 넣는 기능 (2) 완성된 Karnaugh map을 화면에 출력하는 기능 (3) (w,x,y,z, ’,+)이외의 문자가 입력될 경우 다시 입력 (수행 결과 예시) 논리식 입력:w’xz + wx’ + wz’ Minterm : 5 7 8 9 10 11 12 14 0000 0110 1001 1111

Minterm(최소항) (1) 처리 과정 논리 함수의 각 항을 +기호 기준으로 끊는다. string 형의 terms[]에 각 항을 넣는다. terms [0] wx [1] w’z [2] xy f = wx + w’z + xy

Minterm(최소항) (2) 각 항에 대하여 각 변수의 상태에 대한 값을 설정한다. tempTerm[0] ~ [3]은 각각 w~z 변수를 의미한다. tempTerm[0] ~ [3]은 초기 값으로 모두 -1을 가진다. 각 변수의 뒤에 ‘(not) 기호가 붙으면 0, 그렇지 않으면 1을 대입한다. 변수가 없으면 -1이 그대로 남아 있게 된다. [참고] ‘ ’(single quoters)로 둘러싸인 문자는 ASCII 코드를 의미한다. ex) ‘w’== 문자 w의 ASCII 코드 값 (= 167) string형 변수에는 각 문자의 ASCII 코드 값이 들어 있다. string (wxyz) [0] 167 [1] 168 [2] 169 [3] 170

Minterm(최소항) (3) 0이나 1로 나타낸 각 항의 변수 상태를 십진수로 바꾸면 최소항이 된다. ex) wxyz = 1111 → m15 각 항을 조사하여 변수의 등장 여부를 확인한다. if( w가 없으면 ) { if( x가 없으면 ) if( y가 없으면 ) // z else // yz } // 반드시 x가 존재하는 부분 ……

Minterm(최소항) (3) 각 항에 나타나지 않은 변수에 대해서는 0과 1의 경우 모두를 포함한다. ex) xyz = wxyz + w’xyz = 1111 + 0111 → m15 + m7 [참고] xyz는 wxyz + w’xyz = (w + w’)xyz가 간소화된 형태

Karnaugh map (1) 3변수 Kranaugh map (k == 0)?(1):(0)의 의미 y z x 0 0 0 1 1 1 1 0 m0 m1 m3 m2 1 m4 m5 m7 m6

Karnaugh map (2) 4변수 Karnaugh map y z w x 0 0 0 1 1 1 1 0 m0 m1 m3 m2

Karnaugh map (3) 4변수 Karnaugh map의 test case w’xz + wx’ + wz’ xz + x’z’ w’xy + z xy + wxy + w’x’yz + wz w + x + y + z

실습 과제 #1 - 참고사항 제출 기간: 5. 7(금) 반드시 지정일에 제출 5월 7일 수업시간까지: 100%, 이후 메일로 제출가능 5월 9일 자정까지 90% 인정