디지털 회로의 0과 1은 하나의 고정 전압이 아니라 데이터시트가 보장하는 전압 범위다. 일반적으로 입력이 VIL(max) 이하이면 LOW, VIH(min) 이상이면 HIGH로 보장된다. 두 값 사이의 전압은 논리 상태가 보장되지 않는 영역이다. 임계값은 논리 제품군, 공급전압과 동작 온도에 따라 달라지므로 “3V는 언제나 1”처럼 일반화하지 말고 사용하는 부품의 데이터시트를 확인해야 한다.

이처럼 연속적인 전압을 두 논리 상태로 해석한 뒤에는 불 대수(Boolean algebra)로 회로의 동작을 표현할 수 있다. 불 대수의 식을 실제 트랜지스터 회로로 구현하는 기본 블록이 논리 게이트다.

NOT·AND·OR·NAND·NOR·XOR 게이트의 기호와 진리표

불 대수의 기본 연산

이진 변수 A, B, x, y는 0 또는 1의 값을 갖는다. 다음 세 연산만으로 임의의 불 함수를 표현할 수 있다.

  • AND (·, 생략 가능): 모든 입력이 1일 때만 1
  • OR (+): 입력 중 하나 이상이 1이면 1
  • NOT (' 또는 변수 위의 선): 0과 1을 반전

불 대수의 기본 법칙과 드모르간 정리 표

예를 들어 다음 식에서는 앞의 두 항에 공통인 AB를 묶을 수 있다.

F = ABC + ABC' + A'C
  = AB(C + C') + A'C
  = AB + A'C

논리식을 줄이면 필요한 리터럴과 중간 게이트를 줄일 가능성이 있다. 다만 불 대수식이 짧아졌다고 실제 칩의 비용·전력·지연이 반드시 같은 비율로 감소하는 것은 아니다. 최종 결과는 사용 가능한 게이트, 팬인, 배선, 해저드와 합성 도구의 매핑에도 영향을 받는다.

최소항과 최대항

  • 최소항(minterm): 모든 입력 변수가 정확히 한 번씩 AND로 곱해진 항. 예: x'y'z
  • 최대항(maxterm): 모든 입력 변수가 정확히 한 번씩 OR로 더해진 항. 예: x+y'+z

변수가 n개이면 가능한 입력 조합과 최소항은 각각 2ⁿ개다. 변수 순서를 x, y, z로 정하면 m1은 이진수 001, 즉 x'y'z에 대응한다. 진리표에서 출력 F가 1인 최소항만 OR로 묶은 표현을 SOP(Sum of Products)라고 한다.

F(x,y,z) = Σm(1,4,5,6,7)
         = x'y'z + xy'z' + xy'z + xyz' + xyz

최소항 번호를 해석할 때는 변수 순서를 먼저 선언해야 한다. 순서가 바뀌면 같은 번호가 가리키는 입력 조합도 바뀐다.

드모르간 정리로 보수 구하기

합과 곱의 보수는 다음 두 식으로 바꿀 수 있다.

(A + B)' = A'B'
(AB)'    = A' + B'

복합식에서는 바깥쪽 연산을 바꾸고 각 항의 보수를 취한다.

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

논리식과 게이트 회로 및 진리표를 이용한 불 함수 검증 예시

식 변환 뒤에는 원래 식과 변환한 식의 모든 입력 조합을 진리표로 비교하면 실수를 찾을 수 있다.

K-Map으로 논리식 간소화하기

Karnaugh Map(K-Map)은 진리표의 셀을 Gray code 순서로 배치해 인접한 최소항을 시각적으로 묶는 도구다. 행과 열의 값은 한 번에 한 비트만 바뀌도록 00, 01, 11, 10 순서로 놓는다.

2변수·3변수·4변수 카르노 맵의 Gray code 셀 배치

K-Map을 묶을 때는 다음 규칙을 지킨다.

  1. SOP를 구할 때는 출력이 1인 셀을 표시한다.
  2. 그룹은 1, 2, 4, 8처럼 2의 거듭제곱 개수로 이루어진 직사각형이어야 한다.
  3. 맵의 왼쪽과 오른쪽, 위와 아래는 서로 인접하며 네 모서리도 한 그룹으로 묶을 수 있다.
  4. 모든 1을 한 번 이상 포함하되 가능한 한 큰 그룹을 만들고, 필요하면 그룹을 겹친다.
  5. don’t-care 항은 더 큰 그룹을 만드는 데 유리할 때만 선택적으로 포함한다.
  6. 한 그룹 안에서 값이 변하지 않는 변수만 최종 항에 남긴다.

계산 예: Σm(1,3,5,7)

변수 순서를 x, y, z로 두면 네 최소항은 모두 z=1인 입력이다.

x \ yz 00 01 11 10
0 0 1 1 0
1 0 1 1 0

가운데 네 셀을 하나의 그룹으로 묶으면 그룹 안에서 x와 y는 0과 1로 변하므로 사라지고, 항상 1인 z만 남는다.

F(x,y,z) = Σm(1,3,5,7) = z

K-Map은 보통 4변수 이하에서 읽기 쉽다. 변수가 많아지면 Quine–McCluskey 같은 표 형식 방법이나 논리 합성 도구를 사용하는 편이 오류를 줄이기 쉽다.

조합회로와 순차회로

조합회로는 현재 입력으로 출력을 계산한다. 순차회로는 현재 입력뿐 아니라 기억소자에 저장된 상태도 함께 사용한다.

구분 조합회로 동기식 순차회로
상태 저장 없음 플립플롭 등에 저장
출력 결정 현재 입력 현재 상태와 입력, 또는 현재 상태
상태 갱신 해당 없음 활성 클럭 에지에서 다음 상태 저장
예시 가산기, 멀티플렉서, 디코더 카운터, 레지스터, 상태기계

조합회로와 플립플롭 피드백으로 구성된 동기식 순차회로

플립플롭과 래치도 구분해야 한다.

  • D 플립플롭: 일반적으로 상승 또는 하강 에지에서 입력을 저장하는 에지 트리거 소자
  • D 래치: enable이 활성인 레벨 동안 입력을 따라가고, 비활성일 때 값을 유지하는 레벨 민감 소자

두 소자 모두 1비트 상태를 저장할 수 있지만 입력을 받아들이는 시간 조건이 다르다.

상태도와 필요한 플립플롭 수

상태도에서 원은 상태를, 화살표는 상태 전이를 나타낸다. Mealy 모델의 입력/출력은 전이 화살표에 적으며 출력이 현재 상태와 입력에 의해 결정된다. Moore 모델은 출력을 상태 안에 적으며 출력이 현재 상태에 의해 결정된다.

현재 상태·입력·다음 상태·출력을 정리한 상태표

상태가 S개일 때 일반적인 이진 인코딩에 필요한 플립플롭의 이론적 최소 수는 다음과 같다.

필요한 플립플롭 수 = ceil(log2(S))

예를 들어 상태가 5개이면 ceil(log2(5)) = 3이므로 3비트가 필요하다. 이 경우 8개 코드 중 3개는 사용하지 않으므로, 사용하지 않는 상태에 진입했을 때 정상 상태로 복구하는 전이도 정해야 한다. 반면 one-hot 인코딩은 보통 상태마다 한 비트를 배정해 5개의 플립플롭을 사용한다. 어느 방식이 더 빠르고 작은지는 대상 FPGA·ASIC과 합성 결과에 따라 달라진다.

관련 글

참고 자료