정보처리기사전자계산기 구조

카르노 도표(KARNAUGH MAP)

⏱ 읽기 소요 시간: 5 분

부울함수의 간소화 방법 중의 하나인 카르노 도표(KARNAUGH MAP)에 대해 알아봅시다.

카르노 도표 방법

  • 카르노 도표는 여러 개의 사각형으로 된 다이어그램
  • 사각형은 각각 하나의 최소항이나 최대항을 의미
  • 여섯 개 이하의 변수를 가진 부울함수에 사용
  • 카르노 도표는 부울함수의 입력변수의 수에 따라서 기본 도표의 형태가 결정됨

  • 입력변수의 수가 n인 경우를 n변수 카르노 도표라고 하며, 2^n개의 사각형으로 구성됨

  • 카르노 도표를 이용하면, 정규형 부울 함수 -> 표준형 부울함수로 간소화할 수 있음

  • 카르노 도표를 이용해서 부울함수의 각 항들을 곱이나 합 형태로 간소화

  1. 최소항의 합 -> 곱의 합
  2. 최대항의 곱 -> 합의 곱 형태로 간소화 됨

최소항의 합형을 곱의 합형으로 간소화하는 순서

  1. 입력변수의 수 n에 따라 n변수 카르노 도표 작성(도표는 2^n개의 정사각형)

  2. 최소항의 인덱스에 대응되는 사각형을 1로 표시

  3. 1로 표시된 사각형들 중 서로 인접한 사각형끼리 묶음

(주의! 이때 한 묶음은 크게, 전체 묶음의 수는 적게 묶는다.)

  1. 각 묶음이 입력변수 각각에 대해 도표상의 어떤 위치에 있는지 파악

  1. 4)에서 구한 각 묶음에 대한 곱항들을 논리합(OR)으로 연결시키면, 간소화된 표준형(곱의 합형)이 구해진다.

최대항의 곱형을 합의 곱형으로 간소화하는 순서

  1. 입력변수의 수 n에 따라 n변수 카르노 도표 작성(도표는 2^n개의 정사각형)

  2. 최소항의 인덱스에 대응되는 사각형을 0으로 표시

  3. 0으로 표시된 사각형들 중 서로 인접한 사각형끼리 묶음

(주의! 이때 한 묶음은 크게, 전체 묶음의 수는 적게 묶는다.)

  1. 각 묶음이 입력변수 각각에 대해 도표상의 어떤 위치에 있는지 파악

  1. 4)에서 구한 각 묶음에 대한 합항들을 논리곱(AND)으로 연결시키면, 간소화된 표준형(합의 곱형)이 구해진다.

인접 사각형의 정의

  • 카르노 도표에서 각 정사각형은 하나의 최소항(또는 최대항)을 의미
  • 따라서, 인접 사각형이란

    두 정사각형에 대응되는 각 최소항(또는 최대항)의 구성변수 중
    다른 모든 변수는 동일하되 오직 하나의 변수만 서로 보수관계에 있을 때
    두 정사각형은 서로 인접한다”라고 정의

ex) 입력변수가 X, Y, Z 3개의 경우

인접 사각형끼리 묶는 방법

  1. 한 묶음 내의 정사각형의 수는 2^n(n = 0, 1, 2... n)개가 되도록 묶는다.

  2. 한 묶음은 크게, 전체 묶음의 수는 적게 묶는다.

Share