7. 소스 부호화 정리 (Source Coding Theorem) — 엔트로피 한계

핵심 인사이트 (3줄 요약)

1. 본질: 섀넌의 소스 부호화 정리는 엔트로피 H(X)가 무손실 압축의 절대 하한임을 증명 — 어떤 알고리즘도 평균 H(X) 비트/심볼 미만으로 압축할 수 없다.
2. 가치: 허프만 (Huffman) 코딩은 엔트로피에 1 비트 이내로 근접하고, 산술 부호화는 임의로 가깝게 접근하며, LZ 계열은 점근적으로 최적이다.
3. 판단 포인트: 무손실과 손실 압축의 경계 — 레이트-왜곡 이론 (Rate-Distortion Theory) 이 허용 왜곡 D 아래에서 달성 가능한 최소 비트율 R(D)를 정의한다.

Ⅰ. 개요 및 필요성

소스 부호화 정리 (Source Coding Theorem, 또는 섀넌 제1 정리):

"독립 동일 분포 (i.i.d.) 확률원 X를 무손실로 압축할 때, 심볼당 평균 코드 길이 L̄은 반드시 H(X) 이상이다. 반면, H(X) + ε 비트/심볼로 압축하는 알고리즘이 항상 존재한다."

H(X) ≤ L̄ < H(X) + ε   (임의로 작은 ε > 0에 대해 달성 가능)

이 정리는 두 방향으로 동시에 증명된다:

• 불가능성: L̄ < H(X) 압축은 정보 손실 없이 불가
• 달성 가능성: H(X) + ε 이내의 압축 방법 존재

📢 섹션 요약 비유: 소스 부호화 정리는 "짐 싸기 한계"다 — 여행 가방(코드)에 짐(정보)을 아무리 효율적으로 넣어도 짐 자체의 정보량(엔트로피) 만큼은 반드시 넣어야 하며, 그것보다 작게는 절대 불가능하다.

Ⅱ. 아키텍처 및 핵심 원리

주요 압축 알고리즘 성능 비교

평균 코드 길이 L̄
         │
H(X)+1   ├──────────── 허프만 코딩 ────────────────
H(X)+0.1 ├──────────── 산술 부호화 ───────────────
H(X)+ε   ├──────────── LZ 계열 (점근적) ─────────
H(X)     ├──────────── 이론 하한 ─────────────────
         │
         └──────────────────────────────────────►
                        블록 길이 n → ∞

허프만 코딩 (Huffman Coding) 예시

확률 분포: A(0.5), B(0.25), C(0.125), D(0.125)

엔트로피: H = -(0.5·log0.5 + 0.25·log0.25 + 0.125·log0.125 + 0.125·log0.125) = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75 bits

허프만 트리 구성:

심볼:  A(0.5)  B(0.25)  C(0.125)  D(0.125)

단계1:        C+D → 0.25
단계2:     B + 0.25 → 0.5
단계3:  A + 0.5 → 1.0 (루트)

코드: A→0, B→10, C→110, D→111

평균 코드 길이: 0.5×1 + 0.25×2 + 0.125×3 + 0.125×3 = 1.75 bits
→ 엔트로피와 완전히 동일!

허프만의 성질: H(X) ≤ L̄_Huffman < H(X) + 1

알고리즘별 비교

📢 섹션 요약 비유: 허프만 코딩은 "자주 쓰는 단어에 짧은 줄임말"을 배정하는 것이다 — "국제연합"을 "UN"으로, "인공지능"을 "AI"로 쓰는 것처럼 빈도 높은 심볼에 짧은 코드를 준다.

Ⅲ. 비교 및 연결

손실 압축과 레이트-왜곡 이론

무손실 압축의 하한 = H(X). 하지만 약간의 왜곡(오차)을 허용하면?

레이트-왜곡 이론 (Rate-Distortion Theory):

R(D) = min_{P(X̂|X): E[d(X,X̂)]≤D} I(X;X̂)

D: 최대 허용 왜곡, R(D): 그에 대응하는 최소 필요 비트율

R(D)
   ▲
   │╲
   │  ╲
   │    ╲
   │      ─────
   └───────────► D
  D=0   D 증가시 R 감소

D=0: R = H(X) (무손실)
D→∞: R → 0 (극단 손실)

📢 섹션 요약 비유: 레이트-왜곡 트레이드오프는 "사진 화질 vs 파일 크기"다 — 화질(D 낮음)을 높이면 파일(R)이 커지고, 허용 화질 저하(D 높음)를 늘리면 파일이 작아진다.

Ⅳ. 실무 적용 및 기술사 판단

실제 압축 파이프라인 (DEFLATE = ZIP, PNG, gzip)

원본 데이터
     │
     ▼ LZ77 (중복 제거)
길이-오프셋 쌍
     │
     ▼ 허프만 코딩 (심볼 인코딩)
압축 비트스트림
     │
     ▼ 컨테이너 포맷 (.zip, .png, .gz)
최종 파일

영역별 채택 압축 기술

기술사 판단 포인트

1. "무손실 압축 이론 한계는?" → 엔트로피 H(X) [bits/symbol]
2. "허프만 코딩이 최적인가?" → 심볼 수 무한 시 아님, 산술 부호화가 더 가까움
3. "JPEG는 무손실인가?" → 기본은 DCT 손실 압축 (JPEG 2000 웨이블릿도 손실)

📢 섹션 요약 비유: DEFLATE(LZ77+허프만)는 "두 단계 짐 싸기"다 — 먼저 중복 물건을 없애고(LZ77), 나머지를 무게 순으로 효율 포장한다(허프만).

Ⅴ. 기대효과 및 결론

소스 부호화 정리는 압축 기술의 절대 기준점이다. 현대 압축 알고리즘들이 이 한계에 얼마나 가깝게 도달했는지를 평가하는 척도로 활용된다.

신경망 기반 압축 (Neural Compression) 은 비선형 표현 학습으로 기존 알고리즘을 능가하기 시작했다:

• 학습 기반 이미지 압축 (Learned Image Compression): VGG/ResNet 인코더 + 엔트로피 모델 + 디코더
• JPEG와 H.265를 동일 비트율에서 시각 품질 면에서 능가

📢 섹션 요약 비유: 신경망 압축은 "AI 포장 전문가"다 — 고전 알고리즘이 수학 공식으로 짐 쌌다면, AI는 경험으로 인간이 어떤 부분에 덜 민감한지 학습해 더 효율적으로 포장한다.

📌 관련 개념 맵

📈 관련 키워드 및 발전 흐름도

[정보 이론 (Information Theory)]
    │
    ▼
[엔트로피 (Entropy)]
    │
    ▼
[소스 코딩 (Source Coding)]
    │
    ▼
[무손실 압축 (Lossless Compression)]
    │
    ▼
[손실 압축 (Lossy Compression)]
    │
    ▼
[채널 코딩 (Channel Coding)]

정보 이론의 엔트로피 개념이 소스 코딩 원리로 구체화되어 무손실·손실 압축 기술로 발전하는 흐름이다.

👶 어린이를 위한 3줄 비유 설명

1. 엔트로피 = 짐 최소 무게: 아무리 잘 개도 짐의 정보만큼의 무게는 가져가야 한다.
2. 허프만 = 자주 쓰는 단어 줄임말: "반갑습니다"→"반갑", "안녕하세요"→"안녕"처럼 자주 나오는 것에 짧은 코드.
3. 손실 압축 = 살짝 흐릿한 사진: 완벽한 원본 대신 눈에 덜 띄는 부분을 조금 희생해 파일을 작게 만든다.