3
$\begingroup$

Suppose we have an $[n, k+1, n-k]$ Reed Solomon code $\mathcal C$ over $\mathbb F_q$, where $n-k=d$ is the minimum distance, and suppose that $d=2t+1$. We know that for every $r \in \mathbb F_q^n$ the ball $$ B(r,t):=\left\{x \in \mathbb F_q^n \;|\; d(x,r) \leq t \right\}$$ centered in $r$ with radius $t$ contains at most one codeword $c\in \mathcal C$. Obviously also the sphere $$ S(r,t):=\left\{x \in \mathbb F_q^n \;|\; d(x,r) = t \right\}$$ has the same property. ( $d(-,-)$ is the Hamming distance).

Now fix an integer $e$ with $t<e<2t$ I have some questions.

Q1) I would like to know (or to estimate) the probability that, given an $r \in \mathbb F_q^n$, we have $$ \left|B(r,e) \cap \mathcal C\right| \geq 2.$$ In particular I am interested in the case when $e=t+1$

Q2) I would like to know (or to estimate) the probability that, given an $r \in \mathbb F_q^n$, we have $$ \left|S(r,e) \cap \mathcal C\right| =1.$$ In particular I' d like to compute it when $e=t+1$

Edit: Q3) I want to estimate the expected value of : $$ \left|B(r,t+1)\cap \mathcal C\right|, \;\;\; \mbox{ and }$$ $$ \left|S(r,t+1) \cap \mathcal C\right|$$ Thanks for your help!

$\endgroup$
3
  • $\begingroup$ Also asked at math.stackexchange.com/q/943715/18398 $\endgroup$
    – JRN
    Commented Sep 24, 2014 at 1:14
  • $\begingroup$ The first thing I would try (for the case $e=t+1$) is to analyze something like Sudan's list decoding algorithm tuned up for this case. I haven't tried it, and many pitfalls may await. $\endgroup$ Commented Oct 12, 2014 at 7:26
  • $\begingroup$ Yes, of course I've studied Sudan and Guruswami's work. In fact I'm working on a different algorithm for list decoding and this problem comes up when I try to compare their algorithm with mine. The only problem is that Sudan's algorithm works only provided that $e < n-\sqrt{nk}$ (where $k+1$ is the dimension of the code). Unfortunately for high-rate codes it could happen that $t+1\geq n-\sqrt{nk}$ (e.g. when $n=63, k=50$) $\endgroup$
    – Sfarla
    Commented Oct 12, 2014 at 14:50

0

You must log in to answer this question.

Browse other questions tagged .