K-map
k-map 의 작성방법은 truth table 에 입력된 값을 토대로 들어가는 인자들을 x축과 y축의 인자에 채워 놓은 후에 그의 결과값들을 테이블에 채워 넣는다.
위와 같이 만들 수 있다.
그리고 위에 보이는 식과 같이 circle을 묶어서 각각의 값들을 더해서 최적화된 회로를 작성 할 수 있다.
트루스 테이블에서 각각으로 sop를 한 값과 동일하다.
위 처럼 겹치게 묶어도 가능하다. 이 k-map의 원리는 circle로 묶게 되면 입력이 1, 0 둘다 들어와도 성립하는 인수들을 제거하고 1이나 0만이 들어와야하는 인수들만을 묶어서 식을 작성할 수 있다.
따라서 k-map의 위의 인수를 배치 할때에는 00, 01, 11, 10 이런 식으로 하나의 인수만 변경되도록 배치하여야 한다. 따라서 각각의 표의 가장자리끼리도 만난다고 할 수 있다.
따라서 위처럼 생각할 수 있다.
지금 까지는 최대 4개의 인수만을 가지는 k-map을 살펴보았다. 하지만 4개를 넘어가게 되면 케이스가 너무 많아져서 3차원으로 맵을 표현해야 한다는 단점이 있다.
k-map에서 사용하는 용어들을 알아 보자
literal - 변수 ex) a, a', b, b', c, c'
implicant - circle로 묶은 것들을 implicant 라고한다.
prime implicant - 최대한 크게 묶은것 들을 뜻한다.
essential prime implicant - prime implicant 중에서 대체가 불가능한 무조건 포함되어야 하는 circle 이다.
none essential prime implicant - 다른 prime implicant 들로 커버가 가능한 경우이다.
k-map에서 circle 로 묶을 때에는 우선 1,2,4,8, ... 의 개수로 묶어야 식의 최소화가가능하다.
그리고 implicant 들을 택할 때에는 우선 출력 값을 다 포함하는 지를 보아야한다.
따라서 essential prime implicant 를 배치한 후에 나머지 덮을 부분들을 none essential prime implicant를 비용이 가장 적게 드는 방향으로 택해야 한다. 이때의 요령은 최대한 prime implicant 를 크게, 적게 묶어야한다.
비용의 계산 방법은 논리회로의 입력값의 개수와 출력값 개수인 1을 더한 값이다.
예를 들어 ab' + bc + b'c'이 있을때 각각의 논리곱의 비용은 2 + 1 = 3, 그리고 이 논리곱이 3개이므로 총 9 에다가 전체를 묶어주는 논리합 3 + 1 = 4로 총 비용은 9 + 4 = 13 이다.
비용에 따라서 sop나 pos 중 선택하여 표현할 수 있다.