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]$.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Out of curiosity, do you have any applications in mind? $\endgroup$
    – Tsuyoshi Ito
    May 30, 2012 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, 2012 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, 2012 at 23:46

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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, 2012 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$
    – Mahdi Cheraghchi
    Jun 1, 2012 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, 2012 at 19:42

Your Answer

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