n個の符号誤りを最小距離復号で訂正するために必要な符号間の最小ハミング距離dは、以下の式で求められます。
d=2n+1
例えば、以下の4つの符号間のハミング距離は1~3なので、最小ハミング距離は1です。
000/001/011/111
この場合、上記の1個目の符号*が符号誤りにより、001になったとすると、2個目の符号*との区別が付かなくなるため、符号誤りを訂正することはできません。
冒頭の式より、1個の符号誤りを訂正するために必要な符号間の最小ハミング距離は3です。よって、2個に減ってしまいますが、以下の符号*にすれば、1個の符号誤りを最小距離復号で訂正できます。
000/111
例えば、000に1個の符号誤りが発生し、001になったとします。001は、1個目の符号*に対してはハミング距離が1、2個目の符号*に対してはハミング距離が2となるため、最小距離復号で000に訂正できます。
例えば、ビット列2桁の符号*について考えます。最大限符号誤りに強くするために、ハミング距離が最大となる00と11を符号*とします。
太文字を符号誤りとして、01を得たとします。二つの正解の符号*に対して、両方ともハミング距離が1であるため、最小距離復号で訂正はできません。よって、1bit増やしてハミング距離が3となる000と111を符号*とします。これにより、1個の符号誤りを最小距離復号で訂正できます。
続いて、ビット列4桁の符号*について考えます。最大限符号誤りに強くするために、ハミング距離が最大となる0000と1111を符号*とします。
太文字を符号誤りとして、0011を得たとします。二つの正解の符号*に対して、両方ともハミング距離が2であるため、最小距離復号で訂正はできません。よって、1bit増やしてハミング距離が5となる00000と11111を符号*とします。これにより、2個の符号誤りを最小距離復号で訂正できます。
上記の流れから分かるようにn個の符号誤りが発生した場合、最小距離復号で訂正するためには、符号間の最小ハミング距離は最低でも2n+1必要です。