[논리 회로] 6장. 논리식의 간소화
본 내용은 2024년 1학기 '컴퓨터논리개론' 수업을 들으며 노션에다가 정리한 글을 옮겨온 포스트입니다.
제 공부를 위해 작성한 거라서 제가 알아보기 편하게 정리했습니다. 여러분들도 자유자재로 열람 가능하지만 간혹 이해하기 힘든 부분이 있을 수도 있다는 점 양해 부탁드립니다!
(1) 2변수 카르노 맵
앞 장에서는 불 대수로 논리식을 간소화하는 과정을 배웠었는데, 사실 이건 복잡하기도 하고 해서 더 빠른 간소화 방법인 카르노 맵과 퀸-맥클러스키 방법 등이 있음. 일단 카르노 맵 부터!
카르노 맵
함수에서 사용할 최소항들을 각 칸 안에 넣어서 표로 만들어 놓은 것.
2변수일 때에는 4칸, 3변수일 때는 8칸, 4변수일 때는 16칸, …
함수의 출력이 1이 되는 최소항의 카르노 맵에 1을 넣고, 나머지 빈 곳은 비우거나 0으로 채우는데 일반적으로는 비운다.
무관항: 입력값이 0이어도 되고 1이어도 되는, 즉 입력이 결과에 영향을 미치지 않는 최소항. 무관항은 차후 BCD 코드를 다른 형태로 변환할 때 자주 등장할 것…
이 카르노 맵을 묶어서 논리식을 간소화할 수 있다.
카르노 맵을 묶을 때의 규칙은 다음과 같다.
- 출력이 같은 항을 1, 2, 4, 8, 16개로 그룹을 지어 묶는다.
- 바로 이웃한 항들끼리 묶는다.
- 반드시 직사각형이나 정사각형의 형태로 묵어야 한다.
- 최대한 크게 묶는다.
- 중복하여 묶어서 간소화된다면 중복하여 묶는다.
- 무관항의 경우 간소화될 수 있으면 묶어 주고, 그렇지 않으면 묶지 않는다.
같게 묶인다면(하나의 변수가 0만 혹은 1만 묶이면) 남기고, 다르게 묶인다면(하나의 변수가 0과 1이 함께 묶이는 경우) 그 변수는 제거한다.
이렇게 논리식으로 주어지지 않고 진리표로 주어지는 경우에도 카르노 맵으로 나타낼 수 있다. 출력이 1인 것만 표시해주면 되는 것!
(2) 3변수 카르노 맵
3변수 카르노 맵은 사실 막 그리면 여러 가지 형태가 나올 수 있다… → 순서를 정확히 해야 함! 00 01 11 10 순서로 해야 하는데, 즉 이웃하는 항들의 차이가 한 비트만 되도록 해야 한다!
주로 이러한 형태들으로 사용할 수 있는데, 일반적으로는 (b)처럼 사용한다.
이것도 간소화하는 방법은 2변수 카르노 맵과 동일함. 같은 게 남으면 남기고, 다르게 남으면 제거하는 것.
그런데 유의할 점은, 양 쪽 사이드에 1이 있다면 그건 원통 느낌으로 서로 묶을 수 있다는 것!!
저렇게 묶어도 이웃항은 비트가 한 자릿수만 차이나므로 가능한 것…
2개가 아니라 4개를 묶을 수도 있다!
그리고 모든 값이 이미 다른 묶음들에 포함되어 있다면, 굳이 중복해서 묶을 필요가 없다.
중요한 건, 묶을 수 있을 만큼 가장 크게 묶어야 된다는 것임!! 작게 묶는다면 최소로 간소화되게 표현할 수 없다!
물론 이것도 진리표를 가지고 3변수 카르노 맵을 만들 수도 있다!
3변수 카르노 맵에서 묶을 것이 하나도 없으면 논리식은 F=0이고, 8개 모두를 묶을 수 있으면 F=1이다.
(3) 4변수 카르노맵
4변수 카르노 맵도 앞에서 봤던 카르노 맵들이랑 똑같음! 00 01 11 10 이 순서만 잘 지켜서 가로 세로로 배치하면 됨!
(4) 선택적 카르노 맵
카르노 맵은, 어떻게 묶냐에 따라서 다양한 간소화 식이 나타날 수 있다.
(5) 논리식의 카르노 맵 작성
논리식을 카르노 맵으로 바꾸기 위해서는, 모두 최소항으로 바꿔서 나타내면 된다. 이 때, 생략된 항도 모두 찾아 최소항으로 바꿔야 한다!
(6) 5변수, 6변수 카르노 맵
4변수 까지는 그럭저럭 할 만 한데… 5변수와 6변수는 조금 복잡해질 수도 있다. 왜냐하면, 바로 입체감(?)을 더해야 하기 때문!!
(7) 퀸-맥클로스키 간소화 알고리즘
입력 변수가 5개 이상이 되면 카르노 맵은 너무 복잡해진다… 그래서 입력 변수가 5개 이상인 경우에는 카르노 맵보다 퀸-맥클러스키(QM) 알고리즘이 더 유용함!
- 많은 변수에 대해서도 쉽게 간소화할 수 있다.
- 컴퓨터 알고리즘으로 개발하기에 적합하다.
QM 알고리즘은 표를 이용하며, 최종 결과는 SOP식으로 만들어진다.
- 첫 번째 단계: 𝐴𝐵𝐶+𝐴𝐵𝐶ˉ=𝐴𝐵(𝐶+𝐶ˉ)=𝐴𝐵∗1=𝐴𝐵 법칙을 적용하여 변수를 하나씩 제거해 나가는 단계.
- 두 번째 단계: 차트를 이용해 최종 논리식을 구하는 단계.
더 구체적인 과정은 다음과 같다.
1. 최소항을 2진 형태로 표현하여 1의 개수에 따라 인덱스를 매기고 재배열
이런 식으로 하면 된다. 논리식이 주어진 경우에는, 해당 식의 진리표를 구한 다음 출력이 1인 항만을 인덱스 별로 분류하여 QM표를 만들면 된다.
2. QM 알고리즘을 이용한 간소화
이 표를 이용해서 항을 결합하며 식을 간소화해나가면 된다. 즉 QM표에서 인적한 인덱스에 속한 항들끼리 비교하여 한 비트만 다른 항들을 결합하는 것!
- 000과 001은 LSB 1비트만 다르므로 이를 간소화하여 QM표에서 00-로 표시.
- 010과 110은 MSB 1비트만 다르므로 이를 간소화하여 QM표에서 -10으로 표시.
→ 이렇게 하나씩 항들을 줄여서 더 이상 줄일 항들이 없을 때까지 줄여 나가면 된다!
n번째 칼럼에서 결합이 된 항들은 체크 표시를 하고, n+1번째 칼럼에는 결합해서 나타내면 됨
(8) 여러 개의 출력 함수
실제 디지털 시스템에서는 출력이 여러 개 필요한 경우가 많이 있다.
이런 경우에는, (a)처럼 해도 되지만 (b)처럼 하나로 합치면 경제적으로도 효율적인 시스템이 된다.
우리도 우리에게 주어진 논리 함수들을 하나의 시스템으로 통합할 수 있다. 각 논리함수에 해당하는 카르노 맵을 그려서, 겹치는 항이 있으면 그걸로 통합할 수 있음.
아래는 3변수 예시!
4변수의 경우에도 비슷하게 해주면 된다.
- 각 카르노 맵에서 독립적으로 가장 크게 묶을 수 있는 영역을 묶음
- 남은 부분에서 나머지를 묶음
두 개의 함수가 무관항을 가지고 있는 경우에도, 비슷하게 해주면 된다. 필요에 따라 무관항을 묶거나, 묶지 않으면 됨!
