[디지털 논리] 3 불 대수의 응용(Application of Boolean Algebra)

최소항과 최대항

논리 회로를 설계할 때 진리표를 수식으로 옮기는 표준적인 두 가지 방법이다

최소항(Minterm, $m$)

최소항 정의

모든 변수가 한 번씩 나타나는 곱(Product) 형태의 항이다

특징: 해당 항의 결과값이 1이 되도록 변수를 조합한다. 변수가 0이면 보수($X^{\prime }$), 1이면 원래 모양($X$)으로 쓴다

표준 곱의 합(SOP): 진리표에서 결과가 1인 모든 최소항을 더한 것이다

표기법: $\sum m(3,4,5,6,7)$ 처럼 시그마 기호를 사용해 나타낸다

최대항(Maxterm, $M$)

최대항 정의

모든 변수가 한 번씩 나타나는 합 형태의 항이다

특징: 해당 항의 결과값이 0이 되도록 변수를 조합한다. 최소항과 반대로, 변수가 0이면 원래 모양($X$), 1이면 보수($X^{\prime }$)로 쓴다

표준 합의 곱(POS): 진리표에서 결과가 0인 모든 최대 항을 곱한 것이다

표기법: $\prod M(0,1,2)$ 처럼 파이 기호를 사용해 나타낸다

최소항 vs. 최대항

3개의 변수가 있을 때, 각 행에 대응하는 항의 모습은 다음과 같다

행(ROW)	XYZ	최소항-결과 1위주	최대항-결과 0위주
0	0 0 0	$m_0=X^{\prime }{Y}^{\prime }{Z}^{\prime }$	$M_0=X+Y+Z$
3	0 1 1	$m_3=X^{\prime }YZ$	$M_3=X+Y^{\prime }+Z^{\prime }$
7	1 1 1	$m_7=XYZ$	$M_7=X^{\prime }+Y^{\prime }+Z^{\prime }$
상호 보완 관계:
최소항과 최대항은 서로 보수(Complement) 관계에 있다. 즉, 한쪽의 구성을 알면 반대쪽 구성을 바로 알아낼 수 있다

• 예시: 3변수 함수에서 $F(X,Y,Z)=\sum m(0,2,5,7)$ 이라면, 여기에 포함되지 않는 나머지 번호(1,3,4,6)가 최대항의 번호가 된다
  • 결과: $F(X,Y,Z)=\prod M(1,3,4,6)$

최소항의 성질

• 개수: n개의 불 변수가 있을 때. 최소항은 총 $2^n$개 존재한다
• 표현력: 어떤 불 함수도 최소항들의 논리합으로 표현할 수 있다
• 보수: 함수의 보수는 원래 함수에 포함되지 않은 나머지 최소항들의 집합이다
• 전체 합: 모든 $2^n$개의 최소항을 다 더하면 논리값 1이 된다
• 직교성: 서로 다른 두 최소항을 AND연산하면 항상 0이 된다 ($m_i\cdot m_j=0,i\ne j$). 즉, 어떤 입력에 대해 단 하나의 최소항만 1이 될 수 있다

참고사항

최소항은 전개 시 계산이 복잡하여 상대적으로 덜 사용되지 경향이 있다

최소항 및 최대항 전개 방법

논리식에 특정 변수가 빠져있을 때, 모든 변수를 포함하는 표준형으로 만드는 과정이다

최소항 전개(Finding Minterms)

• 핵심: 빠진 변수 $X$에 대해 ($X+X^{\prime }$)=1 임을 이용하여 곱해준다
• 예시: $f(a,b,c,d)=a^{\prime }(b^{\prime }+d)+ac{d}^{\prime }$ 식에서 $a^{\prime }{b}^{\prime }$ 항에는 $c,d$가 없다
  • $a^{\prime }{b}^{\prime }(c+c^{\prime })(d+d^{\prime })$를 곱해 모든 경우의 수를 나열한다
  • 결과: $\sum m(0,1,2,3,5,7,10,14)$

최대항 전개(Finding Maxterms)

• 핵심: 빠진 변수 $X$에 대해 ($X{X}^{\prime }$)=0임을 이용하여 더해준다(분배 법칙 활용)
• 결과: 위 최소항 번호를 제외한 나머지 번호들이 최대항이 된다
  • 결과: $\prod M(4,6,8,9,11,12,13,15)$

일반적인 전개 공식

함수 F는 다음과 같이 일반화하여 표현할 수 있다

• 최소항 합: $F={\sum }_{i=0}^{2^n-1}{a}_i{m}_i$ (여기서 $a_i$는 해당 ㄴㄴ최소항의 출력값 0 또는 1)
• 두 함수의 곱: 두 함수 $F_1,F_2$를 곱할 때, 직교성에 의해 동일한 번호의 최소항끼리 곱한 것들의 합과 같다

불완전 함수와 무관 조건(Don’t Care)

무관 조건의 정의

회로 설계 시 특정 입력 조합이 절대로 발생하지 않거나, 결과가 0이든 1이든 상관없는 경우를 무관 조건이라고 한다. X로 표시한다

• 활용: 식을 간소화할 때, ‘X’를 0이나 1 중 유리한 쪽으로 선택하여 더 크게 묶을 수 있다
• 표기법:
  • 최소항 전개: $F=\sum m(\text{필수 1})+\sum d(\text{무관 조건})$
  • 최대항 전개: $F=\prod M(\text{필수 0})\cdot \prod D(\text{무관 조건})$

덧셈의 기초 예제

2진 가산기 설계(Binary Adder)

가장 기본적인 형태의 가산기로, 보통 반가산기라고 불리는 구조이다 설계 사양:

• 입력: 1비트 입력 2개(A,B)
• 출력: 2비트 출력(X,Y)
  • X: 자리올림수(Carry output)
  • Y: 더하기 결과(Adding output/Sum)

진리표 및 논리식

• $X$ (Carry): $A$와 $B$가 모두 1일 때만 1이 됩니다. $\to$ $X=AB$ (AND 연산)
• $Y$ (Sum): $A$와 $B$가 서로 다를 때만 1이 됩니다. $\to$ $Y=A^{\prime }B+A{B}^{\prime }=A\oplus B$ (XOR 연산)

응용 설계: 에러 검출기(Error Detector)

특정 코드 체계에서 유효하지 않은 조합이 들어왔을 때 이를 감지하는 회로이다

대상: 6-3-1-1 BCD 코드(각 비트의 가중치가 6,3,1,1인 코드)

오류 조건 (F=1):

• 중복 표현: 같은 수를 나타낼 수 있는 여러 조합 중 하나를 오류로 간주
• 범위 초과: BCD는 0~9까지만 표현하므로, 합이 10 이상인 겨우 에러

논리식 도출 및 간소화:

• $F=\sum m(2,6,10,13,14,15)$

구현: 2입력 AND, 3입력 AND, 2입력 OR 게이트 총 3개로 구성 가능

병령 이진 가산기 설계

여러 비트의 이진수를 한 번에 더하는 장치이다

기본 구조

• 4비트 가산기 기준: 9개의 입력(4비트 두 수 + Carry in)과 5개의 출력(4비트 Sum + Carry out)이 필요하다
• 설계 방식: 1비트씩 더하는 전가산기(Full Adder) 모듈을 4개 연결하여 구성한다

논리 설계 진리표를 통해 합과 올림수의 식을 구한다

• 합(Sum): 세 입력 중 1의 개수가 홀수일 때 1이 된다
  • $Sum=X\oplus Y\oplus C_{in}$
• 올림수 ($C_{out}$): 세 입력 중 2개 이상이 1일 때 1이 됩다
  • $C_{out}=XY+X{C}_{in}+Y{C}_{in}$

게이트 구현 $Sum$은 XOR 게이트로, $C_{out}$은 AND와 OR 게이트의 조합으로 구현된다

음수의 덧셈과 오버플로 컴퓨토에서 빼기 연산은 2의 보수를 이용한 덧셈으로 처리된다

• 동작 원리: 2의 보수 처계에서는 일반 덧셈과 동일한 가산기를 그대로 사용할 수 있다
• 주의사항: 첫 번째 가산기의 Carry input($C_0$)은 0으로 둔다. 마지막 Carry out($C_4$)은 버린다
• 오버플로(V) 검출: 계산 결과가 4비트 범위를 벗어나 부호가 잘못되었을 때 발생한다
  • 공식: $V=A_3^{\prime }{B}_3^{\prime }{S}_3+A_3{B}_3{S}_3^{\prime }$
  • 의미:
    • 양수($A_3=0$) + 양수($B_3=0$) $\to$ 결과가 음수($S_3=1$)가 되면 오버플로
    • 음수($A_3=1$) + 음수($B_3=1$) $\to$ 결과가 양수($S_3=0$)가 되면 오버플로

이진 감산기 설계(Binary Subtracter)

전가산기를 이용한 설계 컴퓨터 내부에서 별도의 감산 회로를 만들지 않고, 기존의 전가산기를 그대로 활용하여 2의 보수 연산을 수행하는 방식이다

• 원리: $A-B$ 연산을 $A+(-B)$로 바꾸어 처리한다
• 구현 단계:
  • 1의 보수화: 입력 $B$의 모든 비트를 반전(NOT 게이트)시킨다
  • 2의 보수화: 반전된 결과에 $1$을 더한다. 이를 위해 회로의 첫 번째 하위 비트 Carry input($C_1$)을 1로 설정한다
• 특징: 마지막 올림수는 무시하며, 가산기 하나로 덧셈과 뺄셈을 모두 처리할 수 있어 효율적이다

직접 설계를 통한 전감산기 입력 $X$에서 $Y$를 직접 빼는 논리 회로를 설계하는 방식이다. 이때 핵심은 아랫자리에서 빌려온 값인 빌림수를 고려하는 것이다

• 입력 변수: $x_i$ (피감수), $y_i$ (감수), $b_i$ (입력 빌림수)
• 출력 변수: $d_i$ (차, Difference), $b_{i+1}$ (출력 빌림수)

논리식과 진리표

전가산기(FA)를 이용한 이진 곱셈기 설계

이진 곱셈은 우리가 배운 필산 방식과 똑같은 원리로 작동한다

동작 원리:

• 부분곱(Partial Product) 생성: 각 비트의 곱셈은 AND 게이트를 사용한다($1\cdot 1=1$, 나머지는 $0$)
• 수직 합산: 생성된 부분곱들을 자릿수에 맞춰 아래로 더한다. 이때 전가산기(Full Adder) 혹은 병렬 가산기 모듈이 사용된다

회로 구조 분석

• AND 게이트 배열: $A_0,A_1,A_2$와 $B_0\sim B_3$를 각각 AND 연산하여 부분곱들을 만든다
• 가산기 연결: 첫 번째 줄의 부분곱과 왼쪽으로 한 칸 시프트(Shift)된 두 번째 줄의 부분곱을 4비트 가산기로 더한다. 그 결과에 다시 세 번째 줄의 부분곱을 더하는 방식으로 최종 결과($C_0\sim C_6$)를 얻는다

이진 비교기 설계(Binary Comparator)

두 개의 4비트 수 $A(A_3{A}_2{A}_1{A}_0)$와 $B(B_3{B}_2{B}_1{B}_0)$를 비교하여 $A>B$인 경우를 찾아내는 회로이다

설계 원리 $A>B$가 성립하려면 상위 비트부터 차례대로 비교해야 한다. 출력 $F=1$이 되는 조건은 다음과 같다

• 경우 1: 최상위 비트에서 이미 결정됨 $\to$ ($A_3=1,B_3=0$)
• 경우 2: $A_3,B_3$는 같고, 그다음 비트가 큼 $\to$ ($A_3=B_3$) AND ($A_2=1,B_2=0$)
• 경우 3: $A_3\sim A_2$는 같고, 그다음 비트가 큼 $\to$ ($A_3=B_3,A_2=B_2$) AND ($A_1=1,B_1=0$)
• 경우 4: $A_3\sim A_1$은 같고, 최하위 비트가 큼 $\to$ ($A_3=B_3,A_2=B_2,A_1=B_1$) AND ($A_0=1,B_0=0$)