Расстояние Ли - Lee distance
В теории кодирования , то Ли расстояние является расстоянием между двумя строками и равной длиной п над д -ичного алфавитом {0, 1, ..., д - 1} размером Q ≥ 2.
Это показатель , определяемый как
Рассматривая алфавит как аддитивную группу Z q , расстояние Ли между двумя отдельными буквами и является длиной кратчайшего пути в графе Кэли (который является круговым, поскольку группа циклическая) между ними.
Если или расстояние Ли совпадает с расстоянием Хэмминга , потому что оба расстояния равны 0 для двух одинаковых одинаковых символов и 1 для двух отдельных неравных символов. Поскольку это уже не так, расстояние Ли может стать больше единицы.
Метрическое пространство , индуцированное Ли расстояние является дискретным аналогом эллиптического пространства .
Пример
Если q = 6, то расстояние Ли между 3140 и 2543 равно 1 + 2 + 0 + 3 = 6.
История и применение
Дистанция Ли названа в честь CY Lee . Он применяется для фазовой модуляции, а расстояние Хэмминга используется в случае ортогональной модуляции.
Код Берлекампа является примером кода в метрике Ли. Другие важные примеры являются код Препарата и Кердок коды ; эти коды нелинейны, когда рассматриваются над полем, но линейны над кольцом .
Кроме того , существует Gray изометрии (биекция сохранения веса) между с Ли весом и с весом Хемминг .
Рекомендации
- Ли, CY (1958), "Некоторые свойства недвоичных кодов с исправлением ошибок ", IRE Сделка по теории информации , 4 (2): 77-82, DOI : 10,1109 / TIT.1958.1057446
- Берлекамп, Элвин Р. (1968), алгебраическая теория кодирования , McGraw-Hill
- Волоч, Хосе Фелипе; Уокер, Джуди Л. (1998). "Ли веса кодов из эллиптических кривых". В Варды, Александр (ред.). Коды, кривые и сигналы: общие темы в коммуникациях . Springer Science & Business Media. ISBN 978-1-4615-5121-8 .