リー距離

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

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

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

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