リー距離のソースを表示

'''リー距離'''（{{lang-en-short|Lee distance}}）とは[[符号理論]]における[[距離函数|距離]]の一種。''q'' 文字からなる[[アルファベット]] {0, 1, …, ''q'' &#x2212; 1}（但し''q'' ≥ 2）上の長さ ''n'' の[[文字列]] <math>x_1 x_2 \dotsb x_n</math> と <math>y_1 y_2 \dotsb y_n</math> に対して

: <math>\sum_{i=1}^n \min(|x_i-y_i|,q-|x_i-y_i|)</math><ref name="Deza">{{Citation|last=Deza|first1=Elena|first2=Michel|last2=Deza|author2-link=Michel Deza|title=Dictionary of Distances|year=2014|edition=3rd|publisher=Elsevier|isbn=9783662443422|page=52}}</ref>

により定義される。アルファベットを[[巡回群|加法群 '''Z'''<sub>''q''</sub>]] と見做すと、長さ1の文字列である <math>x</math> と <math>y</math> に対するリー距離は、[[ケイリーグラフ]]における最短経路の長さである <ref name="Blahut2008">{{Cite book|first=Richard E.|last=Blahut|title=Algebraic Codes on Lines, Planes, and Curves: An Engineering Approach|year=2008|publisher=Cambridge University Press|isbn=978-1-139-46946-3|page=108}}</ref> 。

もし <math>q = 2</math> か <math>q = 3</math>であれば、リー距離は[[ハミング距離]]と一致する。これは、それぞれの文字に対して一致していれば0を、一致していなければ1を出力する関数の和となるからである。 <math>q > 3</math> においては、異なる文字に対して2以上を出力しうるため、ハミング距離と一致するとは限らない。

リー距離から導かれる[[距離空間]]は、離散化した[[楕円幾何学|楕円空間]]である<ref name="Deza">{{Citation|last=Deza|first1=Elena|first2=Michel|last2=Deza|author2-link=Michel Deza|title=Dictionary of Distances|year=2014|edition=3rd|publisher=Elsevier|isbn=9783662443422|page=52}}</ref> 。

== 例 ==
もし''q'' = 6であれば、文字列「3140」と「2543」の間のリー距離は1 + ''2'' + 0 + 3 = 6と計算される。特に斜体にした2は、|1-5|ではなく6-|1-5|である。 

== 歴史と応用 ==
リー距離は、[[電気通信]]の研究者だった李建業博士（William C. Y. Lee）にちなんで命名された。リー距離は[[変調方式|位相変調]]に適用され、直交変調の場合はハミング距離が使用される。 

Berlekampコードは、リー距離のコードの一例である<ref name="Roth2006">{{Cite book|first=Ron|last=Roth|title=Introduction to Coding Theory|date=2006|publisher=[[Cambridge University Press]]|isbn=978-0-521-84504-5|page=314}}</ref>。他の重要な例に、 PreparataコードとKerdockコードがある。{{訳語疑問点範囲|これらのコードは、[[体 (数学)|体]]上で考えると非線形符号であるが、[[環 (数学)|環]]上では[[線形符号]]となる|date=2019-10-27}}<ref name="Greferath2009">{{Cite book|editor=Sala|title=Gröbner Bases, Coding, and Cryptography|year=2009|publisher=[[Springer Science & Business Media]]|isbn=978-3-540-93806-4|chapter=An Introduction to Ring-Linear Coding Theory|first=Marcus|last=Greferath|page=220}}</ref>。

== 参照資料 ==
{{Reflist}}

* {{Citation|first1=C. Y.|last=Lee|title=Some properties of nonbinary [[error-correcting codes]]|journal=[[IEEE Transactions on Information Theory|IRE Transactions on Information Theory]]|volume=4|year=1958|pages=77–82|number=2|doi=10.1109/TIT.1958.1057446}}
* {{Citation|first1=Elwyn R.|last=Berlekamp|author-link=Elwyn Berlekamp|title=Algebraic Coding Theory|publisher=McGraw-Hill|year=1968}}
* {{Cite book|editor=[[Alexander Vardy|Vardy, Alexander]]|title=Codes, Curves, and Signals: Common Threads in Communications|year=1998|publisher=Springer Science & Business Media|isbn=978-1-4615-5121-8|chapter=Lee Weights of Codes from Elliptic Curves|first=Jose Felipe|last=Voloch|first2=Judy L.|last2=Walker}}
[[Category:符号理論]]
{{デフォルトソート:りいきより}}