У теорії кодування відстань Лі — відстань між двома рядками і однакової довжини n над q-арним алфавітом розміру . Це метрика що визначається як Якщо або , відстань Лі збігається з відстанню Геммінга, оскільки обидві відстані дорівнюють 0 для двох однакових символів та 1 для двох різних символів. Для це вже не так; відстань Лі між окремими буквами може бути більшою за 1. Однак, існує ізометрія Грея (бієкція зі збереженням ваги) між з вагою Лі та з вагою Геммінга.
Розглядаючи алфавіт як адитивну групу Zq, відстань Лі між двома окремими літерами і — довжина найкоротшого шляху в графі Келі (який є круговим, оскільки група циклічна) між ними. У загальнішому випадку, відстань Лі між двома рядками довжини — це довжина найкоротшого шляху між ними в графі Келі . Це також можна розглядати як фактор-метрику, що виникає внаслідок зменшення на мангеттенську відстань за модулем . Аналогічна фактор-метрика на факторі за модулем довільної ґратки відома як Мангаймська метрика або Мангаймська відстань.
Метричний простір, індукований відстанню Лі, є дискретним аналогом еліптичного простору.
Приклад Якщо , то відстань Лі між 3140 та 2543 дорівнює .
Історія та застосування Відстань Лі названо на честь Вільяма Чі Юаня Лі (). Її застосовують для фазової модуляції, тоді як відстань Геммінга використовують у випадку ортогональної модуляції.
Прикладом коду в метриці Лі є код Берлекампа. Іншими важливими прикладами є та код Кердока; ці коди є нелінійними, якщо розглядати їх над полем, але лінійними над кільцем.
Посилання
Література