10
$\begingroup$

Is there any known construction of a linear error correcting code $\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^m$ (with reasonable parameters), such that when given a Boolean vector $v\in \{0,1\}^n$, it also returns a Boolean vector w.h.p.? (although it is over $\mathbb{F}_q$)

(that is, $\Pr[\mathsf{ECC}(v) \in \{0,1\}^m]>1-\epsilon$, where the probability is taken over uniformly choosing $v\in \{0,1\}^n$, and $\epsilon$ is arbitrarily small)

If not, what if we relax the condition to $$\Pr[\mathsf{ECC}_i(v) \in \{0,1\}]> 1-\epsilon$$ Where $\mathsf{ECC}_i$ returns the $i$'th coordinate of $\mathsf{ECC}$, $\epsilon$ is arbitrarily small, and the probability is taken both over uniformly choosing $v\in \{0,1\}^n$ and uniformly choosing a coordinate $i\in[m]$.

$\endgroup$
  • 3
    $\begingroup$ Out of curiosity, do you have any applications in mind? $\endgroup$ – Tsuyoshi Ito May 30 '12 at 19:30
  • $\begingroup$ Yes, I actually have a couple of applications for an error-correcting-code with such property. However, I think it is infeasible to explain within the scope of a comment. You can contact me by mail if you're interested. $\endgroup$ – user887 May 31 '12 at 7:01
  • $\begingroup$ Thanks for the reply. If it does not fit in a comment, I probably do not have time to understand the whole thing anyway, so I will leave it as it is. Thanks! $\endgroup$ – Tsuyoshi Ito Jun 7 '12 at 23:46
7
$\begingroup$

Yes. For example, a Reed-Solomon code contains a BCH code, which is a binary linear code, as a sub-code. These are called subfield-subcodes.

$\endgroup$
  • $\begingroup$ Does it mean that given a (linear in F_q) Reed-Solomon code, the probability that the code will return a binary codeword, given a binary input, is 1? Can you please direct me to some paper/survey in which I can read about this property in more detail? I'm a bit new to coding theory. Thanks! $\endgroup$ – user887 May 31 '12 at 6:58
  • $\begingroup$ The best reference to read about binary BCH codes is the classical text books "The Theory of Error Correcting Codes" by MacWilliams and Sloane and also "Introduction to Coding Theory" of van Lint. $\endgroup$ – MCH Jun 1 '12 at 14:43
  • 1
    $\begingroup$ @TomGur: I'm not sure that BCH codes meet your requirement. To some extent the answer depends on how much computational effort you want the decoder to put to the task. The "off the shelf" decoders are bounded distance decoders, and only correct up to unique decodability limit (< half the minimum distance). For BCH-codes a non-negligible fraction of the binary space is out of range, and a decoder error will result. Just having a code is not enough unless you specidy the decoding algorithm (not all ECCs have an efficient known one). $\endgroup$ – Jyrki Lahtonen Sep 6 '12 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy