오늘은 정규형(Canonical form)과 최소항(minterm), 최대항(maxterm)에 대해 알아보겠습니다. 계속 수학 내용이 나오는데, 이걸 모르면 나중에 회로를 제대로 그릴 수가 없으니, 어렵고 힘들더라도 함께 공부해나갑시다!
정규형 (Canonical form)
어떠한 논리식은 각 논리 변수(또는 그 부정)들의 곱의 합 또는 합의 곱만으로 표현할 수 있는데요, 이렇게 표현한 식을 정규형이라고 합니다.
이렇게 정규형을 만드는 이유는 여러 가지가 있지만 대부분 게이트의 효율과 관련이 있습니다. 그중 하나인 게이트 레벨을 소개하겠습니다.
게이트 레벨 (Gate level)
어떤 논리 회로가 결과를 출력하기 위해 거쳐야 하는 게이트의 단계를 의미합니다. 동시에 계산할 수 있는 게이트를 묶어 하나의 레벨로 취급합니다. 게이트 레벨이 높을수록 회로를 구성하는 데 있어서 효율이 떨어지므로 같은 식이라도 정규형으로 구현하는 것이 유리합니다.
논리식 상으로는 같을지 모르지만, 실제 하드웨어가 작동하는 과정을 살펴보면, 게이트를 한 단계 거칠 때마다 딜레이가 조금씩 누적됩니다. 이전 계산 결과가 출력되어야만 다음 레벨에서 계산이 가능하기 때문입니다. 이 때문에, 게이트 레벨이 높으면 연산 속도가 느려져 비효율적입니다.
정규형으로 표현하면 게이트 레벨이 최소가 되기 때문에, 똑같은 논리식이라도 게이트 레벨을 줄일 수 있다면 정규형이 아닙니다. 예를 들어, a+b(c+d)는 a+bc+bd와 같이 전개할 수 있으므로 정규형이 아닙니다. a+bc+bd는 각 항이 모든 변수를 포함하고 있지 않으므로 정규형은 아니고 표준형이라고 하는데, 이는 아래에서 다시 설명하도록 하겠습니다.
게이트 레벨에 대한 이해가 어려울 수 있으니 위의 게이트 레벨 그림을 보며 다시 생각해봅시다. 아까 위에서 본 논리식을 다시 예로 들겠습니다. 그림을 보면, a+b(c+d)는 위쪽 회로입니다. 최종 결과를 얻기 위해 3개의 레벨이 필요하므로 3-level 회로라고 할 수 있습니다.
이를 전개한 a+bc+bd도 살펴보겠습니다. 이번에는 2개의 레벨로 결과를 얻을 수 있습니다. 따라서 이는 2-level 회로입니다. 한 레벨을 거칠 때 d만큼 딜레이가 생긴다고 가정하면 3-level 회로는 3d만큼, 2-level 회로는 2d만큼의 시간으로 결과를 얻을 수 있습니다.
따라서 게이트 레벨이 낮은 논리식을 만드는 게 더 좋다는 것을 알 수 있습니다. (물론 게이트 레벨뿐만 아니라 게이트의 개수도 효율을 따질 때 중요한 요소이지만, 이 경우는 똑같이 3개의 게이트를 사용하였고, 레벨은 두 번째가 더 낮으므로 더 효율적이라고 할 수 있습니다.)
게이트 레벨에 대해 알아봤으니, 이제 다시 정규형으로 돌아오겠습니다.
아까 정규형은 두 가지 방식으로 표현할 수 있다고 설명드렸는데, 곱의 합(SOP: Sum Of Product)으로 나타낸 식의 각 항을 최소항(minterm), 합의 곱(POS: Product of Sum)으로 나타낸 식의 각 항을 최대항(maxterm)이라고 합니다.
이렇게 말로 풀어서만 설명하면 이해하기 어려울 테니 직접 최소항과 최대항을 만들어봅시다.
f=xy'+z라는 식이 있습니다. 지금부터 이 식의 진리표는 다음과 같은데요, 이를 가지고 최소항과 최대항을 만드는 과정을 보여드리겠습니다.
최소항 전개 (minterm expansion)
최소항 전개는 Canonical sum of product form이라고도 하는데요, 앞으로는 간단하게 최소항 또는 SOP라고 부르겠습니다. 말 그대로 곱의 합(Sum Of Product)으로 되어 있는 정규형 표현입니다.
최소항은 진리표 상 각 변수의 값에 따라 결정됩니다. 값이 1일 때는 그대로, 0일 때는 NOT을 붙여서 만들어줍니다. 예를 들어, 번호 1의 값을 보면, x=0, y=0, z=1입니다. 이에 해당하는 최소항은 x'y'z입니다. 여기에서 잘 보면 각 변수값에 따른 f와 min의 값이 서로 같음을 알 수 있습니다.
이에 따라 위의 논리식을 최소항 전개하면 f=x'y'z+x'yz+xy'z'+xy'z+xyz라는 표현식을 얻을 수 있습니다. 아까 그 f=xy'+z랑 이 긴 식이랑 같다고 하니 갑자기 이게 뭔가 싶고, 이해가 잘 안 될 수 있는데요, 자세히 설명하겠습니다.
최소항 전개는 곱의 합으로 표현해야 하므로, 1이 되는 최소항을 모두 OR 연산하면 f와 논리적 동치가 됩니다. 곱의 합으로 표현한 그 어떤 최소항도 1이 아니라면 최소항 전개식의 값은 0이고, 그때는 f의 값 역시 0입니다.
예를 들어 x=0, y=0, z=1일 때를 생각해보겠습니다. 먼저, f=xy'+z=0·1+1=1입니다. 최소항 전개식을 보면, f=x'y'z+x'yz+xy'z'+xy'z+xyz=1·1·1+0+0+0+0=1이므로 서로 같은 결과임을 알 수 있습니다. 이해가 어렵다면 다른 경우에 대해서도 값을 넣어 비교해보면 좋을 것 같습니다. 그래도! 이해가 어려울 수 있으니 불 대수 법칙을 이용한 증명도 아래에 남겨두었으니 참고해주세요.
pf)
f=x'y'z+x'yz+xy'z'+xy'z+xyz
=y'z(x'+x)+yz(x'+x)+xy'z'
=y'z+yz+xy'z'
=(y'+y)z+xy'z'
=z+xy'z'
=z+xy' (by Absorption Laws; x+x'y=x+y)
=xy'+z
최소항 전개식을 일일이 다 쓰면 복잡하므로, 위의 진리표 좌측에 있는 번호를 표기하여 다음과 같이 표현합니다.
f=Σm(1,3,4,5,7)
※ x, y, z의 값이 위의 진리표와 같아야 합니다.
최대항 전개 (maxterm expansion)
최대항 전개는 Canonical product of sum form이라고도 하는데요, 이 역시 앞으로는 최대항 또는 POS라고 부르도록 하겠습니다. 말 그대로 합의 곱(Product Of Sum)으로 되어 있는 정규형 표현입니다.
최대항도 역시 진리표 상 각 변수의 값에 따라 결정됩니다. 이번에는 반대로 값이 1일 때 NOT을 붙이고, 0일 때는 그대로 만들어줍니다. 예를 들어, 번호 1의 값을 보면, x=0, y=0, z=1입니다. 이에 해당하는 최대항은 x+y+z'입니다.
이에 따라 위의 논리식을 최대항 전개하면 f=(x+y+z)(x+y'+z)(x'+y'+z)라는 표현식을 얻을 수 있습니다. 이번에는 또 이게 뭔가 싶고, 이해가 잘 안 될 수 있는데요, 또 자세히 설명드리겠습니다.
최대항 전개는 합의 곱으로 표현해야 하므로, 0이 되는 최대항을 모두 AND 연산하면 f와 논리적 동치가 됩니다. 합의 곱으로 표현한 모든 최대항이 1이 아니라면 최대항 전개식의 값은 0이고, 그때는 f의 값 역시 0입니다.
예를 들어 x=0, y=0, z=0일 때를 생각해보겠습니다. f=xy'+z=0·1+0=0입니다. f=(x+y+z)(x+y'+z)(x'+y'+z)=(0+0+0)·1·1=0이므로 서로 같은 결과임을 알 수 있습니다. 이해가 어렵다면 다른 경우에 대해서도 값을 넣어 비교해보면 좋을 것 같습니다. 이번에도 이해를 돕도록 불 대수 법칙으로 증명을 남겨놓았습니다.
pf)
f=(x+y+z)(x+y'+z)(x'+y'+z)
=(x+xy'+xz+yx+yz+xz+y'z+z)(x'+y'+z) (by Absorption Laws : x+xy=x)
=(x+z)(x'+y'+z)
=xy'+xz+x'z+y'z+z (by Absorption Laws : x+xy=x)
=xy'+z
앞선 사례와 같이, 최대항 전개식을 일일이 다 쓰면 복잡하므로, 위에 표 좌측에 있는 번호를 표기하여 다음과 같이 표현합니다.
f=ΠM(0,2,6)
※ x, y, z의 값이 위의 진리표와 같아야 합니다.
표준형 (Standard form/Normal form)
표준형은 정규형의 식을 곱의 합이나 합의 곱 형태를 유지하며 간소화한 것을 의미합니다. f=(x+y+z)(x+y'+z)(x'+y'+z)가 정규형이라면, f=xy'+z는 표준형입니다. 간소화 과정은 이후 포스팅에서 자세히 다루도록 하겠습니다.
이제 기본적인 정규형 내용을 모두 공부했으니, SOP에서 POS로, 또는 POS에서 SOP로 바꾸는 방법에 대해 알아보겠습니다.
※ 표준형을 영어로는 주로 standard form이라고 하는 것 같으나 normal form이라는 용어도 사용하는 것 같습니다.
곱의 합(SOP) -> 합의 곱(POS)
먼저 SOP에서 POS로 바꾸는 방법입니다. 조금 이해가 어려울 수 있지만, 같이 살펴봅시다. 불 대수에서는 덧셈(OR)에도 분배법칙이 성립하므로 다음과 같은 식이 성립합니다.
f=ab+cd
=(a+c)(a+d)(b+c)(b+d)
즉, SOP에 곱셈 전개하듯이 덧셈을 전개하여 분배법칙을 적용해주면 POS가 됩니다.
합의 곱(POS) -> 곱의 합(SOP)
이번에는 POS에서 SOP로 바꾸는 방법입니다. 이번에는 곱셈(AND)의 분배법칙을 이용하면 됩니다.
f=(a+b)(c+d)
=ac+ad+bc+bd
일반 분배법칙과 같아 쉽게 이해할 수 있습니다. 그대로 적용하면 POS를 SOP로 만들 수 있습니다.
사실 지금 여기에서는 설명을 위해 간단하게 2개의 항으로만 구성된 표준형을 예로 들었는데요, 실제 정규형에 항이 많으면 바꿀 때, 계산이 무척 많고 복잡합니다. 가급적이면 최소/최대항을 통해 한 번에 식을 구하는 것을 추천드립니다.
정규형에 대해 알아봤는데, 어떠셨나요? 저는 여기부터 조금 어렵다는 생각이 들었습니다. 힘들지만 계속 공부해 나갑시다! 앞으로 계속 회로 만들다 보면 오늘 배운 내용이 점점 익숙해질 것입니다.
다음번에는 정규형을 표준형으로 만드는 간소화에 대해 다뤄보겠습니다. 그전에 가볍게 NAND/NOR로 회로 구성하는 법을 소개할 예정입니다.
직접 조사해서 작성하는 글이다 보니 일부 정확하지 않은 정보가 포함되어 있을 수 있습니다.
궁금한 사항이나 잘못된 내용이 있으면 댓글로 알려주세요~
구독과 좋아요, 환영합니다!
'컴퓨터 이론 > 컴퓨터 구성' 카테고리의 다른 글
| [컴퓨터 구성] #6 카르노 맵 (Karnaugh Map)과 식 간소화 (2) | 2022.08.20 |
|---|---|
| [컴퓨터 구성] #5 NAND/NOR로 정규형(표준형) 회로 설계하기 (0) | 2022.06.21 |
| [컴퓨터 구성] #3 불 대수(Boolean Algebra)와 기본 법칙 (0) | 2022.03.23 |
| [컴퓨터 구성] #2 완전 집합(Complete Set) (0) | 2022.03.16 |
| [컴퓨터 구성] #1 논리 게이트(Logic Gates) (0) | 2022.03.09 |