リー距離

符号理論において、リー距離は、サイズq ≥ 2のq元アルファベット{0, 1, …, q − 1 }上の等しい長さnの 2 つの文字列間の距離です。これは、次のように定義される メトリック^[1]です。q = 2またはq = 3 の場合、 リー距離はハミング距離と一致 します。これは、2 つの単一の等しい記号に対して両方の距離が 0 になり、2 つの単一の等しくない記号に対して両方の距離が 1 になるためです。q > 3の場合、これは当てはまりません。単一の文字間のリー距離は 1 より大きくなる可能性があります。ただし、リー重み とハミング重みの間にはグレイ等長変換(重みを保存する一対一関係)が存在します。^[2] ${\displaystyle x_{1}x_{2}\dots x_{n}}$${\displaystyle y_{1}y_{2}\dots y_{n}}$ $${\displaystyle \sum _{i=1}^{n}\min(|x_{i}-y_{i}|,\,q-|x_{i}-y_{i}|).}$$${\displaystyle \mathbb {Z} _{4}}$${\displaystyle \mathbb {Z} _{2}^{2}}$

アルファベットを加法群Z _qと見なすと、2つの単一文字と間のリー距離は、それらの間のケイリーグラフ（群が巡回しているため循環的）における最短経路の長さである。 ^{[3]より一般的には、長さ}n の2つの文字列間のリー距離は、のケイリーグラフにおけるそれらの間の最短経路の長さである。これは、マンハッタン距離を法として格子q Z ⁿでZ ^{n を}減算した結果の商メトリックと考えることもできる。任意の格子を法としてZ ⁿの商に関する類似の商メトリックは、として知られている。${\displaystyle x}$${\displaystyle y}$${\displaystyle \mathbf {Z} _{q}^{n}}$ マンハイムメトリックまたはマンハイム距離。^[4][5]

リー距離によって誘導される計量空間は楕円空間の離散類似体である。^[1]

q = 6の場合、3140 と 2543 間の Lee 距離は1 + 2 + 0 + 3 = 6になります。

Lee 距離は、William Chi Yuan Lee (李始元) にちなんで名付けられました。これは位相変調に適用されますが、Hamming 距離は直交変調の場合に使用されます。

ベルレカンプコードはリー計量におけるコードの一例である。^{[6]その他の重要な例としては、}プレパラタコードとカードックコードがある。これらのコードは体上では非線形であるが、環上では線形である。^[2]

• Lee, CY (1958)、「非バイナリエラー訂正コードのいくつかの特性」、IRE Transactions on Information Theory、4 (2): 77–82、doi :10.1109/TIT.1958.1057446
• Berlekamp、Elwyn R. (1968)、代数符号化理論、マグロウヒル
• Voloch, Jose Felipe; Walker, Judy L. (1998)。「楕円曲線からのコードのLee重み」。Vardy , Alexander (編)。コード、曲線、信号: 通信の共通スレッド。Springer Science & Business Media。ISBN 978-1-4615-5121-8。