개요 Quine-McCluskey Method가 비교적 Karnaugh map에 비해 variable 수가 많을 때 더 유용하긴 하지만, 여전히 과정이 오래걸리는 것은 사실이다. 특히 term은 별로 없으면서 cover하는 minterm이 많은 경우에는 특히 더 오래걸리는 때가 있다. 이런 경우에는 Karnaugh map을 사용하는 편이 더 좋은데, 그것도 6-variable이 넘어가는 경우에는 사용하기가 어려웠다. 하지만 Karnaugh map을 약간만 발전시키면 이 문제를 해결할 수 있다. 예제 예를들어 6-variable의 function이 있다고 하자. 우리는 이를 4-variable Karnaugh map에 나타낼 생각이다. 어떤 6-variable function이 다음과 같이 정의된다고 하자..

적용 방법 이 포스트에서는 '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..

형태 5-variable Karnaugh map은 3차원 공간을 생각해야 한다. 왼쪽 그림을 보면, 4-variable Karnaugh map을 3차원 공간에서 위 아래로 펼쳐놓은 형태로 위에는 A=1, 아래는 A=0에 해당한다. 바로 위, 또는 아래의 A는 서로 인접한 것으로 생각한다. 따라서 왼쪽 그림과 같이 위 아래를 looping하는 것이 가능하다. 실제 5-variable Karnaugh map을 위와 같이 3차원으로 그릴 필요는 없고, 오른쪽 그림과 같이 중간에 사선을 그린 형태로 그리면 된다. 오른쪽 그림의 왼쪽을 보면 A 1/0 이라고 되어있는 것을 볼 수 있다. 즉, 사선의 왼쪽은 A=1, 오른쪽은 A=0에 해당하는 칸을 나타낸다. 사선 왼쪽과 오른쪽의 각 16개 칸은 layer 라고 부..