카르노 맵의 무관 조건

요약: 무관 조건은 시스템 계약이 출력 값을 제한하지 않는 입력에 대해 구현이 값을 선택하도록 허용하는 것입니다. K-map에서는 유용한 그룹을 더 크게 만들 때만 X 셀을 포함하세요. SOP에서는 필수 0을, POS에서는 필수 1을 절대 덮으면 안 됩니다. 최적화는 사용 지점에서 care-set 가정이 참일 때만 유효합니다. HDL의 X, 시뮬레이션의 미정 값, 합성 무관 조건은 자동으로 같은 의미가 아닙니다.

일반적인 논리 최소화는 가능한 모든 입력에서 함수를 보존합니다. 무관 조건은 이 요구를 완화합니다. 선택한 입력/출력 경우에 0과 1 중 어느 값을 배정해도 되므로, 실제로 중요한 경우에 대해서만 더 작은 구현을 만들 수 있습니다.

이 자유는 리터럴과 게이트를 줄일 수 있습니다. 그러나 가정이 틀리면 리셋 복구를 제거하거나, 잘못된 표시 패턴을 노출하거나, 시뮬레이션과 실리콘의 동작 차이를 만들 수도 있습니다. 전문적인 설계는 다음 세 가지를 함께 기록합니다.

1. 출력이 반드시 1이어야 하는 on-set
2. 출력이 반드시 0이어야 하는 off-set
3. 어느 결과든 시스템 계약을 만족하는 무관 집합(don’t-care set)

출력이 제약되지 않을 수 있는 두 가지 이유

1. 입력에 도달할 수 없다

환경이 관련 관찰 시점에 특정 입력 벡터가 이 논리에 도달할 수 없음을 보장하는 경우입니다.

유효한 BCD 숫자는 0–9 범위이므로 다음 조건이 모두 충족되면 10–15는 도달 불가능할 수 있습니다.

• 입력원이 언제나 유효한 BCD만 생성한다.
• 리셋과 전원 인가 과정에서 다른 값이 노출되지 않는다.
• 중간 전이 값을 숫자로 샘플링하지 않는다.
• 코드를 손상시키는 고장이 설계에서 요구하는 고장 모델의 범위 밖이다.

4비트 버스가 등록된 두 유효 값 사이를 바꾸는 동안 잠깐 1100이 될 수 있다면, “알고리즘은 12를 요청하지 않는다”는 설명만으로는 부족합니다.

2. 입력은 발생할 수 있지만 이 출력이 관찰되지 않는다

파이프라인 단계는 valid=0일 때 임의의 데이터를 전달할 수 있습니다. 모든 소비자가 같은 valid 상태로 데이터를 한정한다면 invalid 주기의 데이터 출력은 중요하지 않습니다.

이는 입력이 도달 불가능한 조건이 아니라 관찰 가능성 조건입니다. 어느 소비자도 명목상 중요하지 않은 필드를 기록·비교·전달하거나 다른 방식으로 사용하지 않을 때만 계속 안전합니다.

두 경우 모두 2값 최소화 문제에서는 X 셀이 됩니다. 그러나 증명 방식이 다르므로 명세에 그 이유를 보존해야 합니다.

X는 하나의 보편적인 뜻이 아니다

기호 X에는 여러 의미가 겹쳐 있습니다.

• K-map에서 X는 “구현이 0이나 1 중 하나를 선택해도 된다”는 뜻입니다.
• 4상태 HDL 시뮬레이션에서 X는 흔히 “알 수 없음, 충돌 또는 초기화되지 않음”을 뜻합니다.
• 진리표 문서에서 X는 해당 행에서 한 입력 값이 중요하지 않음을 뜻할 수 있습니다.
• 합성 지시문에서 도구별 구문은 최적화를 허용할 수 있습니다.

이 의미들은 서로 바꿔 쓸 수 없습니다.

RTL에서 'x를 할당하면 어떤 흐름에서는 최적화가 좋아질 수 있지만, 시뮬레이션에서는 미정 값을 전파하고, 다른 흐름에서는 무시되거나 변환되며, 실제 초기화 버그를 가릴 수도 있습니다. 조합 할당을 빠뜨리면 무관 조건이 아니라 래치가 추론될 수 있습니다. full_case 같은 도구 지시문은 합성된 동작을 시뮬레이션과 다르게 만들 수 있으며, Intel 문서도 이 가능성을 명시적으로 경고합니다.

대상 언어, 시뮬레이터, 합성 도구, 린트 규칙, 정형 검증 흐름이 지원하는 방법으로 의도를 표현하세요. 그런 다음 같은 환경 가정 아래에서 합성 결과를 검증해야 합니다.

K-map 규칙

최소화된 곱항의 합(SOP)을 구할 때는 다음 순서를 따릅니다.

1. 각 셀을 필수 0, 필수 1 또는 X로 표시합니다.
2. 1과 X만 포함하는 2의 거듭제곱 크기 직사각형을 만듭니다.
3. 모든 필수 1을 덮습니다.
4. 필수 0은 절대 포함하지 않습니다.
5. cover를 개선하지 않는 X는 사용하지 않습니다.
6. 실제 비용 목표에 따라 cover를 선택합니다. 리터럴 수, 셀 수, 깊이, 공유 항 또는 다른 구현 지표가 목표가 될 수 있습니다.

합항의 곱(POS)에는 쌍대 규칙을 적용합니다.

• 필수 0과 선택 가능한 X를 함께 그룹화합니다.
• 모든 필수 0을 덮습니다.
• 필수 1은 절대 포함하지 않습니다.

각 출력은 같은 X를 다르게 사용할 수 있습니다. 한 세그먼트 함수는 특정 invalid BCD 셀을 1로 선택하고, 다른 함수는 0으로 선택할 수 있습니다. 인터페이스 명세가 하나의 전역 invalid 패턴을 강제하지 않는 한 모든 출력이 같은 값을 배정할 필요는 없습니다.

예제: 유효한 BCD 숫자가 5 이상인가

A를 BCD의 최상위 비트, D를 최하위 비트라고 합시다. 필요한 동작은 다음과 같습니다.

• 숫자 0–4에서 F=0
• 숫자 5–9에서 F=1
• 코드 10–15에서 X

행과 열을 그레이 코드 순서로 배열하면 다음과 같습니다.

              CD
           00  01  11  10
AB = 00     0   0   0   0
AB = 01     0   1   1   1
AB = 11     X   X   X   X
AB = 10     1   1   X   X

X 셀 덕분에 유용한 그룹 세 개를 만들 수 있습니다.

• A=1인 두 행 전체가 8셀 그룹을 이루어 A를 얻습니다.
• 0110, 0111, 1110, 1111에서 BC를 얻습니다.
• 0101, 0111, 1101, 1111에서 BD를 얻습니다.

따라서 다음과 같습니다.

인수분해하면 다음과 같습니다.

care set을 확인해 봅시다.

• 숫자 0–4는 0을 출력합니다.
• 숫자 5–7은 $B(C+D)$를 만족합니다.
• 숫자 8–9는 A를 만족합니다.

이 식은 우연히 모든 invalid 코드 10–15에서 1을 출력합니다. 해당 행들이 명시적으로 제약되지 않았기 때문에만 허용되는 결과입니다.

invalid 코드가 반드시 0을 출력해야 한다면

이제 해당 코드는 무관 조건이 아닙니다. 10–15에서 F=0일 때 유효한 SOP 중 하나는 다음과 같습니다.

이 버전은 invalid 코드에서 요구되는 0을 보존합니다. 인터페이스 계약이 더 강하므로 회로도 더 큽니다.

무관 조건이 도움이 되지 않는 경우

유효한 BCD 숫자가 “짝수인가”를 판별하는 식은 다음과 같습니다.

최하위 비트가 이미 홀짝을 부호화합니다. 코드 10–15를 X로 허용해도 필수 값을 바꾸지 않고 유일한 리터럴을 제거할 수 없으므로 최소식은 그대로입니다.

무관 조건은 최적화 공간을 넓히지만 반드시 더 나은 결과를 보장하지는 않습니다.

리터럴 하나가 사라지는 경우

유효한 BCD 숫자 8과 9에서 F=1이고, 유효한 숫자 0–7에서 F=0이라고 정의합니다.

invalid 코드 10–15도 반드시 0이어야 한다면 다음 식이 필요합니다.

1000과 1001만 이 식을 만족합니다.

10–15가 무관 조건이라면 필수 1 두 개를 여섯 개의 X 셀 모두와 그룹화할 수 있습니다.

두 구현은 유효한 BCD에서 일치하고 일부 invalid 입력에서는 의도적으로 다릅니다.

올바른 비교에서 이 점은 중요합니다. invalid 셀을 몰래 그룹 확장에 사용하면서 “무관 조건을 쓰지 않았다”고 주장해서는 안 됩니다.

과도 입력과 샘플링 경계

입력과 출력 레지스터가 유효한 코드만 담더라도 조합 회로의 비트가 동시에 전환되지는 않습니다. BCD 7(0111)에서 8(1000)로 바뀔 때는 네 비트가 모두 변하고, 전기적으로 다른 조합들을 잠깐 거칠 수 있습니다.

문제가 되는지는 경계에 따라 달라집니다.

• 디코더가 안정된 뒤에만 샘플링하는 목적지 레지스터는 중간 결과를 한 번도 캡처하지 않을 수 있습니다.
• 최소화된 논리에서 파생된 비동기 출력 enable, write strobe 또는 clock은 과도 상태에 반응할 수 있습니다.
• 다중화 표시 장치에는 짧은 고스트 패턴이 나타날 수 있습니다.
• 소프트웨어가 한 번도 관찰하지 않는 값이 로직 분석기에는 보일 수 있습니다.

따라서 도달 불가능 집합의 증명은 소프트웨어가 의도하는 정상 상태 값뿐 아니라 출력이 언제 중요한지도 명시해야 합니다.

입력이나 출력을 레지스터에 저장하고, 타이밍을 제약하고, 해저드 없는 제어를 설계하거나 blanking을 추가하면 가정을 참으로 만들 수 있습니다. K-map에 X를 적는 것만으로는 불가능합니다.

상태 머신의 불법 상태

세 비트로 다섯 상태를 부호화한다고 합시다. 정상 동작에서는 세 코드가 사용되지 않습니다. 리셋이 보장되고 상태 손상이 고려 범위 밖이라면 해당 코드를 무관 조건으로 두고 다음 상태와 출력 논리를 최적화하는 것이 합리적일 수 있습니다.

단일 사건 upset, CDC 오류, 부분 리셋 또는 fault injection이 범위에 포함된다면 그 코드들은 중요하지 않은 값이 아닙니다. 설계에는 다음 기능이 필요할 수 있습니다.

• 불법 상태 감지
• 위험한 출력 즉시 억제
• 리셋 또는 다른 안전 상태로 복귀
• 고장 보고
• 요구되는 해밍 거리를 가진 인코딩 사용

FPGA 도구는 명시적인 안전 상태 기능을 제공합니다. 예를 들어 AMD Vivado의 FSM_SAFE_STATE는 면적과 성능을 대가로 invalid 상태 감지 및 복구 논리를 추가합니다. Intel Quartus 문서도 일반 합성과 안전 상태 머신 옵션을 구분합니다.

불법 상태를 최적화로 없애면서 그 상태에서의 복구까지 보장한다고 주장해서는 안 됩니다. 둘은 서로 다른 명세입니다.

원-핫 및 우선순위 입력

정확히 원-핫인 $n$비트 인터페이스에는 n개의 유효 벡터와 $2^n-n$개의 다른 벡터가 있습니다. 프로토콜이 one-hot-or-zero라면 0 벡터도 유효합니다.

업스트림 논리가 정확한 원-핫 입력을 보장하면 일반 인코더는 여러 비트가 동시에 활성화된 행을 무관 조건으로 둘 수 있습니다. 우선순위 인코더는 여러 비트가 활성화된 행의 동작을 의도적으로 정의하므로 이를 제약되지 않은 값으로 취급할 수 없습니다. 요청이 하나도 없을 때 valid 출력이 코드를 한정한다면 그때의 코드는 중요하지 않다고 정의할 수 있습니다.

이 차이는 “encoder” 같은 이름만 보고 가정을 추측하지 말고 모듈 경계에서 입력 조건을 문서화해야 하는 이유 중 하나입니다.

출력이 중요하지 않은 데이터

다음 상태를 생각해 봅시다.

valid = 0
data  = anything

관찰할 수 있는 모든 효과가 다음처럼 게이트될 때만 데이터 의존 다운스트림 논리를 안전하게 최적화할 수 있습니다.

write_enable = valid AND condition(data)

하지만 이 경우에도 condition(data)의 물리적 스위칭은 전력을 소비하고, 부채널 누출을 만들거나, 타이밍에 영향을 줄 수 있습니다. “기능적으로 관찰되지 않는다”가 반드시 “전기적으로 중요하지 않다”는 뜻은 아닙니다.

시뮬레이션을 명확하게 유지하기 위해 많은 팀이 invalid 데이터에도 결정적인 값을 할당하고, 명시적 제약이나 주변 enable을 통해 합성이 최적화하도록 합니다. 최선의 선택은 검증과 구현 흐름에 따라 달라집니다.

HDL 지침

K-map 표기를 생각 없이 HDL X 할당으로 옮기지 마세요.

보수적인 조합 패턴은 모든 출력을 정의합니다.

always_comb begin
  valid = (bcd <= 4'd9);
  ge_five = 1'b0;
  if (valid)
    ge_five = (bcd >= 4'd5);
end

이 코드는 invalid 동작을 0으로 지정합니다. 프로젝트가 invalid 입력을 합성 무관 조건으로 사용하려면 검토를 거친 도구 지원 메커니즘과 그에 대응하는 가정으로 의도를 표현하세요. 정형 입력 제약, 합성 속성, 제약된 모듈 인터페이스 또는 기술별 원시 소자 등이 예가 될 수 있습니다.

어느 방법을 선택하든 다음을 수행해야 합니다.

• 불완전한 할당과 의도하지 않은 래치를 린트로 검사합니다.
• 흐름에서 요구한다면 RTL과 게이트 수준 동작을 비교합니다.
• care set에서 동등성을 증명합니다.
• 환경 가정이 성립하는지 검증합니다.
• 도달 불가능 상태와 case 적용 범위에 관한 경고를 확인합니다.
• 특별히 의도한 동작이 아니라면 미정 제어 비트를 숨길 수 있는 casex 또는 와일드카드 매칭을 피합니다.

검증 계획

무관 조건 최적화에는 서로 보완하는 두 검사가 필요합니다.

care set에서의 기능 동등성

모든 필수 입력에 대해 다음이 성립해야 합니다.

변수가 네 개라면 전체 진리표를 열거합니다. 논리가 더 크다면 명시적인 care-set 제약과 함께 assertion이나 정형 동등성 검증을 사용합니다.

가정 검증

다음 항목을 증명하거나 테스트해야 합니다.

• 출력이 중요할 때 invalid 인코딩이 샘플링되지 않는다.
• 리셋과 전원 인가가 가정을 지킨다.
• CDC 경로가 지원되지 않는 조합을 만들 수 없다.
• 고장 요구 사항에 “도달 불가능” 집합이 포함되지 않는다.
• 다운스트림 valid 게이팅이 모든 부수 효과를 막는다.
• 테스트와 디버그 모드가 qualifier를 우회하지 않는다.

X를 합법으로 만드는 것이 환경이라면 최소화된 불 식만 테스트하는 것은 계약의 잘못된 절반을 검증하는 셈입니다.

DigiSim에서 BCD 예제 만들기

숫자 ≥ 5 검출기 두 개를 만드세요.

1. invalid 정의 버전: $F=\overline A BC+\overline A BD+A\overline B\overline C$를 구현합니다.
2. 무관 조건 최적화 버전: $F=A+BC+BD$를 구현합니다.
3. 16개 입력을 모두 순회합니다.
4. 두 회로가 0–9에서 일치하는지 확인합니다.
5. 10–15에서 의도적으로 달라지는 결과를 기록합니다.
6. BCD 0–9에 대해 valid = NOT(A AND (B OR C))를 추가하고 관찰 가능한 출력을 게이트합니다.
7. 여러 입력 비트를 함께 바꾸어 시뮬레이터가 중간 전이를 모델링하는지 살펴봅니다. 이상적인 동시 갱신을 사용한다면 아날로그 해저드 동작을 추론하지 마세요.

이 연습은 더 좁은 동작 약속을 대가로 더 작은 논리를 얻는다는 올바른 교환 관계를 보여 줍니다.

검토 체크리스트

어떤 셀을 X로 표시하기 전에 다음을 물어보세요.

• 이 출력이 제약되지 않는 이유는 도달 불가능한 입력인가, 관찰되지 않는 출력인가?
• 어느 샘플링 또는 관찰 경계에서 그 설명이 참인가?
• 리셋, CDC, 테스트 모드 또는 고장 동작이 가정을 위반하는가?
• X는 K-map의 허용 표시인가, HDL 미정 값인가, 도구 지시문인가?
• 불법 상태에서 복구해야 하는가?
• 최적화된 구현을 모든 care-set 입력에서 검증했는가?
• 가정 자체를 assertion으로 검사하거나 증명했는가?

무관 조건은 “공짜 게이트”가 아닙니다. 정의된 care set 바깥의 동작을 포기하는 대신 구현 자유를 얻는 것입니다. care set을 명시하고 검증했다면 규율 있는 최적화입니다. 그저 참이라고 추측했다면 숨겨진 기능이 됩니다.

인코딩 계약은 BCD 기초에서, 7개 출력 응용은 BCD-7세그먼트 디코딩에서, 전이 시간 동작은 정적·동적 해저드에서 계속 살펴보세요.

참고 자료

• AMD Vivado 합성: FSM_SAFE_STATE
• Intel Quartus 상태 머신 HDL 지침
• Intel Quartus full_case 합성 속성과 시뮬레이션 불일치 경고