948. 해밍 거리 (Hamming Distance) - 전송 오류 제어 비트 차이 계수 에러 검출 및 정정 수학적 최소 거리 통신망 한계 모델 원리

핵심 인사이트: A 컴퓨터가 "000"을 보냈는데 랜선을 타다 벼락을 맞아 "011"로 바뀌어 도착했다. 받는 컴퓨터는 이게 원본에서 에러가 난 건지, 아님 원래 "011"을 보낸 건지 어떻게 알까? 리처드 해밍이라는 천재는 말했다. "야! 세상의 모든 단어를 '100'이나 '101'처럼 비슷하게 촘촘히 짓지 마! 무조건 단어끼리 스펠링(비트)이 최소 3칸 이상 확 차이 나도록(거리) 사전을 띄엄띄엄 만들어 놔! 그러면 "000"이 한 글자 깨져서 "001"로 와도, 사전에 "001"이란 말이 아예 없으니까 100% 에러인 걸 눈치챌 수 있고, "어? 000에서 1글자만 변한 거네! 정답은 000이다!"라고 스스로 치유(정정)까지 할 수 있잖아!" 에러를 스스로 치유하는 수학적 띄어쓰기 마법, 해밍 거리다.

Ⅰ. 통신 오류(Error)의 필연성

• 구리선이나 무선 전파로 0과 1을 보내면 번개, 노이즈 때문에 비트가 무조건 뒤집힙니다(0 ➜ 1).
• 수신자는 엉망진창으로 바뀐 데이터가 원래 무슨 글자였는지 눈치채야 합니다(오류 검출 및 정정 FEC, 908번 문서 참조). 이를 해결하는 물리학적/수학적 기준점이 해밍 거리입니다.

Ⅱ. 해밍 거리 (Hamming Distance)의 개념 🌟

• 개념: 길이가 같은 두 개의 이진수(0과 1의 문자열)를 나란히 비교했을 때, **서로 값이 일치하지 않고 다르게 튀는 '비트(Bit)의 개수'**를 의미합니다.
• 예시:
  • A = 1011101
  • B = 1001001
  • 앞에서 3번째 비트(1과 0)가 다르고, 5번째 비트(1과 0)가 다릅니다. 두 자리가 다르므로, A와 B 사이의 해밍 거리는 2입니다. (수학적으로는 두 숫자를 XOR 연산하여 1의 개수를 세면 됩니다.)

Ⅲ. 최소 해밍 거리 ($D_{min}$)와 에러 정정의 기적 🌟 핵심 🌟

통신 엔지니어가 규칙(코드 사전)을 만들 때, 사전에 있는 모든 유효한 단어들끼리의 해밍 거리를 계산해 가장 작은 값을 **최소 해밍 거리($D_{min}$)**라고 부릅니다. 이 숫자 하나가 에러를 얼만큼 고칠 수 있는지를 절대적으로 결정합니다.

1. 에러 검출 (Error Detection) 능력 공식

• 공식: $D_{min} \ge e + 1$
• 해석: 최소 해밍 거리가 3($D_{min}=3$)인 규칙을 만들었다면, 최대 2개($e=2$)의 비트가 깨지는 것까지는 "아! 이거 사전에 없는 에러난 단어네!" 하고 눈치(검출)챌 수 있습니다. (만약 3개가 깨져버리면 다른 정상 단어로 완벽히 둔갑해 버리므로 에러인 줄도 모르고 속습니다.)

2. 에러 정정 (Error Correction) 능력 공식 🌟 빈출 🌟

눈치채는 걸 넘어, 부서진 글자를 원래 글자로 원상 복구(치유)하는 능력입니다.

• 공식: $D_{min} \ge 2t + 1$ (또는 $t = \lfloor \frac{D_{min} - 1}{2} \rfloor$)
• 해석: 최소 해밍 거리를 3($D_{min}=3$)으로 띄워놨다면, 최대 1개($t=1$)의 비트가 깨진 것까지는 100% 원래 단어로 완벽 복원(정정)해 낼 수 있습니다.
• 논리 증명: 사전에 000과 111 두 단어만 등록했습니다(최소 거리 3). 수신자가 001을 받았습니다. 사전에 없는 말이니 에러(검출)입니다! 그런데 001은 000에서 1보 거리이고, 111에서는 2보 거리입니다. "아! 1보밖에 안 떨어진 000이 한 글자 깨진 거구나!" 하고 수신기가 즉시 000으로 정답을 꿰맞춰버립니다(정정).

Ⅳ. 해밍 코드 (Hamming Code)의 탄생

• 이 거리를 일부러 넓혀서 에러를 고치기 위해, 원본 데이터 뒤에 추가적인 쓰레기 잉여 비트(Parity Bit)들을 수학적 공식을 돌려 덕지덕지 붙여서 전송합니다.
• 이 기법(해밍 코드) 덕분에 우주선에서 날아오는 위성 데이터가 태양풍에 깨져도, 지구 관제소 컴퓨터가 스스로 깨진 비트를 완벽하게 치유(FEC)하여 사진을 살려내는 기적이 가능해집니다.

📢 섹션 요약 비유: 해밍 거리(Hamming Distance)의 원리는 바다 한가운데서 안전하게 '등대(정상 단어)'를 세우는 이격 거리의 법칙입니다. 만약 1km마다 등대를 촘촘하게 세워두면, 폭풍(노이즈/에러)이 몰아쳐 배(데이터)가 파도에 1km만 휩쓸려도 엉뚱한 B 등대 불빛(다른 글자)을 보고 "오! 잘 도착했군" 착각하여 배가 박살 납니다(에러 검출 실패). **해밍 거리 확보(거리 늘리기)**는 등대와 등대 사이를 아예 3km씩 확 벌려 지어놓는(최소 해밍 거리 3) 수학적 설계입니다. 이제 폭풍이 쳐서 배가 1km(에러 1비트 발생) 휩쓸리더라도, 사방을 둘러봤을 때 가장 가까운 등대는 무조건 원래 목표로 했던 1보 거리의 A 등대밖에 없습니다. 배는 안심하고 "아 내가 살짝 떠내려왔네, 저기 가장 가까운 1km 앞 A 등대로 돌아가야지!" 하고 스스로 원래 항로를 찾아 복구(에러 1비트 정정)해 내는 궁극의 오류 치유 내비게이션 법칙입니다.