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

В теории кодирования расстояние Ли — это расстояние между двумя строками одинаковой длины n в q - арном алфавите {0, 1, …, q − 1 } размера q ≥ 2. Это метрика ^[1], определяемая как Если q = 2 или q = 3, расстояние Ли совпадает с расстоянием Хэмминга , поскольку оба расстояния равны 0 для двух отдельных равных символов и 1 для двух отдельных неравных символов. Для q > 3 это уже не так; расстояние Ли между отдельными буквами может стать больше 1. Однако существует изометрия Грея (сохраняющая вес биекция) между весом Ли и весом Хэмминга . ^[2] ${\displaystyle x_{1}x_{2}\dots x_{n}}$ ${\displaystyle y_{1}y_{2}\dots y_{n}}$ $${\displaystyle \sum _{i=1}^{n}\min(|x_{i}-y_{i}|,\,q-|x_{i}-y_{i}|).}$$ ${\displaystyle \mathbb {Z} _{4}}$ ${\displaystyle \mathbb {Z} _{2}^{2}}$

Рассматривая алфавит как аддитивную группу Z q , расстояние Ли между двумя отдельными буквами и является длиной кратчайшего пути в графе Кэли (который является круговым, поскольку группа является циклической) между ними. ^[3] В более общем смысле, расстояние Ли между двумя строками длины n является длиной кратчайшего пути между ними в графе Кэли . Это также можно рассматривать как метрику фактора, полученную в результате сокращения Z ⁿ с помощью манхэттенского расстояния по модулю решетки q Z ⁿ . Аналогичная метрика фактора на факторе Z ⁿ по модулю произвольной решетки известна как ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle \mathbf {Z} _{q}^{n}}$ Метрика Мангейма илирасстояние Мангейма.^[4][5]

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

Пример

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

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

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

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

Ссылки

1. Деза, Елена ; Деза, Мишель (2014), Словарь расстояний (3-е изд.), Elsevier, стр. 52, ISBN 9783662443422
2. Greferath, Marcus (2009). "Введение в теорию кольцевого линейного кодирования". В Sala, Massimiliano; Mora, Teo; Perret, Ludovic; Sakata, Shojiro; Traverso, Carlo (ред.). Gröbner Bases, Coding, and Cryptography . Springer Science & Business Media . стр. 220. ISBN 978-3-540-93806-4.
3. Блахут, Ричард Э. (2008). Алгебраические коды на линиях, плоскостях и кривых: инженерный подход . Cambridge University Press. стр. 108. ISBN 978-1-139-46946-3.
4. Huber, Klaus (январь 1994) [1993-01-17, 1992-05-21]. "Коды над гауссовыми целыми числами". IEEE Transactions on Information Theory . 40 (1): 207–216. doi :10.1109/18.272484. eISSN  1557-9654. ISSN  0018-9448. S2CID  195866926. Идентификатор журнала IEEE 9215213. Архивировано (PDF) из оригинала 2020-12-17 . Получено 2020-12-17 .[1][2] (1+10 страниц) (Примечание. Эта работа была частично представлена ​​на конференции CDS-92 в Калининграде, Россия, 7 сентября 1992 г. и на симпозиуме IEEE по теории информации в Сан-Антонио, Техас, США.)
5. Стрэнг, Томас; Дамманн, Армин; Рёкль, Матиас; Пласс, Саймон (октябрь 2009 г.). Использование кодов Грея в качестве идентификаторов местоположения (PDF) . 6. GI/ITG KuVS Fachgespräch Ortsbezogene Anwendungen und Dienste (на английском и немецком языках). Оберпфаффенхофен, Германия: Институт связи и навигации Немецкого аэрокосмического центра (DLR). CiteSeerX 10.1.1.398.9164 . Архивировано (PDF) из оригинала 1 мая 2015 г. Проверено 16 декабря 2020 г. (5/8 страниц) [3]
   • Томас Стрэнг и др. (октябрь 2009 г.). «Использование кодов Грея в качестве идентификаторов местоположения». ResearchGate (Аннотация).
6. Рот, Рон (2006). Введение в теорию кодирования . Cambridge University Press . стр. 314. ISBN 978-0-521-84504-5.

• Ли, 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.