Расстояние Ли

редактировать

В теории кодирования расстояние Ли - это расстояние между двумя строками $x 1 x 2… xn {\ displaystyle x_ {1} x_ {2} \ dots x_ {n}}$ $x_1 x_2 \ dots x_n$ и $y 1 y 2… yn {\ displaystyle y_ {1} y_ {2} \ dots y_ {n}}$ $y_ {1} y_ {2} \ dots y_ { n}$ равной длины n по q-ичной алфавит {0, 1,…, q - 1} размера q ≥ 2.

Это метрика, определяемая как

∑ i = 1 n min ( | xi - yi |, q - | xi - yi |). {\ displaystyle \ sum _ {i = 1} ^ {n} \ min (| x_ {i} -y_ {i} |, \, q- | x_ {i} -y_ {i} |).}

{\ displaystyle \ sum _ {i = 1} ^ {n} \ min (| x_ {i } -y_ {i} |, \, q- | x_ {i} -y_ {i} |).}

Рассматривая алфавит как аддитивную группу Zq, расстояние Ли между двумя отдельными буквами $x {\ displaystyle x}$ $x$ и $y {\ displaystyle y}$ $y$ - длина кратчайшего пути в графе Кэли (который является круговым, поскольку группа циклическая) между ними.

Если $q = 2 {\ displaystyle q = 2}$ $q = 2$ или $q = 3 {\ displaystyle q = 3}$ ${\ displaystyle q = 3}$ расстояние Ли совпадает с расстоянием Хэмминга, потому что оба расстояния равны 0 для двух одинаковых символов и 1 для двух одиночных неравных символов. Для $q>3 {\ displaystyle q>3}$ $q>3$ это уже не так, расстояние Ли может стать больше 1.

метрическое пространство, вызванное расстоянием Ли, равно дискретный аналог эллиптического пространства .

Пример

Если q = 6, то расстояние Ли между 3140 и 2543 равно 1 + 2 + 0 + 3 = 6.

История и применение

Расстояние Ли названо в честь. Оно применяется для фазовой модуляции, а расстояние Хэмминга используется в случае ортогональной модуляции.

Это пример кода в метрике Ли. Другими важными примерами являются код Препараты и; эти коды нелинейны, когда рассматриваются по полю, но таковы.

Также существует Изометрия серого (биекция, сохраняющая вес) между $Z 4 {\ displaystyle \ mathbb {Z} _ {4}}$ $\ mathbb {Z} _ {4}$ с и $Z 2 2 {\ отображается tyle \ mathbb {Z} _ {2} ^ {2}}$ $\ mathbb {Z} _ {2} ^ {2}$ с весом Хэмминга.

Ссылки

Lee, CY (1958), «Некоторые свойства недвоичных коды исправления ошибок ", Транзакции IRE по теории информации, 4(2): 77–82, doi : 10.1109 / TIT.1958.1057446
Берлекамп, Элвин R. (1968), Алгебраическая теория кодирования, McGraw-Hill
Voloch, Jose Felipe; Уокер, Джуди Л. (1998). "Ли веса кодов из эллиптических кривых". В Варды, Александр (ред.). Коды, кривые и сигналы: общие темы в коммуникациях. Springer Science Business Media. ISBN 978-1-4615-5121-8.