카노 맵

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 구성 및 활용
- 3.1. 예시
- 3.2. 경쟁 위험 (Race Hazard)
4. 관련 방법
5. 추가 정보
참조

1. 개요

카노 맵은 불 대수를 간편하게 단순화하는 시각적 방법으로, 논리 회로 설계를 위해 진리표를 2차원 격자 형태로 표현한다. 인접한 칸은 그레이 코드를 사용하여 하나의 변수 값만 다르도록 배치되며, 출력값을 묶어 논리식을 단순화한다. 카노 맵은 1950년대 모리스 카노에 의해 개발되었으며, 곱의 합(SOP) 또는 합의 곱(POS) 형태로 논리식을 표현하고, 경쟁 상태를 파악하고 제거하는 데에도 활용된다. 베이치 차트, 스보보다 차트, 마호니 맵, 축소 카르노 맵, 민텀 링 맵 등 다양한 관련 방법이 존재한다.

더 읽어볼만한 페이지

디지털 전자공학 - 트랜지스터-트랜지스터 논리
트랜지스터-트랜지스터 논리(TTL)는 1961년 제임스 L. 부이에 의해 발명된 바이폴라 접합 트랜지스터 기반의 디지털 회로 기술로, 텍사스 인스트루먼츠의 7400 시리즈를 통해 널리 사용되었으며, 저렴한 비용으로 디지털 기술 발전에 기여했다.
디지털 전자공학 - 플립플롭
플립플롭은 1비트 이상의 정보를 저장하는 디지털 논리 회로로, 에클스-조던 트리거 회로에서 기원하여 SR, D, T, JK 등 다양한 유형으로 구현되며, 컴퓨터 기억 장치의 기본 구성 요소로 사용되지만 타이밍 요소에 민감하게 설계해야 한다.
수리논리학 - NAND 게이트
NAND 게이트는 모든 입력이 1일 때 0을 출력하고 그 외에는 1을 출력하는 논리 게이트로서, 다양한 기호로 표현되며, AND 연산의 결과를 부정하는 연산을 수행하고, 여러 방식으로 구현될 수 있으며, 기능적으로 완전하여 디지털 회로 설계에 필수적이다.
수리논리학 - 셈
셈은 대상의 개수를 파악하는 기본적인 행위로, 수학에서는 집합의 원소 개수를 파악하는 과정으로 정의되며, 셈의 방식에 따라 결과가 달라질 수 있고, 셈을 배우는 과정은 아동의 교육 및 발달에 중요한 역할을 한다.

카노 맵
개요
2변수 카르노 맵 애니메이션
유형	간략화 방법
고안자	모리스 카르노 에드워드 W. 베이치
상세 정보
목적	부울 대수식을 간소화하는 방법
응용
응용 분야	디지털 논리 단순화
관련 개념
관련 개념	퀸-매클러스키 알고리즘 부울 대수 논리 회로

2. 정의

카르노 맵은 불 대수를 편리하게 단순화하는 방법이다.^[3] 설계 대상이 요구하는 입력과 출력의 관계를 진리표로 표현하고, 이를 바탕으로 카르노 맵을 그린다. 카노 맵은 진리표를 2차원 격자 형태로 재구성하여 시각적으로 표현한 것이다.^[3] 각 격자 칸은 입력 변수들의 특정 조합에 대한 출력값을 나타내며, 인접한 칸은 하나의 변수만 값이 다르도록 배치된다. (그레이 코드 사용)^[5]^[4]

예를 들어, 다음과 같은 진리표를 보자.

논리 기능의 진리표
	A	B	C	D	f(A, B, C, D)
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	0
6	0	1	1	0	1
7	0	1	1	1	0
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0

단순화되지 않은 불 대수 표현은 다음과 같다.

$f(A, B, C, D) = \sum_{}(6, 8, 9, 10, 11, 12, 13, 14)$

이는 최소항들의 합 (Sum of Products, SOP) 형태로, 다음과 같이 표현할 수 있다.

$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})$

카노 맵을 이용하면, 출력값이 같은 칸들을 묶어 시각적으로 논리식을 단순화할 수 있다. 위 진리표를 카노 맵으로 표현하고 인접한 1의 값들을 묶으면, 다음과 같은 결과를 얻을 수 있다.

빨간 상자: $A\overline{C}$
녹색 상자: $A\overline{B}$
파란 상자: $BC\overline{D}$

따라서, 단순화된 논리식은 다음과 같다.

f(A, B, C, D) = A\overline{C} + A\overline{B} + BC\overline{D}

카노 맵은 이와 같이 인간의 패턴 인식 능력을 활용하여 복잡한 부울 표현식을 최소화된 형태로 만들어 준다.^[3] 이를 통해, 논리 게이트를 최소화하여 구현할 수 있다.^[7] 곱의 합 표현식(SOP)은 AND 게이트를 OR 게이트에 연결하여 구현할 수 있으며, 합의 곱 표현식(POS)은 OR 게이트를 AND 게이트에 연결한다.^[7] 카노 맵은 1950년대에 벨 연구소의 모리스 카노(Maurice Karnaugh)에 의해 발명되었다.

3. 구성 및 활용

카노 맵은 진리표를 기반으로 구성되며, 각 칸은 입력 변수의 가능한 조합에 대한 출력 값을 나타낸다. 카노 맵에서 인접한 칸들은 그레이 코드 순서에 따라 배열되어, 단 하나의 입력 변수만 값이 달라지도록 구성된다.

K-map에서 최소항들은 컬러상자로 표시한다. 갈색은 겹친영역이고, 빨간도식은 2×2 그리고 녹색은 4×1.

출력 값이 1인 칸들을 묶어 (SOP), 또는 0인 칸들을 묶어 (POS) 논리식을 단순화한다. 묶음은 2의 거듭제곱 (1, 2, 4, 8, ...) 크기의 직사각형 형태여야 하며, 가능한 가장 큰 크기로 묶어야 한다. "Don't care" 조건 (출력 값이 0이든 1이든 상관없는 입력 조합)을 활용하여 묶음을 더 크게 만들 수 있다.

예를 들어, 빨간 상자는 변수 ''A''가 1일 때 1로 출력되므로

A\overline{C}

로 표현된다. 녹색 상자는 ''A''와 ''B''가 유지되고 ''C''는 ''D''가 배제되므로, ''B''는 0일 때 1로 출력되어

A\overline{B}

로 표현된다. 파란 상자는

BC\overline{D}

이다. 따라서 출력 1을 모두 포함하는 최소항들의 곱의 합(SOP)은

A\overline{C} + A\overline{B} + BC\overline{D}

이다.

전체 단순화되지 않은 식은 다음과 같다.

:

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})

카노 맵을 통해 단순화하면 다음과 같다.

:

f(A, B, C, D) = A\overline{C} + A\overline{B} + BC\overline{D}

0으로 묶어 역함수를 구하고, 드 모르간의 법칙을 적용하면 합의 곱(POS) 형태로 표현할 수 있다.

갈색상자— $\overline{A}\,\overline{B}$
금색상자— $\overline{A}\,\overline{C}$
파란상자— $BCD$

역함수로 표시하면:

:

\overline{F} = \overline{A}\,\overline{B} + \overline{A}\,\overline{C} + BCD

드 모르간의 법칙을 적용하여 합의 곱(product of sums)으로 표시하면:

:

\overline{\overline{F}} = \overline{ \overline{A}\,\overline{B} + \overline{A}\,\overline{C} + BCD }

:

F = \left(A + B\right)\left(A + C\right)\left(\overline{B} + \overline{C} + \overline{D}\right)

"Don't care" 조건을 활용하면, 위 예시에서 ''f''(1,1,1,1)의 값을 "don't care"로 대체하여, 빨간색 항을 확장하고 녹색 항을 제거할 수 있다.

:

f(A,B,C,D) = A + BC\overline{D}

역의 경우는 다음과 같이 단순화된다.

:

\overline{f(A,B,C,D)} = \overline{A}\,\overline{B} + \overline{A}\,\overline{C} + \overline{A}D

드 모르간의 법칙을 통해 합의 곱을 구하면:

:

f(A,B,C,D) = \left(A + B\right)\left(A + C\right)\left(A +\overline{D}\right)

카노 맵은 경쟁 상태를 시각적으로 파악하고 제거하는 데에도 활용될 수 있다.

3. 1. 예시

카노 맵을 이용한 논리식 단순화 예시를 살펴본다.

4개의 입력 변수 (A, B, C, D)를 가진 진리표를 카노 맵으로 변환하여 논리식을 단순화한다. 최소항 전개(Minterm)와 최대항 전개(Maxterm)를 통해 함수를 표현하고, 카르노 맵을 이용하여 시각적으로 단순화한다.^[1] 1로 표시된 칸들을 묶어 곱의 합(SOP) 형태로, 0으로 표시된 칸들을 묶어 합의 곱(POS) 형태로 표현한다. 드 모르간의 법칙을 이용하여 SOP와 POS 표현 간의 변환을 수행할 수 있다.

제시된 예시에서, 단순화되지 않은 불 대수 표현은 다음과 같다.

$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})$

이는

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

로 표현되며, 여기서

\sum_{}

안의 숫자는 최소항 전개(minterm)의 진리표에서 출력이 1인 항을 나타낸다.

역함수의 경우, 0으로 묶어 상자를 만들고, 드 모르간의 법칙을 적용하여 합의 곱(product of sums)으로 표시한다.

:

\overline{\overline{F}} = \overline{ \overline{A}\,\overline{B} + \overline{A}\,\overline{C} + BCD }

:

F = \left(A + B\right)\left(A + C\right)\left(\overline{B} + \overline{C} + \overline{D}\right)

3. 2. 경쟁 위험 (Race Hazard)

카노 맵은 경쟁 상태를 감지하고 제거하는 데 유용하다. 맵에 그려진 인접하지만 분리된 영역 사이를 이동할 때 경쟁 상태가 존재할 수 있다. 하지만 그레이 코드의 특성상, "인접"은 특별한 정의를 가지며, 실제로 사각형이 아닌 토러스에서 이동하므로 상단, 하단, 측면을 둘러싸고 있다.

위의 예시에서, ''C''가 1이고 ''D''가 0일 때, ''A''가 1이고 ''B''가 1에서 0으로 변할 때(파란색 상태에서 녹색 상태로 이동) 잠재적인 경쟁 상태가 존재한다. 이 경우, 출력은 1로 변하지 않도록 정의되어 있지만, 이 전환은 방정식의 특정 항에 의해 포함되지 않으므로, ''글리치''(출력이 잠시 0으로 전환되는 현상)가 발생할 가능성이 있다.

동일한 예시에서 감지하기 더 어려운 두 번째 잠재적 글리치가 있다: ''D''가 0이고 ''A''와 ''B''가 모두 1일 때, C가 1에서 0으로 변하는 경우(파란색 상태에서 빨간색 상태로 이동). 이 경우 글리치는 맵 상단에서 하단으로 순환한다.

글리치가 실제로 발생할지는 구현의 물리적 특성에 따라 다르며, 이에 대해 걱정해야 하는지는 응용 프로그램에 따라 다르다. 클럭 논리에서는 논리가 타이밍 마감일을 맞출 수 있을 만큼 충분히 빠르게 원하는 값으로 정착하는 것만으로 충분하다. 이 예시에서는 클럭 논리를 고려하지 않는다.

이 경우,

A\overline{D}

의 추가 항은 녹색과 파란색 출력 상태 또는 파란색과 빨간색 출력 상태 사이를 연결하여 잠재적인 경쟁 위험을 제거한다. 이는 인접한 다이어그램에서 노란색 영역(오른쪽 반쪽의 하단에서 상단으로 순환)으로 표시된다.

이 항은 시스템의 정적 논리 측면에서 중복되지만, 이러한 중복 또는 컨센서스 항은 경쟁이 없는 동적 성능을 보장하는 데 종종 필요하다.

마찬가지로, 다른 잠재적인 경쟁 위험을 제거하기 위해

\overline{A}D

의 추가 항을 역에 추가해야 한다. 드 모르간의 법칙을 적용하면 ''f''에 대한 또 다른 곱의 합 표현식이 생성되지만, 새로운 인수는

\left(A + \overline{D}\right)

이다.

4. 관련 방법

카르노 맵 외에도 다양한 논리식 간소화 방법이 존재한다.^[9]^[12]^[4] 에드워드 W. 베이치(1924–2013)가 1952년에 제안한 베이치 차트(Veitch Chart)는 카르노 맵의 변형으로, 변수의 순서를 다르게 배열한다.^[10]^[4] 1956년에는 안토닌 스보보다(1907–1980)가 스보보다 차트를 발표했다.^[11]

마호니 맵(1963, M-맵, 지정 숫자)은 매튜 V. 마호니가 제안한 방법으로, 더 많은 입력 변수를 처리하기 위한 카르노 맵의 반사 대칭 확장 형태이다.

축소 카르노 맵(Reduced Karnaugh Map, RKM) 기술(1969년부터)은 빈번하지 않은 변수를 처리하기 위한 카르노 맵의 변형으로, G. W. 슐츠, 토마스 E. 오스본, 크리스토퍼 R. 클레어 등에 의해 개발되었다.

토마스 R. 맥컬라는 1990년에 더 많은 입력 변수를 처리하기 위한 카르노 맵의 3차원 확장인 민텀 링 맵(MRM)을 제안했다.

5. 추가 정보

참조

_[1] 문서 This should not be confused with the negation of the result of the previously found function.
_[2] 서적 A new approach to the design of switching circuits D. van Nostrand Company, Inc. 1962
_[3] 간행물 The Map Method for Synthesis of Combinational Logic Circuits https://web.archive.[...] 2017-04-16
_[4] 서적 Boolean Reasoning - The Logic of Boolean Equations http://www2.fiit.stu[...] Dover Publications, Inc. 2012
_[5] 서적 Digital Design: Principles & Practices Prentice Hall 1994
_[6] 웹사이트 Karnaugh Maps – Rules of Simplification http://www.ee.surrey[...] 1998-04-01
_[7] 웹사이트 Simplifying Logic Circuits with Karnaugh Maps http://www.utdallas.[...] The University of Texas at Dallas, Erik Jonsson School of Engineering and Computer Science 2015-09-01
_[8] 웹사이트 Using Karnaugh Maps to Simplify Code http://www.quantumra[...] Quantum Rarity
_[9] 간행물 XXXIII: On Logical Diagrams for ''n'' terms http://www.tandfonli[...] 1881
_[10] 서적 Proceedings of the 1952 ACM national meeting (Pittsburgh) on - ACM '52 Association for Computing Machinery 1952-05-03
_[11] 서적 Introduction to the Methodology of Switching Circuits Litton Educational Publishing, Inc. / D. van Nostrand Company 1972-05-01
_[12] 서적 Logic Machines and Diagrams https://archive.org/[...] McGraw-Hill Book Company, Inc. 1958

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com

	A	B	C	D	f(A, B, C, D)
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	0
6	0	1	1	0	1
7	0	1	1	1	0
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0

	A	B	C	D	f(A, B, C, D)
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	0
6	0	1	1	0	1
7	0	1	1	1	0
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0

	A	B	C	D	f(A, B, C, D)
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	0
6	0	1	1	0	1
7	0	1	1	1	0
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0