長さ7のハミング符号を使い、左から位置を1始まりで数える。原文の四ビットを順に 番目へ置く。
この四位置のうちビットが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