드모르간 법칙의 실제 활용: NAND 전용 회로 설계

요약: 드모르간의 두 항등식, 즉 $\overline{A \cdot B} = \overline{A} + \overline{B}$ 및 $\overline{A + B} = \overline{A} \cdot \overline{B}$를 사용하면 반전을 분배하면서 AND를 OR로(또는 그 반대로) 바꿀 수 있습니다. 실질적인 이점은 모든 논리 함수를 NAND 전용 또는 NOR 전용 형태로 구현할 수 있다는 것이며, 이는 CMOS 칩 설계자와 FPGA 합성기가 정확히 수행하는 작업입니다.

드모르간의 두 항등식, 즉 $\overline{A \cdot B} = \overline{A} + \overline{B}$ 및 $\overline{A + B} = \overline{A} \cdot \overline{B}$는 외우기 쉽습니다. 더 어려운 질문은 현업 엔지니어가 실제로 이를 어떻게 활용하느냐입니다. 그 답은 CMOS 트랜지스터 수준 설계, FPGA 합성, NAND 전용 및 NOR 전용 구현, 다단 회로 최적화에 걸쳐 있습니다.

이 글은 실제 설계 상황에서 드모르간 법칙을 활용하는 데 초점을 맞춥니다. 실제 회로에서 게이트 수를 어떻게 줄이는지, 모든 논리를 NAND 전용 또는 NOR 전용 형태로 어떻게 구현하는지, 그리고 시뮬레이터가 등가성을 어떻게 분명하게 보여 주는지를 살펴봅니다.

빠른 복습: 두 법칙

참고를 위해 드모르간의 두 항등식을 살펴보겠습니다.

이는 $n$개의 변수로 일반화됩니다.

NAND 게이트 동작 살펴보기

활용 1: NAND 전용 구현으로 변환하기

정적 CMOS에서 2입력 NAND 게이트는 트랜지스터 네 개를 사용하며, 비반전 AND는 NAND 뒤에 인버터를 연결해 구현할 수 있습니다. 따라서 NAND는 유용한 기본 소자이지만, 설계 전체를 NAND 게이트만으로 구성해야 한다는 뜻은 아닙니다. ASIC 합성은 특성화된 라이브러리에서 사용할 수 있는 셀로 논리를 매핑하고, FPGA 합성은 주로 LUT와 전용 리소스로 매핑합니다.

변환 과정

모든 곱의 합(SOP) 식은 두 단계로 NAND-NAND 형태로 변환할 수 있습니다.

1. SOP에서 시작합니다: $Y = AB + CD$
2. 이중 부정을 적용합니다: $Y = \overline{\overline{AB + CD}}$
3. 바깥쪽 막대에 드모르간 법칙을 적용합니다: $Y = \overline{\overline{AB} \cdot \overline{CD}}$

그 결과는 2단 NAND-NAND 회로입니다. 첫 번째 NAND 단계가 $\overline{AB}$ 및 $\overline{CD}$를 계산하고, 두 번째 NAND 단계가 이를 결합합니다.

풀이 예제: 3변수 함수

$Y = A\overline{B}C + \overline{A}BC$를 NAND 전용으로 변환해 보겠습니다.

1단계: 이중 부정을 적용합니다: $Y = \overline{\overline{A\overline{B}C + \overline{A}BC}}$

2단계: 바깥쪽 막대에 드모르간 법칙을 적용합니다.

구현:

• 게이트 1(NAND): 입력은 $A$, $\overline{B}$, $C$이며 출력은 $\overline{A\overline{B}C}$입니다.
• 게이트 2(NAND): 입력은 $\overline{A}$, $B$, $C$이며 출력은 $\overline{\overline{A}BC}$입니다.
• 게이트 3(NAND): 게이트 1과 게이트 2의 출력을 입력으로 받아 $Y$를 출력합니다.

$\overline{A}$와 $\overline{B}$에 필요한 NOT 게이트는 NAND 게이트의 두 입력을 서로 연결하여 구현합니다.

이 회로도의 게이트 수: NAND 게이트 3개 + NAND 기반 인버터 2개 = NAND 게이트 5개입니다. 직접 그린 AND-OR 회로도 역시 게이트 다섯 개를 사용하지만 게이트 종류는 세 가지입니다. 단일 게이트 종류로 구성하면 패키지 재고가 제한된 상황에서 편리합니다. 실리콘 구현은 대상 라이브러리의 면적, 지연 및 전력 데이터를 기준으로 평가해야 합니다.

NAND 범용 논리 템플릿 사용해 보기

활용 2: NOR 전용 구현으로 변환하기

NAND-NAND 변환의 쌍대 방식은 곱의 합(POS) 식에 적용되며 NOR-NOR 회로를 만들어 냅니다.

변환 과정

1. POS에서 시작합니다: $Y = (A + B)(C + D)$
2. 이중 부정을 적용합니다: $Y = \overline{\overline{(A+B)(C+D)}}$
3. 바깥쪽 막대에 드모르간 법칙을 적용합니다: $Y = \overline{\overline{(A+B)} + \overline{(C+D)}}$

그 결과는 2단 NOR-NOR 회로입니다. 첫 번째 NOR 단계가 $\overline{A+B}$ 및 $\overline{C+D}$를 계산하고, 두 번째 NOR 단계가 이를 결합합니다.

NOR 게이트는 곱의 합 논리나 적합한 복합 셀을 제공하는 라이브러리에 자연스럽게 부합할 수 있습니다. NAND, NOR 또는 혼합 게이트 형식 중 무엇을 선택할지는 팬인, 구동 능력, 부하, 배치 및 대상 기술에 따라 달라지며, 어느 한 형식이 항상 우선하는 것은 아닙니다.

활용 3: 다단 회로 최적화

실제 회로는 두 단계로 제한되는 경우가 드뭅니다. 반전이 곳곳에 흩어진 다단 논리를 만났을 때 드모르간 법칙을 사용하면 회로 전체에서 “버블을 밀어” 중복 반전을 상쇄하고 게이트 수를 줄일 수 있습니다.

풀이 예제: 4게이트 식 단순화

다음을 단순화합니다: $Y = \overline{\overline{A \cdot B} + \overline{C \cdot D}}$

1단계 — 바깥쪽 막대에 드모르간 법칙을 적용합니다(식 내부는 두 항의 합입니다).

2단계 — 이중 부정을 상쇄합니다.

처음에는 NAND 게이트 2개, NOR 게이트 1개, 출력 인버터 1개가 필요한 복잡한 식처럼 보였습니다. 드모르간 법칙을 두 번 적용하면 단일 4입력 AND 게이트로 줄어듭니다.

풀이 예제: 3단 회로에서 버블 밀기

주어진 식: $Y = \overline{\overline{(A + B)} \cdot \overline{(C + D)} \cdot E}$

1단계 — 바깥쪽 NAND에 드모르간 법칙을 적용합니다.

2단계 — 이중 부정을 상쇄합니다.

불 기호 수준에서 이 식은 반전 입력 하나를 갖는 5입력 OR 게이트 하나로 축약됩니다. 실제 하드웨어에서 면적, 속도 또는 전력이 개선되는지는 사용 가능한 셀이나 LUT, 팬인, 라우팅 및 부하에 따라 달라집니다.

활용 4: FPGA 합성 및 기술 매핑

Verilog 또는 VHDL을 작성할 때 합성 도구는 코드를 AND 및 OR 게이트로 직접 번역하지 않습니다. 대신 기술 매핑을 수행하여 논리를 대상 FPGA 또는 ASIC 라이브러리에서 사용할 수 있는 특정 프리미티브로 변환합니다. 드모르간 법칙은 이 과정의 핵심 변환입니다.

합성 도구가 드모르간 법칙을 사용하는 방법

1. LUT 매핑: FPGA의 룩업 테이블(LUT)은 입력 용량 범위 내에서 임의의 불 함수를 구현할 수 있습니다. 합성 도구는 논리를 단순화하고 인수분해한 뒤 함수를 LUT에 패킹하며, 드모르간 변환은 이 과정에서 사용할 수 있는 등가 변환 중 하나입니다.

2. 극성 최적화: 많은 라이브러리 게이트는 반전 출력이나 반전 입력을 기본으로 제공합니다. 버블 푸싱을 통해 유용한 반전 신호를 그대로 유지하면 별도의 인버터 추가를 피할 수 있습니다.

3. 임계 경로 최적화: 특성화된 라이브러리와 배치 결과가 더 나은 타이밍을 예측하는 경우, 도구는 등가 NAND, NOR 또는 복합 셀 형식을 선택할 수 있습니다. 최적의 형식은 대상 기술에 따라 달라집니다.

구체적인 Verilog 예제

다음 RTL 코드를 살펴보겠습니다.

assign y = ~(a & b) | ~(c & d);

합성 도구는 $\overline{AB} + \overline{CD}=\overline{ABCD}$를 인식합니다. 별도의 게이트나 복합 라이브러리 셀을 사용할 수 있으며, 입력 용량이 허용되면 FPGA LUT 하나로 구현할 수도 있습니다. RTL은 동작을 규정할 뿐이며, 실제 구현 면적과 타이밍은 선택한 대상의 보고서를 통해 확인해야 합니다.

활용 5: 레거시 하드웨어와 게이트 대체

빈티지 하드웨어를 다루거나 부품 재고가 제한되어 있다면 드모르간 법칙은 게이트 대체를 위한 핵심 도구입니다.

범용 게이트 구성

NAND 게이트만으로 다른 모든 게이트를 만들 수 있습니다.

OR 구성은 드모르간 법칙에서 바로 나옵니다. $A + B = \overline{\overline{A} \cdot \overline{B}}$이며, 이는 NAND(NOT A, NOT B)입니다.

부품 재고가 제한된 상황에서도 이 구성은 유용합니다. 74LS00의 사용 가능한 섹션만 있다면 NAND 섹션 세 개로 OR 기능 하나를 구현할 수 있습니다. 단, 대체 회로가 원래 회로의 전압, 팬아웃, 타이밍, 전력 및 미사용 입력 처리 요구 사항을 충족해야 합니다.

오실로스코프로 검증하기

DigiSim에서 드모르간 변환을 구성할 때 원래 회로와 변환한 회로의 출력을 비교합니다. OSCILLOSCOPE_8CH를 사용하면 두 출력과 해당 입력 신호를 함께 표시할 수 있습니다.

안정 상태의 모든 입력 조합을 빠짐없이 검사하면 진리표를 검증할 수 있습니다. 입력 전이를 구동하면 시뮬레이터의 전파 지연 모델이 나타내는 차이도 관찰할 수 있지만, 이것만으로 특정 물리 구현의 타이밍을 입증할 수는 없습니다.

논리적으로 등가인 회로가 반드시 타이밍까지 등가인 것은 아닙니다. NAND-NAND와 AND-OR 회로도가 모두 두 논리 단계로 구성되더라도 셀 지연, 입력 슬루, 팬아웃, 부하 및 라우팅은 서로 다를 수 있습니다. 반전 단계가 추가되면 경로가 길어질 수 있지만, 물리적 속도에 관한 판단은 대상별 타이밍 분석을 통해서만 뒷받침할 수 있습니다.

드모르간 법칙 실제 적용 시 흔한 함정

불완전한 뒤집기

학습자는 흔히 각 항을 반전해야 한다는 것은 기억하지만 연산자를 뒤집는 것을 잊습니다. 그러면 $\overline{A \cdot B} = \overline{A} \cdot \overline{B}$라는 잘못된 식이 나옵니다. 항상 AND를 OR로, OR를 AND로 바꾸세요.

NAND/NOR 회로의 부동 입력

DigiSim에서 NAND 전용 회로를 구성할 때는 관련된 모든 입력에 정의된 신호원을 연결해야 합니다. 실제 CMOS 입력을 부동 상태로 두면 예측할 수 없는 전압이 형성되고 결합 잡음에 따라 전환되며 공급 전류가 증가할 수 있습니다. 물리 소자의 미사용 입력은 데이터시트에 따라 적절한 유효 논리 레벨에 연결하고, 회로도 실습에서는 이에 해당하는 CONSTANT 신호원을 사용해야 합니다.

논리적 등가성과 타이밍 등가성 혼동하기

진리표가 같은 두 회로라도 전파 지연은 매우 다를 수 있습니다. 드모르간 법칙으로 회로를 변환할 때는 언제나 변환이 게이트 단계를 추가하거나 제거하는지 확인하세요.

도전 과제: 다단 최적화

다음 식을 최소 게이트 수로 줄여 보세요.

힌트: 바깥쪽 NAND에 드모르간 법칙을 적용하고 이중 부정을 상쇄한 뒤 무엇이 남는지 확인하세요. (해답: $Y = (A + \overline{B}) + (\overline{A} + B) = A + \overline{A} + B + \overline{B} = 1$. 이 식 전체는 항상 참이므로 게이트가 전혀 필요 없습니다.)

이는 강력한 예시입니다. 드모르간 법칙을 보수 법칙과 결합하면 때때로 회로 전체를 없앨 수 있습니다.

카르노 맵에서 같은 단순화를 시각적으로 접근해 보거나, 부울 대수 기초를 다시 살펴보세요. 이러한 변환 중 하나를 직접 배선하려면 NAND 컴포넌트 참조를 여세요.