コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

リー距離

出典: フリー百科事典『ウィキペディア(Wikipedia)』

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

[1]

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

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