카르노 맵 (Karnaugh Map)
쉽게 풀면
논리 함수를 간단히 줄이려면 하나의 변수만 다른 두 항을 찾아 묶어야 하는데, 진리표만 보아서는 그런 짝을 찾기가 번거롭습니다. 카르노 맵은 이웃한 칸이 항상 한 변수만 다르도록 칸을 배열한 표여서, 1이 적힌 칸들이 몰려 있는 덩어리를 눈으로 묶기만 하면 곧바로 간략화된 식이 나옵니다. 묶음은 2의 거듭제곱 크기여야 하고 클수록 식이 간단해집니다.
왜 중요한가
디지털 논리를 배우는 단계에서 간략화의 원리를 직관적으로 이해시키는 표준 도구이며, 게이트 수를 줄이는 일이 곧 면적과 지연을 줄이는 일이라는 감각을 길러 줍니다. 실무의 대규모 설계는 자동화된 논리합성 도구가 맡지만, 도구가 내부에서 수행하는 최소화의 개념적 기반이 여기에 있습니다.
논문에서는 이렇게 쓰입니다
작은 규모의 논리를 손으로 최소화해 회로 지연을 줄인 사례입니다.
조금 더 깊게 보면
칸의 배열에는 인접한 값이 한 비트만 다른 그레이 부호 순서를 사용하며, 이 덕분에 표의 양 끝도 서로 인접한 것으로 취급됩니다. 1인 칸들을 2, 4, 8개 단위의 직사각형으로 묶되 겹쳐도 무방하며, 각 묶음이 하나의 곱항이 되고 이들을 더하면 간략화된 곱의 합 형태가 나옵니다. 어떤 입력 조합이 실제로는 나타나지 않는 경우를 무관 조건으로 표시하면 묶음을 더 크게 만들 수 있어 식이 더 간단해집니다. 변수가 다섯 개를 넘으면 표가 복잡해져 실용성이 떨어지므로, 그 이상은 퀸-맥클러스키 방식이나 컴퓨터 알고리즘을 씁니다.
주의할 점
카르노 맵으로 얻은 최소 곱의 합이 반드시 최소 게이트 수의 회로가 되는 것은 아니며, 다단 논리나 공유 항을 고려하면 다른 구조가 더 나을 수 있습니다. 또한 간략화 과정에서 글리치를 유발하는 위험 조건이 생길 수 있어, 비동기 회로에서는 일부러 중복 항을 남기기도 합니다.