Odległość Lee - Lee distance

W teorii kodowania The Lee odległość jest odległość pomiędzy dwoma łańcuchów i jednakowej długości n nad q -ary alfabetu {0, 1, ...,  q  - 1} o rozmiarze q  ≥ 2. ${\ displaystyle x_ {1} x_ {2} \ kropki x_ {n}}$${\ displaystyle y_ {1} y_ {2} \ kropki y_ {n}}$

Jest to wskaźnik zdefiniowany jako

${\ Displaystyle \ suma _ {i = 1} ^ {n} \ min (| x_ {i} -y_ {i} |, \, q- | x_ {i} -y_ {i} |).}$

Biorąc pod uwagę alfabet jako grupę addytywną Z _q , odległość Lee między dwiema pojedynczymi literami i jest długością najkrótszej ścieżki na wykresie Cayleya (która jest okrągła, ponieważ grupa jest cykliczna) między nimi. ${\ displaystyle x}$${\ displaystyle y}$

Jeśli lub odległość Lee pokrywa się z odległością Hamminga , ponieważ obie odległości wynoszą 0 dla dwóch pojedynczych równych symboli i 1 dla dwóch pojedynczych nierównych symboli. Ponieważ już tak nie jest, odległość Lee może być większa niż 1. ${\ displaystyle q = 2}$${\ displaystyle q = 3}$${\ displaystyle q> 3}$

Przestrzeń metryczna indukowana odległością Lee jest dyskretnym analogiem przestrzeni eliptycznej .

Przykład

Jeśli q  = 6, to odległość Lee między 3140 a 2543 wynosi 1 + 2 + 0 + 3 = 6.

Historia i zastosowanie

Dystans Lee został nazwany na cześć CY Lee . Jest stosowany do modulacji fazy, podczas gdy odległość Hamminga jest używana w przypadku modulacji ortogonalnej.

Kod Berlekamp jest przykład kodu w Lee metryki. Inne znaczące przykłady to kod Preparata i kod Kerdock ; kody te są nieliniowe, gdy rozpatruje się je na polu, ale są liniowe na pierścieniu .

Ponadto, istnieje Grey izometrię (bijection zachowaniu masy ciała) między z masy Lee i z masy Hamminga . ${\ displaystyle \ mathbb {Z} _ {4}}$${\ displaystyle \ mathbb {Z} _ {2} ^ {2}}$

Bibliografia

• Lee, CY (1958), „Some properties of nonbinary Error- Correction 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 Wagi kodów z krzywych eliptycznych”. W Vardy Alexander (red.). Kody, krzywe i sygnały: wspólne wątki w komunikacji . Springer Science & Business Media. ISBN   978-1-4615-5121-8 .