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

개요 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이 다음과 같이 정의된다고 하자..

개요 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..

Veitch Diagram Karnaugh map에 A, B, C, D, 00, 01 ... 을 쓰기 이전에, 위와 같이 표기를 하는 방법도 있다. 기존의 방식보다 상당히 간단한 표현법인데, 위 그림을 살펴보면, A, B, C, D가 1인 부분에 대해서만 각 행, 열에 표시를 한 것을 알 수 있다. 그 이외에 A, B, C, D가 0인 부분에 대해서는 표시가 되어있지 않다. 우리는 이를 Veitch diagram이라고 한다. 이러한 형태로 그려놓으면, variable로 표현된 expression이나 function을 Karnaugh map에 그릴 때 더욱 편하다. 하지만, 나중에 배우게 될 sequential circuit problem을 풀 때는 상대적으로 Karnaugh map에 0 또는 1을 표시하..

Factoring Karnaugh map은 factoring에도 사용될 수 있다. 먼저 minterm들을 map에 표시한 다음, looping이 겹치는 1을 찾는다. 위의 경우에는 2군데에서 각각 두개의 looping이 겹치고 있다. 왼쪽위의 경우에는 3개의 1이 일단 AB=00을 공통적으로 가지고 있다. 즉, 각 loop는 term에 A'B'를 공통적으로 포함하고 있으며 A'B'로 factoring이 가능하다. 한편 오른쪽 아래의 1들은 A=1, C=1을 공통적으로 가지고 있으므로 AC로 factoring이 가능하게 된다. 따라서 F는 위에 보이는 것과 같이 각각 A'B'와 AC로 factoring을 할 수 있다. The Consensus Theorem F = ABCD + B'CDE + A'B' + B..

형태 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 라고 부..