Lee codes and $n$-torus - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T06:13:01Z http://mathoverflow.net/feeds/question/70595 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/70595/lee-codes-and-n-torus Lee codes and $n$-torus unknown (yahoo) 2011-07-18T07:06:56Z 2011-07-20T19:41:02Z <p>This is in continuation with this post: <a href="http://mathoverflow.net/questions/70524/geometric-analytic-techniques-for-constructive-and-asymptotic-bounds-in-the-lee-m" rel="nofollow">http://mathoverflow.net/questions/70524/geometric-analytic-techniques-for-constructive-and-asymptotic-bounds-in-the-lee-m</a></p> <p>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?</p> <p>From wiki:</p> <p>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</p> <p>$\sum_{i=1}^n \min(|x_i-y_i|,q-|x_i-y_i|)$</p> <p>If $q=2$ or $3$, the Lee distance coincides with the Hamming distance.</p> <p>The metric space induced by the Lee distance is a discrete analog of the Elliptic geometry|elliptic space.</p> http://mathoverflow.net/questions/70595/lee-codes-and-n-torus/70841#70841 Answer by Jyrki Lahtonen for Lee codes and $n$-torus Jyrki Lahtonen 2011-07-20T19:41:02Z 2011-07-20T19:41:02Z <p>The best hit I found using IEEEXplore is the following paper by Martinez, Beivide &amp; Gabidulin from August 2009 issue of IEEE Transactions on Inf. Theory. </p> <p>============================================================</p> <p>Perfect Codes From Cayley Graphs Over Lipschitz Integers </p> <p>Abstract</p> <p>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.</p> <p>===========================================================</p> <p>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. </p> <p>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.</p>