필요성 여러개의 함수를 동일한 variable을 이용해서 나타내고자 하는 경우, circuit은 제각각 구현하더라도, gate를 중복해서 사용하면 좀 더 효율적일 것이다. 4개의 input과 3개의 output이 있는 다음 함수를 circuit으로 구현해 보자. 먼저 각 함수를 구현하기 위해서 Karnaugh map을 그린다. 각 함수는 위와 같이 looping할 수 있다. 이를 이용해서 circuit을 구현하면, 위와 같이 그릴 수 있다. 위와 같이 하면 9개의 gate와 21개의 input이 필요하다. 이제 이 circuit을 좀 더 간단히 하고자 한다. 먼저, circuit을 바로 바라봤을 때, 'AB'를 만드는 AND gate가 중복되어 있는 것을 볼 수 있다. 따라서 둘 중 하나를 없애고 없앤 ..

적용 방법 이 포스트에서는 'don't care'에 해당되는 minterm이 있을 때, Quine-McCluskey Method를 어떻게 적용할 것인가 하는 문제를 다룰 것이다. 방법은 기존과 거의 비슷하므로, 대략적인 차이에 대해서 먼저 설명해 보면, 일단 prime implicant를 찾는 과정에서는, don't care들을 모두 1인 것으로 간주하여 prime implicant를 찾는다. 그래야만, 각 term에서 최대한 많은 variable을 제거할 수 있다. (product 내의 각 variable을 literal이라고 한다.) 제거하는 과정에서 필요한 don't care들이 자동적으로 포함되는 셈이다. 한편, prime implicant chart를 그릴 때에는 don't care의 minte..

개요 Petrick's method는 prime implicant chart로부터 모든 minimum sum-of-products solution을 구하는 방법이다. Variable의 숫자가 많아질 수록 prime implicant의 숫자도 늘어날 뿐 아니라, prime implicant chart 역시 점점 더 복잡해진다. 그러면 minimum solution을 구하기 위해서 많은 시행착오를 겪게 되는데, 좀 더 체계적인 방법으로 minimum solution을 구할 수 있는 것이 Petrick's method라고 할 수 있다. 적용방법 1. prime implicant chart에서 essential prime implicant와 해당 minterm을 제거한다. 2. 각 prime implicant가..

1단계 Quine-McCluskey method의 두번째 단계는 prime implicant chart를 통해서 minimum solution을 구하는 것이다. 먼저 prime implicant chart는 다음과 같이 그릴 수 있다. 앞에서 우리가 구했던 prime implicant들이다. 각각의 term들은 minterm들의 조합으로 이루어져 있었다. Minterm의 번호는 왼쪽과 같이 적어주었다. 오른쪽 위에는 f에 속해있는 모든 minterm을 적는다. 그런 다음 각 term에 속해있는 해당 minterm들을 X로 표시한다. 그러고 나서 X표시를 살펴보았을 때, 각 열당 X가 단 하나뿐인 minterm이 보일 것이다. 여기서는 9번과 14번이 X가 하나뿐이다. 이러한 minterm들을 포함하는 p..

개요 Karnaugh map은 비교적 적은 숫자의 variable에 관해서 정리할 때 유용하다. 하지만, variable의 갯수가 많아지는 경우에는 컴퓨터를 사용해야 한다. Quine-McCluskey method는 Karnaugh map에 비해서 비교적 컴퓨터 프로그래밍에 적합하다. Quine-McCluskey method는 minterm expansion (각 term이 모든 variable을 포함하는 sum-of-products expression 형태)으로부터 minimum solution을 구하는 과정에 사용되고, 다음의 2개의 step을 거친다. 1. XY + XY' = X의 식을 기본으로 하여, 가능한한 많은 variable을 줄이도록 한다. 결과에 나온 term들을 prime implica..

정의 Karnaugh map 상의 홀로 떨어진 1이나 1의 묶음들은 function F의 implicant 라고 한다. 한편 prime implicant란 다른 implicant와 더 이상 결합될 수 없는 것들을 말한다. 다음 Karnaugh map을 보면서 예를 살펴보자. abc' 와 ab'c'는 implicant지만, prime implicant는 아니다. ac'와 같이 더 큰 implicant로 합쳐질 수 있기 때문이다. 즉 ac'는 prime implicant라고 할 수 있다. 반면 아래쪽의 a'b'c나 a'cd'는 더 이상 큰 loop로 만들 수 없으므로 prime implicant라고 할 수 있다. 마지막으로 왼쪽 상단의 1은 prime implicant처럼 보일 수 있으나, adjacency..