Відстань Лі

У теорії кодування відстань Лі — відстань між двома рядками $x_{1}x_{2}\dots x_{n}$ і $y_{1}y_{2}\dots y_{n}$ однакової довжини n над q-арним алфавітом ${ 0, 1, \dots, q - 1 }$ розміру $q \geq 2$ . Це метрика^[1] що визначається як $\sum _{i=1}^{n}\min(|x_{i}-y_{i}|,\,q-|x_{i}-y_{i}|).$ Якщо $q = 2$ або $q = 3$ , відстань Лі збігається з відстанню Геммінга, оскільки обидві відстані дорівнюють 0 для двох однакових символів та 1 для двох різних символів. Для $q > 3$ це вже не так; відстань Лі між окремими буквами може бути більшою за 1. Однак, існує ізометрія Грея (бієкція зі збереженням ваги) між $\mathbb {Z} _{4}$ з вагою Лі та $\mathbb {Z} _{2}^{2}$ з вагою Геммінга.^[2]

Розглядаючи алфавіт як адитивну групу Z_q, відстань Лі між двома окремими літерами $x$ і $y$ — довжина найкоротшого шляху в графі Келі (який є круговим, оскільки група циклічна) між ними.^[3] У загальнішому випадку, відстань Лі між двома рядками довжини $n$ — це довжина найкоротшого шляху між ними в графі Келі $\mathbf {Z} _{q}^{n}$ . Це також можна розглядати як фактор-метрику, що виникає внаслідок зменшення $Z n$ на мангеттенську відстань за модулем ґратки $q Z n$ . Аналогічна фактор-метрика на факторі $Z n$ за модулем довільної ґратки відома як Мангаймська метрика або Мангаймська відстань.

Метричний простір, індукований відстанню Лі, є дискретним аналогом еліптичного простору.^[1]

Приклад

Якщо $q = 6$ , то відстань Лі між 3140 та 2543 дорівнює $1 + 2 + 0 + 3 = 6$ .

Історія та застосування

Відстань Лі названо на честь Вільяма Чі Юаня Лі (李始元). Її застосовують для фазової модуляції, тоді як відстань Геммінга використовують у випадку ортогональної модуляції.

Прикладом коду в метриці Лі є код Берлекампа.^[4] Іншими важливими прикладами є код Препарати та код Кердока; ці коди є нелінійними, якщо розглядати їх над полем, але лінійними над кільцем.^[2]

Посилання

↑ ^а ^б Deza, Elena; Deza, Michel (2014), Dictionary of Distances (вид. 3rd), Elsevier, с. 52, ISBN 9783662443422
↑ ^а ^б Greferath, Marcus (2009). An Introduction to Ring-Linear Coding Theory. У Sala (ред.). Gröbner Bases, Coding, and Cryptography. Springer Science & Business Media. с. 220. ISBN 978-3-540-93806-4.
↑ Blahut, Richard E. (2008). Algebraic Codes on Lines, Planes, and Curves: An Engineering Approach. Cambridge University Press. с. 108. ISBN 978-1-139-46946-3.
↑ Roth, Ron (2006). Introduction to Coding Theory. Cambridge University Press. с. 314. ISBN 978-0-521-84504-5.

Література

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. У Vardy, Alexander (ред.). Codes, Curves, and Signals: Common Threads in Communications. Springer Science & Business Media. ISBN 978-1-4615-5121-8.

[Deza-1] а ^б Deza, Elena; Deza, Michel (2014), Dictionary of Distances (вид. 3rd), Elsevier, с. 52, ISBN 9783662443422

[Greferath2009-2] а ^б Greferath, Marcus (2009). An Introduction to Ring-Linear Coding Theory. У Sala (ред.). Gröbner Bases, Coding, and Cryptography. Springer Science & Business Media. с. 220. ISBN 978-3-540-93806-4.

[Blahut2008-3] Blahut, Richard E. (2008). Algebraic Codes on Lines, Planes, and Curves: An Engineering Approach. Cambridge University Press. с. 108. ISBN 978-1-139-46946-3.

[Roth2006-4] Roth, Ron (2006). Introduction to Coding Theory. Cambridge University Press. с. 314. ISBN 978-0-521-84504-5.

[1]

[2]

[3]

[4]