ハミング距離
ハミング距離
2つの符号語 \(\boldsymbol{x}\) と \(\boldsymbol{y}\) のビット列のうち、異なるビットの個数をハミング距離といい、符号語間の距離として定義します。
定義（ハミング距離）
符号語 \(\boldsymbol{x},\boldsymbol{y}\) が
\[
\boldsymbol{x}=\begin{bmatrix} x_1 & x_2 & \cdots & x_n \end{bmatrix}
,\quad
\boldsymbol{y}=\begin{bmatrix} y_1 & y_2 & \cdots & y_n \end{bmatrix}
\]
であるとき
\[
d_H(\boldsymbol{x},\boldsymbol{y}):=\sum_{i=1}^n(x_i\oplus y_i)
\]
を \(\boldsymbol{x}\) と \(\boldsymbol{y}\) のハミング距離という。
例
符号語
\(
\boldsymbol{x}=\begin{bmatrix} 0 & 0 & 1 & 1 \end{bmatrix},~
\boldsymbol{y}=\begin{bmatrix} 0 & 1 & 1 & 0 \end{bmatrix}
\)
のハミング距離は
\[
\begin{align}
d_H(\boldsymbol{x},\boldsymbol{y})
&=(0\oplus0)+(0\oplus1)+(1\oplus1)+(1\oplus0)\\
&=0+1+0+1\\
&=2
\end{align}
\]
符号の最小距離
符号に属する、異なる2つの符号語において、最小のハミング距離を最小距離といい、次のように定義されます。
定義（最小距離）
符号 \(\mathcal{C}\) に対して
\[
d_{\mathrm{min}}:=\min_{\substack{\boldsymbol{c}_1, \boldsymbol{c}_2 \in \mathcal{C} \\ \boldsymbol{c}_1 \neq \boldsymbol{c}_2}}d_H(\boldsymbol{c_1},\boldsymbol{c_2})
\]
を符号 \(\mathcal{C}\) の最小距離という。