Computer Scinece/Computer Architecture & OS

Digital Design [2] : 게이트 레벨 최소화 (Gate-Level Minimization)

JaehyeonByun 2025. 3. 20. 12:02

 

 

1. 게이트 레벨 최소화 (Gate-Level Minimization)

karnaugh maps

 

게이트 레벨 최적화란 디지털 회로를 구성하는 부울 함수(Boolean Function)를 최소화하여 가장 효율적인 게이트 구조를 찾는 과정을 말한다. 이를 위해 사용되는 대표적인 방법이 카노 맵(Karnaugh Map, K-Map)이며, 이 맵은 각 칸이 하나의 최소항(minterm)에 대응된다. K-Map은 일반적으로 2, 3, 4변수의 경우가 많이 쓰이며, 맵의 행과 열은 Gray Code 순서로 정렬되어 인접한 항에서 하나의 비트만 변경되도록 한다. 인접한 1들을 묶어 논리식을 간소화하며, 이때 최소한의 항 개수최소한의 리터럴 수를 가지는 표현이 목표가 된다.

1.1 The Map Method (K-Map을 이용한 간소화 방법)

Karnaugh Map은 각 변수 조합에 대한 함수 출력을 정사각형의 칸에 배치한 것이다. 각 칸은 하나의 최소항(minterm)을 나타내며, 입력이 1이 되는 칸들을 서로 인접한 형태로 묶어 간단한 부울 항으로 변환한다. 맵의 행과 열은 Gray Code로 배치되어 있어, 인접한 칸끼리는 단 하나의 비트만 변경된다. 묶을 수 있는 개수에 따라 리터럴 수가 줄어들며,

  • 1칸 묶음은 3리터럴,
  • 2칸 묶음은 2리터럴,
  • 4칸 묶음은 1리터럴,
  • 8칸 묶음은 상수 1의 함수를 의미한다.

2변수 K-Map

 

두 변수의 K-Map은 총 4칸으로 이루어지며, 각 칸은 x, y의 조합에 따른 출력 값을 나타낸다. 예를 들어, F(x,y) = Σ(0,1)은 x' + y'로 간단히 표현될 수 있다.

 

3변수 K-Map

 

세 변수의 경우 총 8칸이 구성되며, 이들 간의 인접성을 고려하여 묶는다. 예를 들어, F(x,y,z) = Σ(2,3,4,5)의 경우 x’y + xy’로 간략화된다. 이는 m2, m3을 묶어 x’y를 도출하고, m4, m5를 묶어 xy’를 도출한 것이다. 더 나아가 F = Σ(0,2,4,6)과 같은 경우는 x’z’ + xz’로 묶이고, z’(x + x’) = z’가 되므로 최종적으로 F = z’처럼 극단적으로 단순화될 수도 있다.

 

이처럼 K-Map은 시각적 도구를 통해 논리식 간소화를 직관적으로 수행하게 해주며, 특히 변수가 3개 이하일 경우 매우 효과적인 도구로 활용된다.

 

3Four-Variable K-Map (4변수 K-Map)

 

4개의 변수로 이루어진 함수는 총 2⁴ = 16개의 칸을 가진 K-Map으로 표현된다. 이때도 마찬가지로 인접한 1들을 묶어서 간소화를 수행한다. 1, 2, 4, 8, 16개의 인접한 1들을 묶을 수 있으며, 이들은 각각 4, 3, 2, 1, 0개 리터럴을 포함한 항으로 단순화된다. 16개 모두가 1이면 함수는 상수 1이 된다.

 

 주항(Prime Implicant)과 필수 주항(Essential Prime Implicant)

  • 주항은 가능한 가장 많은 인접한 1들을 묶어 얻은 항이다.
  • 필수 주항은 특정 1(minterm)을 유일하게 포함하는 주항으로, 반드시 포함해야 한다.
  • 최종 함수 표현은 모든 필수 주항을 포함하고, 남은 minterm을 포함하기 위한 비필수 주항을 추가하는 방식으로 완성된다.

합의 곱 표현식의 간략화 (Product-of-Sums Simplification)

 

합의 곱(Product of Sums, POS) 형태로 부울 함수를 간소화하려면 먼저 함수의 보수(F′)를 단순화한 다음, 다시 보수를 취하는 방식으로 처리한다. 이 과정은 DeMorgan의 정리에 근거하며, 일반적으로 K-Map을 활용해 수행된다. K-Map 상에서 출력이 1인 부분은 최소항(minterm)을 나타내고, 출력이 0인 칸은 보수 함수 F′의 최소항이 된다. 이를 통해 F′를 곱의 합(SOP) 형태로 단순화하고, 다시 보수를 취해 F를 합의 곱(POS) 형태로 표현하는 것이다.

 

이 방식의 핵심은, F′의 SOP 표현을 DeMorgan 법칙에 따라 보수하면 자동으로 F의 POS 형태가 된다는 점이다. 이 때문에 POS 표현을 직접 구성하는 것이 아니라, 보조적으로 F′를 간단히 만든 후 다시 보수를 취함으로써 POS 형태를 얻는 것이 일반적이다.

예를 들어, F(A, B, C, D) = Σ(0, 1, 2, 5, 8, 9, 10)이라는 함수가 주어졌을 때, 이 함수는 SOP로는 F = B’D’ + B’C’ + A’C’D로 간단화된다. 그러나 POS로 표현하고자 한다면, 먼저 F′ = AB + CD + BD′로 간소화한 뒤, 이를 DeMorgan 정리에 따라 보수하여 F = (A′ + B′)(C′ + D′)(B′ + D)와 같은 합의 곱 표현으로 변환할 수 있다.

 

이와 같은 방식은 논리 회로 구현에서도 구조의 차이를 만든다. 곱의 합(SOP) 표현은 각 항이 AND 게이트로 구성되고, 그 결과를 OR 게이트에 입력하여 출력을 도출한다. 반대로, 합의 곱(POS) 표현은 각 항이 OR 게이트로 구성되고, 그 결과를 AND 게이트에 입력하여 출력을 얻는다. 이 두 방식 모두 두 단계로 구성되므로 이를 2-level implementation이라 한다.  결론적으로, Product-of-Sums 방식은 직접적으로 복잡한 논리합 표현을 만들기보다는, 보수 함수(F′)를 간단하게 만든 후 다시 보수를 취하는 방식으로 효율적으로 간소화하며, 논리 회로의 OR → AND 형태 구현을 위한 중요한 설계 방법이다.

 

더보기

Don't Care

 

디지털 회로에서 다루는 부울 함수 중에는 모든 입력 조합에 대해 출력이 명확히 정의되지 않은 경우가 있다. 이러한 경우의 함수를 불완전 정의 함수(incompletely specified function)라고 하며, 특정 입력에 대해 출력이 0이든 1이든 상관없는 상황Don’t-care 조건이라고 한다. 이런 입력 조합은 회로 설계나 논리 간소화 과정에서 자유롭게 활용할 수 있기 때문에, 함수의 간략화를 더욱 유리하게 만들어주는 도구가 된다.

 

카르노 맵(K-Map)에서는 don’t-care 조건을 가진 칸을 ‘X’로 표시한다. 이 X는 해당 입력 조합에 대해 출력이 꼭 1이거나 0일 필요가 없음을 나타낸다. 설계자는 이 칸을 상황에 따라 1로 간주하여 더 큰 그룹을 만들거나, 필요 없다면 무시할 수 있다. 이 유연성을 통해 더 간단하고 효율적인 논리식으로 최소화할 수 있다.

 

예를 들어, 예제 3.8에서는 함수 F(w, x, y, z) = Σ(1, 3, 7, 11, 15)가 주어지고, don’t-care 조건은 d(w, x, y, z) = Σ(0, 2, 5)로 주어진다. 즉, 총 6개의 출력이 1로 정의되어 있고, 3개의 don’t-care가 제공된다. K-map에서 이 don’t-care 칸들을 포함하여 그룹핑하면 다양한 최소 표현이 가능하다. 실제로 이 문제의 해답은 F = yz + w’x’ 또는 F = yz + w’z로 간소화된다. 이처럼 don’t-care를 활용하면 서로 다른 최소 표현이 존재할 수도 있으며, 이는 회로 설계자가 선택할 수 있는 유연성을 제공한다.

연습문제 3.9에서는 함수 F(w, x, y, z) = Σ(4, 5, 6, 7, 12)와 don’t-care 조건 d(w, x, y, z) = Σ(0, 8, 13)이 주어진다. 여기서도 don’t-care 칸들을 활용하여 더 큰 인접 그룹을 만들면, F = xy’ + xw라는 간단한 표현을 얻을 수 있다. 이는 원래 함수만 가지고 최소화를 수행할 때보다 훨씬 간단한 논리식이다.

 

1.2 NAND와 NOR 게이트를 이용한 구현 (NAND and NOR Implementation)

디지털 회로는 기본적으로 AND, OR, NOT과 같은 논리 게이트를 조합하여 설계된다. 그러나 실제 하드웨어에서는 NAND 게이트와 NOR 게이트만을 사용하여 회로를 구성하는 것이 일반적이다. 이는 두 게이트가 범용 게이트(Universal Gate)로, 모든 논리 연산을 대체할 수 있기 때문이다. 또한 전자적으로 구현이 쉽고 비용이 저렴하며, 다양한 디지털 IC에서 표준으로 사용되고 있기 때문이다.

1.2.1 NAND 게이트 기반 회로 구현

NAND는 AND 연산 후에 NOT을 적용한 게이트이다. 수식으로 표현하면 A NAND B = (A · B)' 이다. NAND 게이트는 단독으로 NOT, AND, OR 연산까지 흉내 낼 수 있기 때문에 범용 게이트로 간주된다. NAND 회로로 구현하려면 먼저 논리식을 곱의 합(SOP: Sum of Products) 형태로 정리해야 한다. 그 후, 다음과 같은 절차를 따른다.

  1. 각 곱 항(Product term)을 NAND로 구현한다.
    예를 들어 AB라는 항은, NAND 게이트로는 (A · B)'로 구현되며, 원래 AB 값을 얻기 위해선 두 번 NAND를 적용해야 한다. 즉, ((A · B)')'로 표현한다.
  2. 모든 곱 항을 OR로 연결하는 부분을 NAND로 바꾼다.
    OR 연산은 DeMorgan 정리에 따라 NAND 게이트 2단계를 사용하여 표현할 수 있다. A + B = ((A') · (B'))' 이므로, 각 항을 먼저 NAND로 부정하고 다시 NAND로 묶으면 된다.
  3. 단일 항(single literal)의 경우 보완적인 처리가 필요하다.
    항이 하나만 있는 경우, 만약 보수가 필요한 항이면 그대로 연결하고, 아닌 경우에는 NAND 인버터를 한 번 더 써야 한다.

 

다음과 같은 함수가 있다고 하자:

F = AB + CD

이를 NAND 게이트만으로 구현하면 다음과 같다:

  • AB는 (A · B)' → 다시 부정해서 ((A · B)')'
  • CD도 동일하게 ((C · D)')'
  • 전체 함수는 AB + CD → ((AB)' · (CD)')' 이므로 NAND 게이트 세 개로 표현 가능하다.

NAND 게이트만으로 논리 회로를 구성하려면 먼저 함수를 간략화하여 곱의 합(SOP) 형태로 표현해야 한다. 이후 각 곱 항(term)이 두 개 이상의 리터럴을 포함할 경우, 이를 NAND 게이트로 구현하여 1단계 회로를 구성한다. 그런 다음 이 출력들을 하나의 NAND 게이트로 연결하여 2단계 회로를 완성한다. 단일 리터럴만 있는 항은 인버터(NAND NOT)로 처리해야 하며, 만약 해당 리터럴이 이미 보수(complement) 형태라면 그대로 2단계 NAND의 입력으로 연결해도 된다.

1.2.2 NOR 게이트 기반 회로 구현

NOR는 OR 연산 후에 NOT을 적용한 게이트이다. 수식으로 표현하면 A NOR B = (A + B)' 이다. 이 또한 NAND처럼 하나의 게이트로 AND, OR, NOT을 모두 표현할 수 있어서 범용 게이트로 분류된다. NOR 회로로 구현할 경우, 논리식을 합의 곱(POS: Product of Sums) 형태로 바꾸어야 한다. 그 후 다음 절차를 따른다.

  1. 각 합 항(Sum term)을 NOR 게이트로 구현한다.
    예를 들어 A + B는, NOR 게이트로 (A + B)'로 표현되고, 원래 A + B 값을 얻기 위해선 이를 두 번 부정해야 한다. ((A + B)')' 형태이다.
  2. 곱 부분(AND 연산)을 NOR 게이트로 바꾼다.
    AND 연산은 DeMorgan 정리에 따라 A · B = ((A') + (B'))'로 바꿀 수 있고, 이는 두 단계 NOR로 구현 가능하다.
  3. 보수 처리가 필요한 경우에는 NOR 인버터를 사용한다.

3. 예시로 보는 NOR 회로 구현

다음과 같은 함수가 있다고 하자:

F = (A + B)(C + D)

 

이를 NOR 게이트만으로 구현하면 다음과 같다:

  • A + B는 (A + B)'
  • C + D는 (C + D)'
  • 두 결과를 곱하면 (A + B)(C + D) → ((A + B)' + (C + D)')' 로 변환되므로, 총 3개의 NOR 게이트로 표현이 가능하다.
더보기

멀티레벨 NAND 회로를 구현하려면 먼저 주어진 부울 함수를 AND, OR, NOT 연산으로 표현하고 이를 일반적인 AND 및 OR 게이트 회로로 구성해야 한다. 그 후 필요에 따라 전체 회로를 NAND 게이트만을 사용한 구조로 변환할 수 있다. 이를 위해 모든 AND 게이트는 AND-반전 기호(AND-invert)로, 모든 OR 게이트는 반전-OR 기호(invert-OR)로 바꾸어 NAND 구조로 전환한다. 회로 내에 있는 ‘버블’(반전 표시 원형 기호)은 입력 또는 출력의 보수를 나타내며, 만약 한 선상에서 다른 버블과 보상되지 않는 버블이 있다면, 해당 지점에 1입력 NAND 게이트(인버터)를 삽입하거나 입력을 보수형으로 바꾸어 처리한다.

 

한편 NOR 연산은 NAND 연산의 쌍대(dual) 개념으로, NOR 게이트 또한 범용 게이트로서 어떤 부울 함수도 구현할 수 있다. OR-invert 기호는 OR 연산 후 보수를 적용한 것으로 NOR 연산을 나타내며, invert-AND 기호는 각각의 입력을 보수한 뒤 AND 연산을 수행한 것으로 역시 NOR와 동일한 기능을 수행한다. 이 두 가지 NOR 기호는 DeMorgan 법칙에 따라 논리적으로 동일하다.

 

NOR 게이트만으로 논리식을 2단계로 구현하려면 함수는 반드시 합의 곱(POS: Product of Sums) 형태로 간략화되어야 한다. 그런 다음 OR 게이트는 OR-invert 기호의 NOR로, AND 게이트는 invert-AND 기호의 NOR로 바꾸어 회로를 구성한다. 예를 들어 F = (A + B)(C + D)E와 같은 논리식은 NOR 게이트를 사용하여 단계별로 변환해 구현할 수 있으며, 복잡한 논리식인 F = (AB’ + A’B)(C + D’)도 동일한 방식으로 NOR 게이트만으로 회로를 완성할 수 있다.

디지털 회로에서 두 단계(2-level)로 구성된 구현 방식은 첫 번째 단계와 두 번째 단계에 어떤 게이트를 사용하는지에 따라 총 16가지 조합이 가능하다. 이 중 일부 조합은 실제로는 한 단계 연산으로 축소되는 퇴화 형태(degenerate form)로, 예를 들어 AND-AND, OR-OR, NAND-OR 등과 같은 조합은 일반적으로 사용되지 않는다. 반면 AND-OR, OR-AND, NAND-NAND, NOR-NOR 등 8가지 비퇴화(non-degenerate) 형태는 실제 회로 설계에서 유용하게 사용되며, 각각 곱의 합(SOP) 또는 합의 곱(POS) 형태의 논리식을 구현할 수 있다.

이 중에서도 AND-OR-INVERT 구현은 곱의 합 형태의 함수에서 보수 F'를 먼저 SOP로 단순화한 다음, 이를 AND-OR 구조로 구성하고 마지막에 출력을 반전시켜 원래 함수 F를 얻는 방식이다. 예를 들어 F = (AB + CD + E)’는 AND-OR 구조로 F'를 구성한 후, 전체 회로에 인버트를 적용하여 F를 완성하는 형태이다.

 

반대로 OR-AND-INVERT 구현은 합의 곱 형태에서 F'를 POS로 단순화한 뒤, OR-AND 구조로 표현하고 마지막에 출력을 보수 처리하여 원래 함수 F를 얻는다. 예를 들어 F = [(A + B)(C + D)E]’는 F'를 OR-AND 구조로 구성한 후, 인버트 출력을 통해 F로 변환하는 방식이다.

 

이러한 AND-OR-INVERT와 OR-AND-INVERT는 각각 NAND 기반 회로나 NOR 기반 회로에서 자주 쓰이는 패턴으로, 복잡한 논리식을 효과적으로 단순화하고 구현할 수 있는 방법이다. 예시로 주어진 F = (x’y + xy’ + z)’는 AND-OR-INVERT 구조를 따르며, F = [(x + y + z)(x’ + y’ + z)]’는 OR-AND-INVERT 방식으로 구현할 수 있다. 이러한 방식은 회로의 계층 구조를 명확히 하고, NAND 또는 NOR 게이트 기반 회로 설계의 기반이 되는 개념이다.

 

 

 

배타적 논리합(XOR) 연산은 두 입력이 서로 다를 때 출력이 1이 되는 연산으로, x ⊕ y = xy' + x'y의 형태로 표현된다. 이 연산은 산술 연산, 오류 검출 및 수정 회로에 자주 사용되며, 입력 값 중 1의 개수가 홀수일 때 출력이 1이 되는 특징 때문에 "홀수 함수(Odd Function)"로 불린다. 이에 반해 **배타적 부정 논리합(XNOR)**은 XOR의 보수로, 두 입력이 같을 때 출력이 1이 되는 "짝수 함수(Even Function)"이다. 수식으로는 (x ⊕ y)' = (xy' + x'y)' 로 표현된다.

 

XOR 연산은 다양한 성질을 가지며, 예를 들어 x ⊕ 0 = x, x ⊕ 1 = x', x ⊕ x = 0, x ⊕ x' = 1, x ⊕ y' = x' ⊕ y 등과 같이 변형 활용이 가능하다. 세 변수 XOR의 예로 A ⊕ B ⊕ C는 (AB' + A'B)C' + (AB + A'B')C로 확장되며, 이는 진리표상으로 Σ(1, 2, 4, 7)의 항과 일치한다. 이처럼 XOR은 다수 입력에서도 홀수 개의 1이 있을 경우 출력이 1이 되도록 일반화할 수 있다.

XOR의 보수인 XNOR 게이트를 출력단에 사용하면 홀수 함수의 보수를 취하여 짝수 함수로 변환할 수 있다. 이러한 관계는 짝수/홀수 판단 및 패리티 검출에서 특히 유용하다.

 

패리티 생성기와 검사기는 XOR 연산을 이용하여 전송 데이터의 오류 여부를 판단하는 회로이다. 짝수 패리티 방식을 사용하는 경우, 전체 1의 개수가 짝수가 되어야 하므로, 보조 비트인 패리티 비트(P)는 x ⊕ y ⊕ z와 같이 XOR로 생성된다. 검사기에서는 이 패리티 비트를 포함한 전체 입력을 다시 XOR하여 출력 플래그 C를 계산하고, C가 1이면 오류가 발생한 것으로 판단한다. 동일한 XOR 회로를 생성과 검사에 재사용할 수 있으며, 이 구조는 데이터 전송의 신뢰성을 높이는 데 효과적이다. XOR 논리는 홀수 또는 짝수 개의 1을 정확히 감지할 수 있기 때문에, 패리티 기반의 에러 검출에 이상적인 구조이다.

 

HDL(Hardware Description Language)은 디지털 회로를 설계하고 모델링할 때 사용하는 텍스트 기반 언어이다. 복잡하고 대규모 회로는 수작업으로 설계하기 어렵기 때문에, HDL을 사용하면 설계 비용을 절감하고, 개발 속도를 높이며, 오류 가능성을 줄일 수 있다. HDL을 이용한 설계 흐름은 설계 기능을 논리식, 진리표, 동작 모델 등으로 기술하는 설계 엔트리 단계에서 시작하여, 제작 전에 동작을 검증하는 논리 시뮬레이션, 물리적 구현을 위한 게이트 수준의 회로망으로 변환하는 논리 합성, 회로의 속도 만족 여부를 확인하는 타이밍 검증, 제조 결함을 미리 확인하는 결함 시뮬레이션의 순서로 진행된다. 이러한 과정을 통해 복잡한 디지털 시스템을 효율적이고 유연하며 신뢰성 있게 설계할 수 있다.

 

댓글수0