반복 부호와 오류정정의 비용

같은 비트를 여러 번 보내는 이유

한 비트를 세 번 보내 0은 000, 1은 111로 표현해 봅시다. 수신열이 001이면 000과 거리는 1, 111과 거리는 2여서 0을 선택합니다. 여기서 거리는 다른 비트 위치의 수인 Hamming 거리입니다. 잉여 비트를 추가하면 가능한 수신열 중 일부가 원래 메시지를 되찾을 단서가 됩니다.

일반적으로 홀수 n의 반복 부호는 길이 n인 두 부호어만 가집니다. 거리가 n이므로 t=(n−1)/2개까지의 임의 오류를 유일하게 고칠 수 있습니다. 이는 확률을 가정하지 않는 최악 경우의 보장입니다.

확률 보장에는 독립성 가정이 필요하다

이제 각 위치가 독립적으로 확률 ε로 뒤집히는 BSC를 가정합니다. 오류 개수 K는 이항분포이며 다수결은 K>n/2일 때 실패합니다. 특정 오류 mask 하나의 확률에는 조합 계수가 없고, 같은 개수의 모든 오류 위치를 합칠 때 조합 계수가 붙습니다.

ε=.1, n=3이면 Pₑ=3×.01×.9+.001=.028입니다. n=5이면 .00856으로 줄지만 정보 비트 하나에 5번의 사용을 지불합니다. ε=.1인 BSC의 용량 약 .531과 비교하면 반복 부호의 전송률 1/3, 1/5가 낮습니다. 오류가 줄어도 좋은 부호의 모든 조건을 만족한 것은 아닙니다.

곡선과 선택 수신열을 따로 읽기

파란 점은 오류 개수별 이항 확률, 주황 점은 실패 영역입니다. 표는 선택한 수신 mask 한 개의 전송·수신 비트를 보여줍니다. 낮은 n비트만 사용하므로 위쪽 mask 비트는 버립니다. 이 표를 바꾼다고 이론적 블록 오류 확률이 달라지지는 않습니다.

n=5, 전송 0, mask=3은 앞 두 위치만 1인 수신열입니다. K=2이므로 0으로 복원하지만 이 열 하나의 확률 .1²×.9³=.00729와 전체 실패 확률 .00856은 다른 양입니다.

독립 오류 모형의 한계와 AI 시스템

ε=.5에서는 다수결도 공정한 동전과 같아 오류 확률이 .5입니다. ε>.5에서는 뒤집힌 값이 더 흔하므로 출력을 먼저 반전하는 등 알려진 채널을 반영해야 합니다. 실습은 이 경우에도 단순 다수결을 그대로 계산해 잘못된 복호 규칙을 드러냅니다.

연속된 장치 장애처럼 오류가 상관되면 이항식은 맞지 않습니다. 분산 학습에서 복제본을 여러 개 만드는 것 역시 독립 실패를 보장하지 않습니다. 공통 원인의 장애와 통신량·지연을 함께 평가해야 합니다.

확인 문제와 해설

1. n=7은 몇 오류까지 보장하나요? 3개입니다. 반경 3의 두 Hamming 공은 거리가 7인 두 부호어 사이에서 겹치지 않습니다.
2. 오류가 정확히 4개인 n=7의 수신은? 다수결이 반대로 판정합니다. 부호 자체의 거리를 늘리지 않고 복호 규칙만 반복 적용해도 복구되지 않습니다.
3. 독립성 없이 .028을 사용할 수 있나요? 아니요. 세 위치가 함께 뒤집히는 모형이라면 같은 위치별 오류율 .1이어도 블록 오류는 .1입니다.

추가 읽기: MIT MAS.160, Error Correction.