기록의 두 자리가 지워지고, 남은 자리에서도 하나가 틀렸어요. 원래 값을 한 자리씩 다시 받을 수 있다면 어디부터 물어야 할까요? 이미 보이는 자리보다 지워진 자리를 먼저 물어야 할 수도 있어요.
0과 1로 된 일곱 자리 기록을 생각해 봐요. 보낸 기록 c₁,…,c₇은 다음 세 검사식의 나머지가 모두 0입니다. ⊕는 두 값이 같으면 0, 다르면 1인 연산이에요. 여러 값에서는 1의 개수가 홀수인지 짝수인지 나타내요.
이 세 식은 알려진 7자리 이진 해밍 부호의 검사조건이에요. 원문에 있는 한 자리 오류 수정 규칙 자체를 새 질문으로 세지는 않아요.
현재는 1번과 2번이 지워져 보이지 않아요. 보이는 3~7번 중에서도 정확히 하나가 뒤집혀 0이 1, 또는 1이 0이 되었어요. 다른 손상은 없어요. 보이는 다섯 값을 r₃,…,r₇이라 해 볼까요? 원래 기록을 보관한 곳에 어느 자리든 원래 0/1값을 다시 물을 수 있어요. 새 답은 정확하고, 다음 자리는 앞 답에 따라 정해도 돼요.
모든 허용 기록에서 복원을 마칠 수 있게 하려면 최악의 경우 몇 번을 물어야 할까요? 그 횟수를 달성하는 첫 자리가 무엇인지도 전부 찾아요. 후보들이 같은 확률이라는 가정이나 평균 요청 횟수의 최적화는 하지 않아요.
먼저 보이는 값만으로 세 나머지를 계산해요.
p=0이면 4~7번은 모두 맞아요. 이 네 자리 중 하나가 틀렸다면 원래 0인 세 번째 검사값이 1로 바뀌었을 거예요. 오류가 정확히 하나라는 조건 때문에 3번만 뒤집혔다고 확정해요. c₃=1−r₃로 고친 뒤 앞 두 식에서 지워진 값을 구해요.
받은 다섯 자리가 00000이어도 원래 일곱 자리가 모두 0은 아니에요. 원래 기록은 1110000이고 3번이 뒤집힌 거예요. 이 경우에는 추가 요청이 전혀 필요하지 않아요.
p=1이면 상황이 달라요. 3번이 뒤집혀서는 이 검사값이 바뀌지 않으므로 오류는 4~7번 중 하나예요. 각 후보 자리의 값을 고치고 앞 두 식으로 c₁,c₂를 정하면 세 검사식 모두를 만족해요. 따라서 어느 후보도 아직 버릴 수 없어요.
| 뒤집힌 자리 | 원래 1번·2번의 값 |
|---|---|
| 4 | (A,B) |
| 5 | (1−A,B) |
| 6 | (A,1−B) |
| 7 | (1−A,1−B) |
네 후보의 지워진 두 자리는 가능한 네 조합을 정확히 한 번씩 가져요. 1번과 2번의 원래 값을 차례로 물으면 어느 자리에서 오류가 났는지 정해지고 전체 기록도 복원돼요.
이 두 요청보다 적게 끝낼 수는 없어요. 한 요청의 답은 0 또는 1뿐이에요. 제공 교재의 곱의 법칙으로 두 요청의 답 조합은 최대 2×2=4가지이며, 한 요청에는 두 답만 있어요. 원래 기록 네 후보가 모두 가능한 현재 경우에는 적어도 두 요청이 필요해요. 여기서 같은 확률이라는 가정은 쓰지 않아요.
그렇다고 아무 자리를 처음에 물어도 두 번에 끝나는 것은 아니에요. 1번이나 2번은 네 후보를 둘씩 나누고, 나머지 지워진 자리를 한 번 더 물어 구별해요. 반면 3번 값은 네 후보에서 모두 r₃로 같아 첫 요청에서 아무 후보도 없애지 못해요.
4~7번 중 하나를 처음에 물으면 그 자리가 틀린 후보 하나와 맞은 후보 세 개로 나뉘어요. 답이 세 후보 쪽이면 한 요청만 남아 있어요. 두 답으로 세 기록을 구별할 수는 없으므로 최악의 경우 두 번에 끝내지 못해요. 그 뒤 1번과 2번을 물으면 세 번에는 끝낼 수 있어요. 3번을 먼저 물은 경우도 마찬가지예요.
예를 들어 받은 값이 00001이면 원래 기록은 1101001,0100101,1000011,0000000 중 하나예요. 네 후보의 1번·2번 값은 11,01,10,00으로 모두 달라요. 눈에 보이는 마지막 자리를 다시 확인하는 것이 지워진 두 자리를 묻는 것보다 항상 낫지는 않아요.
조건의 단어 하나도 중요해요. 오류가 ‘정확히 하나’가 아니라 ‘최대 하나’라면 p=0에서 오류가 전혀 없는 기록도 후보가 돼요. 받은 00000은 0000000과 1110000 두 원래 기록에서 모두 가능해요. 이 바뀐 조건에서는 지워진 1번이나 2번을 한 번 묻지 않고는 두 후보를 구별하지 못해요.
교사는 받은 자료와 새 요청의 답을 구별해 적게 해요. 후보 수를 세는 하한, 두 요청으로 복원하는 구체 규칙, 어떤 첫 요청이 그 하한을 달성하는지를 각각 확인해요. 같은 후보 수만 보고 요청 순서도 같다고 판단하지 않는 것이 질문의 중심이에요. 실제 전송 오류율이나 장치 복구 성능을 측정한 자료는 아니에요.
착안: Yuri Bazlov, Manchester Coding Theory, Decoding a Hamming code의 선택 절을 읽었어요. 알려진 이진 검사조건을 배경으로 쓰고, 두 지움·정확히 한 뒤집힘·한 자리씩의 정확한 재요청이라는 자체 조건에서 모든 관측의 후보 분류와 첫 요청 선택을 증명했어요. 원문 행렬 도판·연습문항·구현 코드는 옮기지 않았어요.