ハミング距離
ナビゲーションに移動
検索に移動
ハミング距離とは、等しい文字数の二つの文字列の対応する位置にある異なった文字の個数。 アメリカの数学者・計算機科学者、リチャード・ハミングにちなむ。信号距離とも。
概要[編集]
ハミング距離は、文字列を別の文字列に変形する際に必要な置換回数であり、 遠距離通信でのシンボル列の中で弾かれたエラーのビット数を数えるために使われる。 文字数nのシンボル列間のハミング距離は、シンボル列間の排他的論理和のハミング重み(文字列内の1の個数)や、各文字列に対応するn次元超立方体の頂点間のマンハッタン距離に相当する。
ハミング重み[編集]
ハミング重みとは、シンボル列の0以外のシンボルの個数である。典型的には、ビット列の1の個数として使われる。 ハミング重みは、0だけからなるシンボル列とのハミング距離と等しい。