논리회로 Ch5. 카르노 맵

Alpha, Orderly·2023년 3월 15일
0

논리회로

목록 보기
5/12
post-thumbnail
post-custom-banner

Switching function의 최소 형태

  • Function의 비용은 AND/OR과 같은 게이트를 덜 쓰고 입력을 덜 받는 형태이다.
  • 카르노 맵을 통해 AND/OR 게이트로 만드는 최소-비용 회로의 구성이 가능하다.
  • Minimum sum-of-product 혹은 Minimum product-of-sum의 형태를 구할수 있다.

Minimum sum-of-product

  1. 항의 갯수가 최소이다.
  2. 동일한 항의 갯수에 대해선 각각의 항이 최소한의 변수를 가진다.
  • 한가지 Function 에 대해 여러개의 Minimum sum-of-product가 있을수 있다.

카르노 맵

  • 기본적으로 여러개의 minterm이나 maxterm을 하나로 묶는것
  • abcd+abcd=abc.ab'cd' + ab'cd = ab'c.
    .는 없어지는 부분을 의미한다.
  • abc+abc=a.cab'c + abc = a.c
  • 두개의 term에 대해 1비트가 complement관계일시 이를 합치고 complement인 literal을 없앨수 있다.

2/3 변수 카르노 맵

2-변수 카르노맵

  • 각각의 cell에 truth table의 값을 넣는다.

  • 이후 2n2^n 개의 직사각형으로 1을 묶어준다.

  • 이후 묶여진 직사각형 범위에서 값이 바뀌지 않는 것을 기준으로 직사각형 하나마다 minterm을 만든다.

  • 왼쪽 위 항은 A=0이고 B=0일때의 output을 의미한다.

줄이는 법

  • 1을 output으로 가지는 cell을 직사각형으로 2n2^n개 묶고, 두 cell이 동일한 input을 가지는것에 한정해 minterm으로 바꾼다.
  • 위 경우 B는 0과 1의 경우지만, 두 경우 A는 0이기 때문에 AA'이 된다.
  • 최대한 크게 합칠수록 term을 더 줄일수 있다.

3-변수 카르노맵

  • 하지만 BC의 순서가 00, 01, 11, 10인데 이는 비트가 하나씩만 바뀌도록 하기 위함이다.

  • 카르노맵은 앞뒤 좌우가 연결되어있다고 가정하고, 각각의 사각형이 겹쳐도 된다.


4변수 카르노 맵

  • 3변수와 동일하되 4 * 4의 형태를 가진다.


최소 표현 찾아내기

  • minterm 표현을 받았을때 바로 카르노 맵을 그릴수 있다.

카르노 맵에서의 Don't care term

  • 해당하는 minterm에 X 표시하기.

  • 2n2^n 직사각형에 포함되거나 포함되지 않을수 있다.
  • 꼭 포함되어야 하진 않는다.

Minimum product of sum

바로 찾기

  • 0이 되는 부분을 2n2^n으로 묶어서 찾는다.
  • 0이 되도록 maxterm을 찾으면 된다.

Complement

  • ff'의 minimum sum of product 를 찾기
  • 찾아진 sum of product에 complement를 취해 드모르간 법칙을 이용, 이를 product of sum으로 변환한다.
sum of product 나 product of sum 형태 중 gate를 적게 쓰는쪽(항의 갯수가 적다) 이 더 좋다.

Implicant of F

  • 카르노맵에서 11이거나 112n2^n개가 묶인 직사각형의 그룹
  • 2n2^n 개의 11로 이루어질수 있다.

Prime Implicant

  • 더이상 다른 Implicant와 합쳐질수 없는 Implicant이다.
  • 만들수 있는 가장 큰 Implicant들중 하나이다.

특정 minterm이 오직 특정한 1개의 prime implicant에 의해 정의 될시, 그 prime implicant는 essential 하다.
Essential Prime Implicant : EPI
반드시 포함되는 Implicant


5변수 카르노 맵

  • 대각선을 이용해 표현한다!
  • 대각선 기준 왼쪽이 1, 오른쪽이 0이다.
  • 대각선에는 A / 첫번째 Literal 이 들어간다.'


다른 카르노맵의 용도

f=Σm(0,2,3,4,8,10,11,15)f = \Sigma m(0, 2, 3, 4, 8, 10, 11, 15) 와 같은 minterm expansion을 쉽게 줄여 표현할수 있다.


다른 형태의 카르노맵


profile
만능 컴덕후 겸 번지 팬
post-custom-banner

0개의 댓글