길이 7의 해밍 부호를 사용한다. 위치 번호는 왼쪽부터 로 센다. 원본의 네 비트를 번 위치에 차례대로 넣는다.
이 네 위치 중 비트가 1인 위치 번호를 모두 XOR한 값을 라 하자. 로 나타내고, 번 위치에 각각 를 넣는다. 그러면 완성된 문자열에서 비트가 1인 모든 위치 번호의 XOR은 이다.
전송 중 번 비트가 뒤집혔다고 하자. 수신 문자열에서 비트가 1인 위치 번호를 XOR하면 가 한 번 추가되거나 빠지므로 결과는 정확히 이다. 루날리티는 그 비트를 다시 뒤집은 뒤 번 비트를 읽으면 된다. 정확히 한 비트가 뒤집히므로 이 전략의 수신 문자열에서 XOR 결과는 항상 1 이상 7 이하이다.
전송 길이는 항상 7이므로 제한을 만족한다. 위치 1,2,4의 검사 비트가 뒤집히는 경우와 위치 3,5,6,7의 데이터 비트가 뒤집히는 경우 모두 같은 방식으로 복구된다.
나이브 복원 방법으로는 16가지 원본을 모두 인코딩하고, 수신 문자열과 정확히 한 위치만 다른 코드워드를 찾을 수도 있다. 서로 다른 코드워드의 거리는 적어도 3이다. 거리가 1이면 두 코드워드의 XOR 검사값이 같을 수 없고, 거리가 2이면 서로 다른 두 위치 번호의 XOR이 0이어야 하므로 모순이다. 따라서 정확히 한 비트 차이인 후보는 유일하다. 입력 크기가 고정이므로 나이브 풀이도 전체 조건을 통과한다.
주 풀이의 시간과 추가 공간은 이다. 나이브 복원은 최대 번의 비트 비교를 하며 역시 이다. 위치 XOR 값은 최대 7, 원본의 수치 표현은 최대 15, 길이 8의 비트마스크는 최대 255이므로 모든 정수 계산은 부호 있는 64비트 범위 안에 있다.
Solution written by GPT6