[논리회로] (5) - 카노맵 (Karnaugh map), 주항, 필수주항

 

 

 

 

스위칭 함수는 일반적으로 대수학적인 방법으로 간략화될 수 있으나 대수학적 방법은 두 가지 문제가 있습니다.

 

1. 체계적인 방법으로 적용하기 어렵다.

2. 최소 해답(minimum solution)을 얻었는지 확인하기 어렵다.

 

이 장에서 학습할 카노맵(Karnaugh map) 방법과 이후 다룰 퀸-맥클러스키(Quine-McCluskey) 방법은 스위칭 함수를 체계적인 방법으로 간략화시킬 수 있으므로 위의 문제점을 해결할 수 있습니다.

 

카노맵은 3변수 혹은 4변수로 이루어진 스위칭 함수를 간략화하고 조작하는 데 특별히 유용한 방법입니다.

 

 

 

 

 

 

🧐 스위칭 함수의 최소 형식

어떤 함수를 AND와 OR 게이트를 사용하여 구현할 때, 이에 들어가는 비용은 게이트의 개수, 게이트 입력의 개수와 연관이 있습니다.

카노맵은 AND와 OR 게이트로 이루어진 2단(two-level) 회로를 최소의 비용으로 구현할 수 있게 합니다.

 

곱의합(SOP, sum-of-product) 항으로 구성된 식은 한 그룹의 AND 게이트의 출력이 한 개의 OR 게이트의 입력으로 연결되어 있는 2단 회로와 일치합니다.

 

비슷하게 합의곱(POS, products-of-sum) 식은 한 그룹의 OR 게이트의 출력이 한 개의 AND 게이트의 입력으로 연결되어 있는 2단 회로와 일치합니다.

 

따라서 최소비용의 2단 AND-OR 게이트 회로를 찾기 위해서 곱의합이나 합의곱 형식의 최소식(minimum expression)을 찾아야 합니다.

 

 

 

 

 

 

 

 

 

🧐 최소 곱의합

어떤 함수에 대한 최소 곱의합(minimum sum of products) 식은 최소 개수의 항을 가지며, 각 항은 최소 개수의 문자를 가지는 곱의합 형식으로 정의된다.

함수에 대한 최소항 전개식과는 다르게, 최소 곱의합은 반드시 유일무이한 것이 아닙니다. 주어진 함수는 같은 수의 항과 같은 수의 문자를 가지는 두 개의 최소 곱의합 식을 가질 수 있다는 의미입니다.

 

최소항 전개식이 주어졌을 때, 최소 곱의합 식은 보통 다음의 과정을 통해 얻을 수 있습니다..

 

 

1. 결합 정리 XY' + XY = X 를 이용하여 항들을 결합한다.

2. 합의(consensus) 정리 또는 이외 다른 정리를 이용하여 중복항을 소거한다.

 

유감스럽게도 위 과정의 결과는, 항이 결합되고 소거될 때의 순서에 의존하므로 마지막 결과 식이 반드시 최소식이라고 할 수 없습니다.

 

 

 

 

 

 

 

 

🧐 최소 합의곱

어떤 함수에 대한 최소 합의곱(minimum products of sum) 식은 최소 개수의 항을 가지며, 각 인수는 최소 개수의 문자를 가지는 합의곱 형식으로 정의됩니다.

 

 

 

 

그러나 부울 대수만으로는 최대 곱의합이나 최소 합의곱을 찾아내기가 쉽지 않습니다. 간략화를 한 것이 과연 가장 이상적인 식일지 알 수가 없다는 뜻입니다. 이를 카노맵을 사용하여 해결할 수 있습니다.

 

 

 

 

 

 

 

 

 

 

🧐 2변수와 3변수 카노맵

 

🌱 2변수 카노맵

어떤 함수의 카노맵은 독립적인 변수들의 모든 조합의 값을 표시할 수 있습니다.

2변수 카르맵에서는 한 변수의 값이 맵의 윗 부분에 가로 방향으로 나열되어 있고, 다른 변수는 맵의 왼쪽 측면에 나열되어 있습니다.

 

그림으로는 다음과 같습니다.

 

 

아래 그림에서는 함수 F에 대한 진리표와 그에 해당하는 카노맵을 보여줍니다.

A = B = 0일 때 F의 값이 사각형 중 왼쪽 위 칸에 채워져 있으며, 비슷한 방법으로 맵의 다른 곳들도 채워져 있습니다.

 

중요한 점은 카노맵에서 각각의 1은 함수 F의 최소항(minterm, 모든 변수가 1번씩 사용된 n개 문자의 곱)입니다.

 

카노맵에서 인접한 최소항들은 하나의 변수만 다릅니다. 예를 들어 위 그림에서는 A'B'과 A'B는 B 하나의 변수만 다릅니다.

하나의 변수만 다르면 서로 결합될 수 있으며, 따라서 위의 예시에서는 A'B' + A'B = A' 가 됩니다.

 

최우측 그림에서처럼, 인접한 1을 하나의 루프로 묶습니다.

 

 

 

 

 

 

 

🌱 3변수 카노맵

위는 3변수 진리표와, 이에 해당하는 카노맵입니다.

변수 A의 값이 맵의 맨 윗부분에 가로로 나열되고, 다른 두 변수인 B와 C는 맵의 측면을 따라서 나열됩니다.

 

각 열들을 00, 01, 11, 10의 순서로 표기되므로, 인접한 열들은 오직 한 개의 변수값만 다르게 됩니다. (만약 00, 01, 10, 11의 순서로 표기된다면, 인접한 열들은 2개의 변수가 다를 수도 있기에, 순서를 위와 같이 지정해줍니다.)

 

2변수 카르맵과 마찬가지로 서로 인접한 칸에 있는 최소항들은 하나의 변수만 다르기에 결합정리를 통해 결합할 수 있습니다.

물리적으로 인접한 칸 뿐만 아니라 가장 윗열과 가장 아랫열도 서로 인접한 것으로 봅니다. 해당 열에 대응하는 최소항들도 한 변수만 서로 다르기 때문입니다.

 

 

함수의 최소항 전개식이 주어졌을 때, 최소항에 해당되는 카노맵의 칸에 1을 채우고, 나머지 칸에 0을 채워 넣어서 표시할 수 있습니다. 아래는 3변수 카노맵에서의 최소항의 위치입니다.

 

 

 

 

 

 

 

 

🌱 곱항들의 카노맵

 

위 그림은 곱항들이 카노맵에 표시되는 방법을 보여줍니다.

항 b는 b=1인 네 칸에 1을 채워넣습니다.

항 bc'는 b=1, c=0일때 1이므로, bc =10인 열의 두 칸에 1을 넣습니다. 항 ac'도 같은 방법으로 채워넣습니다.

 

항이 대수 형식으로 주어지면, 맵에 그리기 전에 최소항 형식으로 전개하는 것은 불필요합니다.

만약 대수식이 곱의합 형식으로 전환되면, 각 곱항들은 1의 그룹으로 맵에 그려질 수 있습니다.

 

예를 들면 다음과 같습니다.

$$f(a,b,c) = abc' + b'c + a'$$

에 대해서, 다음과 같이 카노맵을 작성할 수 있습니다.

 

 

 

 

 

 

🌱 카노맵을 사용한 최소 곱의합

 

 

 

 

 

 

 

 

🌱 카노맵을 통한 최소해의 개수

만약 함수가 둘 이상의 최소 곱의합 형식을 가진다면, 이 식들은 카노맵으로부터 구할 수 있습니다.

아래는 

$$F = \sum m(0,1,2,5,6,7)$$

에 대한 두 개의 최소 해(minimum solutions)을 보여줍니다.

(좌측)F = a'b' + bc' + ac (우측)F = a'c' + b'c + ab

 

 

 

 

 

 

 

🌱4변수 카노맵

아래는 4변수 카노맵에서 최소항의 위치입니다. AB가 11과 10인 부분에 유의해서 봐주셔야 합니다. 

 

 

4변수 카노맵의 사용 예시로 다음 식을 표현해 보겠습니다.

$$abc + a'b + d' $$

 

 

 

 

 

 

🌱 4변수 카노맵을 사용하여  최소항 전개 -> 최소 곱의합 형식으로 전환

 

카노맵에서 간략화를 할 때 주의할 점은 (loop로)묶어지는 칸들의 수는 2의 제곱수여야 합니다.

 

 

 

 

 

 

 

 

 

🌱 무관항 (don't care term)의 표시

카노맵에서 최소항들은 1로 표시되며, 무관항은 X로 표시됩니다.

최소 곱의합 식을 구하기 위해 항들을 선택할 때 모든 1들은 사용되어야 하지만, X는 결과식을 간략화하는데 필요한 경우에만 사용됩니다.

 

 

 

 

 

 

 

 

 

 

 

🧐 필수주항을 사용한 최소식의 결정

 

 

🌱 implicant(관련항)

함수 F에 대한 카노맵에서 단일 1이나 묶음으로 있는 여러개의 1은 F의 관련항(implicant)이라고 불리는 곱항을 나타냅니다.

 

 

 

 

🌱 Prime implicant(주항)

그리고 곱항으로 표시된 관련항(implicant)이, 변수를 소거하기 위한 다른 항과 결합할 수 없다면 주항(prime implicant)이라고 불립니다.

위의 그림을 보면, a'b'c, a'cd', ac'은 변수를 소거하기 위한 다른 항들과 결합할 수 없으므로 주항입니다.

반대로 a'b'c'd'는 a'b'cd'나 ab'c'd'와 결합될 수 있으므로 주항이 아닙니다.

abc'와 ab'c'도 결합되어 ac'가 될 수 있으므로 주항이 아닙니다.

 

 

 

함수의 모든 주항은 카노맵으로부터 구할 수 있습니다.

카노맵에서 단일 1은 다른 1들과 인접하지 않다면 주항이 됩니다.

두 개의 인접한 1은 네개의 1로 이루어진 그룹에 포함되지 않는다면 주항이 됩니다.

네 개의 인접한 1은 여덟 갸의 1로 이루어진 그룹에 포항되지 않는다면 주항이 됩니다.

 

어떤 함수에 대한 최소 곱의합(minunum sum of products) 식은 몇 개의 주항으로 구성됩니다.

따라서 주항이 아닌 항을 포함하는 곱의합 식은 최소식이 될 수 없습니다.

주항이 아닌 항이 있다면 추가적인 최소항과 함께 결합되어 수식을 간략화할 수 있기 때문입니다.

 

카노맵에서 최소 곱의합을 찾기 위해서는 맵에서의 모든 1을 포함하는 최소 개수의 주항을 찾아야 합니다.

주의할 점은 최소 곱의합에 포함되지 않은 주항이 여럿 있을 수 있다는 것입니다.

즉 함수의 모든 주항이 일반적으로 최소 곱의합을 구할 때 필요한 것이 아니므로, 주항을 선택할 때는 체계적인 과정을 통해서 선택해야 최소 곱의합을 구할 수 있습니다.

 

 

 

 

 

 

 

 

🌱 필수주항(essential prime implicant)

최소항(minterm)이 단 하나의 주항에만 포함된다면 그 주항은 필수주항(essential prime implicant)라고 불리고, 최소 곱의합 식에 포함되어야 합니다.

 

예시를 위해 아래 그림을 살펴보도록 하겠습니다.

 

 

위 그림에서 m2 최소항은 B'C에만 포함되지만, 다른 최소항들(m3, m5, m7, ...)은 2개의 다른 주항에 의해 포함됩니다.

최소항이 단 하나의 주항에만 포함된다면, 그 주항은 필수주항이라고 불리므로 B'C는 필수주항이 됩니다.

 

그러나 CD는 CD에 포함된 1들이 다른 주항에도 포함되기 때문에 필수주항이 아닙니다.

 

 

 

 

 

 

 

🌱 카노맵으로부터 최소 곱의합을 구하는 방법

1. 아직 포함되지 않은 최소항(하나의 1)을 선택한다.

2. 그 최소항에 인접한 모든 1과 X(무관항, don't care term)를 찾는다.

3. 단일항이 이 최소항과 인접한 1과 X를 포함한다면, 그 항은 필수주항이므로 선택한다.

4. 모든 필수주항이 선택될 때까지 과정 1, 2, 3 을 반복한다.

5. 맵에서 나머지 1을 포함하는 주항의 최소 집합을 찾는다. (하나 이상의 집합이 있을 때에는 문자수가 최소인 집합을 선택한다.)