섀넌이 부른 정보란
섀넌은 놀라움을 측정하여 정보를 정의했습니다. 확률 p인 메시지는 다음을 전달합니다:
I = −log₂(p) bits
확실한 사건(p = 1)은 0 비트를 전달합니다 — 놀라움 없음, 정보 없음. 드문 사건(p = 1/1024)은 10 비트를 전달합니다.
해밍은 즉시 문제를 지적합니다: 이것은 개념의 정의가 아닌 양을 측정하기 위한 공식입니다. 그것은 인간의 의미가 아닌 기계 같은 놀라움을 측정합니다. 이미 질문의 답을 알고 있는 학생은 답에서 0 비트를 받습니다 — 다른 사람들에게 답이 얼마나 중요한지는 상관없이.
이 공식은 전화 체계, 라디오, 컴퓨터에 잘 적용됩니다. 인간 통신, 생물학, 또는 의미에는 적용이 잘 안 됩니다. 해밍이 선호하는 이름: '정보 이론'이 아닌 '통신 이론'.
엔트로피
q개 기호의 알파벳이 확률 p₁, p₂, ..., p_q를 가질 때, 기호당 평균 정보는 엔트로피입니다:
H = −Σᵢ pᵢ log₂(pᵢ)
H는 모든 확률이 같을 때 최댓값에 도달합니다: H_max = log₂(q) bits. 모든 비균등 분포는 더 낮은 엔트로피를 가집니다.
엔트로피 계산
이진 엔트로피: 두 기호가 있는 소스, P(0) = p, P(1) = 1−p.
H(p) = −p log₂(p) − (1−p) log₂(1−p)
H(p) = 0 at p = 0 or p = 1 (완전히 예측 가능). H(p) = 1 bit at p = 0.5 (완전히 예측 불가능).
깁스 부등식 & 무잡음 부호화
깁스 부등식: 두 확률 분포 p = {pᵢ}와 q = {qᵢ}에 대해:
−Σ pᵢ log₂(pᵢ) ≤ −Σ pᵢ log₂(qᵢ)
등호는 p = q일 때만 성립합니다. 이는 모든 x > 0에 대해 ln(x) ≤ x − 1이고 x = 1일 때 등호가 성립한다는 기본 사실에 기반합니다.
결과: 엔트로피 H(p)는 모든 기호가 동일한 확률을 가질 때 최대화됩니다. q개 기호의 경우: H_max = log₂(q) bits.
무잡음 부호화 정리: 고유하게 복호화 가능한 부호가 주어지면, 크래프트 부등식에서 Σ 2^(−lᵢ) ≤ 1이 필요합니다. 여기서 lᵢ는 기호 i의 부호 길이입니다. 깁스 부등식에 의해 평균 부호 길이 L = Σ pᵢ lᵢ는 다음을 만족합니다:
L ≥ H(p) = −Σ pᵢ log₂(pᵢ)
엔트로피보다 더 잘할 수 없습니다. 허프만 부호화는 L < H + 1을 달성합니다.
채널 용량
이진 대칭 채널(BSC)은 독립적으로 각 비트를 오류 확률 Q = 1 − P로 뒤집습니다. BSC의 용량 — 최대 신뢰할 수 있는 정보율 — 은 다음과 같습니다:
C = 1 + P log₂(P) + Q log₂(Q) = 1 − H(Q)
여기서 H(Q) = −Q log₂(Q) − (1−Q) log₂(1−Q)는 오류율의 이진 엔트로피입니다.
Q = 0 (오류 없음): C = 1 bit/전송 (완벽한 채널). Q = 0.5 (무작위 뒤집기): C = 0 (채널은 정보를 전달하지 않음). Q = 1 (모든 비트 뒤집기): C = 1 (발신자가 보낸 것이 정확히 무엇인지 알고 있습니다. 모든 것을 뒤집기만 하면 됩니다).
C는 임의로 작은 오류 확률로 전송할 수 있는 최대 속도 R을 측정합니다. R < C이면 그러한 부호가 존재합니다. R > C이면 존재하지 않습니다 — 어떤 부호도 용량을 초과할 수 없습니다.
채널 용량 계산
P = 0.9 (10% 오류율, Q = 0.1)일 때:
C = 1 + 0.9 log₂(0.9) + 0.1 log₂(0.1)
log₂(0.9) ≈ −0.152, log₂(0.1) ≈ −3.322
C ≈ 1 + 0.9×(−0.152) + 0.1×(−3.322) = 1 − 0.137 − 0.332 ≈ 0.531 bits/전송
정리가 증명하는 것
섀넌의 기본 정리: 모든 속도 R < C에 대해, 블록 길이 n의 부호가 존재합니다 (n → ∞ 포함). 오류 확률 P_E → 0을 달성합니다.
증명은 놀라운 논증을 사용합니다: 무작위 부호. 특정 부호를 구성하는 대신 섀넌은 모든 가능한 무작위 부호책에 평균을 냅니다 (동전 던지기 인코딩). 그는 모든 부호책에 대한 평균 오류가 작음을 보였습니다. 평균이 작으면 적어도 하나의 부호가 작은 오류를 달성합니다.
구체 기반 분석: 발신자가 메시지 aᵢ을 선택 → aᵢ 주변의 반경 n(Q + ε₂)의 구체. n이 크면 수신된 단어 bⱼ은 높은 확률로 이 구체 안에 있습니다. 수신자는 bⱼ을 포함하는 부호어의 구체로 복호화합니다.
네 가지 경우가 오류 확률 P_E를 결정합니다:
``
aᵢ in sphere other aⱼ in sphere outcome
yes no correct (no error)
yes yes ambiguous → error
no yes wrong decode → error
no no outside all spheres → error
``
P_E의 경계는 다음과 같이 작동합니다: P_E ≤ d + M × 2^(n × (H(Q+ε₂) − C)) 적절하게 선택된 d와 ε₂에 대해. H(Q+ε₂) < C가 되도록 ε₂를 선택하면 지수는 음수입니다. n이 크면 두 번째 항 → 0.
정리의 존재적 성질
해밍은 정리가 하는 것과 하지 않는 것에 대해 정확했습니다.
증명하는 것: 속도 R < C에서의 신뢰할 수 있는 통신은 원칙적으로 충분히 큰 n에 대해 가능합니다.
제공하지 않는 것: 명시적 부호 구성. 용량에 접근할 수 있을 정도로 충분히 큰 길이 n의 무작위 부호는 M × n 비트 크기의 부호책을 가지며, M과 n 모두 천문학적으로 큽니다. 그것을 저장하거나 계산할 수 없습니다.
오류 정정 부호 vs. 섀넌: 오류 정정 부호(해밍, 리드-솔로몬, 터보, LDPC)는 명시적이고 계산 가능한 구성을 제공합니다. 그들은 용량으로부터의 일부 거리와 실용적인 인코더 & 디코더를 교환합니다. n이 증가하고 블록당 더 많은 오류가 수정되면, 실용적인 부호는 용량에 밀접하게 접근할 수 있습니다.
우주 위성 예: 보이저와 파이오니어는 강력한 오류 정정 부호를 사용하여 수십억 마일 거리에서 5-20와트의 전력으로 통신했습니다. 긴 블록 길이를 통해 블록당 더 많은 오류를 수정할 수 있었으며, 거리로부터의 엄청난 잡음에도 불구하고 용량에 가까워질 수 있었습니다.
비판적 평가
해밍은 제13장을 과학의 정의에 대한 더 넓은 비판으로 마쳤습니다. 섀넌의 정보 공식은 인간의 의미가 아닌 기계 놀라움을 측정합니다. '정보 이론' 이름은 과도한 약속입니다. 어부 비유: 망의 그물코보다 큰 물고기만 잡는 어부는 더 작은 물고기가 없다고 결론짓습니다. 도구의 한계는 세계의 겉보기 제약이 됩니다.
정의의 문제
해밍은 정보 이론을 사용하여 더 큰 방법론적 포인트를 만들었습니다: 초기 정의는 대부분의 사람들이 실현하는 것보다 당신이 발견하는 것을 더 많이 결정합니다.
섀넌은 '정보'를 놀라움으로 정의하기로 선택했습니다. 그 정의는 통신 엔지니어링에 생산적이었습니다. 하지만 특정 범위 — 기계 같은 시스템 — 을 보편적 적용 가능성을 암시하는 단어('정보')에 수입했습니다.
어부 그물 비유: 6인치 그물코를 가진 그물은 큰 물고기만 잡습니다. 어부는 결론짓습니다: 최소 물고기 크기는 6인치입니다. 결론은 세계가 아닌 도구를 반영합니다.
평행 사례로서 IQ: '지능'을 측정하도록 설계된 테스트, 정규 분포를 생성하도록 보정됨, 그 다음 '지능'을 정의하는 데 사용됨. 도구는 개념을 형성합니다.
해밍의 권장 사항: 정의를 만날 때마다 다음을 물어보십시오 (1) 그것이 당신의 사전 직관과 얼마나 일치합니까? (2) 그것이 얼마나 왜곡합니까? (3) 어떤 조건에서 그것이 이루어졌습니까? (4) 지금 다른 조건에서 적용되고 있습니까?