3
$\begingroup$

For $n := (n_1,\dots,n_N) \in \mathbb{N}_{>1}^N$, let $X_n := \prod_{j=1}^N [n_j]$, where as usual $[m] := \{1,\dots,m\}$.

Are there any known generic constructions for (Hamming) sphere packings in $X_n$ other than the "trivial" ones that essentially embed each factor $[n_j]$ in some $\mathbb{F}_{p^{r(j)}}$ for $p$ fixed and use a $p$-ary block error-correcting code?

Note that if $n_j = q$ for all $j$ then the problem becomes one of "merely" finding good $q$-ary block error-correcting codes. The "trivial" construction above shows that the general problem posed above can also be embedded in this classical problem, albeit inelegantly and probably far from optimally.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
2
$\begingroup$

I think what you are looking for is mixed codes.

A good start point would be Brouwer--Hämäläinen--Östergård--Sloane. They are talking about mixed binary/ternary code, so for some $k$, $n_1=\cdots=n_k=2$ while $n_{k+1}=\cdots=n_N=3$. Brouwer keep an online list of known 3/2 mixed code. I think they also talked about some general cases.

Another interesting paper is Perkins--Sakhonivich--Smith. It seems to be initially cited as "mixed codes: bounds, constructions and some applications" before publication, which confused me. Fujiwara also find this reference.

Anyway, more papers can be found from the references therein or by the key word. I also find this online list with 4/3/2 mixed covering codes and many references.

update: Turbo mentioned a work of Lenstra in the comment. It already uses the term "mixed codes" on the first page.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Does number field codes by Lenstra fit here? $\endgroup$
    – Turbo
    Commented Feb 17, 2015 at 7:58
  • $\begingroup$ @Turbo, yes, it says on the first page that "they are mixed codes". Is he the first one using this term? $\endgroup$
    – Hao Chen
    Commented Feb 17, 2015 at 8:32
  • $\begingroup$ that would be very correct. $\endgroup$
    – Turbo
    Commented Feb 17, 2015 at 9:26
3
$\begingroup$

As per Hao Chen's comments, check out Lenstra's work on number field codes. Guruswami did some follow-up work couple decades later.

Improve this answer
$\endgroup$
1
$\begingroup$

As mentioned in Hao Chen's answer, what you're looking for seems to be a good mixed code. There don't seem to be many papers on this. But apparently the following paper gives the best known general upper bound on the code side:

S. Perkins, A. L. Sakhnovich, D. H. Smith, On an upper bound for mixed error-correcting codes, IEEE Transactions on Information Theory, 52 (2006), 708--712

The results given there are a little cumbersome to spell out, and I'm not an expert on this at all. So, please check what's in there for yourself. Perhaps, this is (part of) the ``mysterious paper'' Hao Chen is talking about.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks. I also find this paper by the name of the authors. I believe it IS the mysterious paper, just that they change the title. Results there seem to fit what people say when citing it. $\endgroup$
    – Hao Chen
    Commented Feb 17, 2015 at 8:24
  • $\begingroup$ @HaoChen Thanks for the info. It was a bit of a surprise to me that there are so few papers on this topic. Actually, I need an LDPC code version of mixed codes for my research now, and all I could find were a couple results... Oh, and I just noticed you edited your answer before I gave the link to the paper by Perkins, Sakhonivich, and Smith. Have my upvote for beating me to it! $\endgroup$
    – Yuichiro Fujiwara
    Commented Feb 17, 2015 at 8:32
  • $\begingroup$ @Turbo just found a new paper on the topic. It mentioned some properties of mixed code, one of them is non-linearity. This could be the disadvantage to attract people to work on it. I'll acknowledge you in my answer. $\endgroup$
    – Hao Chen
    Commented Feb 17, 2015 at 8:40
  • $\begingroup$ @HaoChen Wow, thanks. You shouldn't have. $\endgroup$
    – Yuichiro Fujiwara
    Commented Feb 17, 2015 at 8:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .