2
$\begingroup$

This is in continuation with this post: Geometric/Analytic techniques for constructive and asymptotic bounds in the Lee metric

Codes over alphabet $\mathbb{Z}_{q}$ of length $n$ for the Lee metric seems to be connected to spaced points on the $n$-torus since both seem to have some circular nature over each dimension. Are there any references which talks about their connection rigorously?

From wiki:

In coding theory, the "Lee distance" is a distance between two strings $x_{1} x_{2} \dots x_{n}$ and $y_{1} y_{2} \dots y_{n}$ of equal length $n$ over the $q$-ary alphabet $\{0,1,\cdots,q-1\}$ of size $q\ge2$. It is a metric, defined as

$\sum_{i=1}^n \min(|x_i-y_i|,q-|x_i-y_i|)$

If $q=2$ or $3$, the Lee distance coincides with the Hamming distance.

The metric space induced by the Lee distance is a discrete analog of the Elliptic geometry|elliptic space.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The best hit I found using IEEEXplore is the following paper by Martinez, Beivide & Gabidulin from August 2009 issue of IEEE Transactions on Inf. Theory.

============================================================

Perfect Codes From Cayley Graphs Over Lipschitz Integers

Abstract

The search for perfect error-correcting codes has received intense interest since the seminal work by Hamming. Decades ago, Golomb and Welch studied perfect codes for the Lee metric in multidimensional torus constellations. In this work, we focus our attention on a new class of four-dimensional signal spaces which include tori as subcases. Our constellations are modeled by means of Cayley graphs defined over quotient rings of Lipschitz integers. Previously unexplored perfect codes of length one will be provided in a constructive way by solving a typical problem of vertices domination in graph theory. The codewords of such perfect codes are constituted by the elements of a principal (left) ideal of the considered quotient ring. The generalization of these techniques for higher dimensional spaces is also considered in this work by modeling their signal sets through Cayley-Dickson algebras.

===========================================================

I don't know if this helps you. Lately Lee-metric has not been a very hot topic in the coding theory community. Lee metric codes experienced a brief revival in the 90s, when it was observed that several good non-linear binary codes can be viewed as isometric images of submodules of $\mathbf{Z}_4^n$ under the isometry $\mathbf{Z}_4^n\rightarrow\mathbf{Z}_2^{2n}$. Here we use the Grey map: $0\mapsto 00, 1\mapsto 01, 2\mapsto 11, 3\mapsto 10$ from $\mathbf{Z}_4$ to $\mathbf{Z}_2^2$. The metric on the mod 4 side is the Lee-metric, and on the binary side we use the Hamming metric.

From your point of view this means that you can add $q=4$ to the list of potentially very useful values. Just last year I heard about a couple of new record breaking constructions of binary codes based on this same isometry.

Improve this answer
$\endgroup$
5
  • $\begingroup$ @Jyrki Lahtonen I have seen only $q=4$ case or only even cases. I have not seen that much of odd cases. Do you know of any asymptotic results? $\endgroup$
    – user16007
    Jul 21, 2011 at 1:46
  • $\begingroup$ @unknown: You did mention the Hamming bound and Glibert-Varshamov bound in your other question. I'm not sure about the others. In the case of the Hamming metric and binary codes the best substitute to the Hamming bound is the so called linear programming bound. It's been ages, so I would need to check things. IIRC the mechanism of that bound depends on a property called 2-point homogeneity of the ambient metric space, and the Lee-metric doesn't have that property. May be the mechanisms of the Elias bound or the Plotkin bound can be generalized? $\endgroup$
    – Jyrki Lahtonen
    Jul 21, 2011 at 9:07
  • $\begingroup$ @unknown: Just recalled relatively recent studies extending the linear programming bound to Frobenius ring alphabet (Greferath, Byrne, other people from Dublin). IIRC they don't use the Lee-metric though, but something that they refer to as the homogeneous metric that somehow naturally emerges from the Frobenius ring properties. $\endgroup$
    – Jyrki Lahtonen
    Jul 21, 2011 at 9:09
  • $\begingroup$ @Jyrki Lahtonen The Frobenius ring alphabet technique looks interesting. Let me look at it. Do you know a connection of Lee-metric to codes on torus. They look very similar. But at q=5 and n=2, the number of code words are different. I am not sure why this is?? $\endgroup$
    – user16007
    Jul 30, 2011 at 0:39
  • $\begingroup$ and d=2 I believe. $\endgroup$
    – user16007
    Jul 30, 2011 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.