リー距離

リー距離（英: 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]}。

参照資料

1. ^ Deza, Elena; Deza, Michel (2014), Dictionary of Distances (3rd ed.), Elsevier, p. 52, ISBN 9783662443422 
2. Blahut, Richard E. (2008). Algebraic Codes on Lines, Planes, and Curves: An Engineering Approach. Cambridge University Press. p. 108. ISBN 978-1-139-46946-3 
3. Roth, Ron (2006). Introduction to Coding Theory. Cambridge University Press. p. 314. ISBN 978-0-521-84504-5 
4. Greferath, Marcus (2009). “An Introduction to Ring-Linear Coding Theory”. In Sala. Gröbner Bases, Coding, and Cryptography. Springer Science & Business Media. p. 220. ISBN 978-3-540-93806-4 

• Lee, C. Y. (1958), “Some properties of nonbinary error-correcting codes”, IRE Transactions on Information Theory 4 (2): 77–82, doi:10.1109/TIT.1958.1057446 
• Berlekamp, Elwyn R. (1968), Algebraic Coding Theory, McGraw-Hill 
• Voloch, Jose Felipe; Walker, Judy L. (1998). “Lee Weights of Codes from Elliptic Curves”. In Vardy, Alexander. Codes, Curves, and Signals: Common Threads in Communications. Springer Science & Business Media. ISBN 978-1-4615-5121-8