Gate-level minimization(게이트 수준 최소화)은 디지털 회로를 보다 효율적으로 설계하기 위해 부울 함수를 간소화하는 과정이다. 이를 위한 대표적인 방법 중 하나가 Karnaugh map(K-map, 카노 맵)이며, 이는 여러 개의 네모 칸으로 이루어진 표로 각 칸이 특정 입력 조합에서 출력이 1이 되는 최소항(minterm)을 나타낸다. K-map은 부울 함수를 간단한 형태로 정리하는 데 유용하며, 곱의 합(SOP) 또는 합의 곱(POS) 형태로 표현될 수 있다.
K-map의 중요한 특징 중 하나는 행과 열이 Gray 코드 방식으로 배열된다는 점이다. Gray 코드란 인접한 두 행 또는 열에서 오직 하나의 비트만 변하는 방식으로 번호를 매기는 방법이다. 이를 통해 논리식을 보다 직관적으로 묶고 최소화할 수 있다. 예를 들어, 두 개의 입력 변수 A, B를 가지는 함수 f(A,B)=A′B+AB가 있다고 가정하면, 이를 2×2 크기의 K-map으로 나타낼 수 있다. 이 K-map에서는 연속된 1을 하나의 그룹으로 묶어 논리식을 단순화할 수 있으며, 최종적으로 f(A, B) = B로 정리할 수 있다. 이처럼 K-map을 활용하면 논리 회로를 보다 간단하게 설계할 수 있으며, 불필요한 논리 게이트를 줄여 하드웨어 구현을 최적화할 수 있다.
카르노 맵을 그리는 기본적인 방법
- 변수 개수에 따른 격자 설정
- 2변수: 2×2
- 3변수: 2×4
- 4변수: 4×4
- 진리표를 보고 1이 있는 위치를 카노 맵에 채운다
- 각 칸은 해당하는 변수 조합을 나타낸다.
- Gray 코드(한 번에 한 비트만 변하는 방식)로 칸을 배치한다.
- 1들을 최대한 큰 그룹으로 묶는다
- 1, 2, 4, 8개 등 2의 거듭제곱 단위로 묶는다.
- 직사각형 또는 정사각형 형태로 묶어야 하며, 대각선으로는 묶을 수 없다.
- 겹쳐도 상관없다.
- 묶은 그룹을 논리식으로 변환한다
- 그룹에서 변하지 않는 변수를 찾는다.
- AND 연산으로 묶어 표현하고 OR 연산으로 결합한다.