개요 Input과 output 사이에 직렬로 연결되는 gate의 최대 개수는 gate의 level의 개수에 따른다. 따라서, sum-of-products 또는 product-of-sums의 형태로 되어있는 function은 곧, 2-level gate circuit로 귀결된다. 일반적으로, gate가 flip-flop output으로 부터 나오는 case에서는 모든 variable과 그의 complement는 circuit input으로 사용할 수 있다. (flip-flop은 이후에 다루게 됨) 이러한 이유 때문에, inverter는 보통 level로 카운트 하지 않는다. 앞으로는 다음의 용어를 사용할 것이다. 1. AND-OR circuit AND gate가 OR gate 다음에 이어지는 2-level..

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

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

모양 2-variable 에서 확장하여 이번엔 3-variable Karnaugh map을 살펴보자. 아래쪽으로 길쭉한 형태인데, 이번엔 A, B 두개가 아니라 A, BC로 표현되어 있기 때문이다. (AB, C라면 가로로 길쭉한 모양이 될 것이다. 어느쪽으로 긴지 짧은지는 큰 상관이 없다.) BC로 표현되면서 0, 1이 아닌 00, 01, 11, 10이 각 행별로 쓰여져 있다. 각 행은 BC가 00, 01, 11, 10에 해당하는 숫자가 된다. 그림에서도 볼 수 있듯이 ABC = 001을 가리키고 있는 화살표를 살펴보면 BC = 01, A = 0 임을 볼 수 있다. 이러한 방식으로 truth table의 각 숫자들이 배치된다. 주의할 점은 00, 01, 11, 10이라는 숫자의 배치가 서로 뒤섞여서는 안..

Minterm & Maxterm n개의 variable, A, B, C ... 가 있다고 하자. 각각의 variable 또는 그의 complement(A' 와 같은)를 한번씩만 사용하여 어떤 곱을 만든것을 minterm이라고 한다. 예를 들면, variable이 A, B, C 3가지가 있다면, ABC, ABC', A'BC ... 와 같은 것들을 minterm이라고 부를 수 있다. 각각의 variable 또는 그의 complement(A' 와 같은)를 한번씩만 사용하여 어떤 합을 만든것을 maxterm이라고 한다. 예를 들면, variable이 A, B, C 3가지가 있다면, A + B + C, A + B + C' ... 와 같은 것들을 maxterm이라고 할 수 있다. Minterm & Maxterm E..

DeMorgan's Laws (X + Y)' = X'Y' (XY)' = X' + Y' (X' + Y')' = XY (X'Y')' = X + Y (A + B + C + D + E + F + … )' = A'B'C'D'E'F' … ABCDEF … = A' + B' + C' + D' + E' + F' + … NOT operation을 통해서 OR operation과 AND operation을 서로 맞바꿀 수 있다. 우리는 이를 complement operation이라고 부르기도 한다. OR이나 AND operator가 여러개 붙어있더라도 모두 적용된다. 몇 가지 예제를 살펴보자. Finding a Complement (A' + B)C' '위 expression의 complement를 찾아라'라는 문제는 곧 [..