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

В теории кодирования расстояние Ли — это расстояние между двумя строками. $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 н$ с манхэттенским расстоянием по модулю решетки $q Z н$ . Аналогичная факторметрика на факторе $Z н$ по модулю произвольной решетки называется Мангеймская метрика или Мангеймское расстояние . ^{[ 4 ]}^{[ 5 ]}

Метрическое пространство , индуцированное расстоянием Ли, является дискретным аналогом эллиптического пространства . ^{[ 1 ]}

Пример

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

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

Расстояние Ли названо в честь Уильяма Чи Юань Ли ( 李始元 ). Оно применяется для фазовой модуляции , а расстояние Хэмминга используется в случае ортогональной модуляции.

Код Берлекэмпа является примером кода в метрике Ли. ^{[ 6 ]} Другими важными примерами являются код Препараты и код Кердока ; эти коды нелинейны, если рассматривать их над полем, но линейны над кольцом . ^{[ 2 ]}

Ссылки

^ Jump up to: ^а ^б Деза, Елена ; Деза, Мишель (2014), Словарь расстояний (3-е изд.), Elsevier, стр. 52, ISBN 9783662443422
^ Jump up to: ^а ^б Греферат, Маркус (2009). «Введение в теорию кольцевого линейного кодирования». В комнате, Массимилиано; Мора, Тео; Перре, Людовик; Саката, Сёдзиро; Траверсо, Карло (ред.). Базы Грёбнера, кодирование и криптография . Springer Science & Business Media . п. 220 . ISBN 978-3-540-93806-4 .
^ Блаут, Ричард Э. (2008). Алгебраические коды на прямых, плоскостях и кривых: инженерный подход . Издательство Кембриджского университета. п. 108 . ISBN 978-1-139-46946-3 .
^ Хубер, Клаус (январь 1994 г.) [17 января 1993 г., 21 мая 1992 г.]. «Коды над гауссовскими целыми числами» . Транзакции IEEE по теории информации . 40 (1): 207–216. дои : 10.1109/18.272484 . eISSN 1557-9654 . ISSN 0018-9448 . S2CID 195866926 . Идентификатор журнала IEEE 9215213. Архивировано (PDF) из оригинала 17 декабря 2020 г. Проверено 17 декабря 2020 г. [1] [2] (1+10 страниц) (Примечание. Эта работа была частично представлена на конференции CDS-92, Калининград, Россия, 7 сентября 1992 г., и на симпозиуме IEEE по теории информации, Сан-Антонио, Техас, США.)
^
Стрэнг, Томас; Дамманн, Армин; Рёкль, Матиас; Пласс, Саймон (октябрь 2009 г.). Использование кодов Грея в качестве идентификаторов местоположения (PDF) . 6-я экспертная дискуссия GI/ITG КуВС Географические приложения и сервисы (на английском и немецком языках). Оберпфаффенхофен, Германия: Институт связи и навигации Немецкого аэрокосмического центра (DLR). CiteSeerX 10.1.1.398.9164 . Архивировано (PDF) из оригинала 1 мая 2015 г. Проверено 16 декабря 2020 г. (5/8 страниц) [3]
- Томас Стрэнг; и др. (октябрь 2009 г.). «Использование кодов Грея в качестве идентификаторов местоположения» . ResearchGate (Аннотация).
^ Рот, Рон (2006). Введение в теорию кодирования . Издательство Кембриджского университета . п. 314 . ISBN 978-0-521-84504-5 .

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

[Deza-1] Jump up to: ^а ^б Деза, Елена ; Деза, Мишель (2014), Словарь расстояний (3-е изд.), Elsevier, стр. 52, ISBN 9783662443422

[Greferath2009-2] Jump up to: ^а ^б Греферат, Маркус (2009). «Введение в теорию кольцевого линейного кодирования». В комнате, Массимилиано; Мора, Тео; Перре, Людовик; Саката, Сёдзиро; Траверсо, Карло (ред.). Базы Грёбнера, кодирование и криптография . Springer Science & Business Media . п. 220 . ISBN 978-3-540-93806-4 .

[Blahut2008-3] Блаут, Ричард Э. (2008). Алгебраические коды на прямых, плоскостях и кривых: инженерный подход . Издательство Кембриджского университета. п. 108 . ISBN 978-1-139-46946-3 .

[Huber_1994-4] Хубер, Клаус (январь 1994 г.) [17 января 1993 г., 21 мая 1992 г.]. «Коды над гауссовскими целыми числами» . Транзакции IEEE по теории информации . 40 (1): 207–216. дои : 10.1109/18.272484 . eISSN 1557-9654 . ISSN 0018-9448 . S2CID 195866926 . Идентификатор журнала IEEE 9215213. Архивировано (PDF) из оригинала 17 декабря 2020 г. Проверено 17 декабря 2020 г. [1] [2] (1+10 страниц) (Примечание. Эта работа была частично представлена на конференции CDS-92, Калининград, Россия, 7 сентября 1992 г., и на симпозиуме IEEE по теории информации, Сан-Антонио, Техас, США.)

[Strang-Dammann-Roeckl-Plass_2009-5] Стрэнг, Томас; Дамманн, Армин; Рёкль, Матиас; Пласс, Саймон (октябрь 2009 г.). Использование кодов Грея в качестве идентификаторов местоположения (PDF) . 6-я экспертная дискуссия GI/ITG КуВС Географические приложения и сервисы (на английском и немецком языках). Оберпфаффенхофен, Германия: Институт связи и навигации Немецкого аэрокосмического центра (DLR). CiteSeerX 10.1.1.398.9164 . Архивировано (PDF) из оригинала 1 мая 2015 г. Проверено 16 декабря 2020 г. (5/8 страниц) [3]
Томас Стрэнг; и др. (октябрь 2009 г.). «Использование кодов Грея в качестве идентификаторов местоположения» . ResearchGate (Аннотация).

[6] Томас Стрэнг; и др. (октябрь 2009 г.). «Использование кодов Грея в качестве идентификаторов местоположения» . ResearchGate (Аннотация).

[Roth2006-6] Рот, Рон (2006). Введение в теорию кодирования . Издательство Кембриджского университета . п. 314 . ISBN 978-0-521-84504-5 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

v т и Струны
Строковая метрика	Примерное соответствие строк Алгоритм битап Расстояние Дамерау – Левенштейна Изменить расстояние Сопоставление гештальт-образцов Расстояние Хэмминга Расстояние Яро – Винклера Расстояние Ли Автомат Левенштейна Расстояние Левенштейна Алгоритм Вагнера-Фишера
Алгоритм поиска строк	Алгоритм Апостола – Джанкарло Алгоритм поиска строк Бойера – Мура Алгоритм Бойера – Мура – Хорспула Алгоритм Кнута – Морриса – Пратта Алгоритм Рабина – Карпа Алгоритм Райта Триграммный поиск Алгоритм двустороннего сопоставления строк Алгоритм сопоставления строк Чжу – Такаока
Поиск нескольких строк	Ахо – Корасик Алгоритм Комментца-Вальтера
Регулярное выражение	Сравнение механизмов регулярных выражений Регулярная грамматика Конструкция Томпсона Недетерминированный конечный автомат
Выравнивание последовательности	ВЗРЫВ Алгоритм Хиршберга Алгоритм Нидлмана – Вунша Алгоритм Смита – Уотермана
Структура данных	ДАФСА Суффиксный массив Суффиксный автомат Суффиксное дерево Обобщенное суффиксное дерево Веревка Тернарное дерево поиска Три
Другой	Разбор Сопоставление с образцом Сопоставление сжатого шаблона Самая длинная общая подпоследовательность Самая длинная общая подстрока Последовательный анализ шаблонов Сортировка Системы перезаписи строк Строковые операции