1. 카르노 맵에 대해
앞서 논리회로 설계의 과정에서 논리식의 간소화
과정을 거쳤다. 이 과정은 꼭 필요하지만 여러가지의 불 대수 법칙을 알고 있어야 하고 변수의 조합에
따라 상당한 시간을 소요하게 된다. 이러한 간소화 과정을 도식화하여 간단명료하게 할 방법으로써 1953년에 모리스 카르노(Maurice
Karnaugh)가 발표한 카르노 맵(Karnaugh map)을 주로 사용한다.
이 카르노 맵은 2차원의 표로 나타내며 입력의 동일항끼리 인접하게
배치하여 묶는 것으로 간소화가 진행된다. 불 대수에서 필산으로 수 분이 걸리는 간소화도 카르노 맵에서
정리하면 10초 전후로 끝낼 정도로 강력하지만 2차원의 표현상
입력이 4개로 제한된다는 한계도 있다. 이러한 카르노 맵의
사용법과 예시를 살펴본다.
2. 2입력 카르노 맵
2입력 카르노 맵은 불 대수의 간소화쪽이 간단한 이유로 잘 쓰이지는 않지만 카르노 맵을 이해하고자 할 때 접근하기에 좋다.
두 개의 입력에 대한 경우의 수를 확인하기 위해 2개의
축에 입력을 기입하고 좌표상 교차하는 모든 칸이 된다. 각 입력은 ‘0’과
‘1’ 두 가지가 있으므로 2×2행렬의 형태로 경우의 수가 4가지임을 알 수 있다. 2진수의 10진수 변환과 같이 두 입력을 조합하여 002, 012, 102, 112 순으로
0, 1, 2, 3의 일련번호가 부여된다. 각 칸은 최소항의
형태가 되어있으므로 ‘m(일련번호)’의 표기법을 사용한다.
다음으로 특징을 보면 각 칸에서 인접한 칸과는 하나의 입력에 대해 상보관계에 있다. 즉, 인접한 두 개의 최소항의 논리합으로 입력 중 하나가 제거된다. 인접한 칸을 세로로 합하여 A’＋A＝1, 가로로 합하여 B’＋B＝1가 되는데 이 특성을 사용하여 간소화한다.
두 개의 입력을 하나의 축에 표현할 수도 있는데 m(1)과 m(3)이 인접하도록 동화와 같이 배열을 회전시킨다. 그와 동시에 좌측 끝과 우측 끝인 m(0)와 m(2)는 기존과 같이 서로 인접한 것으로 간주한다. 하나의 둥근 물체에 말아져 끝과 끝이 연결되어 있다고 생각하면 좋다. 최소항의 배열에 맞추어 입력은 002, 012, 112, 102의 순서로 놓는다.
위와 같이 2입력에 대한 카르노 맵이 두 가지로 표현되지만 최종결과는 항상 같아야 하는데 상세한 간소화 순서는 아래와 같다.
카르노 맵에서 만들어진 행렬의 공란의 각각에 진리표나
불 대수의 최소항이 대응된다는 것을 안다. 그러므로 출력에 대응하는 공란에 ‘1’을 기입하는데, 여러 개의 항이 하나의 칸에 겹치게 쓰이더라도
단일법칙 또는 흡수법칙에 따라서 그대로 ‘1’이다. 만약에
불 대수의 결과가 최소항이 아닌 경우, 최소항이 포함된 개수만큼 기입한다. 예를 들어 2입력 카르노 맵에서의 출력항이 A라면 A·B’＋A·B 이므로 ‘1’을 두 개를 쓰는 방식이 된다. 이것은 카르노 맵에서 A＝1인 칸에 모두 기입하는 것과 일치한다. 그 외에 출력이 무관항(don’t care)을 포함하는 경우 ‘X’로 기입하며, 출력이 없는 빈 칸은 자동적으로 ‘0’이 되지만 기입하지 않아도
무관하다.
간소화 결과는 ‘1’이 기입된 칸이 인접한 경우 하나의 묶음으로 처리하고
해당 축의 행렬 값을 읽는다. 인접하여 묶이는 칸은 상보관계로 간소화되므로 반드시 짝수(2개 또는 4개 등)으로
이루어지며, 가급적 크게 하여 간단하게 만든다. ‘X’가
있을 때는 간소화에 유리한 경우에 출력으로 포함하고 아닌 경우 제외한다. 인접하지 않아 단독으로 ‘1’인 칸이 있다면 그대로 기입한다. 예로 A’B’＋A’·B＋A·B’를 카르노 맵에서 정리해본다.
동화와 같이 2축형 카르노 맵에서 세 개의 항을 배열에 맞추어 ‘1’을 기입하고 가로로 인접하는 항을 A’로, 세로로 인접하는 항을 B’로 묶는다. 두 묶음으로 모든 ‘1’이 정리되었으므로 간소화 결과는 A’＋B’가 된다.
동화와 같이 1축형 카르노 맵에서 세 개의 항과 대응하는 칸마다 ‘1’을 기입하고 인접하는 항끼리 묶는다. 이 때 좌측 끝과 우측 끝이 인접하여 묶인 것을 알 수 있다. 두 묶음으로 표현된 항을 읽어 간소화 결과가 A’＋B’임을 알 수 있다.
3. 3입력 및 4입력 카르노 맵
3입력과 4입력 카르노 맵 모두 1축형으로는 쓰이지 않는다. 2입력 카르노 맵의 1축형과 2축형을 조합한 것으로 생각하면 형태를 짐작할 수 있다.
전반적인 간소화 방법은 2입력 카르노 맵과 동일하므로 각 축에 입력의 개수대로 2진수를 할당, 진리표 또는 논리식의 항을 ‘1’로 기입, 인접한 칸끼리 짝수 단위로 묶기, 묶인 칸의 행렬 읽기 순이 된다.
예시로 무관항을 추가한 4입력 논리식으로 ∑d(0, 13)＋A’·B’·C’·D＋A’·B’·C＋A’·B·C＋A·B’·C을 정리해본다. (d(일련번호)는
‘don’t care’의 머리글자로써 무관항을 의미한다.)
무관항을 ‘X’로 m(0), m(13) 위치에 기입하고 그 외의 항들은 순서대로 찾아 ‘1’로 기입한다. ‘1’이 인접한 칸을 묶어낼 때 2×2형태로 묶으면 여기에 포함되는 2×1 또는 1×2는 모두 흡수되므로 가능한 크게 묶는다. 무관항인 m(0)의 경우 포함하는 것으로 더 큰 묶음으로 만들 수 있으므로 포함시키고 m(13)의 경우 항이 늘어날 뿐 인접한 칸과 묶이지 않으므로 제외시킨다. 그 결과 4×1, 2×2, 2×2형태로 묶어내어 A’·B’＋A’·C＋B’·C으로 정리된다.
4. 5입력 카르노 맵(기본형)
카르노 맵은 5입력부터 3축을 사용하게 되는데 이는 종이나 화면상에 표현하는 데에 어려움이 있다. 가로와 세로축에는 그대로 4입력을 그대로 적용한 채 높이 축 방향으로 2계층(5입력), 4계층(6입력)을 쌓는다고 생각하고 편의상 옆으로 나열하는 것이 일반적이다.
상기한 2입력, 3입력, 4입력과 마찬가지로 출력항을 빈 칸에 기입하고 인접한 가로, 세로 높이방향의 짝수로 묶어 정리한 후 행렬을 읽는다.
5입력 카르노 맵에 한해 그림과 같이 한 칸을 분할하는 방법으로 합치기도 하는데, 여기에 ∑d(0, 1, 17, 21)＋A’·B·C·E＋A·C·D·E＋A’B’CD’E＋A’B’CDE＋A’BC’DE를 정리해본다.
간소화 결과 무관항은 간소화에 영향을 주지 않아 A’CE＋CDE＋A’BDE임을 알 수 있다.
6입력 카르노 맵의 경우 5입력과 동일한 방식으로 4×4인 4개의 행렬을 쌓은 것으로 생각한다. 5입력의 방식에서 양이 늘어날 뿐 방법은 동일하므로 생략한다.
5. 6입력 카르노 맵(수정형)
본래 모리스 카르노가 논문에서 논리를 도식화한 내용은 각 축에서 입력 2개씩을 할당한 것이다. 즉, 2축인
평면에서는 4입력, 3축인 입체에서 6입력 카르노 맵이 최대한도이다. 시간이 지남에 따라 카르노 맵을 기반으로
보다 많은 입력에 대한 간소화 방법을 찾게 되는데 그 핵심은 그레이 부호이다.
그레이 부호는 순서대로 나열할 때 한 자리만 변화하는 특징이 있으므로 연속되는 수 사이에는 항상 상보관계가 존재한다. 4입력의 경우 평면에서 각 축당 2입력으로 기입된 순서는 002, 012, 112, 102으로 그레이 부호의 순서와 일치하고 있다. 여기에 추가하여 한 축에 3입력을 표현하면 0002, 0012, 0112, 0102,
1102, 1112, 1012, 1002의 순서를 예상할 수 있다. 이를 6입력 카르노 맵에 적용하면 아래와 같다.
그레이 부호의 적용으로 인접한 칸들 사이에서 간소화가 끊어지는 부분은 없어졌지만 인접하지 않은 칸들 사이에서 간소화가 생기는 부분에 대해서는 정리과정에서 파악할 수 있어야 한다. 이러한 카르노 맵에 ∑d(9, 15, 27, 43, 45, 47, 57, 61)＋A’·B·C·D·F＋A’·B·C·D’·E’·F＋A’·B’·C·D’·E·F＋A·B·C·D’·E·F＋A·B·C·D·E·F를 정리하면 아래와 같다.
그림과 같이 간소화는 가능하지만 직관적이지 않아 까다롭다. (정리 과정은 생략한다.)
6. 결론
논리식의 간소화에 카르노 맵을 적용하면 불 대수의 간소화 법칙을 몰라도 될 수준이 되지만 두 가지 모두 사용할 수 있는 것이 상황에 따라 유리하다. 실제로는 카르노 맵 또한 전용 계산기가 있으므로 인터넷에서 찾아 쓰도록 한다. 참고로 최대항을 카르노 맵에 적용하는 방법도 있지만 상대적으로 사용하기에 불합리하므로 생략한다.
댓글 없음:
댓글 쓰기