[논리회로] 카르노 맵과 콰인-맥클러스키 알고리즘

https://dev-dx2d2y-log.tistory.com/198

[논리회로] 가장 기본적인 논리게이트로 합성하기

저번에는 SOP나 POS 형태로 논리함수로 논리회로를 만드는 방법에 대해 알아보았다. 그러나 주어진 논리회로의 최소비용을 알아내는 과정에서 대수학적 방법을 사용해야했고, 그 대수학적 과정이 매우 복잡하고, 번거로운 과정인 경우가 많았다.

 

따라서 카르노 맵(Karnaugh map)이라는 방법이 존재하는데, 이를 통해서 최소비용의 논리식을 쉽게 구할 수 있다.

---

민텀 m0, m2, m4, m5, m6으로 구성된 논리함수 f가 있다고 치자. 기존방식을 이용하면

 

로 구할 수 있다. 식을 자세히보면 m0과 m2가, m4와 m5이 결합하고, m6과 다시 m4가 결합한다.

 

m0과 m2가 계산된 값 ~x1~x3와 m4와 m6이 계산된값 x1~x3를 보면, 다시 ~x3로 값을 묶을 수 있다는 것을 알 수 있다. 따라서 m0, m2, m4, m6는 모두 ~x3에 포함된다고 할 수 있다. 여기서 포함이라는 뜻은 m0, m2, m4, m6가 모두 ~x3을 가지고 있다, 즉 민텀값의 x3에 해당하는 값이 0이다라는 뜻이다.

 

m0 = 000

m2 = 010

m4 = 100

m6 = 110

이렇게 x3에 해당하는 값이 0, ~x3를 포함하고 있다.

또한 나머지 민텀인 m5의 경우에는 m4와 함께 묶어서 x1~x2를 산출해낸다.

 

따라서 최종적으로 도출된

f = ~x3 + x1~x2 에서,

 

x3 = 0이라면 중간에 or 연산이 있으므로 f = 1이다. 따라서 x3 = 0이면 f는 x1, x2에 상관없이 값이 1이라는 뜻.

m0, m2, m4, m6끼리 묶여서 ~x3을, m4와 m5가 묶여서 x1~x2를 산출해냈다.

 

이 도표처럼 m0, m2, m4, m6의 경우에는 x3 = 0이라면 x1, x2의 가능한 모든 경우의 수마다 f = 1이다.

또한 m4와 m5의 경우에는 x1 = 1, x2 = 0 일때 x3에 관계없이 f = 1이다.

 

따라서 지금까지 알아본 내용은 단일 항으로 결합가능한 f = 1인 민텀을 그룹화할 수 있다. 즉, 어렵게 대수학적 접근을 할 필요없이, 최종 연산에서 반드시 f = 1이 되도록하는 경우를 민텀들을 그룹화하여 나타낼 수 있다는 뜻이다. 위의 예시에서는 m0, m2, m4, m6를 그룹화해서 x3 = 0일 때와 m4, m5를 그룹화하여 x1 = 1, x2 = 0일 때 f = 1이라는 것을 알 수 있다는 것이다.

 

그래서 카르노 맵은 이러한 목적을 위해서 사용한다. 민텀의 결합에 유용할 뿐 아니라 논리함수를 최소비용으로 구현하도록하는 회로의 유도에 사용할 수 있다.

---

카르노 맵

2-변수 카르노 맵

https://dev-dx2d2y-log.tistory.com/198

[논리회로] 가장 기본적인 논리게이트로 합성하기

이전에 입력이 (0,0), (0, 1), (1,1) 일 때 f = 1이되도록 예제를 알아본 적이 있는데, 이것으로 또 카르노 맵을 작성해보면

 

우선은 도표를 그려서 각 칸을 x1과 x2에 매핑시키고, 각 x1과 x2에 의해 가능한 f를 도표의 각 칸에 기재한다.

 

두 번째 행의 두 셀이 모두 1이며 인접한다. 즉, 행을 담당하는 x2 변수가 1이라면, 반드시 f = 1이라는 뜻이다. 위에서 볼 수 있듯이, x2가 필수적인 변수이고, 나머지 식들은 결합법칙으로 사라질 것이므로 두 번재 행의 인접한 두 셀을 표현하는 방법은 단순히 x2이다.

 

첫 번째 열도 보면 첫번째 열의 두 개의 셀에서도 f = 1이다. 이 셀들은 x1 = 0에 해당한다. 따라서 x1 = 0이면 x2의 값에 관계없이 f = 1이라는 얘기. 따라서 첫 번째 열의 인접한 두 셀을 표현하는 방법은 ~x1이다.

 

이것으로 f = 1이 되는 모든 경우를 처리하였으므로 f = x2 + ~x1이다.

 

따라서 2-변수 카르노 맵을 작성하는 방법은 특정 행 또는 열의 인접한 셀의 값이 모두 1이되는 경우, 해당 셀은 특정 행/또는 특정 열로 인해서 반드시 f = 1이 되는 경우를 뜻한다. 그리고 그 외의 변수는 결과값에 아무런 영향을 끼치지 못한다는 뜻. 따라서 결과에 영향을 미치는 변수를 찾아서, 1이면 그대로, 0이면 그 보수의 형태로 식에 추가하는 식으로 카르노 맵을 사용할 수 있다.

---

3-변수 카르노 맵

3-변수 카르노 맵은 2-변수 카르노 맵을 옆으로 확장하면 된다.

m1, m4, m5, m6을 민텀으로 갖는 논리함수를 가지고오면,

 

열에는 x1과 x2의 조합이, 행에는 x3를 표시한다. 맵상에서 인접한 셀의 민텀이 한 개의 곱 항으로 결합되는 것을 보장하기 위해서는, 인접한 셀들이 오직 한 개의 변수 값을 달리해야한다. 왜냐하면 일반적인 계산방식에서 볼 수 있듯이, 결합법칙을 사용하면 두 개의 변수가 변하지 않고 오직 한 개의 값만 변해서 결합법칙을 사용하여 식을 소거할 수 있는데, 두 가지 변수가 바뀌면 결합법칙을 사용할 수 없기 때문이다.

카르노 맵은 묶을 수 있는 두 개의 항이 쌍으로 배치되어 있어 결합법칙을 통해 연산값을 간단히하는 것을 상정하여 계산되기 때문에, 인접한 두 셀의 변수값이 두 개 이상 차이나면 사용할 수 없다.

 

즉, x1, x2의 조합을 00 01 10 11로 한다면, 두 번째 열과 세 번째 열에서 x1과 x2에서 차이가 발생한다. 따라서 x1, x2의 조합을 00 01 11 10 으로 설정해서 인접한 셀 간 차이가 생기는 변수가 오직 한 개만 발생하게끔 설정한 것이다. 또한 첫 번째 항과 네 번째 항도 인접하다고 생각한 뒤에 계산해야하기 때문에, 더더욱이 00 01 11 10 으로 배치해야한다.

 

그래서 이를 그레이 코드(gray code)라고 한다.

 

아무튼 그래서 식을 짜보자면, 위쪽 행의 3, 4번 열에서 f = 1이다. 여기서는 x1 = 1, x3 = 0으로 고정되므로 x1 = 1과 x3 = 0만 보장되면 x2에 관계없이 f = 1, x1~x3 식이 도출된다.

 

아래쪽 행의 1, 4번 열에서 f = 1이므로, 여기서는 x2 = 0, x3 = 1로 고정되므로 ~x2x3 식이 도출된다.

m4와 m5를 묶지 않는 이유는 이미 m4는 m6와, m5는 m1과 묶였기 때문에, 모든 민텀들이 묶음에 참여 중이기에 또 묶지 않는 편이다. 민텀들은 중복으로 묶일에 참여할 수 있으나, 이미 모든 민텀들이 묶였다면 또 묶지는 않는다. 가장 간단하게 논리식을 표현해야하니까.

 

위와같은 경우에는 000, 010, 110, 100에서 f = 1이므로 x3 = 0과 110, 111에서 f = 1이므로 x1~x2가 추가된 것이다.

 

카르노 맵에서는 최대 8개의 셀에 1이 적힐 수 있다. 즉, 어떤 수가 입력되어도 항상 1이 출력되는 상황이 이에 해당한다.

---

4-변수 카르노 맵

4-변수 카르노 맵은 4x4의 배열을 활용한다. 역시 00 - 01 - 11 - 10 의 순서를 행과 열이 사용한다. 변수를 적어놓은 부분은 해당 부분에서 인접한 셀이 1일 경우 해당 부분에 해당하는 변수가 식에 추가되어야함을 의미한다.

 

f1 함수는 1101, 1001에서 f = 1이다. 고정되는 값은 x = 1, x3 = 0, x4 = 1 이므로 x1~x3x4가 식에 추가되고, 이외에도 0011, 0010, 1011, 1010에서 f = 1이므로 x2 = 0, x3 = 1에서 f = 1이다. 따라서 ~x2x3가 식에 추가되어 f1 = ~x2x3 + x1~x3x4

 

특이한 점으로는 윗 모서리와 아래 모서리도 연결된 것으로 간주한다. (f3)

카르노 맵에서 인접한 셀들을 묶는 과정과 그로인해 도출되는 함수의 경우의 수는 한 가지로 고정된 것이 아니다. 따라서 여러 개가 존재할 수 있다.

 

f4번 같은 경우에는 왼쪽 위의 4개, 오른쪽 아래 4개를 묶고나면 2개의 인접한 두 셀이 1로 연결되어있다. 여기의 식은 x1x2~x3이다만, 이 경우 이 2개만 묶는게 아니라 인접한 2개를 더해서 4개로 묶어도 된다. 이 때 식은 x1x2 (아래로 인접한 셀 4개), x2~x3 (정사각형으로 인접한 셀 4개)이 도출된다. 우선 비용이 줄었고, 두 방식은 비용이 같기 때문에 아무거나 선택해도된다.

 

그래서 카르노 맵에서 셀들을 묶을 때, 2의 제곱수 단위로 묶어야하며, 2개보단 4개, 4개보단 8개를 묶을 수 있는 경우를 우선적으로 고려해야한다. 항은 중복되더라도 회로비용이 감소한다.

---

이외

5변수맵의 경우에는 4변수 맵을 사용하기도하고, 이 이상으로가면 훨씬 복잡하고 까다로운데다가 CAD 툴 같은게 자동최소화를 지원해주기 때문에 굳이 다루지는 않겠다. 전공수업에서 다루면 보강할 예정이다.

 

이렇듯 카르노 맵은 함수값이 1이 되도록하는 모든 경우를 가능한 큰 그룹으로 묶고, 그 그룹의 수가 가능한 적게 나오도록하는 방법이다.

---

카르노 맵이 아닌 최소화 기법

용어정리

카르노 맵에서는 직관적인 방법으로 비용최소화를 진행했다. 5-변수 함수에서 알 수 있듯이, 이 방식은 입력 변수가 적으면 적절하지만, 입력변수가 많은 경우에는 적절하지 못한 방법이다.

 

 

최소화된 식의 각 항은 여러 개의 변수로 구성된다. 각각의 변수들을 리터럴이라고 칭한다. 리터럴은 변수 또는 변수의 보수 형태로 존재한다.

 

함수의 출력이 1이되도록하는 입력 변수들의 조합을 임플리컨트(Implicant)라고한다. 가장 기본적인 임플리컨트는 민텀이다. 여기서 임플리컨트는 논리식이 아니라, 논리식 내에서 각 항을 의미한다.

 

또한, 임플리컨트에서 최소화를 반복하여, 더 이상 최소화를 진행할 수 없는 식, 입력 변수들의 조합을 프라임 임플리컨트(prime implicant)라고한다. 카르노 맵으로 구한 최소화된 SOP 논리식은 프라임 임플리컨트의 논리합으로 구성된다. 카르노 맵에서 민텀의 묶음 한 개가 프라임 임플리컨트.

 

그리고 주어진 함수가 1이 되도록하는 모든 입력조합을 커버라고한다. 대부분의 함수들은 서로 다른 여러 커버를 가지며, 민텀, 임플리컨트, 프라임 임플리컨트들도 커버에 해당한다.

 

회로에서 비용이란 함수를 구현하는 회로의 게이트 수와 모든 게이트의 입력의 수의 총합을 의미한다. 단, 입력 변수에 대한 NOT 연산에는 비용이 발생하지 않는다.

~(x1~x2 + x3)(~x4 + x5)라고하면, AND게이트 2개, OR 게이트 2개, NOT 게이트 1개가 필요하고, 각 AND, OR 게이트마다 입력 2개씩해서 총 8개, NOT 게이트에 입력 1개해서 입력값은 1개. 2 + 2 + 1 + 9 = 14. 총 비용은 14.

---

최소화 절차 알아보기

그래서 최소화 절차에 대해서 더 알아보자면,

 

결국에 비용과 회로의 복잡도를 최소화하려면, 항의 수를 가장 최소로 해야한다. 즉, 프라임 임플리컨트들의 부분집합을 최소한의 비용이 되도록 구성해야한다. 만약 어떤 프라임 임플리컨트가 다른 프라임 임플리컨트에는 포함되지 않으면서 그 자체로 f = 1이 되도록하는 민텀을 포함한다면, 이를 에센셜 프라임 임플리컨트(essential prime implicant)라고 칭한다.

 

프라임 임플리컨트와 최소화 예시를 더 알아보자면,

m5, m13, m3, m7, m11, m2, m6, m14, m10이 민텀인 논리함수를 최소화한다고 하자.

 

1. 주어진 함수에 대해서 모든 프라임 임플리컨트를 구한다.

즉, 카르노 맵에서 구할 수 있는 가장 큰 크기의 f = 1이 되는 민텀 집합을 구하라는 뜻이다. 모든 프라임 임플리컨트를 구하는 것이므로 모든 민텀들이 묶음에 참여하고 있는지는 고려하지 않는다.

 

2. 에센셜 프라임 임플리컨트들을 찾는다.

다른 프라임 임플리컨트들에는 포함되지 않으면서, f = 1이 되도록하는 민텀을 포함하는 프라임 임플리컨트를 찾아야한다.

 

여기서의 프라임 임플리컨트들은 모두 에센셜 프라임 임플리컨트다. x2, x3는 m7을 커버하는 유일한 프라임 임플리컨트, ~x1은 m0, m1, m2를 커버하는 유일한 프라임 임플리컨트다.

 

따라서 위의 예시에서 프라임 임플리컨트들을 찾아보면

x2~x3~x4 (m13을 커버하는 유일한 프라임 임플리컨트)

~x2x3 (m11을 커버하는 유일한 프라임 임플리컨트)

~x3~x4 (m14를 커버하는 유일한 프라임 임플리컨트)

가 될 것이고, 그 중에서 ~x1x3와 ~x1x2x4는 그 어느 민텀도 단독으로 커버하지 못하므로 에센셜 프라임 임플리컨트에서 제외된다.

 

3. 에센셜 프라임 임플리컨트가 f = 1인 모든 경우를 커버하면, 이 집합이 최적의 커버이고, 그렇지 않다면 에센셜 프라임 임플리컨트가 아닌 프라임 임플리컨트 (non-essential prime implicant)를 추가해야한다.

이를 논-에센셜 프라임 임플리컨트라고한다. 위에서 봤듯이, 에센셜 프라임 임플리컨트들로만 식을 구성하면 m7이 커버되지 못하므로 논-에센셜 프라임 임플리컨트 ~x1x2x4를 추가한 것이다. (최소화의 목적이 비용을 줄이는 것이므로 입력변수가 적은 것을 추가)

 

그러나 위의 경우는 쉬운 경우에 해당하고, 주로 회로 규모가 크거나 논에센셜 프라임 컴플리컨트를 정하기 애매한 경우가 태반이다. 그럴 때는 주로 휴리스틱 (heuristic) 방법을 사용한다. 휴리스틱 방식은 논에센셜 프라임 컴플리컨트 하나하나 골라가며 비용이 최소가 되며 모든 민텀을 커버할 수 있는 논리식을 도출하는 과정으로, 마치 트리구조와 비슷하다고 볼 수 있다.

 

예시를 들어보자면, 여기서 에센셜 프라임 컴플리컨트는 m0, m4에 의해 ~x3~x4 밖에 없다. 하지만 이 프라임 컴플리컨트 하나만으로는 모든 민텀을 커버하지 못하므로 논에센셜 컴플리컨트를 추가해야한다.

 

그런다음 x1x2~x3를 선택해보면, 남은 민텀은 m10, m11, m15를 커버하는 프라임 임플리컨트가 필요하며, 이들은 모두 x1x3x4 + x1~x2x3로 커버가 가능하므로 최종식은 ~x3~x4 + x1x2~x3 + x1x3x4 + x1~x2x3 가 된다. (볼드체가 에센셜)

 

두 번째로는 x1x2~x3를 제외해보는 것이다. 그러면 x1x2x4가 m13 때문에 에센셜 프라임 임플리컨트가 된다. 그리고 x1x2x4는 m15를 커버하기 때문에 m10과 m11을 커버해야하므로, x1~x2x3를 사용해 이를 커버할 수 있다. 최종식은 ~x3~x4 + x1x2x4 + x1~x2x3으로, 아까보다 비용이 적다. 이를 모든 논에센셜 프라임 임플리컨트마다 해보면 된다. 사람이 할 때는 민텀을 많이 커버하는 논에센셜 프라임 임플리컨트부터 건드려보는 것이 좋고, 컴퓨터의 경우에는 그냥 재빨리 수행해버리니까 무상관.

 

때로는 에센셜 프라임 임플리컨트가 전혀 없는 경우가 있는데, 이럴 때에는 임의로 하나의 프라임 임플리컨트를 선택하여 계산해나가면 된다.

 

이 방식들을 토대로 논리함수의 크기와 무관하게 최소 비용을 찾을 수 있다. 논리회로 크기가 작은 경우에는 카르노 맵을 이용해 프라임 임플리컨트를 찾는 것이 가장 편하다. 논리회로 크기가 큰 경우에는 프라임 임플리컨트를 찾고, 모든 민텀이 커버가 되지 않을 경우에는 논에센셜 프라임 임플리컨트를 하나씩 대입해보면서 가장 최소의 비용을 찾으면 된다.

 

이를 Qunie-McCluskey 알고리즘이라고 칭한다. (콰인-맥클러스키 알고리즘)

https://github.com/int-main/Quine-McCluskey/blob/master/Quine%20McCluskey.py

Quine-McCluskey/Quine McCluskey.py at master · int-main/Quine-McCluskey

깃허브에 파이썬으로 콰인-맥클러스키 알고리즘을 구현한 사례가 있다. 참고. 사실 잘 모르겠다 파이썬을 너무 오래 안해서 그런가 문법 다까먹음

---

POS에서의 카르노 맵

 

POS형태도 카르노 맵을 이용해 최소화할 수 있다. 이는 SOP형태와 크게 다르지 않다. 맥스텀을 사용하며, 가능한 맥스텀의 크기를 크게 가져가고, 맥스텀의 각 요소들은 논리합으로, 각 항들은 논리곱으로 표현하고, 맥스텀이 0이어야 논리식에 들어가야한다는 것이 다르다.

전에 같은 식이더라도 POS와 SOP의 비용이 다를 수 있다고했는데, 그 예시로 들 수 있다. 딱봐도 식이 더 복잡해보인다.

이외에도 굳이 카르노 맵을 그릴 필요없이 SOP를 구해서 보수를 구하면된다.

---

불완전 정의에서 카르노 맵

디지털회로에서 입력변수 (x1, x2)에 대해 00, 01, 10의 입력은 받을 수 있으나 11의 입력은 절대 받을 수 없다고 가정해보면, 이 (x1, x2) = 11을 반드시 일어나지 않는, 무정의 조건(don't-care condition)이라고 할 수 있다. 또 무정의 조건을 갖는 함수를 불완전 정의(incompletely specified)되었다고한다.

 

무정의항은 논리회로에서 편리하게 사용할 수 있는데, 절대로 발생하지 않는 경우이므로 아무 값이나 할당해도된다. 위의 경우 (x1, x2) = 11인 경우는 일어나지 않으므로 어떤 값을 할당해도된다.

 

무정의 예시

입력 (x1, x2)는 절대로 11이 될 수 없으므로 m12, m13, m14, m15는 무정의 항이라고한다. 그리고 이를 d12, d13, d14, d15라고 칭한다.

 

SOP에서는 가능한 큰 1의 묶음을 만들어야한다. 따라서 d12, d13, d14는 1, d15는 0이라고 가정하면, 가능한 큰 1의 묶음이 도출된다. 논리회로를 저렇게 짜도 1100, 1101, 1110, 1111 같은 경우의 수는 일어나지 않으므로 더 저렴한 비용으로 논리회로를 설계할 수 있다.

 

그래서 x2~x3 + x3~x4라는 간단한 식으로 표현할 수 있다. 만약 무정의항을 0이라고 가정했다면 ~x1x2~x3 + ~x1x3~x4 + ~x2x3~x4라는, 다소 복잡한 식이 등장했을 것이다. 따라서 어차피 일어나지 않으므로 계산에 편리하도록 무정의 항을 가정해서 사용할 수 있다.

---

이렇게 카르노 맵을 통한 최소화 방법에 대해서 알아보았다. 이 뒤로 예제, CAD, 베릴로그 등 약간의 내용이 남았는데, 다음 논리회로 글에서는 그 내용만 한 번 더 정리하고 3장으로 넘어갈 예정이다.

 

원래 자바도 그렇고 C도 그렇고 다 초반이 제일 지루하다. 기초 내용을 배우고 현란하게 응용할 수 있는 레벨이 되기 전까지는 다소 지루한 편이다. 2장만 지나면, 3장부터는 산술회로 - 4장 조합회로 빌딩 블록 - 5장 레지스터, 카운터 - 8장 최적화 - 9장 비동기 - 11장 테스팅 등 다양한 내용들이 있으니 하나씩 읽어나가기만하면 된다.

 

컬러잇으로도 한 번 다룰 생각이긴하다만.. 전공수업을 듣고 다룰지 그냥 다룰지 잘 모르겠다. 우선 3월 전까지 완독을 목표로하는데 그게 쉬운 일도 아니고.. 우선 매일 읽으면 2~3일에 1개의 챕터를 끝내는 것을 목표로한다. 22~33일 완성.