모양 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이라는 숫자의 배치가 서로 뒤섞여서는 안..

유용성 지금까지의 simplification 방법은 물론 유용하긴 하지만 일반적으로 적용하기 어려운 것이 사실이다. 좀 더 간단하게 simplify하기 위한 방법 중 하나가 Karnaugh map이다. Variable이 2~5개 정도인 expression이나 equation에 대해서 상당히 유용한 방법이다. 해야할 일은 Karnaugh map을 만들고, 'looping' 과정을 통해서 minimum solution을 얻는 것이다. 그 과정이 몇 줄에 걸쳐서 식을 쓰는 것에 비해 비교적 간단하기 때문에 자주 사용되며, Boolean algebra를 이용해 얻은 식이 minimum solution인지 확인하는데 쓰이기도 한다. 모양 위 그림은 2개의 variable에 대해 Karnaugh map의 틀을 그려..

Don't Care 비교적 큰 규모의 digital system은 많은 subcircuit으로 나뉜다. 위 그림과 같이 2개의 subcircuit N_1과 N_2이 있는 system을 생각해 보자. 만약, w, x, y, z의 어떤 조합도 ABC = 001 이나 110 이 되는 output을 만들어내지 않는다고 가정하자. 즉, ABC는 001이나 110의 값을 가지는것이 불가능하다. 그렇다면 이때의 F는 어떻게 정의될까? 결론 부터 말하자면, 정의할 필요가 없다. 즉, ABC = 001 or 110 이 되는 그러한 상황에 대해서 고려하지 않더라도 시스템을 분석하는데 문제가 없다. 이런 경우에 우리는 N_2에 대해 다음과 같이 truth table을 만들어볼 수 있다. 위의 truth table을 보면, ..

Methods for Determining if an Equation is Valid 모든 variable combination에 대해서 어떤 equation이 유효한지를 알아보는 방법은 여러가지가 있다. 여기서 지금까지 배운 내용을 바탕으로 몇 가지를 정리해보면, 1. Truth table을 만들고, 모든 variable combination에 대해서 좌우변이 동일한 값을 갖는지 확인한다. 이 방법은 variable의 개수가 늘어날 수록 검사해야 하는 경우의 수가 기하급수적으로 늘어나게 되므로, 상당히 비효율적인 방법이라고 할 수 있다. 2. 지금까지 배운 여러 theorem을 이용하여 equation의 한 변을 다른 한변과 동일하게 만든다. 3. 양변을 개별적으로 simplify해서 같은지 확인한다...

정의 XY + X'Z + YZ = XY + X'Z 어떤 식이 위와 같은 형태를 띄고 있을 때, redundant term (필요없는 항) YZ를 소거할 수 있다. 이러한 항을 consensus term 이라고 한다. 증명은 아래와 같다. 이전의 simplification skill 관련 포스트의 맨 마지막 부분에 multiplying out과 factoring에 활용할 수 있는 유용한 방법에 대해서 설명하고 있다. 거기에 있던 식을 가져와 약간 변형시켜 보면 (X' + Y)(X + Z) 가 되는데, 이것을 무턱대고 풀어보면 X'X + X'Z + XY + YZ 가 된다. X'X = 0이므로 소거되버리지만 YZ가 남는다. 이 때 남아버린 YZ를 소거시킬 수 있는 방법이 바로 the consensus theo..

Simplifying Theorem 어떤 expression이 좌변과 같은 형태인 경우에 우변으로 간단하게 바꿀 수 있다. (1), (2), (5)의 경우에는 앞서 배웠던 associative / distributive law를 이용하면 간단히 증명된다. 나머지의 경우는 다음과 같이 증명된다. 이러한 법칙들은 다양하게 이용할 수 있는데, 보통 복잡해 보이는 식들도 치환법과 위의 법칙을 함께 사용하면 매우 쉽게 정리된다. 몇 가지 예제를 살펴보자. Simplifying Examples Z = A'BC + A' X = A', Y = BC 로 치환하면, Z = XY + X 와 같이 나타낼 수 있으므로, 위의 (3)번 식을 적용할 수 있다. 즉 Z = X = A' 로 간단히 할 수 있다. Z = (A + B'C..