카노 맵 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:K-map 6,8,9,10,11,12,13,14 anti-race.svg|섬네일|카르노 맵의 예]]
'''카르노 맵'''({{llang|en|Karnaugh map}}, 간단히 '''K-map''')은 [[논리 회로]] 용어로,  [[불 대수]] 위의 [[함수]]를 단순화하는 방법이다. 불 대수에서 확장된 논리 표현을 사람의 패턴인식에 의해 연관된 상호관계를 이용하여 줄이는 방법이다.

== 예시 ==
카르노도는 [[불 대수]]를 편리하게 단순화하는 방법을 제공한다. 설계대상이 요구하는 입력과 출력의 관계를 [[진리표]]로 표현하고 이것으로부터 카르노 맵을 그린다.

{| class="wikitable" style="text-align: center"
|+ 논리 기능의 진리표
|-
! &nbsp; !! ''A'' !! ''B'' !! ''C'' !! ''D'' !! ''f(A, B, C, D)''
|-
! scope="row" | 0
| 0 || 0 || 0 || 0 || 0
|-
! scope="row" | 1
| 0 || 0 || 0 || 1 || 0
|-
! scope="row" | 2
| 0 || 0 || 1 || 0 || 0
|-
! scope="row" | 3
| 0 || 0 || 1 || 1 || 0
|-
! scope="row" | 4
| 0 || 1 || 0 || 0 || 0
|-
! scope="row" | 5
| 0 || 1 || 0 || 1 || 0
|-
! scope="row" | 6
| 0 || 1 || 1 || 0 || 1
|-
! scope="row" | 7
| 0 || 1 || 1 || 1 || 0
|-
! scope="row" | 8
| 1 || 0 || 0 || 0 || 1
|-
! scope="row" | 9
| 1 || 0 || 0 || 1 || 1
|-
! scope="row" | 10
| 1 || 0 || 1 || 0 || 1
|-
! scope="row" | 11
| 1 || 0 || 1 || 1 || 1
|-
! scope="row" | 12
| 1 || 1 || 0 || 0 || 1
|-
! scope="row" | 13
| 1 || 1 || 0 || 1 || 1
|-
! scope="row" | 14
| 1 || 1 || 1 || 0 || 1
|-
! scope="row" | 15
| 1 || 1 || 1 || 1 || 0
|}

단순화 되지 않은 불대수 표현에서 불 변수<math>A</math>, <math>B</math>, <math>C</math>, <math>D</math>에 대해:

*<math>f(A, B, C, D) = \sum_{}(6, 8, 9, 10, 11, 12, 13, 14)</math>

여기서 <math>\sum_{}</math>안의 숫자는 [[최소항 전개]](minterm)의 진리표에서 출력이 1이다.

출력 1인 각각의 최소항들을 모두 표시하면:
*<math>f(A, B, C, D) = (\overline{A}BC\overline{D}) + (A\overline{B}\,\overline{C}\,\overline{D}) + (A\overline{B}\,\overline{C}D) + (A\overline{B}C\overline{D}) + (A\overline{B}CD) + (AB\overline{C}\,\overline{D}) + (AB\overline{C}D) + (ABC\overline{D})</math>

이것은 단순화되지 않는 불대수이다.

=== 카노 맵 ===
카노 맵은 입력변수와 출력을 도식화 하고, 같은 출력의 패턴을 찾아 묶음으로 단순화 한다. 배치에서 변수의 값이 변하도록 서로 묶이도록 배치한다.
[[파일:K-map_minterms_A.svg|섬네일|350px|center|K-map construction.]]

이것을 진리표의 출력값을 배치하면:
[[파일:K-map_6,8,9,10,11,12,13,14.svg|섬네일|350px|center|K-map에서 최소항들은 컬러상자로 표시한다. 갈색은 겹친영역이고, 빨간도식은 2×2 그리고 녹색은 4×1.]]

서로 이웃의 출력끼리 묶어 상자를 만든다. 만약 X가 존재하다면 출력 0이든 1이든 어디에도 포함할 수 있다.

=== 단순화 ===
출력 1을 기준으로 단순화 하면

빨간상자는:
*변수 ''A''가 1일 때 1로 출력된다. 따라서 그대로 포함된다.

결국 곱의합(sum-of-products expression) 표현으로 표시하면 <math>A\overline{C}</math>.

같은 방법으로 녹색상자는 ''A''와 ''B''가 유지되고, ''C''는 ''D'' 배제된다. ''B''는 0일 때 1로, 보수로 출력이 나타난다.
<math>A\overline{B}</math>.

파란상자는 <math>BC\overline{D}</math>.

출력 1이 모두 포함하도록 각각의 상자를 위와 같이 표현하고 모두 곱의합형태로 나타내면 단순화 된 결과가 된다:

<math>A\overline{C} + A\overline{B} + BC\overline{D}</math>.

전체 단순화되지 않는 식:

<math>f(A, B, C, D) = (\overline{A}BC\overline{D}) + (A\overline{B}\,\overline{C}\,\overline{D}) + (A\overline{B}\,\overline{C}D) + (A\overline{B}C\overline{D}) + (A\overline{B}CD) + (AB\overline{C}\,\overline{D}) + (AB\overline{C}D) + (ABC\overline{D})</math>

이것을 카노 맵으로 단순화 하면:

<math>f(A, B, C, D) = A\overline{C} + A\overline{B} + BC\overline{D}</math>

===역함수===
역함수를 구하기 위해서는 1대신 0으로 묶음상자를 만든다.

위와 같은 방법으로:
*갈색상자—<math>\overline{A}\,\overline{B}</math>
*금색상자—<math>\overline{A}\,\overline{C}</math>
*파란상자—<math>BCD</math>

역함수로 표시하면:
:<math>\overline{F} = \overline{A}\,\overline{B} + \overline{A}\,\overline{C} + BCD</math>

[[드 모르간의 법칙]](De Morgan's laws)을 적용하여 합의 곱(product of sums)으로 표시하면:
:<math>\overline{\overline{F}} = \overline{ \overline{A}\,\overline{B} + \overline{A}\,\overline{C} + BCD }</math>
:<math>F = \left(A + B\right)\left(A + C\right)\left(\overline{B} + \overline{C} + \overline{D}\right)</math>

== 같이 보기 ==
* [[수리 논리학]]

[[분류:수리논리학]]
[[분류:디지털 전자공학]]