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

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

정의 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..

Location of Minterms on Karnaugh Map Variable이 4개인 경우에는 보통 정사각형 모양으로 Karnaugh Map을 그리기 위해 variable을 두 개씩 나누어 행과 열에 배치한다. 3-variable에서와 같이 여기서도 행과 열을 각각 00, 01, 11, 10으로 배치했다. 그 결과 각 칸의 decimal notation은 위와 같게 된다. 예를 들어 14인 칸에 대해서, 14는 2진수로 1110 으로 표현되므로, A=1, B=1, C=1, D=0 인 칸임을 알 수 있다. 이외에 특기할 만한 사항이 없으므로 곧바로 예제를 살펴보도록 하자. Getting Minimum Expression 다음을 Karnaugh map에 그리고 minimum expression인지 확인..

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