リー距離

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

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

^[1]

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

もし $q=2$ か $q=3$ であれば、リー距離はハミング距離と一致する。これは、それぞれの文字に対して一致していれば0を、一致していなければ1を出力する関数の和となるからである。 $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]。

参照資料[編集]

^ ^a ^b Deza, Elena; Deza, Michel (2014), Dictionary of Distances (3rd ed.), Elsevier, p. 52, ISBN 9783662443422
^ 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
^ Roth, Ron (2006). Introduction to Coding Theory. Cambridge University Press. p. 314. ISBN 978-0-521-84504-5
^ 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

[Deza-1] Deza, Elena; Deza, Michel (2014), Dictionary of Distances (3rd ed.), Elsevier, p. 52, ISBN 9783662443422

[Blahut2008-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

[Roth2006-3] Roth, Ron (2006). Introduction to Coding Theory. Cambridge University Press. p. 314. ISBN 978-0-521-84504-5

[Greferath2009-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

[1]

[2]

[3]

[4]