リー距離

リー距離（テンプレート:Lang-en-short）とは符号理論における距離の一種。q 文字からなるアルファベット {0, 1, …, q − 1}（但しq ≥ 2）上の長さ n の文字列 $x_1{x}_2\cdots x_n$ と $y_1{y}_2\cdots y_n$ に対して

$\sum _{i=1}^n\min (|x_i-y_i|,q-|x_i-y_i|)$

により定義される。アルファベットを加法群 Z_q と見做すと、長さ1の文字列である $x$ と $y$ に対するリー距離は、ケイリーグラフにおける最短経路の長さである 。

もし $q=2$ か $q=3$であれば、リー距離はハミング距離と一致する。これは、それぞれの文字に対して一致していれば0を、一致していなければ1を出力する関数の和となるからである。 $q>3$ においては、異なる文字に対して2以上を出力しうるため、ハミング距離と一致するとは限らない。

リー距離から導かれる距離空間は、離散化した楕円空間である 。

例

もしq = 6であれば、文字列「3140」と「2543」の間のリー距離は1 + 2 + 0 + 3 = 6と計算される。特に斜体にした2は、|1-5|ではなく6-|1-5|である。

歴史と応用

リー距離は、電気通信の研究者だった李建業博士（William C. Y. Lee）にちなんで命名された。リー距離は位相変調に適用され、直交変調の場合はハミング距離が使用される。

Berlekampコードは、リー距離のコードの一例である。他の重要な例に、 PreparataコードとKerdockコードがある。テンプレート:訳語疑問点範囲。

参照資料

• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Cite book