Chap 3. 게이트 레벨 최소화 (2) . Gate-level minimization
3-4. 주항 (Prime Implicants)
우리가 전 포스트에서 K-map 방법을 배웠을 때. 맵 안에서 인접한 네모칸들을 선택했다.
우리가 네모칸을 묶고 선택하는 기준에서..
1. 각 칸을 묶을 때는 함수 안의 모든 푀소항들을 커버해야 한다.
2. 결과식에서 항의 수를 최소화해야 한다.
3. 다른 항에서 이미 그 최소항이 선택 됐다면 중복된 항이 있으면 안된다.
그 중에서도. 배운 것 중 가장 많은 변수 조합인 4변수 k-map과 같은 경우에 묶음의 개수가 많아지면서 더 중요한 묶음의 역할이 누가 하는 것인지 판단해야할 상황이 발생한다.
주항 (Prime Implicants) 라는 개념이 여기서부터 나왔는데, 주항이란 맵에서 인접한 네모 칸을 최대로 많이 묶을 때 생기는 곱의 항을 의미한다.
즉 그 최소항을 커버하면서 동시에 더 적은 수의 리터럴을 갖는 항이 없다면 그 항은 주항이 된다.
언제나 그렇듯. 말로 들으면 이해가 가질 않으니, 예시로 들어보겠다.
(b) 그림의 경우에, 1이 들어가는 네모칸이 상대적으로 더 많다보니. 4개씩 묶을 수 있는 경우의 수가 많아진다.
(16이나 8개씩 묶이는 경우가 없으므로)
이 때 더 우선적으로 묶어야 하는 묶음을 '주항' 이라고 한다.
자 여기에서 m5 항과 m0항을 주목해보자.
m0의 항은 4개의 묶음으로 묶이기 위해선 (m5 m7 m13 m15) 의 중앙 네모모양으로 묶이는 경우밖에 없다.
m5의 항은 4개의 묶음으로 묶이기 위해선 (m0 m2 m8 m10) 의 외곽 네모모양으로 묶이는 경우밖에 없다.
이렇게 하나의 1이 4개의 묶음으로 묶이기 위해서는 위의 경우가 '유일' 하다.
그 외의 1들은 다른 4개의 묶음으로 묶일 수 있는 경우가 존재한다.
이 때 이 유일하게 묶일 수 있는 묶음 자체를 '주항' 이라고 하는 것이다.
이런 주항이 중요한 이유는 결국 간소화를 해야하는 입장에서, 주항을 골라내고 묶음으로써 최대 간소화를 가능하게 하기 때문이다.
앞서서 두가지 4개 묶음으로 주항의 우선순위를 찾을 수 있다고 했는데. 그 두 묶음에서 나온 결과값을 보자
(변하지 않는 변수)
(a) 그림에서 보자면 가운데 묶음에서는 BD, 외곽 묶음에서는 B'D'이 변하지 않는다.
결국 우리는 처음에 주어진 (b) 의 그림에서 간소화를 해서 4변수 k-map을 하는것이 목표이므로.
(b)의 그림에서 볼 수 있듯이 다양한 방법으로 나머지 남은 1을 커버할 수 있다.
이러한 경우의 조합으로 간소화한 최종 답은 다음과 같은 경우로 나올 수 있다.
(결국 주항은 변하지 않고 나머지 항의 조합만 달라진다)
3-5. 합의 곱 표현식의 간략화
우리는 앞서 배웠듯이 정준 형식(Canonical form)은 곱의 합, 합의 곱의 두가지 방식으로 표현될 수 있다.
우리는 지금까지 맵을 이용하여 유도한 최소화 부울 함수는 곱의 합(sum of products) 의 형태로 구해냈다. (최소항)
그렇다면 합의 곱(product of sums)의 형태로도 나타낼 수 있다는 것이다. (보수의 이용)
합의 곱 형식으로 최소화된 함수식을 얻기 위한 과정은 부울 함수의 기본 성질을 따르면 된다.
맵의 네모 칸에서 1이 표시된 곳은 함수의 최소항을 나타내는 부분 이므로
표준 곱의 합 함수에 나타나지 않는 최소항들은 해당 함수의 보수(complement)를 나타낸다. (1이 없는 빈 칸)
비어있는 네모 칸에 0을 채워넣고 그들끼리 묶어서 배열한다면 최대항을 이용해 합의 곱 형식으로 나타낼 수 있다.
그러나 이것은 함수의 보수(F')에 대한 식을 구한 것이란 것을 알아야 한다.
우리가 원하는 함수 F의 합의 곱 형식을 구해내기 위해선. 우리가 윗 방법으로 구해낸 조합의 보수를 취해주어야 한다.
이렇게 결과적으로 우리는 곱의 합 / 합의 곱 이라는 두가지 방식으로 최소화(간략화)할 수 있게 되었다.
(표준형식의 두가지 종류중 하나의 2-level 구현이 가능)
※ 만약 주어진 함수가 정준형식 중 최대항의 곱으로 나타나 있다면. 어떻게 K-map을 사용해야 하는가?
앞서 배웠듯이. 정준 형식(Canonical form) 은 최소항의 합 / 최대항의 곱 의 두가지 형태가 존재하고.
표준형식 (Standard form) 은 곱의 합 / 합의 곱 의 두가지 형태가 존재하는 것을 알고있다.
이 형식들 사이에서는 우리가 자유롭게 다른 형식으로 변환시킬 수 있다. (어떻게??)
우리는 최대항으로 주어졌다고 해서 최소항의 기준에서 K-map을 하던 방식과 달라지지 않는다.
단, K-map을 만들어 낼 때 최대항을 이용했으므로. 원래 1을 쓰던 칸에다가 0을 사용하면 되는 것이다.
(최대항은 0이 나오도록 만들어진 항이므로)
이후 빈 칸에 1을 모두 기입하게 되면 우리가 최소항에서 보수를 이용해 곱의 합/ 합의 곱을 변환했던 첫번째 조건과 동일해진다. (우리가 이제부터 무엇으로 바꾸어 낼 지 선택하면 된다)
그 이후 묶어주는 방식은 앞서 배운것과 동일하게 주항의 기준과 패턴을 이용해서 나타내면 된다.