リー距離
表示
リー距離(英: Lee distance)とは符号理論における距離の一種。q 文字からなるアルファベット {0, 1, …, q − 1}(但しq ≥ 2)上の長さ n の文字列 と に対して
により定義される。アルファベットを加法群 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]。
参照資料
[編集]- ^ 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