リー距離

リー距離（英: Lee distance）とは符号理論における距離の一種。q 文字からなるアルファベット {0, 1, …, q − 1}（但しq ≥ 2）上の長さ n の文字列 ${\displaystyle x_{1}x_{2}\dotsb x_{n}}$ と ${\displaystyle y_{1}y_{2}\dotsb y_{n}}$ に対して

${\displaystyle \sum _{i=1}^{n}\min(|x_{i}-y_{i}|,q-|x_{i}-y_{i}|)}$^[1]

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

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

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

例

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

歴史と応用

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

Berlekampコードは、リー距離のコードの一例である^[3]。他の重要な例に、 PreparataコードとKerdockコードがある。これらのコードは、体上で考えると非線形符号であるが、環上では線形符号となる^{[訳語疑問点][4]}。