목차
1. Q-M 방법 <Quine - McClusky 알고리즘>
지난번까지 저희는 카르노 맵을 만드는 방법을 배웠습니다.
하지만, 카르노맵의 문제점은 5변수부터입니다.
이를 해결하려고 미세하게나마 나온 방법이 Q-M 방법이 되시겠습니다.
길게 말할것 없이 바로 예제로 알아보도록 하겠습니다.
1-1. Q-M 방법 첫번째 <그룹으로 나눠라!>
\(f = \sum m(0,1,2,5,6,7,8,9,10,14)\)을 간소화 하시오
이 문제는 카르노맵으로도 풀수 있지만 이번에는 한번 Q-M 방법을 써보도록 합시다.
먼저, 카르노맵을 한번 볼까요?
여기서 m0는 (0,0,0,0)을 나타냅니다. 맞죠?
m1은 (0,0,0,1)을 나타냅니다.
m2는 (0,0,1,0)을 나타냅니다.
m3는 (0,0,1,1)을 나타냅니다.
이를 쭉 풀어 쓰면 아래와 같은 표가 나옵니다.
그리고 위의 예제를 골라내면 다음과 같습니다.
자, 이제부터가 중요합니다.
빨간색 칸에 있는 2진코드에서 1의 갯수가 몇개인지에 따라서 나눌 계획입니다.
그러니까 1의 갯수가 하나인 경우는 10진법의 숫자로 1,2,8이 있잖아요.
1은 \((0,0,0,1)\), 2는 \((0,0,1,0)\), 8은 \((1,0,0,0)\)인데 보면 1이 전부 하나씩 있습니다.
1의 갯수가 두개인 경우는 5,6,9,10이 있고요.
5는 \((0,1,0,1)\), 6은 \((0,1,1,0)\), 9는 \((1,0,0,1)\), 10은 \((1,0,1,0)\)으로 1이 두개씩 있습니다.
1의 갯수가 3개인 경우는 7과 14가 있습니다.
7은 \((0,1,1,1)\) , 14는 \((1,1,1,0)\)으로 1이 3개씩 존재합니다.
이를 정리해보면 아래 그림처럼 나옵니다.
1-2. Q-M 방법 두번째 <인접한 그룹끼리 묶어라!>
그리고 각자 인접한 그룹끼리 한번 묶어봅시다.
그러니까 Group 0과 Group 1을 묶어보자 이겁니다.
한번 아래의 그림을 봅시다.
여기서 보시면 세자리수는 0으로 같은데 한자리수만 다른점이 보일겁니다.
왜 그렇냐면 아까 위에서 그룹을 묶었을때 1의 갯수가 몇개냐에 따라 그룹을 나눴기 때문입니다.
그래서 이렇게 같은 자리에 같은 숫자가 있는것은 아래로 그대로 내리고 다른경우만 X로 표시합니다.
그럼 이번에는 그룹1과 그룹2를 비교해봅시다.
이번에도 자리와 숫자가 동시에 같은것은 그대로 내리고 다른것은 X로 그리면 위의 그림대로 그려집니다.
빨간색 상자를 제외한 나머지는 자리에 숫자가 똑같습니다. 반면 빨간색 상자는 다르죠.
그룹2와 그룹3도 다음과 같이 그려질것입니다. 이를 정리하면 아래와 같습니다.
또 이번에도! 인접한 그룹끼리 한번 묶어봅시다.
이번에도 같은 자리에 같은 숫자는 그대로 내리고 다른 숫자만 X로 표기합니다.
(여기서 중요한것은 2개씩 묶었을때 나왔던 X있죠? 이 X도 같은 자리에 있는지가 중요합니다!)
그래서 이를 또 정리하면 다음과 같습니다.
1-3. Q-M 방법 세번째 <소거해라!>
이제는 위에서 그룹을 묶어둔 녀석들을 소거할 차례입니다.
소거를 하는 이유는 Prime Implicant 즉 주항을 찾기 위해서입니다.
먼저, 가장 마지막에 했던 4개의 그룹을 보도록 합시다.
\((0,1,8,9)\)는 \(X 00X \), \( (0,8,1,9) \) 는 \( X00 X \) 로 실질적으로는 같습니다.
또한, \( (0,2,8,10) \) 는 \( X 0X0 \), \( (0,8,2,10) \) 는 \( X0 X 0 \) 로 실질적으로는 같습니다.
마지막으로, \( (2,6,10,14) \) 는 \( X X10 \) ,\( (0,8,1,9) \) 는 \( X X 10 \) 로 같으니까 소거합니다.
그렇게 소거하면 \((0,1,8,9)\), \( (0,2,8,10) \), \( (2,6,10,14) \)로 정리가 됩니다.
그리고 이번에는 2개씩 묶은 그룹들을 소거해봅시다.
위 그림에서 보다시피
\((0,1)\) ,\((8,9)\) ,\((0,2)\) ,\((8,10)\) ,\((0,8)\) ,\((1,9)\) ,\((0,8)\) ,\((2,10)\) ,\((2,6)\) ,\((10,14)\) ,\((2,10)\) ,\((6,14)\)가 쓰였습니다.
쓰였던 요소들을 전부 소거합시다.
그렇게 남은 요소들을 정리하면 아래와 같습니다.
위에서도 이야기했지만 이렇게 남은 요소들이 바로 Implicant입니다.
1-4. Q-M 방법 네번째 <차트를 그려라!>
차트를 그리는 이유는 바로 Essential Prime Implicant 즉 필수주항을 찾기 위함입니다.
백문이 불여일견이라고 바로 차트를 그려봅시다.
먼저 상단에는 보시다시피 m0,m1,m2들을 쭉 그리고 세로는 주항을 적어놓습니다.
그리고 각각에 해당하는 숫자들에 X표시를 합니다.
여기까지는 직관적이라 따로 설명이 필요 없겟죠? ㅎㅎ
이제부터 중요합니다.
빨간색 동그라미 친 부분을 보시면 아시겟지만 9와 14는 딱 한번만 X표시가 되어있는 걸 볼 수 있습니다.
나머지는 전부 한번씩은 중복이 된다는게 보이죠?
빨간색 동그라미 친 부분이 바로 EPI, 필수주항입니다.
위의 그림처럼 먼저 빨간 동그라미로 친 부분을 줄을 싹 그어버립시다!
자 그리고 초록색 동그라미 친 부분이 보일텐데 빨간색 줄에 걸린 X표시입니다.
이 친구들은 세로로 쭈욱 그어버립시다.
이제 생존자는 아래의 그림처럼 나올겁니다.
그림에도 적혀있다시피 소거된 부분이 존재하기에(초록색 줄) 생존자는 \((5,7)\)이 되며 이것이 바로 PI입니다.
1-5. Q-M 방법 마지막 <식 정리하기>
이제 위에서 얻은 결과들을 조합하여 식을 정리하면 됩니다.
\((0,1,8,9)\),\((2,6,10,14)\),\((5,7)\)로 요약이 되는데 말입니다.
\((0,1,8,9)\)는 X00X로 나타낼 수 있습니다. 맞죠?
잠시 위의 카르노맵을 들고와봅시다.
이런식으로 그릴수 있습니다. 맞죠?
고로, B'C'으로 요약을 할 수 있습니다.
같은 원리로 \((2,6,10,14)\)는 CD'으로 대수적으로 풀이가 가능합니다.
같은 원리로 \((5,7)\) 는 A'BD로 대수적으로 풀이가 가능합니다.
최종적으로 정리하면 \(F= B'C' + CD' + A'BD \)입니다.
2. 요약정리
방법 자체는 복잡하지만, 5변수부터는 Q-M방법을 쓰는편이 좋습니다.
한번 요약을 해보도록 하겠습니다.
- 그룹을 나눠라! 그룹을 나누는데 있어서 1의 갯수에 따른 기준으로 나눌것!
- 인접한 그룹끼리 묶어라! 그룹끼리 묶을때에는 자리와 숫자가 전부 같아야 한다. 명심하자!
- 중복과 사용했던 요소들을 차근차근 없애라! 남은 요소가 바로 PI이다!
- 차트를 그려서 EPI를 거르자! EPI를 거를때에는 X표시가 딱 한번만 되어있는 숫자가 포함된 녀석이 EPI이다!
- 차트에서 살아남은 최종 승자가 바로 PI이다.
'CS 이론 > 디지털 논리회로' 카테고리의 다른 글
| 디지털 논리회로 10부<Parity Bit와 해밍코드> (0) | 2024.02.14 |
|---|---|
| 디지털 논리회로 9부 <NAND,NOR,XOR 게이트> (0) | 2024.02.14 |
| 디지털 논리회로 7부<카르노맵 Implicant> (0) | 2024.01.30 |
| 디지털 논리회로 6부<카르노맵 4변수> (0) | 2024.01.30 |
| 디지털 논리회로 5부<카르노 맵 2,3변수> (0) | 2024.01.29 |
