Erreur booléenne corrigeant le code sur

Existe-t-il une construction connue d'un code de correction d'erreur linéaire $\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^m$ (avec des paramètres raisonnables), de sorte que lorsqu'il est donné un vecteur booléen $v\in \{0,1\}^n$ , il renvoie également un vecteur booléen whp? (bien que ce soit plus de $\mathbb{F}_q$ )

$\Pr[\mathsf{ECC}(v) \in \{0,1\}^m]>1-\epsilon$ $v\in \{0,1\}^n$ $\epsilon$

Sinon, que se passe-t-il si nous assouplissons la condition à Où renvoie la ème coordonnée de , est arbitrairement petit, et la probabilité est prise à la fois sur le choix uniforme de et sur le choix uniforme d'une coordonnée .

Pr [{E C C}_{i} (v) \in {0, 1}] > 1 - ϵ

$\Pr[\mathsf{ECC}_i(v) \in \{0,1\}]> 1-\epsilon$

{E C C}_{i}

$\mathsf{ECC}_i$

i

$i$

E C C

$\mathsf{ECC}$

ϵ

$\epsilon$

v \in {0, 1}^{n}

$v\in \{0,1\}^n$

i \in [m]

$i\in[m]$

Par curiosité, avez-vous des applications en tête?

Tsuyoshi Ito

Oui, j'ai en fait quelques applications pour un code de correction d'erreur avec une telle propriété. Cependant, je pense qu'il est impossible d'expliquer dans le cadre d'un commentaire. Vous pouvez me contacter par mail si cela vous intéresse.

Merci pour la réponse. Si cela ne rentre pas dans un commentaire, je n'ai probablement pas le temps de comprendre le tout de toute façon, donc je vais le laisser tel quel. Merci!

Tsuyoshi Ito

Réponses:

Oui. Par exemple, un code Reed-Solomon contient un code BCH, qui est un code linéaire binaire, comme sous-code. Ils sont appelés sous-sous-codes de champ.

Mahdi Cheraghchi
la source

Cela signifie-t-il que, étant donné un code Reed-Solomon (linéaire dans F_q), la probabilité que le code renvoie un mot de code binaire, étant donné une entrée binaire, est de 1? Pouvez-vous me diriger vers un document / sondage dans lequel je peux lire plus en détail sur cette propriété? Je suis un peu nouveau dans la théorie du codage. Merci!

La meilleure référence à lire sur les codes BCH binaires est les manuels classiques "The Theory of Error Correcting Codes" de MacWilliams et Sloane et également "Introduction to Coding Theory" de van Lint.

Mahdi Cheraghchi

@TomGur: Je ne suis pas sûr que les codes BCH répondent à vos besoins. Dans une certaine mesure, la réponse dépend de l'effort de calcul que vous souhaitez que le décodeur consacre à la tâche. Les décodeurs "standard" sont des décodeurs à distance bornée et ne corrigent que jusqu'à une limite de décodabilité unique (<la moitié de la distance minimale). Pour les codes BCH, une fraction non négligeable de l'espace binaire est hors de portée et une erreur de décodeur en résultera. Avoir un code ne suffit pas, sauf si vous spécifiez l'algorithme de décodage (tous les ECC n'en ont pas un connu et efficace).

Jyrki Lahtonen