디지털 비교기 해설: 동등성과 크기

동등 비교기와 크기 비교기를 유도하고, 4비트 블록을 캐스케이드하며, 부호 있는 순서와 부호 없는 순서를 구별하고, 큼/같음/작음 출력을 검증합니다.

Denny

2026년 5월 7일약 6분 소요

Chalkboard feature illustration for “디지털 비교기 해설: 동등성과 크기”

요약: 동등성은 비트별 XNOR 결과를 AND 리덕션한 것입니다. 부호 없는 크기는 A와 B가 다른 최상위 위치가 결정합니다. 부호 있는 크기는 부호 비트 또는 뺄셈 플래그를 다르게 해석해야 합니다. 비교기는 폭, 부호 여부, 출력 극성, 캐스케이드 입력이 모두 정의되었을 때에만 정확합니다.

비교기는 두 비트 벡터를 다음 관계로 변환합니다.

A < B, A = B, or A > B

같은 비트도 서로 다르게 해석되면 이 관계는 명확하지 않게 들립니다. 4비트에서 1000은 부호 없이는 8이지만 2의 보수에서는 -8입니다. 0111과 비교하면 부호 없는 해석에서는 더 크고 부호 있는 해석에서는 더 작습니다.

이 안내서는 먼저 동등성을 구성하고, 부호 없는 크기 네트워크를 유도한 뒤, 부호 있는 비교와 블록 캐스케이드가 어떻게 설계를 바꾸는지 보여 줍니다.

계약 정의하기

유효한 $n$ 비트 입력 A와 B에 대해, 3출력 크기 비교기는 흔히 다음을 출력합니다.

G: A가 B보다 큼;
E: A가 B와 같음;
L: A가 B보다 작음.

유효한 2값 입력 모델에서는 다음과 같습니다.

G+E+L=1

그리고 어떤 두 출력도 함께 High가 되지 않습니다. 이 원핫 관계는 완전한 구현과 유효한 논리 레벨에 좌우됩니다. 인에이블 입력, 액티브 로우 인터페이스, 알 수 없는 시뮬레이션 값 또는 잘못 초기화된 캐스케이드 입력은 눈에 보이는 동작을 바꿀 수 있습니다.

동등성은 부호 여부와 무관합니다. 비트 벡터는 일치하거나 일치하지 않을 뿐입니다. 하지만 큼과 작음은 다릅니다.

XNOR로 동등성 만들기

한 위치에 대해 다음과 같습니다.

E_i=A_i\odot B_i=\overline{A_i\oplus B_i}

두 비트가 일치할 때 $E_i=1$ 입니다. 전체 워드는 모든 위치가 일치할 때에만 같습니다.

E=\bigwedge_{i=0}^{n-1}E_i

4비트의 경우 다음과 같습니다.

E=(A_3\odot B_3)(A_2\odot B_2)(A_1\odot B_1)(A_0\odot B_0)

직접 회로도는 4개의 XNOR 게이트 뒤에 AND 리덕션을 둡니다.

이를 “폭과 무관하게 게이트 지연 두 번”이라고 부르고 싶을 수 있습니다. 그러나 이는 팬인이 무한한 부울 수준의 그림일 뿐입니다. 물리 구현은 리덕션을 균형 트리로 구성하거나, 복합 셀로 인수분해하거나, FPGA 룩업 테이블에 매핑할 수 있습니다. 2입력 AND 게이트로는 균형을 이룰 때 리덕션 깊이가 대략 $\lceil\log_2 n\rceil$ 만큼 증가합니다.

부호 없는 크기: 최상위 차이가 이긴다

각 비트에 대해 다음을 정의합니다.

G_i=A_i\overline{B_i}

L_i=\overline{A_i}B_i

E_i=A_i\odot B_i

가장 중요한 서로 다른 위치에서 A가 1이고 B가 0이면 A가 더 크며, 반대이면 A가 더 작습니다. 상위 위치가 모두 일치할 때만 하위 위치가 중요합니다.

4비트 부호 없는 값에서는 다음과 같습니다.

\begin{aligned} G={}&G_3 +E_3G_2 +E_3E_2G_1 +E_3E_2E_1G_0 \end{aligned}

\begin{aligned} L={}&L_3 +E_3L_2 +E_3E_2L_1 +E_3E_2E_1L_0 \end{aligned}

E=E_3E_2E_1E_0

각 G 항은 “모든 상위 비트가 같고, 여기서는 A가 이긴다”를 뜻합니다. 각 L 항은 대칭적인 경우를 뜻합니다.

부호 없는 예제

다음을 비교해 보겠습니다.

A = 0110 (6)
B = 0101 (5)

비트 3과 2는 일치합니다. 비트 1에서 A는 1이고 B는 0이므로 $G_1=1$ 입니다. 더 중요한 차이가 이미 있으므로 비트 0은 관계없습니다.

G=1, E=0, L=0

이는 우선순위 함수이지만, 우선순위는 최상위 데이터 비트에서 최하위 데이터 비트 방향으로 진행됩니다.

재귀 비교기 셀

긴 곱의 합을 전개하는 대신 그룹을 계층적으로 결합할 수 있습니다. H가 상위 그룹을, Lw가 하위 그룹을 나타낸다고 하겠습니다.

G_{\text{all}}=G_H\lor(E_H\land G_{Lw})

E_{\text{all}}=E_H\land E_{Lw}

L_{\text{all}}=L_H\lor(E_H\land L_{Lw})

상위 그룹은 같지 않으면 결정을 내립니다. 같을 때에만 하위 그룹이 통과합니다. 이 결합은 결합 법칙과 유사한 방식으로 선형 캐스케이드나 균형 잡힌 계층 구조를 형성할 수 있습니다.

이 방정식은 4비트 크기 비교기 IC의 확장 입력을 설명합니다. 블록은 로컬 4비트가 동률인 경우를 위해 하위 차수의 G/E/L 결과가 필요합니다.

SN74LS85 블록 캐스케이드

SN74LS85는 두 4비트 스트레이트 바이너리 또는 8-4-2-1 BCD 워드를 비교하며, 3개의 확장 입력과 3개의 관계 출력을 제공합니다.

8비트 비교의 경우 다음과 같이 합니다.

하위 차수 장치가 비트 3:0을 비교합니다.
그 확장 관계를 같음으로 초기화합니다. G_in=0, E_in=1, L_in=0.
그 G/E/L 출력을 상위 차수 장치의 일치하는 확장 입력에 연결합니다.
상위 차수 장치가 비트 7:4를 비교하고 최종 결과를 만듭니다.

상위 절반이 다르면 그 로컬 결정이 하위 입력을 무시합니다. 상위 절반이 같으면 하위 차수 관계가 전파됩니다.

핀 극성, 팬아웃, 전압 및 타이밍은 정확한 데이터시트를 따르세요. 논리 재귀는 전기 설계를 대체하지 않습니다.

부호 있는 2의 보수 비교

동등성은 부호 있는 값과 부호 없는 값에 같은 XNOR 네트워크를 사용합니다. 순서는 다릅니다.

방법 1: 부호 비트를 별도로 해석하기

$s_A=A_{n-1}$ 및 $s_B=B_{n-1}$ 라고 하겠습니다.

$s_A\ne s_B$ 이면 부호 비트가 1인 피연산자가 더 작습니다.
부호가 같으면 나머지 관계의 일반적인 사전식 비교가 올바른 순서를 제공합니다.

편리한 하드웨어 변환은 부호 없는 비교기에 넣기 전에 각 피연산자의 MSB를 반전하는 것입니다.

A'=A\oplus 2^{n-1}

B'=B\oplus 2^{n-1}

부호 비트를 반전하면 2의 보수 순서가 부호 없는 순서로 바이어스됩니다. 4비트에서는 다음과 같습니다.

signed -8 = 1000  → biased 0000
signed -1 = 1111  → biased 0111
signed  0 = 0000  → biased 1000
signed +7 = 0111  → biased 1111

바이어스된 값은 이제 부호 있는 수와 같은 순서로 증가합니다.

방법 2: 빼고 플래그 해석하기

ALU가 $R=A-B$ 를 계산한다면 다음과 같습니다.

E는 Z입니다.
부호 있는 L은 $N\oplus V$ 입니다.
부호 있는 G는 $\overline Z\land\overline{N\oplus V}$ 입니다.

부호 없는 작음은 뺄셈의 캐리 규약에 따라 달라집니다. 원시 캐리 아웃이 빌림 없음을 뜻하면 부호 없는 L은 $\overline C$ 입니다. x86과 같은 빌림 플래그에서는 부호 없는 L이 C입니다. CPU 플래그 가이드가 두 규약을 모두 유도합니다.

부호 있는 작음에 N만 사용하지 마세요. 부호 있는 오버플로는 저장된 결과의 겉보기 부호를 뒤집을 수 있습니다.

서로 반대인 해석의 예

A = 1000
B = 0111

부호 없음:

8 > 7

부호 있는 2의 보수:

-8 < +7

“A>B”라고만 표시된 비교기는 부호 여부를 알기 전까지는 명세가 불충분합니다.

타이밍과 구현 선택

선형 우선순위 체인의 깊이는 폭에 비례합니다. 균형 잡힌 그룹 결합 네트워크는 논리 깊이를 줄일 수 있습니다. 합성은 다음을 사용할 수 있습니다.

넓은 또는 복합 게이트;
프리픽스와 유사한 동등/큼 결합;
ALU에 이미 있는 뺄셈 하드웨어;
FPGA 캐리 체인 또는 룩업 테이블 리소스;
선택한 사용 사례를 위한 조기 종료 구조.

어떤 토폴로지도 보편적으로 가장 빠르지는 않습니다. 전용 비교기는 한 설계에서 산술 결과를 기다리지 않아도 되지만, 다른 설계에서는 가산기를 재사용하는 편이 면적을 절약할 수 있습니다. 현대 프로세서도 하나의 단일 비교기를 구현하기보다 분기, 주소 생성, 벡터 및 기타 실행 논리에 비교를 분산합니다.

타이밍 경로에는 소스 클록-대-Q, 입력 선택, 비교기 논리, 배선, 목적지 설정 및 클록 효과가 포함됩니다. 게이트 수만으로 최대 주파수가 정해지지는 않습니다.

실용적 용도

정확한 주소 일치

동등 비교기는 주소가 고정 값과 같을 때 칩 선택 신호를 만들 수 있습니다. 정렬된 2의 거듭제곱 영역에서는 상위 주소 비트만 비교하고 하위 비트는 오프셋으로 처리하세요. 임의 범위에는 대신 부등식이나 인수분해된 디코드 논리를 사용할 수 있습니다.

버스의 정확성에는 동등성 이상의 것이 필요합니다. 인에이블, 접근 유형, 권한 및 상호 배타적 소유권도 선택 신호를 한정할 수 있습니다.

임계값과 윈도 검사

제어 논리는 다음을 검사할 수 있습니다.

LOW\le X\le HIGH

두 개의 크기 비교로 가능합니다. 포함 또는 제외 경계와 X에 부호가 있는지에 주의하세요.

최소/최대 및 비교-선택

크기 결과는 멀티플렉서를 구동할 수 있습니다.

min = (A < B) ? A : B
max = (A < B) ? B : A

각 값이 메타데이터를 담거나 안정 정렬이 필요할 때는 동률 정책이 중요합니다.

정렬 네트워크

비교-교환 셀은 하나의 비교기와 데이터 라우팅 멀티플렉서를 결합합니다. 고정 네트워크는 이 셀을 단계로 구성합니다. 지연 시간은 셀 수뿐 아니라 비교기 깊이와 비교-교환 단계 수 모두에 따라 달라집니다.

DigiSim에서 구축하고 검증하기

비교기 컴포넌트를 참고한 뒤, 게이트로 방정식을 구성하세요.

XNOR로 4개의 $E_i$ 신호를 구성합니다.
이를 E로 리덕션합니다.
각 위치에 대해 $G_i$ 및 $L_i$ 를 구성합니다.
MSB에서 LSB 방향으로 결합합니다.
유효한 모든 입력 쌍에서 G/E/L 중 정확히 하나가 High인지 단언합니다.
부호 없는 비교와 부호 있는 비교 사이를 전환하는 MSB 바이어스 옵션을 추가합니다.

4비트에서는 모든 경우의 시험이 현실적입니다. 모든 $16\times16=256$ 쌍을 평가하세요.

각 쌍에서 다음을 확인합니다.

E가 비트 벡터 동등성과 같은지;
부호 없는 G/L이 정수 0–15와 일치하는지;
부호 있는 G/L이 정수 -8–7과 일치하는지;
A와 B를 바꾸면 G와 L은 바뀌고 E는 유지되는지;
G, E, L이 상호 배타적이며 전체를 포괄하는지.

그런 다음 4비트 블록 두 개를 캐스케이드하고 0x0F/0x10, 0x7F/0x80, 그리고 상위 절반은 같고 하위 절반은 다른 경계 쌍을 대상으로 하세요.

기능 시뮬레이터는 부울 관계를 확립합니다. 최종 기술에서의 물리 전파 지연, 전기적 호환성 또는 타이밍 클로저를 확립하지는 않습니다.

참고 자료

Texas Instruments SN74LS85 4비트 크기 비교기 제품 페이지 및 데이터시트