카르노맵의 시각적 패턴과 Boolean 공간 구조의 대응 관계 연구

초록 / Abstract

1. 서론

1.1 연구 배경

카르노맵은 디지털 논리회로 설계에서 논리식을 최소화하기 위한 대표적인 도구로 사용된다. 일반적인 교육 과정에서는 카르노맵의 인접 셀을 그룹화하여 SOP(Sum of Products) 또는 POS(Product of Sums) 형태의 최소 논리식을 도출하는 방법을 중심으로 설명한다.

그러나 실제 카르노맵을 관찰하면 단순한 그룹화 이상의 다양한 시각적 구조가 존재한다. 특히 XOR 및 XNOR 함수의 경우 일반적인 직사각형 그룹과는 다른 체커보드 형태의 패턴이 나타난다. 또한 배열 방식에 따라 동일한 논리함수가 체커보드, 대각선, 이중대각선 등 서로 다른 시각적 구조로 표현될 수 있다.

1.2 연구 목적

본 연구의 목적은 카르노맵에 나타나는 시각적 패턴을 체계적으로 분류하고, 이러한 패턴이 Boolean 함수의 구조와 어떠한 관계를 가지는지 탐구하는 데 있다.

Hamming Weight 관점을 도입하여 각 함수를 Boolean 공간의 Layer 구조로 해석하고, 카르노맵의 시각 패턴이 이러한 구조의 2차원 표현으로 이해될 수 있음을 규명하고자 한다.

1.3 연구 범위 및 방법

본 연구는 4변수 카르노맵(총 16개 입력 상태)을 대상으로 수행하였다. 완전대칭함수 중 Exactly-$k$ 함수와 XOR/XNOR 함수를 선정하고, Gray Code 배열(0132)과 일반 이진 배열(0123)을 교차 비교하여 시각적 대칭·동일의 개념을 정의하고, 점·모서리·고리·체커보드·이중대각 패턴의 5대 분류 체계를 수립하였다.

2. 이론적 배경

2.1 카르노맵의 구조

4변수 카르노맵은 총 16개의 셀로 구성되며, 각 셀은 입력 변수 $A, B, C, D$의 하나의 상태에 대응한다. 인접한 상태가 하나의 변수만 다르도록 배치되어 Boolean 공간의 인접성을 보존한다.

2.2 Gray Code 배열과 일반 이진 배열

4변수 카르노맵의 행과 열은 일반적으로 Gray Code 순서인 00, 01, 11, 10으로 배열된다. 이 배열 방식은 인접 상태 사이의 Hamming Distance가 항상 1이 된다는 성질을 가진다 (0132 배열).

반면 일반적인 이진수 순서인 00, 01, 10, 11을 0123 배열이라 부른다. 동일한 함수라도 표현 방식에 따라 인접성이 교란되며 서로 다른 시각 패턴이 나타난다.

2.3 완전대칭함수와 Hamming Weight

변수의 순서와 무관하게 동일한 출력을 유지하는 함수를 완전대칭함수(Symmetric Boolean Function)라 한다. 입력 상태의 Hamming Weight $w$는 다음과 같이 정의된다:

$$w = A + B + C + D$$

여기서 $w \in \{0, 1, 2, 3, 4\}$의 다섯 가지 값이 가능하며, 각 $w$에 해당하는 상태의 수는 조합 공식 $\binom{4}{w}$이다.

2.4 Boolean 공간의 Layer 구조

4변수 공간 16개 상태는 Hamming Weight에 따라 파스칼 삼각형 계수와 동일한 $1\text{-}4\text{-}6\text{-}4\text{-}1$ 층(Layer) 구조를 이룬다.

2.5 Layer 구조와 시각 패턴의 인과 체계

완전대칭함수는 본질적으로 특정 Layer 또는 Layer 집합을 선택하는 함수이다.

3. 시각 패턴의 정의

3.1 시각적 대칭 (Visual Symmetry) & 시각적 동일 (Visual Repetition)

시각적 대칭은 특정 축에 대하여 카르노맵을 반사하였을 때 대응되는 위치의 값이 유지되는 성질이며, 시각적 동일은 특정 부분 블록이 평행이동을 통해 반복적으로 나타나는 현상이다.

3.2 체커보드 패턴 vs 이중대각 패턴

체커보드 패턴은 인접한 모든 셀의 값이 반대가 되는 구조이며, 이중대각 패턴은 주대각선($y=x$)과 부대각선($y=-x$) 대칭에 더해 좌우·상하 반사 대칭도 동시에 가지는 격자 형태이다.

0  1  0  1
1  0  1  0
0  1  0  1
1  0  1  0

0  1  1  0
1  0  0  1
1  0  0  1
0  1  1  0

3.3 고리 패턴 (Ring Pattern)

Exactly-2 함수는 중앙 영역을 감싸는 6개 셀의 연속적 띠를 형성하며 폐곡선 고리 형태로 인식된다.

4. 완전대칭함수의 시각 패턴 분석

4.1 Exactly-0 & Exactly-4 함수 — 점 패턴 (Point Pattern)

$L_0$ 및 $L_4$는 각각 1개 상태만을 가지며 카르노맵의 한 셀에 단일 점으로 나타난다(Exactly-0은 왼쪽 위 모서리 셀 0000, Exactly-4는 중앙 영역의 셀 1111).

4.2 Exactly-1 & Exactly-3 함수 — 모서리 패턴 (Corner Pattern)

$L_1$ 및 $L_3$은 각각 4개 상태를 가지며, 4변수 카르노맵(양 끝을 이어 붙인 인접 관계 기준)에서 각각 $L_0$ 셀과 $L_4$ 셀의 상하좌우 이웃 네 칸으로 배치되는 구조적 쌍대성을 가진다.

4.3 Exactly-2 함수 — 고리 패턴 (Ring Pattern)

Boolean 공간의 최다 상태 Layer인 $L_2$ (6개 상태)는 Gray Code 위에서 서로 인접하지는 않지만 대각 방향으로(양 끝의 이어짐 포함) 이어져 닫힌 고리와 유사한 띠로 인식된다.

4.4 XOR & XNOR 함수 — 체커보드 vs 이중대각 비교

XOR은 홀수 Layer ($L_1 \cup L_3$, 8개 셀), XNOR은 짝수 Layer ($L_0 \cup L_2 \cup L_4$, 8개 셀)를 선택한다.

5. XOR/XNOR 패턴의 구조적 해석

5.1 패리티 구조와 인접 이동

4변수 XOR 함수는 $w$가 홀수인 상태의 합집합($L_1 \cup L_3$)이다. 카르노맵에서 한 셀 이동할 때 비트가 1개 바뀌므로 Hamming Weight는 반드시 $\pm 1$ 변화한다:

$$L_0 \longleftrightarrow L_1 \longleftrightarrow L_2 \longleftrightarrow L_3 \longleftrightarrow L_4$$

따라서 인접한 두 셀은 홀짝성이 반드시 반대이며, 홀수 Layer 전체($L_1 \cup L_3$)를 선택하는 함수는 Gray Code 위에서 필연적으로 체커보드 패턴을 산출한다.

6. 배열 방식에 따른 시각 패턴 변화

6.1 패턴 형성의 이중 원인 모형

본 연구의 분석은 시각 패턴이 단일 원인이 아닌 **함수의 성질(Layer 구조)**과 **표현의 성질(배열 방식)**의 상호작용일 수 있음을 시사한다.

7. 결론 및 탐색적 가설

본 연구는 점, 모서리, 고리, 체커보드 패턴이 개별적 우연이 아니라 파스칼 삼각형 Layer 구조와 인접성 보존 배열의 결합이라는 공통 원리로 통합 설명될 수 있음을 시사한다. 이를 통해 카르노맵은 단순한 회로 간소화 도구를 넘어 4변수 Boolean 공간의 구조를 시각적으로 표현하는 도구로 재해석될 수 있다.

참고문헌 (References)